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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения - повышение быстродействия. Устройство содержит счетчики 2, 8, блоки 4, 6, 13, 14, 19 элементов И, преобразователи 5, 24 прямого кода в дополнительный, блоки 7, 22 элементов ИЛИ, элемент запрета 12, 18, элементы ИЛИ 15,17,20, элементы И 16,21. 1 ил. 2 табл.

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

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

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

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

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

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

00 О

СО

О (21) 4804661/24 (22) 20.03.90 (46) 23.04.93. Бюл. М 15 (72) О.H.Ôoìåíêî, В.А,Краснобаев, В.П.Ирхин, М.В.Юмашев, В.M.Ïàíêîâ, А.А.Журавлев и С.И.Куцый (56) Авторское свидетельство СССР

hL 1683012, кл. G 06 F 7/72, 1989.

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

f4 1546977, кл. 6 06 F 7/72, 19&8.

Авторское свидетельство СССР .z М 1633399, кл. G 06 F 7/72, 1984..

Ä.„ß „„1810889 А1 (54) УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель йзобретения — повышение. быстродействия. Устройство. содержит счетчики 2, 8, блоки 4, 6, 13, 14, 19 элементов И, преобразователи 5, 24 прямого кода в дополнительный, блоки 7. 22 элементов ИЛИ, элемент запрета 12, 18, элементы ИЛИ 15, 17, 20, элементы И 16, 21.

1 ил. 2 табл.

1810889

Изобретение относится к автоматике и вым входом третьего 17 элемента ИЛИ, вывычислительной технике и может быть ис- ход которого соединен с управляющими пользовано в вычислительных машинах и входами первого 12 и второго 18 элементов устройствах, функционирующих в системе запрета, тактовый вход 11 устройства соединен с информационным входом второго

Цельизобретения — повышениебыстро- 18 элемента запрета, выходы разрядов второго 8 счетчика соединены со входами разНа чертеже представлена структурная рядов первого входа пятого 19 блока схема устройства.

10 элементов И и с соответствующими входами

Она содержит 1 — первый информацион- второго 20 элемента ИЛИ, инверсный выход ный вход устройства, 2 — первый счетчик, 3 . которого соединен со вторым входом треть— второйинформационныйвходустройства, его 17 элемента ИЛИ и с первым входом

4 — первый блок элементов И, 5 — первый первого 21 элемента И, выход которого соепреобразователь прямого кода .в дополни- 15 динен со вторым входом четвертого 14 блотельный код по модулю, 6 — второй блок ка элементов И, выход которого соединен с элементов И, 7 — первый блок элементов первым входом второго 22 блока элементов

ИЛИ, 8 — второй счетчик, 9 — вход задания ИЛИ, выход которого соединен со вторым вычитания устройства, 10 — вход задания входом третьего 13 блока элементов И, выожения устройства 11 — тактовый вход 20 ход которого является выходом 23 устройст1 устройства,12 — первыйэлементзагрета,13 ва выходы первого 12 и второго 8 — третий блок элементов И, 14 — четвертый элементов запрета соединены соответстблок элементов И, 15 — первый элемент венно с вычитающими входами первого 2 и

ИЛИ, 16 — второй элемент И, 17 — третий второго 8 счетчиков, прямые выходы первоэлемент ИЛИ, 18 — второй элемент запрета, 25 го 15 и второго 20 элементов ИЛИ соедине19 — пятый блок элементов И, 20 — второй ны соответственно со вторыми входами элемент ИЛИ, 21 — первый элемент И, 22 — первого 21 и второго 16 элементов И, выход второй блок элементов ИЛИ, 23 — выход второго 16 элемента И соединен со вторым устройства, 24 — второй преобразователь входом пятого 19 блока элементов И, выход прямого кода в дополнительный код по мо- 30 которого соединен со входом второго 4. дулю, преобразователя прямого кода в дополниПервый 1 информационный вход уст- тельный код по модулю, выход которого соройства соединен с информационным вхо- единен со вторым входом второго 22 блока дом первого счетчика 2, второй 3 элементов ИЛИ. информационный вход устройства соеди- 35 Работу устройства удобно рассматринен с первым входом первого 4 блока эле- вать в двух режимах„ 1) режим определения ментов И и со входом первого 5 результата операции модульного вычита.преобразователя прямого кода в дополни- ния, 2) режим определения результата опетельный код по модулю, выход которого со- 4 рации модульного сложени . первом единен с первым входом второго 6 блока случае присутствует сигнал на шине 9 и втоэлементов И, выходы первого 4 и второго 6 рой операнд в 8двоичном коде через открыблоков элементов И соединены с соответст- тый первый 4 блок элементов И, первый 7 вующими входами и в о ами первого 7 блока элемен- блок элементов ИЛИ устанавливается во тов ИЛИ, выход которого соединен с 45 втором 8 счетчике. Первый операнд А в двоинформационным входом второго 8 счетчи- ичном коде непосредственно поступает на ка, входы задания вычитания 9 и сложения установочные входы первого 2 счетчика, С

