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

(5) 4 О 06 У 7/ 803 ЗОБРЕТЕНИ ИС ИДЕТЕЛЬСТ ТОРСИ 35 пов оно бло и ( мат столбцов, всоединены с оды элементов И ходами разрясомножителей екции содержит аторы по модулю И, группу элеы сумматоров в блоке коррекго элемента ИЛИ дов пер вого и в тва, блоИ, ИЛИ, сумм уппу элементо ИЛИ, две груп торог к кор устройсэлемент а, грнтов п ва, причем вход перво ии пер ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Патент СНА Бф 3900724, кл.2164, опублик. 1975.Патент С 111 А У 413878, кл. 364-758,опублик. 1978,Патент США Р 4153938, кл. 364-760760, опублик. 1979 (прототип)(54)(57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ,содержащее сумматор с ускореннымпереносом, матрицу одноразрядныхсумматоров, каждый из которых содержит два сумматора по модулю дваи узел переноса, причем первыйвход каждого одноразрядного сумматора соединен с первыми входами первого сумматора по модулю два и узлапереноса этого одноразрядного сумматора, второй вход каждого одноразрядного сумматора соединен с первымвходом второго сумматора по модулюдва и вторым входом узла переносаэтого одноразрядного сумматора, третий вход каждого одноразрядного. сумматора соединен с третьим входомузла переноса и вторым входом второго сумматора по модулю два этогоодноразрядного сумматора, в каждомодноразрядном сумматоре выходы второго сумматора по модулю два, первого сумматора по модулю два и узлапереноса соединены соответственнос вторым входом первого сумматорапо модулю два, выходом суммы и выходом переноса этого одноразрядного сумматора, выход суммы каждого одноразрядного сумматора каждой строки матрицы соединен с первым входом одноразрядного сумматора соответствующего столбца следующей строки матрицы, выход переноса кажЪдого одноразрядного сумматора каждой строки матрицы соединен с вторым входом одноразрядного сумматора следующего столбца следующей строки матрицы, входы округления устройства соединены с входами одного из одноразрядных сумматоров соответственно (11 - 1)-го и (Я)-го столбцов матрицы (Б - разрядность сомножителей), выходы сумматора с ускоренным переносом и выходы суммы первых одноразрядных сумматоров , всех строк матрицы являются выходами старших разрядов результата устройства, входы разрядов сумматора с ускоренным переносом соединены с выходами переносов соответствующих одноразрядных сумматоров последней строки матрицы и выходами суммы последующих одноразрядных сумматоров последней строки матрицы, о т л и - ч а ю щ е е с я тем, что, с цельюышения быстродействия устройства,содержит матрицу элементов И,к коррекции, причем матрица сум 1 т +маторов содержит К =1 --- 1 +2 строк4группы соединен с входом первого разряда второго сомножителя устройства,первый вход каждого элемента ИЛИгруппы, начиная со второго, соединен с выходом предыдущего элемента ИЛИ группы, вторые входы элементов ИЛИ группы с первого по (Б)-йсоединены соответственно с входамиразрядов со второго по (И)-й второго сомножителя устройства, входыпервого элемента И соединены с входом Б-го разряда первого сомножителяустройства и первь 1 м входом управления режимом умножения устройства, выход первого элемента И соединен спервыми входами элементов И группы,второй вход первого элемента И группы соединен с первым входом элемента ИЛИ группы, вторые входы элементов И группы с второго по (И)-йсоединены соответственно с выходамиэлементов ИЛИ группы с первого по(И-З)-й, выходы элементов И группысоединены с первыми входами соответствующих сумматоров по модулю двапервой группы, вторые входы которыхсоединены с выходами элементов И свторого по (И)-й старшего столбцаматрицы, входы второго элемента Исоединены с входом И-го разряда второго сомножителя устройства и вторымвходом управления режимом умноженияустройства, выход второго элемента Исоединен с первыми входами сумматоров по модулю два второй группы, вторые входы которых соединены с выходами элементов И с второго по (И)-йстаршей строки матрицы, входы третьего элемента И соединены с входамиИ-х разрядов первого и второго сомножителей устройства, входы четвертого элемента И соединены с входомБ-го разряда второго сомножителя устройства и вторым входом управлениярежимом умножения устройства, входыпятого элемента И соединены с входом Б-го разряда первого сомножителя устройства, первым входом управления режимом умножения устройства и выходом (И)-го элемента ИЛИгруппы, выходы третьего, четвертогои пятого элементов И соединены свходами сумматора по модулю два,входы шестого элемента И соединеныс инверсным входом Б-го разрядапервого сомножителя устройства, входом И-го разряда второго сомножителя устройства и вторым входом управления режимом умножения устройства, входы седьмого элемента И соединены с входом И-го разряда второго сомножителя устройства, инверсным первым входом управления режимом умножения устройства и вторым входом управления режимом умножения устройства, входы восьмого элемента И соединены с входами Б-х разрядов первого и второго сомножителей устройства, первым входом управления режимом умножения устройства и инверсным вторым входом управления режимом умножения устройства, входы девятого элемента И соединены со входом И-го разряда первого сомножителя устройства, первым входом управления режимом умножения устройства и выходом (И)-го элемента ИЛИ группы, в столбцы матрицы одноразрядных сумматоров с (К+2)-го по (2 М-К)-й введены одноразрядные сумматоры, образующие. дополнительные ветви суммирования, причем в каждой дополнительной ветви суммирования данного столбца матрицы одноразрядных сумматоров первый вход одноразрядного сумматора каждой строки соединен с выходом суммы одноразрядного сумматора предыдущей строки, выход переноса одноразрядного сумматора каждой строки каждого столбца дополнительной ветви суммирования матрицы соединен с третьим входом одноразрядного сумматора следующей строки следующего столбца дополнительной ветви суммирования матрицы, второй вход одноразрядного сумматора (Кш)-й строки (ш= 0,1,) данного столбца матрицы соединен с выходом суммы одноразрядного сумматора (Кш)-й строки последующей дополнительной ветви суммирования данного столбца матрицы, выходы элементов И диагоналей со второй по (2 И)-ю матрицы за исключением элементов И с второго по (Б)-й старшей строки и старшего столбца матрицы соединены свходами одноразрядных сумматоров столбцов с первого по (2 Б)-й матрицы соответственно, выходы сумматоров по модулю два первой и второй групп блока коррекции соединены с входами одноразрядных сумматоров столбцов с Б-го (2 И)-й матрицы, выход десятого элемента И блока коррекции соединен с входом одного из одноразрядных сумматоров Б-го столбца матрицы, выход элемента И перво1 1 го стопбца первой строки матрицы является выходом младшего разряда устройства, выходы элементов И с шестого по девятый блока коррекции соединены с входом элемента ИЛИ блока коррекции, входы десятого элемента И блока коррекции соединены с выходом второго элемента И блока коррекции ОО 18 ОЗи инверсным входом первого разряда первого сомножителя устройства, выходы сумматора по модулю два и элемента ИЛИ блока. коррекции сое, динены соответственно с входами (М+ 2 ) - го и ( 1 Ч+ 3) -го разрядов сумматора с ускоренным переносом.1Изобретение относится к вычислительной технике и может найти применение, в электронных вычислительных машинах и быстродействующих процессорах обработки данных.Известно устройство для умножения, реализующее алгоритм перемножения с двумя шагами коррекции псевдопроизведения, содержащее матрицуэлементов И, матрицу И х И одноразрядных сумматоров. В каждом столбцесумматоры объединецы шинами суммы,выход переноса одноразрядного сумматора каждого столбца каждой строкисоединен с входом переноса одноразрядного сумматора последующего столбца последующей строки,При высокой однородности структуры устройство имеет недостаточноебыстродействие.Известно также устройствс дляумножения, в котором матрица одноразрядных сумматоров выполнена в видемодифицированного дерева Уоллеса.В устройстве выполняется два шагакоррекции псевдопроизведения,Недостатком устройства является то, что блоки коррекции подсоединены к выходам матрицы, что увеличивает время суммирования частичныхпроизведений.Известно устройство для умножения, содержащее шифраторы Бута,мультиплексоры, сдвигатели, сумматорс ускоренным переносом, матрицу одноразрядных сумматоров, каждый изкоторых содержит два сумматора помодулю два и узел переноса. Устройство обладает невысоким быстродействием.Целью изобретения является повышение быстродействия устройства. ЪУказанная цель достигается тем,что устройство для умножения, содержащее сумматор с ускоренным переносом, матрицу одноразрядных сумматоров, каждый из которых содержитдва сумматора по модулю два и узелпереноса, причем первый вход каждого одноразрядного сумматора соединенс первыми входами первого сумматора 10 по модулю два и узла переноса этогоодноразрядного сумматора, второйвход каждого одноразрядного сумматора соединен с первым входом второгосумматора по модулю два и вторым вхо дом узла переноса этого одноразрядного сумматора, третий вход каждого одноразрядного сумматора соеди-.нен с третьим входом узла переносаи вторым входом второго сумматора 20 по модулю два этого одноразрядногосумматора, в каждом одноразрядномсумматоре выходы второго сумматорапо модулю два, первого сумматора помодулю два и узла переноса соедине ны соответственно со вторым входомпервого сумматора по модулю два,выходом суммы и выходом переноса этого одноразрядного сумматора, выходсуммы каждого одноразрядного суммаЗ 0 тора каждой строки матрицы соединенс первым входом одноразрядного сумматора соответствующего столбцаследующей строки матрицы, выход переноса каждого одноразрядного сум"матора каждой строки матрицы соединен с вторым входом одноразрядногосумматора следующего столбца следующей строки матрицы, входы округления устройства соединены с входа ми одного из одноразрядных сумматоров соответственно (Б)-го и+ 2 строк и (2 Б-З) стол 4бцов, входы элементов И матрицы соединены с входами разрядов первого и второго сомножителей устройства, блок коррекции содержит элементы И, ИЛИ, сумматоры по модулю два, группу элементов И, группу элементов ИЛИ, две группы сумматоров по модулю два, причем в блоке коррекции первый вход первого элемента ИЛИ группы соединен с входом первого разряда второго сомножителя устройства, первый вход каждого элемента ИЛИ группы, начиная со второго, соединен с выходом предыдущего элемента ИЛИ группы, вторые входы элементов ИЛИ группы с первого по (Б)-й соединены соответственно с входами разрядов со второго по (Б)- й второго сомножителя устройства, входы первого элемента И соединены с входом Ж-го разряда первого сомножителя устройства и первым входом управления режимом умножения устройства, выход первого элемента И соединен с первыми входами элементов И группь, второй вход первого элемента И группы соединен с первым входом первого элемента ИЛИ группы, вторые входы элементов И группы со второго по (Б)-й соединены соответственно с выходами элементов ИЛИ группы с первого по (Б -3)-й, выходы элементов И группы соединены с первыми входами соответствующих сумматоровпо модулю два первой группы, вторые входы которых соединены с выходами элементов И со второго по (Б)-й старшего столбца матрицы, входы второго элемента И .соединены с входом Б-го разряда второго сомножителя устройства и вторым входом 50 55 зрядность сомножителей), выходы сумматора с ускоренным переносом и выходы суммы первых одноразрядных сумматоров всех строк матрицы являются выходами старших разрядов результата устройства, входы разрядов сумматора с ускоренным переносом соединены .с выходами переносов соответствующих одноразрядных сумматоров последней строки матрицы и выходами суммы последующих одноразрядных сумматоров последней строки матрицы, содержит матрицу элементов И, блок коррекции, причем матрица сумматоров содержит К управления режимом умножения устройства, выход вторОго элемента И соединен с первыми входами сумматоровпо модулю два второй группы, вторыевходы которых соединены с выходамиэлементов И со второго по (Б)-йстаршей строки матрицы, входы третьего элемента И соединены с входами И-х разрядов первого и второгосомножителей устройства, входы четвертого элемента И соединены с входом д-го разряда второго сомножителя устройства и вторым входом управления режимом умножения устройства, входы пятого элемента И соединены с входом И-го разряда первого сомножителя устройства, первымвходом управления режимом умноженияустройства и выходом (И)-го эле мента ИЛИ группы, выходы третьего,четвертого и пятого элементов И соединены с входами сумматора по модулю два, входы шестого элемента Исоединены с инверсным входом И-горазряда первого сомножителя устройства, входом И-го разряда второго сомножителя устройства и вторым входом управления режимом умножения устройства, входы седьмогоэлемента И соединены с входом И-горазряда второго сомножителя устройства, инверсным первым входом управления режимом умножения устройства ивторым входом управления режимомумножения устройства, входы восьмого элемента И соединены с входамиИ-х разрядов первого и второго сомножителей устройства, первым входом управления режимом умноженияустройства и инверсным вторым вхо 40дом управления режимом умноженияустройства, входы девятого элемента И соединены с входом М-го разряда первого сомножителя устройства, первым входом управления режимом умножения устройства и выходом(Б)-го элемента ИЛИ группы, встолбцы матрицы одноразрядных сумматоров с (К+2)-го по (2 И-К)-й введены одноразрядные сумматоры, образующие дополнительные ветви суммирования, причем в каждой до- полнительной ветви суммирования данного столбца матрицы одноразрядных сумматоров первый вход одноразрядного сумматора каждой строки соединен с выходом суммы одноразрядного сумматора предыдущей строки, выход переноса одноразрядного сумма20 40 Устройство содержит матрицу 1 элементов И, матрицу 2 одноразрядных сумматоров, блок 3 коррекции, сумматор 4 с ускоренным переносом, В состав матрицы 2 входят одноразрядные сумматоры 5, каждый из котора каждой строки каждого столбцадополнительной ветви суммированияматрицы соединен с третьим входомодноразрядного сумматора следующейстроки следующего столбца дополни 5тельной ветви суммирования матрицы,второй вход одноразрядного сумматора(Кш)-й строки (ш= 0,1,) данногостолбца матрицы соединен с выходомсуммы одноразрядного сумматора(Кш)-й строки последующей дополнительной ветви суммирования данного столбца матрицы, выходы элементов И диагоналей со второй по(2 Б)-ю матрицы за исключением элементов И со второго по (И)-й старшей строки и старшего столбцаматрицы соединены с входами одноразрядных сумматоров столбцов с первогопо (2 Б)-й матрицы соответственно,выходы сумматоров по модулю два первой и второй групп блока коррекциисоединены с входами одноразрядныхсумматоров столбцов с (Б)-го по25(2 Б)-й матрицы, выход десятого элемента И блока коррекции соединен свходом одного иэ одноразрядных сумматоров Б-го столбца матрицы, выходэлемента И первого столбца первойстроки матрицы является выходоммладшего разряда устройства, выходыэлементов И с шестого по девятыйблока коррекции соединены с входамиэлемента ИЛИ блока коррекции, входыдесятого элемента И блока коррекции35соединены с выходом второго элемента И блока коррекции и инверснымвходом первого разряда первого сомножителя устройства, выходы сумматора по модулю два и элемента ИЛИблока коррекции соединены соответственно с входами (И+2)-го и (0+3)-горазрядов сумматора с ускоренным переносом,На фиг. 1 показана структурнаясхема устройства для случая 8-разрядных операндов; на фиг 2 - схемаматрицы сумматоров; на фиг. 3 - схема блока коррекции на фиг. 4 - схем50ма одноразрядного сумматора; нафиг. 5 - схема узла переноса. торых содержит сумматоры 6 по модулю два, и узел 7 переноса, выполненный, например, на одном элементе И-ИЛИ 8. Блок коррекции содержит элементы ИЛИ 9, И 10, сумматоры 11 по модулю два, элементИ 12, сумматоры 13 по модулю два,элементы И 14, 15, 16, 17, 18, 1920, 21 и 22, сумматор по модулюдва 23 элемент ИЛИ 24,Устройство для умножения работает следующим образом. Разряды множимого х -х и множителя у -у. поо ю 7ступают на входы матрицы элементов И 1,в которой выполняется поразрядное перемножение цифр с множителей, исключая произведение восьмых (старших) х и у разрядов. Одновременно разряды мйожителя у-у .поступают на входы элементов ШП 1 9и вход первого элемента И О.Выходы элементов ИЛИ 9 соединены с входами элементов И 1 О, другие входы которых соединены с выходом элемента И 12, входы которогосоединены с первым входом управлениярежимом умножения (х) и входом старшего разряда первого сомножителя(х ). Выходы элементов И 10 соединены с первыми входами сумматоров 11по модулю два, на другие входы которых поступают выходы матрицы 1 элементов И и второго по седьмой старшего столбца матрицы (Ь - ). Выходы сумматоров 11 по модулю два по-ступают на входы одноразрядных сумматоров 5 столбцов с восьмого по тринадцатый всех четырех строк, кромепервой, с целью повышения быстродействия устройства. Соединение элементов ИЛИ 9 может быть выполнено попараллельно-последовательной схеме,Выход шестого элемента ИЛИ 9 соединен с выходами элементов И 22.Входы элемента И 16 соединены свходами восьмых разрядов (х 7 и у )первогои второго сомножителей. Входы элемента И 17 соединены с входомвосьмого разряда (у ) второго сомножителя и вторым входом (у)" 1.управления режимом умножения устройства. Входы элемента И 18 соединеныс первым входом (хя) управления режимом умножения и входом восьмогоразряда (х ) первого сомножителя.Выходы элементов И 16, 17 и 18соединены с входами сумматора 23 помодулю два. Выход сумматора 23 помодулю два (Р) поступает на вход четырнадцатого разряда сумматора 4 с ускоренным переносом. Входы элемента И 19 соединены с инверсным вхо 5 дом восьмого разряда (х) первого сомножителя, вторым входом (у) управления режимоми входом цосьмого разряда (у ) второго сомножителя.7Входы элемента И 20 соединены с входом восьмого разряда (у ) второго сомножителя, вторым входом управления режимом (у) умножения и инверсным первым входом (х ) управления режимом умножения. 15Входы элемента И 21 соединены с первым входом (х) управления режимом умножения, входом восьмого разряда (х,) первого сомножителя, инверсным вторым входом (уи) управления режимом умножения и восьмым разрядом (у ) второго сомножителя.чВходы элемента И 22 соединены с вторым входом (хм) управления режимом умножения и входом восьмого разряда (х ) первого сомножителя. Выходы элементов И 19-22 соединены с входами элемента ИЛИ 24. Выход элемента ИЛИ 24 (Р ) поступает на вход пятнадцатого разряда сумматора 4 с уско-з ренным переносом.Таким образом на выходе Рц Фор- мируется признак логического расширения знаков частичных произведений. С помощью выхода Г и переноса35 из десятого разряда сумматора 4 с ускоренным переносом формируется знак произведения.Выход элемента И 15 соединен с первыми входами сумматоров 15 по мо- ф дулю два и первым входом элемента И 4, второй вход которого соединен с инверсным входом (х,) первого разряда первого сомножителя. Выход элемента И 14 соединен с входом одного из одноразрядных сумматоров 5 первой строки восьмого столбцы матрицы 2, вторые входы сумматоров по модулю два группы соединены с выходами матрицы 1 элементов И со второго (Ь ) по седьмой (Ь ) старшие разряды последней строки матрицы. Выходы сумматоров 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 выполняется суммирование логических произведений разрядов х -х и у -у соо 1 о 7множителей, расположенных по диагоналям матрицы,В устройстве для умножения выполняются операции над числами, представленными дополнительным кодом ичислами без знака.При этом устройство работает вследующих режимах:перемножение чисел со знакомперемножение чисел без знака(х=О,у=1;х=,у=О),Таким образом, распараллеливание процесса суммирования в столбцах3001803 Х-Х сумматоров матрицы 2 введением дополнительных ветвей суммирования, атакже подсоединение выходов блока 3коррекции к входам одноразрядныхсумматоров 5 строк, кроме первой,обеспечивает минимальное время прохождения сигнала от входа к выходу устройства.Введение дополнительных регистров сомножителей и произведения позволяет использовать устройство в конвейерном режиме перемножения.1001803 ц 4 э lфей, о Ъ й 5Фиг 5аказ 1338/3 НТираж 671 Подписное Филиал ППП "Патент", г, Ужгород, ул. Проектная, 4