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

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

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

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

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

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

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

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

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

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

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

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

Таблица 5.1 (см. скан) Некоторые двоичные циклические коды исправляющие пакеты ошибок

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

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

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

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

информационных многочленов на с последующим перемежением этих слов Точнее, пусть

представляют собой выбранные кодовые слова. Для формирования слова из кода-перемежения каждое из этих выбранных информационных кодовых слов растягивается вставкой между всеми символами слова нулей. Кодовое слово из кода-перемежения получается затем задержкой и сложением этих слов:

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

Замена на эквивалентна перемежеиию копий кода, порождаемого многочленом

Кроме найденных на ЭВМ кодов и получающихся из них перемежением кодов известны также коды, построенные аналитическими методами. Одним из классов таких кодов являются кода Файра. Параметры некоторых кодов Файра приведены в табл. 5.2.

Таблица 5.2 (см. скан) Параметры некоторых двоичных кодов Файра

Определение 5.7.3. Кодом Файра называется исправляющий пакеты ошибок циклический код над с порождающим многочленом

где примитивный мпогочлен над степень которого не меньше длины исправляемого пакета и который не делит Длина кода Файра равна наименьшему целому такому, что делит

Теорема 5.7.4. Длани кода Файра равна , где наименьшее целое число. такое, что делит Следовательно, если примитивен, то для этого кода

Доказательство. При возможно несколько разложений многочлена :

Так как делит то он делит и Так как он не делит то он должен делить многочлен Таким образом,

для некоторого и так как не существует меньшего для которого имеет место это разложение, то такое равно длине кода.

В частности, если примитивный многочлен степени то делит при и не делит ни при каком меньшем значении

Теорема 5.7.5. Код Файра исправляет все пакеты ошибок длины и менее.

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

Но многочлен делит для всех неотрицательных Следовательно, можно записать

Складывая эти равенства, получаем

или, что эквивалентно,

для некоторых и Но теперь в каждом из последних даух равенств можно выбрать неотрицательное целое меньшее с, так что будет умножаться на Таким образом, за счет выбора получаем

или

где так что степень многочлена в квадратных скобках не превышает . Но должен делить стоящий в квадратных скобках многочлен. Следовательно, или

или

По определению пакета ошибок оба коэффициента отличны от нуля. Следовательно, к 0 или соответственно . В любом случае Остается показать, что Но исходное соотношение

теперь приводится к виду

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

доказанным равенством противоречит выбору двух разных пакетов.

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

В качестве примера кода Файра выберем и положим равным примитивному многочлену степени 10. Тогда с и мы получаем -код, исправляющий все пакеты ошибок длнны 10 и менее.

Коды Файра являются высокоскоростными кодами с малой (при избыточностью . В этих случаях избыточность равна , что превышает границу Решера только на Метод перемежения позволяет строить из кодов Файра более длинные коды, исправляющие более длинные пакеты ошибок. Эти коды являются лучшими известными высокоскоростными кодами, исправляющими пакеты ошибок. В следующей главе мы увидим, что для этих кодов известны очень простые способы построения декодеров.