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

 

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

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

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

РЕСПУБЛИК (5Н 4 С 06 F 7/52

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

H А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21} 43 9080/24-24 (22) 25.01.88 (46) 15.08.89. Вюл. У 30 (71) Харьковский политехнический институт им.В.И.Ленина (72) В.В.Шатилло и С.Н,Прохоров (53) 681.325 (088.8) (56) Авторское свидетельство СССР

У 1117635, кл. С 06 F 7/52, 1983.

Авторское свидетельство СССР

Ф 1156664, кл. G 06 F 7/52, 1982. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ (57) Изобретение относится к цифровой вычислительной технике и предназначено для использования в униИзобретение относится к цифровой вычислительной технике и предназначено для использования в универсаль ных и специализированных цифровых вычислительных устройствах, Целью изобретения является расширение функциональных возможностей за счет обеспечения умножения чисел, представленных в дополнительном ко де.

На фиг.1 представлена функциональная схема устройства для умножения; на фиг.2 — схема (j,Ê)-го одноразрядного сумматора матрицы, кроме (р,К)-го и (2р,К)-го одноразрядных сумматоров матрицы; на фиг.3— схема (р,К)-го и (2р,К)-го одноразрядных сумматоров матрицы; на фиг.4 — функциональная схема (j,n)„,SU„„ 47 А 1

2 версальных и специализированных цифровых вычислительных устройствах.

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

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

-ro одноразрядного сумматора матрицы,, кроме (р,n)-го и (2р,n}-го одноразрядных сумматоров матрицы; на фиг.5— функциональная схема (р,n)-ro u (2р,n)-ro одноразрядных сумматоров матрицы; на фиг.6 — временные диаграммы работы устройства соответст венно в прямом и дополнительных кодах.

Устройство для умножения (фиг.1) содержит матрицу одноразрядных сумматоров 1.1-1п-1, 2.1-1.п-1, 3.1,3 п-1, 4,1-4.п-1 и 5.1-5.4, матрицу элементов И 6, входы 7.1-7.п разрядов первого операнда А устройства, .входы 8.1-8.4 разрядов второго операнда В устройства, первый 9.1-9.2 и второй 10.1-10.2 входы сброса

3 1501047 устройства, выходы 1).1-11.4 произведения устройства, дополнительные информационные входы 12.1-12.4 устройства, выходы 13.1-13.2п-1 устройства, управляющий вход 14.устройства.

Одноразрядные сумматоры 1.1-1.п-1, 3. 1-3. и-1 (фиг. 2) содержат семь элементов И 15, два элемента ИЛИ-16 и 10 три элемента НЕ 17, первый 18, второй 19 и третий 20 информационные входы одноразрядных сумматоров, выход суммы 21 и переноса 22 одноразрядного сумматора. 15

Одноразрядные сумматоры 2.1-2.п-1, 4.1-4.п-1 (фиг.3) содержат четыре элемента НЕ 23, девять элементов

И 24, два элемента ИЛИ 25 и элемент

26 задержки, первый 27, второй 28 20 и третий 29 информационные входы одноразрядных сумматоров, первый 30 и второй 31 управляющие входы одноразрядных сумматоров, выход суммы

32 и переноса 33 одноразрядных сумматоров, первый 34 и второй 35 управляющие выходы одноразрядных сумматоров.

Одноразрядные сумматоры 5 ° 1 и .

5.3 (фиг.4) содержат четыре элемен- . 30 та HE Зб,семь элементов И 37 и два элемента ИЛИ 38, первый 39, второй

40 и третий 41 информационные входы одноразрядных сумматоров, управляющий вход 42 одноразрядных суммато- 35 ров, выходы суммы 43 и переноса 44 одноразрядных сумматоров.

Одноразрядные сумматоры 5.2 и

5.4 (фиг.5) содержат шесть элементов НЕ 45, десять элементов И 46, 40 два элемента ИЛИ 47 и элемент 48 задержки, первый 49, второй 50, третий 51 информационные входы одноразрядных сумматоров, первый 52 и второй 53 и третий 54 управляющие вхо- 45 ды одноразрядных сумматоров, выходы суммы 55 и переноса 56 одноразрядных сумматоров, первый 57 и второй 58 управляющие входы одноразрядных сумматоров. 50

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

При умножении двоичных чисел А и В, представленных в прямом коде, в исходном состоянии на входах 9 ° 1, 9.2, 10. 1, 10.2 устанавливается сигнал "1" (фиг.б). На входах 12 112.4 и 14 устанавливается сигнал "О".

