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

ОЮЗ СОВЕТСКИХ ОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 191 (11))4 Н 0 ГОСУДАРСТВЕНН ПО ДЕЛАМ ИЗОБ КОМИТЕТ СССР ЕНИЙ И ОТКРЫТ(56) Авторское свидетельство СССР У 1001079, кл. Н 03 М 7/18, 1981.Авторское свидетельство СССР 9 1156058, кл. Н 03 М 7/18, 1984.(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ОСТАТКА ПО МОДУЛИ ОТ ДВОИЧНОГО ЧИСЛА (57) Изобретение относится к вычислительной технике и может быть использо вано для сопряжения вычислительных устройств, функционирующих в системеостаточных классов, а также в составесредств передачи данных, использующихмодулярные коды. Целью изобретенияявляется повышение быстродействия.Поставленная цель достигается тем,что устройство для вычисления остатка по модулю от двоичного числа, содержащее входной регистр 1, блок 4умножения на константу по модухпо,сумматор 5 по модулю, регистры 6,7и коммутаторы 8.9, дополнитсльно со -держит блоки 2,3 свертки по модулю ссоответствующими связями, 2 ил:30 Используя схему Горнера преобразуем (1) к виду, удобному для нахожде ния остатка х от числа Х по модулю Р: х = (Х= //а 2/ ++ а,(ф кх 2(,+ аар(7 1Пусть выбранный модуль Р имеет разрядность и. Разобьем двоичное представление числа Х на группы по ш двоичных разрядов, причем ши. С учетом разбиения преобразуем (2) к 55 виду 1х = /,;/А /+ 2 ( р ++(А,/р/ )(3) Изобретение относится к вычислительной технике и может быть использовано для сопряжения вычислительных устройств, функционирующих в системе остаточных классов, а также в составе5 средств передачи данных, использующих модулярные коды.Целью изобретения является повышение быстродействия, . 10На фиг.1 приведена схема устройст.- ва для вычисления остатка по модулю от двоичного числа; на фиг,2 - схема блока свертки по модулю (для ш = 4, р = 3). 15Устройство (фиг.1) содержит входной регистр 1, блоки 2 и 3 свертки по модулю, блок 4 умножения на константу по модулю, сумматор 5 по модулю, регистры 6 и. 7, коммутаторы 8 и 9, 20 устройства, выход 10 устройства, группу тактовых входов 11,1-11.5 устройства.Блок 2 (3) свертки по модулю (фиг.2) содержит дешифратор 12 и 25 группу элементов ИЛИ 13.1 и 13.2. Входной регистр 1 имеет 1 ш разрядов с 0 по (1 ш)-й управляющий вход, при подаче сигнала на который содержимое регистра 1 сдвигается на ш разрядов влево. Блоки 2 и 3 свертки по модулю одинаковы и преобразуют ш-разрядное входное число в остаток по модулю Р. Блок Ь умножения осуществляет операцию умножения входного и-разрядного кода на константупо модулю Р. Разрядность регистров 6 и 7 коммутаторов 8 и 9 равна и.Устройство в своей работе использу ет следующее.Двоичное К-разрядное число Х может быть представлено в видекЬХ=а,2 а 2 +а 2. (1)+ в,(+ (4)При этом (э является константой, вычисленной заранее.Устройство работает следующим образом.В исходном состоянии в регистре 1 находится код преобразуемого числа Х. Коммутатор 8 подключает выход блока 2 к входу блока 4, а коммутатор 9 под ключает выход регистра 6 к входу коммутатора 9, Содержимое регистров 6 и 7 произвольно.На первом такте число А, определяемое ш старшими разрядами преобразуемого числа Х, преобразуются блоком 2 в остаток В по модулю Р.Аналогично на выходе блока 3 получается остаток В 1, от числа А, по модулю Р. Значение числа В через коммутатор 8 поступает на вход блока 4 где оно умножается на константу Р по модулю Р и складывается с Вб, в сумматоре 5.Таким образом, по окончании переходных процессов на выходе сумматора 5 имеем Результат суммирования записывается в момент поступления импульса по входу 11,4 в регистр 6.На втором такте преобразования в момент поступления импульса по входу 11.4 в регистр 6.На втором такте преобразования в момент поступления импульса по входу 11,1 содержимое регистра 1 сдвигается на ш разрядов влево, Изменяется потенциал на входе 11.2, под действием которого коммутатор 8 подключает к входу блока 4 коммутатора 9. В этом состоянии коммутатор 8 остается до конца преобразования. Содержимое регистра 6 через коммутаторы 9 и 8 поА- ступает на вход блока 4, в котором умножается на константу Р по модулю Р,Одновременно число А , представ ленное третьей группой из разрядов, преобразуемых по модулю Р блоком 3,3 14171 поступает на сумматор 5 и по окончании переходных процессов в перечисленных блоках на выходе сумматора 5 имеем результат5////в р/ + в/ р/ + в, / который в момент поступления импульса по входу 11.5 записывается в регистр 710Далее процесс преобразования происходит аналогично описанному.В последнем (1-1)-м такте результат предпоследнего (1"2)-го такта умножается в блоке 4 напо модулю Р 15 и суммнруется с величиной В определенной блоком 3 свертки. Окончательный результат преобразования Х снимается с выхода сумматора 5 на выход 1 О устройства. торов и входы разрешения ;риема первого и второго регистров соединены соответственно с тактовыми входами группы устройства, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, оно одержит первый и второй блоки свертки по модулю, причем выходы разрядов с (1 ш)-го по (1 ш-ш)-й входного регистра подключены к входу первого блока свертки по модулю (п. и, где и - разрядность1 кГмодуля 1 =К разрядность двоичного числа), выход которого со.единен с вторым информационным входом первого коммутатора, выходы разрядов с (1 ш-.тп)-го по (1 шш)-й входного регистра подключены к входу второго блока свертки по модулю, выход которого подключен к входу второго слагаемого сумматора по модулю. 20 Клю Составитель А. ев едактор Е,Копча Техред М,Ходанич Корректор А,Тясказ 4078/57В Подписнокомитета открытийкая наб И Государственногоделам изобретенийМосква, Ж, Рауш 130 Произ твенно-полиграфическое предприятие, г, Ужгор Проектная,Таким образом, предлагаемое устройство вычисляет остаток по модулю от числа произвольной разрядности, в то время как прототип оперирует лишь 25 с числами, разрядности кратной п. оформула из обре тения Устройство для вычисления остатка по модулю от двоичного числа, содержащее первый и второй регистры, входной регистр, первый и второй коммутаторы, блок умножения на константу по модулю и сумматор по моду 35 лю, причем выход первого коммутатора 4соединен с входом блока умножения на константу по модулю, выход которогосоединен с входом первого слагаемого сумматора по модулю, выход которого является выходом устройства и соединен с информационными входами первого и второго регистров, выходы которых соединены соответственно с первым и вторым информационными входами второго коммутатора, выход которого соединен с первым информационным входом первого коммутатора, вход разр=шения сдвига входного регистра, .управляющие входы первого и второго коммута