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

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

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

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

умножителя; на фиг.6 - пример реализации схемы корректора; на фиг.7 - пример реализации схемы двух тетрад блока суммирования.

Устройство для умножения (фиг.1) содержит регистр 1 множимого, регистр 2 множителя, регистр 3 результата, блок 4 формирования кратных множимого, матричный умножитель 5, блок 6 сумми- рования, вход 7 выбора режима работы устройства, управляющий вход 8 устройства, выход 9 регистра множимого, выходы двукратного 10, четырехкратного 11 и восьмикратного 12 множимого блока 4, выходы 13 разрядов тетрады регистра множителя, выходы первой 14 и второй 15 групп блока суммирования.

Матричный умножитель 5 (фиг.З) содержит п/4 подматриц, каждая из ко- торых содержит первую строку из п/4 вычислительных модулей 16, вторую строку из (п/4+1) вычислительных.модуСП

vj

00

J

Лей 16 третью и четвертую строки по (п/4+1) вычислительных модулей 17 и Группу из п/4 корректоров 18, входы 19-21 вычислительных модулей 16, выход суммы 22 вычислительных модулей 16, вход 23 и выход 24 переноса вычислительных модулей 16, входы 25-30 вычислительных модулей 17, выход суммы 31 вычислительных модулей 17, вход 32 и выход 33 переноса вычислительных модулей 17.

Вычислительный модуль 16 (фиг.4) содержит четырехразрядный сумматор 34 и элементы И .

Вычислительный модуль 17 (фиг.5) содержит четырехразрядный сумматор 36, элементы И , элементы И 384-384. и элементы ИЛИ 39 -394Корректор 18 (фиг.6) содержит де- шифратор 4 - 16 40, элементы ИЛИ 41 , 41 , элемент ИЛИ 42 и элементы ИЛИ 43,, 432.

Блок суммирования 6 (фиг.7) (для одной тетрады) содержит сумматоры 44- 46, элемент И 47, элемент НЕ 48, элементы И 49 - 51.

P.accMofpHM функциональное назначение и реализацию основных узлов и блоков устройства.

Регистры 1 и 2 множимого и множителя предназначены для хранения п-раз рядных двоичных или n/4-разрядных десятичных сомножителей. В регистре 3 результата записывается 2п-разрядное двоичное или n/2-разрядное десятичное произведение.

Блок 4 формирования кратных множимого комбинационного типа и служит для формирования двух-, четырех-, восьмикратных множимого.

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

Модули 17 третьей строки каждой подматрицы матричного умножителя при умножении чисел, представленных в двоичной системе счисления (на прямом входе 7 выбора режима работы устройст

5

0

5 Q

5

ва уровень логического нуля), осуществляют прибавление к сумме частичных произведений, сформированной на выходе предыдущей строки вычислительных модулей, значения четырехкратного множимого с входа 11, если значение третьего разряда соответствующей тетради регистра 2 множителя равно единице, или же нуль - если значение третьего разряда соответствующей тетрады регистра 2 множителя равно нулю. При умножении чисел, представленных в десятичной системе счисления, модули 17 третьей строки каждой подматрицы осуществляют прибавление к сумме частичных произведений, сформированной на выходе предыдущей строки вычислительных модулей, четырех- или восьмикратного множимого с входов 11 и 12 соответственно, если третий или четвертый разряды соответствующей тетрады регистра 2 множителя равен единице, и значение нуля, если данные разряды равны нулю. Прибавление к сумме частичных произведений четырех- или восьмикратного множимого на одной строке модулей 17 умножения при умножении чисел, представленных в коде прямого замещения 8421, возможно потому, что два старших разряда тетрады множителя не могут одновременно быть равны единице (максимальное значение тетрады в коде прямого замещения 8421 не может быть больше 1001).

На входы 25 модулей 17 умножения четвертой строки каждой подматрицы поступает с входа 12 матрицы 5 восьмикратное множимое. На входы 30 модулей 17 умножения четвертой строки каждой подматрицы матрицы 5 умножения подается значение четвертого разряда соответствующей тетрады регистра 2 множителя. На входы 26 модулей 17 умножения четвертой строки каждой подматрицы поступает код коррекции, сформированный на выходах соответствующих корректвров 18. На входы 28 и 29 модулей 17 умножения четвертой строки каждой подматрицы матрицы 5 умножения подаются управляющие сигналы с инверсного 74 и прямого 7 входов входа 7 выбора режима работы устройства соответственно.

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

