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

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

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

На чертеже представлена структурная схема устройства.

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

- второй информационный вход устройства, 4 - первый блок элементов И, 5 - первый преобразователь прямого кода в дополнительный код по модулю, 6 - второй блок элементов И, 7 - первый блок элементов ИЛИ, 8 - второй счетчик, 9 - вход задания вычитания устройства, 10 - вход задания сложения устройства, 11 - тактовый вход устройства, 12-первый элемент запрета, 13

- третий блок элементов И, 14 - четвертый блок элементов И, 15. - первый элемент ИЛИ, 16 - второй элемент И, 17 - третий элемент ИЛИ, 18 - второй элемент запрета, 19 - пятый блок элементов И, 20 - второй элемент ИЛИ, 21 - первый элемент И, 22 - второй блок элементов ИЛИ, 23 - выход устройства, 24 - второй преобразователь прямого кода в дополнительный код по модулю.

Первый 1 информационный вход устройства соединен с информационным входом первого счетчика 2, второй 3 информационный вход устройства соединен с первым входом первого 4 блока элементов И и со входом первого 5 преобразователя прямого кода в дополнительный код по модулю, выход которого соединен с первым входом второго 6 блока элементов И, выходы первого 4 и второго 6 блоков элементов И соединены с соответствующими входами первого 7 блока элементов ИЛИ, выход которого соединен с информационным входом второго 8 счетчика, входы задания вычитания 9 и сложения 10 устройства соединены соответственно со вторыми входами первого 4 и второго 6 блоков элементов И, тактовый вход 11 устройства соединен с информационным входом первого 12 элемента запрета, управляющий вход которого соединен с первым входом третьего 13 блока элементов И, выходы разрядов выхода первого 2 счетчика соединены со входами разрядов первого входа четвертого 14 блока элементов И и с соответствующими входами первого 15 элемента ИЛИ, инверсный выход которого соединен с первым входом второго 16 элемента И и с пер0

5

0

5

0

5

0

5

0

5

вым входом третьего 17 элемента ИЛИ, выход которого соединен с управляющими входами первого 12 и второго 18 элементов запрета, тактовый вход 11 устройства соединен с информационным входом второго 18 элемента запрета, выходы разрядов второго 8 счетчика соединены со входами разрядов первого входа пятого 19 блока элементов И и с соответствующими входами второго 20 элемента ИЛИ, инверсный выход которого соединен со вторым входом третьего 17 элемента ИЛИ и с первым входом первого 21 элемента И, выход которого соединен со вторым входом четвертого 14 блока элементов И, выход которого соединен с первым входом второго 22 блока элементов ИЛИ, выход которого соединен со вторым входом третьего 13 блока элементов И, выход которого является выходом 23 устройства выходы первого 12 и второго 18 элементов запрета соединены соответственно с вычитающими входами первого 2 и второго 8 счетчиков, прямые выходы первого 15 и второго 20 элементов ИЛИ соединены соответственно со вторыми входами первого 21 и второго 16 элементов И, выход второго 16 элемента И соединён со вторым входом пятого 19 блока элементов И, выход которого соединен со входом второго 24 преобразователя прямого кода в дополнительный код по модулю, выход которого соединен со вторым входом второго 22 блока элементов ИЛИ.

Работу устройства удобно рассматривать в двух режимах:. 1) режим определения результата операции модульного вычитания, 2) режим определения результата операции модульного сложения. В первом случае присутствует сигнал на шине 9 и второй операнд в 8 двоичном коде через открытый первый 4 блок элементов И, первый 7 блок элементов ИЛИ устанавливается во втором 8 счетчике. Первый операнд А в двоичном коде непосредственно поступает на установочные входы первого 2 счетчика, С тактового входа 11 устройства через первый 12 и второй 18 элементы запрета тактовые импульсы поступают соответственно на вычитающие входы первого 2 и второго 8 счетчиков. Пусть для определенности А В, тогда через В тактов содержимое второго 8 счетчика станет равно нулю. При этом на инверсном выходе второго 20 элемента ИЛ И будет сигнал, который поступит на первый вход первого 21 элемента И, на втором , входе которого присутствует сигнал. Сигнал с инверсного выхода второго 20 элемента ИЛИ через третий 17 элемент ИЛ И поступит