При этом сумматоры 5.1-5.4 реализуют обычные функции суммы и переноса.

Перед началом работы устройства для умножения на вход 10.2 подается отрицательный импульс., который сбрасывает одноразрядные сумматоры 4.14.п-1,5.4 в нулевое состояние. На всех выходах суммы и переноса устанавливается сигнал "О".

Процесс вычисления начинается с подачи на входы 7.1,...,7n и-разрядного двоичного множимого А и двух младших разрядов В, В и-разрядного множителя В на входы 8.1 и 8.2. Через время Т на вход 9.1 подается сигнал "0", по которому производится суммирование на сумматорах 2.1-2.п-1 и 5 ° 2.

Когда вычисления в первых двух строках заканчиваются, на вход 9.1 подается сигнал "1", который осуществляет запоминание информации, установившейся на входах сумматоров

2.1-2.n-i, 5.2 и запрещает обработку сумматорами 2.1-2.п-1, 5.2 сигна- лов, которые будут появляться на их информационных входах.

В течение времени, пока проходит вычисление на сумматорах 1.1-1. п-1, 5. 1 и 2. 1 — 2. п-1, 5. 2, на сумматорах 3. 1-3. п-1, 5. 3 и 4. 1 — 4. п-1, 5.4 идет подготовка к вычислению, на входы 8.3-8.4 подаются разряды

В и В4 множителя В. К моменту завершения подачи В и В+ вычисление продолжается на сумматорах 3.1-3. п-1, 5.3, а затем после подачи на вход 9.2 сигнала "0" вычисление осуществляется и на сумматорах 4.14. п-1, 5.4.

В то же время на сумматорах 1.1п-1, 5.1 и 2.1 — 2. п-1, 5.2 осуществляется считывание двух младших разрядов С, и С произведения С с выходов 11.1 и 11.2, а также подача разрядов В и В множителя В на входы 8.1 и 8.2.

После подачи на вход 9.2 сигнала

"1", который осуществляет запоминание промежуточного результата на выходах сумматоров 4.1-4. п-1, 5.4, а также запрет обработки сумматорами 4.1 - 4.п-1, 5.4 поступающей информации, вычисление продолжается в сумматорах 1.1 — 1. п-1, 5.1 и

2.1 — 2. п-1, 5.2. В течение времени, пока идут вычисления, осуществляется считывание разрядов С и С

5 15 произведения С с выходов умножителя

11.3 и 11.4 и подача разрядов В> и

Ве на входы 8.3 и 8.4.

Процесс продолжается циклически.

Когда все п разрядов множителя В будут поданы, на входах 8.1-8 ° 4 устанавливается сигнал "0", а процесс вычисления не прекращается до получения всех 2п разрядов произведения

С с выходов 11.1-11.4.

При умножении двоичных чисел А и В, представленных в дополнительном коде, в исходном состоянии на входах 9.1, 9.2, 10.1, 10.2, а также и на входах 12.1 — 12.4, 14 устанавливается сигнал "!" (фиг ° 7).

Перед началом работы устройства для умножения на вход 10.2, как и при умножении чисел, представленных в прямом коде, подается отрицательный импульс, который сбрасывает одноразрядные сумматоры 4.1-4.п-1 в нулевое состояние, а на выходах суммы и переноса сумматора 5.4 при этом устанавливаются соответственно сигналы "0" и "1" ° В дальнейшем работа устройства умножения аналогичНа умножению в прямом коде за исклюФ чением того, что в последних и тактах на входы 8.1-8.4 подается не сигнал "О.", а старший знаковый разряд Вп множителя В.

При подаче на входы 12.1 — 12.4 и 14 сигнала "1" сумматоры 5.1, 5.3 реализуют логические функции:

s =а р=а b, где а — сигнал на первом информационном входе 39 сумматоррв 5.1 и 5.3;

Ь вЂ” сигнал на втором информационном входе 40 сумматоров 5.1 и 5.3;

s p — соответственно значения сигналов на выходе суммы

43 и выходе переноса 44 сумматоров 5. 1 и 5.3.

Сумматоры 5.2 и 5 ° 4 реализуют следующие логические функции (без учета цепей начальной установки):

s(t+1) = а.z + s(t) z;

p(t+1) = à.b z +p(t) z, 01047 где а сигнал на первом информационном входе 49 сумматороь

5.2 и 5.4; сигнал на втором информационном входе 50 сумматоров

