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

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в СиИзобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Известно устройство (аналог) для умножения в системе остаточных классов, содержащее входные и выходной регистр, дешифраторы, группы ключей, группу узлов табличного формирования разрядов результата , группы элементов И, сумматор по модулю Р, сумматор по модулю два, элементы И и ИЛИ. Недостаток устройства -большое количество используемого оборудования. Близким по технической сущности (аналогом ) к предлагаемому изобретению является устройство, которое содержит первый и второй входные регистры, дешифраторы, группы элементов ИЛИ, группы элементов стеме остаточных классов. Цель изобретения - уменьшение количества оборудования . Цель достигается за счет уменьшения количества блоков умножения на константу, по модулю путем введения группы элементов ИЛИ 7, элемента ИЛИ 8, элемента НЕ 10, двух блоков 9, 11 элементов И, второго 12 блока элементов ИЛИ. Сущность изобретения состоит в выполнении операции модульного умножения при помощи Сокращенного числа блоков умножения на константу за счет использования соотношения A(m-B)modm(ni-AB)modm (А, В - операнды , m - модуль -операции). Количество блоков умножения по модулю сокращено с (тп-2) до (2) блоков. 1 ил. табл. И, элементы И и ИЛИ, табличный вычислитель , шифратор, выходной регистр. Недостаток устройства - большое количество используемого оборудования. Наиболее близким по технической сущности (прототипом) к изобретению является устройство, которое содержит группу блоков умножения на константу по модулю, дешифратор , группу блоков элементов И, блок элементов ИЛИ. Недостаток прототипа-большое количество блоков умножения на константу по модулю, причем их число существенно зависит от модуля операции. Также число этих блоков тесно связано с количеством блоков элементов И, входящих в группу. Это приводит к увеличению количества элементов И, необходимых для реализаций устройства. & Ј ч ь о ел

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

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

РЕСПУБЛИК

„,5U,, 1716511 А1 (я)5 G 06 F 7/72

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ .(57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано s вычислительных маши- нах и устройствах, функционирующих в сиИзобретение относится к области авто- И, элементы И и ИЛИ, табличный вычислиматики и вычислительной техники и может тель, шифратор, выходной регистр. Недобыть использовано в вычислительных маши- статок устройства — большое количество нах и устройствах, функционирующих в си- используемого оборудования. стеме остаточных классов.

Известно устройство (аналог) для умно- Наиболее близким по технической сущжения в системе остаточных классов, содер-: ности (прототипом) к изобретению является жащее входные и выходной регистр, устройство. которое содержит группу блодешифраторы, группы ключей, группу узлов ков умножения на константу по модулю, детабличного;формирования разрядов резуль- .. шифратор, группу блоков элементов И. блок тата, группы элементов И, сумматор по мо- элементов ИЛИ. дулю Р, сумматор по модулю два, элементы Недостаток прототипа — большое коИ и ИЛИ. Недостаток устройства — большое личество блоков умножения на константу по количество используемого оборудования, модулю, причем их число существенно завиБлизким по технической сущности(ана- сит от модуля операции. Также число этих логом) к предлагаемому изобретению явля- блоков тесно связано с количеством блоков ется устройство, которое содержит. первый элементов И; входящих в группу. Это привои второй входные регистры, дешифраторы, дит к увеличению количества элементов И, группы элементов ИЛИ, группы элементов необходимых для реализации устройства.

1 (2:1 ) 4832194/24

„(22) 29..05;90 (46) 29.02.92..Бюл; N 8

P2) В.А,Краснобаев, В.П.Ирхин, B,Ä.Ýêñòà, А.А,Сахаров и М.В.Юмашев (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М 1187161, кл. G 06 F 7/49, 1983. . Авторское свйдетельство СССР

N- 1617439, кл. G 06 F 7/72. 1988.стеме остаточных классов. Цель изобретения — уменьшение количества оборудования. Цель достигается за счет уменьшения количества блоков умножения на константу по модулю путем введения группы элементов ИЛИ 7, элемента ИЛИ 8, элемента HE

10, двух блоков 9, 11 элементов И, второго

12 блока элементов ИЛИ, Сущность изобретения состоит в выполнении операции модульного умножения при помощи сокращенного числа блоков умножения на константу за счет использования соотношения A(m-B)modmgm-АВ)гпобв (А,  — опе.ранды, m — модуль. операции), Колйчество блоков умножения по модулю сокращено с (в-2) до (— ) блоков, 1 ил. Р T80h

171657 1

10 входами элементов ИЛИ группы, выходы ко- 25 торых соединены соответственно с первыми входами блоков элементов И группы, m — 1 выходы (— + I)-e дешифратора (m — мо2

m — 1 30 дулъ устройства) (1=1, ) соединены с

2 соответствующими I-ми входами элемента

