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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах на устройствах, функционирующих в системе остаточных классов. Цель изобретения - повышение быстродействия. Цель достигается за счет уменьшения в два раза количества импульсов для продвижения содержимого кольцевого регистра 6 сдвига путем введения трех преобразователей 14, 15. 9 кода, третьего блока 4 элементов И, третьего 25 и четвертого 26 элементов И. двух элементов ИЛИ 22. 29. двух элементов НЕ 24, 30. элемента ИЛИ - НЕ 17, сумматора 23 по модулю два. Сущность изобретения состоит в повышении быстродействия выполнения модульных операций сложения и вычитания , которое достигается уменьшением диапазона значений входных операндов. 1 ил., 3 табл. /9/

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

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

РЕСПУБЛИК (м)з G 06 F 7/72

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4926165/24 (22) 05;04,91 (46) 07.06,93. Бюл. N. 21 (72) О.Н,Фоменко, В.А.Краснобаев, В.П.Ирхин, В.Н.Чичеватов, С.И,Куцый. Ю.С.Власишен и И.В;Приходько (56) Авторское свидетельство СССР

М 1257643, кл. G 06 F 7/72, 1984.

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

В 1168934, кл. G 06 F 7/72, 1985..

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

М 1546976, кл. G 06 F 7/72, 1988 (54) УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах на

„„. Ж,, 1820380 А1 устройствах, функционирующих в системе остаточных классов. Цель изобретения — повышение быстродействия. Цель достигается за счет уменьшения в два раза количества импульсов для продвижения содержимого кольцевого регистра 6 сдвига путем введения трех преобразователей 14, 15, 9 кода, третьего блока 4 элементов И, третьзго 25 и четвертого 26 элементов И, двух элементов

ИЛИ 22, 29, двух элементов HE 24, 30, элемента ИЛИ вЂ” НЕ 17, сумматора 23 по модулю два. Сущность изобретения состоит в повышении быстродействия выполнения модульных операций сложения и вычита- .ния, которое достигается уменьшением диапазона значений входных операндов 1 ил., 3 табл.

1820380

Таблица 3

20

yA (ye)Таблица

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

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

Сущность изобретения- состоит в повышении быстродействия выполнения модульных операций сложения и вычитания путем уменьшения диапазона значений входных операндов, Известно, что. в схеме модульного умножения используются свойства симметрии арифметической таблицы относительно правой и левой диагонали, а также вертикали и горизонтали, проходяm— - 1 в+1 щих между величинами и †где m — модуль устройства. Обозначив индекс операнда как

О, если О А(В) а — — а 1

1, если — —, А(В) S m-1, m+1 а А (В ) - m — А(В). можно получить следующие соотношения для операций модульного сложения и вычитания: при уд =уц-О (А+ B)modm-(A+ B) modm; (A- В)тобе»

-(A — B)modm, при уд =О, + =1 (А+ B)modm -(А- В )modm;(A- B)modm» (А+ В )modm, при уд =1, =0 (А + B)modm - m — (А — B)modm; (А — B)modm m — (А + B)modm, при уд =у = 1 (А+ B)modm m — (А + В)modm; (А—

B)modm m — (А — В )modm.

Данные соотношения позволяют существенно уменьшить величину входных опе. рандов. Рассмотрим их реализацию при а - 5. Для определения величины ф первый преобразователь кода необходимо выполнить согласно табл. 1.

Второй и третий преобразователи кода (табл, 2 и 3) реализуют соответственно функции преобразования В-+ В и (m — Х), где

Х вЂ” предварительное значение результата операции.

Таблица 2

Быстродействие работы определяется величиной второго операнда В, так как от него зависит количество тактов сдвига для

25 получения результата. В изобретении макm — 1 симэльная величина Bwa c2 . Группа элементов ИЛИ в данном случае (m - 5) состоит из двух элементсв, к первым входам

30 которых подключены соответственно первый и второй выходы дешифратора, э к вторым — соответственно четвертый и третий.

Возможность достижения положительного эффекта от использования изобрете35. ния состоит в повышении быстродействия работы устройства, ввидууменьшения количества сдвигов регистра для получения ре зультата.

Дополнительным положительным эф40 фектом является уменьшение количества оборудования и коммутаций, что позволяет

plpocTMTb устройство и повысить его надежность.

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

ИЛИ. 12 — выход устройства, 13 — второй информационный вход устройства, 14- пер55 вый преобразователь кода, t5 — второй преобразователь кода, 16 — счетчик, 17— элемент ИЛИ вЂ” НЕ, 18 — элемент запрета. 19 — тактовый вход устройства, 20 — первый элемент И, 21 — второй элемент И, 22— первый элемент ИЛИ, 23 — сумматор по мо1820380

10

25

55 дулю два, 24 -- первый элемент НЕ. 25— третий элемент И, 26 — четвертый элемент

