Вернер М. Основы кодирования (2004) (1151882), страница 28
Текст из файла (страница 28)
Такой код действительно существует, его удалось построить швейцарцу Голею в 1949 году, В силу особенностей своейалгебраической структуры, он является весьма притягательным дляматематиков различным направлений и, поэтому, подробно описан влитературе [8].В основе конструкции кода лежит разложение(3.81)Глава 3. Циклические кодыв котором д\{Х) и #2(X) представляют собой порождающие многочлены кода Голлея, причем,gi(X) = 1 + X2 + X4 + Хь + X6 + X10 + X 1 1д2(Х) = 1 + X + X5 + X6 + X7 + X9 + Xй.(3.82)(3.83)Коды Голлея можно декодировать с помощью декодера с вылавливанием ошибок. Этот метод использует вычисление синдрома иможет быть реализован на регистрах сдвига с помощью схем, аналогичных рис. 3.21.
В [7] описана модификация декодера кода Голлеяс вылавливанием ошибок, позволяющая корректировать исправляемые, но не вылавливаемые ошибки, предложенная Т. Касами.3.11. CRC кодыПримером использования семейства циклических кодов является контроль ошибок с помощью циклического избыточного кода, то естьCRC кода ( Cyclic redundancy check), называемого также кодом Абрамсона. При передаче данных в пакетньрс режимах, эти коды используются для определения целостности блоков данных (FCS Frame Checking Sequence).
Примером систем с FCS являются стандарты передачи данных Х.25 (HDSL), ISDN, DECT и LAN. CRC коды представляют собой расширения циклических кодов Хэмминга.Пусть р(Х) - примитивный многочлен степени т , тогда порождающий многочлен CRC кода д(Х) можно записать в виде произведенияд(Х) = (1 + Х)р(Х).(3.84)С помощью порождающего многочлена д(Х) может быть построенmтциклический CRC (п, &)-код с параметрами п = 2 —I, k = 2 —т—2,1имеющий т + 1 проверочных символов и d m j n = 4.CRC-коды обладают пятью важными свойствами::С Е С код отличается от расширения кода Хэмминга, описанного в разделе 2.4.5.Расширенный ( 2 т , 2 т - т - 1 ) - к о д получается из циклического ( 2 т - 1 , 2 т - т - 1 ) кода Хэмминга присоединением проверки на четность по всем символам и имеетминимальное расстояние, также равное 4. Этот код не является циклическим.mтаХотя в CRC ( 2 — 1,2 — т — 2)-коде также добавлена дополнительная проверкана четность, длина кода не увеличилась, так как при этом был исключен один информационный символ.
В результате CRC код представляет собой совокупностькодовых векторов четного веса первоначального кода Хэмминга и по-прежнемуостается циклическим - Прим. перев.3.11. СЯСкоды 199]Таблица 3.8. Порождающие многочлены CRC кодов.КодПорождающий многочлен д(Х)l + X + X4CRC-4(3.85)Используется в ISDN(1 + X)(l + X2 + X3 + X4 + X5 + X6 + X7) =, 1 + X + X2 + XsCRC-8(3.86)Используется в ATM в качестве НЕСCRC-122("••«.•*••*••>-.«•*•«•„•••*. (3.87)(1 + X)(l + Х+Х15)CRC-16= 1 + X2 + Х1Ь + X 1 6(3.88)IBMCRC-16(1 + Х)(1 + X + X2 + X3 + X4 + X12 + X13Ы16+Х + Xi&) = \ + Хь + Хп + X(3.89)Является стандартом CCITT для HDLC и LAPD1 + X + X2 + X4 + X5 + X7 + Xs + X10CRC-32+Х11(3.90)+ X12 + Хш + X22 + X23 + X26 + X32Используется в HDLC1.
Все ошибки кратности 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 проверочныхсимволов. На его базе строится (224,184)-код Файера, способный обнаруживать все пакеты ошибок длиной до 40 символов, или исправлять все пакеты длиной до 12 символов.
Этот код может эффективнобороться с замираниями и используется в мобильной связи GSM длязащиты канала управляющей информации SACCH (Slow AssociatedControl Channel).•-.'Для определенности, здесь и в дальнейшем будем считать, что кодовый векторпоступает в канал начиная со старших разрядов, которые соответствуют старшим степеням многочлена. - Прим. перев.3.12.
Укороченные коды 201^Таблица 3.9. (6,3)-код.ВходКодовое слово000000 000100П О 100010011 010ПО101 П О001Ш101001 101001011100 011ш010 111Из примера кода Файера видно, что использование при кодировании простого дополнения информационного слова нулями практически неприемлемо, поэтому должен применяться более эффективныйметод кодирования укороченных кодов.Пример: Укороченный (б,3)-код. .Рассмотрим метод кодирования и декодирования кода, полученного укорочением (7,4)-кода Хэмминга. Выберем из множества кодовых слов базового кода все кодовые слова, начинающиеся с символа«0».
Выбрасываемые при укорочении символы полагаются равныминулю и, поэтому, не передаются. Таким образом получаем укороченный (6,3)-код. В левой части таблицы 3.3 приведены кодовые слова(7,4)-кода Хэмминга, у которых старший разряд равен нулю. Выбрасывая из этих слов лишние нули, получаем кодовые слова укороченного (6,3)-кода (см. табл. 3.9).Замечание. Построенный (6,3)-код не является циклическим, таккак циклический сдвиг кодовых слов не во всех случаях являетсякодовым словом, однако, его конструкция позволяет использоватьсвойства циклических кодов при декодировании.Проверим таблицу 3.9 с помощью алгоритма деления Евклида.Рассмотрим информационный вектор и = (101), многочлен которого23и(Х) = 1 + X .
Умножая и(Х) на X и используя алгоритм деления Евклида (см. табл. 3.10), получим многочлен остатка от деленияХ3и(Х) на д(Х) = 1 + X + X3, равный Ь{Х) = X2. Таким образом,ч202Глава 3. Циклические кодыТаблица 3.10. Определение проверочных символов (алгоритм деления Евклида) для и(Х) = 1 + Xng(X)= \+Х+3Х.Л"5X4А"3AT2X1101000= х3 и(Х)101100= X2-100= X3--9(Х)3и(Х) + X д(Х) = Ь(Х)многочлен систематического (6,3)-кода равенv(X) = Х3и(Х)+ Ъ(Х) = Х3[Х2 + 1] + X2 = X5 + X 3 + X2,(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)-кода мы покажем, как могла бывыглядеть оптимальная процедура распознавания ошибки в компоненте 7*5 и коррекции соответствующзго синдрома. Как уже отмечалось ранее, в нижнем регистре рис. 3.22 производится вычислениесиндромов циклических сдвигов вектора ошибки для неукороченного (7,4)-кода Хэмминга, поэтому таблицу 3.6 можно использовать идля (6,3)-кода с учетом того, что первым вычисляется синдром дляГлава 3. Циклические ковыв5 = (000 0010).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
