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

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

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

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

Устройство для сложения и вьгаита- ния чисел по модулю Р содержит: первый и второй информационные входы и 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 и 3,.седьмую, восьмую, девятую и де- |Сятую группь элементов И 32, 33, 34 и -35, второй и третий сумматоры 36 и 37 по модулю Р, вход 38 задания значения модуля Р устройства, четвертый и третий элементы И 39 и 40„

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

Сдвиг разрядов кольцевого сдвигающего регистра производится как в положительном (против часовой стрелки, как в прототипе), так и в отрицательном (по часовой стрелке) направлениях, т.е. положительный сдвиг наП В разрядов содержимого кольцевого регистра равнозначно отрицательному сдвигу содержимого кольцевого регистра на разрядов,

г

где Я.

Я.В, если 0 В --- ,

fl--p-B, если-iBiP-.

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

A-(P-B)(A+B)modP

57643, 2

Время выполнения операции будет прямо пропорционально величине S.

Сумматоры 12, 36 и 37 инвертируют по модулю Р входные операции. 5 В момент поразрядного совпадения состояний соответственно приемного регистра 24 и суммирующего счетчика 23 схема 21 поразрядного сравнения вырабатывает сигнал совпадения.

Умножитель 22 частоты ъ п lof,f )(Р-1 ) . раз увеличивает количество выходных импульсов генератора 18.

Количество разрядов кольцевого регистра 8 равно количеству возмож15 ных остатков по исходному модулю Р, Каждый разряд регистра 8 состоит из (Р-1)-1-1 двоичных разрядов, необходимых для представления наибольшего остатка Р-1.

20 Предположим, необходимо определить ()raodP (присутствует сигнал шины 15 сложения). Исходное состояние устройства: нулевое состояние всех регистров 3, 4, 24 и суммирующего

25 счетчика 23j в кольцевом регистре 8 записана первая строка таблицы модульного сложения.

Через первый информационный вход 1 в двоичном коде поступает первый

30 операнд А во входной регистр 3, а через второй информационный вход 2 в двоичном коде во входной регистр 4 поступает второй операнд В, который поступает и на первый вход пер35 вого сумматора 12 по модулю Р. Первый дешифратор 5 преобразует операнд А из двоичного кода в унитарный и

соответствующий сигнал поступает на один определенный элемент И первой

40 Группы элементов И 6. С выхода входного регистра 4 сигнал через открытые элементы И третьей группы Элементов И и пятой группы элементов И 13 и 26 поступает на дешифратор 29

45 (через группу элементов ИЛИ 28) и на первые входы седьмой и восьмой групп элементов И 32 и 33. Второй дешифратор 29 преобразует второй операнд Б из двоичного кода в унитар50р 2

ный. Предположим, --- , тогда

присутствует вьгходной сигнал третье- го элемента ИЛИ 30, который открывает элементы И седьмой и восьмой групп 55 элемейтов И и элемент 39, 32 и ЗЛ. В этом случае сигнал с выхода группы элементов И 13 через группу элементов И 32 и группу элементов ИЛИ 25

заносятся в приемный регистр 24. По сигналу шины 17 запуска устройства с выхода генератора 18 импульсов на входа открытых элементов И 19 и 20 поступают импульсы. С выхода элемента И 19 через умножитель 22 частоты, через открытый четвертый элемент И 39 на первый (положительный) вход кольцевого регистра 8 поступает последовательность из п В импульсов, В момент поразрядного совпадения состояния суммирукицего счетчика 23 и приемного регистра 24 схема 21 сравнения выдает сигнал, который закрывает элементы И 19, 20 и открывает соответствующие элементы И первой группы элементов И, второй группы элементов И 7, через который установившийся (после сдвига по часовой стрелке Л, В разрядов кольцевого регистра 8) разряд кольцевого регистра 8 через первый элемент ИЛИ 9 поступает в выходной регистр 10. Пусть р х ВбР-}, тогда выходной сигнал

второго элемента ИЛИ 31 открывает элементы И восьмой и десятой групп элементов И 33, 35 и третий элемент И 40. В этом случае сигнал с выхода первой группы элементов И 13 через восьмую группу элементов И 33 поступает на первый вход второго сумматора 36 ло модулю Р, на второй вход с входа 38 в двоичном коде поступает значение модуля Р. G вькОда второго сумматора 36 по модулю Р значение Р-В через первую группу элементов ИЛИ 25 поступает в приемный регистр 24. С выхода умножителя 22 частоты через третий элемент И 40 на второй (отрицательный) вход кольцевого регистра 8 поступает последовательность из п(Р-В) импульсов, сдвигая по часовой стрелке (отрицательное направление) на JZ Р-В разрядов кольцевого регистра 8, после чего значение соответствующего разряда кольцевого регистра 8 через вторую группу элементов И 7, элемент ИЛИ 9 поступает в выходной регистр 10.

Если необходимо определить результат операции (гтрисутствует снг- нап шины 16 вычитания), в этом случае работа устройства аналогична определению результата операции модульного сложения при входных операндах А и Р-В.

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

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

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

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

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

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

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

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

пам входов соответственно пятой и шестой групп элементов И, выходы ко- ,торых через вторую группу элементов ИЛИ подключены к входу второго деР-шифратора, первая (0... ---) и вто Р рая ( ...Р-) группы выходов (где

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

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

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

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

10

11

em 22

(puf.t

7«

(puS.Z

Изобретение относится к области автоматики и вычислительной техники. Цель изобретения - повышение быстродействия выполнения операций сложения и вычитания чисел по модулю Р. Для достижения цели в устройство введены второй дешифратор, второй и третий сумматоры по модулю Р, вторая группа элементов ИЛИ, второй и третий элементы ИЛИ, пятая, шестая, седьмая, восьмая, девятая и десятая группы элементов И, третий и четвертый элементы И, В устройстве для операндов, лежащих в диапазоне 6 (Р-1), за счет использования свойства сравнения А-() (A4-B)inodP, сдвиг содержимого кольцевого сдвигающего регистра на В разрядов влево (против часовой стрелки) заменен на сдвиг на Р-В разрядов вправо (по часовой стрелке). 2 ил. (Л (С :л