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

 

Изобретение относится к вычислительной технике и может быть использовано при проектировании устройств, выполняющих модульные операции. Цель изобретения - упрощение устройства и расширение функциональных возможностей за счет умножения чисел по произвольному модулю. Устройство содержит блок формирования частичных произведений 1, группу элементов ИЛИ 2, преобразователь 3 двоичного кода в код по модулю К, входы 4 и выходы 5. Группа элементов ИЛИ 2 позволяет уменьшить разрядность кода за счет объединения выходов одного веса элементов И блока 1, на которых невозможно одновременное появление единичных сигналов, что обеспечивает упрощение преобразователя 3 и, соответственно, устройства в целом. 2 ил.

союз советских

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

РЕСПУБЛИК (я)5 G 06 F 7/49

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4769084/24 (22) 11,12.89 (46) 15.11.91. Бюл. th 42 (72) О.Н,Музыченко (53) 681.325(088.8) (56) Авторское свидетельство СССР

1Ф 1476614, кл. Н 03 М 7/04, 1986.

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

th 1160398, кл. 6 06 F 7/49, 1983. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО

МОДУЛЮ К (57) Изобретение относится к вычислительной технике и может быть использовано при проектировании устройств, выполняющих

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

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

На фиг.1 показана схема устройства умножения по модулю К = 5; на фиг.2 — схема устройства умножения по модулю К = 11.

Устройство умножения по модулю К содержит блок 1 формирования частичных произведений, группу элементов ИЛИ 2, преобразователь 3 двоичного кода в код по модулю К, входы 4 и выходы 5. Блок 1 формирования частичных произведений соединен входами с входными шинами 4 устройства, а выходами — с входами группы

2 элементов ИЛИ и преобразователя 3 двоЯ2,, 1691834 А) ТЕНИЯ „.".:- :::" :.. модульные операции. Цель изобретения— упрощение устройства и расширение функциональных возможностей за счет умножения чисел по произвольному модулю.

Устройство содержит блок формирования частичных произведений 1, группу элементов ИЛИ 2, преобразователь 3 двоичного кода в код по модулю К, входы 4 и выходы 5.

Группа элементов ИЛИ 2 позволяет уменьшить разрядность кода за счет объединения выходов одного веса элементов И блока 1, на которых невозможно одновременное появление единичных сигналов, что обеспечивает упрощение преобразователя 3 и, соответственно, устройства в целом. 2 ил. ичного кода в код по модулю К, соединенноеюй

ro также входами с выходами элементов

ИЛИ группы 2, а выходами — с выходами 5 . О устройства. Блок 1 формирования частич- Q ных произведений содержит Р элементов И, где t — разрядность входных. кодов. Каждый Оф из элементов соединен первым входом с (Д одной из входных шин первого сомножите- Д, ля, а вторым входом — с одной из входных шин второго сомножителя таким образом, что на входах элементов И образуются все неповторяющиеся комбинации пар входных шин сомножителей.

Преобразователь 3 двоичного кода в код по модулю К может иметь любую иэ известных схемных реализаций, в том числе может быть выполнен в виде блока 6 весо- вого суммирования, входы которого являются входами преобразователя, а выходы соединены с входами узла 7 суммирования

1691834 по модулю К. Блок 6 весового суммирования выполнен на сумматорах двоичных чисел, соединенных параллельно-последовательНо, причем выходы каждого из сумматоров, кроме последнего, с весом в соединены с входами последующих сумматоров с весами

o) такими, что их сумма равна (в) mod I: . На