5.2 и 5.4; сигнал на первом управляющем входе 52 сумматоров

5.2 и 5.4;

5 — значения сигналов на выходе суммы 55 сумматоров

5.2 и 5.4 в последующий и предыдущий моменты времени; р(с+1), p(t) — значения сигналов на выходе переноса сумматоров

20 5.2, 5.4 в последующий и предыдущий моменты времени.

Реализация приведенных функций

° позволяет учесть, что вес знакового

25 разряда отрицателен, и если знаковый разряд А, множимого А равен "1", то сумматоры 5.1 — 5.4 производят фактически не добавление, а вычитание множителя В иэ суммы остальных

30 частичных произведений. Таким образом, учитывается алгебраический знак множимого 4.

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

1 р должна определяться, исходя иэ следующей системы неравенств:

Алгебраический знак множителя В учитывается путем расширения разрядной сетки (т. е. подачи в последних и тактах умножения на входы 8.1-8.4 знакового разряда В„) и начальной установки "1" по выходу переноса сум40 матора 5 4

При необходимости ускорения получения результата умножения используются выходы 13.1-13.2 п-1, на которых после и первых тактов получается

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

1501047 -о г » и (tel н НЕ t min И )

N0x at г + и т +Т -Т г Îõ к tffoy K&ih > En h при TK„„„„и Т „не меньше чем

М Т (т -Т .)„пиТ

1 + мак каюк км;л j ° P к „„„либо Т,„ „меньше чем (Tx + e„h ) кwin -о

Ь +" . Р : (Р-1) „-(+г „," нь) ) р мру

r e

ma к

t и м1ff максимальное и минимальное время переходного процесса в логическом элементе. И; максимальное время, необходимое для считывания результата с выходов 11.1-11.4 °

Т

Змс к

Т

Т

Kmin — максимальное и миниМах (35

Ч-Р

tvax HE

tQ g

mar HE — максимальное время переходного процесса в логическом элемента НЕ

40 при переходе соответсте венно из "1" в "0" и из

IlPff "1" ° — минимальное время переходного процесса в логическом элементе НЕ при переходе из "1" в

"0"

v л-О

t м и HF мальное время коммутации разрядов множителя

В на входах 8.1-8.4 с учетом времени прохож- . дения сигналов через элементьг И; величина,. равная большему иэ элементов, записанных в квадратных скобках. величина временной задержки сигнала в элементе задержки;

Наличие в устройстве для умножения входов 12. 1-12.4 позволяет наращивать разрядность. Это удобно при модульной реализации устройства или выполнении его в виде интегральной схемы. При этом увеличение разрядности достигается соответствующей коммутацией входов 12.1-12.4 одного модуля с выходами 11.1-11.4 другого модуля.

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

Устройство для умножения, содержащее матрицу элементов И и матрицу одноразрядных сумматоров, причем первые входы элементов И i-ro столбца матрицы (i=1,2,..., n, п — разрядность первого операнда) соединены соответственно с входом i-го разряда первого операнда устройства, вход j-го разряда второго операнда которого соединен с вторыми входами элементов И )-й строки матрицы (j=

=1,...,2р, р — произвольное целое число), выход (j, i)-ro элемента И матрицы соединен соответственно с первым информационным входом (j,i)ro одноразраядного сумматора матрицы, выход переноса которого, кроме (2р,i)-х одноразрядных сумматоров матрицы, соединен соответственно с вторым информационным входом (j+1, i)-ro одноразрядного сумматора матрицы, выход суммы (j 1)-ro одноразрядного сумматора матрицы, кроме (2р,i)-х одноразрядных сумматоров матрицы, (1=2,...,n), соединен соответственно с третьим информационным входом ()+1, k)-ro одноразрядного сумматора матрицы (1с=1,2,..., п-1), третий информационный вход (j,ï)-го одноразрядного сумматора матрицы соединен соответственно с j-м дополнительным информационным входом устройства, выход переноса (2 р,i)-го. одноразрядного сумматора матрицы соединен соответственно с вторым информационным входом (1,i)ro одноразрядного сумматора матрицы, выход суммы (2р,1)-го одноразрядного сумматора матрицы соединен соответственно с третьим информационным входом (1 k)-ro одноразрядного сумматора матрицы, выходы суммы (j,1)-го одноразрядного сумматора матрицы и (2р, 1)-го одноразрядного

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

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

