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

гл

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

F 2 +1,

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

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

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

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

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

Принцип гаиоты ус /ройстяа следующий.

Пусть задано число Л(п) с колаче- .; 1 Б ом р а 3 р ядов

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

В целях исключения операций вычи- талия необходимо преобразовать (3), причем знак единицы переполнения предыдущей ступени должен совпадать со знаком слагаемых по следующей ступени матршда. Это возможно, если инвертировать результаты, получаемые на выходах суг- Шаторов всех ступеней. На входы v,yMMaTopoB первой ступени следует подать слагаеьш1е в такой комбинации 1ншерсных и прямых кодов, чтобы получаег-ц.ш в результате свертки остаток не требовал коррекции. Для зтого используются дополнения по модулю F отрицательных слагаемых AJ и всех результатов, получаемых на выходах сумматоров каждой ступени

-Л, :, ; П - (Л + лр

т

5

где Л| - обратньй код от Л; ;

- поправка.

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

Изобретение относится к вычислительной технике и предназначено AI I -Ai I м -- I -Лз I Ояаиааам„а„а„еивоОо Ы 9 10 Оп сываются V 2 для формирования остатков чисел по модулям F чисел Ферма, которые опивыражением F 2 + 1, t О, 1,2... Целью изобретения является расширение области применения за счет формирования остатков по модулю чисел Ферма. Поставленная цель достигается тем, что в устройстве, содержащем одноразрядные сумматоры 1, объединенные в группы 2, и блок 3 свертки, содержащий группу одноразрядных сумматоров, блок 3 свертки содержит дополнительно вторую группу одноразрядных сумматоров с соответствующими связями. 2 ил. 0 4 ОпО в,1вна„«Лая«1,л,а -/If I «А M «ff«J i«(«« (Л

h-1

Л(п) - а,- 2

(1)

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

е-1 V

R -vll .,.; а; 2 (-1У

j O

гда i n/v с округлением го большего целох о числа.

ООозпачгл)

Л /.. aj,, 2 ,

J . Л

получают

(3)

R Л-(-1).

J.O

Такип образом, получение остатка связано с суммированием 1 частей Л ; разряд 5остью , числа Л(п), причем асе нечетные cjiaraeNn.ie Л отрицательные. При обработке суммы (3) единица переполне}1ия v-разрядной сетки слага- eMiiix А; од1шакового знака зкпиналент- на единице младУ1 ;го разряда тех же

5

0

5

А2)-У-Аб)+,

0

