Устройство для формирования остатков по модулю

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (!9) (11) А1 (51) 4 С 06 Р 11/08

ОПИСАНИЕ ИЗОБРЕТЕНИЯ . Н АВТОРСНОМУ СВИДЕТЕЛЬСТВУ

«)

°,«

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3968649/24-24 (22) 21.10.85 (46) 23.04.87. Бюл. № 15 (71) Львовский политехнический инсти-. тут им. Ленинского комсомола (72) Н.В. Черкасский (53) 681.3(088.8) (56) Авторское свидетельство СССР

¹ 1084798, кл. G 06 F 11/08, 1982.

Гаврилов Ю.В., Пучко А.M. Арифме— тические устройства быстродействующих

ЭЦВН. — М.: Советское радио, 1970, с. 150, рис. 3.3.2. (54)(57) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

ОСТАТКОВ ПО МОДУЛЮ, содержащее (1-1) группу одноразрядных сумматоров (1

I1 ) — где р — разрядность числа, Lv ) р — простое число), причем входы первого, второго слагаемого и переноса одноразрядных сумматоров первой группы соединены соответственно с первой, второй .и третьей группы по р-разрядов информационного входа устройства,выходы суммы одноразрядных сумматоров

i-й группы соединены с входами первого слагаемого соответствующих одноразрядных сумматоров (i+1)-й группы i

1-(1-3), входы второго слагаемого одноразрядных сумматоров (i+1)-й группы соединены соответственно с разрядами (i+3) é группы информационного входа устройства, выход переноса

k-го (k=1-и-1) одноразрядного сумматора i-й группы соединен с входом переноса (k+1)-го одноразрядного сумматора (i+1)-й группы, выходы суммы одноразрядных сумматоров предпоследней группы соединены с входами первого слагаемого соответствующих одноразрядных сумматоров последней группы, выход переноса j-го одноразрядного сумматора предпоследней группы (j = 1 †s=n-р(1-2) соединен с входом второго слагаемого (j+1)-го одноразрядного сумматора последней группы, вход переноса j-ro одноразрядного сумматора последней группы соединен с выходом переноса ()-1) одноразрядного сумматора последней группы, выход переноса t-ro одноразрядного сумматора последней группы (t=s+1-р-1) соединен с входом переноса (t+1)-ro одноразрядного сумматора последней группы, о т л и ч аю щ е е с я тем, что, с целью расп)ирения области применения за счет формирования остатков по модулю чисел Ж

Мерсенна, оно содержит блок свертки, содержащий группу одноразрядных сумма- %Ф торов, группу элементов И, элемент

ИСКЛЮЧАЮЩЕЕ ИЛИ и элемент И, причем выход переноса р-го одноразрядного сумматора i-й группы соединен с входом переноса первого одноразрядного сумматора (i+1)-й группы, выход переноса р-го одноразрядного сумматора последней группы соединен с входом переноса первого одноразрядного сум- © матора последней группы, выход переноса s-ro одноразрядного сумматора (1-3)-ей группы соединен с входом переноса (s+1)-го одноразрядного сумматора последней группы, выходы суммы одноразрядных сумматоров с (s+1)-го

rio p-й (1-.3)-й группы соединены с вхо- 35 дами первого слагаемого соответствующих одноразрядных сумматоров последней группы, выход переноса t-го одноразрядного сумматора (1-3)-ей группы соединен с входом второго слагаемого (t+1)-го одноразрядного сумматора по1305685 следней группы, выходы одноразрядных сумматоров группы блока свертки являются выходом устройства, выходы суммы одноразрядных сумматоров последней группы и выход переноса s-го одноразрядного сумматора последней группы соединены соответственно с первыми входами элементов И группы блока свертки, причем в блоке свертки первые входы (р+1)-го и (я+1)-го элементов

И группы соединены соответственно с первым и вторым входами элемента

