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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИ ХРЕСПУБЛИН 06 Р 11 0 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ ФОТАТКОВ ПО МОДУЛЮ(57) Изобретение относлительной технике и для формирования остатков чисел помодулям Р чисел ферма, которые описываются выражением Р = 2 +ч = 2 ,= О, 1, 2 Целью изобретения является расширение областиприменения за счет формирования остатков по модулю чисел ферма. Поста"вленная цель достигается тем, что вустройстве, содержащем одноразрядныесумматоры 1, объединенные в группы2, и блок 3 свертки, содержащийгруппу одноразрядных сумматоров, блокЗсвертки содержитдополнительно вторуюгруппу одноразрядных сумматоров с соответствующими связями. 2 ил. нический и ола льство СССР 11/08, 1982. ство СССР 11/08, 17.04. РИИРОВАНИЯ ОС сится к вычи предназначенИзобретение относится к вычислительной технике ц предназначено для формиронация остатков от и-разрядных чисел по )оцулям чисел Ферма, которые опцс ВаОтс. я В 1 ражециеь Г =2 +1(1) 3 статок цкла по модулю числа Ферма ранец о,.татку от суки 40Р=;, а 2 (-1, (2) гд. 1 = и, с округлением до ближайшего больше)о елого числа.О о заВцпо.)учают-1К =( ", 1 (-)0Таки) образом, получение остатка связано с суммированием 1 частей Л) разрядностью числа Л(и), причем нсе нечетные с;агаемь)е Л; отрицательные, Прц обрзботке суммы (3) единица переполиецця "-разрядной сетки слага" емых Аодиакон о го знака экн гн але ц тца единице младего разряда тех же(3) 50 сгде ч = 2 , прц е = О, 1, , 3,..Целью изобретения является расширение обл;)стп применения за счет формирования остатков по модулям чиселФерма.11 а фи, 1 представ.еца схема устройства для формирования остатковпо модулю; ца фиг. 2 - схема блокасвертки (схемы даны для случая Р17, и =- 32, ч = 4).Устройство для формирования остатков по модулю (фцг. 1) содержитодноразрядные сум)аторы 1.1-1,4,объединенные в группы 2.1-2,7 н блок3 свертки с Входамиц выходац 5остатка, 25Блок 3 свертки содержит для четного 1 (Фиг. 2 а) группы одноразрядныхсумматоров б.1-6.4, 7.1-7.4, а длянечетного 1 (фцг, 2 б) - группу однораэр)дцых су)"ато ров Я. 1-8. ", 3 ОПри и цц 1 а.о ты ус; р ой с тл а следующий,Пусть з дано число А,и) с коц;иеслагаемых, но с противоположным знаком. Это обстоятельство позволяетсинтезировать прямоугольную матрицу свертки беэ увеличения разрядной сетки сумматоров по мере накопления результата с диагональной цепью распространения переноса сумматоров.В целях исключения операций вычитаия необходимо преобразовать (3), причем знак единицы переполнения предыдущей ступени должен совпадать со знаком слагаемых по следующей ступени матрицы. Это возможно, если инвертировать результаты, получаемые на выходах сумматоров всех ступеней, На входы .ум еторов первой ступени следуе г подать слагаемые н такой комбицац%н инверсных и прямых кодов, чтобы получаемый н результате свертки остаток не требовал коррекции. Для этого используются дополнения по модулю Г отрицательных слагаемых Л и всех результатов, получаемых на выходах сумматоров каждой ступени) ) Ъ 1=1,-(А +Л) =2,гд Л, - обратный код от А,поправка. С учетоиэложеьцого выражение(3) преобразуется в следующую форму К =(Ло +8+ А, + + Аа) )-э+)еГ 1 о,цо инвертировать А так, что компец -.ируются н се о трица тельные и положитгльцые значенияУстройство для формирования остатков по модулю работает следующим образом,Работу устройства рассмотрим на прнере формирования остатка от 32- разрядного числа по модулю Р 27. В этом случае исходное число разбивается на восемь групп по четыре разряда н каждой (фиг. 1), причем нечетные числа отрицательны. Блок 3 позволяет получить цаимецьший нычет и скомпенсировать пре четном количестве групп поправку. Для компенсации используется код, равный разности чисел Ферма и поправки. В частности для Г = 17 этот код равен 15, = 1111. В данном случае 1 = 8 четное и блок 3 свертки выбирается по схеме фиг, 2 а. Группы разрядов исходного числа поступают ца входы одноразрядных сумГРУЕп, ,. "- ВЬХС МатОРОЕ) СООтВС гченная сумма ".: н ц,. оразрядных су о 1 ог групгеь 1 2. 7 и от"уг:;:.1 ц свертки, на выхопс ко; ется ужный Осз аток,В." .;1): с 1; ). Формула из обре т)содержащЕй перв ) руппу одноразрядных сумматор; . рцчем прямые Входы перво: о се.;Гае.сго и входы переноса одноразрлдньх сумматоров первои груп 20 1 гы соединены соответственно с первой и третьей группами иэ ч-разрядов информационного входа устройства, прямые входы первого слагаемого одноразрядных сумматоров е-й группы (е - 1-2) соединены с (1+2)-й группой разрядов информационного входа устройства, выход переноса последнего одноразрядного сумматора к-й групгы (к = 1 1-2) соединен с гггл. " входом первого одноразрядого ср;,) - тора (к+1)-й группы, выход п рено : р-го одноразрядного су и: ора и-,дней группы (р = 1 , - 1) сос 1 сц с входом переноса (р+1-го одно,)а лдного сумматора после Евй, рупчь гыхо д переноса р-го сдр)езрядцог с"л)- матора первой гр. ппь блока герт.и соединен с входом переноса (р+1)-гс) одноразрядного сукатора первой груп 40 пы блока свертки, Выходы с Е)емы оди- разрядных сумматоров первой группы блока свертки явллются Выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения эа сче г форин)овация ос"45 татков по модулв чисел ерьа, блок свертки прц четном 1 сод ржит Вто ую групп одцораэрлдньх сумматоров, причем инверсные входы второго слагаеого одноразрядных суеь 1 торов перцы Ос, 1. ы . соо -,с ст),)УППЫ СОЕДИНЕНЫ :- ь -М 1. П, мц второго слагаем;го с. с:ств.,юВЕих одноразрядных су.;) 1)- группы, выход перенос,; -, , рлдного сумматора к-й груг)с цен с инверсным входом пе (р, го одноразрядного сумматор (к.й группы, выход переноса последнег. одноразрядного сум)атора первой ггы блока свертки соединен с выход, устроцства, выходы суммы одноразрядных сумматоров и выход переноса последнего одноразрядного сумматора по.- следней группы : ц ., сс ответственно прц ит: 11;ра ., ) х)ЕЕарва г сла ае.",а ; н а рл;,ь)хТа О)., ПЕ;. Ьй 1 В, Т.ВХОДОМПс цо.а арвоогц: р; р)11 с)о су) ма гара )ервой )ру,пь блока зверткиЭьг: Од Сумгь од раэ)лдвых сумаор в 1 выход пе рсцс са г)ослед": го сд", ц,азрлдцз го с,мматог;. и: с).едней гръпгь,р четсл 1 .:)е,.)цеы со:Емарг:1; рой ГрэгЕее бло; ) ,рт;1, цр): ем в бл ке св ртки прцЬц)М П Л ьХ: дЬ В:) )ОГО СЛВ":; О с од)ора:) 51,чьх уьл:) горВ в СРОй ГРУгГь Е,1 1 " ВхоДО ло- ГЧЕ.Е)Е СДИНИЦ 1 )ТРО Са ) ВЫ.ОД и рс.цаса р-го однорззрлд.)го суматора втогой группы саед " ц с входом переноса (р+1) - го однораз ,)ноо сумматора второй груп ы, вь:,е перено- СЗ ПССЛСДНЕГО ОДНОРаЗРЛД)"ГО СУММатора вт)рой групгг) соед;нец с входом перс носа первого одно ра з, дно го суммг тора пс.р ОЙ Гуппе , Вьх)дь 1 суммы одртрлдых су)сатаров второй груг ГЦ 1 СОС,ЕИНЕНЫ С:НГЕРг.нЬМИ ВХОДаМИ первсго слагаемогооотге гствующих одц. разрядных сумматоров первой груп1397918 ль А. КлюевКравчук остав ехред орректор М. Демчи едактор И. Николайчу Тирах 704 Под ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, 1-35, Рауаская наб., д, 4/5