Метод и средства кодирования

Применительно к циклическим кодам принято отводить под информаци­онные символы k старших разрядов многочлена кода, а под проверочные символы n-k низших разрядов.

Применяется следующая процедура кодирования:

многочлен а(х), соответствующий k -разрядной комбинации информационных разрядов кода, умножается на х^т, где т - степень образующего многочлена. Это со­ответствует добавлению к комбинации а(х) m нулей со стороны младших раз­рядов. Произведение a(x)x^m делится на образующий многочлен g₀(x). В общем случае при этом получаем некоторое частное q(x) и остаток r(x):

a(x)x^m=q(x)g₀(x) Å r(x).

Остаток прибавляется к а(х)х^т. Поскольку степень остатка r(x) не превы­шает т-1, а в комбинации, соответствующей многочлену а(х)х^т, т младших разрядов-нулевые, то указанная операция сложения равносильна приписыва­нию r(x) к а(х) со стороны младших разрядов.

Полученный многочлен f(x)=a(x)x^mÅ r(x)=q(x)g₀(x) делится на g (x) без ос­татка и, следовательно, соответствует разрешенной комбинации кода.

Техническая реализация описанного процесса кодирования в случае двоичных кодов осуществля­ется посредством регистра сдвига с обратными связями, состоящего из ячеек памяти и сумматоров по модулю два. Сдвиг информации в регистре осу­ществляется импульсами, поступающими с генератора продвигающих импуль­сов, который на схеме, как правило, не указывается. На вход регистра посту­пают только коэффициенты многочленов, причем, начиная с коэффициента при переменной в старшей степени.

На рис.3.1 представлена схема, выполняющая деление произвольного мно­гочлена (например, многочлена а(х)=а_п-1х^п-1+а_п-2х^п-2+,...,+а₁(х)+а₀) на некоторый фиксированный (например, образующий) многочлен

g(x)=g^n-kх^п-к+...+g₁(x)+g₀.

Обратные связи регистра соответствуют виду многочлена g₀(x). Количество включаемых в него сумматоров равно числу отличных от нуля коэффициентов g₀(x), уменьшенному на единицу. Это объясняется тем, что сумматор сложения коэффициентов старших разрядов многочленов делимого и делителя в регистр не включается, так как результат сложения заранее известен (он равен нулю).

За первые m тактов коэффициенты многочлена-делимого заполняют регистр, причем коэффициент при х в старшей степени достигает крайней пра­вой ячейки. На следующем такте единица делимого, выходящая из крайней ячейки регистра по цепи обратной связи, подается к сумматорам по модулю два, что равносильно вычитанию многочлена-делителя из многочлена-делимого. Если в результате предыдущей операции коэффициент при старшей степени х у остатка оказался равным нулю, то на следующем такте вычитания делителя не происходит. Коэффициенты делимого только сдвигаются вперед по регистру на один разряд, что находится в полном соответствии с тем, как это делается при делении многочленов столбиком.

Рис. 3.1 Схема деления на произвольный многочлен.

Деление заканчивается с приходом последнего символа многочлена-дели­мого. При этом разность будет иметь более низкую степень чем делитель. Эта разность и есть остаток.

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

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

Для случая g₀(x)=x³+x²+1 и а(х)=а³+1 схема кодирующего устройства приведена на рис. 3.2.

В исходном состоянии ключ К₁ находится в положении 1, а ключ К₂ замк­нут. Информационные символы одновременно поступают как в линию связи, так и в регистр сдвига, где за к тактов образуется остаток. Затем ключ К₂ раз­мыкается, ключ К₁ переходит в положение 2 и остаток выводится в канал связи.

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

Рис. 3.2 Схема кодирующего устройства.

Таблица 3.1