Устройство для умножения

 

А.М. Карцев (72) Автор изобретения

Ц

Ордена Ленина институт кибернетики АН Украин .кой-ССР-: (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ

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

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

Устройство содержит прямоугольную матрицу из M(N+1) логических ячеек и (И+1) управляющих ячеек — по одной на каждом из (N+l) столбцов матрицы. Каждая управляющая ячейка состоит из двух каскадов U u V и может находиться в состоянии "1" либо нО". Ячейки

U и Ч служат для управления всеми операциями, выполняемыми соответствующим

20 столбцом. Каждая ячейка матрицы, также состоящая из двух каскадов Х и У, связана с соотве гствующей управляющей ячейкой и выраба1нвает выходные сигна2 лы D и Е в зависимости от входных сигналов А, В и С. Выходы D и Е .каждой ячейки связаны со входами соседней ячейки, а выходы ячеек крайнего стол бца подключены ко входам следующей логической или дополнительной матрицы.

Каждый столбец матрицы может быть выбран, исходя из состояния каскада

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

Известно также устройство для умножения, содержащее регистр множимого, регистр множителя, блок формирования частичных произведений и блок сумми97437 рования частичных произведений. Входы блока формирования частичных произведений соединены с выходами регистров множимого и множителя. Выходы блока формирования частичных произведений подключены ко входам блока суммирования частичных произведений, выходы которого являются выходами устройства f2 3.

Наиболее близким к предлагаемому является устройство для умножения, которое содержит регистр множимого, регистр множителя, блок формирования частичных произведений, блок суммирования частичных произведений, блок

IS поразрядного накопления переносов, сумматор с распространением переносов и регистр результата. Входы регистра результата подключены к выходам:сумматора. Первая и вторая группы входов сумматора подключены к первой группе выходов блока суммирования частичных произведений и к выходам блока поразрядного накопления переносов соответственно, Входы блока суммирования частичных произведений подключены к первой группе выходов блока формирования частичных произведений, вторая

Группа выходов которого подключена к первой группе входов блока поразряд30 ного накопления переносов, вторая группа входов которого подключена ко второй группе выходов блока суммирования частичных произведений; Первая и вторая группы входов блока формирования частичных произведений подключены к выходам регистров множимого и множителя соответственно 3 1.

Недостатками известных устройств для умножения являются большие затра-ЯО ты оборудования, значительную часть которых составляет блок формирования частичных произведений, содержащий при умножении n - -разрядных р-ичных

2 чисел (2n>- np) х2р двухвходовых элементов И, малая достоверность получаемого результата.

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

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

На фиг. 1 представлена блок-схема устройства для умножения;(на фиг. 223 показана реализация устройства для случая и =3), на фиг. 2 - структурная схема блока формирования частичных произведений; на фиг. 3 — функциональная схема матрицы умножения; на фиг. 4, 5 - функциональные схемы матриц, сложения для. р=10; на фиг. 6 - структурная схема блока суммирования частичных произведений; на фиг. 7 — функциональная схема матрицы сложения двух однородных Р-ичных чисел; на фиг. 8— структурная схема блока накопления коэффициентов; на фиг. 9, 10 и 11 функциональные схемы матриц двухвходовых элементов И и матриц многовходовых элементов И; на фиг. 12 — структурная схема блока накопления переносов на фиг. 13 — функциональные схемы матриц элементов И, реализующих блок накопления переносов; на фиг. 14структурная схема блока суммирования коэффициентов и переносов, на фиг. !51

9743

23 — функциональные схемы матриц weментов И, реализующих блок суммирования коэффициентов и переносов, выполненные для примера на диодных сборках.

Устройство содержит регистр 1 мно- жимого, регистр 2 множителя, блок 3 формирования частичных произведений, блок 4 суммирования частичных произведений, блок 5 накопления коэффициентов, блок 6 накопления переносов, Io блок 7 суммирования коэффициентов и переносов, сумматор 8 с распространением переноса, регистр 9 результата.

Входы регистров 1 и 2 подключены соответственно ко входам множимого 10 Is и множителя 1! устройства, а их выходы соединены с первым и вторым входами блока 3 соответственно. Первый выход блока 3 подключен ко входу блока

4, второй - к первому входу блока 6, 2в третий выход блока 3 — ко входу блока 5. Первый выход блока 4 соединен со вторым входом блока 6, второй выход блока 4 подключен к входу перво: го слагаемого сумматора 8. Выход бло- 2S ка 5 соединен с первым входом блока суммирования 7, второй вход которого подключен к выходу блока 6, а выходко входу второго слагаемого сумматора

8. Выход сумматора 8 соединен со вхо- зв дом регистра 9, выход последнего подключен к выходу 12 результата устройства.

Блок 3 представляет собой схему (см. Фиг. 2), включающую матрицы 14 умножения и матрицы 15 и 16 сложения двух одноразрядных чисел, причем вхо= ды 1 и 2 каждой матрицы 14 подключены к соответствующим ей входным шинам группы 1 и 2 блока 3 соответственно.

Входы 1 и 2 матриц .15, а также входы матриц 16 подключены к выходам 3 и выходам 4 матриц 14. Выходы 1 матриц

14 и 15 объединены в группу 1 выходов

45 .блока 3. Выходы 2 матриц 15 и выходы матриц 16 объединены в rpynny 2 входов блока 3. Выходы 2 матриц 14 и выходы 3 матриц 15 объединены в группу

3 выходов блока 3. Функциональные схе— мы матриц 14, 15 и 16 представлены на

50 фиг. 3, 4 и 5 соответственно для примера в счислении с основанием p=l0.

Блок 4 представляет собой многоуровневую схему (см. Фиг. 6), включающую матрицу 17 сложения двух одноразрядSS ных р-ичных чисел. Функциональная схема матрицы 17 представлена на фиг. 7 для примера для р=10.

70. d

Блок 5 представляет собой многоуровневую схему (см. Фиг. 8), включающую матрицы 18 и 19 двухвходовых элементов И, а также матрицы 20-22 многЬвходовых элементов И. функциональные схемы матриц 18-22 представлены на фиг. 911. При этом матрицы 20-22 выполнены гля примера на диодных сборках.

Блок 6 представляет собой многоуровневую схему (см. фиг. 12), включающую матрицы 23-27 двухвходовых элементов И, причем входы 1 и 2 матриц 23 подключены к входным шинам группы 1 входов блока 6. Один из входов матрицы 24 подключен к входной шине группы или группы 2 входов блока 6, а другой - к выходам матрицы 23. Входы матрицы 25 — к выходам соответствующих матриц 23. Входы матрицы 26 - к выходам соответствующих матриц 23 и

24, а входы матриц 27 — к выходам соответствующей матрицы 24 и входной шине группы 2 входов блока 6. Функци- ональные схемы матриц 23-27 представлены на фиг. 13.

- Блок 7 представляет собой группу (см. Фиг. 14) матриц 27 и 30 двухвходовых элементов И, а также .матриц 28 и 29 многовходовых элементов И. Входы 1 и 2 матрицы 27 блока 7 подключены к входным шинам О группы 1 и 2 sxoдов этого блока соответственно. Входы 1, 2 и 3 матрицы 28 подключены к входным шинам l, 2 и 3. (4, 5 и 6) группы входов блока 7, а входы 4 и 5 этой матрицы подключены к входам 1 и 2 (3 и 4) группы 2 его входов. Входы 1 матрицы 29 подключены к входной шине

7 группы 1 входов блока 7, а входы 2 и 3 матрицы 29 подключены к входным шинам 5 и 6 группы 2 входов этого блока. Входы 1 и 2 матрицы 26 подключены к входной шине 8 группы 1 входов блока 7 и входной шине 7 группы 2 его входов соответственно. Функциональные схемы матриц 28, 29 и 30 представлены на фиг. 15-23. При этом матрицы 29 и 28 выполнены для применения на диодных сборках.

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

С выходов регистров и 2 множимое и множитель поступают на входы 1 и 2 блока 3, в котором все цифры множимого умножаются на все цифры множителя одновременно. При этом на входы каждой матрицы 14 сигналы, соответствующие цифре множимого (множителя), поступают следующим образом.

7 9743

На вход с номером 1, 2, ..., -1

Р или — сигнал поступает в том случае, еСли цифра множимого (множителя) равF на —, — +1,; ., р-2 или р- ) соответственно. На вход с номером +1, — + 5