ИЛИ, выход которого соединен с вторым входом второго блока элементов И, а через

Цель изобретения — уменьшение количества оборудования.

Поставленная цель достигается тем, что в устройство, содержащее дешифратор, группу блоков элементов И и первый блок элементов ИЛИ, группу блоков умножения на константу по модулю, причем вход второго сомножителя устройства соединен с вторым входом первого блока элементов И группы и с входами блоков умножения на константу по модулю группы, выход К-ro (К=1 — (m-3)/2, m — значение модуля) блока. умножения на константу по модулю группы соединен с. вторым входом (К+1)-го блока элементов И группы, выходы которого соединены с соответствующими входами первого блока элементов ИЛИ, введены группа элементов ИЛИ, элемент ИЛИ, элемент НЕ, „два блока элементов И,.второй блок элементов ИЛИ и преобразователь обратного кода . по модулю, причем вход первого сомножителя устройства соединен с входом дешифратора, выходы которого, кроме младшего, соедийены попарно с первыми и вторыми. элемент Н Е с вторым входом первого блока . элементов И, первый вход которого соединен с выходом первого блока элементов

ИЛИ, а выход — с первым входом второго блока элементов.ИЛИ, второй вход которого соединен с выходом второго блока элементов И, а выход является выходом устройства, вход преобразователя кода соединен с выходом первого блока элементов ИЛИ, а . выход — с первым входом второго блока элементов И.

Сущность изобретения состоит в следующем. Рассмотрим табл. 1, в которой отражены результаты операции А B(mod5) (А,  — операнды), Отметим следующую закономерность при А либо В равном нулю А B(mod5)=0, при

B=1 А B(mod5)=A; следовательно, необходимо реализовать три строки при В=-2, 3, 4, Однако можно использовать соотношение

A(m-B)mod m=.(m — А B)mod m, где m — модуль. При этом для реализации устройства достаточно одного. блока умножения на константу по модулю. Изобразим в табл; 2 ре/ зультат его работы для В=2(А — результат}.

В общем случае потребуется (m 3)/2 блока умножения на константу по модулю..

Необходимо также отслеживать, в первой или второй половине диапазона находится операнд В. Если 0 <  — — (ув =:0) то и\ .1 работа устройства происходит при помощи существующих блоков умножения на константу по модулю (если m,=5, то один блок), m+1

При < В

Коммутация операнда В отмечена в таб- . лице I. Одновременно с сокращением блоков умножения на константу по модулю происходит и уменьшение числа блоков эле-. ментов И, Возможность достижения положительного эффекта от использования данного изобретения состоит в уменьшении количества оборудования ввиду уменьшения количества блоков умножения на константу по модулю, На чертеже представлена структурная схема устройства, где: 1 — вход второго сомножителя устройства, 2 — группа блоков элементов И, 3 — группа блоков умножения на константу по модулю, 4 — первый блок элементов ИЛИ, 5 — вход первого сомножителя устройства, 6- дешифратор, 7- группа элементов ИЛИ, 8- элемент ИЛИ, 9- второй блок элементов И, 10 — элемент WE, 11первый блок элементов И, 12 — второй блок элементов ИЛИ, 13 — выход устройства, 14— преобразователь кода.

Вход 1 второго сомножителя устройства соединен с вторым входом первого блока элементов И 2 группы и с входами блоков . умножения на. константу по модулю 3 группы, выход K-ro (К=1-(m-3)/2, пт —: значение модуля) блока умножения на константу по модулю 3 группы соединен с вторым входом (К+1)-го блока элементов И 2 группы, выходы . которых. соединены с соответствующими-. входами первого блока 4 элементов ИЛИ, вход 5 первого сомножителя устройства с0единен с входом дешифратора 6, выходы которого, кроме младшего, соединены попарно с первыми и вторыми. входами элементов ИЛИ 7 группы, выходы .которых соединены соответственно с первыми вхо-, дами блоков элементов И 2 группы, выходы

m — 1 (+ I)-e дешифратора 6 (m — модуль) (I=1, 1716511

20

m — 1

) соединены с соответствующими I-ми входами элемента ИЛИ 8, выход которого соединен с вторым входом второго 9 блока элементов И, а через элемент НЕ 10 — с вторым входом первого блока 11 элементов

И, первый вход которого соединен с выходом первого блока 4 элементов ИЛИ, а выход — с первым входом второго блока 12 элементов ИЛИ, второй вход которого соединен с выходом второго блока 9 элементов

И, а. выход является выходом 13 устройства, вход преобразователя 14 кода соедийен с выходом первого блока 4 элементов ИЛИ, а выход — c первым входом второго блока 9 элементов И.

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

