<< Предыдущая

стр. 32
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


(3.60)

со степенью
deg[f{X)} = кг < т. (3.61)
Эта же единица заносится в регистр формирования а(Х) при за-
мкнутом переключателе 52 и в дальнейшем не меняется.

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




1=т-г
Частное |а„-,|'"1 аг | а\ \ До | * | A S 2


Остаток \Ь,-ijfl Ь% I Ьр Г



Рис. 3.6. Схема деления многочленов /(х) : д(х) —
а(х)д(х) + Ь(х).

На последующих I = т — г тактах алгоритм деления остается
таким же. Так, если степень укороченного многочлена f(X) в (3.60),
Глава 3. Циклические коды

равная к\ (3.61), остается большей и равной г, то с помощью цени об-
ратной связи производится укорочение теперь уже многочлена f(X)
из (3.60).

f{X) = f(X) (3.62)
= f(X)
со степенью
(3.63)
-к2<ку.
Таким образом, после I = т — г тактов мы получаем разложение
(3.59), причем, в регистре делимого находится остаток от деления
Ь{Х). После этого, ключ 51 размыкается, переключатель 52 перево-
дится в нижнее положение и на следующих г тактах остаток Ь(Х)
заносится в регистр формирователя остатка.
Как уже упоминалось ранее, кодер систематического кода не ис-
пользует при своей работе сомножитель а(Х) из разложения (3.59).
Его задачей является только получение остатка от деления сдви-
га информационного многочлена на порождающий многочлен д(Х).
Этот остаток образует затем младшие разряды кодового слова.



0
п
Такт fiX) ft,>
] 0
0 0
0
1 1 1

1
10
1
1
1 1
т Г 1 I 0
0
ТТТЛИШ 1 ! 0
'()
3

1 1
гп| |
4

Остаток
5



Рис. 3.7. Схема деления многочлена 1 + X + X2 + X4 на
1 + Х2.

В связи с вышеизложенным, схему деления двух многочленов
(рис. 3.6) для нужд кодирования можно существенно упростить. За-
метим, что для получения остатка от деления по алгоритму Евклида,
нам достаточно хранить в памяти помимо делимого только промежу-
точные суммы. Если степень д(Х) равна г, каждая промежуточная
сумма занимает не более чем г двоичных разрядов и обновляется на
каждом такте процедуры деления, причем, на этом же такте про-
изводится сложение очередного двоичного разряда промежуточной
суммы с соответствующим разрядом делимого. Таким образом, схе-
ма деления многочлена f(X) = 1 + X + X2 + X4 на д{Х) = 1 + X2
3.5. Схемная реализация циклического кодирования
•*.




(рис. 3.5) преобразуется в схему получения остатка от деления (рис.
3.7). Здесь уже не требуется предварительной загрузки делимого в
регистр деления, а остаток bo, b\ образуется в этом регистре на пятом
такте.
Выше мы подробно разобрали схемные реализации алгоритмов
деления Евклида. Покажем теперь принцип действия схем кодиро-
вания циклических кодов, построенных на регистрах сдвига с обрат-
ными связями. Рассмотрим уже знакомый нам систематический код
Хэмминга с порождающим многочленом д(Х) = 1 + X+ X3 (3.24).
Пусть передается информационный вектор и = (1001) из (3.30). Со-
гласно (3.35), ему соответствует кодовое слово в систематическом
виде v = (011 1001). Алгоритм деления Евклида для вычисления
проверочных разрядов приведен в табл. 3.2. Здесь делимым являет-
ся информационный многочлен и^г\Х), делителем - порождающий
многочлен д(Х). Проверочные разряды определяются как коэффи-
циенты многочлена Ь(Х), который представляет собой остаток от
деления и^(Х) на д(Х).

Для формирования кодового слова v по информационному век-
тору и используется цепь деления (рис. 3.8). Для получения про-
верочных разрядов, воспользуемся вычислениями, приведенными в
табл. 3.2. Поместим информационные биты и = (1001) во входной
регистр и обнулим разряды верхнего регистра формирователя остат-
ка bo,bi,b2- Ключ выходного регистра находится в положении 51, а
цепь обратной связи в устройстве деления замкнута. На первом такте
старший разряд двоичного информационного вектора «з заносится
во выходной регистр сдвига, одновременно сумма щ и Ь% подается в
цепь обратной связи регистра формирования остатка.

