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

 

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

0 А1

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

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

РЕСПУБЛИК (19) (И) (so 4 С 06 F 7/49

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4137271/24-24 (22) 17.10.86 (46) 15.04.88. Бюл. ¹ 14 (72) О. Н. Фоменко, В. А. Краснобаев, С. В. Иванов, M. В. Юмашев и И. Б. Захаревич (53) 681.325.5(088.8) (56) Авторское свидетельство СССР № 1095172, кл. 6 06 F 7/49, 1983.

Автор с ко е с вид ет ель с тв о СССР № 1168934, кл. 6 06 F 7/72, 1983, (54) УСТРОЙСТВО ДЛЯ CJIOKEHHH И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ P (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах и устройствах, функционирующих в системе остаточных классов (СОК).

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

1388850

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

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

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

3, первую и вторую группы элементов

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

29, третий и четвертый элементы

ИЛИ 30 и 31, элементы И 32 и 33, Сущность изобретения состоит в

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

У торому работает устройство), т,е. 45 величина максимального сдвига будет

P — 1 равна - — — разряда а не P — 1 раз2

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

P Р

А+В=А +В = (А + -) + (В )ю

2 2 где А и В - входные операнды (О- А;

В Р - 1), 55

При этом в исходном состоянии в разрядах кольцевого регистра сдвига содержится не нулевая (как в проP - 1 тотипе) а -"- — строка матрицы мо2 дульного сложения (А + B)mod P. Отметим, что признаки положительного („=1) и отрицательного (=1) сдвигов кольцевого регистра сдвига опре" деляются следующим образом:

Р + 1

1 если "——

2 +=

О, если 0 B аВ Р

P-1 («» е

Р 1

1, если 0 (В

Р+ 1

Ф если — — -,

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

В этом случае в приемный регистр

I устройства заносится операнд /В f в двоичном коде, Р 1 где 0 «(/В/»

Дешифратор 27 преобразует входной операнд В (В = P-В) в унитарный код. Количество двух входовых элементов И 28 равно P — 1

Шифратор 29

2 преобразует унитарный код в двоичный, Устройство работает следующим образом.

В исходном состоянии все регистры

2, 6, 10 и 18 обнулены, в регистре

Р + 1

26 сдвига записана (— — -)-я

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

Допустим необходимо определить (A+B)modP. По входной шине 1 в двоичном коде поступает первый операнд в регистр 2 и далее через дешифратор 3 сигнал, соответствующий значению A. в унитарном коде, поступает на соответствующий элемент И 4. На вход

9 второй операции В в двоичном коде поступает на вход регистра 10 сумматора 1). С выхода регистра 10 через открытые элементы И 13 (присутствует сигнал шины 16), через элементы ИЛИ 15 поступает на вход дешифратора 27, с выхода которого сигнал, соответству1388850 ющий значению В в унитарном коде через соответствующий элемент ИЛИ 28, поступает на шифратор 29, с выхода

I которого значение /В / в двоичном коде заносится в регистр 18. Если

P - 1

О <Вй "-""- то на выходе элемента

ИЛИ 30 присутствует сигнал (K=1), который открывает элемент И 32. По сигналу шины 21 с выхода генератора

22 через открытые элементы И 23 и

24 импульсы поступают соответственно в счетчик 20 и на вход умножителя 25, с выхода которого через элемент И 32 - на отрицательный вход регистра 26, сдвигая исходное содерf жимое на и /В / двоичных разрядов по часовой стрелке (n = (log (Р - 1))+

+1). В момент поразрядного совпадения состояний счетчика 20 и регистра 18 схема 19 сравнения выдает сигнал, который открывает соответству.— ющие элементы И 4 и 5 и закрывает элементы И 23 и 24. Через соответствующий элемент И 5 содержимое установившегося (после сдвига) разряда регистра 26 поступает через элемент

Р + 1

ИЛИ 6 в регистр 7. Если (В а

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

Пусть необходимо определить (АB)modP (присутствует сигнал шины 1?).

В этом случае инвертированное значение В = P — В с выхода сумматора 11 поступает через элементы И 14 на входы элементов ИЛИ 15. Далее работа устройства аналогична работе в случае поступления входных операндов А и В.

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

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

50 приемный регистр, кольцевой регистр сдвига, сумматор по модулю Р, первую, вторую, третью и четвертую группы элементов И, первую группу элементов

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

ИЛИ, первый дешифратор, умножитель частоты, при этом первый информационный вход устройства подключен к входу первого дешифратора, выходы которого подключены к первым входам соответствующих элементов И первой группы, выходы которых подключены к первым входам соответствующих элементов И второй группы, выходы которых через первый элемент ИЛИ подключены к-входу результата устройства, второй информационный вход устройства подключен к первому входу сумматора по модулю P к второму входу которого подключен вход подачи значения модуля P а выходы второго входного регистра и сумматора по модулю P через первые входы соответственно первой и второй группы элементов И подключены к входам элементов ИЛИ первой группы, к вторым входам элементов И первой и второй группы подключены входы управления соответственно сложением и вычитанием устройства, выход приемного регистра подключен к первому входу схемы сравне †ния, к второму входу которой подключен выход суммирующего счетчика, вход запуска устройства подключен к входу генератора импульсов, выход которого подключен к первым входам первого и второго элементов И, выходы которых подключены к входам соответственно суммирующего счетчика и умножителя частоты, выходы разрядов кольцевого регистра сдвига подключеНы к вторым входам соответствующих элементов И второй группы, а выход схемы сравнения подключен к вторым входам элементов И первой группы, к третьим входам элементов И второй группы и к вторым входам первого и второго элементов И, о т л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия выполнения операций, введены второй дерифратор, вторая группа элементов ИЛИ, шифратор, второй и третий элементы ИЛИ, третий и четвертый элементы И, причем выходы элементов ИЛИ первой группы подключены к входу второго дешифратора, выходы которого попарно через соответствующие элементы ИЛИ второй группы подключены к входу шифратора, выход которого подключен к входу приемного регистра, одновреP — 1 менно первая (Π— -- †-) и вторая

Р+ 1

2 (----- — P — - 1) группы выходов вто2 рого дешифратора подключены к входам соответственно второго и третьего элементов ИЛИ, выходы которых подключены соответственно к входу уп1388850 равления направлением сдвига кольцевого регистра сдвига, к вторым входам третьего и четвертого элементов

И подключен выход умножителя частоты.

1388850

ИЗЗ нМ53

Составитель М. Есенина

Техред 11.Дидык

Корректор С. Черни

Редактор Ю. Середа

Подписное

Заказ 1580/49 Тираж 704

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4