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

группы соединен с входом первого разряда второго сомножители устройства, первый вход каждого элемента ИЛИ группы, начиная со второго, соединен с выходом предьщущего элемента ИЛИ группы, вторые входы элементов ИЛИ группы с первого по (К-2)-й соединены -соответственно с входами разрядов со второго по (N-1)-й второго сомножителя устройства, входы первого элемента И соединены с входом N-ro разряда первого сомножителя устройства и первым входом управления режимом умножения устройства, выход первого элемента И соединен с первыми входами . элементов И группы, второй вход первого элемента И группы соединен с первым входом элемента ИЛИ группы, вторые входы элементов И группы с-второго по (11-2)-й соединены соответственно с выходами элементов ИЛИ группы с первого по (Н-З)-й, выходы элементов И группы соединены с первыми входами соответствующих сумматоров по модулю два первой группы, вторые входы которых соединены с выходами элементов И с второго по (N-I )-й старшего столбца, матрицы, входы второго элемента И соединеныс входом N-ro разряда второго- сомножителя устройства и вторым входом управления режимом умножения устройства, вькод второго элемента И соединен с первыми входами сумматоров по модулю два второй группы, вторые входы которых соединены с выходами элементов И с второго по (N-1)-й старшей строки матрицы, входы третьего элемента И соединены с входами N-X разрядов первого и второго сомножителей устройства, входы четвертого элемента И соединены с входом N-ro разряда второго сомножителя устройства и вторым входом управления режимом умножения устройства, входы пятого элемента И соединены с входом N-ro разряда первого сомножителя устройства, первым входом управления режимом умножения устройства и выходом (N-2)-ro элемента ИЛИ группы, выходы третьего, четвертого и пятого элементов И соединены с входами сумматора по модулю два, входы шестого элемента И соединены с инверсным входом N-ro разряда первого сомножителя устройства, входом N-ro разряда второго сомножителя устройства и вторым входом управления режимом умножения устройства, входы седьмого элемента И соединены с входом -N-ro разряда второго сомножителя устройства, инверсным первым входом управления режимом умножения устройства и вторым входом управления режимом умножения устройства, входы восьмого элемента И соединены с входами N-x разрядов первого и второго сомножителей устройства, первым входом управления режимом умножения устройства и инверсным вторым входом управления режимом умножения устройства, входы девятого элемента И соединены со входом N-ro разряда первого сомножителя устройства, первым входом управления режимом умножения устройства и выходом (N-2)-ro элемента ИЛИ группы, в столбцы матрицы одкоразрядньрс сумматоров с (К+2)-го по (2И-К-3)-й введены одноразрядные сумматоры, образующие, дополнительные ветви суммирования, причем в каждой дополнительной ветви суммирования данного столбца матрицы одноразрядных сумматоров первый вход одноразрядного сумматора каждой строки Соединен с выходом суммы одноразрядного сумматора предыдущей строки, выход переноса одноразрядного сумматора каждой строки каждого столбца дополнительной ветви суммирования матрицы соединен с третьим входом одноразрядного сумматора следующей строки следующего столбца дополнительной ветви суммирования матрицы, второй вход одноразрядного сумматора (К-21п)-й строки (га 0,1,...) данного столбца матрицы соединен с выходом суммы одноразрядного сумматора (К-2т-2)-й строки последующей дополнительной ветви суммирования данного столбца матрицы, выходы элементов И диагоналей со второй по (2N-3)-ю матрицы за исключением элементов И с второго по (N-)-й старшей строкн и старшего столбца матрицы соединены с входами одноразрядных сумматоров столбцов с первого по (2К-4)-й матрицы соответственно, выходы сумматоров по модулю два первой и второй групп коррекции соединены с входами одноразрядных сумматоров столбцов с N-ro (2К-3)-й матрицы, выход десятого элемента И блока коррекции соединен с входом одного из одноразрядных сумматоров N-ro столбца матрицы, выход элемента И первого столбца первой строки матрицы является выходом младшего разряда устройства, выходь элементов И с шестого по девятый блока коррекции соединены с входом элемента ИЛИ блока коррекции, входы десятого элемента И блока коррекции соединены с выходом второго элемента И блока коррекции

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

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, содержащее сумматор с ускоренным переносом, матрицу одноразрядных сумматоров, каждый из которых содержит два сумматора по модулю два и узел переноса, причем первый вход каждого одноразрядного сумматора соединен с первыми входами первого сумматора по модулю два и узла переноса этого одноразрядного сумматора, второй вход каждого одноразрядного сумматора соединен с первым входом второго сумматора по модулю два и вторым входом узла переноса этого одноразрядного сумматора, третий вход каждого одноразрядного, сумматора соединен с третьим входом узла переноса и вторым входом второго сумматора по модулю два этого одноразрядного сумматора, в каждом одноразрядном сумматоре выходы второго сумматора по модулю два, первого сумматора по модулю два и узла переноса соединены соответственно с вторым входом первого сумматора по модулю два, выходом суммы и выходом переноса этого одноразрядного сумматора, выход суммы каждого одноразрядного сумматора каждой строки матрицы соединен с первым входом одноразрядного сумматора .соответствующего столбца следующей строки матрицы, выход переноса каждого одноразрядного сумматора каждой строки матрицы соединен с вторым входом одноразрядного сумматора следующего столбца следующей строки матрицы, входы округления устройства соединены с входами одного из одноразрядных сумматоров соответственно (N-1)-го и (N-2)-ro столбцов матрицы (N - разрядность сомножителей), выходы сумматора с . ускоренным переносом и выходы суммы первых одноразрядных сумматоров (Л ,, всех строк матрицы являются выхода.ми старших разрядов результата устройства, входы разрядов сумматора с ускоренным переносом соединены с с с выходами переносов соответствующих одноразрядных сумматоров последней строки матрицы и выходами суммы последующих одноразрядных сумматоров последней строки матрицы, отличающееся тем, что, с целью 00 повьшения быстродействия устройства, о оо оно содержит матрицу элементов И, блок коррекции, причем матрица сумматоров содержит К строк и

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

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

При высокой однородности структуры устройство имеет недостаточное быстродействие.

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

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

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

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

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

0 по модулю два и узла переноса этого одноразрядного сумматора, второй вход каждого одноразрядного сумматора соединен с первым входом второго сумматора по модулю два и вторым вхо5 дом узла переноса этого одноразрядного сумматора, третий вход каждого одноразрядного сумматора соеди-. нен с третьим входом узла переноса

и вторым входом второго сумматора

0 по модулю два этого одноразрядного сумматора, в каждом одноразрядном сумматоре выходы второго сумматора по модулю два, первого сумматора по модулю два и узла переноса соедине5 ны соответственно со вторым входом первого сумматора по модулю два, выходом суммы и выходом переноса этого одноразрядного сумматора, выход суммы каждого одноразрядного сумма0 тора каждой строки матрицы соединен с первым входом одноразрядного сумматора соответствующего столбца следующей строки матриЩ), выход переноса каждого одноразрядного сум матора каждой строки матрицы соединен с вторым входом одноразрядного сумматора следующего столбца следующей строки матрицы, входы округления устройства соединены с входаQ ми одного из одноразрядных сумматоров соответственно (N-I)-го и (N-2)-ro столбца матрицы (N - разЭ

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

+ 2 строк и (2N-3) стол4

бцов, входьт злемеитов И матрицы соединены с входами разрядов первого и второго сомножителей устройства, блок коррекции содержит элементы И, ИЛИ, сумматоры по модулю два, группу элементов И, группу элементов ИЛИ, две группы сумматоров по модулю два, причем в блоке коррекции первый вход первого элемента ИЛИ группы соединен с входом первого разряда второго сомножителя устройства, первый вход каждого элемента ИЛИ группы, начиная со второго, соединен с выходом предьщущего элемента ИЛИ группы, вторые входы элементов ИЛИ группы с первого по (Ы-2)-й соединены соответственно с входами разрядов со второго по (N-1 и второго сомножителя устройства, входы первого элемента И соединены с входом К-го разряда первого сомножителя устройства и первым входом управления режимом умножения устройства, выход первого элемента соединен с первыми входами элементов И групп), второй вход первого элемента И группы соединен с первым входом первого элемента ИЛИ группы, вторые входы элементов И группы со второго по (Н-2)-й соединены соответственно с выходами элементов ИЛИ группы с первого по (N -3)-й, выходы элементов И группы соединены с первыми входами соответствующих сумматоров по модулю два первой группы вторые входы которых соединены с входами элементов И со второго по (К-1)-й старшего столбца матрицы, входы второго элемента И .соединены с входом N-ro разряда второго сомножителя устройства и вторым входом

01803

управления режимом умножения устройства, выход BTOpdro элемента И соединен с первыми входами сумматоров по модулю два второй группы, вторые JJ входы которых соединены с выходами элементов И со второго по (N-1)-й старшей строки матрицы, входы третьего элемента И соединены с входами N-X разрядов первого и второго

JO сомножителей устройства, входы четвертого элемента И соединены с входом Н-го разряда второго сомножителя устройства и вторым входом управления режимом умножения устрой)5 ства, входы пятого элемента И соединены с входом N-ro разряда первого сомножителя устройства, первым входом управления режимом умножения устройства и выходом (N-2)-ro эле20 мента ИЛИ группы, выходы третьего, четвертого и пятого элементов И соединены с входами сумматора по модулю два, входы шестого элемента И соединены с инверсным входом N-ro

