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

 

Изобретение относится к вычисли тельно.й технике и может быть использовано для сопряжения вычислительных устройств, функционирующих в системе остаточных классов, а также в составе средств передачи данных, использующих модулярные коды. Целью изобретения является повышение быстродействия. Поставленная цель достигается тем, что устройство для вычисления остат ка по модулю от двоичного числа, со держащее входной регистр , блок 4 умножения на константу по модулю, сумматор 5 по модулю, регистры 6,7 и коммутаторы 8,,9, дополнительно со-- держит блоки 2,3 свертки по модулю с соответств тощими связями, 2 ил ///

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (19) (11) (51) 4 Н 03 М 7/18

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н A BTGPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4183107/24-24 (22) 20.01.87 (46) 15.08 ° 88. Бюл.N- 30 (72) А,Б. Акулинчев и С.Н.Хлевной (53) 681.3(088.8) (56) Авторское свидетельство СССР №- 1001079, кл. Н 03 М 7/18, 1981.

Авторское свидетельство СССР

¹ 1156058, кл. H 03 М 7/18, 1984. (54) УСТРОЙСТВО ДЛЯ В11ЧИСЛЕНИЯ ОСТАТКА ПО МОДУЛИ ОТ ДВОИЧНОГО ЧИСЛА (57) Изобретение относится к вычислительной технике и может быть использовано для сопряжения вычислительных устройств, функционирующих в системе остаточных классов, а также в составе средств передачи данных, использующих модулярные коды. Целью изобретения является повышение быстродействия.

Поставленная цель достигается тем, что устройство для вычисления остатка по модулю от двоичного числа, содержащее входной ре-.èñòð блок 4 умножения на константу по модулю, сумматор 5 по модулю, регистры 6,7 и коммутаторы 8.9, дополнитсльно со— держит блоки 2,3 свертки по модулю с соответствующими связями, 2 ил:

1417192

Используя схему Горнера преобразуем (1) к виду, удобному для нахожде- 45 ния остатка х от числа Х по модулю P: х= Xf = /,„./а„„2/ + ... +а/ к х 2/ + аь/ (71, Пусть выбранный модуль P имеет разрядность и. Разобьем двоичное представление числа Х на группы по т двоичных разрядов, причем m > n, С учетом разбиения преобразуем (2) к 55 виду

I х = /,;../А /р 2 / р + ° ° ° +/A,/ð/ ) (3) Изобретение относится к вычислительной технике и может быть использовано для сопряжения вычислительных устройств, функционирующих в системе остаточных классов, а также в составе

5 средств передачи данных, использующих модулярные коды.

Целью изобретения является повышение быстродействия.. 10

На фиг.l приведена схема устройст.ва для вычисления остатка по модулю от двоичного числа; на фиг.2 - схема блока свертки по модулю (для m = 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 имеет 1m разрядов с 0 по (1m-1)-й управляющий вход, при подаче сигнала на который содержимое регистра 1 сдвигается на ш разрядов влево. Блоки 2 и 3 свертки по модулю одинаковы и преобразуют m-разрядное входное число в остаток по модулю P.

Блок 4 умножения осуществляет операцию умножения входного и-разрядного кода на константу по модулю P. Разрядность регистров 6 и 7 коммутаторов 8 и 9 равна и.

Устройство в своей работе использу ет следующее.

Двоичное К-разрядное число Х может быть представлено в виде

1с -1 1 Ь

X= а,2 +...+а,2 + а,2 . (1) + а;„,„, k где1=) /mf, i= l, 1.

Обозначая В (А,I н Р =/Z" приведем (3) к виду:

" - / ° "/ 1 Р/ + В1- / Р! + ° "+

Р з В1 Р ° ° °

+ В,/ (4) При этом является константой, вычисленной заранее.

Устройство работает следующим образом.

В исходном состоянии в регистре 1 находится код преобразуемого числа Х.

Коммутатор 8 подключает выход блока 2 к входу блока 4, а коммутатор 9 под ключает выход регистра 6 к входу коммутатора 9, Содержимое регистров

6 и 7 произвольно.

На первом такте число А, определяемое m старшими разрядами преобразуемого числа X преобразуются блоком

2 в остаток В по модулю P.

Аналогично на выходе блока 3 получается остаток В1, от числа А »1 по модулю Р. Значение числа В через коммутатор 8 поступает на вход блока 4 где оно умножается на константу Р по модулю P и складывается с В 1 в сумматоре 5.

Таким образом, по окончании переходных процессов на выходе сумматора

5 имеем

//В Р/, В,/

Результат суммирования записывается в момент поступления импульса по входу 11,4 в регистр 6.

На втором такте преобразования в момент поступления импульса по входу

ll,4 в регистр 6.

На втором такте преобразования в момент поступления импульса по входу

11.1 содержимое регистра 1 сдвигается на m разрядов влево. Изменяется потенциал на входе 11.2, под действием которого коммутатор 8 подключает к входу блока 4 коммутатора 9. В этом состоянии коммутатор 8 остается до конца преобразования. Содержимое регистра 6 через коммутаторы 9 и 8 по ступает на вход блока 4, в котором умножается на константу Р по модулю Р, I (Одновременно число А, представленное третьей группой из разрядов, преобразуемых по модулю P блоком 3, 3 14171 поступает на сумматор 5 и по окончании переходных процессов в перечисленных блоках на выходе сумматора 5 имеем результат

////в p/ + в,,l+ р/ + в,,/ который в момент поступления импульса по входу 11.5 записывается в регистр 7.

Далее процесс преобразования происходит аналогично описанному.

В последнем (1-1)-м такте результат предпоследнего (1-2)-го такта умножается в блоке 4 íà р по модулю Р15 и суммнруется с величиной В,, определенной блоком 3 свертки. Окончательный результат преобразования (Х снимается с выхода сумматора 5 на выход 1О устройства. торов и входы разрешения -., риема первого и второго регистров соединены соответственно с тактовыми входами группы устройства, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, оно одержит первый и второй блоки свертки по модулю, причем выходы разрядов с (1тп-1 )-ro no (Im-m)-й входного регистра подключены к входу первого блока свертки по модулю (п и, где n — разрядность

1 кГ модуля> 1 = ) (> К разрядность двоичного числа), выход которого со.единен с вторым информационным входом первого коммутатора, выходы разрядов с (1ш--тп-I)-го по (1m-2m)-й входного регистра подключены к входу второго блока свертки по модулю, выход которого подключен к входу второго слагае-мого сумматора по модулю.

20!

Ь формула из обре тения

Составитель А.Клюев

Редактор Е,Копча Техред M.Õoäàíè÷ Корректор А.Тяско

Заказ 4078/57 Тираж 928 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д, 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Таким образом, предлагаемое устройство вычисляет остаток по модулю от числа произвольной разрядности, в то время как прототип оперирует лишь 25 с числами, разрядности кратной п-1.

Устройство для вычисления остатка по модулю от двоичного числа, содержащее первый и второй регистры, входной рег ис тр, первый и в торой коммутаторы, блок умножения на константу по модулю и сумматор по моду35 лю, причем выход первого коммутатора

92 4 соединен с входом блока утножения на константу по модуттю, выход которого ! соединен с входом первого слагаемого сумматора по модулю, выход которого является выходом устройства и соединен с информационными входами первого и второго регистров, выходы которых соединены соответственно с первым и вторым информационными входами второго коммутатора, выход которого соединен с первым информационным входом первого коммутатора, вход разр=шения сдвига входного регистра, .управляющие входы первого и второго коммута