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

 

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

СООЗ СОВЕТСНИХ

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

РЕСПУБЛИН (1% (И) (5р С 06 Р 7/72

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

К ASTOPCHOMV СВИДЕТЕЛЬСТВУ

l

1 .1

*с !

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3827586/24-24 (22) 19. 12. 84 (46) 15.09.86. Бюл. У 34 (72) О.Н.Фоменко,В.А.Краснобаев, В.А.Каревский и В.М.Панков (53) 681.325,5(088.8) (56) Авторское свидетельство СССР

Р 454550, кл, G 06 F 7/50, 1974.

Авторское свидетельство СССР

Р 1168934, кл. (: 06 F 7/72, 1984 ° (54) устРО(":СТВО дЛя СЛожЕНИя И ВМЧИТАНИЯ ЧИСЕЛ ЛО МОДУЛ1(1 P (57) Изобретение относится к области автоматики и вычислительной техники..Цель изобретения " повышение быстродействия выполнения операций сложения и вычитания чисел по модулю P. Для достижения цели в устройство введены второй дешифратор, второй и третий сумматоры по модулю

Р, вторая группа элементов ИЛИ, второй и третий элементы ИЛИ, пятая, шестая, седьмая, восьмая, девятая и десятая группы элементов И, третий и четвертый элементы И. В устройстве для операндов, лежащих в диапазоне P/2 8 В «< (P-l), за счет использования свойства сравнения А-(Р-В) (A+8)modP, сдвиг содержимого кольцевого сдвигающего регистра на В разрядов влево (против часовой стрелки) заменен на сдвиг на P-В разрядов вправо (по часовой стрелке). 2 ил.

1257643

A-(P-В)=(А+В)modP

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

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

На фиг. 1 и 2 представлены структурные схемы устройства для сложения и вычитания чисел по модулю Р, Устройство для сложения и вычитания чисел по модулю P содержит: первый и второй информационные входы 1 и 2 устройства, первый и второй входные регистры 3 и 4, первый дешифратор 5, первую группу элементов

И 6, вторую группу элементов И 7, кольцевой регистр 8, первый элемент

ИЛИ 9, выходной регистр 10, выход

11 устройства, первый сумматор 12 по модулю Р, третью группу элементов

И 13, четвертую группу элементов

И 14, шину 15 сложения, шину 16 вычитания, шину 17 запуска устройства, генератор 18 импульсов, третий и четвертый элементы И !9 и 20, схему

21 сравнения, умножитель 22 частоты, суммирующий счетчик 23, приемный регистр 24, первую группу элементов

ИЛИ 25, пятую и шестую группы элементов И 26 -и 27, вторую группу элементов ИЛИ ?8, второй дешифратор 29, второй и третий элементы ИЛИ 30 и

Зl,.седьмую, восьмую, девятую и де,,сятую группы элементов И 32, 33, 34 и 35, второй и третий сумматоры

36 и 37 цо модулю Р, вход 38 задания значения модуля P устройства, четвертый и третий элементы И 39 и 40.

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

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

Й =В, если Ос В6--гдей = Р

+ +Р =Р-В, если — «ьВ < Р-1.

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

1О !

Щ

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

Сумматоры 1?, 36 и 37 инвертйруют по модулю P входные операции.

В момент поразрядного совпадения состояний соответственно приемного регистра 24 и суммирующего счетчика

23 схема 21 поразрядного сравнения вырабатывает сигнал совпадения.

Умножитель 22 частоты в п=(1од

«(P-1)) +1.раз увеличивает количество выходных импульсов генератора 18.

Количество разрядов кольцевого регистра 8 равно количеству возможных остатков по исходному модулю P.

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

Предположим, необходимо определить (A+B)modP (присутствует сигнал шины

15 сложения). Исходное состояние устройства: нулевое состояние всех регистров 3, 4, 24 и суммирующего счетчика 23; в кольцевом регистре 8 записана первая строка таблицы модульного сложения.

Через первый информационный вход

1 в двоичном коде поступает первый операнд А во входной регистр 3, а через второй информационный вход 2 в двоичном коде во входной регистр

4 поступает второй операнд В, который поступает и на первый вход первого сумматора 12 по модулю P. Первый дешифратор 5 преобразует операнд

А из двоичного кода в унитарный и

1 соответствующий сигнал поступает на один определенный элемент И первой группы элементов И 6. С выхода входного регистра 4 сигнал через открытые элементы И третьей группы элементов И и пятой группы элементов

И 13 и 26 поступает на дешифратор 29 (через группу элементов ИЛИ 28) и на первые входы седьмой и восьмой групп элементов И 32 и 33. Второй дешифратор 29 преобразует второй операнд В из двоичного кода в унитарP-2 ный. Предположим, 0 "  — —, тогда присутствует выходной сигнал третьего элемента ИЛИ 30, который открыва.ег элементы И седьмой и восьмой групп элементов И и элемент 39, 32 и 34.

В этом случае сигнал с выхода группы элементов И 13 через группу элементов И 32 и группу элементов ИЛИ 25

l?57643 4

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

3 заносятся в приемный регистр 24. По сигналу шины 17 запуска устройства с выхода генератора 18 импульсов на входы открытых элементов И 19 и .20 поступают импульсы. С выхода элемента И 19 через умножитель 22 частоты, через открытый четвертый эле" мент И 39 на первый (положительный) вход кольцевого регистра 8 поступает последовательность из п В импульсов, В момент поразрядного совпадения состояния суммирующего счетчика

23 н приемного регистра 24 схема 21 сравнения выдает сигнал, который закрывает элементы И 19, 20 и открывает соответствующие элементы И первой группы элементов И, второй группы элементов И 7, через который установившийся (после сдвига по часовой стрелке52, =В разрядов кольцевого ре гистра 8) разряд кольцевого регистра 8 через первый элемент ИЛИ 9 поступает в выходной регистр 10. Пусть

- В ы Р-1 тогда выходной сигнал

Ф второго элемента ИЛИ 31 открывает элементы И восьмой и десятой групп элементов И 33, 35 и третий элемент

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

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

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

Р, схему сравнения, первый элемент

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

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

I элемента И подключен к информационноМу входу суммирующего счетчика, выход схемы сравнения подключен к вторым входам первой группы элементов И, к вторым входам первого и второго элементов И и к третьим входам элементов И второй группы, О т л и ч аю щ е е с я тем, что, с целью новы- 10 шення быстродействия, в устройство введены Второй дешифратор, второй и третий сумматоры по модулю Р, вторая группа элементов ИЛИ, второй . и третий элементы ИЛИ, пятая, mec- 15 тая, седьмая, восьмая,, девятая и десятая группы элементоВ И, третий и четвертый элементы И, выходы второго входного регйстра и первого сумматора по модулю P подключены к груп- 20 пам входов соответственно пятой и шестой групп элементов И, выходы ко;торых через вторую группу элементов

ИЛИ подключены к входу второго деP2 . 25 шифратора, первая (0... - ) и втоР рая (— 2 . ° .P-I) группы ВыхОДОВ (Где

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

:групп элементов И соединены соответственно с шинами управления сложени43 Ь ем и вычитанием устройства, выходы первой группы элементов И подключены соответственно к группе входов седьмой и восьмой групп элементов И, выходы второй группы элементов И подключены соответственно к группе входов девятой и десятой групп элементов И, выходы восьмой группы элементов И и десятой группы элементов И подключены соответственно к первым входам второго и третьего сумматоров по модулю Р, вторые входы которых соединены со входом задания значения модуля P устройства, выходы второго и третьего сумматоров по модулю F седьмой и девятой групп элементов И подключены к соответствующим входам первой группы элементов ИЛИ, вторые входы седьмой и девятой групп элементов И и первый вход четвертого элемента И подключены к выходу третьего элемента ИЛИ, выход четвертого элемента И соединен с первым (положительным) входом кольцевого регистра сдвига, вторые входы восьмой и десятой групп элементов И и первый вход третьего элемента И подключены к.выходу второго элемента ИЛИ, вто" рые входы третьего и четвертого элементов И подключены к выходу умножителя частоты, выход третьего элемента И соединен с вторым (отрицательным) входом кольцевого регистра сдвига.

1257643

1257643

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

Техред Л.Сердикова Корректор И.Муска

Редактор Э.Слигон тираж 671 Подписное

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

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

Закаэ 4958/48

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