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

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

ОГЛАВЛЕНИЕ

Следующая >>


Такт 10
о|о|Ч-1-
Выходной регистр




Рис. 3.21. Декодер Меггитта циклического (7,4)-кода Хэмминга с
порождающим многочленом д(Х) = 1 + X + X3 и при-
нятым вектором г (заключительная фаза).


На восьмом такте декодирования компонента г$ поступает в вы-
ходной регистр без изменения (поскольку синдром был равен «111»),
а новое значение синдрома равно «101», что соответствует ошибке в
компоненте г§ и на девятом такте эта ошибка корректируется, а син-
дром обнуляется (рис. 3:21). Таким образом, на тактах п — 10... 14
оставшиеся компоненты принятого слова загружаются в выходной
регистр без коррекции, так как синдром сохраняет нулевое значе-
ние.
Глава 3. Циклические коды

3.9. Циклические коды Хэмминга
Циклические коды Хэмминга образует важное семейство цикличе-
ских (те, &)-кодов. Свойства кодов Хэмминга, как подмножества ли-
нейных кодов, были подробно рассмотрены в разделе 2.4. Коды Хэм-
минга, имеющие циклическую структуру, обладают дополнительны-
ми, весьма полезными свойствами.
При определении методов построения циклических кодов исполь-
зуются понятия неприводимых и примитивных многочленов.
Многочлен р(х) степени т называется неприводимым в поле GF(2),
если он не делится ни на какой многочлен" с коэффициентами из
GF{2) степени меньшей т., но большей 0.
Неприводимый многочлен р{х) степени m называется примитив-
ным, если наименьшая степень те, при которой многочлен Хп + 1
делится на р(х) без остатка, равнд п = 2т — 1.
В таблице 3.7 приведены некоторые примитивные многочлены с
коэффициентами из GF{2).
Замечание. Примитивные многочлены играют важную роль в тех-
нике передачи сообщений, например, примитивный многочлен сте-
пени т = 23 используется в устройствах перемешивания символов
в сетях ISDN и xDSL. Примитивные многочлены являются так-
же основой для построения порождающих многочленов псевдослу-
чайных последовательностей. С помощью таких псевдослучайных
последовательностей производится адресование сообщений в систе-
мах мобильной связи.

Основой для построения циклических кодов Хэмминга служит
следующая теорема.

Теорема 3.9.1. Любой циклический код Хэмминга длины 2т — 1
с т > 3 может быть построен с помощью некоторого примитивного'
многочлена степени т.

Имеется также обратная теорема. В ней утверждается, что лю-
бому примитивному многочлену степени т соответствует некоторый
циклический код Хэмминга длины 2т — 1 [7].
Пример: Циклический (15,11)-код Хэмминга.
Для построения циклического (15,11)-кода Хэмминга использу-
ется многочлен степени степени т = 4. Из таблицы 3.7 следует, что
197]
3.10. Двоичный код Голлея

Таблица 3.7. Примитивные многочлены.

m m P(X)'
P(X)
3 2 U
l +X + X 1 +X + X
11
3
1 + X + X4 1 + X + X4 +X6 + X12
4 12
2 5 3 4 13
1+X + X 1 +X +X +X + X
5 13
6 2 e w 14
1 +X + X 1+ X +X +X +X
6 14
3 7
1 + X + X15
1+X + X
7 15
2 3 4 ъ ь 7
1+Х +Х +Х +Х +Х + Х

1 + X2 + X3 + X4 + X9
8 23 1 ˜т Л5 -j- Л V23
_i_
1 J_ Y
i + x4 + x9 1 + X + X2 + X4 + X5 + X7 +
32
9
X% + Xl0 + Xn +X12 + Xl6+
l + X3 + Xi0 +X22 + X23 + X26 + X32
10




таким многочленом является многочлен р{Х) = 1 + X + X4 и ис-
пользуя его в качестве порождающего, можно получить все кодовые
слова циклического (15,11)-кода Хэмминга.
С помощью порождающих многочленов д(Х) можно строить по-
рождающие и проверочные матрицы, а также схемы декодеров лю-
бых циклических кодов Хэмминга.


3.10. Двоичный код Голлея

Используя равенство (2.25) можно заметить, что [С^ + С^3 + С§3 +
С23]212 = 2 2 3 . Возникает гипотеза о том, что 23-мерное двоичное
пространство можно плотно упаковать сферами радиуса 3. Это ра-
венство представляет собой необходимое (но недостаточное) условие
существования совершенного (23,12)-кода, исправляющего все трой-
ные ошибки. Такой код действительно существует, его удалось по-
строить швейцарцу Голею в 1949 году, В силу особенностей своей
алгебраической структуры, он является весьма притягательным для
математиков различным направлений и, поэтому, подробно описан в
литературе [8].
В основе конструкции кода лежит разложение

(3.81)
Глава 3. Циклические коды

в котором д\{Х) и #2(X) представляют собой порождающие много-
члены кода Голлея, причем,

gi(X) = 1 + X2 + X4 + Хь + X6 + X10 + X 1 1 (3.82)

д2(Х) = 1 + X + X5 + X6 + X7 + X9 + Xй. (3.83)
Коды Голлея можно декодировать с помощью декодера с вылав-
ливанием ошибок. Этот метод использует вычисление синдрома и
может быть реализован на регистрах сдвига с помощью схем, анало-
гичных рис. 3.21. В [7] описана модификация декодера кода Голлея
с вылавливанием ошибок, позволяющая корректировать исправляе-
мые, но не вылавливаемые ошибки, предложенная Т. Касами.