25 разряда первого сомножителя устройства, входом N-ro разряда второго сомножителя устройства и вторым входом управления режимом умножения устройства, входы седьмого элемента И соединены с входом N-ro разряда второго сомножителя устройства, инверсным первым входом управления режимом умножения устройства и вторым входом управления режимом умножения устройства, входы восьмо го элемента И соединены с входами N-X разрядов первого и второго сомножителей устройства, первым входом управления режимом умножения устройства и инверсным вторым входом управления режимом умножения устройства, входы девятого элемента И соединены с входом N-ro разряда первого сомножителя устройства, первым входом управления режимом умножения устройства и выходом (N-2)-ro элемента ИЛИ группы, в столбцы матрицы одноразрядных сумматоров с (К+2)-го по (2N-K-3)-й введены одноразрядные сумматоры, образующие дополнительные ветви суммирования, причем в каждой дополнительной ветви суммирования данного столбца -матрицы одноразрядных сумматоров первый вход однораз55 рядного сумматора каждой строки соединен с выходом суммы одноразрядного сумматора предьщущей строки, выход переноса одноразрядного сумматора каждой строки каждого столбца дополнительной ветви суммирования матрицы соединен с третьим входом одноразрядного сумматора следующей строки следующего столбца дополнительной ветви суммирования матрицы, второй вход одноразрядного сумматора (К-2т)-й строки (т 0,1,...) данного столбца матрицы соединен с выходом суммы одноразрядного сумматора (К-2т-2)-й строки последзпощей дополнительной ветви суммирования данного столбца матрицы, выходы элементов И диагоналей со второй по (2И-3)-ю матрицы за ис1слючением элементов И со второго по (Ы-1)-й старшей строки и старшего столбца матрицы соединены с входами одноразрядных сумматоров столбцов с первого по (2К-А)-й матрицы соответственно, выходы сумматоров по модулю два первой и второй групп блока коррекции соединены с входами одноразрядных сумматоров столбцов с (Н)-го по (2Н-3)-й матрицы, выход десятого элемента И блока коррекции соединен с входом одного из одноразрядных сумматоров N-ro столбца матрицы, выход элемента И первого столбца первой строки матрицы является выходом младшего разряда устройства, выходы элементов И с шестого по девятый блока коррекции соединены с входами элемента ИЛИ блока коррекции, входы десятого элемента И блока коррекции соединены с выходом второго элемента И блока коррекции и инверсным входом первого разряда первого сомножителя устройства, выходы сумматора по модулю два и элемента ИЛИ блока коррекции соединены соответственно с входами (Ы+2)-го и (N+3)-ro разрядов сумматора с ускоренным переносом .