ИСКЛЮЧАЮШЕЕ ИЛИ, выход которого и первые входы элементов И, кроме (р+1)-ro и (s+1) ãî,ãðóïïû соединены соответственно с входами элемента И, 1

Изобретение относится к вычислительной технике и предназначено для формирования остатков по модулям чисел Мерсенна, которые имеют вид М и

2 -1, где р — простое число, и используются при цифровой обработке сигналов.

Целью изобретения является расширение области применения за счет формирования остатков по модулю чисел 10

Мерсенна.

На фиг. 1 представлена схема устройства для формирования остатков по модулю; на фиг. 2 представлена схема блока свертки. f5

Устройство для формирования остатков по модулю (фиг. 1) содержит одноразрядные сумматоры 1.1-1.р, объединенные в группы 2.1-2(1-1), блок 3 свертки, вход 4 блока 3 свертки,вы- 20 ход 5 устройства. Блок 3 свертки (фиг. 2) содержит группу элементов И

6.1-6.р, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 7, элемент И 8, группу одноразрядных сумматоров 9.1-9.р.

В основу принципа работы положены следующие соображения.

Исходное число А может быть представлено в виде многочлена

A=A +A2 +A22 +... р 2Р о

Остаток от деления многоразрядного числа А на модуль числа Мерсенна М равен инверсный выход которого соединен с вторыми входами элементов И группы, выходы которых, крсме (р+1) — го, сое— динены с входами первого слагаемого соответствующих одноразрядных сумматоров группы, выход (р+1)-го элемента

И группы соединены с входом второго слагаемого (s+1)-го одноразрядного сумматора группы, выход переноса р — го одноразрядного сумматора группы соединен с входом переноса первого одноразрядного сумматора группы, выход переноса k-го одноразрядного сумматора группы соединен с входом переноса (k+1)-го одноразрядного сумматора группы.

2 (А) М =(А +A„+A ... )М где АО,А1,А2 . — последовательные группы двоичных чисел по р-разрядов, начиная с младших.

В соответствии с (1) и (2) вес р-ого разряда суммы (2) равен весу младшего разряда, в связи с чем выходы переносов старших р-разрядов сумматоров могут быть соединены с входами переносов младших разрядов, что позволяет синтезировать прямоугольную матрицу сумматоров с диагональной цепью распространения сигнала переноса, На выходе матрицы сумматоров должен быть блок свертки, назначение которого состоит в преобразовании входного (р+1)-разрядного кода в рразрядный остаток.

Устройство для формирования остатков по модулю (фиг. 1 и 2) работает следующим образом:

Рассмотрим работу устройства на примере формирования остатка от 32разрядного числа по модулям числа

Мз

Исходное 32-разрядное число (фиг. 1) развито на трехразрядные числа A ° ..

А„, . В этом случае устройство содержит группы 2.1-2.16 в каждой из которых по три сумматора 1 ° 1 — 1.3, а в группе 2.9 — два сумматора,так как число А — двухразрядное. В первой группе 2.1 наблюдается сумма чисел

А + А1+А, в коде с сохранением пере1305685 носов. В последующих группах складываются полученный результат со спeдующим числом Л также в коде с сохранением переносов, при этом единицу переноса из старшего сумматора сумми- руют с младшим разрядом следующей группы.

В блоке 3 элемент И 8 не препятствует прохождению сигналов с входа 4 через элементы И 6 на входы суммато- 10

42 ров 9, так как при наличии хотя бы одного нулевого сигнала на входе элемента И 8, на входе его будет едиэ ничный сигнал. Только код со всеми единичными сигналами поступит на входы с мматооов 9 в виде нулевых сигналов. Правомерность такого преобразования вытекает из того, что остаток

"111" по модул М> 7„> равен

1lpppll

Ar! 305685

Составитель В. Клюев

Техред А.Кравчук

Корректор Л. Патай

Редактор Г. Гербер

Заказ 1453/47 Тираж 673

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Рауыская наб., д. 4/5

Подписное

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4