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

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

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

Сущность изобретения состоит в од нозначном соответствии меяду остатками числа С А{, AJ,

и

,, Aft по основало основанию Р|Рз. (гДе р( основание системы остаточных классов, взаим- нопростые числа, ,п), которое реализуется с помощью основного изобре- (тения по основанию

Взаимосвязь для Р 7, PgHI изображена в табл. 1.

При условии применения известного коммутатора табл . 1 распадается на четыре таблицы (табл. 2-4), соответствующие четырем номерам квадратов арифметической таблицы, причем таблицы с пятой по восьмую соответствуют номерам квадратов с первого по четвертый соответственно. Величина операндов не кодируется, т.е. остатки по основанию 1 1-77, кратю

10

30

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

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

На чертеже представлена функцио- ff нальная схема устройства, где приняты следующие обозначения: 1 - первый входной регистр, 2 - вход первого операнда устройства, 3 - второй входной регистр, 4 - вход второго операнда 20 устройства, 5 - первый дешифратор, 6 - второй дешифратор, 7 - первая группа элементов ИЛИ, 8- первая группа ключей, 9 - вторая группа ключей, 10 - шина логической единицы, 11-14 -25 с первого по четвертый элементы ИЛИ, 15 - сумматор по модулю два, 16 - вторая группа элементов ИЛИ, 17 - коммутатор, 18 - первый элемент И, 19 - второй элемент И, 20 - пятый элемент ИЛИ, 21 - шестой элемент ИЛИ, 22 - первый выходной регистр, 23 - первый выход устройства, 24 - третий эле-1 мент И, 25 - четвертый элемент И, 26 седьмой Элемент И„ 27 - восьмой элемент И, 28 - пятый элемент И, 29 - шестой элемент И, 30 - 33 - с третьей по шестую группы элементов ИЛИ, 34 - 37 - с третьей по шестую группы ключей, 38 - седьмой элемент ИЛИ, 39 - второй выходной регистр, 40 - второй выход устройства.

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

Входные операнды А2 и А2 (остатки 45 по основанию Р,,) по соответствующим входам 2 и 4 первого и второго операнда в двоичном коде поступают в соответствующие входные регистры 1 и 3 и далее через соответствующие дешифра 50 торы 5 и 6 и соответствующую пару элементов ИЛИ 7 и 16 операнды У2и &/J поступают на соответствующую пару ключей 9 и 8. Сигнал шины 10 логической единицы открывает эту пару ключей 9 и 8 и сигналы, соответствующие эна- чениям и , поступают соответственно на первый и второй входы коммутатора 17. Если jfjf2 y,yЈ „ тогда

35

40

55

0

0

f 0 5

45 50 35

40

55

на нулевом выходе сумматора 15 по модулю два присутствует сигнал, который поступает на первые входы элементов И 18 и 25. Если на выходной управляющей шине коммутатора 17 отсутствует сигнал, то элемент И 18 открыт, и сигнал нулевого выхода сумматора 15 по модулю два через элемент ИЛИ 20 поступает на нулевой вход первого выходного регистра 22. Если на выходную управляющую шину коммутатора 17 поступает сигнал, то элемент И 25 открыт и сигнал первого выхода сумматора 15 по модулю два через элемент ИЛИ 21 поступает на единичный вход первого выходного регистра 22. Когда jye ( то сигнал единичного выхода поступает на первые входы элементов И 19 и 24, Если на выходной управляющей шине коммутатора 17 отсутствует сигнал, то элемент И 19 открыт и сигнал единичного выхода сумматора 15 по модулю два через элемент ИЛИ 21 поступает на единичный вход первого выходного регистра 22. Если на выходной управляющей шине коммутатора 17 присутствует сиг- пал, то элемент И 24 открыт, и сигнал с единичного выхода 15 по модулю два через элемент ИЛИ 20 поступает на нулевой вход первого выходного регистра 22. Одновременно результат операции р 0(rood)P с выхода коммутатора 11 поступает на соответствующий вход первого выходного регистра 22. Таким образом, в первом выходном регистре 22 содержится результат операции A2A2(modPz) в КТУ.

При рассмотрении работы устройства, реализующего функцию определения остатка числа по основанию, равному произведению двух оснований в системе остаточных классов, отметим, что группы элементов ИЛИ (30-33) с третьей по шестую осуществляет преобразование выходного сигнала элемента И коммутатора I7 в соответствующие двоичные представление результата для данного квадрата табл. 1, Определение соответствующего квадранта производится элементами И (28, 20, 26, 27) с пятого по восьмой. Выходной сигнал с одного из этих элементов производит открытие соответствующей группы ключей (33-37) с третьей по шестую. Элемент И 28 реализует выбор второго квадранта, И 29 первогоs И 26 - третьего и И 27 - четвертого.

5164

Входные операнды А и А2 (остатки по основанию соответственно Р( и Р ) По соответствующим входам 2 и 4 первого и второго операнда в двоичном коде поступают в соответствующие входные регистры 1 и 3, далее через соответствующие дешифраторы 5 и 6 через соответствующую пару элементов ИЛИ 7 и 16 операнды о( и поступают на соответствующую пару ключей 9 и 8. Сигнал шины 10 логической единицы открывает эту пару ключей 9 и 8 и сигналы, соответствующие значениям ф, и 0Л, поступают соответственно на первый и второй входы коммутатора 17. Далее элементами И (28, 29, 26, 27) с пятого по восьмой производится выбор соответствующего квадранта табл. 1, в зависимости от того, в каком диапазоне находятся операнды &f

и

Р2.-1

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

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

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

Входные операнды А., 0011 и А 0100 поступают через соответствующие элементы устройства на третий вход первой группы входов коммутатора 17 и

36

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

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

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

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

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

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

Таблица 1

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