+2,, р-1 или р сигнал поступает в трм случае, если она равна О, 1, P — 2 или — 1 соответственно. На вход с номером р+1 сигнал поступает, е ли цифра находится в диапазоне О - 10 — 1 включительно, а на вход с номе1 ром р+2 - если рна находится в диапазоне значений — - - р-1 включительно.

На вход с номером р+3, р+4 и т. д. сигнал, соответствующий цифре множимо 1>

ro (множителя), поступает в том случае, если она принимает одно из двух значений О или f, 1 или T+1 и т. д.. соответственно. Например, для р=10 при умножении цифр множимого и множителя 20

8 и 9 сигналы, соответствующие этим цифрам, приходят на входы с номерами .4, 12 и 16 группы входов 1 и входы с номерами 5, 12.и 17 группы входов 2.

Выходные сигналы в отмеченном примереИ появляются на следующих выходах блока 14: на выходной шине 1 группы выходов 1, выходной шине О группы выходов

2, выходной шине 1 и выходной шине 6 группы выходов 3, выходной шине 2 и 30 еыходной шине 5 группы выходов 4 и однозначно соответствует результату умножения 8) 9=72.

С выходов матриц 14 сигналы, соответствующие правым и левым составляю-З щим результата умножения, поступают на входы матриц 15 и 16 и на выходы групп выходов 1, 2 и 3 блока 3.