На фиг. 1 показана структурная схема устройства дпя случая б- разрядных операндов; на фиг. 2 - схема матрицы сумматоров; на фиг. 3 - схема блока коррекции; на фиг. 4 - схема одноразрядного сумматора; на фиг. 5 - схема узла переноса.

Устройство содержит матрицу 1 элементов И, матрицу 2 одноразрядных сумматоров, блок 3 коррекции, сумматор 4 с ускоренным переносом. В состав матрицы 2 входят одноразрядные сумматоры 5, каждый из которых содержит сумматоры 6 по модулю два,и узел 7 переноса, выполненный, например, на одном элементе И-ИЛИ 8. Блок коррекции содержит элементы ИЛИ 9, И 10, сумматоры 11 по модулю два, элемент И 12, сумматоры 13 по модулю два, элементы И 14, 15, 16, 17, 18, 19, 20, 21 и 22, сумматор по модулю два 23 элемент ИЛИ 24.

Устройство для умножения работает следующим образом. Разряды множимого XQ-X-, и множителя У-,У-- поступают на входы матрицы элемен- . тов И 1,в которой выполняется поразрядное перемножение цифр с множителей, исключая произведение восьмых (старших) X и. у разрядов. Одновременно разряды множителя УО УЙпоступают на входы элементов РШИ 9 и вход первого элемента И 10.

