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

(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ДВОИЧНЫХ ЧИСЕЛ

t. .

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

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

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

Наиболее близким к изобретению по техническому решению является устройство, содержащее матрицу N x(N-1) полных одноразрядных сумматоров (где N - разрядность операндов), матрицу NxN элементов И, 2N- разрядный сумматор, причем выходпереноса полного одноразрядного сумматора j-ro столбца i-й строки соединен с входом переноса полного одноразрядного сумматора (j+l)-ro сталбца (|+1)-й строки, где ,...,M-l,

(N-1), выход ууммы а,Ь-го полного одноразрядного сумматора соединен с входом суммл (а+1)у Ь-го полного одноразрядного сумматора (где ,...,N-1, ,...,М-1), выход реноса полного одноразрядного сумматора (N-1) -и строки с-го столбца соединен с входом переноса полного одноразрядного сумматора строки

,5 (с+1)-го столбца, где ,...,М-1, первые входы элементов И соединены соответственно с разрядными входными шинами множимого устройства, вторые входы элементов И соединен) со-

20 ответственно с разрядными входными шинами множителя устройства, выходы элементов И (я+1)-й диагонали матрицы элементов И (где ,...2N-2) соединены соответственно с входа а{ первых К полных одноразрядных суЧматрров У-го столбца (где ,.,., .. j М), где % iJTL: hжайшее целое меньшее или равноеan- вес разряда произведения, шходы 2Н-разрядного сумматора являют ся вькодами устройства t21. Недостатками зтого устройства яв ляются: -избыточное количество основных и дополнительных выводов устройства -недостаточное быстродействиеj отсутствие возможности вынесения из устройства 2М-разрядного сум waTopa в качестве внешнего автономного узла, что позволяет сзкономить количество выводов в устройстве. Цель изобретения - расширение функциональных возможностей за счет выполнения операции суммирования 2М-разрядного слагаемого, повышение быстродействия. Поставленная цель достигается тем, что в устройство введены 2N элементов памяти, причем выход пере носа полного одноразрядного сумматора (Н-2)-й строки d-ro столбца соединен с входом переноса полного одноразрядного сумматора (М-1)-й строки (d+l)-ro столбца {где d М/2-1 ,... ,М-2) , выход переноса пол ного одноразрядного сумматора (Н-З) строки е-го столбца соединен с входом cyMhbi полного одноразрядного сумматора (N-l)-u строки (е+1)-го столбца (где ,...,М-3), выходы выходных полных одноразрядных сумматоров соединены соответственно с входами (2N-1) старших элементов памяти, выход элемента И первой диагонали матрищл элементов И соединен с входом младшего элемента памяти, выходы 2N элементов памяти соединены соответственно с входами первой группы 2М-разрядного сумматора, входы второй группы которого являются входами суммирования устройства, вход переноса полного одноразрядного сумматора последней строки (М/2+1)-го столбца является входом округления устройства. На фиг. 1 представлена функциональная схема восьмиразрядного устр ства для умножения двоичных чисел, на 4мг. 2 - то же, матрицы умножеНИН, на фиг. 3 - структурная схема,. иллюстрирующая работу устройства. Устройство содержит элементы И 1, матрицу 2 полных одноразрядных сумматоров 3, 2М-разрядный сумматор 4, шины 5 множимого, шины 6 множителя, вход 7 управления, входы 8 суммирования, вход 9 округления, выходы 10 устройства, элементы 11 памяти. Устройство для умножения шестнадцатиразрядных чисел состоит из четырех модулей умножителей 12-15 восьмиразрядных чийел, кая:дь1й из которых содержит матрицу 16, включающую элементы И, регистры 17, шестнадцатиразрядный сумматор 4, выходной регистр 18, выход 19 переноса и вход 20 управления. Матрица 16, регистр 17 и сумматор 4 разделены, пунктиром на старшую и младшую части. В устройстве выход переноса полного одноразрядного сумматора 3j-го столбца i-и строки соединен с входом переноса полного одноразрядного сумматора 3 (j+l)-ro столбца (1+1)-й СТРОКИ гдеj 1,...,М-1, (N-1), ,...,N выход суммы а,Ь-го полного одноразрядного сумматора 3 соединен с входом суммы (а+1), Ь-го полного сумматора 3 (где ,..., N-1, ,...,М-1), выход переноса полного одноразрядного сумматора 3 (N-1)-й строки С-го столбца сое- динен с входом переноса полного одноразрядного сумматора 3 N-й строки (с+1)-го столбца где ,...,М-1 первые входы элементов И 1 соединены соответственно с разрядными вход№лмк шинами 5 множимого устройства, вторые входы элементов И 1 соеданены соответственно с разрядными входными шинами 6 множителя устройства, выходы элементов И I (q-fl)-й диагонали матрицы элементов И 1 (где ,...,2N-2) соединены соответственно с входами первых К полных одноразрядных сумматоров 3 V-ro столбца (где ...,M), где K liiLr nr 1«. ..lUl ближайшее целое меньшее или равное п/2, an- вес разряда произведения, выходы 2М-разрядного сумматора 4 являются выходами 10 устройства, выход переноса полного одноразрядного сумматора 3 (М-2)-й строки d-ro столбца соединен с

входом переноса полного одноразрядного С5тматора 3 (М-1)-й строки ( столбца (где d :M/2-1 ,..., М-2), выход переноса полного одноразрядного сумматора 3 (М-З)-й, строки е-го столбца соединен с входом суммы полного одноразрядного сумматора 3 (М-1)-й строки (е+1)-го стопица (где ,...,М-3), выходы выходных полных одноразрядных сумматоров 3 соединены соответственно с входами (2N-1) старших элементов 11 памяти, выход элемента И 1 первой диагонали матрицы элементов И 1 соединен с входом младшего элемента 11 памяти, ш 1ходы 2N элементов 11 памяти соединены соответственно с входами первой группы 2М-разрядного сумматора 4, входы 8 второй группы которого являются входами суммирования устройства, вход переноса полного одноразрядного сумматора последней строки (M/2+t)-ro столбца является входом 9 округления устройства.

Реализация устройства может быть выполнена в виде модуля. В матрице 2 полных одноразрядных сумматоров 3 непосредственно выполняется перемножение двух N-разрядных чисел, которая может быть вьщелена в виде автономного устройства, а 2Ы-разрядный сумматор 4 может быть либо включен в состав устройства умножения при его реализации в виде БИС с целью исключения дополнительного оборудования при объединении модулей, либо вьщелен из БИС с целью экономии выводов.

Введение элементов 11 памяти в сочетании с размещением дополнительных входов по краям матрицы 1 позволяет легко осуществить конвейерный режим умножения при объединении модулей с целью расширения разрядной сетки сомножителей.

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

На вход модуля 12 поступают X-J.Q и разряды сомножителей, на вход модуля 13 X-j.QH Yvg.g, на вход модуля 14 и Y, и на вход модуля 15 и Y|g-. В каждой матрице 16 на элементах И выполняется логическое умножение разрядов сомножителей, после чего непосредственно в матрице 2 полных одноразрядных

сумматоров 3 выполняется поразрядное сложение логических произведений и распространение сигнала переноса вдоль матрицы 2 за время, равное 2(N-1)f где f г- время распространения сигнала в полном одноразрядном сумматоре 3.

Для разрядов зто составит 14. По первому такту, поступающему на вход 7-1 , полученные произведения Р,, Pg. , P;5to Pif-o з п°минаются в регистрах 17. С выходов регистров 17 произведения поступают на соответствующие входы сумматоров

4 с сдвигом влево частичных произведений, обусловленным алгоритмом перемножения. При сложении частичных произведений в сумматорах 4 сигнал переноса с выхода 19 образуется только в сумматоре 4 модуля 14. Сигнал переноса на выходе 19 модуля 13 отсутствует, так как в нем производится сложение старшей части произведения, сформированной моДулем 12, и младшей части произведения, формируемой модулем 13.

При этом в выходном сумматоре 4 устройства при формировании произведения сигнал переноса отсутству-

ет. В устройстве сигнал переноса возникает в выx. сумматоре 4 только в момент сложения частичных произведений при объединении модулей, при этом сигнал переноса с выхода 19 модуля 14 поступает на вход 8 модуля 15.

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

Объединений модулей осуществляетбя подключением выходов 10 старших разрядов произведения модуля 12 к входам 8 модуля 13, при этом выходы 10 модуля 13 соединены с входами 8 модуля 14 и т.д.

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

Конвейерная структура шестнадцатиразрядного умножителя, составленнал из восьмиразрядных модулей, тре бует равенства временных соотношений в ступенях конвейера. Поэтому, с целью выравнивания переходного процесса в ступенях, суммйтоуы 4 могут быть выполнены по схеме с гру повым перенос 4. Таким образом, в результате новой организации связей в матрице по ных одноразрядных сумматоров, введе ния дополнительных входов в 2М-разрядный румматор, общее количество выходов и входов становится на два меньше, чем в известном устройстве, уменьшается время умножения на время задержки одноразрядного сумматора, осуществлен конвейерный принцип умножения при объединении модулей, получена возможность дополнительного сложения в М-разрядном умножителе 2М-разрядного яясла с 2N-pa3рядным произведением. При объединенш модулей получена возможность уменьшения щ емени умножения. Модульная структура устройства для умножения позволяет ориентировать реализацию устройства в виде вис; : Формула изобретения Устройство для умножения двоичных чисел, содержащее матрицу NX x(N-l) полных одноразрядных сумматоров (где N - разрядность операндов), матрицу NxMJ элементов И, 2Nразряд|&1й сумматор,спричем выход переноса полного одноразрядного сум матора j-ro столбца соединен с входом переноса полного одноразрядного сумматора (j+1) -го столбца, где ,...,M-1, M-2(N-1), выход сумьш аЬ-го полного одноразрядного сумматора соединен с входом суммы {а+1) Ь-го полного одноразрядного сумматора (где ae1,,..,N-1, ,.. М-1), выход переноса полного одноразрядного сумматора (М-1)-й строки с-го столбца соединен с входом пере носа полного одноразрядного сумма-, тора N-й строки (с+1)-го столбца, где ,... ,М-1), первые входы эл ментов И соединены соответственно с разрядшлми входными шинами миожимого устройства, вторые входы элементов И соединены соответственно с разрядными входными шинами множителя устройства, выходы элементов И (q+1)-й диагонали матрицы элементов И (где ,...,2N+1) соединены соответственно с входами первых К полных одноразрядных сумматоров V-ro столбца (где ,..., nsi М), где К ,,жайшее целое меньшее или равное п/2, an- вес разряда произведения, выходы 2К-разрядного сумматора являются .выходами устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет выполнения операции суммирования 2Н-разрядного слагаемого, повьшхения быстродействия в устройство введены 2N элементов памяти, причем выход переноса полного одноразрядного сумматора (N-2) -и строки столбца соединен с входом переноса полного одноразрядного сумматора (М-1)-й строки (d+1)-ro столбца (где d M/2-1, ..,М-2), выход переноса полного одноразрядного cy waтopa (Н-З)-й строки е-го столбца соединен с входом суммы полного одноразрядного сумматора (N-1)-й строки (е+1)-го столбца (где ,,.. ,М-3), выходы выходных полных одноразрядных сумматоров соедасиены соответственно с входами (2N-I) старших элементов памяти, выход элемента И первой диагонали матрицы элементов И соединен с входом младшего элемента памяти, выходы 2N элементов памяти соединены соответственно с входами первой группы 2Н-разрядного сумматора, входы второй группы которого являются входами суммирования устройства, вход переноса полного од-, поразрядного сумматора последней строки (М/2+1)-го столбца является входом округления устройства. Источники информации, принятые во внимание при экспертизе U Патент ОПА № 3914589, кл. G 06 F 7/39, опублик. 1975. 2. Патент США В 3752971, кл. G 06 F 7/39, опублик. 1975 (прототип).

«о,

.«

ЗР

i-S

5)38282 t: Ж К