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

 

Устройство для вычисления остатка по модулю от двоичного числа относится к вычислительной технике и может быть использовано в специализированных вычислительных устройствах, функционирующих в СОК. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается сокращением блока свертки, коммутатора и перераспределением связей между остальными блоками. Устройство содержит входной регистр 1. блок свертки 2, сумматор по модулю 3, блок 4 умножения на константу по модулю, коммутатор 5, регистры 6 и 7, группу тактовых входов 8.1-8.4, выход 9. 1 ил.

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

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

РЕСПУБЛИК (н)ю Н 03 М 7/18

")1 1 О:.! 4

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4886580/24 (22) 26.11.90 (46) 30.07.92, Бюл. М 28 (72) Н.И.Червяков и А.А,Оленев (56) Авторское свидетельство СССР

ЬЬ 1156058, кл. Н 03 М 7/18, 1984, Авторское свидетельство СССР.

N. 1417192, кл. Н 03 М 7/18, 1987. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ДВОИЧНОГО ЧИС-, . . ЛА (57) Устройство для вычисления остатка по модулю от двоичного числа относится к вы,, Ы,, 1751858 А1 числительной технике и может быть использовано в специализированных вычислительных устройствах, функционирующих в СОК.

Цель изобретения — сокращение аппаратурных затрат. Поставленная цель достигается сокращением блока свертки, коммутатора и перераспределением связей между остальными блоками. Устройство содержит входной регистр 1, блок свертки 2, сумматор по модулю 3, блок 4 умножения на константу по модулю, коммутатор 5, регистры 6 и 7, группу тактовых входов 8.1-8.4, выход 9. 1 ил.

1751858

Изобретение относится к вычислительной технике и может быть использовано для сопряжения вычислительных устройств, функционирующих в системе остаточных классов.

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

Недостатком известного устройства являются большие аппаратурные затраты.

Наиболее близким к изобретению является устройство для вычисления остатка по модулю от двоичного числа содержащее входной регистр, первый и второй блоки свертки по модулю, первый и второй регистры, первый и второй коммутаторы, блок умножения на константу по модулю и сумматор по модулю, причем первый и второй блок и свертки по модулю, причем выхОды разрядов с (Im-1 )-Г 0 и О (Im-m)-Й входного регистра подключены к входу первого блока свертки по мо улю(m n, где n—

K разрядность модуля, =- — —, (К вЂ” разрядITI ность двоичного числа), выход которого соединен с вторым информационным входом первого коммутатора, выходы разрядов c (fm — m-1)-го по (!л — 2m)-й входного регистра подключены к входу блока свертки по модулю, выход которого подключен к входу второго слагаемого сумматора по модулю, выход первого коммутатора соединен с входом блока умножения на константу по моду лю, выход которого соединен с входом первого слагаемого сумматора по модулю, выход которого является выходом устройства и соединен с информационными входами первого и второго регистра, выходы которых соединены соответственно с первым и вторым информационными входами второго коммутатора, выход которого соединен с первым информационным входом первого коммутатора, вход разрешения сдвига входного регистра, управляющие входы первого и второго коммутаторов и входы разрешения приема первого и второго регистров соединены соответственно с тактовыми. входами группы устройства.

Недостатком известного устройства являются большие аппаратурные затраты.

Целью изобретения является сокращение аппаратурных затрат.

Поставленная цель достигается тем, что из известного устройства, содержащего входной регистр, два блока свертки, два коммутатора, блок умножения на константу, сумматор по модулю, два регистра, имеется возможность изымать один блок свертки по модулю и один коммутатор.

Тогда устройство будет содержать входной регистр, блок свертки, сумматор по мо5 дулю, блок умножения на константу, два регистра и коммутатор, причем выходы входного регистра с (1„-1)-го по (I>-m)-й подключены к блоку свертки„выходы блока свертки подключены к первым входам сум10 матора по модулю, вторыми входами сумматора по модулю является выход коммутатора, выход сумматора по модулю является входом блока умножения по модулю, его выход является входом для регист15 ров хранения промежуточных результатов, их выходы являются входами коммутатора.

В основу работы устройства положено следующее, Двоичное К-разрядное число X может

20 быть представлено в виде

Х = ак-12 + ... a12 + ap2

Используя вычисления по схеме Горне25 ра преобразуем выражение (1) к виду, удобному для нахождения остатка х от числа X по модулю Р х = !Х!р = I... !ак1 2 I+p+, а1 р х

30 x2! p+ap р (2)

Пусть выбранный модуль P имеет раз-. рядность и. Разобъем двоичное представление числа Х на группы по m двоичных

35 разрядов, причем m>n. С учетом разбиения преобразует выражение (2) к виду х= I...I ÀI! р 2 I+p+ ...)А1! р р, (3)

