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

 

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

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

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

РЕСПУБЛИК

„.Я0„„163,(51)5 G 06 F 7/72

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

К АВТОРСКОМ .Ф СВИДЕТЕЛЬСТВУ

3Z

:Ь

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

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

ПРИ ГКНТ СССР (21) 46 786 74/24 (22) 11.04.89 (46) 23,03.91. Вюп. 11 - 11 (72) О,Н,Фоменко, В.А. Краснобаев, В.П.Ирхин, А.А. Журавлев, ; С.И. Куцый, А.А,Леваков и С.В.Иванов (53) 681. 325 (088. 8)

, (56) Авторское свидетельство СССР 11 1120325е кл. G 06 F 7/72р 1983.

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

У 1532923, кл. G 06 F 7/72, 1988.

2 (54) УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИ;" ТАНИЯ ЧИСЕЛ ПО ИОДУЛ10 (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в вып слительных машинах и устройствах, функционирующих в системе остаточных классов.

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

1636844

1

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

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

Устройство содержит первый информационный вход 1 устройства, первый дешифратор 2, второй информационный . вход 3 устройства, первый блок 4 эле- 30 ментов И, вычитатель 5, вход 6 задания модуля устройства, второй блок 7 элементов И, вход 8 задания вычитания устройства, первый блок 9 элементов

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

18, второй элемент И 19, первый зле;40 мент ИЛИ 20, тактовый вход 21 устройства, элемент НЕ 22, выход 23 устройства, первый шифратор 24, группу эле4 четвертый блок 27 элементов И,, пятый блок 28 элементов И, второй i блок 29 элементов ИЛИ, вход 30 задания сложения устройства, третий элемент

ИЛИ 31, вход 32 задания умножения устройства, второй элемент ИЛИ 33, 50 значение (m""Â) через открытый второй блок 7 элементов И, блок 9 элементов ИЛИ поступает на второй дешифратор -!

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

14 и второй 15 элементы запрета, Рассмотрим работу устройства в трех режимах. При проведении операции модульного сложения; (A+8)modm в двоичном коде на вход 1 поступает

55 операнд А, на вход 3 — операнд В, который также поступает на вход вычита- теля 5 (ao модулю m), на выходе котокольцевой сдвигающий регистр 17, пер вый 18 и второй 19 элементы И, первый элемент HJM 20, элемент НЕ 22, первый шифратор 24 и группу элементов ИЛИ 25, второго шифратора 26, второго 33 и третьего 31 элементов

: ИЛИ 33 и 31, второго бпока 29 элементов ИЛИ, четвертого 27 и пятого

28 блоков элементов И. 4 табл., 1 ил. рого получают значение (m-В) Сигнал с входа 30 проходит через элемент

ИЛИ 33 и открывает первый блок 4 элементов И, через который и через первый блок 9 элементов ИЛИ операнд В поступает на вход второго дешифратора

10. С выхода второго дешифратора 10 операнд В в унитарном коде поступает на первую группу входов первого шифратора 24, на вторую группу входов которого поступает через первый дешифратор 2 операнд А. В зависимости от соотношения операндов А и В на выходах элементов ИЛИ 25 группы образуется двоичное число, соответствующее количеству сдвигов регистра 11 ° а на выходе элемента ИЛИ 20 образуется сигнал, если направление сдвига правое (т.к. сигнал на выходе элемента ИЛИ

31 присутствует, то открыт четвертый блок 27 элементов И) . Сигнал с выхода элемента ИЛИ 20 поступает на первый вход элемента И 18, а если сигнал отсутствует, то открывается элемент И 19, обеспечивая левое направление сдвига. С входа 21 на входы открытых; ,элементов 14 и 15 запрета поступают им- 3 пульсы. При совпадении состояний счетчика 12 и приемного регистра 11 схема 13 сравнения выдает сигнал, который закрывает элементы 14 и 15 запрета и открывает блок 16 элементов И, через который значение группы двоичных разрядов регистра 17 (результат операции модульного. сложеция) поступает на выход 23 устройства.

Пусть необходимо определить результат (А-8)modm. В этом случае сигнал с входа 8 поступает на второй блок 7 элементов И. С выхода.вычитателя 5

