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

 

Изобретение является усовершенствованием устройства по авт.св. № 1095178, относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов устройства. Цель изобретения - расширение функциональных возможностей за | счет реализации функции определения остатка числа по основанию, равному произведению двух оснований в системе остаточных классов. Цель достигается введением четырех элементов И, четырех групп элементов ИЛИ, четырех групп ключей, седьмого элемента ИЛИ, второго выходного регистра. Сущность изобретения состоит в однозначном соответствии между остатками числа С (А, А, .. .Ajj) по основаниям Р и Р и остатком этого числа по Ьснованию Р(Р-(Р., где ,n - основания системы остаточных классов, взаимно .простые числа), которое реализуется с помощью основного изобретения по основанию 1 ил., 5 табл. i (Л

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

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

РЕСПУБЛИК ((9(SU (lll

3 А2 щ) <: 06 F 7/72

;l- «(((9(",: ( 79f 4Ч 6,9 (1 . ..-.",, (9( 11ЙЬ "" - ; 9 ;" :- U((j3, ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А STOP tHOMY СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР

i (61) 1095178 (21) 4711759/24 (22) 27.06.89 (46) 07.05.91. Бюл. Ф 17 (72) В.А.Краснобаев, В.П.Ирхин, И.К.Костенко, И.В.Михеева и M.È.Öûáà (53) 681..325(088.8) (56) Авторское свидетельство СССР

Ф 1095178, кл. G 06 F 7/72, 1983. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ

ПО МОДУЛ1 ) (57) Изобретение является усовершенствованием устройства по авт.св.

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

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

Ф 1095178.

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

Сущность изобретения состоит в однозначном соответствии межпу остатками числа С А(, А,..., А по основаииям Р1 и Р и остатком этого числа

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

=(А<9 А 9 ...А ) по основаниям Р1 и Р и остатком этого числа по основанию P > Р (Р, где i=19п — основания

9 системы остаточных кляссов, взаимно .простые числа), которое реализуется с помощью основного изобретения по основанию P рР . 1 ил., 5 табл. по основанию Р1Р (где Р; — основание системы остаточных классов, взаимнопростые числа, i=1,п), которое реализуется с помощью основного изобретения по основанию Р ъР . (Взаимосвязь для Р =7, Р =11 изображена в табл. 1.

При условии применения иэвестI ного коммутатора табл.1 распадается на четыре таблицы (табл. 2 — 4), соответствующие четырем номерам квадратов арифметической таблицы, причем ф ф таблицы с пятой по восьмую соответствуют номерам квадратов с первого по четвертый соответственно. Величина операндов не кодируется, т.е. остатки Jlo ocHoBRNHM Р, P =l ° 11=-77, крят1647563 ные 7 или 11 необходимо выполнить анализом операндов с использованием свободных клеток табл. 1 для третьего и четвертого ее квадрантов.

В частности, если система остаточных классов состоит из двух оснований, =-о с помощью предлагаемого устройства реализуется перевод чисел из системы остаточных классов в позиционную сис- lð тему счисления.

Для кодирования результата операции необходимо иметь семь двоичных разрядов (2 -1=127р 77) .

На чертеже представлена Аункцио- 15 нальная схема устройства, где приняты следующие обозначения: 1 — первый входной регистр, 2 — вход первого операнда устройства, 3 — второи входной регистр, 4 — вход второго операнда 2р устройства, 5 — первый дешиАратор, б - второй дешифратор, 7 — первая группа элементов HPH 8- первая группа ключей, 9 — вторая группа ключей, l0 — шина логической единицы, 11 — 14 -25 с первого по четвертый элементы ИЛИ, 15 — сумматор по модулю два, 16 вторая группа элементов ИЛИ, 17 — коммутатор, 18 — первый элемент И, 19— второй элемент И, 20 — пятый элемент 3р

ИЛИ, 21 — шестой элемент ИЛИ, 22 первый выходной регистр, 23 — первый выход устройства, 24 - третий элег мент И, 25 — четвертый элемент И, 26 седьмой элемент И, 27 - восьмой элемент И, 28 — пятый элемент И, 29 шестой элемент И, 30 — 33 — с третьей по шестую группы элементов ИЛИ, 34

37 — c третьей по шестую группы ключей, 38 — седьмой элемент ИЛИ, 39 — 40 второй выходной регистр, 40 — второй выход устройства.

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

Входные операнды А< и А (остатки 45 по основанию Р ) по соответствующим входам 2 и 4 первого и второго операнда в двоичном коде поступают в соответствующие входные регистры 1 н 3 .и далее через соответствующие дешиАра-5р, тори 5 и 6 и соответствующую пару элементов КПИ 7 и 16 операнды ф и Ь. поступают на соответствующую пару ключей 9 и 8. Сигнал шины 1Р логической единицы открывает эту пару ключей 9 ц 8 и сигналы, соответствующие значениям 5 и р(, поступают соответственно на первйй и второй входы коммутатора !7. Если $g, тогда на нулевом выходе сумматора 15 по модулю два присутствует сигнал, который поступает на первые входы элементов И 18 и ?5. Если на выходной управляющей шине коммутатора 17 отсутствует сигнал, то элемент И l8 открыт, и сигнал нулевого выхода сумматора 15 по модулю два через элемент ИЛИ 20 поступает на нулевой вход первого выходного регистра 22.

Если на выходную управляющую шину коМиутатора 17 поступает сигнал, то элемент И 25 открыт и сигнал первого выхода сумматора 15 по модулю два через элемент ИЛИ 21 поступает на единичный вход первого выходного регистра 22. Когда g>,у, то сигнал едиz ничного выхода поступает на первые входы элементов И 19 и 24 . Если на выходной управляющей шине коммутатора 17 отсутствует сигнал, то элемент И 19 открыт и сигнал единичного выхода сумматора 15 по модулю два через элемент ИЛИ 21 поступает на единичный вход первого выходного регист- ра 22. Если на выходной управляющей шине коммутатора 17 присутствует сигнал, то элемент И 24 открыт, и сигнал с единичного выхода 15 по модулю два через элемент ИЛИ 2О поступает на нулевой вход первого выходного регистра 22. Одновременно результат опеРации р ф (mod)P с выхода коммутатора 11 поступает на соответствующий вход первого выходного регистра 22.

Таким образом, в первом выходном регистре 22 содержится результат операции A(modP<) в КТУ.

Г

При рассмотрении работы устройства, реализующего Аункцию определения остатка числа по основанию, равному произведению двух оснований в системе остаточных классов, отметим, что группы элементов ИЛИ (30-33) с третьей по шестую осуществляет преобразование выходного сигнала элемента И коммутатора 17 в соответствующие двоичные представление результата для данного квадрата табл. 1. Определение соответствующего квадранта производится элементами И (28, 2О, 26, 27) с пятого по восьмой. Выходной сигнал с одного иэ этих элементов производит открытие соответствующей группы ключей (33-37) с третьей по шестую. 3s.eìåíò И 28 реализует выбор второго квадранта, И 29 первого, И 26 — третьего и И 27 четвертого.

5 164 756

Входные операнды А < и A 2 (остатки по основанию соответственно P < и Р2)

1 по соответствующим входам 2 и 4

1 первого и второго операнда в двоичном коде поступают в соответствующие входные регистры 1 и 3, далее через соответствующие дешифраторы 5 и 6 через соответствующую пару элементов ИЛИ 7 и 16 операнды g,è g2 поступают на 10 соответствующую пару ключей 9 и 8.

Сигнал шины 10 логической единицы открывает эту пару ключей 9 и 8 и сигналы, соответствующие значениям ()(, и ф, поступают соответственно на пер-15

Э вый и второй входы коммутатора 17.

Далее элементами И (28, 29, 26, 27) с пятого по восьмой производится выбор соответствующего квадранта табл . 1, в зависимости от того, в ка- 20 ком. диапазоне находятся операнды 0 и ф . (Если О А (А ) — — — то curPg-1

2 2 2 нал поступает с выхода И 29, обозначая выбор второго квадранта). Сигнал выбора квадранта поступает на управляющие входы соответствующей группы ключей (33-37) с третьей по шестую.

Выходной сигнал коммутатора 17, соответствующий результату операции, пре- 30, образованный соответствующей группой элементов ИЛИ (30-33) с третьей по шестую в двоичное представление, поступает на информационные входы группы ключей (33-37) и с выхода одной из 35 них (при втором квадранте выбирается четвертая группа ключей 34). Через седьмой элемент ИЛИ 38 результат поступает на вход второго выходного регистра 39, с выхода которого — на 4О второй выход 40 устройства.

Рассмотрим пример конкретного выполнения операции определения остатка числа по основанию, равному произведению двух оснований в системе оста-. 5 точных классов. Пусть Р =7, Р =11.

Необходимо определить остаток числа по основанию 77, если остаток числа по основанию Р равен 3, а остаток по основанию Р2 равен 4. В этом слу- 50 чае реализуется второй квадрант, так как О А1(А2) < 5, т.е. сигнал на выбор группы ключей (33-37) поступает с шестого элемента И 29.

Входные операнды А =0011 и А =0100

1 2 поступают через соответствующие weменты устройства на третий вход пер,— вой группы входов коммутатора 17 и

3 6 на четвертый вход второй группы вхо.— дов коммутатора 17. Сигнал с выхода

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

l7 в двоичные представления

00 1110112=591 результата операции согласно табл.6. Результат операции через четвертую группу 35 ключей, седьмой 38 элемент ИЛИ поступает во второй выходной 39 регистр. Это и будет результат операции. ф о р мул а изобретения

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

ИЛИ соединен с первыми входами пятого и шестого элементов И, выход третьего элемента ИЛИ соединен с вторыми входами шестого и восьмого элементов И, выход четвертого элемента

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

ИЛИ третьей, четвертой, пятой и шес той лпупп.

1647563

Таблица 1

А

2 3. 4 5 6 7 8 9 19

71 50

16 72

38 . .17

60 39

5 61

27 - 6

Таблица2.

Таблица 3

Г(Г Ч

Ат

2. 3 4 5

10 9 -8 7 6

8 29 50

30 51 72

52 73 17

74 18 39

19 40 61

1 43 64

2 65 9

3 10 31

4 32 53

5 54 75

Т а б л и ц а 5

Таблица4

ЗО А

Г(А

1 2 3 4 5

М ф

Ш 9 8 7 Ь

35 9 .8

6 76 20 41 — 62 6

6 34 13 69 48 27

Z

4

6 1

23

67

12

57

24

46

68

36 15

58 37

3. 59

25 - 4

4? 26

69 48

3. 4 5

29 8

51 30

73 52

18 74

40 19

62 41

57 36

23 2 58

45 24 . 3

65 46 25

12 68 47

64 43 .

9 65

31 10

53 32

75 54

20 76

15 71

37 16

59 38

4 60

26 5

1647563

Составитель Е.Иур зина

Техред М.Дидык Корректор Л.Патай.Редактор В.Бугренкова

Заказ 1400 Тирам 405 Подписное

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

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

Производственно-нэдательский комбинат "Патент", r.ужгород, ул. Гагарина,101