Устройство для деления многочлена на многочлен

 

Союз Советск ив

Социалистических

Республик

ОП ИКАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (i ii 951298 (61) Дополнительное н авт. саид-ву (51) М. Кл. (22) Зая влено 15.08.80 (21) 3005987/18 — 24 с присоединением заявки № (23) Приоритет

G 08 F 7/52

Ркударетмнный квинтет

СССР дв двдам нзоаретеннй и втарытнй

Опубликовано 15 08.82. Бюллетень № З0

Дата опубликования описания 15.08.82 (53) УЛ К 681.325 (088,8) E. Б. Бродская, А. П. Чурус, Е. Л. Спнваьсоваай (72) Авторы изобретения и В. И. Величко

13

ГЕХ 1 Ы (ГФ йИЬЛНОП1;А.

3 (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ МНОГОЧЛЕНА

HA МНОГОЧЛЕН

Изобретение относится к области передачи данных н может быть использовано в устройствах защиты от ошибок и в устройствах фазирования аппаратуры передачи дискретной информации.

Известно устройство для деления многочлена

5 на многочлен, используемое для вычисления синдромов . циклического кода (11.

Однако это устройство пригодно для обработки только двоичной информации.

Наиболее близким по технической сущности к данному изобретению является устройство, содержащее r элементов задержки, (r — 1) сумматоров, г+1 умножителей (где г — степень многочлена делителя), причем выход i ãî элемента задержкй соединен с первым входом

j-ro сумматора (где i = 1,..., r — 1, j = 1,..., r — 1), выход j-ro сумматора соединен с первым входом а-го элемента задержки (где а = 2,..., r), выход r-го элемента задержки соединен с ур входом (г+1) -го умножнтеля, выход которого соединен с входами r умножителей, выход b-го умножителя соединен с вторым входом j-го сумматора (где b = 2, . . ., r) (2).

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

Цель изобретения — повышение быстродейсг:. вия.

Поставленная цель достигается тем, что в устройство введены rсумматоров,,r умножителей, блок памяти и регистр comma, причем выход первого умножителя соединен с первым входом первого элемента задержки, информационный вход регистра сдвига подключен к входу устройства, выход с-ro элемента задержки соединен с первым входом d-го сумматора (где с=1,..., г, d = r,..., 2r — 1), второй вход которого соединен с выходом k-го-умножителя (где k = r+ 2,..., 2r+ 1), выходы m сумматоров соединены соответственно с вторыми входами r элементов задержки (где m- г, ..., 2r — 1) и подключены соответственно к выходам устройства, выход младшего разряда регистра сдвига соединен с третьим входом, r-ro сумматора, разрядные выходы регистра

951298

Формула изобретения сдвига соединены соответственно с первыми входами k умножителей, вторые входы которв1х соединены соответственно с выходами блока памяти.

На чертеже показана схема устройства.

Устройство содержит элементы 11 — 1 . задерЪ жки, сумматоры 2i — 21. 1, умножителя

31 — 3 -4.1, сумматоры 41 — 4Г умножители

51 ° 51, блок 6 памяти, регистр 7 сдвига.

В устройстве выход элемента 1,; задержки соединен с первым входом 2 -го сумматора (где i 1,..., r — 1, j = 1....., r -1), выход 2 j-го сумматора соединен с первым входом элемента 1а — го задержки (где а = 2, ...; r), выход элемента 11. задержки соединен 1S с входом 31.+,1 -ro умножителя, выход которого соединен с входами умножителей 3,;3 ., выход 3 Ь-го умножителя соединен., с вторым входом 2 j ro сумматора, (где Ь = 2,..., r), выход умножителя 3 соединен с первым вхо- 20 дом элемента 11 задержки, информационный вход регистра 7 сдвига подключен к входу устройства, выход 2 с-го элемента задержки соединен с первым входом 4 d-ro сумматора (где с = 1,..., r, d = r,..., 2 r — 1), второй 25 вход которого соединен с выходом 5 k-ro умножителя (где k = r + 2,..., 2 +1), выходы сумматоров 41 — 4, соединены соответственно с вторыми элементами 1, — 1> задержки и подключены соответственно к выходам уст- щ ройства, выход младшего разряда регистра 7 сдвига соединен с третьим входом сумматора

41, разрядные выходы регистра 7 сдвига соединены соответственно с первыми входами умножителей 51 — 5г, вторые входы которых соединены соответственно с выходами блока 6 папяти. Цепи передачи импульсов на чертеже не показаны. Количество элементов 11 — 11 задержки и количество сумматоров 41 — 4 равно степени делителя, количество умножите- 40 лей 31 - 31-+.1 и сумматоров 21 - 2 „зависит от вида делителя, количество умножителей

51 — 51, зависит от вида производящего полинома кода и длины кодовых комбинаций (от вида делителя и степени делимого). могут выполняться параллельно, причем число операций не зависит от степени делимого, Действительно, если имеется принимаемая последовательность

1 1 i 1

ah 1 an й1 O1 OlO" all 1 И-У.Л1 01РО и допустимо, что известен остаток Ri (х) от деления многочлена

@ Ю=0„ „Х"+ аИ Х",„",-a„Õ+ао на многочлен F (Х), то остаток R> (Х) от деления многочлена

9 (Х)о х +а х ...+ а х а Х+атi q

1 на многочцен F (Х) равен

И-Ъ"

1 а„х -о х+о1 ) mode(x)=

Г1 И 1 N1 1 И+

= а„„х+а„,х +а„,х +" +

a„ õ +а х +он- -а „„х" 3 ed И х) =

1 х(а >< Х + аи-Р +...+01Х+ аo)+o„„-o „„х" )мой (х) х Р„()кй„„-О„.„ f"

räå 1 1 — mod F (x).

И1

Так как величина Х у при передаче информации укороченным циклическим кодом представляет собой какой-то определенный многочлен степенИ меньше r, то каждый последующий остаток определяется предыдущим остатком, младшим разрядом делимого многочлена и старшим разрядом предыдущего делимого многочлена, Таким образом, устройство выполянет функции определения остатка при делении - многочлена многочлен, при этом требуется незначительное количество операций, независящее от длины делимого многочлена, т. е. увеличивается,быстродействие по сравнению с прототипом, Устройство работает следующим образом.

Вычисление в каждом j-ом такте остатка

R) от,деления многочлена 0 1 (х) на многочлен F (х) получается однотактным сдвигом

50 по элементам задержки вычисленного в предыдущем такте остатка R< „, поразрядного суммирования сдвинутого остатка R „с многочленом, записанным в ПЗУ, поразрядно умноженным на коэффициент старшего разряда, многочлена 0 - „(х) и Последующим прибав- 5> лением к полученной сумме младшего разряда многочлена 0 > (х), т. е. требуется выполнить всего четыре операции, некоторые иэ которых

Устройство для деления многочлена на мгогочлен, содержащее r элементов задержки, (r — i), сумматоров, (r + 1) умножителей (где r — степень многочлена делителя), причем выход i-ro элемента задержки соединен с первым входом j-ro сумматора (где i=1,..., r — 1, j = 1,..., r — 1), выход j ro сумматора соединен с первым входом a-ro элемента задержки (где а = 2,..., r), выход r-го элемента задержки соединен с входом (r+ 1)-го умножителя, выход которого соединен с входами r умножителей, выход b-го умножителя соединен с вторым входом j-го сумматора (где

Ь = 2,... r), о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены r сумматоров, r умножителей, блок памяти и регистр сдвига, причем выход

: первого умножителя. соединен с первым входом первого элемента задержки„информационный вход регистра сдвига подключен к входу устройства, выход с-го элемента задержки соединен с первым входам d-го сумматора (где с 1, .. r,d r,...2r — 1),второй вход которого соединен с выходом k-го умножителя (где k = r + 2,..., 2 r + 1), выходы m сумматоров соединены соответственно с вторыми входами г элементов залерж1298 ки (где m г..., 2 r — 1) и подключены соответственно к выходам устройства, выход младшего разряда регистра сдвига соединен с третьим входом r-го сумматора, разрядные

5 выходы регистра сдвига соединены соответст вельо с первыми входами k умножителей, вторые входы которых соединены соответствеи но с выходами блока памяти.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР У 710040, кл. 6 06 F 7/52, 1975.

2. Питерсон У., Уэлдон Э. Коды, нсправлаещие ошибки. М., "Мир", .197б, с. 199 — 200 (прототип) .