Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
ЧЗ-тО-^
Рис. 16.
«запоминают», но и «сдвигают» поступающие в них коэффициенты (играют роль сдвигающего регистра). Сумматоры осуществляют сложение по правилам сложения в поле F,;
,84 Кроме того, в схему введены добавочные устройства, производящие умножение на элемент gi?F (на рис. 16 эти устройства показаны кружками, помеченными соответствующими множителями). В двоичном случае особых устройств для этого не требуется: если g,-=l, то в соответствующем месте схемы имеется «вертикальное» соединение и двоичный сумматор, в противном случае они отсутствуют.
Столь же просты схемы деления многочлена на многочлен с остатком. Вот, например, как устроена схема деления на многочлен 1+Х2+Х3 (рис. 17).
На вход поступают коэффициенты делимого, начиная со старших степеней, на выходе последовательно появляются
Вход Делите
Выход
Частное
Рис. 17.
коэффициенты частного. После окончания деления в ячейках памяти слева направо оказываются записанными коэффициенты остатка, начиная с младших степеней. Проследим последовательность работы схемы при делении на X3+ + Х2+1 многочлена Х5+Х4+Х3+Х+1. Деление углом дает:
Х* +X' + X3 + 0.X2 + X + 1 }Х3 + Х2 + 0Х + 1 Х6 + Х4 + 0-Х3 + Х2 Х2 + 0-Х+1
Х3 + Х2 + 0Х+1
0Х2 + Х + 0
(рамочками выделены последовательные частичные остатки).
В первые три такта работы схемы старшие коэффициенты делимого сдвигаются по ячейкам памяти. При этом старший коэффициент (при X5) окажется в крайней правой ячейке (рис. 18, ?). Все это время на «нижних» входах
85
к сумматоров сохраняются нулевые элементы, не влияющие на работу схемы. В следующем такте (рис. 18, б) старший коэффициент сдвигается на выход схемы, одновременно попадая на нижние входы сумматоров. На вход схемы поступает нулевой коэффициент при X2. В первую ячейку записывается выход первого сумматора, равный 1+0=1, во
'О >0 ' hl "J
0 SJ
ho
,0
'¦1
г)
Рис. 18.
вторую — содержимое первой ячеики в предыдущем такте (т. е. 1), а в третью — выход второго сумматора, равный
1 + 1=0. В итоге в ячейках памяти сдвигающего регистра оказываются записанными коэффициенты первого из обведенных рамочкой остатков.
На рис. 18, в показано состояние схемы после еще одного такта ее работы. Теперь уже содержимое ячеек — коэффициенты второго из заключенных в рамочку остатков.
Еще один такт работы схемы переводит ее в конечное состояние (рис. 18, г). В ячейках памяти получены коэффициента остатка, а последовательность символов 1,0,1 на выходе — это коэффициенты частного.
Приведем без комментариев схему, осуществляющую деление с остатком на произвольный многочлен g(X) (рис. 19), предоставляя читателю самому разобраться в принципе ее действия.
Схемы умножения и деления многочленов, рассмотренные нами,— это, по существу, уже готовые кодирующие устройства (или, как их называют, кодеры) для циклических кодов. В самом деле, вспомним правило кодирования линейным (п, k)-кодом. Если Л =CX0- • -^k-I— произвольное сообщение длины k, то ему сопоставляется кодовый вектор а = (сс0.. .(Xfl_1) G, (1)
где G — порождающая матрица линейного кода.
,86 Разумеется, правило остается в силе и для любого циклического кода, но на языке многочленов ему можно придать теперь иную, гораздо более удобную форму.
Если а(х)—многочлен, соответствующий вектору а, и
А (х) = а0 jTaiX+ . . . -\-(xk_^xk~1
— многочлен, соответствующий сообщению А, то равенство (1) перейдет в равенство многочленов
a(x) = A{x)g{x), (2)
где g(x) — порождающий многочлен циклического кода.
Шстнов
Рис. 19.
Для того чтобы убедиться в этом, достаточно подставить в (1) матрицу G из формулы (9) § 11 и проверить, что координаты получающегося вектора служат коэффициентами многочлена A(x)g(x).
Итак, операция кодирования сводится к умножению многочленов. При этом можно считать, что речь идет об обычном умножении многочленов, поскольку степень g(x) равна т, а степень А(х) меньше п—т, так что сумма степеней этих многочленов меньше п. Но схемы, которые мы здесь рассмотрели (рис. 14 и 16), как раз и вычисляют обычное произведение многочленов. Первая из них может служить кодером для циклического (7,4)-кода с порождающим многочленом х3+хЯ+1, а вторая — для произвольного циклического кода с порождающим многочленом g(x). Если на вход последней поступают информационные символы а0, at,. . ., ап_х (коэффициенты многочлена А(х)), то на выходе согласно (2) будем иметь коэффициенты кодового многочлена а(х).
На основе схем деления чрезвычайно удобно строить кодеры для систематических циклических кодов, в которых информационные символы отделены от проверочных (см. дополнение 4 к этому параграфу).
Даже наше беглое знакомство с устройствами кодирования показывает, что все они имеют унифицированную струк-
,87 туру. Как видно из рис. 16, путем определенных видоизменений схемы, предназначенной для одного кода, можно получить схему кодирования для другого кода. Поэтому в ряде случаев целесообразно использовать не конкретные схемы для каждого кода, а достаточно разветвленное устройство с большим набором стандартных элементов, работу которого можно было бы перестраивать, вводя в него ту или иную программу. Такое устройство, в сущности, и есть специализированная мини-ЭВМ с программным управлением.