частичных произведений, сформированной на выходе предыдущей строки модулей 17 восьмикратного множимого с входа 12, если значение четвертого разряда соответствующей тетрады регистра 2 множителя равно единице, и нуль, если значение четвертого разряда соответствующей тетрады регистра 2 множителя равно нулю. При умножении чисел, представленных в десятичной системе счисления, модули 17 четвертой строки каждой подматрицы осуществляют прибавление к сумме частичных произведений, сформированной на выходе предыдущей строки модулей 17, кода коррекции, получаемого на выходах соответствующей группы корректоров 18.

Корректор 18 предназначен для формирования кода коррекции при умножении чисел, представленных в десятичной системе счисления. Код коррекции формируется на выходах корректора по следующему правилу

С В 6, где С - код коррекции;

В - число переносов из соответствующих модулей умножения. Можно показать, что при таком построении матричного умножителя умножения значение В не может быть больше трех, т.е. ,1,2,3.

Работу корректора 18 можно описать

так как сигнал на нем всегда равен

нулю.

Блок 6 суммирования служит для . получения результата, как в двоичной, так и в десятичной системах счисления При работе в двоичной системе счисления блок 6 суммирования осуществляет прибавпение к сумме, полученной на 10 выходе 14 матричного умножителя, значений переносов, сформированных на выходе 15 матричного умножителя. При работе в десятичной системе счисления наряду с учетом переносов осуществля- ется коррекция результата по следующему алгоритму.

Анализируются межтетрадные переносы, возникшие на выходе 15 матричного умножителя. Если в некоторой тетраде выходной перенос равен единице, то к содержимому данной тетрады необходимо прибавить код коррекции 0110.

Далее, на втором этапе, анализируются межтетрадные переносы, возникшие при первом двоичном суммировании кода 0110. Если в некоторой тетраде перенос равен единице, то к содержи15

20

25

Входы корректора 48

х,х4 х, х.

Выходы корректора 18

4 УЗ Уг у

40

мому данной тетрады необходимо приба- 30 вить код коррекции 0110.

На третьем этапе, если при выполнении второго этапа в некоторой тетраде имеет место запрещенная комбина- следующеи таблицей истинности. ч «LJij ция (1010-1111), то к содержимому

jc данной тетрады необходимо прибавить код коррекции 0110.

Блок суммирования 6 при работе в - двоичной системе счисления на вход 7 выбора режима работы подается значение логического нуля, в результате чего на выходе элементов И 47, 49, 50, 51 формируются значения логич ес- кого нуля.

Сумматоры 44 и 45 осуществляют суммирование сумм, полученных на выходах 14 матричного умножителя с значениями переносов сформированных на выходе 15 матричного умножителя, т.е. фактически преобразует двухрядный код результата в однорядный.

При работе в десятичной системе счисления на вход 7 выбора режима работы устройства подается значение логической единицы. Если на выходе 15 переносов умножителя 5 какой либо тетрады возник перенос, то к значению данной тетрады на соответствующем сумматоре 44 прибавляется код коррекции 0110, сформированный элементом И 47.

О О О

о о о о о 1 1 1 1 1 1 1 1

о

о о о 1 1 1 1 о о о о 1 1 1 1

о о 1 1

о о 1 1 о о 1 1 о о 1 1

о 1

о 1

о 1

о 1

о 1 о 1 о 1

о 1

о о о 1

о 1 1 1

о 1 1 1 1 1 1

X

о о о о о о о 1

о о о 1 о 1 1

X

о 1 1 о 1 о о о 1 о о о о о о

X

о 1 1 1 1 1 1 о 1 1 1 о 1

о о

X

о о о о о

О

о о о о о о о о о

X

45

50

Выходы Уг , Уэ, У 4 образуют первый выход корректора (выход суммы), а У 5 - второй выход корректора (выход переноса). Выход У4 не используется,

55

так как сигнал на нем всегда равен

нулю.

Блок 6 суммирования служит для . получения результата, как в двоичной, так и в десятичной системах счисления. При работе в двоичной системе счисления блок 6 суммирования осуществляет прибавпение к сумме, полученной на 0 выходе 14 матричного умножителя, значений переносов, сформированных на выходе 15 матричного умножителя. При работе в десятичной системе счисления наряду с учетом переносов осуществля- ется коррекция результата по следующему алгоритму.