10 устройства соединены соответственно со тактового входа 11 устройства через первый вторыми входами первого 4 и второго 6 бло- 12 и второй 18 элементы запрета тактовые ков элементов И, тактовый вход 11 устрой- 50 импульсы поступают соответственно на выединен с информационным входом читающие входы первого 2 и второго 8 счетпервого 12 элемента запрета, управляющий чиков. Пусть для определенности > вход которого соединен с первым входом тогда через В тактов содержимое второго 8 третьего13блока элементов И, выходы раз- счетчика станет равно нулю. При этом на рядов выхода первого2счетчикасоединены 55 инверсном выходе второго 20 элемента со входами разрядов первого входа четвер- ИЛИ будет сигнал, который поступит на пертого 14 блока элементов И и с соответству- . вый вход первого 21 элемента И, на втором ющими входами первого 15 элемента ИЛИ,, входе которого присутствует сигнал. Сигнал инверсный выход которо;о соединен с пер- с инверсного выхода второго 20 элемента вым входом второго 16 элемента И и с пер- ИЛИ черезтретий17элемент ИЛИ поступит !

1810889 на управляющие входы первого 12 и второго

18 элементов запрета, прекращая поступление тактовых импульсов на счетчики 2 и 8, Одновременно сигнал с выхода первого 18 элемента И поступает на вторые входы четвертого 14 блока элементов И и результат операции (А — B) через второй 22 блок элементов ИЛИ и далее через открытый третий

13 блок элементов И поступает на выход 23 устройства (на вторые входы третьего 13 блока элементов И поступает сигнал с выхода третьего 17 элемента ИЛИ). Если А < В, то результат операции — (А — В) modm образуется на выходе второго 8 счетчика и для

его коррекции необходимо провести операцию(в -(А — B)) modm которую осуществляет второй 24 преобразователь прямого кода в дополнительный код по модулю и результат операции по соответствующим цепям поступит на выход 23 устройства. Прекращение подачи тактовых импульсов на управляющие входы счетчиков 2, 8 производит в этом случае сигнал с выхода второго

16 элементов И.

Во втором режиме работы присутствует сигнал на входе 10. В этом случае второй операнд В поступает на установочные входы второго 8 счетчика через первый 5 преобразователь прямого кода в дополнительный код по. модулю, который осуществляет унарную операцию (m — В), где m — модуль устройства. Дальнейшая работа устройства аналогично первому режиму, Рассмотрим примеры выполнения модульных операций вычитания и сложения при m = 7. Пусть А = 5, В.= 3 и необходимо определить результат операции (А—

В)тоб7. Первый операнд А=101 в двоичном коде поступает на установочные входы первого 2 счетчика. Второй операнд В = 011 поступает на установочные входы второго 8 счетчика. С тактового входа 11 устройства поступают на вычитающие входы счетчиков

2, 8 три тактовых импульса. При этом на инверсном выходе второго 20 элемента

ИЛИ, будет сигнал, который приведет к образованию сигнала на выходе первого 21 элемента И. Сигнал с выхода элемента ИЛИ

17 поступит на управляющие входы элементов запрета 12, 18. Состояние первого 2 счетчика в этот момент времени будет 010, что соответствует числу 2 в двоичном представлении. Это значение по сигналу с выхода первого 21 элемента И через четвертый

14 блок элементов И, через второй 22 блок элементов ИЛИ, через третий 13 блок элементов И поступит на вьixoq 23 устройства.

Проверка: (5 — 3)mod7 -- 2mod7.

Рассмотрим пример выполнения модульной операции сложения при том же модуле. Пусть А = 2, В = 3 и необходимо стояние первого 2 счетчика будет 000, а состояние второго 8 счетчика будет 010. Далее поступление тактовых импульсов сигналом с выхода элемента ИЛИ 17 прекращается.

Сигнал с инверсного выхода первого 15 элемента ИЛИ приводит к образованию сигнала на выходе второго 16 элемента И, 20 который открывает пятый блок элементов И и предварительный результат операции поступает на второй 24 преобразователь прямого кода в дополнительный код по модулю, 25 который производит как и первый 5 преобразователь прямого кода в дополнительный код по модулю операцию (m — B)modm, т,е. на выходе второго 24 преобразователя прямого кода в дополнительный код по модулю

30 получим величину (7 — 2)mod7 = 5mod7. Зна35 чение 101 пройдет на выход 23 устройства по соответствующим цепям. Это и будет результатом операции мОдульного сложения.

Проверка (2.+ 3)mod7 =- 5mod7.

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

40 состоит в существенном повышении быстродействия выполнения модульных операций сложения и вычитания, ввиду уменьшения количества сдвигов для получения результата операции. Рассмотрим табл, 1, в которой для каждой пары операндов А и B (m = 7) запишем количество сдвигов для ее реализации в прототипе. В табл. 2 подобным образом отразим взаимосвязь между парой операндов и количеством необходимых тактов. Сравнение по быстродействию будем производить путем суммирования общего количества тактов табл.1 и 2..

Обозначим через N< и й2 сумму значений в клетках соответственно табл,1 и 2, тогда N> = 112, а Мг = 91, Выигрыш в быстродействии достигает 24 Д.

Полох ителЬиый эффект от внедрения данного изобретения состоит в том, что определить результат операции(А+ B)mod7.

Первый операнд А = 010 в двоичном коде поступает на установочные входы первого 2 счетчика. Второй операнд В = 011 поступает на вход первого 5 преобразователя прямого кода в дополнительный код по модулю, с выхода которого В = (7 — 3)mod7 = 4mod7 поступает на установочные входы второго 8

15 . счетчика. С тактового входа 11 устройства поступают на вычитающие входы счетчиков

2, 8 два тактовых импульса, после чего со1810889

Таблица 2

Таблица1

50 уменьшается стоимость машинной операции, повышается производительность средств вычислительной техники.

Достоверность достижения поставленной целИ подтверждается конкретными примерами выполнения модульных операций сложения и вычитания при m = 7.

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

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