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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

01803 A (19) (11) (5!) 4 G 06 F 7/52

Щ см = ф .уу

1я j

1 ,;т

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

CO

CO

Cr4

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗО6РЕТЕНИЙ И ОТКРЫТИЙ (21 ) 2998912/18-24 (22) 29.10.80 (46) 23.03.86. Бюп, 1(- 11 (72) А.И. Березенко, Ф.Л. Гладыш, С.Е. Калинин, Л.Н. Корягин, А.И.Репетюк и Е.М. Репетюк (53) 681.325.5(088.8) (56) Патент СНА ) - 3900724, кл.235164, опублик. 1975.

Ф

Патент СНА Ф 413878, кл. 364-758, опублик. 1978.

Патент США Р 4153938, кл. 364-760, 760, опублик. 1979 (прототип) ° (54)(57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, содержащее сумматор с ускоренным переносом, матрицу одноразрядных сумматоров, каждый из которых содержит два сумматора по модулю два и узел переноса, причем первый вход каждого одноразрядного сумматора соединен с первыми входами первого сумматора по модулю два и узла переноса этого одноразрядного сумматора, второй вход каждого одноразрядного сумматора соединен с первым входом второго сумматора по модулю два и вторым входом узла переноса этого одноразрядного сумматора, третий вход каждого одноразрядного. сумматора соединен с третьим входом узла переноса и вторым входом второго сумматора по модулю два этого одноразрядного сумматора, в каждом одноразрядном сумматоре выходы второго сумматора по модулю два, первого сумматора по модулю два и узла переноса соединены соответственно с вторым входом первого сумматора по модулю два, выходом суммы и выходом переноса этого одноразрядного сумматора, выход суммы каждого одноразрядного сумматора каждой строки матрицы соединен с первым входом одноразрядного сумматора соответствующего столбца следующей строки матрицы, выход переноса каж\ дого одноразрядного сумматора каждой строки матрицы соединен с вторым входом одноразрядного сумматора следующего столбца следующей строки матрицы, входы округления устройства соединены с входами одного из одноразрядных сумматоров соответственно (N — 1)-го и (N-2)-ro столбцов матрицы (N — разрядность сомножителей), выходы сумматора с ускоренным переносом и выходы суммы первых одноразрядных сумматоров, всех строк матрицы являются выходами старших разрядов результата устройства, входы разрядов сумматора с ускоренным переносом соединены с выходами переносов соответствующих одноразрядных сумматоров последней строки матрицы и выходами суммы последующих одноразрядных сумматоров последней строки матрицы, о т л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, оно содержит матрицу элементов И, блок коррекции, причем матрица сум1 т маторов содержит K =)- — — (+2 строк

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

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

N-x разрядов первого и второго сомножителей устройства, входы четвертого элемента И соединены с входом

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

ro стопбца первой строки матрицы является выходом младшего разряда устройства, выходы элементов И с шестого по девятый блока коррекции соединены с входом элемента ИЛИ блока коррекции, входы десятого элемента И блока коррекции соединены с выходом второго элемента И блока коррекции

ОО18ОЗ и инверсным входом первого разряда первого сомножителя устройства, выходы сумматора по модулю два и элемента ИЛИ блока. коррекции сое; динены соответственно .с входами(Я+2) — ro и (И+ 3) -го разрядов сумматора с ускоренным переносом.

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

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

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

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

В устройстве выполняется два шага коррекции псевдопроизведения.

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

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

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

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

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

20 по модулю два этого одноразрядного сумматора, в каждом одноразрядном сумматоре выходы второго сумматора по модулю два, первого сумматора по модулю два и узла переноса соедине25 ны соответственно со вторым входом первого сумматора по модулю два, выходом суммы и выходом переноса этого одноразрядного сумматора, выход суммы каждого одноразрядного суммаЗ0 тора каждой строки матрицы соединен с первым входом одноразрядного сумматора соответствующего столбца следующей строки матрицы, выход переноса каждого одноразрядного сумматора каждой строки матрицы соединен с вторым входом одноразрядного сумматора следующего столбца следующей строки матрицы, входы округления устройства соединены с входа40 ми одного из одноразрядных сумматоров соответственно (Б-1)-го и (N-2)-ro столбца матрицы (N — раз001803 4

ХТ+3

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

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

И-х разрядов первого и второго сомножителей устройства, первым входом управления режимом умножения устройства и инверсным вторым вхо40 дом управления режимом умножения устройства, входы девятого элемента И соединены с входом N-го разряда первого сомножителя устройства, первым входом управления режи45 мом умножения устройства и выходом (N-2)-го элемента ИЛИ группы, в столбцы матрицы одноразрядных сумматоров с (К+2)-ro по (2N-К-3)-й введены одноразрядные сумматоры, образующие дополнительные ветви суммирования, причем в каждой pî- полнительной ветви суммирования данного столбца матрицы одноразрядных сумматоров первый вход одноразрядного сумматора каждой строки соединен с выходом суммы одноразрядного сумматора предыдущей строки, выход переноса одноразрядного суммаIOOI8O3

40

Устройство содержит матрицу I элементов И, матрицу 2 одноразрядных сумматоров, блок 3 коррекции, сумматор 4 с ускоренным переносом, В состав матрицы 2 входят одноразрядные сумматоры 5, каждый из котора каждой строки каждого столбца дополнительной ветви суммирования матрицы соединен с третьим входом одноразрядного сумматора следующей строки следующего столбца дополни5 тельной ветви суммирования матрицы, второй вход одноразрядного сумматора (К-2m)-й строки (m= 0,1,...) данного столбца матрицы соединен с выходом суммы одноразрядного сумматора (К-2m-2)-й строки последующей дополнительной ветви суммирования данного столбца матрицы, выходы элементов И диагоналей со второй по (2N-3)-ю матрицы за исключением элементов И со второго по (N-1)-й старшей строки и старшего столбца матрицы соединены с входами одноразрядных сумматоров столбцов с первого по (2N-4)-й матрицы соответственно, выходы сумматоров по модулю два первой и второй групп блока коррекции соединены с входами одноразрядных сумматоров столбцов с (N)-го по

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

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

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

50 ма одноразрядного сумматора; на фиг. 5 — схема узла переноса. торых содержит сумматоры 6 по модулю два, и узел 7 переноса, выполненный, например, на одном элементе И-ИЛИ 8. Блок коррекции содержит элементы ИЛИ 9, И 10, сумматоры 11 по модулю два, элемент

И 12, сумматоры 13 по модулю два, элементы И 14, 15, 16, 17, 18, 19 °

20, 21 и 22, сумматор по модулю два 23 элемент ИЛИ 24.

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

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

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

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

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

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

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

Входы элемента И 20 соединены с вхо- 1О дом восьмого разряда (у ) второго

7 сомножителя, вторым входом управления режимом (у„) умножения и инверсным первым входом (х ) управления режимом умножения. 15

Входы элемента И 21 соединены с первым входом (х„) управления режимом умножения, входом восьмого pasряда (х,) первого сомножителя, инверсным вторым входом (уи) управления режимом умножения и восьмым разрядом (у ) второго сомножителя. ч :Входы элемента И 22 соединены с вто1 рым входом (х ) управления режимом умножения и входом восьмого разряда (х ) первого сомножителя. Выходы элементов И 19-22 соединены с входами элемента ИЛИ 24. Выход элемента

ИЛИ 24 (Р „ ) поступает на вход пятнадцатого разряда сумматора 4 с ускоренным переносом.

Таким образом на выходе F ö Фор- мируется признак логического расширения знаков частичных произведений. С помощью выхода F и переноса

35 из десятого разряда сумматора 4 с ускоренным переносом формируется знак произведения.

Выход элемента И 15 соединен с первыми входами сумматоров 15 по мо- 4О дулю два и первым входом элемента И 14, второй вход которого соединен с инверсным входом (x,) первого разряда первого сомножителя. Выход элемента И 14 соединен с входом 45 одного из одноразрядных сумматоров 5 первой строки восьмого столбцы матрицы 2, вторые входы сумматоров по модулю два группы соединены с выходами матрицы 1 элементов И со второго (h „) по седьмой (h ) старшие разряды последней строки матрицы. Выходы сумматоров 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 выполняется суммирование логических произведений разрядов х -х и у -у соо t o 1 множителей, расположенных по диагоналям матрицы.

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

При этом устройство работает в следующих режимах . перемножение чисел со знаком перемножение чисел без знака (х = О, у = О), смешанное произведение чисел (x=О,у=1;х„= l,у=0).

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

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

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

100!803 лг л» лю лг

lro л ь» лг лг йр <о

Лн Л

©мг 3

Фиг.5

ВНИИПИ Заказ 1338/3 Тираж 671 Подписное

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