Результат вычисления из © & = 1 заносится в разряды & и ^1
2 о
верхнего регистра. Обратим внимание на тот факт, что при вычис-
лении первой промежуточной суммы в алгоритме деления Евклида
(см. табл. 3.2) происходит сложение < i с щ и до с и%. Это в точности
?
соответствует сложению Ь\ = & = 1 с разрядами, поступающими
о
из входного регистра сдвига (см. рис. 3.8) двумя и тремя тактами'
позже. Таким образом, на нервом такте by = Ьц = 1, a. b2 = 0-


Замечание. Операция сложения производится по правилам ариф-
метики по модулю 2 и обозначается знаком ©. Заметим, что в
арифметике по модулю 2, «-1» равна «+1» и операция вычитания
эквивалентна операции сложения,.
182 Глава 3. Циклические коды




SI СХ С$2 Такт: л = 0 Start


ь
ь« > *2 LJJLJ
!••(, V, V; V, l> 4 V5 Vb
U0 И| И 2
Кодовое слово
Информационное
слово

Такт:л=1


Ьо Ь, Ьг [ _ , *




Sl<-\ °S2 Такт:п =


*o *i «2
- LXJ




S1<A ° S 2 Такт: л = 3


[_;!>2
bo ь, h
1-l-l-llU V, V5 Vj V4 V,
SI


S1<A ° S 2 Такт: n = 4



*« *Г ь2 L T


Р и с . З.8. Кодер систематического циклического (7,4)-кода
с порождающим многочленом д(Х) = 1 + X + X 3 .


Так как схема получения кодового слова v по информационному
вектору и остается неизменной во времени, то она обладает свой-
ством линейности относительно операций в поле GF{2). Следова-
тельно, многократные сдвиги и суммирования коэффициентов по-
3.5. Схемная реализация циклического кодирования

рождающего многочлена д(Х) и полученные промежуточные резуль-
таты соответствуют промежуточным результатам алгоритма деле-
ния Евклида (табл. 3.2).
На втором такте разряд «2 загружается в выходной регистр фор-
мирования кодового слова. Одновременно вычисляется сумма мг с
очередным значение Ьг- Результат u-i фЬг = 0 подастся в цепь обрат-
ных связей. Таким образом, значение & равно «О», а Ъ\ — Ьг = 1.
о
На третьем такте в выходной регистр загружается информацион-
ный разряд щ и, одновременно, вычисляется сумма щфЬ2- Результат
вычисления гц © Ъч = 1 поступает в цепь обратных связей и после
= =
третьего такта Ьо & Ьг — 1-
1
На четвертом такте в выходной регистр заносится младший раз-
ряд щ. Вычисленное значение щ ф Ьг = 0 подается в цепь обратных
связей. В результате имеем Ьо = 0 и Ь\ = Ьг = 1-


5,0 Р Si
4

b0 b\ bi
Обратная связь
lololil
v, v 4 vs
v, v2
Кодовое слово


Р и с . 3.9. Процедура считывания проверочных символов.

Согласно алгоритму деления Евклида, после четвертого такта
многочлен Ь(Х) = & + Ь\Х + Ь^Х2 равен остатку от деления и^г\Х)
о
на д(Х). Формирование проверочных символов завершено. На пя-
том, шестом и седьмом тактах проверочные символы &> Ь\ и Ьо До-
2
г
писываются к старшим* разрядам и( \Х) кодового слова v(X). Для
этого оба ключа предварительно' переводятся в положение 52 (рис.
3.9).
В рассмотренном примере показана реализация алгоритма де-
ления Евклида с помощью регистра сдвига со встроенными сум-
маторами, поэтому данная схема не ограничивается приведенными
числовыми значениями. Исходя из заданного многочлена д(Х) =
1 + giX + д2Х2 Н hgr-\Xr˜l + Xr, можно построить схему коди-
рования для любого двоичного циклического (п, &)-кода (рис. 3.10).

Замечание. Таким, оке образом строятся кодеры дуальных цикли-
ческих кодов с порождающим многочленом h(X).
184 Глава 3. Циклические коды




Выходной буфер с кодовыми символами



проверочные | информационные
символы символы
Входной буфер с информацией ными
символами



Рис. 3.10. Кодер систематического циклического (п,
кода с порождающим многочленом д(Х).

<< Предыдущая

стр. 32
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>