Устройство для формирования остатков по модулю Советский патент 1988 года по МПК G06F11/08 

1 1 I I I

а|Н «ая л% М а4( / М «4г Ъ К ,|/ «.

j TJ.

л,ле|в, , ff «,а.

Л

kJktll/ll%

иI

СО

со

со

:о

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

24

1,

где V 2 , при t О, 1, 2, 3, 4...

Целью изобретения является расширение области применения за счет фор- М11рона1 ия остатков по модулю чисел Ферма.

На фиг. 1 представлена схема уст- ройства для формирования остатков по модулю; на фиг. 2 - схема блока свертки (схемы даны для случая РЗ г- 17, п 32, V 4).

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

Блок 3 свертки содержит для чет- ного 1 (фиг. 2а) группу одноразрядных OT-iMaropoB 6.1-6.4, а для нечетного 1 (фиг. 2б) - группы одноразрядных г.ум.;аторог.( 7.1-7.4 и 8.1-8.4.

Пртпгцип работы устройства следующий

Пусть задано число А (п) с коли- м р.cTotJM разрядов п v

A(u) (О

:0

Остаток числа по модулю чисел Ферм. рапен остатку от суммы

. |:aj,,.a;.2(-1) , (2)

i-n

где 1 Ькруглением до ближайшего 6оль;:сго целого числа. Оболначяв

V ;

Л

J

1., 2

получают

е-(

R (-1), .(3).

Таким , получение остатка связано с суммированием 1 частей AJ разрядиистьп V числа А (п), причем псе начот ые слагаемые А отрицательны. При отработке суммы (3) еди- ни 1а перепл:н1ения v-разрядной сетки слагаемых Л; одинакового знака эквивалентна еднгпще младшего разряда тех же слагаемых, но с противоио- ЛОХСН11М зт1аком. Это обстоятельство

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

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

-Aj Aj

F - (Aj + AJ) - 2, (4)

где A: - обратный код от А;;

S - поправка.

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

R ...(А„ - А, -S) + AJ + S)-. ..F.

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

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

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

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

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

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

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

КОВ по модулю чисел Ферма, блок свертки при 1-нечетном содержит вторую группу одноразрядных сумматоров, причем инверсные входы второго слагаемого одноразрядных сумматоров

5

с 5

0

0

0

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

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