Устройство для умножения Советский патент 1982 года по МПК G06F7/52 

(S) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ

Изобретение относится к вычисли- тельной технике и может быть использовано при умножении чисел, в частности в системах счисления с большими основаниями. Известны устройства, в которых выполнение арифметических и логических операций осуществляется путем обращения, к матрице, представляющие собой программируемый блок для выполнения арифметических и логических операций. Устройство содержит прямоугольную мат рицу из M(N+I) логических ячеек и (N+I) управляющих ячеек - по одной на каждом из (N+I) столбцов матрицы. Каждая управляющая ячейка состоит из двух каскадов U и V и может находиться в состоянии 1 либо О. Ячейки и и V служат для управления всеми операциями, выполняемыми соответствующим столбцом. Каждая ячейка матрицы, также состоящая из двух каскадов X и Y, связана с соответствующей управляющей ячейкой и вырабатывает выходные сигна лы D и Е В зависимости от входных сигналов А, В и С. Выходы D и Е -каждой ячейки связаны со входами соседней ячейки, а выходы ячеек крайнего подключены ко входам следующей логической или дополнительной матрицы. Каждый столбец матрицы может быть выбран, исходя из состояния каскада и управляющей ячейки, с целью выполнения соответствующей арифметической или логической операции. Кроме того выбор соответствующего столбца может быть осуществлен, исходя из состояния каскада V: во-первых, в результате реализации каскада U и V логических функций И или ИЛИ в случае выполнения логической операции и, во-вторых, путем подачи двоичного сигнала на вход столбца в случае выполнения арифметических операций flj . Известно также устройство для умножения, содержащее регистр множимого, регистр множителя, блок формирования частичных произведений и блок суммирования частичных произведений. Вход блока формирования частичных произве дений соединены с выходами регистров множимого и множителя. Выходы блока формирования частичных произведений подключены ко входам блока суммирова ния частичных произведений, выходы которого являются выходами устройства 2 . Наиболее близким к предлагаемому является устройство для умножения, ко торое содержит регис;тр множимого, ре гистр множителя, блок формирования частичных произведений, блок суммиро вания частичных произведений, блок поразрядного накопления переносов, сумматор с распространением переносо и регистр результата. Входы регистра результата подключены к выходам тсумматора. Первая и вторая группы входо сумматора подключены к первой группе выходов блока суммирования частичных произведений и к выходам блока поразрядного накопления переносов соответственно. Входы блока суммирования частичных произведений подключены к первой группе выходов блока формирования частичных произведений, вторая Группа выходов которого подключена к первой группе входов блока поразрядного накопления переносов, вторая группа входов которого подключена ко второй группе выходов блока суммирования частичных произведений. Первая и вторая группы входов блока формирования частичных произведений подключены к выходам регистров множимого и множителя соответственно ( 3 Недостатками известных устройств для умножения являются, большие затраты оборудования, значительную часть которых составляет блок формирования частичных произведений, содержащий при умножении пр- разрядных р-ичных чисел (2пр-Пр)х2р двухвходовых элементов И, малая достоверность получаемого результата. Цель изобретения - уменьшение затрат оборудования за счет уменьшения числа двухвходовых элементов И блока формирования частичных произведений, а также повышение достоверности результата умножения. Поставленная цель достигается тем что устройство для умножения, содержащее регистр множимого, регистр множител, блок формирования частичных произведений,-блок суммирования частичных произведений, блок накопления 97 переносов, сумматор с распространением переноса и регистр результата, причем входь регистров множимого и МНО-. жителя подключены соответственно ко входам множимого и множителя устройства, выходы регистров множимого и множителя подключены соответственно к первому и второму входам блока формирования частичных произведений, первый выход которого подключен ко входу блока суммирования частичных произведений, а второйк первому входу.блока накопления переносов, второй вход которого подключен к первому выходу блока суммирования частичных произведений, второй выход которого подключен ко входу первого слагаемого сумматора с распространением переноса, выход которого подключен ко входу регистра результата, выход последнего подключен к выходу результата устройства, содержит блок накопления коэффициентов и блок суммирования коэффициентов и переносов, причем вход блока накопления коэффициентов соединен с третьим выходом блока суммирования частичных произведений, выход блока накопления коэффициентов подключен к первому входу блока суммирования коэффициентов и переносов, второй вход которого подключен к выходу блока накопления переносов, а выход блока суммирования коэффициентов и переносов подключен ко входу второго слагаемого сумматора с распространением переноса. На фиг. 1 представлена блок-схема устройства для умножения; (на фиг. 223 показана реализация устройства для случая ),на фиг. 2 - структурная схема блока формирования частичных произведений; на фиг. 3 - функциональная схема матрицы умножения-, на фиг. k, 5 - функциональные схемы матриц, сложения для- , на фиг. 6 - структурная схема блока суммирования частичных произведений; на фиг. 7 функциональная схема матрицы сложения двух Однородных Р-ичных чисел; на фиг. 8структурная схема блока накопления коэффициентов; на фиг. 9. Ю и 11 функциональные схемы матриц двухвходовых элементов И и матриц многовходовых э-лементов И; на фиг. 12 - структурная схема блока накопления переносов-; на фиг. 13 - функциональные схемы матриц элементов И, реализующих блок накопления переносов; на фиг. l структурная схема блока суммирования коэффициентов и переносов; на фиг. 155 . 37 23 функциональные схемы матриц элементов И, реализующих блок суммирования коэффициентов и переносов, выполненные для примера на диодных сборках Устройство содержит регистр 1 множимого, регистр 2 множителя, блок 3 формирования частичных произведений, блок t суммирования частичных произве дений, блок 5 накопления коэффициентов, блок 6 накопления переносов, блок 7 суммирования коэффициентов и переносов, сумматор 8 с распространением переноса, регистр 9 результата. Входы регистров 1 и 2 подключены соответственно ко входам множимого 10 и множителя 11 устройства, а их выходы соединены с первым и вторым входами блока 3 соответственно. Первый выход блока 3 подключен ко входу блока k, второй - к первому входу блока 6, третий выход блока 3 - ко входу блока 5. Первый выход блока t соединен со вторым входом блока 6, второй выход блока подключен к входу первого слагаемого сумматора 8. Выход блока 5 соединен с первым входом блока суммирования 7, второй вход которого подключен к выходу блока 6, а выход ко входу второго слагаемого сумматора 8. Выход сумматора 8 соединен со входом регистра 9. выход последнего подключен к выходу 12 результата устройства. Блок 3 представляет собой схему (см. фиг. 2), включающую матрицы И умножения и матрицы 15 и 16 сложения двух одноразрядных чисел, причем входы 1 и 2 каждой матрицы подключены к соответствующим ей входным шинам группы 1 и 2 блока 3 соответственно. Входы 1 и 2 матриц 15. а также входы матриц 16 подключены к выходам 3 и выходам i матриц 1Д. Выходы 1 матриц 1 и 15 объединены в группу 1 выходов блока 3. Выходы 2 матриц 15 и выходы матриц 16 объединены в группу 2 входов блока 3- Выходы 2 матриц 1 и выходы 3 матриц 15 объединены в группу 3 выходов блока 3- Функциональные схе мы матриц I, 15 и 16 представлены на фиг. 3, и 5 соответственно для примера в счислении с основанием . Блок представляет собой многоуро вневую схему (см. фиг. 6), включающую матрицу 17 сложения двух одноразряд ных р-ичных чисел. Функциональная схе ма матрицы 17 представлена на фиг. 7 для примера для . 0 Блок 5 представляет собой многоуровневую схему (см. фиг. 8), включающую матрицы 18 и 19 двухвходовых элементов И, а также матрицы 20-22 MHort)Bxoдовых элементов И. Функциональные схемы матриц 18-22 представлены на фиг. Э 11. При этом матрицы 20-22 выполнены примера На диодных сборках. Блок 6 представляет собой многоуровневую схему (см. фиг. 12), включающую матрицы двухвходовых элементов И, причем входы 1 и 2 матриц 23 подключены к входным шинам группы 1 входов блока 6. Один из входов матрицы 2i подключен к входной шине группы 1 или группы 2 входов блока 6, а другой - к выходам матрицы 23. Входы матрицы 25 - к выходам соответствующих матриц 23. Входы матрицы 2б - к выходам соответствующих матриц 23 и 2k, а входы матриц 27 - к выходам соответствующей матрицы 2Ц и входной шине группы 2 входов блока 6. Функциональные схемы матриц 23-27 представлены на фиг. 13. - Блок 7 представляет собой группу (см. фиг. 1) матриц 27 и 30 двухвходовых элементов И, а также матриц 28 и 29 многовходовых элементов И. Входы 1 и 2 матрицы 27 блока 7 подключены к входным шинам О группы 1 и 2 входов этого блока соответственно. Входы 1 , 2 и 3 матрицы 28 подключены к входным шинам 1, 2 и 3- С. 5 и 6) группы входов блока 7 а входы и 5 этой матрицы подключены к входам 1 и 2 (3 и ) группы 2 его входов. Входы 1 матрицы 29 подключены к входной шине 7 группы 1 входов блока 1, а входы 2 и 3 матрицы 29 подключены к входным шинам 5 и 6 группы 2 входов этого блока. Входы 1 и 2 матрицы 2б подключены к входной шине 8 группы 1 входов блока 7 и входной шине 7 группы 2 его входов соответственно. Функциональные схемы матриц 28, 29 и 30 представлены на фиг. . При этом матрицы 29 и 28 выполнены для применения на диодных сборках. Устройство работает следующим образом. С выходов регистров 1 и 2 множимое и множитель поступают на входы 1 и 2 блока 3, в котором все цифры множимого умножаются на все цифры множителя одновременно. При этом на входы каждой матрицы 1 сигналы, соответствующие цифре множимого (множителя), поступают следующим образом. На вход с номером , 2, ..., - или - сигнал поступает в том случае если цифра множимого (множителя) равна -, , .., р-2 или р-L соответственно. На вход с номером Т +2, .., р-1 или р сигнал поступает в TJDM случае, если она равна О, 1, .., j- 2 или - - 1 соответственно. На вход с номером р+1 сигнал поступает, цифра находится в диапазоне О - - 1 включительно, а на вход с номером р+2 - если -рна находится в диапазоне значений - - р-1 включительно. На вход с номером р+3, р+ и т. д. сигнал, соответствующий цифре множимо го (множителя), поступает в том случае, если она принимает одно из двух значений О или -j-, 1 или и т. д. соответственно. Например, для умножении цифр множимого и множителя 8и 9 сигналы, соответствующие этим цифрам, приходят на входы с номерами Л, 12 и 16 группы входов 1 и входы с номерами 5, 12 и 17 группы входов 2. Выходные сигналы в отмеченном примере появляются на следующих выходах блока на выходной шине 1 группы выхо дов 1, выходной шине О группы выходов 2, выходной шине 1 и выходной шине 6 группы выходов 3, выходной шине 2 и выходной шине 5 группы выходов и од нозначно соответствует результату умножения 8). С выходов матриц Т сигналы, соответствующие правым и левым составляющим результата умножения, поступают на входы матриц 15 и 16 и на выходы групп выходов 1, 2 и 3 блока 3На выходах матриц 15 и 16 каждая цифра представлена двумя сигналами; Первый из wx поступает на с номером О Т, У U второй на шину с номером -я- или -2-+1. Результат сложения двух цифр на матрице 15 появляется на трех ее выходах. При этом известно, что на выходах групп 1 и 3 сигналы, соответствующие значению переноса 1 и значению коэффициента S, появиться одновременно не могут. С выходов 2 блока 3 сигналы, соответствующие значениям частичных про изведений в данном разряде, поступают на входы блока k, в котором происходит их сложение на многоуровневой схеме, причем на входы матриц 17 этой схемы каждая цифра поступает в коде 1 из р (например, цифре О, 1, 2, ..., 9соответствует наличие сигнала на входе с номером О, 1, ..., 9), а результат появляется на двух группах выходов. С выходов 1 блоков 3 и 4 сигналы, соответствующие единицам переносов из каждого разряда в соседний старший разряд, поступают на входы 1 и 2 блока 6 соответственно. С выходов 3 блока 3 сигналы, соответствующие коэффициентам О или - данного разряда поступают на входы блока 5. Сложение мастичных произведений в блоке k, накопление коэффициентов в блоке 5 и накопление переносов в блоке 6 осуществляется практически одновременно. Значения коэффициентов каждого разряда, образование на выходах блока 5, и переносов в соседний старший разряд накопленных в блоке 6, суммируются в блоке 7- При этом максимально возможная сумма в одном из разрядов для расс отреннрго примера () составляет , т. е. для - число 13-. Поскольку максимально возможная цифра одного р-ичного разряда составляет р-1, то этот факт говорит о том, что предложенное устройство целесообразно использовать для значений (так, при и п 3 максимально возможная сумма коэффициентов и переносов составляет ). Кроме того; число выходов блока 7 превышает максимально возможное значение в одном разряде и составляет -24-9 поэтому появление сигнала на выходе блока 7 с максимальным номером может быть использовано как признак ошибки результата. Эта шина на вход сумматора 8 не заводится и самостоятельной группой 2 выходов подается на выход устройства. Значения сумм каждого разряда, образованные на выходах 2 блока 4, а также значения сумм коэффициентов этого разряда с переносами из соседнего младшего разряда суммируются на сумматоре 8, с выходов которого результат поступает на регистр 9 результата. Общие аппаратурные затраты на реализацию предлагаемого устройства для умножения составляют А,п2р2 + ()(|рП8) +D,Dif Оэ где D-t, Dj и Оз элементарных компонентов, необходимых для пойтроения блоков накопления переносов, накопления коэффициентов и суммирования коэффициентов и переносов соответственно. Общие аппаратурные затраты на реализацию устройства-прототипа состав ляют: A.i () Экономию от внедрения предлагаемо го устройства для умножения можно оп ределить из следующего выражения: 2 -А:, Поскольку для рассмотренного в опи сании случая () значения D-i, Dj определены как , D,, Dj 1820, то для этого случая положител ный эффект от внедрения предлагаемого устройства по сравнению с устройством прототипом при и. составляет Э 1084о и 3 50008 элементарных компонентов соответственно. Таким образом, в предлагаемом устройстве затраты оборудования меньше, чем в устройстве-прототипе и, кроме ,. того, достоверность его функционирования выше за счет наличия признака достоверности получаемого решения. Формула изобретения Устройство для умножения, содержащее регистр множимого, регистр множителя,блок формирования частичных произведений, блок суммирования частичных произведений, блок накопления переносов , сумматор с распространением переноса и регистр результата, причем входы регистров множимого и множителя подключены соответственно ко входам множимого и множителя устройства, выходы регистров множимого и множителя подключены соответственно к первому и второму входам блока формирования частичных произведений, первый выход которого подключен ко входу блока суммирования частичных произведений, а второй - к первому входу блока накопления переносов, второй вход которого подключен к первому выходу блока суммирования частичных произведений, второй выход которого подключен ко входу первого слагаемого сумматора с распространением переноса, выход которого подключен ко входу регистра результата, выход которого подключен к выходу результата устройства, отличающееся тем, что, с целью уменьшения затрат оборудования и повышения достоверности результата умножения, устройство содержит блок накопления коэффициентов и блок суммирования коэффициентов м переносов, причем вход блока накопления коэффициентов соединен с третьим выходом блока суммирования частичных произведений , выход блока накопления коэффициентов подключен к первому входу блока суммирования коэффициентов и переносов , второй вход которого подключен к выходу блока накопления переносов, выход блока суммирования коэффициентов и переносов подключен ко входу второго слагаемого сумматора с распространением переноса. Источники информации, принятые во внимание при экспертизе 1.патент США № , кл. G Об F 7/39, опублик. 1977. 2.Прангишвили И. В. и др. Микроэлектроника и однородные структуры для построения логических и вычислительных устройств. М., Наука, 19б7, с. 180. 3.Авторское свидетельство СССР 739531 кл. G 06 F 7/52, 1Э79 (прототип).

Г.

I 1 iI г I

1J

1

u.

4

13

i t2

Фиг.1

t

t

У

5

1

«о

v:iv

V

r CM

V4

i

N

КЗ

5

1

ЧК

дч

55

K

Уч

V

S

s

r

й

ffiJ

Г7-Г

-w

Г-К fHC

гЭ

OTI

г б

r

. Cv