<< Предыдущая

стр. 36
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

символов. На его базе строится (224,184)-код Файера, способный об-
наруживать все пакеты ошибок длиной до 40 символов, или исправ-
лять все пакеты длиной до 12 символов. Этот код может эффективно
бороться с замираниями и используется в мобильной связи GSM для
защиты канала управляющей информации SACCH (Slow Associated
Control Channel). •.
-

'Для определенности, здесь и в дальнейшем будем считать, что кодовый вектор
поступает в канал начиная со старших разрядов, которые соответствуют стар-
шим степеням многочлена. - Прим. перев.
3.12. Укороченные коды 201^

Таблица 3.9. (6,3)-код.

Вход Кодовое слово
000 000 000
100 П О 100
010 011 010
ПО 101 П О
001 Ш 01
0
001 101
101
011 100 011
ш 010 111




Из примера кода Файера видно, что использование при кодирова-
нии простого дополнения информационного слова нулями практиче-
ски неприемлемо, поэтому должен применяться более эффективный
метод кодирования укороченных кодов.
Пример: Укороченный (б,3)-код. .
Рассмотрим метод кодирования и декодирования кода, получен-
ного укорочением (7,4)-кода Хэмминга. Выберем из множества кодо-
вых слов базового кода все кодовые слова, начинающиеся с символа
«0». Выбрасываемые при укорочении символы полагаются равными
нулю и, поэтому, не передаются. Таким образом получаем укорочен-
ный (6,3)-код. В левой части таблицы 3.3 приведены кодовые слова
(7,4)-кода Хэмминга, у которых старший разряд равен нулю. Выбра-
сывая из этих слов лишние нули, получаем кодовые слова укорочен-
ного (6,3)-кода (см. табл. 3.9).

Замечание. Построенный (6,3)-код не является циклическим, так
как циклический сдвиг кодовых слов не во всех случаях является
кодовым словом, однако, его конструкция позволяет использовать
свойства циклических кодов при декодировании.

Проверим таблицу 3.9 с помощью алгоритма деления Евклида.
Рассмотрим информационный вектор и = (101), многочлен которого
и(Х) = 1 + X2. Умножая и(Х) на X3 и используя алгоритм деле-
ния Евклида (см. табл. 3.10), получим многочлен остатка от деления
Х3и(Х) на д(Х) = 1 + X + X3, равный Ь{Х) = X2. Таким образом,
202 Глава 3. Циклические коды
ч


Таблица 3.10. Определение проверочных символов (алго-
ритм деления Евклида) для и(Х) = 1 + X
3
ng(X) = \+Х + Х.


X
3 2
1
Л"5 X4 А" AT

= х3 и(Х)
0 0
1 1 0
0
2
0 0 9(Х)
1 1 1
0 =X
3
и(Х) + X д(Х) = Ь(Х)
3
0 0
1 =X
- -
-




многочлен систематического (6,3)-кода равен
+ Ъ(Х) = Х3[Х2 + 1] + X2 = X5 + X 3 + X2,
v(X) = Х3и(Х) (3.91)

что соответствует кодовому вектору v = (001 101) из табл. 3.9.
За основу кодера систематического (6,3)-кода может быть при-
нята схема кодирования, приведенная на рис. 3.8. Так как (6,3)-код
образуется укорочением (7,4)-кода Хэмминга, схема рис. 3.8 суще-
ственно упрощается: из регистров удаляются разряды из и VQ И ко-
дирование заканчивается уже после третьего такта.
Для практической реализации декодера укороченного кода име-
ются три альтернативы:
1. Для декодирования (6,3)-кода можно, в принципе, использо-
вать декодер базового (7,4)-кода Хэмминга (см. рис. 3.20). В
этом случае, к принятому слову приписывается недостающий
ноль и процесс декодирования занимает столько же тактов,
сколько требуется для декодера базового кода.
Для декодирования кодов с Z-кратным укорочением необходимо
затратить I дополнительных тактов. В случае, когда / велико
(как, например, в случае кода Файера) такой метод декодиро-
вания неприемлем.
2. При коррекции ошибок и модификации синдрома принимают-
ся во внимание особенности конструкции укороченного кода.
Схема декодера (6,3)-кода приведена на рис. 3.22. Здесь векто-
ру ошибки е = (000 001) в компоненте г$, согласно табл. 3.6,
соответствует синдром s = (1,1,1), поэтому, схема распознава-
ния ошибок настраивается на этот синдром (а не на синдром
(101) в случае (7,4)-кода). Рассмотрим теперь алгоритм моди-
фикации синдрома. В нижнем регистре вычисляются синдро-
мы всех сдвигов ошибки в слове базового (7,4)-кода (эта схема
3.12. Укороченные коды


«не знает об укорочении») и следующим за синдромом «111»
будет синдром «101». В соответствии с его числовым вектором
и производится модификация текущего синдрома на рис. 3.22.

Замечание. В силу линейности кодов и схем их реализации,
рассмотренный метод декодирования может быть применен
для любых укорочений кода Хэмминга.

Такой метод декодирования, в ряде случаев, приводит к доста-
точно простой схеме построения декодеров и, поэтому, весьма
интересен для практики. В качестве примера в [4] приведена
схема декодирования укороченного (272,260)-кода.