И, 27 — вход задания операции сложения устройства, 28 — вход задания операции вычитания устройства, 29 — второй элемент

ИЛИ, 30 — второй элемент НЕ.

Первый информационный вход 1 устройства соединен с входом дешифраторэ 2, младшие и старшие выходы которого соединены соответственно с первыми и вторыми входами соответствующих элементов ИЛИ

3 группы, Выходы последних соединены с первыми входами соответствующих элементов И третьего блока 4, вторые входы которых соединены с входом 5 начальной установки устройства и входом разрешения записи кольцевого регистра 6 сдвига, а выходы — с входами соответствующих младших разрядов кольцевого регистра 6 сдвига.

Выходы разрядов регистра 6 соединены с соответствующими входами шифратора 7, выход которого соединен с первыми входами элементов И первого блока 8 и с входом третьего преобразователя 9 кода, выход которого соединен с первым входом второго блока 10 элементов И. Выходы первого 8 и второго 10 блоков элементов И соединены соответственно с первым и вторым входами блока 11 элементов ИЛИ, выход 12 которого я вл я ется выходом устройства. Второй информационный вход 13 усгройства соединен с входами первого 14 и второго 15 преобразователей кода, выход которого соединен с информационным входом счетчика

16. выходы разрядов счетчика 16 соединены с соответствующими входами элемента

ИЛИ-Н Е 17, выход которого соединен с вторым входом элемента 18 запрета. Первый вход последнего соединен с тактовым sxoдом 19 устройства, а выход — с вычитающим входом счетчика 16 и с первыми входами первого 20 и второго 21 элементов И, выходы которых соединены соответственно с еходав".и задания сдвига вправо и влево кольцевого регистра 6 сдвига. Старшие выходы дешифратора 2 соединены с соответствующими входами первого элемента ИЛИ

22, выход которого соединен с первым вхо QoM сумматора 23 по модулю два, вторыми входами элементов И второго блока i0 и с входом первого элементами НЕ 24, выход которого соединен с вторыми входами элементов И первого блока 8. Выход младшего разряда первого преобразователя 14 кода соединен с вторым входом сумматора 23 по модулю два, инверсный и прямой выходы которого соединены с первыми входами соответственно третьего 25 и четвертого 26 элементов И. вторые входы которых соединены соответственно с входами задания операций сложения 27 и вычитания 28 устройства, Выходы третьего и четвертого элементов И соединены с первым и вторым входами второго элемента ИЛИ 29, выход которого соединен с вторым входом первого элемента И 20 и с входом второго элемента

HE 30, выход которого соединен с вторым входом второго элемента И 21.

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

Кольцевой регистр 6 сдвига содержит m двоичных разрядов (Π— m — l). m — значение модуля. Исходное состояние регистра — нули во всех разрядах. Сигнал на выходе элемента ИЛИ вЂ” HF. 17 появляется в том случае, когда на всех выходах счетчика 16 нули. При проведении операции модульного сложения операнд А поступает на вход дешифратора 2, с выхода которо о. пройдя через группу 3 элементов ИЛИ, преобразуется в А при уд = 1, Одиночный импульс, поступающий с входа 5 на второй вход блока 4 элементов И, обеспечивает запись единицы в

А(А )-м разряде кольцевого регистра б сдвига. Операнд В поступает на вход 13. с выхода второго преобразователя 15 кода он в виде В(В при уп = 1) поступает на установочный вход счетчика 16. С тактового входа

19 через открытый элемент 18 запрета поступают импульсы на вычитающий вид счетчика 16. Сигнал с выхода первого элемента

ИЛИ 22 поступает, если уд = 1, а с выхода преобразователя 14 кода — eci,и ув -= 1. С инверсного выхода сумматора 23 по модул.о два поступает сигнал, если уд = 1 и . В да нном случае (присутствует сигнал на входе

27) при уд = ув сигнал с выхода третьего элемента И 25 через второй элемент ИЛИ 29 поступает на вход сдвига вправо содержимого регистра 6 через открытый элемент И

20 (на другой его вход поступают тактовые импульсы). Производится продвижение единицы, записанной в регистр, на В(В ) двоичных разрядов вправо, когда содержимое счетчика 16 равно нулю, сигнал с выхода элемента ИЛИ вЂ” НЕ 17 закрывает элемент 18 запрета, запрещая прохождение импульсов на сдвиг двоичных разрядов регистра (этот сигнал является сигналом окончания модульной операции), Результат операции с выходов разрядов регистра, полученный в унитарном коде, поступает на вход .i шифратора 7. с выхода которого он поступает на входы первого блока 8 элементов И L1 через третии преобразователь 9 кода (произ;..>дит операцию m — X) на входы второго 1А локэ

1820380 (-0 — 0 — 1 — 0 — 0-) O

Второй операнд В = 100 поступает на вход второго преобразователя 15 кода, с выхода которого число В = 001 (см. табл, 2) устанавливается в содержимом счетчика 16.

