Устройство для вычисления остатка по модулю от двоичного числа

)5 Н 03 М 7/18 111 ПИСАНИЕ ИЗОБРЕТЕНИЯ СКОМУ СВИ ЕЛЬСТ К числительной технике и зовано вспециализиро ных устройствах, функц Цель изобретения - с турник затрат. Постав гается сокращение коммутатора и перера зей между остальными во содержит входно свертки 2, сумматор и умножения на констан мутатор 5, регистры 6 входов 8.1-8.4, выход 9 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(72) Н.И.Червяков и А.А,Оленев (56) Авторское свидетельство СССР Я 1156058, кл. Н 03 М 7/18, 1984,Авторское свидетельство СССР. В 1417192, кл. Н 03 М 7/18, 1987. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ДВОИЧНОГО ЧИСЛА(57) Устройство для вычисления остатка по модулю от двоичного числа относится к выможет быть испольванных вычислительионирующих в СОК, окращение аппараленная цель достим блока свертки, спределением свяблоками, Устройстй регистр 1, блок о модулю 3, блок 4 ту по модулю, коми 7, группу тактовых ,1 ил.Изобретение относится к вычислительной технике и может быть использовано для сопряжения вычислительных устройств, функционирующих в системе остаточных классов.Известно устройство для вычисления остатка по модулю от двоичного числа, содержащее первый и второй регистры. входной регистр, первый и второй коммутаторы, блок умножения на константу по модулю и сумматор по модулю,Недостатком известного устройства являются большие аппаратурные затраты.Наиболее близким к изобретению является устройство для вычисления остатка по модулю от двоичного числа содержащее входной регистр, первый и второй блоки свертки по модулю, первый и второй регистры, первый и второй коммутаторы, блок умножения на константу по модулю и сумматор по модулю, причем первый и второй блок и свертки по модулю, причем выходы разрядов с (1-1)-го по (-гп)-й входного регистра подключены к входу первого блока свертки по мо улю(пп, где и -Кразрядность модуля, = -- ,(К - разрядП 1ность двоичного числа), выход которого соединен с вторым информационным входом первого коммутатора, выходы разрядов с(1 - гл)-го по (1 - 2 п)-й входного регистра подключены к входу блока свертки по модулю, выход которого подключен к входу второго слагаемого сумматора по модулю, выход первого коммутатора соединен с входом блока умножения на константу по модулю, выход которого соединен с входом первого слагаемого сумматора по модулю, выход которого является выходом устройства и соединен с информационными входами первого и второго регистра, выходы которых соединены соответственно с первым и вторым информационными входами второго коммутатора, выход которого соединен с первым информационным входом первого коммутатора, вход разрешения сдвига входного регистра, управляющие входы первого и второго коммутаторов и входы разрешения приема первого и второго регистров соединены соответственно с тактовыми. входами группы устройства.Недостатком известного устройства являются большие аппаратурные затраты.Целью изобретения является сокращение аппаратурных затрат.Поставленная цель достигается тем, что из известного устройства, содержащего входной регистр, два блока свертки, два коммутатора, блок умножения на константу, сумматор по модулю, два регистра, имеется возможность изымать один блок свертки помодулю и один коммутатор,Тогда устройство будет содержать входной регистр, блок свертки, сумматор по мо 5 дулю, блок умножения на константу, дварегистра и коммутатор, причем выходывходного регистра с (п)-го по 1 о-гп)-й подключены к блоку сверткивыходы блокасвертки подключены к первым входам сум 10 матора по модулю, вторыми входами сумматора по модулю является выходкоммутатора, выход сумматора по модулюявляется входом блока умножения по модулю, его выход является входом для регист 15 ров хранения промежуточных результатов,их выходы являются входами коммутатора,В основу работы устройства положеноследующее,Двоичное К-разрядное число Х может20 быть представлено в видеХ =а.12 +а 12 + ао 2Используя вычисления по схеме Горне ра преобразуем выражение (1) к виду, удобному для нахождения остатка х от числа Х по модулю Рх= Хр=акр+а 1р х30 х 2 р+аОр 2)Пусть выбранный модуль Р имеет раз-.рядность и, Разобъем двоичное представление числа Х на группы по п двоичных 35 разрядов, причем щп. С учетом разбиенияпреобразует выражение (2) к видух=А 1 р 2р+)А 1 рр, (3)40 . А = а 2 + .+ аь-+ 2+ аа-,П 3-1где =)К/гп,=, 1Обозначим В = Ариф= 2"+р, приведя (3) к виду:45х = . В 3 р+ Вь 1 р ф р++ В 1 р (4)При этом,д является константой, вычисленной заранее,50 Таким образом, выражение(4) позволяет реализовать получение остатка от исходного числа по модулю Р,На чертеже приведена функциональнаясхема устройства для вычисления остатка55 по модулю от двоичного числа,Устройство для вычисления остатка помодулю содержит входной регистр 1, блок, свертки 2, сумматор по модулю 3, блок умножения на константу по модулю 4. регист(1 п)-й управляющий вход, при подаче сигнал на который содержимое регистра 1сдвигается на т разрядов влево.Блок 2 свертки является функциональноизвестным элементом, Выходы входного регистра 1 с (Ь)-го по (1 п-т)-й подключены к 10блоку свертки 2,Сумматор по модулю 3 известный функциональный элемент, К его входам подклю:чены выходы блока свертки 2 и коммутатора5. Выходы сумматора по модулю 3 подключены к известному элементу блока 4 умножения на константу по модулю, Выход блока4 подключен к известным функциональноэлементам регистрам 6 и 7, которые в своюочередь подключены к коммутатору 5. Запись в регистры б и 7 осуществляется потактовым импульсам 8.3-8.4, Работой коммутатора управляет импульс 8,2. Выходсумматора 3 является и выходом устройства, 25Устройство работает следующим образом,В исходном состоянии в регистре 1 находится код преобразуемого числа Х, Регистры 6 и 7 обнулены, 30На первом такте число Аь определяемоегп старшими разрядами преобразуемогочисла Х, преобразуются блоком 2 свертки востаток В по модулю Р;На сумматоре 3 по модулю происходит 35сложение В с нулем, так как коммутатор 5подключен регистры 6 или 7, которые обнуленьь В блоке умножения 4 на константу помодулю происходит умножение на константур по модулю Р, аоТаким образом, по окончании переходных процессов на выходе блока умножения4 имеем1 В /31 р.Результат умножения записывается в 45 момент поступления импульса по входу 8,3 в регистр 6.На втором такте преобразования в момент поступления импульса ко входу 8.1 содержимое регистра 1 сдвигается на т 50 разрядов влево. Коммутатор 5 подключен к входу сумматора 3 регистр б, Содержимое регистра 6 через коммутатор 5 поступает на вторые входы сумматора по модулю 3, на первые входы которого поступает следую щий остаток Вн и сумма поступает на вход блока 4 умножения, По окончании переходных процессов и. еем результат который в момент поступления импульса ко входу 8,4 записывается в регистр 7,Далее процесс преобразования происходит аналогично.В последнем (1-1)-ом такте окончательный результат снимается с выхода сумматора 3 на выход устройства 9.В предлагаемом устройстве отсутствуют два блока; блок свертки и коммутатор, что обеспечивает следующую экономию. Например, если коммутатор построен на схе- мах И, то происходит сокращение на 2 гл двухвходовых схем И, Если блок свертки имеет дешифратор и схемы ИЛИ и дешифратор построен как пирамидальн ы й, то н е обходи ма 4(2 - 1) двух входовых элементов И, а также затраты на элементы ИЛИ, которые также будут расти с ростом модуля. Выигрыш в оборудовании очевиден, при этом в быстродействии предлагаемое устройство проигрывает прототипу всего один, такт, Преимущество предлагаемого устройства достигается изменением связи между блоком свертки и сумматором по модулю и блоком умножения на константу по модулю. Формула изобретения Устройство для вычисления остатка по модулю от двоичного числа, содержащее сумматор по модулю, блок умножения на константу по модулю, входной регистр, выходы с (Ъ)-го по (1 п=т)-й которого соединены с входами блока свертки по модулю (где п и, 1 = )К/п(, К - разрядность двоичного числа, и - разрядность модуля), информационные выходы первого и второго регистров подключены к информационным входам коммутатора, вход разрешения сдвига входного регистра, управляющий вход коммутатора, вход разрешения записи первого и второго регистров соединены с тактовыми входами группы устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, в нем выходы блока свертки подключены к первой группе входов сумматора по модулю, вторая группа входов которого соединена с выходами коммутатора, выход сумматора по модулю подключен к входу блока умножения на константу по модулю, выход которого подключен к информационным входам первого и второго регистров, выход сумматора по модулю является выходом устройства,