На выходах матриц 15 и 16 каждая цифра представлена двумя сигналами: 40

Первый из них поступает на ши; у с номером 0 - — - 1 а второй на шину с р 2

Hove pov > as + 1 .

Результат сложения двух цифр на матрице 15 появляется на трех ее выходах. При этом известно, что на выходах групп 1 и 3 сигналы, соответствующие значению переноса 1. и значению коэффициента 5, появиться одновременно не могут. $0

С выходов 2 блока 3 сигналы, соответствующие значениям частичных произведений в данном разряде, поступают йа входы блока 4, в котором происходит их сложение на многоуровневой . И схеме, причем на входы матриц 17 этой схемы каждая цифра поступает в коде 1 из р (например, цифре О, 1, 2, 9 соответствув1 наличие сигнала на

70 8 входе с номером О, 1, ..., 9), a результат появляется на двух группах выходов. С выходов l блоков 3 и 4 сигналы, соответствующие единицам переносое из каждого разряда в соседний старший разряд, поступают на входы 1 и 2 блока 6 соответственно. С выходов

3 блока 3 сигналы, соответствующие ко.эффициентам О или данного разряда поступают на входы блока 5. Сложение частичных произведений в блоке 4, накопление коэффициентов в блоке 5 и накопление переносов в блоке 6 осуществляется практически одновременно.

Значения коэффициентов каждого разряда, образование на выходах блока 5, и переносов в соседний старший разряд, накопленных в блоке 6, суммируются в блоке 7. При этом максимально возможная сумма в одном из разрядов для рассмотренного примера (и =3) составляет +8, т. е. для p=10 - число 13. Поскольку максимально возможная цифра одного р-ичного разряда составляет р-1, то этот факт говорит о том, что предложенное устройство целесообразно использовать для значений р>16 (так, при р=16 и п =3 максимально возможная сумма коэффициентов и переносов составляет 8+8=16). Кроме того; число выходов блока 7 превышает максимально возможное значение в одном разряде и составляет — +9, поэтому появление сигнала на выходе блока 7 с максимальным номером может быть использовано как признак ошибки результата. Эта шина на вход сумматора 8 не заводится и самостоятельной группой 2 выходов подается на выход устройства. Значения сумм каждого разряда, образованные на выходах 2 блока 4, а также значения сумм коэффициентов этого разряда с переносами из соседнего младшего разряда суммируются на сумматоре 8, с выходов которого результат поступает на регистр 9 результата.

Общие аппаратурные затраты на реализацию предлагаемого устройства для умножения составляют

A„=ri pp — + (np-и )(„-р +8) +p„ p +

i о, где Dq, О и 0 - число элементарных компонентов, необходимых для поСтроения блоков накопления переносов, накопления коэффициентов и суммирования коэффициентов и переносов соответственно.

9 9743

Общие аппаратурные затраты на реализацию устройства-прототипа составляют:

А = (Зп -2пР)2р +О„

Экономию от внедрения предлагаемо- 3 го устройства для умножения можно определить из следующего выражения:

Э=А 2 -А1

Поскольку для рассмотренного в описании случая (пР=3) значения О, О и14

Dy определены как D„=71, 0 =348, О>=

=1820, то для этого случая положительный эффект от внедрения предлагаемого устройства по сравнению с устройствомпрототипом при p=32 и. p=64 составляет1

Э=10840 и Э=50008 элементарных компонентов соответственно. . Таким образом, в предлагаемом устройстве затраты оборудования меньше, чем в устройстве-прототипе и, кроме, того, достоверность его функционирования выше за счет наличия признака достоверности получаемого решения.

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

Устройство для умножения, содержащее регистр множимого, регистр множи-- Ю теля,блок формирования частичных про.изведений, блок суммирования частичных произведений, блок накопления переносов, сумматор с распространением переноса и регистр результата, причем3ф входы регистров множимого и множителя подключены соответственно ко входам множимого и множителя устройства, выходы регистров множимого и множителя подключены соответственно к первому 40 и второму входам блока формирования частичных произведений, первый выход

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

Источники информации, принятые во внимание при экспертизе

1. Патент CNA М 3584205, кл. G 06 F 7/39, опублик. 1977.

2. Прангишвили И. В. и др. Микроэлектроника и однородные структуры для построения логических и вычислительных устройств. И., "Наука", 1967, с. 180.

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

11 739531, кл. 6 06 F 7/52 ° 1979 (прототип).