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

 

Изобретение относится к вычислительной технике и предназначено 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«(«« (Л

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

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

РЕСПУБЛИН

1 А1 ()9) (И) 51) 4 С 06 F 11 08

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

-41 Фаа -43 +l ч -лз +41 Ai аа ааа,аа а а„а„а а а„а n u„a а а„а„ааы аа а,й аа а,а, а,а, ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К ABTOPCKOMY СВИДЕТЕЛЬСТВУ (2 1) 3972606/24-24 (22) 04 ° 11. 85 (46) 23. 05. 88. Бюл. И 19 (71) Львовский политехнический институт им. Ленинского комсомола (72) И.В. Черкасский (53) 681.3(088 ° 8) (56) Авторское свидетельство СССР

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

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

N 1305684, кл. С 06 F 11/08, 17.04.86. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКОВ ПО МОДУЛЮ (57) Изобретение относится к вычислительной технике и предназначено для формирования остатков чисел по модулям F чисел Ферма, которые описываются выражением F< = 2 +

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

2, и блок 3 свертки, содержащий группу одноразрядных сумматоров, блок

Зсвертки содержитдополнительно вторую группу одноразрядных сумматоров с соответствующими связями. 2 ил.

1397918

Изобретение относится к вычислительной технике и предназначено для формирования остатков от п-разрядных чисел по г!оцулям чисел Ферма, которые оп!rс! !ва!Отс. rr В!>1ражениег!

Г = 2 +1

1

3 геок разоядов

0 -1

A(n) -- ? а; 2

35 (1) :Gòàòî : !псла по модугпв числа Ферма равен о.:татку от сумм!! ч . 40

Р. =- « 1;, а 2 (-1) >„, (2) гд 1 = n, с округлением до ближайшего больше. о !!еле го числа.

0 iо з па "..!!

1- — !

Л = a 2

- j+s г

»0 получают ! -1

R =C A (- )"

j -0

Taxrr r образом, получение остатка связано с суммированием 1 частей A .! разрядностью; числа Л(в), причем все нечетrrrre слагаемые Л; отрицательные, При обрзботке суммы (3) единица переполнения "-разрядной сетки слагаемых А одинакового знака эквивалент-! на единице младllr:l о разряда тех же (3) 50 с где ч = 2, при t = О, 1, 2, 3,... 1О

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

Ферма.

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

17, r; =- 32, v = 4).

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

3 свертки с входами 4 и выходами 5 остатка, 25

Блок 3 свертки содержит для четного 1 (фиг. 2а) группы одноразрядных сумматоров 6.1-6.4, 7.1-7.4, а для нечетного 1 (фиг. 2б) — группу однораэр!гдных c ç : 1HTop0r3 о ° 1-8 ° 4, 30

При!!цип 1аооты ус;ройсra;r следующий, Пусть з дано !испо Л(п) с колнчеслагаемых, но с противоположным знаком. Это обстоятельство позволяет синтезировать прямоугольную матрицу свертки беэ увеличения разрядной сетки сумматоров по мере накопления результата с диагональной цепью распространения переноса сумматоров.

В целях исключения операций вычитания необходимо преобразовать (3), причем знак единицы переполнения предыдущей ступени должен совпадать со знаком слагаемых по следующей ступени матрицы. Это возможно, если инвертировать результаты, получаем ге на выходах сумматоров всех ступеней. На входы ..Ум !аторов первой ступени следуе r подать слагаемые в такой комбина— ц%п ин!.ерсных и прямых кодов, чтобы получаега!й в результате свертки остаток не требовал коррекции. Для этого используются дополнения по модулю Г отрицательных слагаемых Л; и всех результатов, получаемых на выходах сумматоров каждой ступени

-Л = . +F °

) ) Ъ

F 1, -(А +A) =., 1 где Л обратный код GT A; в — поправка.

С учето.r иэложе!!нoro выражение (3) преобразуется в следующую форму

R = ...с (Л +8+ A, . Ь+ А )-у Aq)q> е

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

YcTpQHcTBG для формирования остатков по модулю работает следующим образом, Работу устройства рассмотрим на пр!в!ере формирования остатка от 32разрядного числа по модулю F< !

7. В этом случае исходное число разбивается на восемь групп по четыре разряда в каждой (фиг. 1), причем нечетные числа отрицательны. Блок 3 позволяет получить наименьший вычет и скомпенсировать пгг! четном количестве групп поправку. Для компенсации используется код, равный разности чисел Ферма и поправки. В частности для

F = 17 этот код равен 15, = IIII. В данном случае 1 = 8 четное и блок 3 свертки выбирается по схеме фиг. 2а.

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

< ру!(и > в»xcr ..

МатОРОВ СООтВС с .<), <