3. Этот вариант построения декодера Меггита особенно интере-
сен для практики, так как используемые в нем алгоритмы рас-
познавания ошибок и коррекции синдрома не зависят от дли-
ны укорочения I и строятся с наименьшими затратами. Длина
укорочения учитывается путем умножения принятого слова на
некоторый многочлен, зависящий от I.

Принятое из канала • Выходной
регистр


Исправление
ошибок


Модификация
синдрома




Рис. 3.22. Декодер Меггитта укороченного (6,3)-кода Хэм-
мига.

На примере укороченного (6,3)-кода мы покажем, как могла бы
выглядеть оптимальная процедура распознавания ошибки в компо-
ненте 75 и коррекции соответствующзго синдрома. Как уже отмеча-
*
лось ранее, в нижнем регистре рис. 3.22 производится вычисление
синдромов циклических сдвигов вектора ошибки для неукороченно-
го (7,4)-кода Хэмминга, поэтому таблицу 3.6 можно использовать и
для (6,3)-кода с учетом того, что первым вычисляется синдром для
Глава 3. Циклические ковы

в5 = (000 0010). На последующих тактах в нижнем регистре вычис--
ляются синдромы для

1 ]
е 6 = 4 ' = (000 0001), е 0 = ef = (100 0000),

е2 = ef] = (001 0000)
е, = 4 3 ) = (010 0000),
и т. д. Наиболее благоприятным с точки зрения затрат на модифи-
кацию в схеме рис. 3. 22 является синдром s = (0,0,1). Из таблицы
3.6 следует, что этот синдром соответствует вектору ошибки

е 2 = 4 4 ) = (001 0000),

т.е. ошибке в компоненте гг- Таким образом, для реализации опти-
мальной процедуры исправления ошибки и коррекции синдрома в
схеме рис. 3.22 необходимо предварительно произвести четыре цик-
лических сдвига верхнего и нижнего регистров (при этом верхний
регистр должен быть модифицирован: в него должны быть добавлен
дополнительный разряд г% и цепь обратной связи (Прим. переводчи-
ка)).
На примере укороченного (6,3)-кода может показаться, что эти
затраты не слишком велики, однако, для используемого в сети GSM
кода Файера миллион и более сдвигов плюс затраты на модифи-
кацию регистра оказываются технически неприемлемыми. Ниже мы
теоретически покажем, что дополнительные затраты такого рода от-
нюдь не. являются необходимыми. После этого мы рассмотрим по-
строение схемы оптимального декодера укороченного (6,3)-кода.
Будем искать схему построения декодера укороченного кода, в
которой технические затраты на исправление ошибки и коррекцию
синдрома были бы минимальными. Так как базовый (п, &)-код яв-
ляется циклическим, эта схема должна обнаруживать и исправлять
ошибку в младшем разряде кодового слова укороченного (п—I, к — I)-
кода. Многочлен такой ошибки имеет вид

е{Х) = Хп˜1-\ (3.92)

где I - длина укорочения.
Постараемся найти линейную операцию, отображающую е(Х) в
некоторый вспомогательный многочлен е'(Х), синдром которого при
е(Х) = Хп˜1˜1 был бы равен

s'{X) = Xn-k˜l. (3.93)
3.12. Укороченные коды 205J

Пусть такая операция отображает многочлен е(Х) = Хп˜х˜1 в

п к 1
(3.94)
е'(Х) = Х ˜ - .

Так как степень многочлена е'(Х) меньше степени д(Х), равенство
п к 1
(3.93) остается справедливым. Заметим, что е'(Х) = Х ˜ ˜ можно
п 1 1
получить из многочлена е(Х) = Х ˜ ˜ , г-кратным циклическим
сдвигом, то есть
. (3.95)
е!(Х) = е^{Х),

где
(3.96)
i = п - к + I.

При этом после / + 1 первых сдвигов е'(Х) = Х°, а после оставшихся
п — к — 1 сдвигов выполняются равенства (3.94) и (3.93). Постара-
емся заменить операцию г-кратного циклического сдвига линейной
операцией умножения многочленов.
Из соотношения (3.9) следует, что в нашем случае справедливо
равенство
Х*е{Х) = q(X){Xn + 1) + е«(Х), (3.97)

где д(Х) - некоторый многочлен, конкретное значение которого не
представляет для нас интереса. Согласно теореме 3.2.5, порождаю-
щий многочлен д(Х) делит Хп + 1 без остатка, поэтому можно за-
писать
(Хп + 1) = а1(Х)д(Х).
- - (3.98)

Применяя алгоритм деления Евклида, сомножитель X* можно пред-
ставить в виде
Х{ = а2(Х)д(Х) + d(X), (3.99)

где deg[d(X)] < deg[g(X)}.

Подставляя (3.98) и (3.99) в (3.97), имеем

+ d(X)]e(X) - q(X)ai(X)g(X) + e«(X). (3.100)
ЫХ)д(Х)

Из (3.100) следует

(3.101)
е®(Х) = [q{X)ai(X) + а2(Х)е(Х)]д(Х) + d(X)e(X).
Равенство (3.101), на первый взгляд, может показаться довольно
сложным, однако оно сильно упрощается при вычислении синдро-
мов обоих частей равенства. Следует заметить, что выражение в
Глава 3. Циклические коды

квадратных скобках умножено на д(Х) и, следовательно, это про-
изведение не оказывает влияние на синдром в правой части (3.101).

<< Предыдущая

стр. 36
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>