8. Коды Боуза — Чоудхури

Этот класс циклических кодов является, пожалуй, одним из наиболее интересных как с теоретической, так и с практической точки зрения. В табл. X.7 показана связь между параметрами кодов Боуза—Чоудхури [66] (звездочками отмечены коды, найденные В. Д. Колесником уже после выхода в свет работы [29]).

Таблица X.7

Код (23, 127) известен под названием кода Голея. Этот код является совершенным.

Код (7, 4, 3) совпадает с кодом Хэмминга, а целый ряд других — с кодами Мак-Дональда [например, (15, 5,

7), (31, 6, 15), (63, 6, 31) и др.] Многие коды, приведенные в табл.X.7 , неоптимальны, сюда относятся все коды , коды (25, 5, 5), (49, 7, 7) и ряд других. Простыми методами можно построить коды, параметры которых лучше, а иногда и существенно лучше, чем у некоторых из кодов Боуза — Чоудхури.

Так, например, для известен циклический код Хаффмена (7, 3, 4). Простым четырехкратным повторением комбинаций такого кода может быть образован код (28, 3, 16), который существенно лучше, чем код (39, 3, 13). При пятикратном повторении указанного кода образуется код (35, 3, 20) [код Боуза — Чоудхури (57, 3, 19)]. Наконец, при шестикратном повторении образуется код с и ( и ).

При двукратном повторении кода Хаффмена (15, 4,

8) мы имеем код (30, 4, 16), тогда как в коде Боуза — Чоудхури , и . При трехкратном повторении кода (15, 4, 8) получим код с и ( и ). Число таких примеров можно увеличить.

Наконец, обратим внимание еще на то примечательное обстоятельство, что параметры некоторых кодов, приведенных в табл. X.7, оказываются кратными параметрам одного и того же кода. Например, при параметры всех кодов Боуза — Чоудхури кратны параметрам кода с и .

А это означает, что эквивалентные коды могут быть получены простым повторением кода с и . (При трехкратном повторении образуется код с и при пятикратном с и ; при семикратном — с и ).

То же самое можно сказать и о кодах . Код (45, 5, 21) может быть получен трехкратным повторением комбинаций кода (15, 5, 7). Заметим, что при двукратном повторении последнего кода образуется код (30, 5, 14), лучший, чем коды (55, 5, 11) и (65, 5, 13), см. табл.X.7.

При решении задачи практического выбора кода следует учитывать сделанные замечания относительно оптимальности кодов Боуза — Чоудхури и синтеза кодов с параметрами, им эквивалентными (или лучше). Это тем более важно, что сочетание циклических кодов с методом повторения в ряде случаев позволяет упростить кодирующую и декодирующую аппаратуру.

Теоретические аспекты кодов Боуза—Чоудхури довольно сложны и требуют предварительного знакомства с рядом специальных разделов высшей алгебры. Подробное изложение этого вопроса читатель может найти в работе [29]. Далее будут приведены некоторые положения из теории кодов Боуза — Чоудхури, в какой-то мере поясняющие связь между параметрами указанных кодов.

Если порождающий полином бинарного кода Боуза — Чоудхури обладает тем свойством, что его корнями являются элементы поля :

(X.8.1)

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

(X.8.2)

В (X.8.1) — примитивный элемент поля . Порождающий полином кодов Боуза—Чоудхури представляется в виде произведения полиномов:

(X.8.3)

Каждый полином имеет в качестве своих корней элементы поля

(X.8.4)

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

(X.8.5)

Значиость кодов Боуза — Чоудхури определяется порядком элемента а и по уже указанным причинам

(X.8.6)

Если в (X.8.1) элемент а не является примитивным [корнями полинома являются некоторые другие элементы поля , то при и

(X.8.7)

значность кода по-прежнему определяется порядком [например, при [поле GF (64)] и значность кода ()].

Корни полинома в случае (X.8.4) удовлетворяют условию, по форме совпадающему с (X.8.4):

(X.8.8)

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

В заключение отметим, что существуют полиномы, среди корней которых не содержатся все корни, требующиеся по Боуза — Чоудхури, но порождающие коды с . Сюда относится упоминавшийся уже код Голея. В связи с этим первостепенное значение приобретают задачи по разложению на множители полиномов, в частности двучлена , и исследование корректирующих возможностей кода, порождаемого полиномом с заданными алгебраическими свойствами [105—106].