Вернер М. Основы кодирования (2004) (1151882), страница 27
Текст из файла (страница 27)
Найденный синдром соответствует ошибке в (п — 1)-ой компоненте принятого слова, то есть еп-\ = 1;2. Синдром не соответствует такой ошибочной компоненте.В последнем случае процесс, представленный на рис. 3.11 можетбыть повторно проделан для сдвинутого слова г^(Х).При этом,для вычисления s^\X) нет необходимости проводить действия, аналогичные нахождению s(X). Согласно теореме 3.6.1, синдром s(X)преобразуется в синдром s^(X)за один такт с помощью схемы,представленной на рис. 3.15.После того, как определен s(X), мы можем последовательно получить синдромы s^(X),s^(X),...,s( n ~''(X). Если синдромы некорректировать, то через п тактов мы опять придем к первоначальному синдрому s(X) = s(n)(X) многочлена г(Х). Однако, если впроцессе работы получен синдром, соответствующий еп-\ = 1, тонекоторая компонента многочлена г(Х) должна быть исправлена.В этом случае также корректируется еще и некоторый синдром из/последовательности s^(X),s^(X),...,s("~l)(X).
Рассмотрим простейший случай. Пусть синдром s(X) сразу же соответствует (п —1)ой ошибочной компоненте многочлена г(Х), то есть e n _i = 1. Тогдаскорректированный многочлен т)(Х) будет иметь вид:17 7 (Х)=го + г 1 Х + --- + ( г п _ 1 + е „ _ 1 ) Х " - .•(3.78)Заметим, что на последующих шагах декодирования должен использоваться синдром модифицированного многочлена из (3.78). Таккак s(X) является синдромом r(X), a s'(X) - синдром многочленае'(Х) = Хп~г, синдром многочлена т](Х) равен(X)Sl= s{X) + s'(X).(3.79)Коррекцию синдрома удобнее производить только на следующем такте декодирования.
В этом случае, после циклического сдвига г(Х)ошибочной нулевой компоненте будет соответствовать многочлен.3.8. Декодер Меггиттае'(Х) = 1, а синдром скорректированного многочлена rf^{X)равенбудетs[i}(X) = sW(X)(3.80)+ l.Контроль ошибок производится по всем п компонентам принятого многочлена г(Х) и найденные ошибки исправляются. Если послеп тактов контроля ошибок синдром отличен от нулевого, то выдаетсясигнал о наличии неисправляемых ошибок. Такой алгоритм можетбыть, в принципе, использован для декодирования всех циклических(п, &)-кодов.
Его реализация, декодер Меггитта, в общем виде представлена на рис. 3.18.Принятое из каналасловои- разрядный буфер-> Выходной регистр. ИсправлениеошибокМодификациясиндрома' Логическая схемаР и с . 3.18. Декодер Меггитта для двоичного циклического(га, fcj-кода с порождающим многочленом д{Х).Перед началом работы оба регистра декодера Меггитта обнуляются. На первых п тактах декодирования принятое слово загружается в верхний регистр, а в нижнем регистре вычисляется синдроммногочлена г(Х). После этого вход декодера отключается и в течении последующих п тактов проводится покомпонентное обнаружениеи исправление ошибок. В каждом такте с помощью логической схемыраспознавания ошибок проверяется соответствие текущего синдромаошибочной (п — 1)-ой компоненте сдвинутого многочлена г(Х).
Приобнаружении такого соответствия на следующем такте декодировапия, ошибка исправляется, а синдром модифицируется.Пример: Декодер Меггитта циклического (7,4)-кода Хэмминга.В качестве примера рассмотрим уже знакомый нам циклический(7,4)-кода Хэмминга с порождающим многочленом д(Х) = 1 + X 4X 3 . Напомним, что код Хэмминга позволяет исправлять все однократные ошибки. Более того, так как (7,4)-код Хэмминга являетсясовершенным, таблица синдромов однократных ошибок (см.
табл.Глава 3. Циклическиекоды3.6) содержит все возможные синдромы от «001» до «111» (синдром000 интерпретируется как отсутствие ошибок). Для построения декодера Меггитта нам достаточно знать синдром одиночной ошибкив компоненте г 6 принятого слова. Из таблицы 3.6 следует, что синдром одиночной ошибки г 6 = 1 равен «101» или при полиномиальномпредставлении \ + Х3. Схема декодера Меггитта циклического (7,4)кода Хэмминга приведена на рис. 3.19. Блок распознавания ошибокможет быть построен при помощи логической схемы совпадения «И»(&) с инверсией входа S\ (в соответствии с синдромом «101» дляг6 = 1).Принятое из каналасловоВыхолной регистрМодификациясиндромаР и с .
3.19. Декодер Меггитта циклического (7,4)-кода Хэмминга спорождающим многочленомд(Х) — 1 + X + X .Принятое словоo | i | i | i | o | i i n*Выходной регистрТакты 1 -7: В регистрзаносится принятоеслово и вычисляетсяего синдромР и с . 3.20. Декодер Меггитта циклического (7,4)-кода Хэмминга спорождающим многочленом д(Х) = 1 + X + X и принятым вектором г (начальная фаза).Рассмотрим процесс декодирования принятого слова с ошибочной компонентой г 5 . В 5том случае г = (011 1011). После первыхсеми тактов работы декодера слово г(Х) полностью занесено в буфферный регистр, а в нижнем регистре находится синдром s(X) для3.8. Декодер МеггиттаI9S,г(Х) (рис. 3.20). В соответствии с таблицей 3.6 этот синдром равен«111».Такт 8'6 = 1 <k=lВыходной регистрТакт 9#5=1^=01 Ч - I - I о I Ч Ч | I о 1—»$—-t о I Ч - I- 1-I- IВыходной регистрМодификациясиндромаТакт 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 следует, что3.10. Двоичный код Голлея197]Таблица 3.7. Примитивные многочлены.mmP(X)'3111 + X2 + XU4P(X)l +X + X341+X + X121 + X + X4 +X6 + X1251 + X2 + X5131 + X + X3 + X4 + X1361 + X + X6141 + X2 + Xe + Xw + X1473151 + X + X1571+X + X1+Х2+Х3+Х4+Хъ7+Х + Х91 + X2 + X3 + X4 + X9i + x4 + x910l + X3 + Xi08ь2332511 ~тJ_ YЛ_i_ Л V23-j-1 + X + X2 + X4 + X5 + X7 +X% + Xl0 + Xn +X12 + Xl6++X22 + X23 + X26 + X32таким многочленом является многочлен р{Х) = 1 + X + X4 и используя его в качестве порождающего, можно получить все кодовыеслова циклического (15,11)-кода Хэмминга.С помощью порождающих многочленов д(Х) можно строить порождающие и проверочные матрицы, а также схемы декодеров любых циклических кодов Хэмминга.3.10.
Двоичный код ГоллеяИспользуя равенство (2.25) можно заметить, что [С^ + С^3 + С§3 +С23]212 = 2 2 3 . Возникает гипотеза о том, что 23-мерное двоичноепространство можно плотно упаковать сферами радиуса 3. Это равенство представляет собой необходимое (но недостаточное) условиесуществования совершенного (23,12)-кода, исправляющего все тройные ошибки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
