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

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

Поставленная цель достигается тем, что в устройство, содержащее дешифратор, группу блоков элементов И и первый блок 5 элементов ИЛИ, группу блоков умножения на константу по модулю, причем вход второго сомножителя устройства соединен с вторым входом первого блока элементов И группы и с входами блоков умножения на 10 константу по модулю группы, выход К-го ((т-3)/2, т - значение модуля) блока умножения на константу по модулю группы

.соединен с вторым входом (К+1)-го блока элементов И группы, выходы которого сое- 15 динены с соответствующими входами первого блрка элементов ИЛИ, введены группа элементов ИЛИ, элемент ИЛИ, элемент НЕ,

два блрка элементов И, второй блок элементов ИЛ И и преобразователъ обратного кода 20

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

выходы + l)-e дешифратора (гп - модуле устройства) (, -) соединены с

соответствующими l-ми входами элемента ИЛИ. выход которого соединен с вторым входом второго блока элементов И, а через элемент НЕ с вторым входом первого блока 3.5 элементов И, первый вход которого соединен с выходом первого блока элементов ИЛИ, а выход - с первым входом второго блока элементов ИЛИ, второй вход которого .соединен с выходом второго блока элемен- 40 тов И. а выход является выходом устройства, вход преобразователя кода соединен с выходом первого блока элементов ИЛИ, а выход - с первым входом второго блока элементов И,45

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

Отметим следующую закономерность: 50 при А либо В равном нулю A B(mod5)0, при A B(mod5)A, следовательно, необходимо реализовать три строки при , 3, 4. Однако можно использовать соотношение A(m-B)mod m(m-A B)mod m, где m - мо- 55 дуль. При этом для реализации устройства I. достаточно одного блока умножения на константу по модулю. Изобразим в табл. 2 результат его работы для (А- результат).

В общем случае потребуется (т-3)/2 блока умножения на константу по модулю. Необходимо также отслеживать, в первой или второй половине диапазона находится

операнд В. Если 0 В т (ув -0 ), то

работа устройства происходит при помощи существующих блоков умножения на константу по модулю (если , то один блок).

При

m + 1

В m (ув 11 ) .согласно соотношению.и результатам таблицы 1 необходимо произвести инверсию промежуточного результата операции по модулю уст ройства, выполняемую при помощи преобразователя кода. Изобразим в табл. 3 результат его работы.

Коммутация операнда В отмечена в таблице 1. Одновременно с сокращением блоков умножения на константу по модулю п роисходит и уменьшение числа блоков эле-, ментов И,.

Возможность достижения положительного эффекта от использования данного изобретения состоит в уменьшении количества оборудования ввиду уменьшения количества блоков умножения на константу по модулю.

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

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

+ I )-е дешифратора 6 (т - модуль)(,

m-1

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

входами элемента ИЛИ 8, выход которого соединен с вторым входом второго 9 блока элементов И, а через элемент НЕ ТО - с вторым входом первого блока 11 элементов И, первый вход которого соединен с выЯр- дом первого блока 4 элементов ИЛИ, а выход - с первым входом второго блока 1 элементов ИЛИ.второй вход которого сое- динен с выходом второго блока 9 элементов И, а выход является выходом 13 устройства, вход преобразователя 14 кода соединен с выходом первого блока 4 элементов ИЛИ, а выход- с.первым входом второго блока 9 элементов И.

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

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

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

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

-) по модулю. Через

открытый блок 2 элементов И группы соответствующее произведение А1 поступит на вход первого 4 блока элементов ИЛИ и с его выхода (сигнал на выходе элемента ИЛИ 8 отсутствует, ) на вход первого 11 блока элементов И, на второй вход которого по- ступает сигнал с выхода элемента НЕЮ и далее через второй блок 12 элементов ИЛИ на выход 13 устройства. При значение А (см. табл. 2) также равно нулю, что приводит к формированию нулевого произведи- ния.

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

работа устройства п роисходит, как и в предыдущем случае, но сигнал на выходе элемента ИЛИ 8 присутствует, поэтому промежуточный результат операции поступает на вход преобразователя 14 кода и значение результата модульного умножения через открытый второй 9 блок элемен50 5

0 5

.0

5

0

5 0

5

тов И и далее через второй 12 блок элементов ИЛИ поступает на выход 13 устройства.

Рассмотрим примеры конкретного выполнения операции при .

П р и м е р 1. Пусть необходимо определить результат модульного умножения для , (А, В-операнды).

На вход дешифратора 6 поступает число , на вход 1 .-чи., Сигнал на выходе элемента ИЛИ 8 отсутствует (). Сигнал с второго выхода дешифратора 6 поступает на второй вход первого элемента ИЛИ 7 группы, которая в этом случае состоит из двух элементов. С выхода первого элемента ИЛИ 7 сигнал поступает на первый вход блока умножения 2 на константу по модулю (см. табл. 2), на другой вход которого поступает . Результат операции А Bmod5 100 поступает через первый блок 4 элементов ИЛИ, первый блок 11 элементов И, второй блок 12 элементов ИЛИ на выход 13 устройства.,

П р и м е р 2. Пусть необходимо определить результат модульного умножения для , (А, В-операнды),

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

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

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

, приггДр- 2. m - р

Ф о р м у л а и з о б р е т е н и я Устройство для умножения чисел по модулю, содержащее дешифратор, группу блоков элементов И и первый блок элементов ИЛИ, группу блоков умножения на константу по модулю, причем вход второго сомножителя устройства соединен с первым входом первого блока элементов И группы и входами блоков умножения на константу по модулю группы, выход K-ro ((т-3)/2, т - значение модуля) блока умножения на

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

(f1 0-е т- 1

выходы дешифратора () соединены с соответствующими 1-ми

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

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

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

В

I

Т а б л и ц а 2

20

Таблица 3