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

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

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

Недостатком устройства являются низкие функциональные возможности.

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

Нед остатком это го устройства являются низкие функциональные возможности.

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

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

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

ся

о

,Ј

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

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

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

0 которого соединен с входом элемента НЕ.

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

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

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

5 18, тактовый вход 19 устройства, элемент НЕ 20, выход 21 устройства, матрицу 22 элементов И, первый шифратор 23, четвертый блок 24 элементов И, пятый блок 25 элементов И, второй блок 26 элементов ИЛИ, вход

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

5 шифратор 34, выход 35 сигнала ошибки устройства, третий элемент И 36, третий элемент ИЛИ 37.

Первый информационный вход 1 устройства соединен с первым входом первого дешифратора 2, второй информационный

вход 3 устройства соединен с первым входом первого блока 4 элементов И, с входом вычитаемого вычитателя 5, вход уменьшаемого и выход которого соединены соответственно с входом 6 задания модуля устройства и с первым входом второго блока 7 элементов И. выходы первого 4 и второго 7 блоков элементов И соединены соответственно с первым и вторым входами первого блока 8 элементов ИЛИ, выход которого соединен с входом второго дешифратора 9, выходы приемного регистра 10 и счетчика 11 соединены соответственно с первым и вторым входами схемы 12 сравнения, выход которой соединен с управляющими входами первого 13 и второго 14 элементов запрета, с первым входом третьего блока 15 элементов И, входы разрядов второго входа которого соединены соответственно с выходами (Iog2m И), (т - величина модуля) младших разрядов кольцевого сдвигающего регистра 6, входы разрешения сдвига вправо и влево которого соединены соответственно с выходами первого 17 и второго 18 элементов И, тактовый вход 19 устройства соединен с информационными входами первого 13 и второго 14 элементов запрета, выход элемента 14 запрета соединен со счетным входом счетчика 11, первый вход первого элемента И 17 через элемент НЕ 20 соединен с первым входом второго элемента И 18, второй вход которого объединен с вторым входом первого элемента И 17 и соединен с выходом элемента 13 запрета, выход третьего блока 15 элементов И является информационным выходом

21устройства, выходы дешифратора 2 соединены соответственно с первыми входами элементов И строк матрицы 22, выходы дешифратора 9 соединены соответственно с вторыми входами элементов И столбцов матрицы 22, выходы элементов И матрицы

22соединены соответственно с входами первого шифратора 23, выходы разрядов, кроме младшего которого соединены соответственно с входами разрядов первого входа четвертого блока 24 элементов И, выходы четвертого 24 и пятого 25 блоков элементов И соединены соответственно с первым и вторым входами второго блока 26 элементов ИЛИ, входы 27 и 28 задания сложения и вычитания устройства соединены соответственное первым и вторым входами первого 29 элемента ИЛИ, выход которого соединен с вторым входом блока 24 элементов И, вход 27 задания сложения устройства соединен с первым входом второго 30 элемента ИЛИ, выход которого соединен с вторым входом блока 4 элементов И.

Вход 31 задания деления устройства сп единебн с вторым входом 30 элемента ИЛИ с первыми входами четвертого 32 и пятого 33 элементов И и с первым входом блока 25 5 входы разрядов второго входа которого со единены соответственно с выходами разрядов, кроме младшего, выхода второго 34 шифратора, входы которого соединены соответственно с вйхбдами элементов И

10 матрицы 22, Младший выход дешифратора 9 соединен с вторым входом элемента И 33, выход которого является выходом 35 сигнала ошибки устройства, выход блока 26 элементов ИЛИ соединен с входом приемного

15 регистра 10, выход элемента ИЛИ 29 соединен с первым входом третьего элемента И 36, выходы младших разрядов выходов первого 23 и второго 34 шифраторов соединены соответственное вторыми ходам и третьего

20 36 и четвертого 32 элементов И, выходы которых соединены с оответственно с первым и вторым входами третьего элемента ИЛИ 37, выход которого соединен с входом элемента НЕ 20.

