9.2. Двоичные коды

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

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

являются корнями многочлена Итак, код порождается многочленом

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

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

Все коды Боуза — Чоудхури этого типа, длина которых не превосходит 255, приведены в табл. 9.1 с указанием фактического числа проверочных символов.

Рис. 9.1. Исправление ошибок некоторыми кодами Боуза — Чоудхури.

Графики зависимости скорости передачи от числа исправляемых ошибок для некоторых длин кодов показаны на рис. 9.1. Если отношение остается постоянным, то скорость передачи стремится к нулю, когда неограниченно возрастает. Справедливость этого утверждения подсказывается графиками на рис. 9.1, и, кроме того, она действительно доказана в работе |58]. Неравенство Варшамова — Гилберта показывает, что существуют и более хорошие коды. Может оказаться, что коды

Боуза — Чоудхури этого типа не обладают наибольшим возможным минимальным расстоянием для заданных длины кода и числа проверочных символов при большой длине кода, или может оказаться, что эти коды на самом деле лучше, чем мы смогли показать. Все коды этого типа, длина которых не превосходит 15, оптимальны [58], и все коды, исправляющие две ошибки, квазисовершенны и, следовательно, оптимальны [26]. Кроме того, из рис. 9.1 видно, что даже при длине, равной 1023, код близок к границе Варшамова — Гилберта и, значит, является определенно хорошим. Любое отклонение оптимального поведения этих кодов проявляется только в кодах столь длинных, что для них безнадежно пытаться установить это отклонение иначе, чем при помощи теоретического исследования.

Таблица 9.1 (см. скан) Коды Боуза-Чоудхури, порождаемые примитивными элементами порядков, меньших чем 2е:

Примеры. В последних двух примерах на стр. 159 и 160 гл. 8 рассматриваются двоичные коды Боуза — Чоудхури. Второй из этих кодов определялся условием, что вектор принадлежит коду тогда и только тогда, когда -корни многочлена где а — примитивный элемент Было показано, что в этом случае многочлен степени 20, так что получается код с минимальным расстоянием, равным 11, исправляющий все комбинации из 5 или меньше ошибок, содержащий 20 проверочных символов (поскольку длина кода равна информационных символов.

Другой код, т. е. первый из рассмотренных в гл. 8 на стр. 159 кодов, используется далее в главе для подробной иллюстрации метода

исправлення ошибок, так что здесь приводится его более детальное описание. Вектор принадлежит этому коду тогда и только тогда, когда корни причем а — примитивный, элемент Длина кода равна Было получено, что

Если в качестве х взять корень многочлена как это сделано в табл. 6.1, то и можно проверить, что Таким образом,

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

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

Следовательно, многочлен

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

Все нетривиальные коды такого типа, длина которых меньше 75, перечислены в табл. 9.2. Следует указать, что -код и

Таблица 9.2 (см. скан) Некоторые двоичные коды Боуза-Чоудхури, порождаемые непримитивными элементами:

-код был» изучены также Мрейнджем [63], [64], а -код — это код Голея (см, разд. 5.3 и [62]). Интересно отметить, что в действительности этот код исправляет все тройные ошибки, хотя метод оценки расстояния для кодов Боуза — Чоудхури позволяет сделать вывод лишь о том, что код исправляет все двойные и одиночные ошибки. Это единственный пример кода, о котором известно, что упомянутый способ позволяет найти только нижнюю оценку для числа исправляемых ошибок, но не точную границу.

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