4.8. Коды, исправляющие пачки ошибок

Для любого линейного -кода, исправляющего пачки ошибок длины и меньше, должно выполняться следующее соотношение Рейджера [57] (утверждение 3.7):

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

где Следовательно, для того чтобы код исправлял пачки ошибок длины и менее, необходимо, чтобы для произвольных многочленов таких, что и любых целых чисел выполнялось соотношение

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

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

Теорема 4.10. Если (укороченный) циклический с порождающим многочленом исправляет пачки ошибок длины и менее, то (укороченный) циклический -код с порождающим многочленом исправляет пачки ошибок длины и менее.

Доказательство. Так как С — циклический код, то Следовательно, так что также является

циклическим кодом. Для любого многочлена и любого имеет место равенство где Если многочлены целые числа такие, что то

(здесь индекс у вычисляется по модулю Обозначим левую часть последнего равенства через Заметим что только в том случае, если Следовательно, . Поскольку это противоречит тому, что код С исправляет пачки ошибок длины и менее, то

т. е. код исправляет пачки ошибок длины и менее. Следующая теорема принадлежит Файру [9, 58].

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

Доказательство. Предположим, что для многочленов и целого таких, что

имеет место следующее сравнение:

Пусть остаток, а частное от деления на . Так как

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

а поэтому

Так как неприводим и то

По предположению так что

Поскольку то это противоречит тому, что является минимальным целым числом, таким, что

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

Коды, введенные в этом следствии, называют кодами Файра [58]. Код Файра имеет более чем проверочных символов, что на больше, чем нижняя граница Рейджера, равная Для длин кодов до нескольких тысяч построены «вручную» или с помощью вычислительных машин таблицы порождающих многочленов лучших циклических и укороченных циклических кодов, исправляющих пачки ошибок [60—65].

Утверждение 4.30 [66]. Пусть С — укороченный циклический код с порождающим многочленом исправляющий пачки ошибок длины и меньше. Если минимальный вес С равен то код С исправляет все случайные ошибки веса и менее, а кроме того, все пачки ошибок длины и менее.

Краткое доказательство. Если то утверждение очевидно. Предположим, что Пусть -многочлен ошибок. Положим

1) Если вес многочлена не больше чем то

2) Если или если пачка ошибок длины или менее, то

Следовательно, остатки от деления векторов ошибок типа 1 и типа 2 на различны, а поэтому принадлежат различным смежным классам.

Кодами, подобными кодам из утверждения 4.30, которые могут исправлять как случайные ошибки, так и пачки ошибок, являются коды, описанные ниже, а также коды, которые получаются, когда в качестве многочленов в утверждении 4.30 используются порождающие многочлены БЧХ-кодов, а также некоторые другие многочлены [66, 67].

Вообще говоря, если в -коде над элементы заменить на их представления в виде векторов размерности над то можно получить -код над Если исходный код линейный, то полученный таким образом код также будет линейным. Однако если исходный код является циклическим, то получающийся код может не быть циклическим. Возьмем в качестве исходного кода -ичный -код Рида — Соломона, исправляющий ошибок. Пусть -ичный линейный -код, получающийся указанным выше способом. Непосредственно из построения кода С можно видеть, что он исправляет все пачки ошибок длины и менее, а также все случайные ошибки веса и менее. Аналогичные коды можно построить, если вместо кода Рида — Соломона использовать коды из примера 4.5.

Утверждение 4.31. Описанный выше код С исправляет любые I или менее пачек ошибок длины и менее.