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

 

А.И. Березенко, Ф.Л. Гладыш, С.Е. Калинин, 3 ."НЖврядин, А.И.Репвтюк и Е.M.Ðåïåòþê (72) Автори изобретем мя (7l) Заявмтель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ДВОИЧНЫХ

ЧИСЕЛ

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

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

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

Наиболее близким к изобретению по техническому решению является устройство, содержащее матрицу Йк к(Й-1) полных одноразрядных сумматоров (где Й вЂ” разрядность операндов), матрицу Йхй элементов И, 2Й-разрядный сумматор, причем выход переноса полного одноразрядного сумма" тора j-го столбца i-й строки соединен с входом переноса полного однаразрядного сумматора (j+1)-го столбца (1+1)-й строки, где j=l, ° .. M-1„

M=2(N-1), i=1 выход уммы а,Ь-го полного одноразрядного сумматора соединен с входом суета (а+1)-, Ь-ro полного одноразрядного сумматора (где а=l,...,N-1, Ь=2,...,И-1 ), выход переноса полного одноразрядного сумматора (N-1)-й строки с-ro столбца соединен с входом переноса полного одноразрядного сумматора Й-й строки (с+1)-го столбца, где С=,...,M-1, первые входы элементов И соединены соответственно с разрядными входными шинами множимого устройства, вторые входы элементов И соединены соответственно с разрядными входными шинами множителя устройства, выходы элементов И (q+1}-й диагонали матрицы элементов И (где q=l 2N-2) соединены соответственно с входамю

3 . 93 первых К полных одноразрядных суй маторов Ч"го столбца (где V=1,. ° ., .У

° 1, п=! пг,:

