13.4. ЦИКЛИЧЕСКИЕ КОДЫ, ОСНОВАННЫЕ НА ПЕРЕСТАНОВКАХ

Теперь опишем метод построения некоторых допускающих одношаговое мажоритарное декодирование кодов, основанный на группе аффинных перестановок (см. § 13.3). Этот метод может применяться для нахождения циклических кодов над длины при условии, что составное число, а именно что Кроме того, необходимо предположить, что не сравнимо с нулем модулю где характеристика Это условие всегда удовлетворяется для тех которые являются примитивной длиной или ее делителем.

Выберем длину кода примитивной и составной; Тогда

Обозначим второй член этого разложения через так что

Ненулевые элементы являются корнями или или Если а — примитивный элемент то являются корнями . Поэтому при каждом не кратном является корнем

Определим многочлен такой, что взаимный ему многочлен является проверочным многочленом рассматриваемого кода. При всех которые не кратны и -ичный потомок которых не кратен а является корнем Так как каждый корень является корнем многочлен кратен

Пусть многочлен, взаимный к и пусть определяется соотношением

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

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

Как мы видели ранее, является корнем многочлена

тогда и только тогда, когда не кратно Следовательно, кратно и является кодовым словом дуального кода. Поэтому все элементы множества многочленов

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

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

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

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

1) каждое кодовое слово из множества кодовых слов имеет единицу в локаторе

2) одно и только одно кодовое слово из множества кодовых слов имеет ненулевую компоненту в локаторе со при

Теперь мы можем использовать теорему 13.3.4. В самом деле, предыдущие определения были выбраны таким образом, чтобы можно было применить эту теорему. Так как код обладает свойством дважды транзитивной инвариантности, он инвариантен относительно любой аффинной перестановки. В частности, выберем

Эта перестановка переводит множество кодовых слов в другое множество кодовых слов обладающее следующими свойствами:

1) каждое кодовое слово из вновь построенного множества кодовых слов имеет единицу в локаторе

2) одно и только одно кодовое слово из вновь построенного множества кодовых слов имеет ненулевую компоненту в локаторе при

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

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

декодируемым кодом над с минимальным расстоянием не меньше

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

Код является кодом над если каждый сопряженный с корнем многочлена элемент также является корнем этого многочлена. Если а является корнем то, поскольку кратно кратно (по модулю следовательно, также корень Если же является корнем вследствие того, что некоторый -ичный потомок числа кратен то -ичный потомок числа кратен

Проиллюстрируем теорему простым примером над GF (2). Так как

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

Ненулевые кратные 5 равны 5 и 10; число 5 является двоичным потомком чисел 7 и 13; число 10 является двоичным потомком чисел 11 и 14. Следовательно, корнями являются где а — примитивный элемент поля а корнями являются Следовательно,

и код имеет восемь информационных битов.

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

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

Таблица 13.1 (см. скан) Сравнение параметров некоторых двоичных кодов, декодируемых в один шаг, с параметрами кодов БЧХ

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