10.3. Другие коды, исправляющие пачки ошибок

Коды Файра образуют самый обширный известный класс кодов, исправляющих пачки ошибок. Они пригодны для целой области длин пачек и длин кодов Найдены также другие коды; для некоторых из них требуется меньшее число проверочных символов, чем для соответствующих кодов Файра. Такие коды перечисляются в этом разделе. Все эти коды могут быть реализованы методами, описанными в разд. 10.5 и 10.6.

Коды Хэмминга можно рассматривать как коды, исправляющие пачки ошибок длины 1. Интересно отметить, что для кода Файра, исправляющего пачки ошибок длины так что это код второго типа из недвоичных кодов Хэмминга, описанных в разд. 8.8.

Двоичные коды, исправляющие все пачки ошибок длины 2 или меньше, — это просто коды, которые исправляют одну ошибку и две соседние ошибки. В качестве такого кода может быть использован циклический код Хэмминга, исправляющий одну ошибку и обнаруживающий две ошибки, с изменением, состоящим в том, что когда обнаруживаются две ошибки, то предполагается, что произошли ошибки на двух соседних местах. Это коды Эйбрамсона [120].

Эйбрамсон [122] пытался также найти двоичные циклические коды для исправлений, пачек ошибок, обладающие минимальной избыточностью. Для циклических кодов каждый циклический сдвиг некоторого образующего смежного класса может быть выбран в качестве образующего нового смежного класса в соответствии с теоремой 11.2, а если это уже сделано, то граница, полученная нами в теореме 4.9, может быть преобразована следующим образом. Общее число пачек ошибок длины или меньше равно и каждая может начинаться с любого из символов кода. Таким образом, общее число смежных классов, одним из которых является сам код, равно

Эйбрамсон показал что если наибольшее целое число, удовлетворяющее неравенству (10.6) для двоичного кода, исправляющего пачки ошибок длины 3, то многочлен, порождающий код, должен иметь вид

где примитивный многочлен четной степени, превосходящей 2. Кроме того, он придумал упрощенный критерий для определения того, пригоден ли некоторый многочлен и нашел, в частности, коды, перечисленные в табл. 10.1. Кажется очень правдоподобным, что для всех четных степеней, превосходящих 2, существуют примитивные многочлены задающие по правилу 10.7 многочлены которые порождают коды, исправляющие все пачки ошибок длины 3 или меньше.

Таблица 10.1 (см. скан) Образующие многочлены для кодов, исправляющих три соседние ошибки и обладающих минимальной избыточностью

Мелас [52] заметил, что в некоторых случаях произведение двух примитивных многочленов порождает циклические коды, исправляющие пачки ошибок. Рейгером [66] и Файром [86] рассматривались укороченные циклические коды, порождаемые примитивными многочленами, и Рейгер составил таблицу нескольких кодов такого типа, исправляющих пачки ошибок. Единственный известный способ нахождения порождающих многочленов для кодов обоих типов — это метод испытаний и ошибок.

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

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

Доказательство. Доказательство представляет собой лишь незначительную модификацию доказательства теоремы 10,1. В самом деле, если то приложима теорема 10.1, поэтому достаточно провести доказательства только для Как и прежде, справедливы равенства (10.4) и (10.5), однако теперь так что равенство (10,5) записывается в виде

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

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

Таким образом,

и так как то разность должна делиться на Далее, так как многочлены и X взаимно просты и степень больше степени многочлена делится на только в том случае, когда многочлен делится на Если 1 делится на то разность должна делиться на порядок корней многочлена так же как и на Таким образом, разность должна делиться на длину кода Это невозможно, и, следовательно, если делится на многочлен то не может делиться на . Ч. т. д.