Для построения такого кодирующего устройства не обходимо иметь два устройства: одно, обеспечивающее умножение многочлена на хг, другое, обеспечивающее
деление полученного произведения xrq(x) |
на |
Р(х). |
Для |
выполнения первой |
операции |
специального |
устройства |
не пробуется, так как умножение .многочлена на хг |
озна |
чает добавление к |
этому многочлену |
справа г |
нулей. |
Рассмотрим подробнее вопрос |
деления |
многочленов. |
Двоичные последовательности могут быть записаны двумя способами: или непосредственно в двоичной фор ме, или в виде многочленов. Между этими формами за писи имеется следующее соответствие. Единицы при ДРОИЧНОЙ форме записи свидетельствуют о наличии чле нов в многочлене, имеющих степень на единицу меньше порядкового номера разряда в двоичной записи при от счете разрядов справа налево. Нулям в двоичной записи соответствует отсутствие членов многочлена со степеня ми, также на единицу меньшими порядкового номера раз ряда, отсчитанного тем же способом. Следовательно, число разрядов при двоичной записи на единицу больше степени соответствующего многочлена. Обе формы запи си двоичных последовательностей имеют вид:
1) F1(x)=xs+x4+x3+x2+\; |
Fi(x)s= |
100011 101; |
2) F2{x)=xu+x?+\\ |
F2(x) = |
100000001 001. |
Прежде чем рассмотреть особенности построения уст ройств, осуществляющих деление многочлена на много член, поясним несколько подробнее само деление. Пусть требуется разделить многочлен xs+x6 + x3 + x + 1 на мно гочлен х* + х+\. Запишем деление в столбик:
l . v » + 0 x ' + l ; r « + 0 ; ^ + 0 |
* 4 - l ^ + 0 * a + l * + l |
1х*+0х3+0х2-\-\х+1 |
1Х 8+0Х 7 +0Л ?+1Д :5 |
+1Л :* |
|
l * H - 0 x s + l x 2 - f - l * + l |
|
|
|
№+\х*+\хъ+1х*+\х*ь |
|
|
0 х 7 4 - 0 * в + 0 * 6 |
+ 0 х 4 + 0 л : 3 |
|
1 * » + 1 * 6 + 1 ; е 4 + 1 х 3 + 0 л - 2 1Д-»+0А:6 +0Л^+1Л-3 +1Л-2
1 х 6 + 1 ^ + 0 д ; 3 + 1 д - 3 + 1 л ;
\х6+0х*+0хЗ+1х2+\х
1*4 -|-0л:3 +0л:2 +0л:+1 1 * 4 + 0 л - 3 + 0 д - а + 1 л : + 1
Qx3-\-Qx2-\-lx-\-0 — остаток
Деление производится обычным способом, но ниж
няя строчка |
вычитается из верхней |
по модулю |
2, что |
эквивалентно |
сложению по модулю 2. |
|
|
Запишем |
теперь это же деление, |
пользуясь |
только |
коэффициентами |
многочленов: |
|
|
|
~. |
1010010ПЦ0011 |
|
|
|
w |
10011 |
10 111 |
|
|
|
|
|
|
|
|
ш 0 0 0 0 0 |
|
|
|
|
|
- Л И Ю |
|
|
|
|
|
^ 1 0 0 1 1 |
|
|
|
|
|
да n o i l |
|
|
|
|
|
^ 1 0 0 1 1 |
|
|
|
|
|
^ 1 0 0 0 1 |
|
|
|
|
|
w 1 0 0 1 1 |
• |
|
|
0010 — остаток
Мз этого примера ясно, что деление заключается в последовательном сложении по модулю 2 делителя вна чале со старшими членами делимого, затем со старши ми членами (начиная с первого значащего члена) полу чившегося остатка и так до тех пор, пока, наконец, сте пень остатка не станет меньше степени делителя. Такая последовательность операций (суммирования) при деле нии любого многочлена на многочлен Р(х) степени г может быть осуществлена регистром с обратными связя ми, состоящим из г ячеек и (z—1) встроенных суммато ров, где 2 — количество членов этого многочлена. Пос леднее объясняется тем, что сумматор для сложения старших разрядов многочлена Р(х) и последовательно сти информационных элементов не нужен, так как ре зультат сложения старших разрядов делимого и дели теля равен нулю. Место включения сумматоров опреде ляется структурой многочлена делителя Р(х).
Для рассмотренного выше примера схема регистраделителя приведена на рис. 6.12а. На вход регистра по ступает, начиная с высшего разряда, последовательность разрядов многочлена-делимого. Как только первый раз ряд этой последовательности появляется на выходе, про исходит суммирование по модулю 2 делителя и первых разрядов делимого и в регистре записывается остаток. Затем при появлении на выходе регистра первой едини цы остатка производится суммирование делителя с этим 362
остатком и т. д. Наконец, после записи последнего раз ряда делимого в регистре фиксируется окончательный остаток. Очевидно, что для деления многочлена степени (/;—1) на регистр-делитель необходимо подать а тактов (по числу членов делимого).
Рис. |
6.12. |
Схемы |
регистров-делителей |
инфор |
мационных |
последовательностей |
соответствен |
но на |
многочлен: |
|
|
|
а) хЧ-x+l; |
б) Х 2 |
+ А - + 1 ; в) хъ+х^+х2 |
+ 1 |
'Примеры |
построения |
регистров |
с логическими обрат |
ными связями, обеспечивающих деление информацион
ной |
последовательности на |
многочлены х2+х+\ |
и |
хъ + х* + х2+\, |
представлены |
соответственно на |
рис. |
6.116, |
в. |
|
|
|
•На основании вышеизложенного нетрудно построить схему кодирующего устройства циклического кода.
Для примера рассмотрим построение преобразовате ля циклического кода (10,6), эквивалентного коду Хэм
минга, исправляющего |
одиночные ошибки. |
Такой |
код |
характеризуется |
/г' = 6, |
г=4 |
и «='10 . |
Из табл. 6.7 |
для |
л = 4 выбираем |
образующий |
многочлен |
Р(х) |
=х*+х+1. |
Кодирующее устройство такого кода будет состоять из двух сдвигающих регистров: одного для временной за держки информационных разрядов, а другого для деле
ния |
информационной |
последовательности |
на образую |
щий |
многочлен |
(рис. |
6.13). |
|
Схема рис. |
6.13 |
работает следующим |
образом. Ин |
формация на вход кодирующего устройства поступает в
последовательном |
коде. |
Для деления |
многочлена |
x'G(x), имеющего |
степень |
( л — 1 ) , требуется |
(п—1) + 1 = |
= ft тактов. В нашем примере п. = 10. В течение первых г тактов оба регистра заполняются информационными разрядами. Затем в течение последующих k тактов про исходит деление информационной последовательности на
образующий |
многочлен, |
и |
на |
выход |
поступают все k |
|
_ Лш&я_£Э&£>кки |
|
В х |
Г г --, |
j — I |
i — 1 |
; — » ~l |
ВИХ |
а- |
|
|
|
|
|
I
... (_
Рис. 6.13. Функциональная схема кодирующего устройства циклического кода
информационных разрядов комбинации (ключ |
/ закрыт, |
а ключ // открыт). Остаток R(x) от деления |
комбина |
ции первичного кода на образующий многочлен фикси руется на элементах регистра-делителя. Далее ключ // закрывается, разрывая обратную связь и исключая влияние выхода регистра на его вход, а ключ / открыва ется. В течение последующих г тактов на выход коди
рующего устройства поступает остаток R(x), |
а оба ре |
гистра заполняются первыми г разрядами |
следующей |
комбинации. Состояния обоих ключей вновь изменяют ся, и весь цикл повторяется для новой комбинации. Та ким образом, на выход кодирующего устройства посту пает вся «-разрядная комбинация, состоящая из первых k информационных и последующих г проверочных раз рядов.
Недостаток |
описанного |
кодирующего устройства — |
необходимость |
линии задержки |
информации на г так |
тов — можно |
устранить, |
если |
использовать несколько |
видоизмененную схему деления многочлена на много член, представленную на рис. 6.14а.
Эта схема эквивалентна схеме рис. 6.13 в случае де ления многочленов, оканчивающихся г нулями. Только здесь деление начинается сразу с приходом первого раз ряда комбинации и оканчивается после прихода /г-го разряда. При использовании схемы рис. 6.14а дополни-
тельной задержки не требуется й кодирующее устрой* ство имеет вид, представленный на рис. 6.146. В течение первых к тактов к информационных разрядов поступают на выход и одновременно происходит деление информа ционной последовательности на образующий многочлен
а)
т
Выл
Вл
6)
Вл
Рис. 6.14. Упрощенные схемы кодирующего устройства циклического кода
(ключ // открыт, а ключ / закрыт). Затем ключ // зак рывается и открывается ключ /. В течение последующих г тактов на вход подаются нули и из регистра на выход поступает остаток от деления R(x). При этом сам ре гистр очищается. По окончании передачи комбинации после п-го такта ключи возвращаются в исходные со стояния и начинается преобразование следующей ком бинации и т. д.
Рассмотрим теперь построение и работу декодирую щего устройства. На вход декодирующего устройства из
кснала |
поступает |
последовательность |
H(x)=F(x) |
+ |
+ Е(х), |
где F(x) — исходная комбинация; |
Е(х)—поме |
ха, представляемая |
в виде многочлена от х, содержаще |
го единицы в тех разрядах, где произошли ошибки. Сог ласно структуре построения циклических кодов призна
ком наличия ошибок в принимаемой |
комбинации |
Н(х) |
является ее неделимость без остатка |
на |
Р(х) или, |
что |
т». же, неделимость без остатка Е(х) |
на |
Р(х). |
|
