Березкин Основы теории информации и кодирования 2010

член степени m . Длина кода n равна наименьшему общему кратному e и c :

n НОК{e,c},

где e – максимальный показатель для p(x) , т.е. наименьшее число, при котором xe 1 0 mod p(x) . Причем c не должно делиться нацело на e 2m 1. В частности, если p(x) является прими-

тивным многочленом, то e 2m 1. Число проверочных разрядов равно n k m c .

Код позволяет исправить вспышку ошибок длиной l или менее и одновременно обнаружить любую вспышку ошибок длиной t l , если c t l 1 и m l .

Например, код Файра, генерируемый g(x) (x4 x 1)(x7 1) ,

содержит n 105 разрядов, из которых 11 являются проверочными, и позволяет обнаружить и исправить произвольную вспышку ошибок длиной 4 и менее.

В табл. 10.7 приведены параметры некоторых циклические коды Файра (n, k) .

Таблица 10.7

10.6. МЕТОДЫ ПОСТРОЕНИЯ ЦИКЛИЧЕСКОГО КОДА ХЭММИНГА

Существуют различные методы построения циклического кода. Рассмотрим основные из них. При классификации циклических кодов были введены понятия неразделимых и разделимых циклических кодов.

241

10.6.1. Неразделимый циклический код

Разрешенные n -разрядные комбинации циклического кода получаются умножением многочленов, соответствующих k - разрядным информационным комбинациям, на порождающий

многочлен: a~i (x) ai (x) g(x) . Кодер при этом легко реализует-

ся, однако при декодировании возникают трудности.

Пусть необходимо построить код для исправления одиночных ошибок. Остатки от деления многочлена ошибки E j (x) x j 1 на

g(x) являются признаком ошибки в соответствующем j -м разряде. Декодирующее устройство должно осуществлять деление принятого кода a~i (x) на g(x) . В случае равенства остатка от деления

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

Рассмотрим пример кода (7,4) с порождающим многочленом

Пусть передается код 0111, после кодирования на выходе кодера будет код

(x2 x 1)g(x) (x2 x 1)(x3 x2 1) x5 x 1 0100011.

Допустим, что на приемном конце принимается кодовая комбинация с искажением четвертого разряда: x5 x3 x 1 0101011. Эта комбинация делится на g(x) x3 x2 1 1101:

242

x2 1 101

По таблице ошибок (табл. 10.9) находим, что искажение произошло в четвертом разряде. Этот разряд исправляется и деление повторяется, при этом получается правильный код:

243

10.6.2. Разделимый циклический код

Более широкое распространение на практике получили разделимые циклические коды. Под информационные символы принято отводить старшие k разрядов, а под проверочные n k младших разрядов. Чтобы получить такой код, применяется следующая про-

Таким образом, циклический код можно строить, приписывая к каждой неизбыточной комбинации информационных символов

остаток от деления этой комбинации на g(x) . Для кодов, число k

для которых удовлетворяет условию k n k , рассмотренный метод особенно прост.

Рассмотрим опять пример кода (7,4), но с порождающим многочленом g(x) x3 x 1 (табл. 10.10).

Таблица 10.10

244

g(x) . Если результат деления – нуль, то, отбрасывая три младших

разряда, получаем передаваемый код. Если же результат деления не нулевой, то остаток от деления указывает номер разряда, где произошла ошибка в соответствии с табл. 10.11.

Пусть передавалась комбинация 1001. После кодера имеем 1001110. Пусть на приемном конце получена последовательность 1011110, т.е. ошибка произошла в пятом разряде. Производим деление:

Остаток 110 указывает, что ошибка произошла в пятом разряде. Этот разряд исправляется, а три младших проверочных разряда отбрасываются.

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

Разделимый циклический код так же, как и групповой, удобно записывать в матричной форме:

245

10.7. ПОСТРОЕНИЕ ОДНОКАНАЛЬНЫХ КОДИРУЮЩИХ И ДЕКОДИРУЮЩИХ УСТРОЙСТВ ЦИКЛИЧЕСКОГО КОДА ХЭММИНГА

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

D D

Рис. 10.10. Компоненты фильтра:

а– сумматор по модулю 2; б – элемент задержки (D триггер);

в– объединенный элемент

Структура фильтра описывается матрицей связей между его элементами

где r – количество элементов задержки в фильтре, а m ij 1 , если выход j -го элемента задержки связан с входом i -го элемента задержки, в противном случае mij 0 .

246

i 1

где g(x) 1 g1 x g2 x2 ... gr xr – порождающий многочлен, для которого g1 x g2 x2 ... gr xr 1mod g(x) .

247

позволяет выполнять деление на полином g(x) [13].

то состояние фильтра в следующем такте (на вход схемы информация не поступает) равно

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

Если начальное состояние (0) (x) 0 и на вход фильтра по-

ступает последовательность символов a0 , a1 ,..., an 1 , а эта по-

следовательность соответствует коэффициентам произвольного полинома степени не более n 1

An (x) a0 a1x ... an 1xn 1 ,

то фильтр будет последовательно принимать состояния

248

так как xn 1mod g(x) .

После поступления последнего символа an 1 содержимое

фильтра будет равно остатку от деления полинома An (x) на g(x) .

Структура рассмотренного фильтра, описываемого матрицей связи M (x) x 1 1 x ... xr 2 , приведена на рис. 10.12.

Вход

Рис. 10.12. Структура фильтра с входом

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

Кодер работает следующим образом. Сначала ключ находится в 1-м положении, и k информационных разрядов a0 , a1 ,..., ak 1

поступают на вход фильтра, который вначале находится в нулевом состоянии, и непосредственно в линию связи. Затем ключ переключается во 2-е положение. В этом случае обратная связь в фильтре размыкается и r n k контрольных разрядов последо-

249

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

кодового слова длиной n фильтр оказывается в нулевом состоянии.

Формально работа кодера описывается следующим образом. После поступления k информационных символов содержимое фильтра равно

(k ) (x) a0 x k a1 x k 1 ... ak 1 x 1

x k (a0 a1 x ... ak 1 xk 1 ) x k Ak (x) xn k Ak (x) mod g(x) ,

которое совпадает с контрольным вектором.

На рис. 10.14 представлена блок-схема декодирующего устройства.

Коэффициенты b0 ,b1,..., bn 1 полинома Bn (x) последовательно поступают на вход буферного ЗУ и одновременно на вход много-

Если ошибка отсутствует, то после поступления последнего символа bn 1 содержимое фильтра будет равно нулю.

Получение ненулевого результата свидетельствует о наличии обнаруживаемой ошибки, полином которой имеет вид

E(x) xie(x) .

Если продолжить работу декодирующего устройства (синхронно производить сдвиги БЗУ и блока деления в автономном режи-

250