Глава 5 Двоичные циклические коды

5.1. Переупорядочение столбцов проверочной матрицы кодов Хэмминга

В разделе 1.3 было показано, как строить исправляющие одиночные ошибки коды с блоковой длиной /г = 2"" - 1, пг проверочными позициями & п - т информационными позициями. У такого кода все п столбцов проверочной матрицы представляют собой различные ненулевые двоичные последовательности длины пг, которые мы назвали локаторами позиций. Если задано однозначное соответствие между п различными позициями и п ненулевыми локаторами, то порядок столбцов не играет никакой роли. Например, проверочная матрица исправляющего одиночные ошибки кода с блоковой длиной /г = 15 может быть записана в виде

гО О О О О О О 1 1 1 1 1 1 1 1-000111100001111

se= 011001100110011

Ll 0101010101010 1.

Для того чтобы исправлять дополнительные ошибки, к этой, матрице надо добавить новые строки. Чтобы сделать изящными эту процедуру и процедуру декодирования результирующего кода, локаторы удобно рассматривать как ненулевые элементы поля GF (2™), представленные в виде двоичных многочленов степени < Щ от корня а некоторого неприводимого двоичного многочлена степе- ни т. Мы покажем сейчас, что такое представление является также полезным и для построения эффективных кодеров и декодеров дл1 кодов, исправляющих одиночные ошибки.