Выходы элементов ИЛИ 9 соединены с входами элементов И 10, другие входы которых соединены с выходом элемента И 12, входы которого соединены с первым входом управления режимом умножения (х) и входом старП

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

Выход шестого элемента ИЛИ 9 соединен с выходами элементов И 22.

Входы элемента И 16 соединены с входами восьмых разрядов (х и у ) первого и второго сомножителей. Входы элемента И 17 соединены с входом восьмого разряда (у ) второго сомножителя и вторым входом (yf) управления режимом умножения устройства. Входы элемента И 18 соединены с первым входом (х) управления режимом умножения и входом восьмого разряда (х) первого сомножителя.

Выходы элементов И 16, 17 и 18 соединены с входами сумматора 23 по модулю два. Выход сумматора 23 по

модулю два (Fy) поступает на вход четырнадцатого разряда сумматора 4 с ускоренным переносом. Входы элемента И 19 соединены с инверсным вхдом восьмого разряда (х) первого сомножителя, вторым входом (у) управления режимоми входом JBOCBMOго разряда (у ) второго сомножителя Входы элемента И 20 соединены с входом восьмого разряда (у ) второго сомно кителя, вторым входом управления режимом (УМ) умножения и инверным первым входом (х ) управления

Гп

режимом умножения.

Входы элемента И 21 соединены с первым входом (х) управления режимом з ножения, входом восьмого разряда (ху) первого сомножителя, инверсным вторым входом (УМ) управления режимом умножения и восьмым разрядом (у) второго сомножителя. ;Входы элемента И 22 соединены с вторым входом (х) управления режимом умножения и входом восьмого разряда (х) первого сомножителя. Выходы элментов И 19-22 соединены с входами элемента ИЛИ 24. Выход элемента ИЛИ 24 (F;|5) поступает на вход пятнаддатого разряда сумматора 4 с ускренным переносом.

Таким образом на выходе F формрфуется признак логического расши рения знаков частичных произведе; ний. С ПОМОЩЬЮ выхода F и переноса из десятого разряда сумматора 4 с ускоренньпч переносом формируется знак произведения.

Выход элемента И 15 соединен с первыми входами сумматоров 15 по модулю два и первым входом элемента И 14, второй вход которого соединен с инверсным входом (XQ) первого разряда первого сомножителя. Выход элемента И 14 соединен с входом одного из одноразрядных сумматоров 5 первой строки восьмого столбцы матрицы 2, вторые входы сумматоров по модулю два группы соединены с выходами матрицы 1 элементов И со второго (h) по седьмой (hg) старшие разряды последней строки матрицы. Выходы сумматоров 13 по модулю два соединены с входами одноразрядных сумматоров 5 столбцов с восьмого по тринадцатый всех строк матрицы 2, кроме первой. Входы элемента И 15 соединены с входом восьмого разряда (у.) второго сомножителя устройства и вторым входом (у) управления режимом умножения. Таким образом производится коррекция псевдопроизведения.

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

Каждый одноразрядный сумматор 5 содерижт два сумматора 6 по модулю два и узел 7 переноса, причем первый вход каждого одноразрядного сумматора 5 соединен с первыми входами первого одноразрядного сумматора 6 по модулю два и узла 7 переноса этого одноразрядного сумматора 5, второй вход каждого одноразрядного сумматора 5 соединен с первым входом второго сумматора 6 по модулю два и вторым входом узла 7 переноса этого одноразрядного сумматора 5.

Третий вход каждого одноразрядного сумматора 5 соединен с третьим входом узла 7 переноса и вторым входом второго сумматора 6 по модулю два этого одноразрядного сумматора 5.

Матрицы 2 одноразрядных сумматоров 5 выполнена в виде модифицированного дерева Уоллеса, имеющего дополнительные ветви суммирования в пределах с шестого по десятый столбцов матрицы 2.

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

В устройстве дпя умножения выполняются операции над числами, представленными дополнительным кодом и

числами без знака.

При этом устройство работает в следующих режимах:

перемножение чисел со знаком

УМ К

(-м

перемножение, чисел без знака (х. О, у„ 0),

смешанное произведение чисел

м О УМ ; м 1. УМ 0).

Таким образом, распараллеливание процесса суммирования в столбца

сумматоров матрицы 2 введением дополнительных ветвей суммирования, а также подсоединение выходов блока 3 коррекции к входам одноразрядных сумматоров 5 строк, кроме первой, обеспечивает минимальное время проХз-Х

о

хождения сигнала от входа к выходу устройства.

Введение дополнительных регистров сомножителей и произведения позволяет использовать устройство в конвейерном режиме перемножения.

УггИ