9.3. Негациклические коды

9.31. Определение. Негациклическим кодом с блоковой длиной над простое нечетное число, называется множество кратных порождающего многочлена делящего многочлен над Отношение называется проверочным многочленом

Так как то корни многочлена совпадают с теми корнями многочлена которые не являются корнями многочлена Если а — примитивный корень многочлена то его нечетные степени суть корни многочлена а четные степени — корни многочлена

Отметим повторно, что корни многочлена являются нечетными степенями примитивного корня из единицы степени. Следовательно, как порождающий многочлен, так и проверочный многочлен негациклического кодасблоковойдлиной/гмогутбыть удобно описаны указанием их корней, являющихся нечетными степенями одного примитивного корня из единицы степени. Для кода, исправляющего двойные ошибки, с блоковой длиной 12 над описанного в предыдущем разделе, корни порождающего многочлена суть а сопряженные к ним над это

Остальные восемь нечетных степеней являются корнями проверочного многочлена.

Этот способ описания негациклических кодов обладает тем преимуществом, что сразу задает уравнения для определения локаторов ошибок. Если корень порождающего многочлена, то, вычисляя значение полученного многочлена при декодер сразу получает сумму степеней локаторов ошибок, Зная эти декодер должен далее определить взаимные корни многочлена локаторов ошибок задающие локаторы ошибок. Соотношения между величинами описываются тождествами Ньютона, к рассмотрению которых мы и переходим. Пусть где не обязательно различны. Тогда

Отсюда вытекает и тождество Ньютона для производящей функции:

В случае негациклических кодов все коэффициенты при четных степенях в производящей функции 5 первоначально не известны. Поэтому удобно исключить эти члены с помощью разбиения тождества Ньютона на две части.

Тождество Ньютона можно теперь записать в виде уравнения

которое распадается на два уравнения

и

Умножим первое уравнение на а и вычтем из него второе, умноженное на а. Тогда

Уравнение (9.33) может быть решено при достаточно разумных ограничениях. Основной результат содержится в теореме 9.34.

9.34. Теорема. Если среди корней порождающего многочлена негациклического кода над содержатся элементы где то этот код исправляет все ошибки, вес Ли которых

Замечания. Прежде чем доказывать эту теорему, приведем таблицу 9.1, в которой записаны параметры некоторых кодов, удовлетворяющих условиям теоремы. Большим и сравнительно малым

Таблица 9.1 (см. скан) Значения параметров некоторых негациклических кодов, описываемых теоремой 9.34

числам проверочных позиций обычно соответствуют примитивные коды с блоковой длиной вида Однако имеются также сравнительно хорошие непримитивные коды этого типа с другой блоковой длиной; эти коды в таблице отмечены единичкой.

Доказательство теоремы 9.34. Приводимое доказательство является конструктивным и задает эффективную процедуру декодирования.

Начнем с уравнения

Так как то можно разделить обе части равенства на

Вводя производящую функцию

получим, что

или

Хотя с первого взгляда это уравнение может показаться громоздким, на самом деле оно решается тривиальным образом, поскольку каждый коэффициент выражается через некоторые коэффициенты и ранее определенные коэффициенты:

Дополнительные трудности возникают при определении коэффициента так как при этом нужно выполнять деление на нуль поля Однако, согласно предположению теоремы, и при вычислении этого затруднения нет.

Так как нечетная функция от то можно ввести производящую функцию с помощью уравнения Очевидно, что Если коэффициенты известны, то это уравнение позволяет рекурсивным образом вычислить коэффициенты Так как то, введя многочлены

очевидно, получим

и

так что

Мы теперь утверждаем, что если произошло не более ошибок, то удовлетворяют дополнительным условиям

и являются взаимно простыми.

Последнее утверждение вытекает из того факта, что никакие два взаимных корня многочлена не дают в сумме нуля. Действительно, в этом случае не может иметь делителей положительной четной степени и, следовательно, , так же как и , взаимно просты.

Учитывая эти условия (9.35), можно решить уравнения (9.35) относительно с помощью алгоритма 7.4:

Подытожим процедуру декодирования в виде алгоритма:

9.36. Алгоритм декодирования негациклических кодов, описанных теоремой 9.34.

1. Вычислить при помощи уравнения

2. Вычислить при помощи уравнения

3. Используя алгоритм 7.4, найти

как решения уравнений

4. Положить

5. Используя процедуру Ченя, вычислить многочлены а для , где а — примитивный корень из единицы степени, соответствующие степени которого задают локаторы позиций кода. Если а то в позиции кода произошла положительная ошибка; если то в позиции кода произошла отрицательная ошибка. В любом из этих случаев кратность ошибки может быть определена с помощью производных от и . Если для

но

то кратность ошибки равна к. В этих уравнениях знаку минус соответствует положительная ошибка и наоборот.

Если требуется большая скорость вычислений и имеется достаточно много вычислительных регистров, то процедуру Ченя можно применять к каждому из многочленов

С другой стороны, если число вычислительных регистров недостаточно, а время вычисления не ограничено, то процедуру Ченя можно применять только к многочленам аист. Подходящее программирование позволяет вычислять производные только тогда, когда они необходимы, не прерывая процедуру Ченя для а

Хотя теорема 9.34 определяет достаточно мощный класс негациклических кодов с практически приемлемым алгоритмом декодирования, естественным является желание освободиться от ограничения поскольку возможна ситуация, когда кратность ошибки больше, чем Очевидное решение — использование кода, корни порождающего многочлена которого содержат другие подходящие нечетные степени элемента а. Если элементов оказалось недостаточно, то, возможно, помогут элементы ? К сожалению, эта гипотеза также не проходит. Причины этого будут ясны из теоремы 11.65.

Задачи

(см. скан)

(см. скан)