10.3. БЧХ-коды общего типа и 1-удлиненные БЧХ-коды

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

определяет БЧХ-коды общего типа с исправлением ошибок; при получаем частные БЧХ-коды с исправлением ошибок. Не ограничивая общности, можно считать, что так как случай совпадает со случаем где блоковая длина.

Декодирование БЧХ-кодов общего типа с исправлением ошибок может быть осуществлено следующим образом. В общем случае справедливо равенство

или, что то же самое,

и

Так как левая часть этого равенства делится на то правая часть также делится на и поэтому можно определить многочлен

Очевидно, что или

Для решения уравнения (10.31) относительно многочленов и можно использовать алгоритм 7.4. Многочлен значений ошибок задается формулой

Общая формула (10.14) для значений ошибок в данном случае запишется в виде

Здесь

Таким образом, для декодирования БЧХ-кодов общего типа можно использовать следующий алгоритм:

10.33. Алгоритм декодирования. 10.331. Определить взвешенные симметрические функции Функции можно найти по формуле где остаток от деления полученного многочлена на минимальный многочлен элемента над

10.332. Используя алгоритм 7.4, решить уравнение (10.31) относительно многочленов и

10.333. Используя процедуру Ченя отыскания корней степени из единицы над найти взаимные корни многочлена локаторов ошибок. Это определит локаторы ошибок.

10.334. Найти значения ошибок по формуле (10.32).

При алгоритм 10.33 сводится к алгоритму 10.15.

Случай также заслуживает специального рассмотрения. Если положить

то

так что

Следовательно, уравнения (10.31) и (10.32) остаются справедливыми при

БЧХ-код с на самом деле является -укороченным вариантом 1 - удлиненного БЧХ-кода, обладающего тем же числом проверочных позиций и одной дополнительной информационной позицией. В общем случае -удлиненные БЧХ-коды с блоковой длиной могут быть построены путем добавления общей проверки на четность к циклическому БЧХ-коду с блоковой длиной Например, проверочная матрица расширенного БЧХ-кода с блоковой длиной 16, исправляющего две ошибки, получается путем добавления общей

проверки на четность к проверочной матрице (5.21)

В качестве локатора этой дополнительной проверки выберем нулевой элемент поля. Так как все ненулевые локаторы являются степенями элемента а, то 0 также удобно представить в виде степени а, положив Это соглашение является чистой условностью; оно не может быть получено предельным переходом, так как не существует. Если положить также то общую проверку на четность можно интерпретировать как число ошибок, . В общем случае она представляет собой сумму значений ошибок:

Многочлен локаторов ошибок для -удлиненного БЧХ-кода определяется уравнением (10.11); многочлен значений ошибок определяется уравнением (10.34), где суммы и произведения распространяются на все локаторы ошибок, возможно включая и Если ни одна из фактических ошибок не имеет своим локатором то, как обычно, Однако если одной из ошибок соответствует локатор то что следует из (10.34) и соотношения

если для некоторого

Мы подытожим этот результат в виде теоремы.

10.36. Теорема. Для -удлиненного БЧХ-кода тогда и только тогда, когда имеется ошибка с локатором

Для декодирования -удлиненного БЧХ-кода можно использовать слабо модифицированный алгоритм 10.33. Используя теорему

10.36 на шаге 10.333, определяем наличие ошибки с локатором локаторы остальных ошибок могут быть определены с помощью процедуры Ченя. Значения всех ошибок можно затем вычислить на основании (10.32). Если произошла ошибка с локатором то ее величина определяется равенством

Эта процедура декодирования -удлиненных БЧХ-кодов может быть представлена и в другой форме. Положим

где многочлены и задаются алгоритмом 7.4 как решения уравнения

При такой формулировке ошибка с локатором определяется точно так же, как и любая другая.

Если в -удлиненном БЧХ-коде произошло не более ошибок, то их локаторы задаются корнями многочлена и их значения определяются при помощи формулы