И), где. К и для >J — (:- бли; я(, nye Я, жайшее целое меньшее или равное — а и - вес разряда произведения, 3ыходы 2N-разрядного сумматора являют" ся выходами устройства f23.

Недостатками этого устройства яв-, ляются: — избыточное количество основных и дополнительных выводов устройства; — недостаточное быстродействие;

-. отсутствие возможности вынесения из устройства 2N-разрядного сумматора в качестве внешнего автономного узла, что позволяет сэкономить количество выводов в устройстве.

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

Поставленная цель достигается тем, что в устройство введены 2N элементов памяти, причем выход переноса полного одноразрядного сумматора (Й-2)-й строки d-го столбца соединен с входом переноса полного одноразрядного сумматора (N-l)-й строки (d+1)-го столбца (где 4=

=И/2-1,...,M-2), выход переноса пол« ного одноразрядного сумматора (N-3)"й строки е-ro столбца соединен с входом сумма полного одноразрядного сумматора (Й-l)"й строки (е+1)-го столбца (где е=И/2,. ...И-З), выходы выходных полных одноразрядных сумматоров соединены соответственно с входами (2N-1) старпжх элементов памяти, выход элемента И первой диагонали матрицы элементов

И соединен с входом младшего элемента памяти, выходы 2N элементов памяти соединены соответственно с входами первой группы 2й"разрядного сумматора, входы второй группы которого являются входами суммирования устройства, вход переноса полного одноразрядного сумматора последней строки (И/2+l)-го столбца является входом округления устройства.

На фиг. 1 представлена функциональная схема восьжразрядного устрой ства для умножения двоичных чисел, на фиг. 2 - то же, матрицы умножения, на фиг, 3 — структурная схе8282 4 ма,, иллюстрирующая работу устройства.

Устройство содержит элементы е И 1, матрицу 2 полных одноразрядных сумматоров 3, 2N-разрядный сумматор 4, шины 5 множимого, шины 6 множителя, вход 7 управления, входы

8 суммирования, вход 9 округления, выходы 10 .устройства, элементы 11

1р памяти.

Устройство для умножения шестнадцатиразрядных чисел состоит из четырех модулей умножителей 12-15 восьмиразрядных чисел, каждый из

1 которых содержит матрицу 16, включающую элементы И, регистры !7, шестнадцатиразрядный сумматор 4, выходной регистр 18, выход !9 переноса и вход 20 управления. Матрица

16, регистр 17 и сумматор 4 разделены. пунктиром на старшую и младшую части.

В устройстве выход переноса полного одноразрядного сумматора 3 1 -го

25 столбца 1 -й строки соединен с входом переноса полного одноразрядного сумматора 3 (j+1)-ro столбца (i+ l)"й строки где! =1,...,M-!, M=2(N"l), i-=1,...,N выход суммы а,Ь"го полного одноразрядного сумматора 3 соединен с входом суммы (а+l), b-ro полного сумматора 3 (где a=i й-l, b=2,...,И-1), выход переноса полного одноразрядного сумматора

3 (N"1)-й строки С-го столбца соединен с входом переноса полного одноразрядного сумматора 3 К-й строки (с+l)-ro столбца где с=М/2,...,М-1 первые входы элементов И соединены соответственно с разрядными вход4р

HblMH шинами 5 множимого устройства, вторые входы элементов И соединены соответственно с разрядными входяами шинами 6 множителя устройства выходы элементов И (q+1)-й диагонали матрицы элементов И (где q l, ° ...2К-2) соединены соответственно с входами первых К полных одноразрядных сумматоров 3 V-го столI р бца (где V=1 И), где К= )п! дпя

П- 1 1!!

1у-ф- ближайшее целое меньшее

Ï 7 или равное n/2, а h — вес разряда произведения, выходы 2N-разрядного

"И сумматора 4 являются выходами !О устройства, выход переноса полного одноразрядного сумматора 3 (N-2)-й строки d-го столбца, соединен с

938282 6 норазрядном сумматоре 3. й, Для N=8 разрядов это составит 147..

По первому такту, поступающему

10 на вход 71, полученные произведе1 2 1Э 14 1 ииЯ Р15 -о РЮ-о Рю-o> P15-о минаются в регистрах 17. С выходов регистров 17 произведения поступают на соответствующие входы сумматоров д 4 с сдвигом влево частичных произведений, обусловленным алгоритмом перемножения. При сложении частичных произведений в сумматорах 4 сигнал переноса с выхода 19 образуетрр ся только в сумматоре 4 модуля 14.

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

При этом в выходном сумматоре

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

3S да 19 модуля 14 поступает на вход 8 модуля 15.

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

Объединение модулей осуществля45 ется подключением выходов 10 старших разрядов произведения модуля

12 к входам 8 модуля 13, при этом выходы 10 модуля 13 соединены с входами 8 модуля 14 и т.д.

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

Конвейерная структура шестнадцатиразрядного умножителя, составленвходом переноса полного одноразрядного сумматора 3 (N-1)-й строки (с1+1) -го столбца (где d=M/2" 1,..., М-2), выход переноса полного одноразрядного сумматора 3 (М-3) -й стро. ки е-го столбца соединен с входом суммы полного одноразрядного сумматора 3 (N-1)-й строки (е+1)-го стол ца (где е=М/2,...,М-З), выходы выходных полных одноразрядных сумматоров 3 соединены соответственно с входами (2N-1) старших элементов

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

Реализация устройства может быть выполнена в виде модуля ° В матрице

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

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

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

На вход модуля 12 поступают Х1О и Y разряды сомножителей, на вход

1-О одуля 13 Xl-он ля 14 Х о и Yqg 8 и на вход модуля

15 Х1 8 и 71 .8. В каждой матрице 16 на элементах И выполняется логическое умножение разрядов сомножителей, после чего непосредственно в матрице 2 полных одноразрядных сумматоров 3 выполняется поразряд ное сложение логических проиэведений и распространение сигнала переноса вдоль матрицы 2 за время, равное 2(N-1) где С вЂ”. время распространения сигнала в полном одФормула изобретения

7 9382 ная из восьмиразрядных модулей тре бует равенства временных соотноше» ний в ступенях конвейера. Поэтому, с целью выравнивания переходного процесса в ступенях, сумматоры 4 5 могут быть выполнены по схеме с груп" повым переносом. |

Таким образом, в результате новой организации связей в матрице полных одноразрядыах сумматоров, введе- lO ния дополнительных входов в 2Й;раз- : рядный сумматор, общее количество выходов и входов становится на два меньше, чем в известном устройстве, уменьшается время умножения на вре- 15 мя задержки одноразрядного сумматора, осуществлен конвейеряай принцип умножения при объединении модулей, получена возможность дополнительного сложения в Й-разрядном умножите- щ ле 2Й-разрядного числа с 2N-разрядным произведением.

При объединении модулей получена возможность уменьшения времени умножения. 2$

Модульная структура устройства для умножения позволяет ориентировать реализацию устройства в виде БИС;

Устройство для умножения двоич, ных чисел, содержащее матрицу Nx. к(М" 1) поляих одноразрядных сумматоров (где N — - разрядность операндов)3, матрицу Й||М элементов И, 2Мразрядный сумматор,спричем выход переноса полного одноразрядного сум матора J-ro столбца соединен с входом переноса полного одноразрядного сумматора (J+1)-ro столбца, где

)1,...,М-1, М-2(й"1), выход сум|ы аЬ-vo полного одноразрядного сумматора соединен с входом суммы (а+1) b-rо полного одноразрядного сумматора (где а *1,...,N-l, b2, М-1), выход переноса полного одноразрядного сумматора (й-1) -й строки

50 с-го столбца соединен с входом переноса полного одноразрядного сумматора N-й строки (с+1)-го столбца, где СМ/2,...,М" 1), первые входы эле" ментов И соединены соответственно с разряд|ш|ми входными шинами множи82 8 мого устройства, вторые входы элементов И соединены соответственно с разрядными входными шинами множителя устройства, выходы элементов

И (ц+1)-й диагонали матрицы элементов И (где |1=1,...,2N+1) соединены соответственно с входами первых К полных одноразрядных сумматоров V-го столбца (где Ч1,..., 1

Нз |

М), где К- п для,1-| - бли.М | 1жайшее целое меньшее или равное и/2, à n - вес разряда произведея|я, выходы 2N-разрядного сумматора являются .выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выполнения операции суммирования 2N-разрядного слагаемого, повышения быстродействия в устройство введены 2Й элементов памяти, причем выход переноса полного одноразрядного сумматора (Й"2)-й строки с1-го столбца соединен с входом переноса полного одноразрядного сумматора (Й-1)"й строки (д+13--ro столбца (где d=M/2-1, ° ° °,М-2), выход переноса полного одноразрядного сумматора (N-3)-й строки е-ro столбца соединен с входом суммы полного одноразрядного сумматора (й-l)"é строки (e+1)-ro столбца (где е=М/2,...,И-З), выход| выходных полных одноразрядных сумматоров соединены соответственно с входами (2Й-1) старших элементов памяти, выход элемента И первой диагонали матрицы элементов И соединен с входом младшего элемента памяти, выходы 2N элементов памяти соединены соответственно с входами первой группы 2Й-разрядного сумматора входы второй группы которого являются входами сум|жрования устройства, вход переноса полного одноразрядного сумматора последней строки (М/2+1)-го столбца является входом округления устройства.

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

1.. Патент США У 3914589, кл. С 06 F 7/39, опублик. 1975.

2. Патент США Ф 3752971, кл. G Об F 7/39, опублик. 1975 (прототип).

938282

Составитель Л.Медведева

Редактор Н.Джуган Техред И. Гайду Корректор Н. Швыдкая

Заказ 4466 73 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, K-35, Раушская наб,, д. 4/5

Филиал ППП Патент, r. Ужгород, ул. Проектная, 4