Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 9.3. Негациклические коды9.31. Определение. Негациклическим кодом с блоковой длиной Так как Отметим повторно, что корни многочлена Остальные восемь нечетных степеней Этот способ описания негациклических кодов обладает тем преимуществом, что сразу задает уравнения для определения локаторов ошибок. Если
Отсюда вытекает и тождество Ньютона для производящей функции:
В случае негациклических кодов все коэффициенты при четных степенях
Тождество Ньютона можно теперь записать в виде уравнения
которое распадается на два уравнения
и
Умножим первое уравнение на а и вычтем из него второе, умноженное на а. Тогда
Уравнение (9.33) может быть решено при достаточно разумных ограничениях. Основной результат содержится в теореме 9.34. 9.34. Теорема. Если среди корней порождающего многочлена негациклического кода над Замечания. Прежде чем доказывать эту теорему, приведем таблицу 9.1, в которой записаны параметры некоторых кодов, удовлетворяющих условиям теоремы. Большим Таблица 9.1 (см. скан) Значения параметров некоторых негациклических кодов, описываемых теоремой 9.34 числам Доказательство теоремы 9.34. Приводимое доказательство является конструктивным и задает эффективную процедуру декодирования. Начнем с уравнения
Так как
Вводя производящую функцию
получим, что
или
Хотя с первого взгляда это уравнение может показаться громоздким, на самом деле оно решается тривиальным образом, поскольку каждый коэффициент
Дополнительные трудности возникают при определении коэффициента Так как
очевидно, получим
и
так что
Мы теперь утверждаем, что если произошло не более
и являются взаимно простыми. Последнее утверждение вытекает из того факта, что никакие два взаимных корня многочлена Учитывая эти условия (9.35), можно решить уравнения (9.35) относительно
Подытожим процедуру декодирования в виде алгоритма: 9.36. Алгоритм декодирования негациклических кодов, описанных теоремой 9.34. 1. Вычислить
2. Вычислить
3. Используя алгоритм 7.4, найти
как решения уравнений 4. Положить 5. Используя процедуру Ченя, вычислить многочлены а
но
то кратность ошибки равна к. В этих уравнениях знаку минус соответствует положительная ошибка и наоборот. Если требуется большая скорость вычислений и имеется достаточно много вычислительных регистров, то процедуру Ченя можно применять к каждому из многочленов С другой стороны, если число вычислительных регистров недостаточно, а время вычисления не ограничено, то процедуру Ченя можно применять только к многочленам аист. Подходящее программирование позволяет вычислять производные только тогда, когда они необходимы, не прерывая процедуру Ченя для а Хотя теорема 9.34 определяет достаточно мощный класс негациклических кодов с практически приемлемым алгоритмом декодирования, естественным является желание освободиться от ограничения Задачи(см. скан) (см. скан)
|
1 |
Оглавление
|