ЧЕННая СуММа r . = Н(He.. поразрядных су .. О1 Ог( г рупгпл 2 . << и< > c-< -r.ñ . <" свертки, на вы?;О!ге ко-.. ется нужнь(й <)c"< аток.! (I Ъ

В .;I о )<: С> ф<>; >;I;;.

Ф о р и у л а и э о б р т -- .. с

> устройс. (Го .">лл фс рь::); гат10 ков по мод li<) с );1<1:.к;)гесс - 1 — 1 . руппу одноразрядных сум.сс)то! Ов ( — v = 2

7 3, 15 и-разряднос:тв иола) и блок свертки у содержащ!Вй 88ð8 ") 1,)уппу однораэряд— ны!. суммато1..-,1, . ричем прямые Входы перво: о сл:< "ae:-саго и входы переноса одноразр?!днь<х сумматоров первои груп20

ilk I соединены соответственно с первой и третьей группами иэ ч-разрядов информационного входа устройства, прямые входы первого слагаемого одноразрядных сумматоров ч.-й группы (i — 1-2) соединены с (1+2)-й группой разрядов информационного входа устройства, выход переноса последнего одноразрядного сумматора к-й групгы (к = 1,..., 1-2) соединен с . р>в:(" входом первого одноразряд«ого ср(;

С ВХОДОМ ПЕРЕНОСа (Р+1 <-ГO ОДНО,>а--.(:ВДного сумматора послс.днс й, руп Еь(, выхо а ПЕРЕНОСа Р-ГО;.Д!«>Р<ЕЗРЯД;(Огс. СУММатара ПЕрВОй Гр. ПЭЬ(бЛона ГI. .Ерт!.И соединен с входоь(переноса (p+1)-го одноразрядного сук!атора первой груп40 пы блока свертки, Выходы суммы од!Ес>разрядных сумматоров первой группы блока свертки явллютсл Вы?.одом устройства, о тл 1: ч ающ е е с я тем, что, с велью расширения области применения за сче г pop! Iir;>nil

45 татков по модул!в чисел ьерыа, б.:Еа>с свертки при четном 1 сод ржит е)тс» ую гру!!п однораэрлдньсх суе(маторов, причем инверсные входы второго слагае. (ого одноразрядных с ум?:, ч оров па р( пi<ы ..Оед.<1.: ы . соо.".с ст!()<"

; -(зРлц,.?(! I<: и ГГУ;(Еэ. 11 (фоРм: (1«ОГО ВХОД<) 3, ><О.1< Ч .,, Г<Ы., 1,<1

: ) 1).!ы одноразрл;.. ?с <.) - >Ов

;)уппы соединены: " - -, - 1... ц,( ми второго слагаем: го с. - .. з.. рлдного сумматора к-й r ру(>гэ(с ° нен с инверсным входом пе,>< . (p (, го одноразрядного сумматора (к- 1 и группы, выход переноса последне! одноразрядного сумматора первой ггы блока сверчки соединен с выход устройства, выходы суммы одноразрядных сумматоров и выход переноса последнего одноразрядного сумматора по-следней группы: >:,и ::ь(сс.<)тветственно Гц11! нс :. т !(< 1 1 .<: .! р(: (.! 1II !<к<)да= рг а r, < ла "(<эм ) . >. )..н >с) а. p? .I;.(ых

:" " .(ВТС >О1, ПЕ: 1< I Г. VI:!т <- с!ХОДОМ !

I. Оe!Inс,! !арво. <> ОГ >;< p (11с. О су?!. ма горa I!ep8ok> i рус,пы олова с.вертки

1 ь(-. Одь! сумс .ь< Од(«. «а э с>лдных c V."ма ор В;1 выход переноса г!Ослед"=-.го од.;

;. >,)азрлд,!э го с,ммато, и, с. !" äíeÀ гpviiгеь(, р.! че т>1. м 1 .: )е,.(ш!е(ы со .

Ест.(<..ii>(<, с < не<а; <"..I!í. -!и Вхо !ами гlс D

Ва Г, Ci!.:. аа Л го О,;НС)Р;: 3Р.:Д; Л;. С,М-.(а..<:1: )1 вт;,;-ой I ру !1и:. j. с гх<"дс>ь! 1<арен > P-)С ГС> С., ";:;. ГС с ДI! Ра-(РЛД-;(ма- р.; rrI,;.<>I(r p<, rrrik бг!Ок ), (Ipò .;1, нр! )ем в бл к-. св ртки при

< .;НОМ Г:; Л(;,1=- Х(ГДЬ) В:) >ОГО СЛВ":)< 1!() C ОД),ОРаз (<>1, 1ЬЕЛ . VI 41 . . д >l(!! В кодо(< ло

Г ВЫ.<Од и ° p(носа р-го Ог,норзэрлд. )г0 сумматора втогой группы cocä» " !! с входом пе ре!!оса (р+1) — го однораэ,(г(но! о сумматора второй груп чь1, r<1!x <л переноса пс следне "о одноразрлд! "го сумматОРа Втс. Рой ГРУППЬ(СОЕД.И(ЕН С ВХОДОМ перс носа перво гс эд;-:ораз, дно го сумм .< ТОРа пс .D )ОЙ ГР у ппе i, Выл >li I сУммы (),.<(с>1)азрле>1(ых сумматоров второй гругс" пьi сов динены с:!HF pp ".нь;ми входами

ПЕРВ СГ О СЛаГВЕМОГ<;, СН) тГЕ ГСтВУЮЩИХ од!(а,)азрядных сумматоров первой группы.

1397918

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

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

Корректор И. Демчик

Редактор И. Николайчук

Подписное

Тирах 704

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

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

Заказ 3223

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