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

 

Изобретение относится к вычислительной технике и предназначено для формирования остатков чисел по модулям F чисел Ферма, которые описываются выражением F 2 + 1, V 2, t О, 1, 2... Целью изобретения является расширение области применения за счет формирования остатков по модулю чисел Ферма. Поставленная цель достигается тем, что в устройстве, содержащем одноразрядные сумматоры 1, объединенные в группы 2 , и блок 3 свертки, содержащий группу одноразрядных сумматоров, блок 3 свертки содержит дополнительно вторую группу одноразрядных сумматоров с соответствующими связями. 2 ил. о S

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

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

РЕСПУБЛИК

1 А1 и") (11) 1 114 С 06 F 11 08

ВСЕГО1 1 3! И

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

13 „" .13

СМЪЛЩ 1ЫА,ф -Фр 4

"з "в Ф Ф ааааа с а,д, аз а еае Ь еаежа ав пей ФФ 3 ВВ аае ау ар

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3972606/24-24 (22) 04. 11. 85 (46) 23.05.88. Бюл. В 19 (71) Львовский политехнический институт им. Ленинского комсомола (72) Н.В. Черкасский (53) 681. 3(088. 8) (56) Авторское свидетельство СССР

У 1084798, кл. С 06 F 11/08, 1982.

Авторское свидетельство СССР

В 1305685, кл. G 06 F 11/08, 17.04.86. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

ОСТАТКОВ ПО МОДУЛЮ (57) Изобретение относится к вычислительной технике и предназначено для формирования остатков чисел по модулям F чисел Ферма, которые опич сываются выражением F = 2 + 1

У

V = 2, t = О, 1, 2... Целью изобретения является расширение области применения за счет формирования остатков по модулю чисел Ферма. Поставленная цель достигается тем, что в устройстве, содержацем одноразрядные сумматоры 1, объединенные в группы 2, и блок 3 свертки, содержащий группу одноразрядных сумматоров, блок 3 свертки содержит дополнительно вторую группу одноразрядных сумматоров с соответствуницими связями.

2 ил.

1397919

-А A +S30

= е.тво. разрядов

A(n) = Q а,2

V ,1 получают

Изобретение относится к вычислителыгой технике и предназначено для формирования о статкон о т n-pa эрядпих чисел по йодулю чисел Ферма, которь,е описылаются выражением

Г = 2 + 1

»

Э

С где V = 2, npEI t = О, 1, 2, 3, 4...

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

Ферма.

На фиг. 1 представлена схема устройства для формирования остатков по модулю; на фиг. 2 — схема блока свертки (схемы даны для случая F э

17, n=32, v=4).

Устройство для формирования остатков по модулю (фиг. 1) содержит одноразрядные сумматоры 1.1-1.4, объединенныо в группы 2.1-2.7, и блок 3 сВ0рТКп с входами 4 и выходами 5.

Блок 3 свертки содержит для четного 1 (фиг, 2а) группу одноразрядных с»иматорон 6,1-6.4, а для нечетного

1 (фш . 2б) — грушы одноразрядных су; ...аторов 7. 1-7. 4 и 8, 1-8. 4.

ITpnnvлп работы устройства следующий. ! усть задано число А (п) с колиС!-таток числа по модулю чисел

Ферм; рапеп остатку от суммы е-!

R --- g ) а -„а,р2 (-1) ), (2) ! A t .де 1 = г/» с округлением до ближайше гг t. îë :;, ã целого числа.