на управляющие входы первого 12 и второго 18 элементов запрета, прекращая поступление тактовых импульсов на счетчики 2 и 8. Одновременно сигнал с выхода первого 18 элемента И поступает на вторые входы четвертого 14 блока элементов И и результат операции ( А - В) через второй 22 блок элементов ИЛИ и далее через открытый третий 13 блок элементов И поступает на выход 23 устройства (на вторые входы третьего 13 блока элементов И поступает сигнал с выхода третьего 17 элемента ИЛИ). Если А В, то результат операции - (А - В) modm образуется на выходе второго 8 счетчика и для его коррекции необходимо провести опера- (А-В) modm которую осуществляет второй 24 преобразователь прямого кода в дополнительный код по модулю и результат операции по соответствующим цепям поступит на выход 23 устройства. Прекращение подачи тактовых импульсов на управляющие входы счетчиков 2, 8 производит в этом случае сигнал с выхода второго 16 элементов И.

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

Рассмотрим примеры выполнения модульных операций вычитания и сложения при m 7. Пусть А 5, В 3 и необходимо определить результат операции (А - B)mod7. Первый операнд А 101 в двоичном коде поступает на установочные входы первого 2 счетчика. Второй операнд В 011 поступает на установочные входы второго 8 счетчика. С тактового входа 11 устройства поступают на вычитающие входы счетчиков 2, 8 три тактовых импульса. При этом на инверсном выходе второго 20 элемента ИЛИ, будет сигнал, который приведет к образованию сигнала на выходе первого 21 элемента И. Сигнал с выхода элемента ИЛИ 17 поступит на управляющие входы элементов запрета 12, 18. Состояние первого 2 счетчика в этот момент времени будет 010, что соответствует числу 2 в двоичном представлении. Это значение по сигналу с выхода первого 21 элемента И через четвертый 14 блок элементов И, через второй 22 блок элементов ИЛИ, через третий 13 блок элементов И поступит на выход 23 устройства. Проверка: (5 - 3)mod7 2mod7.

Рассмотрим пример выполнения модульной операции сложения при том же мо- 5 дуле. Пусть А 2, В 3 и необходимо определить результат операции (А + B)mod7. Первый операнд А 010 в двоичном коде поступает на установочные входь первого 2 счетчика. Второй операнд В 011 поступает

® на вход первого 5 преобразователя прямого кода в дополнительный код по модулю, с выхода которого в -{7 - 3)mod7 4mod7 поступает на установочные входы второго 8 счетчика. С тактового входа 11 устройства поступают на вычитающие входы счетчиков 2, 8 два тактовых импульса, после чего состояние первого 2 счетчика будет 000, а состояние второго 8 счетчика будет 010. Далее

Q поступление тактовых импульсов сигналом с выхода элемента ИЛИ 17 прекращается. Сигнал с инверсного выхода первого 15 элемента ИЛИ приводит к образованию сигнала на выходе второго 16 элемента И,

5 который открывает пятый блок элементов И и предварительный результат операции поступает на второй 24 преобразователь прямого кода в дополнительный код по модулю, который производит как и первый 5 преоб0 разователь прямого кода в дополнительный код по модулю операцию (m - B)modm, т.е. на выходе второго 24 преобразователя прямого кода в дополнительный код по модулю (получим величину (7 - 2)mod7 5mod7. Зна5. чение 101 пройдет на выход. 23 устройства по соответствующим цепям. Это и будет результатом операции модульного сложения. Проверка (2 .+ 3)mod7 5mod7.

Техническое преимущество заявляемо0 го изобретения в сравнении с прототипом состоит в существенном повышении быстродействия выполнения модульных операций сложения и вычитания, ввиду уменьшения

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

5 Обозначим через NI и N2 сумму значений в клетках соответственно табл.1 и 2, тогда NI 112, а N2 91. Выигрыш в быст- родействии достигает 24%.

Положительный эффект от внедрения данного изобретения состоит в том, что

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

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

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

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

и

10

15

20

25

30

35

40

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

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