В предыдущем примере с пг = 4 в качестве примитивного многочлена можно выбрать ж* + х + 1. При этом крайний слева столбег имеет локатор 1, второй - локатор а; третий - локатор а + 1, • • • одиннадцатый столбец - локатор а" + а + 1, • • • Если обозна-чить локаторы элементами поля r\i, i = О, 1, . . . , 14, положр Ti; = 1, ri; = а, ri; = а + 1, ri; = a = + 1, [ = о? + а, . . ., rij = а" + a-f а + 1, то 15-мерному двоичному вектори R = [i?o, • • •> -RiJ будет соответствовать синдром dR, кото рый как элемент поля Галуа является суммой соответствующи!

локаторов, (R = 2 гПг-

Если каждой из п позиций кода однозначно сопоставлен локатор из поля GF {2™), то код исправляет все одиночные ошибки независимо от того, как упорядочены локаторы. Так как а - корень примитивного неприводимого двоичного многочлена четвертой степени, то каждый элемент в GF (16) является степенью а. Это позволяет установить, например, такое соответствие между позициями и локаторами, при котором номер позиции будет совпадать со степенью а, r\i = = а. Такое соответствие обладает тем преимуществом, что если

сопоставить вектору R многочлен Л (х) = 2 то синдрому при-

пятого вектора R = [i?o, Ri, . ., Rx будет соответствовать много-

член от а: cR = 2 jc - R {а). Это приводит к простому методу

вычисления синдрома. Согласно алгоритму деления, R {х) = = М {х) Q {х) + г (ж), где степень г (х) меньше степени М (х). Если неприводимый двоичный многочлен М (х) степени т является минимальным многочленом для а, то Tlf (а) = О и Л (а) = г (а). Таким образом, синдром вектора R,равен г (а), где г (х) - остаток от деления двоичного многочлена R (х) на двоичный многочлен М (х).

Прежде чем переходить к описанию устройства для деления произвольного двоичного многочлена R (х) на фиксированный двоичный многочлен М (х), рассмотрим пример. Пусть R (х) = = ж" + х + х + хо + х + х + х"" + X ж М (х) = X* + X + 1. Деление вручную («в столбик») приведено в табл. на стр. 130.

Частное от деления представляется двоичным многочленом

V.10

+ х х + х + X + i пятнадцатой степени, коэффициентами

Частное (на выходе)

Делимое (на входе)

* +1 + 1

Рис. 5.1. Схема для деления.

которого являются первые . цифры каждой новой строчки: 0000010100100111. Остаток имеет вид ООН = х + 1.

Такое деление может быть реализовано с помощью схемы, изображенной на рис. 5.1. Состояния четырех триггеров памяти описывают последовательные шаги деления. Для данного примера такими последовательными состояниями триггеров являются 0000, 0001, 0010, 0101, 1011, 0100, 1000, 0010, . . ., ООН. По окончании деления в триггерах окажутся записанными коэффициенты остатка.

OOOOOlOlHOlOOOllOlO 00000

00001

noooo

00010 00000

00101 00000

01011 00000

10111 10011

01000 00000

10001 10011

00100 00000

01000 00000

10000 10011

00111 00000

01111 00000

11110 10011

11011 10011

10000 10011

Символы

г 14

К+> *<+)*

Рис. 5.2. Схема для деления полученного слова на фиксированный многочлен.

такая методика исправления потребовала бы по вентильной схеме для каждой из п ячеек буферного регистра, в который записывается принятое слово. Менее дорогостоящей является схема исправления ошибок после вывода искаженных символов из буферного регистра. Если Si = а\ то прежде чем исправлять искаженный символ, необходимо вывести из буфера п - i - j правильных символов. Это можно легко осуществить, отсоединив от канала входы регистра сдвига с обратной связью и используя этот регистр в автономном режиме работы. При каждом сдвиге буфера содержимое регистра умножается на а.

Для обеспечения непрерывности работы в декодере используются два регистра с обратной связью, первый из которых реализует деление входящего блока, а второй - исправление искаженных символов выходящего блока. На рис. 5.3 приведена полная схема декодера.

В конце каждого блока элемент поля Si, образуемый в верхнем регистре с обратной связью, перезаписывается в нижний регистр с обратной связью, который затем сдвигается, а верхний регистр с обратной связью устанавливается в нулевое положение. (На рис. 5.3 это обозначено пунктирными линиями.) После этого нижний регистр содержит Si а. При выходе из буферного регистра позиций с локаторами а, а"*, а"*, . . ., а, 1 нижний регистр последовательно

10011

Если позиции передаются в порядке Ri, Rg, . . ., Rq, to для деления в декодере можно использовать схему, представленную на рис. 5.2.

После приема всех п позиций в верхнем регистре окажется записанным многочлен R{x), а в регистре с обратными связями - остаток от деления, г{х). Сумма локаторов ошибочных позиций определяется равенством Si = г(а).

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

содержит Sa, Sa, Sa, . . ., So., Sy. Когда позиция с локатором покидает буферное устройство, на вход элемента ИЛИ

подается величина 1 -\- Sa. Если 1 + Sja Ф О, то Ф а~. В этом случае локатору а" соответствует безошибочная позиция, и она выводится из буферного регистра без изменений. Если же 1 -1- Sa = О, то Si = и при выводе из буфера ошибка исправляется.

Для кодов Хэмминга так же легко реализуются и кодирующие устройства. Заданные п - т информационных позиций кодер передает как позиции С„-х, „.2, . . ., С- Последние т позиций

Символы Шканала

г-*-, " r-L, rJL, г-*-п

*(±>0<±>CHIHIP

►0-

Рис. 5.3. Полная схема декодера для кода Хэмминга.

Сщ-и Cni-27 • • •! Со ДОЛЖНЫ быть выбраны таким образом, чтобьЙ кодовое слово удовлетворяло всем проверочным соотношениям» При выборе локаторов в виде соответствующих степеней а это эквивалентно требованию С{а) = О, что в свою очередь эквивалентно: требованию, чтобы многочлен С{х) был кратен минимальному много-Й члену элемента а, который мы обозначим теперь через g{x). ПрВ

этом ясно, что нужный выбор проверочных символов Cjn-l, Cni-2.

. . ., С о состоит в выборе коэффициентов многочлена, являющегося

остатком от деления 2 «х* на g{x).

Если деление многочлена 2" г на g (х) выполнять с помощы

1=711

метода, использованного в схеме декодера, то остаток нельзя буде

[>€>

Символы частного

Символы часгтюго

4)

Рис. 5.4. Схема с дублированием деления.

легко может убедиться, проверив, что если регистр содержит сумму двух верхних регистров, то после любого сдвига он также содержит их сумму. Обратные связи среднего и нижнего регистров идентичны и определяются коэффициентами делителя. После записи входной последовательности Сп-ъ Сп-%, • •, С, О, О, . . ., О первые т ячеек верхнего буферного регистра заняты нулями, а средний и нижний регистры содержат идентичные последовательности, равные

остатку от деления многочлена 2 г* на g {х). Следовательно,

при вычислении остатка оба верхних регистра могут быть опущены, а содержимое нижнего регистра после ввода в него последовательности Сп-1, Сп-г, . • м Cm и будет определять остаток. Таким образом, как показано на рис. 5.5, декодер можно строить из одного регистра с соответствующими тактовыми и вентильными схемами.

В начальном положении, как показано на рисунке<все три ключа находятся в верхнем положении и регистр сдвига содержит нули. После включения источника информации генерируемые им позиции

получить ДО тех пор, пока через регистр с обратной связью не пройдут все п позиций C„ i, С„ 2, . . ., С, О, О, . . ., 0. К счастью, существует другая схема деления, которая позволяет вычислить коэффициенты остатка, не дожидаясь, пока последние т нулей пройдут через регистр сдвига. Чтобы понять, как это сделать, полезно сначала остановиться на избыточной трехрегистровой схеме, изображенной на рис. 5.4.

Верхний регистр сдвига является буферным для входного многочлена. Средний регистр реализует деление на g{x), причем в рассматриваемом примере g{x) = х* + а; + 1. Нижний регистр содержит сумму (содержимых) двух верхних регистров, в чем читатель