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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 801444 504 С 06 Р 11/О ОПИСАНИЕ ИЗОБРЕТЕНК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ехнич го комсомо тельство СССР Г 11/00, 1985 57Фы 7 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ, (71) Львовский поли институт им.Ленинск(54) УСТРОЙСТВО ДЛЯ ФОРИИРОВАНИЯОСТАТКОВ ПО ИОПУЛН 3(57) Изобретение относится к вычислительной технике и может быть ис" пользовано для формирования остатка числа по модулю 13 беэ выполнения операции деления, 11 ель изобретения расширение области применения эа сч увеличиния числа модулей. Устройст содержит сумматоры 1.1-1,6, объединенные в группы 2.1-2.5, элементы 2 И-ИЛИ 3, 1-3,4, дополнительные сумм торы 4,1-4.8, блок 5 свертки, 1 з.п ф-лы, 2 ил., 2 табл,(2) 40 Изобретение относится к вьтчислительной технике и может быть использовано для формирования остатка числапо модулю 13 без выполнения операцииделения,Цель изобретения - расширение области применения устройства за счетувеличения числа модулей.На фиг, 1 изображена функциональная схема предлагаемого устройства; на фиг. 2 - схема блока свертки,Устройство содержит сумматоры ,.1, 1-1,6,объединенные в группы 2.12,5, элементы 2 И-ИЛИ 3,1"3,4, дополнительньте сумматоры,4. 1-4,8 и блок 5свертки, Блок 5 свертки содержит вхо-.ды 6 и выходы 7, сумматоры 81-8,4,элемент И-НЕ 9, элемент НЕ 10, элементы 2 И-ИЛИ 11 и элементы И 12,1-2012,4,Устройство работает следующимобразом.Пусть А(п) - исходное число, за"данное в следующей двоичной системе 25счисления: А = А,) + А 2+ А 2 +ф, (1) Р, Е,а Фгде А А и А - группа последовательных цифр содинаковым количеством разрядов.Остаток от деления числа А(п) на модуль ттт равен35(А(п = (А, + Я,А, + где Я; = (2 ) ,;Я = 1,2Коэффициенты Я; определяют сложность вычисления остатков по выраже". нию (2), Наименьшее число вычислений при Я, = Я = = 1 имеет место для модулей чисел Иерсенна и Ферма. В обоих этих случаях количество разрядов в группах 1 равно степени р или ч двойки. 50Для отыскания минимальных значений Я. составим табл, 1 положительных и1отрицательных остатков от деления последовательного ряда степени двойки на модуль 13. 55 Как видтто из табл, 1, значения вычетов периодичны, причем для Я = + 1 это период равен с 1:.6. Отсюда выражение для отыскания вычета г можнозаписать как г =(Ао А,+А -А 3+ ) 131 т 1=6. Выражение (3) позволяет свернуть многоразрядные числа до шестиразряд-, ного вычета по модулю 13, Для отыскания остатка г (наименьшего вычета) необходима дополнительная сверткаIФ так как вычет г имеет семь разрядов, а вычет г - четыре разряда для модуля гп = 13 - 1101, Можно разбить г на дне группы чисел, содержащие, например, четыре и два разряда. КоэфФ фициент при 2 по табл, 1 равен 3, поэтому где С и С- четыре младших и тристарших разряда г 1.При использовании выражения (4) возможно получение отрицательного остатка, в связи с чем следует произвести переход к положительному остатку, Так как где г д - дополнение г до модуля ш, то где г Ь - обратный код значения остатка г, а с - ттт (г + г, )г + го(тп,7) Для модуля 13 д = 2 о =. 0010. Таким образом, получение остатка связано с суммированием 1 частей А . разрядностью т 1 =6 числа А(п), причем все нечетные слагаемые А отрица-. тельные, При обработке сумм, определяемых выражением (3), единица переполнения тт-. разрядной сетки слагаемых А одинакового знака эквивалентна единице младшего разряда тех же слагаемых, но с противоположным знаком, Это обстоятельство позволяет синтезировать прямоугольную матрицу без увеличения разрядной сетки сумматоров по мере накопления результата с диагональной цепью распространения сигнала переноса сумматоров. В целях+ 100110 000011 1110 0010 001011 ооо 101001001 Ц 0 0011 з 14447 исключения операции вычитания используется дополнение по модулю чисел Ферма ( д= 2- 10) отрицательных слагаемых А и всех результатов по 11б лучаемых на выходах сумматоров каждой группы, Компенсация дпроизводится в сумматорах 4 путем добавления двойки (в частности, в сумматорах 4.1 и 4.5),1 ОВ элементах 2 И-ИЛИ 3 и сумматорах4 производится переход от семиразрядного вычета гк 4-разрядному. Переходная схема синтезирована по табл. 2 истинности, в которой выход 15 сумматора 1.5 обозначен В , выход сумматора 1,6 обозначен Р , выход переноса сумматора 1.6 обозначен Р а выходы элементов 3. 1-3,4 обозначены соответственно С -С ,. 20.Здесь Со-С з - это результат умно. жения В, В, и В на три, По табл, 2 составим уравнения и минимизируем их; Сумматоры 4 служат для получениянаименьшего вычета. В них не производится компенсация поправки, равная.д"= 2 = 10. Прибавление двойки "распределено на сумматоры 4.1 и 4.5,путем прибавления в каждом из этихсумматоров по единице, При возник. новении сигнала переноса в сумматоре. 4 О4.4 (пятого разряда) происходит суммирование этого сигнала, умноженногона три, с четырьмя разрядами сумматоров 4.1-4,4 в сумматорах 4.5-4.8. ,.При этом на выходах сумматоров 4.5- . 454,8 и соответственно на входах 6 блока;4-разрядныйвычет,В блоке 5 свертки вычет гпреоб- .разуется в наименьший положительныйвычет. Для этого в сумматорах 8 вычет,г.складывается с д= 2= 0010 .Если при этом возникает перенос(что соответствует случаю, когда выполняется неравенство ш 6 г . 15),.55то наименьший остаток снимается свыходов сумматоров 8 через элемент2 И-ИЛИ 11. Если сйгнала переноса насумматоре 8.4 не возникает, остаток подается на выход схемы, минуя сумма" торы 8, с выходов сумматоров 4,5-4,8 из-за наличия сигнала ч 1" на выходе инвертора. Исключение составляет случай, когда г .= т = 13, = 1101 Для получения г0 служат элемент И-НЕ 9 и элементы И 12, При г.= 1101 на входе элемента И-НЕ 9 установятся все "1", а на выходе образуетея "0". Этот сигнал закрывает все элементы И 12 и на выходах У образуется код 0000 независимо от состояния сумматоров 8, Во всех остальных случаях элементы И-НЕ 9 и И 12 не прес.пятствуют прохождению данных на выходы 6. Кроме того, такое подключение элементов И-НЕ 9 и И 12 запрещает возникновение возбужденияв сумматорах 8 при г = ш.П р и м е р, А=1100010001101101001 0000111110111, При этом А=11011 -А,=000111; А=010010 -А=011011, А,=000100 А =115 1444774 6 Проверка, Деление промежуточно" устройства, прямые входы первого го результата т на модуль 13: слагаемого сумматоров (1-й групп+ 0010 поправка за счет инвертирования - А11101101 0001 На Выходах сумматоров,4 5-4,8 образуется код 1110, При этом,на выходе элемента И-НЕ 9 устанавливается "1", которая разрешает прохождение кода через элементы И 12. При сложении в сумматорах 8 чисел 1 110+0010 образуется переполнение, т.е, единицаи ;,приплюсовывается в сумматоре 8,1 а на ввщод 7 результат поступаетчерез элемент 2 И-ИЛИ 11 с выходов сумматоров 8, а не с выходов сумма. торов 4.5-4,8.Таким образом, Функциональныевозможности предлагаемого устройства (по сравнению с устройством-прототипом) расширены за счет использования его матричной структуры с диагональнрй Цепью распространения сигнала .переноса для формирования остатков по модулю чисел Ферма.и по модулю 13. при добавлении переходной схемы свертки (логические элементы и сумматоры) и введения блока свертки,Ф о р м у л а и з о б р,е т е н и я 1. Устройство для Ьормирования остатков йо модулю, содержащее 1 -1 группу сумматоров (1 = и/ц, и -раз+ рядность числа, 1 - число .сумматоров в группе) и блок свертки, выходы которого являются выходами устройства, прямые входы первого слагаемого инверсные входы второго слагаемого и входы переноса сумматоров первой группы являются первой, второй и третье группами информационного входов и( = 2; 3, , 1 - 2) являются(1+2) - ,й группой информационных входов устройства, выходы сумм сумматоров1 с-й Ос = 1, 2, , 1 - 2) группысоединены с инверсными входами вто"рого слагаемого одноименных сумматоров Ь+1)-й группы,: выход переноса -го (д=1, 2,;, ц) сумматора не-й группы соединен с инверсным входом переноса И+1)-госумматора Ь + 1)-й группы, выходпереноса последнего сумматора Е-йгруппы соедйнен с прямым входомпервого сумматора В+1)-й группы,выход переноса каждого сумматорапоследней группы,;кромепоследнего20 сумматора, соединен с входом переноса последующего сумматора даннойгруппы, о т л и ч а ю .щ е е с ятем; что, с целью расширения областиприменения за счет увеличения чис 25 ла.модулей, число сумматоров в группе равно 6 и в него введены элементы2 И-ИЛИ и.дополнительные сумматоры,прямые входы первых слагаемых первых четырех дополнительных сумматоров ф30 подключены к выходам сумм соответству- .Фющих сумматоров последней группы,. первый инверсный вход первого ипервый прямой вход второго элементовИ первого элемента 2 И-ИЛИ, прямыеЗБ первые входы. элементов И второго элемента 2 И-ИЛИ, инверсные первые входыэлементов И третьего элемента 2 И-ИЛИи первый инверсный вход первого ипервый прямой вход второго элементов40 И четвертого элемента 2 И-ИЛИ объединены и подключены к выходу суммы .пятого сумматора последней группы,. вторые прямые входы первых элементовИ первого и второго элементов 2 И-ИЛИ,45,второй инверсный вход второго элемента И второго элемента 2 И-ИЛИ ивторые прямые входы вторых элементовИ третьего и четвертого элементов2 И-ИЛИ объединены и подключены к50 выходу суммы последнего сумматорапоследней группы, третий прямой входпервого ивторой инверсный вход второго элемента И первого элемента.2 И-ИЛИ, третий инверсный вход пер 55 вого элемента И второго элемента 2 ИИЛИ и последние прямые входы первыхэлементов И третьего и четвертогоэлементов 2 И-.ИЛИ объединены и подключены к выходу переноса последнего г г.Та блица 0 0 0 0 0 0 0 0 О 0 0 0 0 О 1 1 0 0 0 0 0 о 0 0 О О 014447 сумматора .последней группы, выходы элементов 2 И-ИЛИ соединены с прямыми входами вторых слагаемых соответствующих первых четырех дополнительных сумматоров, выходы сумм которых сое 5динены с прямыми входами первых слагаемых соответствующих вторых четырех дополнительных сумматоров, выходы сумм которых соединены с соответ ствующими входами блока свертки, выходы переноса дополнительных сумматоров, кроме четвертого, соединены с .входами переноса последующих сумматоров, выход переноса четвертого до полнительного сумматора подключен к прямым входам второго слагаемого пятого и шестого дополнительных сумматоров, прямые входы третьих слагаемых первого и пятого дополнительных 20 сумматоров подключены к источнику сигнала логической единицы,2, Устройство по п. 1, о т л и ч аю щ е е с я тем, что блок свертки содержит сумматоры, элементы 2 И-ИЛИ, элементы Ии элемент И-НК, выход которого соединен с первыми входамипервого-четвертого элементов И,выходы сумм сумматоров подключены кпервым входам первых элемейтов И соответствующих элементов 2 И-ИЛИ, выходпереноса каждого из первых трех сумматоров соединен с входом переносаследующего сумматора, выход переносачетвертого сумматора соединен с вторыми входами первых элементов И элементов 2 И-ИЛИ,входом переноса сумматора и входом элемента НЕ, выход которого соединен с первыми входамивторых элементов И элементов 2 И-ИЛИ,входы первого слагаемого сумматоров,подключены к источнику кода 0010,первый прямой вход, второй инверсньп,третий и четвертый прямые входы элемента И-НЕ объединены соответственнос входом второго слагаемого одноименного сумматора и вторым входом второго элемента И одноименного элемента2 И-ИЛИ и является соответствующимвходом блока свертки, выходы элементов Иявляются соответствующими выходами блока свертки,1444774 Составитель 0Техред Л.Олийн ох орректор Л. Пата Редактор вин аказ 6482/48 Подпис та СССР и роизводственно-полиграфическое предприятие, .г. Ужгород, ул. Проектная, 4 Тираж 704ВНИИПИ Государственнопо делам изобретений13035, Москва, Ж, Ра комии откская .