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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 1191 (11 06 Г 11 ЕГЙИИ ОПИСАНИЕ ИЗОБРЕТЕ а%ф ффф+фв е"43 ГОСУДАРСТ 8 ЕННЫЙ НОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫ А ВТОРСКОМУ СВИДЕТЕЛЬСТ(46) 23.05.88. Бюл. В 19 (.71) Львовский политехнический институт им. Ленинского комсомола (72) Н.В. Черкасский(56) Авторское свидетельство СССР У 1084798, кл. С 06 Г 11/08, 1982.Авторское свидетельство СССР В 1305685, кл. С 06 Г 11/08, 17.04.86.(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКОВ ПО МОДУЛЮ(57) Изобретение относится к вычислительной технике и предназначено д ля формирования остатков чисел помодулям Г чисел Ферма, которые опич сываются выражением Г = 2 + 1У Ч = 2 , с = О, 1, 2 Целью изобретения является расширение области применения за счет формирования остатков по модулю чисел ферма. Поставленная цель достигается тем, что в устройстве, содержацем одноразрядные сумматоры 1, объединенные в группы 2, и блок 3 свертки, содержащий группу одноразрядных сумматоров, блок 3 свертки содержит дополнительно вторую группу одноразрядных сумматоров с соответствунзцими связями, 2 илее,3 получают 1 эобретецце относится к вычислительной технике ц предназначено для формирования остатков от п-разрядных чисел па йодулю чисел Ферма, которь,е описылыотся выражением Г =2+1ЭСгде ч = 2 , прц= О, 1, 2, 3, 4Целью цзобретенця является расширение области применения за счет формировацця остатков по модулю чисел Ферма,На фцг. 1 представлена схема устроцства для Формирования остатков по модулю; на фцг. 2 - схема блока свертки (схемы даны для случая Гэ17, я=32,ч=4).Устройство для формирования остатков по модулю (фиг. 1) содержит одноразрядные сумматоры 1.1-1.4, объедицеццыо в группы 2.1-2,7, и блок 3 свертки с входами 4 ц выходами 5.Блок 3 свертки содержит для четного 1 (фцг, 2 а) группу одноразрядных сммсторон 6,1-6,4, а для нечетного 1 (Фцг, 2 б) - грушы одноразрядных сусл,; торов 7. 1-7, 4 и 8, 1-8. 4.11 ргцццц работы устройства следующий.1 усть задано число А (и) с колий-таток числа по модулю чисел Ферм; равен остатку от суммыЯ-К -1 , а а,2 (-1) ), (2)5.де 1 = г/ с округлением до ближайшего боль;," го целого числа.Обт;цацв 1-1Й А (-1)(3) .Таким обозом, получение остатка сюзязацо с суммированием 1 частей А разряд;ыстью ч числа А (п), причем псе нечетые слагаемые А отрица 3тельцы. 11 рц отработке суммы (3) единц 1 а це ре п,хшснця ч-разрядной сетки слагаемых А одинакового знака эквивалентна едц.еще младшего разряда тех же слагаемых, но с противоположнья эц;,ком. Зто обстоятельство 5 10 15 20 25 40 45 50 15 позволяет синтезировать прямоугольную матрицу свертки беэ увеличения разрядной сетки сумматоров по мере накопления результата с горизонтальной цепью распространения переноса сумматоров.В целях исключения всех операций вычитания необходимо преобразовать (3), причем знак единицы переполнения предыдущей ступени должен совпадать со знаком слагаемых последующей ступени матрицы. Это возможно, если инвЕртировать результаты, получаемые на выходах сумматоров всех ступеней. На входы сумматоров первой ступени следует подать слагаемые в такой комбинации инверсных и прямых кодов, чтобы получаемый в результате свертки остаток не требовал коррекции. Для этого используются дополнения по модулю Г отрицательных слагаемых А3 и всех результатов, получаемых на выходах сумматоров каждой ступени:-А е А +е ю В Р - (А+А) 2, (4)где А - обратный код от А3 Ф3 - поправка.С учетом изложенного выражениеАо А ) + А 2+ ВЭгФЗдесь горизонтальные линии означают инверсию слагаемых или сумм, заключенных в скобках. Можно инвертировать слагаемые А; так, что взаимно компенсируются все отрицательные и положительные значения 3Устройство для формирования остатков по модулю работает следующим образом.Работу устройства рассмотрим на примере формирования остатка от "32"- разрядного числа по модулю Р 17, В этом случае исходное число разбивается на восемь групп по четыре разряда в каждой. Разбивка числа А(п) па группы АА. показана на фиг.1, причем нечетные числа отрицательны. Блок 3 позволяет получить наименьший вычет. В данном случае 1 щ 8 - четное, и блок 3 свертки выбирается по схеме фиг. 2 а.Группы разрядов исходного числа поступают на входы одноразрядных3 13979 сумматоров соответствующих групп, полученная сумма и перенос с выхо, ов одноразрядных сумматоров последней группы 2.7 поступают на вход блока 3 свертки, на выходе которого формиру 5 ется нужный остаток.Формула изобретенияУстройство для формирования остатков по модулю, содержащее 1-1 группу одноразрядных сумматоров (1ГиЧгде ч = 2 , с = О, 1, 2, ивразрядность числа) н блок свертки, содержащий группу одноразрядных сум 15 маторов, причем прямые входы первого слагаемого одноразрядных сумматоров д-й группы соединены с (д+1)-й группы из ч разрядов информационного входа устройства ( = 1, , 1-1), выход20 переноса последнего одноразрядного сумматора к-й группы соединен с входом переноса первого одноразрядного сумматора (к+1)-й группы (к= 1,1-2), выход переноса р-го одноразрядного сумматора д-й группы соединен с входом переноса (р+1)-го одноразрядного сумматора д-й группы р =ч), выходы одноразрядных сумматоров первой группы блока свертки являют 30 ся выходом устройства, выход переноса р-го одноразрядного сумматора первой группы блока свертки соединен с входом переноса (р+1)-го одноразрядного сумматора первой группы блока сверт ки, о т л и ч а ю,щ е е с я тем, что, с целью расширения области применения за счет формирования остатков по модулю чисел Ферма, блок свертки при 1-нечетном содержит вторую40 группу одноразрядных сумматоровпричем инверсные входы второго слагаемого одноразрядных сумматоров 194первой группы соединены с соответстующими разрядами второй группы информационного входа устройства, вьходы суммы одноразрядных сумматоров к-й группы соединены с инверсными входами второго слагаемого соответствуницих одноразрядных сумматоров (к+1)-й группы, выходы суммы одноразрядных сумматоров и выход последнего одноразрядного сумматора последней группы при 1-четном соединены соответственно с инверсными входами первого слагаемого одноразрядных сумматоров первой группы и с входом переноса первого одноразрядного сумматора первой группы блока свертки, выход переноса последнего одноразрядного сумматора первой группы которого соединен с выходом устройства, выходы суммы одноразрядных сумматоров и выход последнего одноразрядного сумматора последней группы при 1- нечетном соединены соответственно с инверсными входами первого слагаемого одноразрядных сумматоров второй группы и с входом переноса первого одноразрядного сумматора второй группы блока свертки, выход переноса последнего сумматора первой группы которого соединен с выходом устройства, причем в блоке свертки при 1- нече гном выход череноса р-го одноразрядного сумматора второй группы соединен с входом (р+1)-го одноразрядного сумматора второй группы, выход последнего одноразрядного сумматора которой соединен с входом первого одноразрядного сумматора первой группы, выходы одноразрядных сумматоров второй группы соединены с инверсными входами первого слагаемого соответствующих одноразрядных сумматоров первой группы.1397919 Составитель Л. КлюТекред А.Кравчук Корректор, М, Демч дн кр 11, Николайчук 322 3 писное роизло;,стнегп в п и рафическое предприятие, г. Ужгород, ул. Проектная, 4 Тираж 7 В 11 И 1 ПИ Государственц по цлам изобретен 113035, Москва, Ж, Рго ком йиот ушская ета СССРьлийаб д, 4/5