3.11. CRC коды
Примером использования семейства циклических кодов является кон-
троль ошибок с помощью циклического избыточного кода, то есть
CRC кода ( Cyclic redundancy check), называемого также кодом Аб-
рамсона. При передаче данных в пакетньрс режимах, эти коды ис-
пользуются для определения целостности блоков данных (FCS -
Frame Checking Sequence). Примером систем с FCS являются стан-
дарты передачи данных Х.25 (HDSL), ISDN, DECT и LAN. CRC ко-
ды представляют собой расширения циклических кодов Хэмминга.
Пусть р(Х) - примитивный многочлен степени т , тогда порож-
дающий многочлен CRC кода д(Х) можно записать в виде произве-
дения
(3.84)
д(Х) = (1 + Х)р(Х).
С помощью порождающего многочлена д(Х) может быть построен
циклический CRC (п, &)-код с параметрами п = 2 m —I, k = 2 т —т—2,
имеющий т + 1 проверочных символов и d m j n = 4.1
CRC-коды обладают пятью важными свойствами:
:
С Е С код отличается от расширения кода Хэмминга, описанного в разделе 2.4.5.
Расширенный ( 2 т , 2 т - т - 1 ) - к о д получается из циклического ( 2 т - 1 , 2 т - т - 1 ) -
кода Хэмминга присоединением проверки на четность по всем символам и имеет
минимальное расстояние, также равное 4. Этот код не является циклическим.
Хотя в CRC ( 2 m — 1,2та — т — 2)-коде также добавлена дополнительная проверка
на четность, длина кода не увеличилась, так как при этом был исключен один ин-
формационный символ. В результате CRC код представляет собой совокупность
кодовых векторов четного веса первоначального кода Хэмминга и по-прежнему
остается циклическим - Прим. перев.
3.11. СЯСкоды 199]
Таблица 3.8. Порождающие многочлены CRC кодов.

Код Порождающий многочлен д(Х)

4
l +X + X
CRC-4 (3.85)

Используется в ISDN


(1 + X)(l + X2 + X3 + X4 + X5 + X6 + X7) = (3.86)
CRC-8
, 1 + X + X2 + Xs

Используется в ATM в качестве НЕС


2
("••«.•*••*••>-.«•*•«•„•••*. (3.87)
CRC-12




= 1 + X2 + Х1Ь + X 1 6
(1 + X)(l + Х+Х15) (3.88)
CRC-16

IBM


(1 + Х)(1 + X + X2 + X3 + X4 + X12 + X13 (3.89)
CRC-16
+Х + Xi&) = \ + Хь + Хп + X
Ы 16




Является стандартом CCITT для HDLC и LAPD


2 4 5 7 s 10
1 + X+ X +X +X +X +X + X (3.90)
CRC-32
11 12 ш 22 23 26 32
+Х +X +Х +X +X +X +X

Используется в HDLC




1. Все ошибки кратности 3 или меньше обнаруживаются;

2. Все ошибки нечетной кратности обнаруживаются;

3. Все пакеты ошибок длины I = т + 1 или меньше обнаружива-
ются;

4. Доля необнаружимых пакетов ошибок длины / = т + 2 состав-
ляет 2˜ т ;

5. Доля необнаружимых пакетов ошибок длины I > т + 3 состав-
ляет г - ^ - 1 ) .
Глава 3. Циклические коды


Все перечисленные свойства позволяют эффективно использо-
вать CRC код при передачи данных с переспросами (протокол ARQ).
На практике часто используются укороченные CRC коды. В таб-
лице 3.8 приведены наиболее употребляемые порождающие много-
члены CRC кодов, а также указаны области их применения.


3.12. Укороченные коды

Во всех рассмотренных нами циклических кодах длина кодовых слов
однозначно определяется степенью выбранного примитивного мно-
гочлена. Это обстоятельство накладывает большие ограничения на
число информационных разрядов в кодируемом блоке. Между тем, в
используемых в настоящее время стандартах передачи данных, дли-
на информационных блоков может колебаться в довольно широких
пределах. В соответствии с этим, кодирование также должно быть
достаточно гибким.
Здесь на помощь приходят укороченные коды, построенные на
основе циклических кодов. Пусть, например, нами выбран много-
член с га = 5. На базе этого многочлена можно построить цикличе-
ский (31,26)-код Хэмминга. Рассмотрим подможество слов этого ко-
да, содержащее все кодовые слова с тремя нулями в старших разря-
1
дах Это подмножество образует укороченный (28,23)-код Хэммин-
га. Укороченный код сохраняет все свойства циклического (31,26)-
кода, так как в процессе декодирования мы можем дописать к кодо-
вым словам три недостающих нуля и рассматривать их как векторы
основного (31,2б')-кода Хэмминга.
В качестве следующего примера можно привести код Файера, ис-
пользуемый в мобильной связи. Этот код является сильным укоро-
чением кода Хэмминга. Соответствующий код Хэмминга имеет непо-
мерно большую длину, равную 3014633 и содержит 40 проверочных

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

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

ОГЛАВЛЕНИЕ

Следующая >>