5 Устройство работает в трех режимах При проведении операции модульного сложения (А + Bjmodm в двоичном коде на вход 1 поступает операнд А, на вход 3 - операнд В, который также поступает на вход вычита0 теля 5 (по модулю т), на выходе которого получим значение (т-В). Сигнал с входа 27 проходит через элемент И 30 и открывает блок 4 элементов И, через который и блок 8 элементов ИЛИ операнд В поступает на

5 вход дешифратора 9. С выхода дешифратора 9 операнд В в унитарном коде поступает на вторые входы элементов И столбцов матрицы 22, на первые входы элементов И строк матрицы 22 поступает через дешифра0 тор 2 операнд А. В зависимости от соотно- шения операндов А и В на выходе шифратора 23 образуется двоичное число, соответствующее количеству сдвигов регистра 16, а на выходе элемента И 36 образу5 ется сигнал, если направление сдвига правое (так как сигнал на выходе элемента ИЛИ 29 присутствует). Этот сигнал поступает на первый вход элемента И 17, а если сигнал отсутствует, то открывается элемент

0 И 18, обеспечивая левое направление сдвига. С выхода шифратора 23 через элемент И 24 и ИЛИ 26 число сдвигов в двоичном коде поступает в приемный регистр 10. С входа 19 на входы открытых элементов 13 и 14

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

разрядов (результат операции модульного сложения)-поступает на выход 21 устройства.

Пусть необходимо определить результат (А - B)mod m. В этом случае сигнал с входа 28 поступает на блок 7 элементов И, С выхода вычитателя 5 значение (т - В) через открытый блок 7 элементов И, блок 8 элементов ИЛИ поступает на дешифратор 9. Дальнейшая работа аналогична определению результата операции модульного сложения.

Если определяется результат (A/B)mod m, то присутствует сигнал на входе 31, который открывает блок 4 элементов И, элемент И 32, блок 25 элементов И. В зависимости от соотношения операндов А и В на выходе шифратора 34 образуется двоичное число, соответствующее количеству сдвигов регистра 16 при модульном делении, а на выходе И 32 образуется сигнал, если направление сдвига правое при заданной операции. В этом случае на вход приемного регистра 10 информация поступает с выходов элементов ИЛИ 34 через элементы И 25 и ИЛИ 26, а на вход элемента И 17 - с выхода ИЛИ 37. Дальнейшая работа аналогична определению результата модульного сложения. Если В 0, то на выходе элемента И 33 будет сигнал, свидетельствующий об ошибке при проведении операции модульного деления (деление на ноль).

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

Исходное состояние регистра 16: 1- 0- 1-1-0-0-0. Первые три двоичных разряда соответствуют числу 5. Число 3 соответствует сдвигу регистра влево на один двоичный разряд, 2 - вправо на один двоичный разряд и т.д. Составим таблицу для реализации операции модульного сложения. В табл. 1 отражены результаты операции модульного сложения,

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

Таблица 1

Таблица 2

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

Таблица 3

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

Таблица 4

Следовательно, первый 23 и второй 34 шифраторы формируют четыре числа: 00, 01, 10, 11. На входе элемента И 36 объединяются выходы матрицы 22 элементов И, которые помечены знаком - в табл.2, а на входе элемента и 32 объединяются выходы матрицы 22 элеметов И, которые помечены знаком - в табл. 4.

Пример 1. А О, В 2. Необходимо (А + B)mod m. Первый операнд А 0 поступает на первый дешифратор 2, с входа которого поступает на первый вход первых входов элементов И строк матрицы 22. Операнд В через блок 4 элементов И, блок 8 элементов ИЛИ поступает на дешифратор 9. С выхода дешифратора 9 поступает на третий вход вторых входов элементов И столбцов матрицы 22. В приемном регистре 10 будет записано число 01 согласно таблице 2 (сигналом с выхода ИЛИ 29 открыт элемент И 36 и блок 24 элементов И). Сигнал на выход элемента И 36 не поступит, а на элемент И 18 поступит сигнал. Импульсы через открытые элементы 13 и 14 запрета поступают на регистр 16 и на счетчик 11. В момент совпадения состояния регистра 10 и счетчика 11 (в счетчике 11 содержится значение 01) схема 12 сравнения формирует сигнал, закрывающий элементы 13 и 14 запрета и открывающий блок 15 элементов И. Состояние регистра 16 будет следующее:

0-1-0-1-1-0-0

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

Пример 2. А О, В 2. Необходимо определить (А - B)mod m.

В этом случае на первый вход первых входов элементов И строк матрицы 22 поступает си гнал. На шестой вход вторых входов элементов И столбцов матрицы 22 также поступает сигнал (7 - 2 5). В приемном регистре 10 будет записано число 00. Сигнал с выхода элемента И 36 не поступит, а схема 12 сравнения в момент включения устройства вырабатывает сигнал, закрывающий элементы 13 и 14 запрета и открывающий блок 15 элементов И. Сдвига не произойдет. Состояние регистра 16 будет следующее:

1-0-1-1-0-0-0

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

Пример 3. А 2, В 3. Необходимо определить (A/B)mod m. Первый операнд А« 2 поступает на первый 2 дешифратор, с выхода которого поступает на третий вход первых входов элементов И строк матрицы 22. Операнд В через блок 4 элементов ИЛИ через второй 9 дешифратор поступает на четвертый вход вторых входов элементов И столбцов матрицы 22. Во втором 34 шифраторе формируется двоичное число, соответствующее количеству сдвигов регистра 16 при операции модульного деления (согласно таблице 4). В данном случае в приемном 10 регистре будет записано число 01 согласно таблице 4 (сигнал присутствует на втором входе блока 25 элементов И). Сигнал с выхода элемента НЕ 20 поступит на вход элемента И 18. Импульсы через открытые

элементы 13 и 14 запрета посгуплкп на рр гистр 16 и на счетчик 11. В момент совпал0 ния состояния регистра 10 и счетчикя 11 (е; счетчике 11 содержится значение 01)схе ма 12 сравнения формирует сигнал, закры вающий элементы 13 и 14 запрета и открывающий блок 15 элементов И. Состояние регистра 16 будет следующее1

10

0-1-1 -0-0-0 - 1-0

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

Техническое преимущество предлагаемого устройства в сравнении с известным состоит в расширении области применения за счет выполнения деления с небольшими затратами оборудования.

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

Дополнительным преимуществом данного способа реализации операции (A/B)mod rn является также то, что используется только одна матрица 22 элементов И для всех модульных операций и то, что быстродействие

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

35

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

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

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

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

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

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

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

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

с первым и вторым входами третьего элемента ИЛИ, выход которого соединен с входом элемента НЕ.

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