6.6. УКОРОЧЕННЫЕ ЦИКЛИЧЕСКИЕ КОДЫ

Любой систематический циклический код можно укоротить, а именно от -кода можно перейти к -коду выбрасыванием информационных позиций в каждом кодовом слове. Будем полагать, что меньше и что выбрасываются старших разрядов. Последнее объясняется тем, что выбрасываемые символы при укорочении полагаются равными нулю и поэтому не передаются, но при декодировании декодер их восстанавливает, так что декодирование осуществляется на полной длине кода. Если минимальное расстояние исходного кода равно то минимальное расстояние укороченного кода не меньше Аналогично если исходный код позволяет исправлять пакеты ошибок длины то укороченный код позволяет исправлять пакеты длины (или больше). С помощью укорочения и перемежения из кодов табл. 5.1 можно построить большой набор хороших кодов, исправляющих пакеты ошибок.

Укороченный циклический код уже не является циклическим, так как многочлен в общем случае уже не является кодовым словом для произвольного кодового слова с Однако укороченный циклический код все-таки обладает алгебраической структурой подмножества соответствующего кольца. В то время как циклический код является идеалом кольца многочленов по модулю укороченный циклический код является идеалом кольца многочленов по модулю некоторого многочлена степени Точный результат дается следующей теоремой.

Теорема 6.6.1. Если укороченный циклический код, то существует многочлен такой, что если с кодовое слово, а произвольный многочлен, то также является кодовым словом.

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

Так как то степень остатка меньше Пусть тогда степень

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

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

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

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

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

Тогда

Следовательно, единственным ненулетим коэффициентом многочлена является старший коэффициент.

Пусть

Тогда, согласно правилам вычислений по модулю, многочлен можно записать в виде

Все, что нужно сделать, сводится к предварительному (перед делением на умножению на фиксированный многочлен Такое умножение можно реализовать с помощью

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

Сначала приведем два примера декодеров для циклических кодов. Первым рассмотрим укороченный циклический код, исправляющий пакеты ошибок. Предположим, что в некотором приложении потребовалось укоротить -код из табл. 5.1 до -кода. Этот код исправляет все пакеты ошибок длины не более 4. В данном случае и необходимо вычислить

Одним из способов этого вычисления является представление в виде

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

Рис. 6.30. Декодер с пылавливаниеы ошибок для -кода, исправляющего пакеты ошибок.

Рис. 6.31. Декодер Меггитта для (64, 60)-кода Хэмминга над

и, наконец,

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

В качестве второго примера рассмотрим -код над являющийся укорочением -кода Хэммннга. Как уже обсуждалось в -код Хэмминга является циклическим с порождающим многочленом . В данном случае Выполняя деление «уголком», получаем

и модифицированный синдром задается равенством

Показанное на рис. 6.31 устройство является декодером Меггитта для этого укороченного кода, время декодирования для которого равно 128 тактам. Для вычисления модифицированного синдрома

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