Анализируются межтетрадные переносы, возникшие на выходе 15 матричного умножителя. Если в некоторой тетраде выходной перенос равен единице, то к содержимому данной тетрады необходимо прибавить код коррекции 0110.

Далее, на втором этапе, анализируются межтетрадные переносы, возникшие при первом двоичном суммировании кода 0110. Если в некоторой тетраде перенос равен единице, то к содержи5

40

45

50

55

В предлагаемом варианте построения блока 6 суммирования второй и третий шаги алгоритма коррекции объединены. В результате этого, если при прибавлении кода 0110 на выходе пере- носа сумматора 44 возникает перенос, то в сумматоре 45 к результату, полученному на выходе сумматора 44, прибавляется код 1100 (0110+0110), сфор- мированный элементом И 50, если же перенос на выходе переноса сумматора 44 не возник, то к данной тетраде на сумматоре 45 прибавляется код 0110, сформированный элементом И 49.

Этим самым обеспечивается избыток шести во входной информации сумматора 45. Перенос, возникающий на выходе сумматора 45 поступает на вход переноса последующего сумматора 45. В том случае, если из какой-либо тетрады сумматора 45, не возникает перенос, то из данной тетрады на сумматоре 46 вычитается код 0110 путем суммирования с кодом 1010, сформированным на выходе элемента И 51.

Рассмотрим работу устройства при умножении двоичных и десятичных чисел

В режиме умножения чисел, представленных в двоичной системе счисле- ния по сигналу на входе 7 выбора режима работы устройства блок 4 формирования кратных множимого, умножитель 5 и блок 6 суммирования настраиваются на работу с двоичными числами. Далее, по сигналу на управляющем входе 8 устройства одновременно или последовательно во времени в регистры 1 и 2 соответственно множимого и множителя загружаются n-разрядные двоичные сом- ножители без знаков. После этого, .на выходах блока 4 формирования кратных множимого формируются двух-, четырех- и восьмикратные множимого простым сдвигом влево на один, два и три дво- ичных разряда соответственно. Значения разрядов регистра 1 множимого и двукратного множимого через входы 9, 10 поступают на первые входы модулей 16 первой и второй строки каждой подматрицы умножителя 5 соответственно, четырехкратное и восьмикратное множимые через входы 11, 12 поступают на соответствующие входы модулей 17 третьей и четвертой строк каждой подматрицы умножителя 5 соответственно. Каждая строка умножителя 5 управляется соответствующим двоичным разрядом регистра 2 множителя. Если разряд

е

Q 5

«

5

0

5

множителя равен единице, то в соответствующей строке модулей осуществляется прибавление кратного множимого к сумме частичных произведений, сформированной на выходе предыдущей строки модулей умножения. Тетрадные переносы в умножителе 5 распространяются не вдоль строки матрицы, в которой они формируются, а подаются на вход переноса соответствующего модуля следующей строки умножителя 5. Таким образом, на выходе 14 умножителя Ь умножения формируется значение суммы частичных произведений3 а на выходе 15 - значение переносов, к.оторые далее суммируются в блоке 6 суммирования по правилам двоичной арифметики. Сформированный в блоке 6 двоичный результат по сигналу на входе 8 записывается в регистр 3 результата.

В режиме умножения чисел, представленных в десятичной системе счисления, по сигналу на входе 7 выбора режима работы устройства блок 4 формирования кратных множимого, умножитель 5 и блок 6 суммирования настраиваются на работу с десятичными чис- лами.

Далее, по сигналу на управляющем входе 8 устройства одновременно или последовательно во времени в регистры 1 и 2 соответственно множимого и множителя загружаются десятичные сомножители без знаков. После этого на выходах блока 4 формирования кратных множимого формируются двух-, четырех- и восьмикратные множимого в десятичной системе счисления. Значение разрядов регистра 1 множимого и двухкратного множимого через входы 9 и 10 поступают на первые входы модулей 16 первой и второй строк каждой подматрицы умножителя 5 соответственно, четырехкратное и восьмикратное множимые через входы 11 и 12 поступают на соответствующие входы модулей 17 третьей строки каждой подматрицы умножителя 5. На вход модулей 17 четвертой строки каждой подматрицы умножителя 5 поступает код коррекции, сформированный соответствующей группой кг фекторов 18.

