0„-lff„-t-l-f" +

(a„-2-0n-ie,,-k-i)<" + (fl„ 2-o„-,.g„-t-i)x"--H

Эти вычислеция можно записать в виде системы двух рекуррентных равенств. Пусть QC) (х) и Т?**") (х) - соответственно частное и остаток на г-м шаге рекурсии с начальными значениями (х) = О и R (х) = а (х). Тогда рекуррентные равенства записываются в виде

. Q"4x) = Q"-"{x) + R,zPx--, R{x) = R-\x)-R]z,x-g{x),

и после k шагов итерации получаются частное Q) (х) и остаток RW (х).

Изображенная на рис. 6.И цепь является цепью деления произвольного многочлена на фиксированный многочлен g {х). Это легко понять, обратившись к любому из двух приведенных описаний процедуры деления. Единственной не отраженной на цепи операцией является вычитание члена Rn-rX"~ из самого себя, выполнять которую не надо, так как результат всегда равен нулю. После п сдвигов на выходе регистра будет вычислено частное, а в регистре окажется записанным остаток от деления.

На рис. 6.12, а приводится пример цепи, реализующей деление произвольного многочлена над GF (2) на многочлен g (х) = = х + х + х + х + х+1.

Рис. 6.10. Два устройства умножения на многочлен }fi + х + х* + + х + 1.

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

br-г.ЬпА

Рис. 6.11. Устройство деления на многочлен g(x).

....a„.z.o„-d

--*<±>х-

Вниз на тактах " от /? +1 Эо л +А

ооот

Остаток, на так.тах -от /7 + 1 йо п-

Частное на тактах от йо/?

Рис. 6.12. Два устройства деления на многочлен + х-{-x + -{- х-{- 1.

Отметим, ЧТО в этой цепи между внутренними разрядами регистра вставлены сумматоры и это часто усложняет работу цепи. Вместо описанной цепи деления можно использовать цепь, в которой производится только считывание содержимого разрядов регистра сдвига без их изменения. Для построения такой цепи организуем иначе деление многочленов. Идея сводится к одновременному выполнению всех вычитаний одного столбца в описанном выше делении «уголком». Чтобы показать, как это делается, заметим, что можно записать

R<n (х) = а{х)- QC") (х) g (х),

так что

Ri:= = a,-r-"Lgn-rcQr- 1=1

Q\{x)==g-4x) + Ri-rx-.

Эти равенства можно реализовать с помощью модификации цепи умножения на g (х). На рис. 6.12, б показана соответствующая цепь деления на многочлен g- (х) = + х + х* + + л; + 1.

6 р. Блейхут

6.3. КОДЕРЫ И ДЕКОДЕРЫ НА РЕГИСТРАХ СДВИГА

Целесообразность использования регистров сдвига для построения циклических кодеров и декодеров объясняется структурой циклических кодов. При несистематическом кодировании циклических кодов для формирования кодового слова с [х) надо соответствующий информационный многочлен i [х) умножить на фиксированный порождающий многочлен g [х). Эту операцию можно реализовать на КИО-фильтре над GF (q). Такой кодер для (15, 11)-кода Хэмминга представлен на рис. 6.13. Для кодирования непрерывного потока информационных битов последовательностью слов jj(15, 11)-кода Хэмминга информационная последовательность просто разбивается на блоки по И битов, каждый блок дополняется «прокладкой» из четырех нулей, а результирующий поток битов пропускается через КИО-фильтр. На выходе получается последовательность непересекающихся 15-битовых слов кода Хэмминга. Такой кодер, показанный на рис. 6.14, очень прост, но кодовые, слова оказываются несистематическими.

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

с (х) = x-i (х) + t (х),

t{x) = -R.y [x•~i (Х)],

так что

RsM [с(х)] = 0.

Для реализации систематического кодера используется цепь деления на g (х). Для (15, 11)-кода Хэмминга

t (х) - Rg м W ];

соответствующее устройство показано на рис. 6.15. Одиннадцать информационных битов, занимающих старшие разряды, вводятся слева в цепь деления на + л: + 1. Умножение на х* учитывается временем работы цепи. Первый бит понимается как коэффициент при х. Деление не начинается до тех пор, пока не выполнены четыре тактовых сдвига, так что первые четыре бита оказываются записанными в разрядах регистра сдвига. Поэтому ниже цепи деления в устройство включен буфер из четырех разрядов, так, что первые четыре бита начинают поступать в канал одновременно с началом деления. После 11 тактов работы все И информационных битов поданы в канал, деление закончено и вы-