Устройство для умножения по модулю К Советский патент 1991 года по МПК G06F7/49 

сл

с

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

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

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

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

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

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

сх

Ч)

00 GO

по модулю К. Блок 6 весового суммирования выполнен на сумматорах двоичных чисел, соединенных параллельно-последовательно, причем выходы каждого из сумматоров, кроме последнего, с весом ш соединены с входами последующих сумматоров с весами о) такими, что их сумма равна (ш) mod k На выходах блока 6 суммирования формируется I 1од2(К+1) + 1-разрядный код. Узел 7 суммирования по модулю К выполнен в виде порогового блока 9, соединенного выходами с первой группой входов выходного сумматора 8, вторая группа входов которого соединена с входами порогового блока 9 и входами узла суммирования, причем с входами выходного сумматора 8 соединяются входы узла 7, соответствующие (1-1) младшим разрядам входного кода, а с входами порогового блока все I входов узла. Когда код на входах узла 7 суммирования по модулю К менее 2 К, пороговый блок 9 выполняют и виде порогового элемента с весами входов « 2м (i 1,... I) и порогом К на последовательно соединенных элементах И и ИЛИ. Выход блока соединен с входами разрядов выходного сумматора 8 с номерами, равными номерам единичных, разрядов в двоичном представлении числа С 2 - К, что при К 5 составляет С 23 -5 3. В соответствии с этим выход порогового блока соединен с входами первого и второго разрядов сумматора 8. Если входной код узла 7 суммирования по модулю К равен или превышает 2К, пороговый блок выполняют в виде многопорогового элемента 10, соединенного выходами с входами блока 11 формирования вычетов. Многопороговый блок элемент 10

имеет входы с весами 2 (I 0, 11-1) и

порогами выходов А К, 2К,..., а К (где

а. ; гп - максимальное значение кода

на входах многопорогового элемента 10). Блок 11 формирования вычетов в общем случае содержит («--1) элементов запрета, выходы которых соединены с входами I элементов ИЛИ. j-й элемент запрета соединен прямым входом с выходом многопорогового элемента с порогом JK, а инверсным входом - с его выходом с порогом Q + 1) К. элемент ИЛИ соединен выходом - с входом /о-го разряда выходного сумматора 8, а входами - с выходами элементов запрета с номерами J, для которых в двоичном представлении числа Bj 2 jK в р-м разряде

имеется единица (i - 01; Bj 0), а также

с выходом многопорогового элемента с порогом а К, если в разряде числа В 2 - а К имеется единица. Для К - 11 В - 5, Е$2 - 10.

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

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

Коды сомножителей X и Y поступают на входы блока 1 формирования частичных

0 произведений, на выходах которого формируется t -разрядный двоичный код, где t log2 (К + 1), имеющий веса разрядов, равные произведениям весов разрядов входного кода.

5Сигналы с части выходов блока 2. на

которых возможно одновременное появление единичных сигналов поступают на входы блока 6 весового суммирования преобразователя 3 двоичного кода в код по

0 модулю К, а остальные- на входы элементов ИЛИ группы 2, а с их выходов - также на входы блока 6. При .BTOIV элементы ИЛИ 2 сокращают разрядность кода на входах преобразователя 3. Преобразователь 3 форми5 рует код остатка входного кода по модулю К. Сначала блок 6 весового суммирования формирует на своих выходах путем последовательной свертки iog2(K+ 1)+ 1-разрядный двоичный код, остаток по модулю К

0 которого равен остатку по модулю К произведения входных кодов. Сигналы (-1) младших разрядов кода с выходов блока 6 поступают на первую группу входов узла 7 суммирования по модулю К, кроме того - на

5 входы порогового блока, на выходах которого формируются сигналы кода вычета, поступающие на вторую группу входов выходного сумматора 8, причем код на выходах блока 9 формируется таким образом,

0 что, суммируясь с кодом поступающим на другую группу входов сумматора 8, он фор- мирует.на его выходах суммы код остатка по модулю К входного кода блока 7, т е. код остатка по модулю К произведения входных

5 кодов X и Y.

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

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

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

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

4

У,

Ч

&

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

Фиг1