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

v

ё

Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств для умножения двоичных и десятичных чисел. Целью изобретения является увеличение быстродействия устройства. Устройство для умножения содержит регистр множимого 1, регистр множителя 2, регистр результата 3, блок 4 формирования кратных множимого, матричный умножитель 5 и блок 6 суммирования. Цель изобретения достигается за счет сокращения времени задержки информации в матричном умножителе, так как формирование кода коррекции происходит во время формирования результатов на выходе вычислительных модулей третьей строки подматрицы, то есть наличие групп корректоров в матричном умножителе не вносит задержки. 8 ил., 2 табл.

-Э

6в

12 /;ф ХЫ ф

0

75

;«

Os 1

О

о

00

ел

Фие.1

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

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

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

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

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

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

Матричный умножитель 5 (фиг.З) содержит п/4 подматриц, каждая из которых содержит первую строку из п/4 вычислительных модулей 16, и вторую строку из (п/4 + 1) вычислительных модулей 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, элементы И 37i-37/i, элементы И и элементы ИЛИ 39i-39.q

Корректор 18 (фиг.6) содержит элементы И 40, сумматор 41 по модулю два, элемент ИЛИ 42, элемент И 43, элемент ИЛИ-НЕ 44, элемент И 45, элементы ИЛИ

46, элемент ИЛИ 47.

В тетраду блока 6 суммирования (фиг.7) входят двоичные четырехразрядные двух- входовые сумматоры 48-49, двоичный трехразрядный двухвходовой сумматор 50,

0 корректор 51, элемент НЕ 52, элементы И 53-55, двоичный четырехразрядный двухвходовой сумматор 56.

Корректор 51 (фиг.8) содержит сумматор 57 по модулю два, элементы ИЛИ 58 и 59 и

5 элементы И 60-62.

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

Регистры 1 и 2 множимого и множителя

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

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

Модули 16 первой и второй строк осу0 ществляют прибавление к сумме частичных произведений, сформированной на выходе предыдущей строки модулей умножения в двухрядном коде (значения тетрадных переносов модулей умножения предыдущей

5 строки подаются на входы 23 переноса модулей 16, а значения суммы на входы 20 модулей 16), соответствующего кратного множимого с выхода регистра 1 множимого или выхода блока 4 формирования кратных

0 множимого, если значение двоичного разряда множителя на входе 21 данных модулей 16 равно единице, или же значение нуля, если двоичный разряд множителя равен нулю.

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

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

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

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

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

С- В 6,

где С - код коррекции

В - число переносов из соответствующих модуле1 множения

Работу корректора 18 можно описать таблицей истинности приведенной в табл 1.

Выходы У2, Y3, Y4 образуют первый выход корректора (выход суммь ) a Y5 второй выход корректора (выход перенося) Выход Y1 не используется так как сигнал на нем всегда равен нулю

Блок 6 суммирования служит для пол учения конечного результат как в двоичной так и в десятичной системах счисления При

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

На первом этапе двухрядный код, полученный на выходе 14 матричного умножителя 5 потетрадно приводится к однорядному путем суммирования на тетрадных сумматорах. Затем анализируются межтетрадные переносы, возникающие на двух последних строках матричного умножителя, и тетрадные переносы, возникающие в резулотэте потетрэдного суммирования двухрядного кода с выхода 4 матричного умножителя В зависимости от ч: ела межтетрадных переносов формируется код коррекции 0, б, 12 или 18, если число переносов равно 0,1,2 или 3 соответственно Далее полученный код коррекции суммируется с однорядным кодом результата

На втором этапе анализируются межтетрадные переносы, возникшие при суммировании кода коррекции с однорядным кодом результата Гели в некоторой тетраде перенос равен единице го к содержимому ДРННОИ тетрады необходимо прибавить О 110 для коррекции

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

Корректор 51 предназначен для форми- рпвания кода коррекции при суммировании чисрл представленных в десятичной системе счисления Код юррекции формируется на В Одвх корректора по следующему праi И ,

С F б,

где С код коррекции,

Г число переносов из тетрад.

Работу корректора 51 можно описать таблицей истинности приведенной в табт

Выходы Y2, Y3 Y4 образуют первый выход корректора (выход суммы), a Y5 - второй его вычод (выход переноса) Выход Y1 не используется так как сигнал на нем всегда равон н/лю Поясним функционирование бпока 6 гуммирования При ртботе в двоичной системе счисления на вход 7 выбора

режима работы подается значение О, в результате чего на выходе элементов И 5355и корректора 51 формируются значения О. Сумматоры 56, 48, 49 преобразуют двухрядный код, полученный на выходе 14 матричного умножителя 5 к однорядному.

При работе в десятичной системе счисления на вход выбора режима работы устройства подается значение 1. Сумматоры

