7.5. Циклические кодеры.

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

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

.

Задав начальные значения в виде

на каждом последующем шаге итерации вычисляются

(7.8)

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

Рис. 7.1.

Элементами структуры регистра являются ячейки памяти, сумматоры по модулю 2 и перемножители. Информационные символы поступают в кодер по тактам, когда ключзамкнут, анаходится в положении 1. Предположим, что на–м интервале времени коэффициенты–го многочлена остатковхранятся в регистре (и, следовательно, доступны для наблюдения в точках), причем коэффициент при старшей степени содержится в крайней правой ячейке. При поступлении на вход кодера вй момент времени информационного символав точкесхемы формируется коэффициент, а в точках– коэффициенты полиномасогласно рекуррентному соотношению (7.8). Поскольку коэффициентыстоят при степенях, меньше старшей, они фактически являются коэффициентами , значения которых можно наблюдать в точках, и, значит, участвуют в формировании коэффициентов полинома, получаемых в точках. При поступлении–го такта указанные коэффициентызапоминаются в ячейках памяти регистра с тем, чтобы использовать их наэтапе рекурсии в качестве коэффициентов.

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

Пример 7.5.1.Кодер (7,4) циклического кода из примера 7.4.1, реализующий алгоритм кодирования (7.8), изображен на рис. 7.2. Таблица, представленная там же, содержит значения информационных символов, состояние регистра и выходные символы. Легко проверить, что для одного и того же информационного полиномарезультат кодирования, что с помощью кодера (правая колонка таблицы), что при помощи порождающей матрицы примера 7.4.1 будет одинаковым.

Рис. 7.2.