На выходе первого элемента ИЛИ 22 сигнала нет, а с выхода первого преобразователя

15 кода (см, табл. 1) поступает сигнал. В этом случае (сигнал на входе 27 присутствует) сигнал поступает с выхода второго элемента

НЕ 30 на вход второго элемента И 21. Сигнал также поступает с выхода первого элемента НЕ 24 на вход первого блока 8 элементов И, С тактового входа 19 через элемент 18 запрета поступает один импульс, который продвигает единицу в регистре на один двоичный разряд влево и уменьшает содержимое счетчика 16 до нуля, так как поступает на его вычитаюьций вход.

С выхода элемента ИЛИ вЂ” HE 17 поступает

55 элементов И. Если 1 д= 1. то производится коррекция результата путем поступления сигнала на другой вход второго блока 10 элементов И с выхода первого элемента

ИЛИ 22. В противном случае поступает сиг- 5 нал с выхода первого элемента НЕ 24 на другой вход первого блока 8 элементов И и результат операции через блок 11 элементов ИЛИ поступает на вход 12 устройства.

Если уд Фур, то сигнал с выхода второго 10 элемента HE 30 поступает на вход сдвига влево содержимого регистра через открыый элемент И 21, Иначе говоря, при

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

Работаустройства при выполненииоперации. модульного вычитания отличается от модульного сложения только тем, что в данном случае при уд Ф ув производится изме- 20 нение сдвига двоичных разрядов регистра с левого на правое.

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

Пример 1, Пусть необходимо определить результат операций модульного сложения для А = 2, В = 4 (А.  — операнды).

Первый операнд А =- 010 поступает на вход дешифратора 2, на втором выходе которого 30 будет сигнал. Этот сигнал поступает на первый вход второго элемента ИЛИ 3 группы, с выхода которого он поступает через третий блок 4 элементов И (после импульса с входа

5) во второй разряд регистра (см. табл. 2), содержимое которого следующее сигнал, который закрывает элемент 18 запрета. Содержимое регистра следующее.

Следовательно, результат операции равен единице, Он поступает на входы шифратора. с выхода которого поступает в двоичном коде (001) на первый вход первого блока 8 элементов И и с его выхода через блок 11 элементов ИЛИ на выход 12 устройства (2+ 4)mod5 = (1)mod5.

Пример 2. Пусть необходимо определить результат операции модульного вычитания для А = 4, В =- 3 (А,  — операнды).

Первый операнд А = 100 поступает на вход дешифратора 2, на четвертом выходе которого будет сигнал, Этот сигнал поступает на второй вход первого элемента ИЛИ 3 группы, с выхода которого он поступает через блок 4 элементов И (после импульса с входа

5) в первый разряд регистра (см, табл, 2), содержимое которого следующее !

-О 1 О-0 О-, Второй операнд В = 011 поступает на вход второго преобразователя 15 кода, с выхода которого число В "010 (см, табл. 2) устанавливается в содержимом счетчика 16.

Сигналы поступают с выхода первого элеме та ИЛИ 22 и с выхода первого преобразователя 14 кода (см. табл, 1), В этом случае (сигнал на входе 28 присутствует) сигнал поступает с выхода второго элемента НЕ 30 на вход второго элемента И 21, а с выхода первого элемента ИЛИ 22 на вход второго блока 10 элементов И. С тактового входа 19 через элемент 18 запрета поступают два импульса, которые продвигают единицу в регистре на два двоичных разряда влево и уменьшают содержимое счетчика 16 до нуля..Содержимое регистра следующее г-о-о-o o-

Этот результат (100) в двоичном коде поступает с выхода шифратора 7 на третий преобразователь 9 кода, с выхода которого окончательный результат 001 (см. табл. 3) через второй блок 10 элементов И, блок 11 элементов ИЛИ поступает на выход 12 устройства (4 — 3)mod5 = (1)mod5.

Техническое преимущество изобрете ния в сравнении с прототипом состоит существенном (максимально в jloggm(х

1820380

m — 2

1 раз) повышении быстродействия

2 (т — 1 выполнения модульных операций. Дополнительным преимуществом является уменьшение количества оборудования и связей, приводящее к упрощению устройства.

Достоверность достижения цели подтверждается конкретными примерами выполнения операций сложения и вычитания при m =5. дами соответственно третьего и четвертого элементов И, вторые входы которых соеди35 нены соответственно с входами задания операций сложения и вычитания устройства, а выходы третьего и четвертого элементов И соединены с первым и вторым входами второго элемента ИЛИ, выход которого соединен с вторым входом первого элемента И и входом второго элемента НЕ, выход которого соединен с вторым входом второго элемента И, 40

Составитель В, Ирхин

Редактор С. Кулакова Техред М.Моргентал Корректор Н. Король

Заказ 2031 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород. ул.Гагарина, 101

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

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

И, блок элементов ИЛИ и группу элементов

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

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

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