4 6 элементов ИЛИ поступает на второй дешифратор 10. С выхода второго дешифратора 10 поступает на третий вход первой группы входов шифратора 24 ° В приемном регистре 1 будет записано число "01" согласно табл. 2 (сигналом с выхода ИЛИ 31 открыт четвертый блок

27 элементов И). Сигнал с выхода элемента ИЛИ 20 не поступает, а на элемент И. 19 поступает сигнал. Импульсы через открытые элементы 14 и 15 запрета поступают на регистр 17 и на счетчик 12. В момент совпадения состояния регистра 11 и счетчика 12 (в счетчике

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

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

Состояние регистра 17 будет следующее: о- z-o-z-z-o-o

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

Пример 2. A=O, 8=2, Необходи мо определить (А-В)modm. В этом случае на первый вход второй группы первого шифратора 24 поступает сигнал. На шестой вход первой группы входов первого шифратора 24 также поступает. сигнал (7-2=5) .. В приемном регистре

11 будет записано число "00". Сигнал с выхода элемента ИЛИ 20 не поступает, а схема 13 сравнения в момент включения устройства вырабатывает сигнал, закрывающий элементы 14 и 15 запре та и открыв ающий бло к 16 элементов

И, (сдвиг не происходит) . Состояние регистра 17 будет следующее:

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

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

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

Исходное состояние регистра 17:

1-0- 1-1-0 — 0-0. Первые три 20 двоичных разряда соответствуют числу

"5". Число "3" соответствует сдвигу регистра 17 влево на один двоичный разряд. "2" — вправо на один двоичный разряд и т.д. Составим таблицу для ре-25 ализ ации операции модульного сложения, В табл. 1 отражены результаты операции модульного сложения.

В табл. 2 для. построения шифратора

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

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

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

I дов и направления сдвига., Следовательно, группа элементов

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

Пример 1. А=О, В=2. Необходимо определить {А+В) modm, Первый операнд А=О поступает на первый дешифра- 55 тор 2, с входа которого поступает на первый вход второй группы входов шифратор а 24. Опер анд В через первый блок 4 элементов И и первый блок 9

I — Π— I — I — Π— Π— О

Содержимое первых трех двоичных разрядов регистра 17 представляет результат операции модульного вычитания, Пример 3. A=2, 8=3. Необходимо определить (А В) modm. Первый операнд А=2 поступает на первый дешифратор 2, с выхода которого поступает на третий вход второй группы входов второго шифратора 26, Операнд В через четвертый блок 4 элементов И (сигнал на выходе ИЛИ 33 присутствует) и первый блок 9 элементов ИЛИ через второй дешифратор 10 поступает на четвертый вход.первой группы входов второго шифратора 26. В приемном регистре 11 будет записано число "10" сог1б Зб 844 ласно табл. 4 (сигнал присутствует на втором,,входе пятого блока 28 эле" ментов И) .

Сигнал с. выхода элемента ИЛИ 20 поступает на вход элемента И 18. Им5 пульсы через открытые элементы 14 и

15 запрета поступают на регистр 17 и на счетчик 12. Б момент совпадения состояния регистра Н и счетчика 12 (в счетчике содержится значение "10".) схема 13 сравнения формирует сигнал, закрывающий элементы 14 и 15 запрета и открывающий блок 1б элементов И. Сос- . тояние регистра 17 будет следу|сщее:

CI I=9 — 0 — Π— т — 0

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

МОДУЛЬНОГО p" ÌÍÎÆÅßÈß, формулаизобретения

Устройство для сложения и вычитания чисел по модулю, содержашее пер- 5 вый и втоРой ДешифРатОРы, вычитательр приемный регистр, схему сравнения, счетчик р кольцевой сдвигающий per I;;C Tp пеРвый шпфРатОРр с пеРвого по тует.. и блоки элементоь Н первый блок элемен-3g тов ИЛИ, первый и второй, элементы за- . прета, первый и второй элементы И, группу элементов ИЖр первый элемент

KIH и элемент 112, причем первый информационнлй вход устройства соединен с

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

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

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

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

1636844

Т аблица 1

А 0 1 . 2 3 4 5

2 3 4

3 4 5

4 5 6

5 6 0

6 0 l

0 1 2

2 3

0 0 1

1 2

2 2 3

3 3 4

4 4 5

5 5 6 б 6 0

Р

Таблица 2

0 1- 2 3 4 5

3- 22- 1I- 1+

1+ 3+

3+ 0 .0 2+

2+ 311+

3+

2+

32Таблица 3

0 1 2 3 4 5 б

0 0 0

2 0 1

2 0 2

3 0 3

4 0 4

5 0 5

6 0 6

0 0 0

2 3 4

4 б 1 б 2 5 ! 5 2

3 l 6

5 4 3

Таблиц а 4

0 ) 2 3 4 5 6 !

3- Э2- 11- 3+

1+ 2+

3+ 2О, 1+

2+ 0

0 3° l 32 33 34 35 3б 33- 33+ 0

2- 1+

0 21- 2+

2+ 3+

1+ 1"

Составитель В. Клюев

Техред Л. Сердюкова

Корректор М. Самборская

РеДактор В. Бугренкова

Заказ 816 Тираж 399 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r.Óæãîðîä, ул. Гагарина,101

1

Э

5

3l+

2+

1 0

23+

1+

3+

2+

3213+

2+

3211+

5 6

6 0

0 1

1 2

2 3

3 4

4 5

0 22+ 33- 22- 1-, 1+

1+ 3+

3+ 0

0 0

5 6

3 5

1 4

6 3

4 2

32+

3+

1+

12