Основные понятия и определения теории информации и кодирования. Задачи теории информации и кодирования, страница 36

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

ЦИКЛИЧЕСКИМ ПАКЕТОМ длины t называется вектор,все ненулевые компоненты которого расположены среди t последовательных (по циклу) компонент,первая и последняя из которых отличны от нуля.

Пакет ошибок можно описывать полиномом вида e(X) = X^i * b(X) *

* (mod X^n-1),где b(X) - полином степени не выше t - 1 с отличным от нуля коэффициентом b0.Таким образом,b(X) описывает пакет ошибок, а X^i указывает начальный локатор пакета.

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

S(X) = R g(X) [e(X)]

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

НАПРИМЕР,полином

g(X) = X^6 + X^3 + X^2 + X + 1

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

e(X) = X^i,                                       i = 0,...,14,

e(X) = X^i(1 + X)(mod X^15 - 1),                  i = 0,...,14,

e(X) = X^i(1 + X^2)(mod X^15 - 1),                i = 0,...,14,

e(X) = X^i(1 + X + X^2)(mod X^15 - 1),            i = 0,...,14.

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

g(X) циклический код позволяет исправлять все пакеты длины 3.

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

Каждый ЛИНЕЙНЫЙ БЛОКОВЫЙ КОД,ИСПРАВЛЯЮЩИЙ ВСЕ ПАКЕТЫ ДЛИНЫ t И МЕНЕЕ,ДОЛЖЕН СОДЕРЖАТЬ ПО МЕНЬШЕЙ МЕРЕ 2t ПРОВЕРОЧНЫХ СИМВОЛОВ.

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

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

М Е Т О Д   П Е Р Е М Е Ж Е Н И Я .

Из приведённых в таблице кодов можно построить более длинные коды методом перемежения.Чтобы из (n,k) - кода получить (jn,jk) - код, выберем из исходного кода j произвольных кодовых слов и укрупним кодовые слова,чередуя их символы.

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

───────────────────────────────────────────────────────────────────

Порождающий полином           │    Параметры   │   Длина пакета

───────────────────────────────────────────────────────────────────

X^4+X^3+X^2+1                  │   (7,3)        │        2

X^5+X^4+X^2+1                  │   (15,10)      │        2

X^6+X^5+X^4+X^3+1              │   (15,9)       │        3

X^6+X^5+X^4+1                  │   (31,25)      │        2

X^7+X^6+X^5+X^3+X^2+1          │   (63,56)      │        2

X^8+X^7+X^6+X^3+1              │   (63,55)      │        3

X^12+X^8+X^5+X^3+1             │   (511,499)    │        4

X^13+X^10+X^7+X^6+X^5+X^4+X^2+1│   (1023,1010)  │        4

───────────────────────────────────────────────────────────────────