Обт .на ив (-<

- -c А (-1) > (3) .

Таким обозом, получение остатка связано с суммированием 1 частей А °

3 разрядностью v числа А (n), причеи псе нечет..ые слагаемые А отрица3 телы ь.. Нри отработке суммы (3) единя. а переполнения v-разрядной сетки слагаемых А одинакового знака эквивалентна едп.еще младшего разряда

-,ех же слагаемых, но с противоположньм знаком. Зто обстоятельство

f5 позволяет синтезировать прямоугольную матрицу свертки беэ увеличения разрядной сетки сумматоров по мере накопления результата с горизонтальной цепью распространения переноса сумматоров.

В целях исключения всех операций вычитания необходимо преобразовать (3), причем знак единицы переполнения предыдущей ступени должен совпадать со знаком слагаемых последующей ступени матрицы. Это возможно, если инвертировать результаты, получаемые на выходах сумиаторов всех ступеней.

На входы сумматоров первой ступени следует подать слагаемые в такой комбинации инверсных и прямых кодов, чтобы получаемый в результате свертки остаток не требовал коррекции. Для этого используются дополнения по модулю F отрицательных слагаемых А

J и всех результатов, получаемых на выходах сумматоров каждой ступени:

ВР - (А +А) 2, (4) где А — обратный код от А

3 Ф

3 — поправка.

С учетом изложенного выражение (3) преобразуется в форму

К (е ° ° (Ао А 8) + А2+ Э ° .

Здесь горизонтальные линии означают инверсию слагаемых или сумм, заключенных в скобках. Можно инвертировать слагаемые А; так, что взаимно компенсируются все отрицательные и положительные значения S

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

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

В этом случае исходное число разбивается на восемь групп по четыре разряда в каждой. Разбивка числа А(п) па группы A ... А. показана на фиг.1, причем нечетные числа отрицательны.

Блок 3 позволяет получить наименьший вычет. В данном случае 1 8 — четное, и блок 3 свертки выбирается по схеме фиг. 2а.

Группы разрядов исходного числа поступают на входы одноразрядных

3 13979 сумматоров соответствующих групп, полученная сумма и перенос с выхо;.,ов одноразрядных сумматоров последней группы 2.7 поступают на вход блока 3 свертки, на выходе которого формиру5 ется нужный остаток.

Формула и з о б р е т е н и я

Устройство для формирования остатков по модулю, содержащее 1-1 группу одноразрядных сумматоров (1

ГA× t где ч = 2, t = О, 1, 2, ив разрядность числа) н блок свертки, содержащий группу одноразрядных сум15 маторов, причем прямые входы первого слагаемого одноразрядных сумматоров

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

20 переноса последнего одноразрядного сумматора к-й группы соединен с входом переноса первого одноразрядного сумматора (к+1)-й группы (к= 1,...

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

v-1), выходы одноразрядных сумматоров первой группы блока свертки являют30 ся выходом устройства, выход переноса р-го одноразрядного сумматора первой группы блока свертки соединен с входом переноса (р+1)-го одноразрядного сумматора первой группы блока сверт- 35 ки, отличаю.щее ся тем, что, с целью расширения области применения за счет формирования остатков по модулю чисел Ферма, блок свертки при 1-нечетном содержит вторую

40 группу одноразрядных сумматоров, причем инверсные входы второго слагаемого одноразрядных сумматоров

19

4 первой группы соединены с соответст ующими разрядами второй группы информационно го входа устрой стна, вьходы суммы одноразрядных сумматоров к-й группы соединены с инверсными входами второго слагаемого соответствующих одноразрядных сумматоров (к+1)-й группы, выходы суммы одноразрядных сумматоров и выход последнего одноразрядного сумматор= последней группы при 1-четном соединены соответственно с инверсными входами первого слагаемого одноразрядных сумматоров первой группы и с входом переноса первого одноразрядного сумматора первой группы блока свертки, выход переноса последнего одноразрядного сумматора первой группы которого соединен с выходом устройства, выходы суммы одноразрядных сумматоров и выход последнего одноразрядного сумматора последней группы при 1нечетном соединены соответственно с инверсными входами первого слагаемого одноразрядных сумматоров второй группы и с входом переноса первого одноразрядного сумматора второй группы блока свертки, выход переноса последнего сумматора первой группы которого соединен с выходом устройства, причем в блоке свертки при 1нече гном выход переноса р-го одноразрядного сумматора второй группы соединен с входом (р+1)-го одноразрядного сумматора второй группы, выход последнего одноразрядного сумматора которой соединен с входом первого одноразрядного сумматора первой группы, выходы одноразрядных сумматоров второй группы соединены с инверсными входами первого слагаемого соответствующих одноразрядных сумматоров первой группы.

1397919

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

1екред А.Кравчук Корректор. М. Демчик

Род.i;; -о р I l. П пкол;ш чук

Тираж 704 Подписное

В1 ИМЭПИ Государственного комитета СССР по ц лам изобретешш и открьлий

1l3035, Иоск- а, Ж-35, Раув?ская наб., д, 4/5

32к:?3 3223

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