И, вход второго элемента НЕ соединен с вторым информационным входом одноразрядного сумматора матрицы, вторыми входами первого, третьего и седьмого элементов И и первым входом пятого элемента И, выход второго элемента НЕ соединен с вторыми входами второго и четвертого элементов

И, вход третьего элемента НЕ соединен с третьим информационньм входом одноразрядного сумматора матрицы, вторыми входами пятого и шестого элементов И и с третьими входами первого и второго элементов И, выход третьего элемента НЕ соединен с

I третьими входами третьего и четвертого элементов И, каждый одно-. разрядный сумматор р-й и 2р-й строк матрицы содержит девять элементов И, два элемента ИЛИ, четыре элемента НЕ и элемент задержки, причем выходы первого, второго, третьего, четвертого и пятого элементов И соединены соответственно с пятью входами первого элемента ИЛИ, выход которого соединен с выходом суммы одноразрядного сумматора мат5

55 рицы и первым входом пятого элемента И, выходы шестого, седьмого, восьмого и девятого элементов И соединены соответственно с четырьмя входами второго элемента ИЛИ, выход которого соединен с выходом переноса одноразрядного сумматора матрицы и первым входом девятого элемента И, вход первого элемента HE соединен с первым информационным входом одноразрядного сумматора матрицы и первыми входами первого, четвертого, седьмого и восьмого элементов И, выход первого элемента НЕ соединен с первыми входами второго и третьего элементов И, вход второго элемента

НЕ соединен с вторым информационным входом одноразрядного сумматора мат-,, рицы, вторыми входами первого, третьего и восьмого элементов И и первым входом шестого элемента И, выход второго элемента НЕ соединен с вторыми входами второго и четвертого элементов И, вход третьего элемента НЕ соединен с третьим информационным входом одноразрядного сумматора матрицы, вторыми входами шестого и седьмого элементов И и третьими входами первого и второго элементов И, выход третьего элемента

НЕ соединен с третьими входами третьего и четвертого элементов И, вход элемента задержки соединен с первым управляющим входом одноразрядного сумматора матрицы, вторыми входами пятого и девятого элементов И, выход элемента задержки через четвертый элемент НЕ соединен с четвертыми входами первого, второго, третьего и четвертого элементов И и третьими входами шестого, седьмого и восьмого элементов И, третьи входы пятого и девятого элементов If соединены с вторым управляющим входом одноразрядного сумматора матрицы, о т— л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей, за счет обеспечения умножения чисел, представленных в дополнительном коде, в каждый (1,n)-й одноразрядный сумматор матрицы, кроме (р,n)-го и (2р,n)-го одноразрядных сумматоров матрицы, введен четвертый элемент НЕ, выход которого соединен с третьими входами шестого и седьмого элементов И, трс. тий вход пятого элвис.пта И соединен с выходом первого э1емслтn Нf;, вход

Фиг 1

11

1 четвертого элемента НЕ соединен с управляющим входом, одноразрядного сумматора матрицы, а в каждый (р,n)-й и (2р,n)-Л одноразрядный сумматор матрицы введены десятый элементы И и пятый и шестой элементы НЕ, причем первый вход десятого элемента И соединен с третьим управляющим входом одноразрядного сумматора матрицы и входом пятого элемента НЕ, выход которого соединен с четвертыми входами седьмого и восьмого элементов И, пятый вход второго элемента ИЛИ соеди124 123 12.2 121

501047

12 нен с выходом десятого элемента И, второй вход которого через шестой элемент НЕ соединен с вторым управляющим входом одноразрядного суммато5 ра матрицы, выход первого элемента

НЕ соединен с четвертым входом шестого элемента И, управляющий вход (j n)-ro одноразрядного сумматора матрицы, кроме (р,n)-го и (2р,n)-ro одноразрядных сумматоров, и третьи управляющие входы (р,n)-го и {2p,п}ro одноразрядных сумматоров соединены с управляющим входом устройства.

ir. l

Tie 1 - 7.g

1 501047

1501047

ai. hatt.B

Вл 117.>

%97

Hx9 2

Редактор О.Спесивых

Тираж 668

Заказ 4868/44

Подписное

БНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

Bi РРР, 4.1-4, Р, tg7

Ае 1

11.2

М 113, 11 Р

Вх ЮЮ

Bg B3B4r го длй, IZ t-IX4

РЙР

Ь РРР, 11.2

8by.ï.3

РИ

Вх ВР,В

ai И.

ВФ

Составитель E.Ìóðçèíà

7exgeg, Д,0лиднык Корректор Н.Борисова