Рассмотрим работу умножителя 5 на примере одной из ее подматриц.

Модули 16 первой строки подматрицы осуществляют прибавление к сумме частичных произведений, сформированной на выходах модулей 17 предыдущей строки, частичного произведения множимаго на первый (самый младший) двоичный разряд соответствующей тетрады регистра 2 множителя. Далее, сумма частичных произведений, полученная на выходах модулей 16 .первой строки подматрицы, суммируется с частичным произведением множимого на второй двоичный разряд соответствующей тет суммы частичных, произведений, а на выходе 15 - значения тетрадных переносов, которые далее суммируются в блоке 6 суммирования по следующему правилу: если значение переноса из данной тетрады равно единице, то к данной тетраде прибавляется коррекция 0110; если в результате суммирования

Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств для умножения двоичных и десятичных чисел. Целью изобретения является увеличение быстродействия устройства. Устройство содержит регистр множимого, регистр множителя, регистр результата, блок формирования кратных множимого, матричный умножитель и блок суммирования. Введение в матричный умножитель групп по N/4 корректоров, а также изменение связей внутри вычислительных модулей умножения позволило выполнять умножение десятичных чисел за один такт и тем самым обеспечить положительный эффект, заключающийся в увеличении быстродействия при умножении десятичных чисел. 3 з.п. ф-лы. 7 ил.

рады регистра 2 множителя. На модулях ю этой коррекции в некоторой тетраде

15

16 второй строки подматрицы, т.е. на этих вычислительных модулях прибавляется или не прибавляется двухкратное множимое. Затем на модулях 17 третьей строки подматрицы к сумме частичных произведений, сформированной на выходах модулей 16 второй строки подматрицы прибавляется частичное произведение множимого на третий двоичный разряд соответствующей тетрады регистра 2 множителя или же частичное произведение множимого на четвертый двоичный разряд соответствующей тетрады регистра 2, т.е. прибавляется или четырехкратное множимое, или восьмикрат-25 ное или ничего не прибавляется. Далее, полученная в рассматриваемой подматрице сумма частичных произведений корректируется на модулях 17 четвервозникает перенос, то к содержимому данной тетрады прибавляется код 011 для поддержания в данной тетраде из бытка шесть. Сформированный десятич ный результат на выходах блока 6 по

устройства запис

сигналу на входе о вается в регистр 3

результата.

20

Формула изобретени

той строки подматрицы (коррекция свя- зо входом блока формирования кратных мнозана с тем, что в модулях 16 и 17 суммирование осуществляется по правилам двоичной арифметики). Код коррекции формируется на специально введенной в устройство группе корректоров 18 по следующему алгоритму.

Если в результате суммирования по правилам двоичной арифметики десятичных чисел, представленных в коде прямого замещения 8421, из некоторой тетрады возникает перенос, то необходимо в данную тетраду прибавить код 0110. Каждый корректор 18 формирует код коррекции, исходя из значений сигналов на выходах переносов четырех модулей Однако не трудно показать, что в устройстве одновременно может возникнуть не более трех переносов, т.е. значение коррекции может быть равно 0,6,12 или же 18. Аналогично работают остальные подматрицы умножителя 5. Тетрадные переносы в умножителе 5 распространяются не вдоль строки умножителя 5, в которой они образуются, а подаются на вход переноса соответствующего модуля следующей строки умножителя 5. В результате всего этого на выходе 14 умножителя 5 формируется скорректированное значение

35

40

45

50

55

жимого и первым информационным входом матричного умножителя, второй, третий и четвертый информационные входы которого соединены соответственно с выходами двукратного, четырехкратного и восьмикратного множимых блоков формирования кратных множимого, управляющий вход которого соединен с входом выбора режима работы устройства, выходы 1-х разрядов К-й тетрады регистра множителя соединены соответственно с i-ми управляющими входами группы матричного умножителя (,...,n/4,n - разрядность сомножителей, ,...,4), о т - личающееся тем, что, с целью повышения быстродействия,выходы первой и второй групп матричного умножителя соединены соответственно с входами первого и второго слагаемых блока суммирования, выход которого соединен с информационным входом регистра результата, вход выбора режима работы устройства соединен с входом выбора режима работы матричного умножителя и блока суммирования.