40 А;= aim2 + ... + almm+12+ а> -m, -1 где! =)К/m(, i =,1,i, Обозначим В =- IAII p tnP= !2 !+р, при ведя (3) к виду:

x = I... IBIPI р+В -1I р 3I+p+ ...+ В1! р(4)

При этом,д является константой, вычисленной заранее, 50 Таким образом, выражение (4) позволяет реализовать получение остатка от исходного числа по модулю P.

На чертеже приведена функциональная схема устройства для вычисления остатка

55 по модулю от двоичного числа.

Устройство для вычисления остатка по модулю содержит входной регистр 1, блок . свертки 2, сумматор по модулю 3, блок умножения на константу по модулю 4. регист1751858

6 ры, 6 и 7, коммутатор 5, выход устройства 9, группу тактовых входов 8.1-8.4 устройства.

Входной регистр 1, функционально известный элемент, имеет I разрядов, с 0 по (1 -1)-й управляющий вход, при подаче сигнал на который содержимое регистра 1 сдвигается на m разрядов влево.

Блок 2 свертки является функционально известным элементом, Выходы входного регистра 1 с (Im-1)-ro по (1„-m)-й подключены к блоку свертки 2.

Сумматор по модулю 3 известный функциональный элемент. К его входам подклю:чены выходы блока свертки 2 и коммутатора

5. Выходы сумматора по модулю 3 подключены к известному элементу блока 4 умножения на константу по модулю. Выход блока

4 подключен к известным функционально элементам регистрам 6 и 7, которые в свою очередь подключены к коммутатору 5. Запись в регистры 6 и 7 осуществляется по тактовым импульсам 8.3-8.4, Работой коммутатора управляет импульс 8.2. Выход сумматора 3 является и выходом устройства, Устройство работает следующим образом, В исходном состоянии в регистре 1 находится код преобразуемого числа Х, Регистры 6 и 7 обнулены.

На первом такте число Аь определяемое

m старшими разрядами преобразуемого числа Х, преобразуются блоком 2 свертки в остаток В по модулю P.

На сумматоре 3 по модулю происходит сложение В с нулем, так как коммутатор 5 подключен регистры 6 или 7, которые обнулены. В блоке умножения 4 на константу по модулю происходит умножение на константу Р по модулю Р.

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

4 имеем

IB Plp.

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

На втором такте преобразования в момент поступления импульса ко входу 8.1 содержимое регистра 1 сдвигается на m разрядов влево. Коммутатор 5 подключен к входу сумматора 3 регистр 6. Содержимое регистра 6 через коммутатор 5 поступает на вторые входы сумматора по модулю 3, на первые входы которого поступает следующий остаток Вь1 и сумма поступает на вход блока 4 умножения, По окончании переходных процессов и - еем результат

lBI 3I ð+ Вь1 /3I р, который в момент поступления импульса ко входу 8.4 записывается в регистр 7.

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

В последнем (1-1)-ом такте окончательный результат снимается с выхода сумматора 3 на выход устройства 9.

В предлагаемом устройстве отсутствуют два блока: блок свертки и коммутатор, что

10

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

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

35 константу по модулю, входной регистр, выходы с (I -1)-го по (lm=m)-й которого соединены с входами блока свертки по модулю (где m>n,! =)К/m(, К вЂ” разрядность двоичного числа, n — разрядность модуля), информационные выходы первого и второго регистров подключены к информационным входам коммутатора, вход разрешения сдвига входного регистра, управляющий

40 вход коммутатора, вход разрешения за45 писи первого и второго регистров соединены с тактовыми входами группы устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, в нем выходы блока свертки подключены к первой группе входов сумматора по моду50 лю, вторая группа входов которого соединена с выходами коммутатора, выход сумматора по модулю подключен к входу блока умножения на константу по модулю, выход которого подключен к информационным входам первого и второго регистров, выход сумматора по модулю является выходом устройства, 55 обеспечивает следующую экономию. Например, если коммутатор построен на схе15 мах И, то происходит сокращение íà 2m двухвходовых схем И. Если блок свертки имеет дешифратор и схемы ИЛИ и дешифратор построен как пирамидальн ы й, то н е обходи ма 4(2 — 1) двух входо20 вых элементов И, а также затраты на элементы ИЛИ, которые также будут расти с ростом модуля. Выигрыш в оборудовании очевиден, при этом в быстродействии предлагаемое устройство проигрывает прототи25 пу всего один .такт. Преимущество предлагаемого устройства достигается изменением связи между блоком свертки и сумматором по модулю и блоком умножения на константу по модулю.