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

 

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

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

рождающего полинома , выделив в ней старшую степень :

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

.

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

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

(7.8)

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

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

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

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