Сомножитель В с входа 5 поступает:на вход дешифратора 6. При В=О на выходах, кроме младшего, дешифратора. 6 нулевые значения. Следовательно, все блоки 2 элементов И закрыты, и на их выходах, а следовательно и на выходе первого блока 4 элементов ИЛИ; нулевое значение; которое 25 в виде нулевого результата операции посту пает. на выход 13 устройства. При Ос

< В <: 2 сигнал с выхода дешифратора

m — 1

6 через соответствующий элемент группы 30 элементов ИЛИ 7 открывает соответствующий.значению В блок элементов И 2. Сомножитель А поступает со входа 1. устройства на. входы блоков 3 умножения на константу по модулю и на второй вход первого блока 2 35 элементов И группы. В блоках 3 умножения формируются соответствующие произведеm — 1 ния А =А К(К=2- ) по модулю. Через.

2 открытый блок 2 элементов И группы соот- 40 ветствующее произведение А поступит на. вход первого 4 блока элементов ИЛИ и с его выхода (сигнал на выходе элемента ИЛИ 8; отсутствует, ув=О) на вход первого 11 блока. элементов И, на второй вход которого по- 45 ступает сигнал с выхода элемента НЕ 10 и далее через второй блок 12 элементов ИЛИ . на выход 13 устройства. При А=О значение

A (см. ° табл, 2) также равно нулю, что приводит к формированию нулевого произведения.

Если В (m — 1(ув =1), то

IYl +1

2 работа устройства происходит, как и в предыдущем случае, но сигнал на выходе эле- 55 мента ИЛИ 8 присутствует, поэтому промежуточный результат операции поступает на вход преобразователя 14 кода и значение результата модульного умножения через открытый второй 9 блок элемен-: тов И и далее через второй 12 блок элементов ИЛИ поступает на выход 13 устройства, Рассмотрим примеры конкретного выполнения операции при m=5.

Пример 1. Пусть необходимо определить результат модульного умножения для

A=2, В=2 (А,  — операнды).

На вход дешифратора 6 поступает число

В=010, на вход 1 -число А=010..Сигнал на выходе элемента ИЛИ 8 отсутствует (уц=О).

Сигнал с второго выхода дешифратора 6 поступает на второй вход первого элемента

ИЛИ 7 группы, которая в этом случае состоит из двух элементов. С выхода первого элемента ИЛИ 7 сигнал поступает на первый вход блока умножения 2 на константу по модулю (см. табл. 2), на другой вход которого поступает A=010. Результат операции Ак Bmod5=100 поступает через первый блок 4 элементов ИЛИ, первый блок 11 элементов

И, второй блок 12 элементов ИЛИ на выход

13 устройства.

Пример 2. Пусть необходимо определить результат модульного умножения для

А=2, В=4 (А,  — операнды).

В этом случае путь операнда А аналогичен первому примеру. Сигнал на выходе элемента ИЛИ 8 присутствует,-Сигнал с четвертого выхода дешифратора 6 поступает на второй вход второго элемента ИЛИ 7 группы, с выхода которого поступает на второй вход первого блока 2 элементов И группы, На выходе первого 4 блока элементов

ИЛИ будет число 010, которое поступит на вход преобразователя 14 кода, с выхода которого (см; табл. 3) число 011 через открытый второй 9 блок элементов И и второй 12 блок элементов ИЛИ поступит на выход 13 устройства, Рассмотрим, какой выигрыш достигается при реализации данного изобретения.

Прототип содержит (m — 2) блоков умножения на константу по модулю, изобретение(m 3)/2. Следовательно выигрыш R составит

m — 2

R=2 —, при mf R-4 2.

m — 3

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

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

ИЛИ, группу блоков умножения на константу по модулю, причем вход второго сомножителя устройства соединен с первым входом первого блока элементов И группы и входами блоков умножения на константу по модулю группы, выход К-ro (К=1-(т-3)/2, m — значение модуля) блока умножения на

1716511

Таблица2

Таблица 3

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

ИЛИ, элемент НЕ, два блока элементов И, второй блок элементов ИЛИ и преобразователь обратного кода по модулю, причем выходы дешифратора, кроме младшего, соединены попарно с первыми и вторыми входами элементов ИЛИ группы, выходы которых соединены соответственно с вторыми входами .блоков элементов И группы, m — 1 (+ 1 -е выходы дешифратора (l=l2

«m — 1

) соединены с соответствующими I-ми

5 входами элемента ИЛИ, выход которого соединен.с первым входом первого блока элементов И и через элемент НŠ— с первым входом второго блока элементов И, второй вход которого соединен с выходом первого

10 блока элементов ИЛИ и входом преобразователя обратного кода по модулю, выход которого соединен с вторым входом первого блока элементов И, выход которого соединен с первым входом второго блока элемен15 тов ИЛИ, второй вход которого соединен с выходом второго блока элементов И, а выход — с выходом результата устройства.

Таблица 1