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

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

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

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

В предыдущем примере с в качестве примитивного многочлена можно выбрать При этом крайний слева столбец имеет локатор 1, второй — локатор а; третий — локатор одиннадцатый столбец — локатор Если обозначить локаторы элементами поля положив

1, то -мерному двоичному вектору будет соответствовать синдром который как элемент поля Галуа является суммой соответствующих локаторов,

Если каждой из позиций кода однозначно сопоставлен локатор из поля то код исправляет все одиночные ошибки независимо от того, как упорядочены локаторы. Так как а — корень примитивного неприводимого двоичного многочлена четвертой степени, то каждый элемент в является степенью а. Это позволяет установить, например, такое соответствие между позициями и локаторами, при котором номер позиции будет совпадать со степенью Такое соответствие обладает тем преимуществом, что если сопоставить вектору многочлен то синдрому принятого вектора будет соответствовать многочлен от Это приводит к простому методу вычисления синдрома. Согласно алгоритму деления, где степень меньше степени Если неприводимый двоичный многочлен степени является минимальным многочленом для а, то и Таким образом, синдром вектора равен где остаток от деления двоичного многочлена на двоичный многочлен

Прежде чем переходить к описанию устройства для деления произвольного двоичного многочлена на фиксированный двоичный многочлен рассмотрим пример. Пусть и Деление вручную («в столбик») приведено в табл. на стр. 130.

Частное от деления представляется двоичным многочленом пятнадцатой степени, коэффициентами которого являются первые цифры каждой новой строчки: 0000010100100111.

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

Остаток имеет вид

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

(кликните для просмотра скана)

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

После приема всех позиций в верхнем регистре окажется записанным многочлен , а в регистре с обратными связями — остаток от деления, Сумма локаторов ошибочных позиций определяется равенством

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

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

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

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

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

содержит Когда позиция с локатором покидает буферное устройство, на вход элемента ИЛИ подается величина . Если , то . В этом случае локатору соответствует безошибочная позиция, и она выводится из буферного регистра без изменений. Если же то и при выводе из буфера ошибка исправляется.

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

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

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

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

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

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

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

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

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

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

Рис. 5.5. Кодер для кода Хэмминга.

После передачи по каналу всех позиций регистра сдвига ключи возвращаются в верхнее положение и начинается передача следующего блока.