I выходах блока 6 суммирования формируется =- )Iogz(K+1)(+ 1-разрядный код. Узел 7 суммирования по модулю К выполнен в виде порогового блока 9, соединенного выходами с первой группой входов выходного сумматора 8, вторая группа вхоцов которого соединена с входами порогового блока 9 и входами узла суммирования, причем с входами выходного сумматора 8 соединяк>тся входы узла 7, соответствующие (I-1) младшим разрядам входного кода, а с входами порогового блока все I входов узла, Когда код на входах узла 7 суммирования по модулю К менее 2 К, порогoBblA блок 9 выполняют в виде порогового элемента с весами входов а = 2 (! = 1„„.I) и порогом К на последоваi-1 тельно соединенных элементах И и ИЛИ.

Выход блока соединен с входами разрядов выходного сумматора 8 с номерами, равными номерам единичных разряцов в двоичном представлении числа С = 2 - К„что при

К = 5 составляет С = 2 — 5 =: 3. В соответствии э," этим выход порогового блока соединен с входами первого и второго разрядов сумматора 8, Если входной код узла 7 суммирования по модулк> К равен или превышает 2К, пороговый блок выполняют в виде многопорогового элемента 10, соединенного выходами с входами блока 11 формирования вычетов. Многопороговый блок элемент 10 имеет входы с весами 2 (i == О, 1,...,I-1) и порогами выходов А = K, 2К,..., а К (где

a = — 1, m — максимальное значение хода — () на входах многопорогового элемента 10), Блок 11 формирования вычетов в общем случае содержит (а-1) элементов запрета, выходы которых соединены с входами элементов ИЛИ. j-й элемент запрета соединен прямым входом с выходом многопорогoBQI элемента с порогом JK, а инверсным входом — с его выходом с порогом (j + 1) К. р-й элемент ИЛИ соединен выходом — с входом р-го разряда выходного сумматора 8, а входами — с выходами элементов запрета с номерами ), для которых в двоичном представлении числа BI =- 2 — jK в р-м разряде имеется единица (i =- О,...,I; BI О), а также с выходом многопорогового элемента с порогом а К, если в р-м разряде числа В = 2 - а К имеется единица, Для К == 11 ВI = 5, Bz =-=

= 10.

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

Коды сомножителей Х и Y поступают на входы блока 1 формирования частичных произвеуений, на выходах которого формируется t -разрядный двоичный код, где t =

=)logz (К+ 1)(, имеюший веса разрядов, равные произведениям весов разрядов входного кода.

Сигналы с части выходов блока 2, на которых возможно одновременное появление единичных сигналов поступают на входы блока 6 весового суммирования преобразователя 3 двоичного кода в код по моцулю К, а остальные- на входы элементов

ИЛИ группьI 2, а с их выходов — также на входы блока б. При этом эл= менты ИЛИ 2 сокращают разрядность кода на входах преобразователя 3. Преобразователь 3 формирует код остатка входного кода по модулю

К. Сначала блок б весового суммирования формирует на своих выходах путем последовательной свертки =)Iogz (K+ 1)(+ 1-разрядный двоичный код, остаток по модулю К которого равен остатку по модулю К произведения входных кодов. Сигналы (i-1) младших разрядов кода с выходов блока 6 поступают на первую группу входов узла 7 суммирования по модулю К, кроме того — на входы порогового блока, на выходах которого формируются сигналы кода вычета, поступающие на вторую группу входов выходного сумматора 8, причем код на выхоцах блока 9 формируется таким образом, что, суммируясь с кодом, поступающим на другую группу входов сумматора 8, он формирует.на его выходах суммы код остатка по модулю К входного кода блока 7, т.е. код остатка по модулю К произведения входных кодов X u Y.

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

Устройство для умножения по модулю К, содержащее блок формирования частичных произведений, состоящий из tz элементов

И, где с = )logz (К+ 1)(, и преобразователь двоичного кода в код по модулю К, выходы которого соединены с выходами разрядов результата устройства, входы разрядов первого и второго сомножителей устройства соединены с первыми и вторыми входами соответствующих элементов И блока формирования частичных произведений, выходы которых соединен ы с входами соответствующих весов преобразователя двоичного кода в код по модулю К, о т л и—

3691834 ча ю щееся тем,что,сцельюупрощения устройства и расширения функциональных возможностей эа счет умножения чисел по произвольному модулю. в него введена группа элементов ИЛИ, причем входы каж- 5 дого элемента ИЛИ группы соединены с выходами одного веса соответствующих элементов И блока формирования частичных произведений, а выходы элементов ИЛИ группы — с входами соответствующих весов преобразователя двоичного кода в код по модулю К,