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

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

2) одно и только одно кодовое слово из вновь построенного множества / кодовых слов имеет ненулевую компоненту в локаторе а при j = оо. О, 1, п - 2.

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

Теорема 13.4.1. Пусть п = cf - \ может быть представлено в виде п = J- L. Предположим, что порождающий многочлен циклического кода W надСР (q) строится по следующему правилу. Для каждого целого числа j элежнт а является корнем многочлена g (х) тогда и только тогда, когда j или любой его q-ичный потомок кратны числу L. Тогда является мажоритарно

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

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

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

2) одно и только одно кодовое слово из множества / кодовых слов имеет ненулевую компоненту в локаторе а при / = О, 1, ...

п - 1.

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

Y = аХ +- а"-.

декодируемым кодом над GF (q) с минимальным расстоянием не меньше J.

Доказательство. По определению h (х) а" не является корнем g{x) тогда и только тогда, когда а является корнем h {х). Поэтому h (х) имеет корень а тогда и только тогда, когда ни /, ни любой его -ичный потомок не являются ненулевыми кратными L. Следовательно, как мы видели при рассмотрении дуального кода, для каждой координаты имеется / согласующихся в ней проверочных равенств.

Код является кодом над GF (q), если каждый сопряженный с корнем многочлена g (х) элемент также является корнем этого многочлена. Если а- является корнем g (х), то, поскольку / кратно L, qj кратно q- L (по модулю LJ), и, следовательно, а~ также корень g- (х). Если же а- является корнем g- (х) вследствие того, что некоторый -ичный потомок / числа / кратен L, то q-v4-ный потомок q] (mod LJ) числа qj (mod LJ) кратен qL (mod LJ). □

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

= (х - 1) (х" + х + 1),

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

Ненулевые кратные 5 равны 5 и 10; число 5 является двоичным потомком чисел 7 и 13; число 10 является двоичным потомком чисел И и 14. Следовательно, корнями Я (х) являются а, а, а, а*, а, а, а" и а*, где а - примитивный элемент поля GF (16), а корнями g (х) являются а, а, а*, а, а, а" и а". Следовательно,

g (х) = (х - 1) (х - а) (х - а) (х - а*) (х ~ а) (х - а«) X X (х - а°) = х + х + X + I,

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

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

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

Таблица 13.1

Сравнение параметров некоторых двоичных кодов, декодируемых в один шаг, с параметрами кодов БЧХ

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

13.5. СВЕРТОЧНЫЕ КОДЫ С МАЖОРИТАРНЫМ ДЕКОДИРОВАНИЕМ

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

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

Сверточный (12,6)-код, порождаемый кодером, представленным на рис. 12.3, и декодируемый декодером, представленным на рис. 12.20, может декодироваться и мажоритарно. Чтобы проде-монстировать природу мажоритарных декодеров, мы опишем два