R - ...-i (АО +5 + А, -ь К

Можно 1 11вертировать AJ так, что компен.ируются все отрицательные и положительные значения 5 .

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

Работу устройства paccMOTpiiM на примере формирования остатка от 32- разрядного числа по модулю F 17. В этом случае исходное число разбивается на восемь групп по четыре разряда в каждой (фиг. 1), причем нечетные числа отрицательны. Блок 3 позволяет получить наименьш101 вычет и скомпенсировать при четном количестве групп поправку. Для компенсации используется код, равный разности чисел Ферма и поправки. В частности для F 17 этот код равен 15,о IIII. В данном сл-учае четное и блок 3 свертки выбирается по схеме фиг. 2а. Группы разрядов исходного числа по- cr naioT на входы одноразрядных сумматорон соотве TI , rj ,( .: групп, nf,.,; /- ченная сумма я нь-.: . оыхсг , - , - поразрядных су..;.. О1 пг; I. I.L .,,. групгпл 2.7 ппс1 уг:{;| 7 на гхол v:.:. / i .: свертки, на вы ;от1Г: K0,4jpc; t) фо;мк;,- ется нужный остаток.

Формула и 3 о б р с т fi л ; я

УстронсмЕо Л.ПЯ фггм : jai H ; Ov гатКОВ по модулю, СЛ1Л01 /K;iU(f;V 1-1

одноразряднь х c; M; aTOiJOB (1 И-

п-разрядность чис.Пс) и блок свертки, содержащий перк;, о группу одноразрядных сумматоргл;, причем входрл перво;о схпгаемого и входы переноса одноразрядных сумматоров первой, груп 11Ы соединены соответственно с первой к третьей группами из v-разрядов информационного входа устройства, прямые входы первого слагаемого одноразрядных сумматоров i-й группы (i 2,..., 1-2) соединены с (1+2)-й группой разрядов информационного вход устройства, выход переноса последнего одноразрядного сумматора к-й группы (к 1,..., 1-2) соединен с . фя.:.- входом первого одноразрядног о cy. тора (к+1)-й группы, выход псрено - р-го одноразрядного сумм.-ггорл по -лод- ней группы (р 1,...j v 1) со.;:ми;;ен с входом переноса (р+1у-го одно)л:-( яд ного сумматора последнее групчы, пь; ход переноса р-го г.-д);ор.-1зрядиого су.м- матора первой группы блока спертки соединен с входом переноса (р+)-го одноразрядного сумматора первой группы блока свертки, выход1 1 с:/1-1мы одноразрядных сумматоров первой группы блока свертки являются выходом устройства, отличающееся тем, что, с целью расширения применения за счет формирования ос-- татков по модулю чисел , блок свертки при сетном 1 содержит вто-г то группу одноразрях ных сумматоров, причем инверсные входы второго слага.,-

епого одно раз р.ядиьо; с:-/м с торов пер

10

15

20

95а ..-, - Jb

40

45

50

-.. .- ; П1|Ы с оед. iH . : ы с cooT t стиуК -- ; .чзряди Р: грулга: ичформ.н .иного входа уг , пыкии . .. iMbi одноразря;и : х г :..: л :ion к--.;; ;1уппы соединены : ;- . ,.-хи ).Ч|Д.| .ми второго слагаемого с.. не : с пгут-э-- щих одноразрядных ci Ti.M.i .. ii (нч-Р- i группы, выход пepeнoc i р- х ... Э рядного сумматора к-й rpyurai с-ч i - нен с инверсным входом пер ;- а / го одноразрядного сумматора (к- 1 --г группы, выход переноса последнего; одноразрядного сумматора первой пы блока свертки соединен с выход1.ч- устройства, выходы суммы одноразрядных с мматоров и выход переноса последнего одноразрядного сумматора последней группы .. ь. ин : г«-ь1 гоответственНО ПрГ НС и Т О 1 С 1 Н :. , . СИ.ЛЧИ

I j - ipi iv-r-.i гллт ae. .), 1,Н ;плг-.ряц. ых г .iaTO ioij пе;. i пугго с входом г;-. рено(-а iiepDo o о.гнора 1 рч,пнсч о сум- .матора первой груьпы блокл свертки, пьС ОД -, од11Г 11азр;:дкь х ров .и выход переноса последг его од-;- ип,разряд.IOго сумматор; п..с. еднеи rpvnrb лри .м 1 .медииепь: со-- : еTCT;feH ii; с инверсны - и вхо 7. пао- ci..-.гаамсI o о/1нор;;зр..гдных суммл- .. j; второй т pyjisn,; и с .дом г;ере- г:иго ггерпого (.j,. . o;i;i ,,п.-,- ...ф;.; ято;:о11 rpyniu; бло а .ч.ч .рткл, причем в блоке при i 4. jHOM npHi ibiC: ::. fft.i i .);)oru сля- (V.c од1,ораз.я,; ;:- х сум;- :i горев i.i (.-рой rpynrj.. с, :;Дч ;е Ы с входом логической едини1Цл1 устройства, перглгоса р-го однорлзряД .ого сумматора второй группы т-н с входом переноса (р+1)-го однораз.дно1-о сумматора второй гр% п;1ы, выход переноса посль;дне о одноразрядн-то сумматора второй групШ) соединен с входом переноса первого одмораз;-ьд;юго сх м- матора псртзой rpynnbi, выход c T-iMbi оди1. рл.рядных сумматоров второй груг шл соединены с .г нрер .ными входами первог о слагаемого соотгетствующих однс раз рядных сумматоров первой груп пы.