11.9. Регистры сдвига для кодирования

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

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

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

Как практически производится деление? Рассмотрим регистр сдвига, показанный на рис. 11.9.1. Предполагается, что символы сообщения поступают справа, начиная с символа, соответствующего самой большой степени; в конце вводятся три нулевых символа. Стрелки под регистром сдвига указывают направление обратной связи. Если в старшем разряде содержится символ 1, то он добавляется (или вычитается) к указанным стрелкам и символам. Детали процесса показаны на рис. 11.9.2, на котором опущены первые несколько шагов, поскольку в течение первых четырех шагов, пока первая цифра не дойдет до крайнего левого положения, не происходит ничего интересного. Таблицу на рис. 11.9.2 нужно рассматривать, начиная с верхней строки. Во второй строке показаны символы, возвращаемые обратной связью, а в третьей строке (непосредственно над двойной линией) содержится результат сложения. (Для того чтобы процесс в точности соответствовал

процессу деления, показано прибавление 1 в крайней левой позиции; на практике этот символ не возвращается.) Двойная линия указывает на сдвиг, и под этой линией приводятся сдвинутые символы. В трех строках между двойными линиями отображено происходящее между двумя сдвигами. В этом примере имеется всего четыре множества по три строки.

Рис. 11.9.1. Регистр сдвига с обратной связью

Рис. 11.9.2. Результаты работы регистра

В последней строке записан остаток. Непосредственное сравнение показывает, что регистр сдвига делает то же самое, что и процесс деления углом.

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

Рис. 11.9.3. Кодер

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

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

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

Затем произвести сдвиг, и всю процедуру повторить. Нетрудно описать все это подробно.

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

Задача

11.9.1. Напишите программу для кодирования сообщения по схеме, представленной в этом разделе.