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

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

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

В устройстве операнды - положительные числа, представленные в виде

А 21а; 2 , а; 6fo,l, где А

... двоичный п-разрядный код числа А. Выполнение операции умножения в устройстве основано на таблично-алгоритмическом методе умножения с использованием конвейеризации за счет совмещения во времени получения элементарных произведений

л

У..2-и накопления частичных произведений и распараллеливания за счет совмещения во времени вычисления произведений множимого на старшую и .младшую части множителя.

tt

Пусть X х- 2 и Y

множимое и множитель соответственно, где X ; и у - значения i-x разрядов кодов сомножителей. Тогда для представления точного результата Z X«Y требуется 2п-разрядный двоичный код.

Процесс вычисления произведений

Z запишется в виде л л

Z z:(Y:z:x,-( ).(2 г, (1) -I

где X

X;х

1+1

к

,Чр-1 я двоично-кодированная цифра кода множимого в ка(онической

а

СП

позиционной системе счисления с основанием q

y;yj4.f -yj+p-i двоично- кодированная циЛра кода множителя .

Если Y представить как сумму старшей и младшей частей:

О

2

ИЛ

у;гда процесс вычисления Z

(2) запишется

вид if

Z

,

J.,РЧx:(2) ).( +

(Y

(2V ).2 r

(3)

Таким образом, п роцесс умножения состоит из однотипных повторяющихся циклов. Во время очередного j-ro цикла j -го частичное произведение Y р.cr.j

Д- X ; 2 множимого на очередные

р разрядов старшей части множителя

п „ вычисляется на К умножителях,

п

на

Р

30

выполняющих операцию умножения р-разН рядного двоичного кода Y: на р-раз-- рядньм двоичньй код X, с образованием произведения разрядности 2р, Далее элементарные произведения собираются в п + р двоично-разрядный код частичного произведения х YCT.J на 35 сумматоре, одновременно на тех же К умножителях формируются элементарные произведения X на очередные р разряов младшей части множителя Y, которые затем собираются в частичное роизведение на другом сумматоре.

Наличие регистров частичных произ ведений при соответствующем управлении позволяет организовать конвейер ри вычислении X или Х- Yд,д, когда в один и тот же момент времени на соответствующем сумматоре формируется частичное произведение X YpT.jV, MAji-i) а на другом сумматоре формируется сумма частич «-О

40

45

50

ных произведений ZJ..T.J X YCT.J (или Z

+ + X Y

мд. 1

ссы или X

ZCT.I.. --i7 9-Р

Zw,j., 2

+

+

YMA.() Процессы вычисления

cT.j-n WA.j овмещены во времени.

MA.

Г

и Z

ct.J

55

После вычисления --- п-разрядных

10

15

0

5

0

5

0

5

0

5

Z - Zj происходит суммирование на одном из сумматоров Z- и п старщих разрядов Z. В результате

3

определяются --- п старших разрядов

Z, а младшие -|- разрядов опредены при вычислении Z,,.

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

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

Блок 6 синхронизации (фиг.З) содержит выходы 16-21, вход 22 пуска, тактовый вход 23, RS-триггер 24,элемент И 25, счетчик 26 и элемент 27 памяти.

Регистр 1 множимого предназначен для хранения множимого

х i:x;(2 r Хх,.. (2)- .

Регистр 7 старшей части множителя.сдвиговый, разрядный, причем

сдвиг осуществляется на р разрядов, предназначен для хранения Y.

Умножители 3 - 3|( предназначены для вычисления очередного элементарного произведения X ;-Yj, i ,.., ...,К, имеют два р-разрядных входа и 2р-разрядный выход. В качестве умножителей могут быть применены одно- тактные матричные умножители или ПЗУ с прошитой таблицей умножения в 2 -ной системе счисления.

Первьй коммутатор 8 - р-разряд- ньй, предназначен для передачи на вход умножителей , соответствующих р разрядов с регистра 7 или 2.

Регистр 2 М)1адшей части множите

Изобретение относится к цифровой вычислительной технике и может найти применение в высокопроизводительных машинах и системах. Целью изобретения является повышение быстродействия за счет введения двух регистров, двух коммутаторов, двух сумматоров и соответствующих связей. Устройство работает по принципу конвейера, за счет наличия в нем регистров частичных произвеений, причем в каждом цикле осуществляется умножение на очередные P разрядов старшей и младшей частей множителя, (где P*983), и в процессе умножения простой основной части оборудования сведен к минимуму. 3 ил.

значений Z . и Z ддд

для определения ля - -|- + р-разрядньй, сдвиговый.

причем сдвиг осуществляется на р рязрядов, предназначен для хранения

АЛАПервый и второй сумматоры 4 и 9 элементарных произведений - п-раз- рядные, предназначены для формирования старших п разрядов частичных произведений Y, X и Y,. X соответственно.

Первый и второй регистры П и 10 частичных произведений ,- n p-paзpяд- ные, предназначены для хранения частичных произведений YJ,д X и YfT-ГХ соответственно, п разрядов которых поступ :.от из соответствующего сумматора 4 и 9, а младшие р разрядов - из умножителя 3,.

Второй коммутатор 12 предназначен для передачи на вход второго слагаемого сумматора 13 частичных произведений операнда из регистра 10 частичных произведений или старших п разрядов регистра 15 младшей части результата.

Сумматор 5 частичных произведений - двухвходовый, пз-р-разрядньш, предназначен для вычисления значе- .

Сумматор 13 частичных произведе- 3 НИИ - двухвходовый, --- п-разрядный,

предназначен для вычисления значений Zp-r j и суммы Z Z f-f + .

Регистр 14 старшей части произве3

дения - --- п + р-разрядньй,сдвиговый, причем сдвиг осуществляется на р разрядов. Регистр 15 |- п+р-разрядный, сдвиговый, причем сдвиг осуществляется на р разрядов.

Блок 6 синхронизации обеспечивает формирование последовательностей управляющих сигналов (фиг.2),

Уст15ойство работает следующим образом.

3 исходном состоянии в регистре 1 находится множимое X, в старших разрядах регистра 2 - младшая часть множителя Yддд, в регист эе 7 - старшая .часть множителя YC,-, регистры 10, 11 14 и 15 обнулены (на фиг.1 цепи сброса и питания не показаны).

В каждом цикле по сигналу на выходах 19, 21 и 17 блока синхронизации происходят формирование К элементарных произведений , i 1,...,К, сдвиг содержимого регист157066

ра 2 в сторону младших разрядов на р разрядов, сложение сформированных на предыдущем (-1)-цикле элементарных произведений на сумматоре 4 и за-| пись результата на регистр 11,сложение сформированного в (j-l)-M цикле частичного произведения X, -Yj.7-.: - 1 с содержимым регистра 14 на суммато10 ре 13 (цри j-rl складываются нули), сдвиг содержимого регистра 15 в рону младших разрядов на р разрядов. Далее по сигналам на выходах 18, 19 и 16 блока синхронизации происходят

j формирование К элементарных произведений сдвиг содержимого регистра 7 в сторону младших разрядов на р разрядов, сложение сформированных ранее X;YpT j , i 1К на

20 сумматоре 9 и запись полученного XYpf на регистр 10, сложение содержимого регистра 11 с содержимым регистра 15 на сумматоре 5 и запись результата на регистр 15 (при j 1

25 складываются нули), сдвиг содержимого регистра 14 п сторону младших разрядов на р разрядов. 1

п к

После 2- циклов умножения по сигналу на выходе 21 блока синхронизации происходят сложение на сумматоре 13 содержимого регистра 10 с содержанием регистра 14 и запись сфо рмирован- ной старшей части произведения Z,. 3i на регистр 14. По тому же сигналу происходят сложение на сумматоре 4 сфор К

мированных в последнем (j --.-)

цикле элементарных произведений .j запись сформированного частичного произведения XYд на р е- гистр 11. Далее по сигналу на выходе 16 блока синхронизации происходит , сложение на сумматоре 5 содержимого 45 регистров 11 и 15 и сформированная младшая часть произведения Z, записывается на регистр 15. По сигналам на выходах 20 и 21 блока синхрони- . зации происходит сложение на сумма- 50 3

торе 5 п-разрядного кода п

старших разрядов Z д , полученные

. 3 значения --- п разрядов Z записыва-

55 ются на регистр 14, а - младших разрядов Z находятся в младших раз- разрядов Z находятся в младших разрядах регистра 15.

71615706

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

п т с п в 2Q и вх со пу

j Устройство для умножения, содержа- ;щее регистр множимого, регистры стар- 1шей и младшей частей множителя, К j умножителей (где К. р5:п, п - раз- Iрядность операндов, р - количество I одновременно обрабатываемых разрядов Iоперандов), регистры старшей и кпад- шей частей результата, первый и второй сумматоры частичных произведений |и блок синхронизации, причем вход Iпервого сомножителя каждого умножи- |теля соединен с выходом соответст- |вуюших р разрядов регистра множимо- |го, выходы первого и второго сумматоров частичных произведений соеди- |нены соответственно с информацидн- ными входами регистров старшей и |младшей частей результата, выходы Которых соединены соответственно с Iвходами первых слагаемых первого и

.

23

8

0

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

5

Абтомотное бремя Фиг.г