Каждый элемент поля является локатором некоторой позиции -удлиненного частного БЧХ-кода с блоковой длиной Эти коды обладают даже большей симметрией, чем обычные БЧХ-коды; -удлиненные БЧХ-коды инвариантны не только относительно циклических перестановок и подстановок (следствие 5.82), а также относительно афинной группы подстановок над Этот результат принадлежит Питерсону. Мы начнем с теоремы 10.37, доказанной Казами и являющейся слабым обобщением теоремы Питерсона.

10.37. Теорема. Пусть а — примитивный элемент поля и пусть порождающий многочлен циклического кода с блоковой длиной над имеет вид где К — множество целых чисел по модулю Предположим, что

и если Пусть нуль поля выбран в качестве локатора общей проверки на четность в -удлиненном коде. Тогда -удлиненный код инвариантен относительно аффинной группы подстановок, т. е. относительно группы подстановок вида

Замечания. Прежде чем доказывать теорему 10.37, рассмотрим следствия из нее. Согласно следствию из теоремы Луьаса в поле характеристики тогда и толььо тогда, когда каждая цифра в -ичном представлении числа не превосходит по величине соответствующей цифры в -ичном представлении числа . В сокращенных обозначениях тогда и только тогда, когда

В случае БЧХ-кода с исправлением ошибок к тогда и только тогда, когда для к выполняется сравнение где Если то сравнимо с числом так что Следовательно, из теоремы 10.37 вытекает следующее утверждение.

10.371. Теор а (Питерсон). Каждый -удлиненный БЧХ-код над с блоковой длиной инвариантен относительно аффинной группы подстановок над

10.372. Пример. Согласно теореме 10.37, код, задаваемый проверочной матрицей (10.38), инвариантен относительно подстановки которая переводит кодовое слово в слово

Доказательство теоремы 10.37. Пусть локаторы ненулевых позиций кодового слова в исходном -удлиненном коде, а — значения символов, соответствующие этим локаторам. Пусть локаторы позиций кодового слова после подстановки. Если к то Перестановка символов в кодовом слове дает кодовое слово тогда и только тогда, тогда для всех к Согласно свойствам биномиальных коэффициентов, Согласно предположению теоремы, если к то для каждого либо либо

. В любом случае Для всех .

Казами, и Питерсон [1967] показали, что если -удлиненный циклический код инвариантен относительно аффинной группы, то к Другими словами, условия теоремы 10.37 являются не только достаточными, но и необходимыми.

Группа подстановок, действующая на множестве называется транзитивной, если для любых двух элементов существует подстановка группы, переводящая а в Аффинная группа над очевидно, транзитивна. Этим свойством обладает также циклическая группа корней степени из единицы, если

Из инвариантности -удлиненного двоичного кода относительно транзитивной группы подстановок вытекает следующее свойство его весовой структуры:

10.38. Теорема (Прейндж). Пусть — число кодовых слов веса в линейном двоичном коде с блоковой длиной и пусть А, — число кодовых слов веса в -удлиненном коде с блоковой длиной Если -удлиненный код инвариантен относительно транзитивной группы подстановок, то для всех

Доказательство. -удлиненный код содержит точно кодовых слов веса . Точно в из них локатору соответствует символ 1, и точно в из них локатору соответствует символ 0. Суммарный вес кодовых слов с весом равен Так как -удлиненный код инвариантен относительно транзитивной группы подстановок, то этот суммарный вес должен быть равномерно распределен по локаторам кода. Каждому локатору должна соответствовать 1 в кодовых словах веса Так как локатор не отличается от любого другого локатора, то

что эквивалентно утверждению теоремы,

10.39. С ледствие. Если -удлиненный линейный двоичный код инвариантен относительно транзитивной группы подстановок, то минимальный вес исходного (неудлиненного) кода нечетен.

Из теоремы Питерсона 10.371 и следствия 10.39 вытекает, что каждый двоичный БЧХ-код имеет нечетный минимальный вес.