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

вэ±

СЕ) 00 (35 00

Let

11

кольцевого сдвигающего регистра 17 для операции умножения путем введения в устройство, содержащее первый 2 и второй 10 дешифраторы, с первого по третий блоки 4, 7 и 16 элементов И, вычитатель 5, первый блок 9 элементов ИЛИ, приемный регистр 11, счетчик 12, схему 13 сравнения, первый 14 и второй 15 элементы запрета,

кольцевой сдвигающий регистр 17, первый 18 и второй 19 элементы И, пер, вый элемент ИЛИ 20,- элемент НЕ 22, первый шифратор 24 и группу элементов ИЛИ 25, второго шифратора 26, второго 33 и третьего 31 элементов : ИЛИ 33 и 31, второго блока 29 элементов ИЛИ, четвертого 27 и пятого

10 г- 6локов ЭЛЈментов И. 4 табл., 1 ил.

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

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

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

На чертеже представлена схема устройства для сложения и вычитания чисел по модулю.

Устройство содержит первый информационный вход 1 устройства, первый дешифратор 2, втброй информационный вход 3 устройства, первый блок 4 элементов И, вычитатель 5, вход 6 задания модуля устройства, второй блок 7 элементов И, вход 8 задания вычитания устройства, первый блок 9 элементов ИЛИ, второй дешифратор 10, приемный регистр 11, счетчик 12, схему 13 срав нения, первый элемент 14 запрета, второй элемент 15 запрета, третий блок 16 элементов И, кольцевой сдвигающий регистр 7, первый элемент И 18, второй элемент И 19, первый элемент ИЛИ 20, тактовый вход 21 устройства, элемент НЕ 22, выход 23 устройства, первый шифратор 24, группу элементов ИЛИ 25, второй четвертый блок 27

пятый блок 28 элементов И, второй i 29 элементов ИЛИ, вход 30 задания сложения устройства, третий элемент ИЛИ 31, вход 32 задания умножения устройства, второй элемент ИЛИ 33.

шифратор 26-р- элементов И9 ,

Рассмотрим работу устройства в трех режимах. При проэедении операции модульного, сложения, (A+B)modm в двоичнрм коде на вход 1 поступает операнд А, на вход 3 - операнд В, который также поступает на вход вычита- теля 5 (по модулю т), на выходе кото5

5

0

ч

Q

0

5

0

рого получают значение (m-В). Сигнал с входа 30 проходит через элемент ИЛИ 33 и открывает первый блок 4 эле- ментов И, через который и через первый блок 9 элементов ИЛИ операнд В поступает на вход второго дешифратора 10, С выхода второго дешифратора 10 операнд В в унитарном коде поступает на первую группу входов первого шифратора 24, на вторую группу входов которого поступает через первый дешифратор 2 операнд А. В зависимости от соотношения операндов А и В на выходах элементов ИЛИ 25 группы образуется двоичное число, соответствующее количеству сдвигов регистра 17, а на выходе элемента ИЛИ 20 образуется сигнал, если направление сдвига правое (т.к. сигнал на выходе элемента ИЛИ 31 присутствует, то открыт четвертый блок 27 элементов И). Сигнал с выхода элемента ИЛИ 20 поступает на первый вход элемента И 18, а если сигнал отсутствует, то открывается элемент И 19, обеспечивая левое направление сдвига. С входа 21 на входы открытыхч Элементов 14 и 15 запрета поступают им- J пульсы. При совпадении состояний счетчика 12 и приемного регистра 11 схема 13 сравнения выдает сигнал, который закрывает элементы 14 и 15 запрета и открывает блок 16 элементов И, через который значение группы двоичных разрядов регистра 17 (результат операции модульного сложения) поступает на выход 23 устройства.

Пусть необходимо определить результат (A-B)modm. В этом случае сигнал с входа 8 поступает на второй блок 7 элементов И. С выхода вычитателя 5 значение (т-8) через открытый второй блок 7 элементов И, блок 9 элементов (ИЛИ поступает на второй дешифратор -1 10. Дальнейшая работа устройства ана

логична определению результата операции модульного сложения.

Если определяют результат (А tB)modm, то присутствует сигнал на входе 30, который открывает первый блок 4 элементов И и пятый блок 28 элементов И. В этом случае на входы элементов ИЛИ 25 группы и первого элемента ИЛИ 20 информация поступает с выходов второго шифратора 26 через пятый блок 28 элементов И и второй блЗк 29 элементов ИЛИ. Дальнейшая работа аналогична определению результата операции модульного сложения.

Рассмотрим примеры конкретного выполнения операции модульного сложения вычитания и умножения для .

Исходное состояние регистра 17: 1-0- 1- 1-0-0-0. Первые три двоичных разряда соответствуют числу 5й. Число 3 соответствует сдвигу регистра 17 влево на один двоичный разряд. 2 - вправо на один двоичный

разряд и т.д. Составим таблицу для ре-25 ментов И поступает на выход 23. Это

ализации операции модульного сложения, В табл. 1 отражены результаты операции модульного сложения.

В табл. 2 для построения шифратора 24 отражено необходимое количество тактов сдвига для каждой пары операн- . дов А и В и направление сдвига, Сдвиг влево соответствует положительному направлению сдвига и отражен в табл. 2 знаком +.

Составим таблицу для реализации операции модульного умножения. В табл.3 отражены результаты операции модульного умножения.

В табл. 4 для построения шифратора 26 отражено необходимое количество тактов сдвига для каждой пары операн- дов и направления сдвига.,

Следовательно, группа элементов ИЛИ 25, выполняющая функцию шифратора, состоит из двух элементов, которые формируют четыре числа: 00, 01,, 11. В элементе ИЛИ-20 объединяются выходы шифратора 24, либо шифратора 26, которые поме.че- ны знаком - соответственно в . . табл. 2 и 4.

Пример 1. , . Необходимо определить (A+B)modm. Первый опе,есть результат операции.

Пример 2. , , Необходи- мо определить (A-Sjmodm. В этом слу- чае на первый вход второй группы пер- 30 вого шифратора 24 поступает сигнал. На шестой вход первой группы входов первого шифратора 24 также поступает- сигнал () ./ В приемном регистре 11 будет записано число 00. Сигнал с выхода элемента ИЛИ 20 не поступает, а схема 13 сравнения в момент . включения устройства вырабатывает сигнал, закрывающий элементы 14 и 15 запрета и открывающий блок 16 элементов И, (сдвиг не происходит). Состояние регистра 17 будет следующее:

35

40

I

.L

I-0-I-I-0-0-0

3

Содержимое первых трех двоичных 45 разрядов регистра 17 представляет результат операции модульного вычитания.

ПримерЗ. , . Необходимо определить (AXB)modm. Первый операнд поступает на первый дешифра- 50 тор 2, с выхода которого поступает на третий вход второй группы входов второго шифратора 26, Операнд В через четвертый блок 4 элементов И (сигнал на выходе ИЛИ 33 присутствует) ранд поступает на первый дешифра- 55 и первый блок 9 элементов ИЛИ через тор 2, с входа которого поступает навторой дешифратор 10 поступает на четпервый вход второй группы входов шиф- вертый вход .первой группы входов вто- ратора 24. Операнд В через первый .рого шифратора 26. В приемном регистблок 4 элементов И и первый блок 9ре 11 будет записано число 10 сог0

0

элементов ИЛИ поступает на второй дешифратор 10. С выхода второго дешифратора 10 поступает на третий вход первой группы входов шифратора 24. В приемном регистре I1 будет записано число 01 согласно табл. 2 (сигналом с выхода ИЛИ 31 открыт четвертый блок 27 элементов И). Сигнал с выхода элемента ИЛИ 20 не поступает, а на(элемент И 19 поступает сигнал. Импульсы через открытые элементы 14 и 15 запрета поступают на регистр 17 и на счетчик 12. В момент совпадения состояния 5 регистра 11 и счетчика 12 (в счетчике

12содержится значение 01) схема

13сравнения, формирует сигнал, закрывающий элементы 14 и 15 запрета и открывающий третий блок 16 элементов И. Состояние регистра 17 будет следукщее:

с1

0-1-0

I - I - 0 - От

Содержание первых трех розрядов регистра 17 через третий блок 16 эле,есть результат операции.

Пример 2. , , Необходи- мо определить (A-Sjmodm. В этом слу- чае на первый вход второй группы пер- вого шифратора 24 поступает сигнал. На шестой вход первой группы входов первого шифратора 24 также поступает- сигнал () ./ В приемном регистре 11 будет записано число 00. Сигнал с выхода элемента ИЛИ 20 не поступает, а схема 13 сравнения в момент . включения устройства вырабатывает сигнал, закрывающий элементы 14 и 15 запрета и открывающий блок 16 элементов И, (сдвиг не происходит). Состояние регистра 17 будет следующее:

I

.L

I-0-I-I-0-0-0

3

Содержимое первых трех двоичных разрядов регистра 17 представляет результат операции модульного вычитания.

ПримерЗ. , . Необходимо определить (AXB)modm. Первый операнд поступает на первый дешифра- тор 2, с выхода которого поступает на третий вход второй группы входов второго шифратора 26, Операнд В через четвертый блок 4 элементов И (сигласно табл. 4 (сигнал присутствует на втором входе пятого блока 28 элементов И).

Сигнал с выхода элемента ИЛИ 20 поступает на вход элемента И 18, Импульсы через открытые элементы 14 и 15 запрета поступают на регистр 17 и на счетчик 12, В момент совпадения состояния регистра 11 и счетчика 32 (в,счетчике содержится значение 10) схема 13 сравнения формирует сигнал, закрывающий элементы 14 и 15 запретна и открывающий блок 16 элементов И. Состояние регистра 17 будет следующее:

QJ

1-0-0-0

о

D

Содержание первых трех разрядов регистра 17 и есть результат операции JQ модульного умножения.

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

Устройство для сложения и вычитания чисел по модулю, содержащее первый и второй дешифраторы, вычитатель, приемный регистрs схему сравнения, счетчик, кольцевой сдвигающий регистр, иервъЗ-- шифратор,} с первого по трети блоки элементов И, первый блок элементов ИЛИ, первый и второй, элемента запрета, первый и второй элементы И, группу элементов ИЛИ, первый элемент ИЛИ и элемент 3$ причем первый информационный вход устройства соединен с входом первого дешифратора, второй информационный вход устройства соединен с первым входом первого блока элементов И и с входом вычитаемого вычита- теля, вход уменьшаемого и выход которого соединены соответственно с входом задания модуля устройства и с первым входом второго блока элементов И, вход задания вычитания устройства соединен с вторым входом второго блока элементов И, выходы первого и второго блоков элементов И соединены соответственно с первым и вторым входами первого блока элементов ИЛИ, выход которого соединен с входом второго дешифратора, выходы приемного регистра и ечетчика соединены соответственно с первым и вторым входами схемы сравнения, выход которой соединен с управляющими входами первого.и второго элементов запрета, с первым входом третьего блока элементов И, входы разрядов второго входа которого соединены соответственно с выходами

0

5

Q

5

0

5

0

5

0

5

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

163684410

Таблица 1