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

(Л

с:

Изобретение относится к автоматике и вычиcлиteльнoй технике и может быть использовано в системах и устройствах, функционируюпшх в системе остаточных классов (СОК). Цель изобретения - повышение быстродействия . Поставленная цель достигается за счет введения второго дешифратора, шифратора, второй группы элементов ИЛИ, второго и третьего элементов ШШ, третьего и четвертого элементов И. Сущность изобретения состоит в повьш1ении быстродействия выполнения операции сложения и вычитания чисел по модулю Р. Изобретение целесообразно использовать в системах и устройствах, функционирующих в СОК. 2 ил.а

со

00 00 00

ел

11

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

Цель изобретения - повышение быст родейртвия выполнения операций.

На фиг. 1 и 2 представлены струк турные схемы устройства для сложения и вычитания чисел по модулю Р.

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

Сущность изобретения состоит в повышении быстродействия выполнения операций сложения и вычитания чисел по модулю Р. Это достигается за счет того, что сдвиг содержимого кольцевого регистра сдвига как по часовой стрелке (J-), так и против часовой стрелки (у+) производится относительно величины Р - 1 ,

--- (р - модуль, по которому работает устройство), т.е.. величина максимгшьного сдвига будет

Р - 1

равна --- разряда, а не Р - 1 разрядов, как в прототипе. Это легко показать, используя следующее равенство:

+в (А

i

(В - |),

где А и В - входные операнды (0 А; ВИР - 1).

При этом в исходном состоянии в разрядах кольцевого регистра сдвига содержится не нулевая (как в прототипе) , а

Р - 1

строка матрицы модульного сложения (А + B)mod Р. От метим, что признаки положительного ( и отрицательного (j l) сдвигов кольцевого регистра сдвига определяются следующим образом:

1;

5При данных обозначениях рабочий операнд В представим в следующем

виде: п

в (уУвУ).

в этом случае в приемньй регистр устройства заносится операнд /В А в двоичном коде,

где О /в / --™.

Дешифратор 27 преобразует входной операнд В (В Р-В) в унитарный код. Количество двух входовых элементов И 28 равно Р - I ,„ , „„ ---. Шифратор 29

преобразует унитарный код в двоичный .

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

В ИСХОДНОМ состоянии все регистры 2, 6, 10 и 18 обнулены, в регистре

26 сдвига записана

,Р + К (-2)-я

строка таблицы модулярного сложения операндов А и В.

Допустим необходимо определить (A+B)modP. По входной щине 1 в двоичном коде поступает первый операнд А в регистр 2 и далее через дешифратор 3 сигнал, соответствующий значению А в унитарном коде, поступает на соответствующий элемент И 4. На вход 9 второй операции В в двоичном коде поступает на вход регистра 10 сумматора 11. С выхода регистра 10 через открытые элементы И 13 (присутствует сигнал щины 16), через элементы ИЛИ 15 поступает на вход дешифратора 27, с выхода которого сигнал, соответствующий значению В в унитарном коде че рез соответствующий элемент ИЛИ 28, поступает на шифратор 29, с выхода которого значение /В / в двоичном коде заносится в регистр 18, Если

Р - Г О-йВб-- , то на выходе элемента

РШИ 30 присутствует сигнал (jf l), который открывает элемент И 32. По сигналу шины 21 с выхода генератора 22 через открытые элементы И 23 и 24 импульсы поступают соответственно в счетчик 20 и на вход умножителя 25, с выхода которого через элемент И 32 - на отрицательный вход регистра 26, сдвигая исходное содержимое на п /в / двоичных разрядов по часовой стрелке (п - +1). В момент поразрядного совпадения состояний счетчика 20 и регистра 18 схема 19 сравнения выдает сигнал, который открывает соответствующие элементы И 4 и 5 и закрывает элементы И 23 и 24. Через соответствующий элемент И 5 содержимое установившегося (после сдвига) разряда регистра 26 поступает через элемент

Р + 1

ИЛИ 6 в регистр 7, Если --- В

Р - 1, то на выходе элемента ИЛИ 31 (J+ О присутствует сигнал, который открывает элемент И 33. В этом случае исходное содержимое регистра 26 сдвигается на п/В / двоичных разрядов против часовой стрелки. В остальном работа устройства аналогична ранее описанной.

Пусть необходимо определить (А - B)niodP (присутствует сигнал шины 17). В этом случае инвертированное значение В Р - В с выхода сумматора 11 поступает через элементы И 14 на входы элементов ИЛИ 15. Далее работа .устройства аналогична работе в случа поступления входных операндов.А и В.

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

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

0

5

0

5

0

5

0

5

0

5

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

/о Р - 1ч менно первая (О - ---) и вторая

Р + 1

(--- - Р - 1) группы выходов ВТОрого дешифратора подо:лючены к входам соотйетственно второго и третьего элементов ИЛИ, выходьл которых подключены соответственно к входу упОТ f9

фие. I

13888506

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

в

Hft.5

I

1

/fJJ /vJ/JJ

фиг. г