56осуществляют потетрадное преобразование двухрядного кода результата, полученного на выходе 14 матричного умножителя, к однорядному. Далее в зависимости от числа переносов корректор 51 формирует код коррекции, который затем потетрадно суммируется с однорядным результатом на сумматоре 28. В предлагаемом варианте построения блока 6 суммирования второй и третий шаги алгоритма коррекции объединены. В результате этого, если при прибавлении кода коррекции на выходе переноса сумматора 48 возникает перенос, то в сумматоре 49 к результату, полученному на выходе сумматора 48, прибавляется код 1100 (0110 + 0110), сформированный элементом И 54, если же перенос на выходе переноса сумматора 48 не возникает, то к данной тетраде на сумматоре 49 прибавляется код 0110, сформированный элементом И 53. Этим самым обеспечивается избыток шести во входной информации сумматора 49. Перенос, возникающий на выходе сумматора 49, поступает на вход переноса последующего сумматора 49. В том случае, если из какой-либо тетрады сумматора 49 не возникает перенос, то из данной тетрады на сумматоре 50 вычитается код 0110 путем суммирования с кодом 1010, сформированным на выходе элемента И 55. В качестве сумматоров 49 можно использовать быстродействующий 2п-разрядный двоичный сумматор, например параллельно-параллельного типа

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

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

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

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

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

5 6 суммирования настраиваются на работу с десятичными числами Далее по сигналу на входе 8 управления устройства одновременно или последовательно во времени в регистры 1 и 2 соответственно множимого и

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

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

Модули 16 первой строки подматрицы осуществляют прибавление к сумме частичных произведений, сформированной на выходах модулей 17 предыдущей строки, частичного произведения, множимого на первый (самый младший) двоичный разряд соответствующей тетрады регистра 2 множителя. Далее сумма частичных произведений, полученная в двухрядном коде на выходах модулей 16 первой строки подматрицы, суммируется с частичным произведением множимого на второй двоичный разряд соответствующей тетрады регистра 2 множителя. На модулях 16 второй строки подматрицы, т.е. на этих модулях прибавляется или не-прибавляется двухкратное множимое. Затем на модулях 17 третьей строки подматрицы к сумме частичных произведений, сформированной в двухрядном коде на выходах модулей 16 второй строки подматрицы, прибавляется частичное произзеде- ние множимого на третий двоичный разряд соответствующей тетрады регистра 2 множителя или частичное произведение множимого на четвертый двоичный разряд соответствующей тетрады регистра 2, i e прибавляется или четырехкратное множимое или восьмикратное или ничего не прибавляется. Далее полученная в рассматриваемой подматрице сумма са.:- тичных произведении корректируется на модулях 17 четвертой строки подматрицы (коррекция связана с тэм. что в модулях 16 17 суммирование осуществляется по правилам двоичной арифметики). Код коррекции формируется на специально введенной в устройство группе корректоров 18 по следующему алгоритму. Если в результате суммирования по правилам двоичной арифметики десятичных «исел, представленных в коде прямого замещения 8421, из некоторой тетрады возникает перенос, то необходимо в данную тзтраду прибавить код 0110. Каждый корректор 18 формирует код коррекции, исходя из значений сигналов на выходах переносов четырех модулей. Аналогично работают остальные подматрицы матричного умножителя, переносы в умножителе 5 распространяются не вдоль строки умножителя 5, в которой они образуются, а подаются на вход соответствующего модуля следующей строки умножителя 5. В результате всего этого на выходе 14 суммы умножителя 5 формируется скорректированное значение суммы частичных произведений в двухрядном коде, а на выходе 15 переносов - значения тетрадных переносов для коррекции результатов, которые далее обрабатываются в блоке 6 суммирования по следующему правилу: двухрядный код суммы частичных произведений преобразуется потетрадно к однорядному, затем в зависимости от числа тетрадных переносов формируется код коррекции который 5 прибавляется к однорядному результату, если в результате суммирования этой коррекции в некоторой тетраде возникает перенос, то к содержимому данной тетрады прибавляется код 0110 для поддержания в данной

0 тетраде избытка шесть Сформированный десятичный резуль гат на выходах блока 6 по сигналу на входе 8 управления устройства записывается в регистр 3 результата. Формула изобретения

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

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

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

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

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

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

n/4-й подматрицы (т 1п/4-П)и выходы

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

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

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

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

0 третьей строки n/4-й подматрицы и выходы тетрадных переносов первых вычислительных модулей третьей строки подматриц с первой по (п/4-1)-ю соединены с выходами второй группы матричного умножителя.

Таблица 1

П5-

t-я с/прока № i 2-я с/прока Г7 I J-я с/лрока П Л 4-я с/прохо

Фиг. Z

Продолжение табл.

Таблица 2

1-я строка 2-я строка IJ-a строка 4- с/прот

1-я лодмо/прица

, 2-я лодмолфуца

3-я подмо/прица

LO

со

to о riЈ

0 S fc SN

&

I

I

I- t, -

Vr,

t.

го

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

Пердый дыход корректора Фигв