136 гл. 5.:ЦИKЛИЧECKИE LKOДЫ

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

5.7. ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ПАКЕТЫ ОШИБОК

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

Определение 5.7.1. Циклическим пакетом длины называется вектор, все ненулевые компоненты которого расположены среди t последовательных (по циклу) компонент, первая и последняя из которых отличны от нуля.

Пакет ошибок можно описывать многочленом вида е (х) = - xb (х) (mod X" - 1), где b (х) - многочлен степени не выше t- 1 с отличным от нуля коэффициентом bf). Таким образом, b {х) описывает пакет ошибок, а x указывает начальный локатор пакета.

Синдромные многочлены s (х) для исправляющего пакеты ошибок циклического кода должны быть различными. А именно: если многочлены

S (х) = ;c) [е (х) ]

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

g (х) = х*" + х"" + х- + X + I

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

Заметим, что сумма кодового слова и исправляемого пакета не может быть равна сумме другого кодового слова и исправляемого пакета ошибок. В частности, в данном примере никакой пакет длины 6 не должен являться кодовым словом. В общем случае если линейный код исправляет все пакеты длины t и меньше, то он не может содержать в качестве кодовых слов пакеты длины 2t или меньше.

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

Теорема 5.7.2 (граница Рейгера). Ка/сдый линейный блоковый код, исправляющий все пакеты длины t и менее, должен содержать по меньшей мере 2t проверочных символов.

Доказательство. Предположим, что код исправляет все пакеты ошибок длины t и менее. Тогда он не содержит в качестве кодового слова ни одного пакета длины 2 или менее. Если два вектора принадлежат одному и тому же смежному классу, то их разность равна кодовому слову. Выберем два произвольных вектора, все компоненты которых, кроме первых 2t, равны нулю. Если эти два вектора принадлежат одному смежному классу в стандартном расположении, то их разность равна кодовому слову. Но эта разность представляет собой пакет длины 2/ и, согласно сказанному ранее, не может быть кодовым словом. Поэтому два таких вектора должны лежать в разных смежных классах, а число смежных классов должно быть по меньшей мере равным числу различных таких векторов. Всего имеется д различных векторов, все ненулевые компоненты которых содержатся в первых 2t позициях; следовательно, число смежных Классов равно по меньшей мере q", так что код содержит по меньшей мере 2t проверочных символов, □

порождает двоичный код длины 15. Перечислим все циклические пакеты ошибок длины не более 3:

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

Наиболее изученными кодами, исправляющими пакеты ошибок, являются циклические коды, и мы ограничимся рассмотрением только этого класса. Для малых t и умеренных длин кода с помощью поиска на ЭВМ было найдено много хороших циклических кодов над GF (2). Некоторые из этих кодов приведены в табл. 5.1.

Из приведенных в табл. 5.1 кодов можно построить более длинные коды методом перемежения. Чтобы из [п, )-кода получить (/«, /)-код, выберем из исходного кода / произвольных кодовых слов и укрупним кодовые слова, чередуя их символы. Если исходный код исправлял произвольный пакет ошибок длины t, то, очевидно, результирующий код будет исправлять все пакеты ошибок длины у/. Например, применяя метод перемежения к четырем копиям (31,25)-кода, получаем (124,100)-код. Так как каждый из четырех исходных кодов исправлял пакет ошибок длины 2, то новый код будет исправлять любой пакет ошибок длины 8.

Для циклических кодов метод перемежения приводит к циклическим кодам. Предположим, что исходный код порождается многочленом g{x). Тогда порождающий многочлен получаемого перемежением кода равен g (х-). Чтобы установить это, заметим, что перемежение символов нескольких информационных многочленов с последующим умножением на g (xi) дает то же самое кодовое слово, что и умножение каждого из исходных

Таблица 5.1

Некоторые двоичные циклические коды исправляющие пакеты ошибок