возникает перенос, то к содержимому данной тетрады прибавляется код 0110 для поддержания в данной тетраде избытка шесть. Сформированный десятичный результат на выходах блока 6 по

устройства записысигналу на входе о вается в регистр 3

результата.

Формула изобретения

5

0

5

0

5

жимого и первым информационным входом матричного умножителя, второй, третий и четвертый информационные входы которого соединены соответственно с выходами двукратного, четырехкратного и восьмикратного множимых блоков формирования кратных множимого, управляющий вход которого соединен с входом выбора режима работы устройства, выходы 1-х разрядов К-й тетрады регистра множителя соединены соответственно с i-ми управляющими входами группы матричного умножителя (,...,n/4,n - разрядность сомножителей, ,...,4), о т - личающееся тем, что, с целью повышения быстродействия,выходы первой и второй групп матричного умножителя соединены соответственно с входами первого и второго слагаемых блока суммирования, выход которого соединен с информационным входом регистра результата, вход выбора режима работы устройства соединен с входом выбора режима работы матричного умножителя и блока суммирования.

п/4 корректоров и четыре строки вычислительных модулей, причем первая строка содержит п/4, а остальные по (п/4+1) вычислительных модулей, при этом первый, второй и третий информационные входы матричного умножителя соединены соответственно с первыми входами вычислительных модулей первой, второй и третьей строк каждой подматрицы матричного умножителя, первый, второй и третий управляющие входы группы которого соединены соответственно с вторыми входами вычислительных модулей первой, второй и третьей строк каждой подматрицы матричного умножителя, третьи входы К-х вычислительных модулей j-й строки (,3,4) К-й подматрицы которого соединены соответственно с выходами суммы k-x вычислительных модулей (.1-1)-и Строки К-й подматрицы матричного умножителя, третьи входы k-x вычислительных модулей первой строки Р-й подматрицы (,.. . ,п/4) которого соединены соответственно с выходами суммы (К+1)-ых вычислительных модулей четвертой строки (Р-1)-й подматрицы матричного умножителя, третьи входы и входы переноса К-х вычислительных модулей первой строки первой подматрицы и входы переноса первых вычислительных модулей 1-х строк каждой подматрицы матричного умножителя соединены с входом логического Нуля устройства, четвертый информационный вход матричного умножителя соединен с четвертыми входами вычислительных модуле третьей и четвертой строк каждой подматрицы матричного умножителя, пятые входы вычислительных модулей четвертой строки каждой подматрицы которого соединены с пятыми входами вычислительных модулей третьей строки каждой подматрицы матричного /умножителя и четвертым управляющим входом группы матричного умножи теля, прямой вход выбора режима работы которого соединен с шестыми входами вычислительных модулей третьей, вторыми входами вычислительных модулей и четвертой стро каждой подматрицы матричного умножителя, инверсный вход выбора режима работы которого соединен с шестыми

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

Q -

5

0

5

соответственно с первым выходом К-го корректора группы и вторым выходом (К-1)-го корректора группы этой же подматрицы матричного умножителя, выход переноса t-ro вычислительного модуля (,...,п/4) 1-й строки (1я в1,2,3) каждой подматрицы которого соединен соответственно с входом переноса (t+1)-ro вычислительного модуля (1+1)-й строки и третьим, вторым и перзым входами t-ro корректора группы каждой подматрицы матричного умнож#- теля, вход переноса (t+1)-rd вычислительного модуля первой строки Р-й подматрицы которого соединен соответственно с выходом переноса t-ro вычислительного модуля четвертой строки (р-1)-й подматрицы и четвертым входом t-ro корректора Р-й подматрицы матричного умножителя, выходы суммы т-х вычислительных модулей четвертой строки n/4-й подматрицы (,...,п/4+1) и вы ходы суммы первых вычислительных модулей четвертой строки подматриц с первой по (п/4-1)-ную соединены с выходами первой группы матричного умножителя, выходы второй группы которого соединены с выходами переноса га-х вычислительных модулей четвертой строки п/-4-й подматрицы матричного умножителя и вторыми выходами n/4-x корректо- оов группы каждой подматрицы матричного умножителя.

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

11Ш51

I

I.

S. «a 8