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

 

Изобретение относится к цифровой вычислительной технике и может найти применение в высокопроизводительных машинах I / h С t i.. .1 г 1- и системах. Целью изобретения является повышение точности при получении п-разрядного результата за счет устранения систематического смещения в общей ошибке вычислений. Новым в устройстве, содержащем резисторы 1 и 2 множимого и множителя , К блоков 3 умножения, сумматоры 4 и 5 элементарных и частичных произведений, регистр 6 частичных произведений, регистр 7 результата и блок 8 микропрограммного управления, является введение трех элементов ИЛИ 9, 12, 14, пяти элементов И 10, 11,15.16,18м двух триггеров 13,17. Устройство работает по принципу конвейера. 2 ил. Г9 СП с х| ел со 4. XI фиг1

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

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

РЕСПУБЛИК

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

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

ПРИ ГКНТ СССР . Г".*

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ;" „ " -I)<::-:::-. .

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

2 (21) 4829140/24 (22) 29.05.90 (46) 07.08.92. Бал, hL 29 (72) А.И.Бобровский и В.Н.Марчук (56) Карцев М.А,, Брик В.А. Вычислительные системы и синхронная арифметика. — М.:

Радио и связь, 1981, с. 180-182, Авторское свидетельство СССР

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

1753471 А1

) (sl)s G 06 F 7/52 и системах, Целью изобретения является повышение точности при получении и-разрядного результата за счет устранения сис-. тематического смещения в общей ошибке вычислений. Новым в устройстве, содержащем резисторы 1 и 2 множимого и множите-ля, К блоков 3 умножения, сумматоры 4 и 5 элементарных и частичных произведений, регистр 6 частичных произведений, регистр

7 результата и блок 8 микропрограммного управления, является введение трех элементов ИЛИ 9, 12, 14, пяти элементов И 10, 11, 15, 16, 18 и двух триггеров 13, 17, Устройство работает по принципу конвейера. 2 ил.

1753471

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

Целью изобретения является повышеwe точности при получении п-разрядного результата за счет устранения систематического смещения в общей ошибке вычислений.

В устройстве операнды положительные числа представляются в виде А = а(2 (l =1 а(6{0,1}, где А = а1 аз ... а — двоичный и-разрядный код числа А. Выполнение операции умножения в устройстве основано на таблично-алгоритмическом методе умножения.

Процесс умножения конвейериэирован за счет совмещения во времени получения элементарных произведений и накопления суммы частичных произведений. и

-1 " -1

ПустьХ= g x(2 и Y- ), у!2

i =1 (=1 множимое и мйожитель соответственно, где хь y> — значение l-x разрядов кодов сомножителей. Тогда для представления точного результата Z = X . Y требуется 2п-разрядный двоичный код.

Процесс вычисления произведения 2 запишется в виде

n/ . n/

Z = g (Y g xi (2Р) )(1Р)

) =1 1=1 где х(= x(xl+) ... х(+р-1 — i-ÿ двоично-кодированная цифра кода множимого в канонической позиционной системе счисления с основанием q = 2;

У(- у(у +()-1 — j-я двоично-кодированная цифра кода множителя.

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

n/ó частичное произведение Yj =, Х(2 Р вы-!

=1 числяется на — = к умножителях, выполняр ющих операцию умножения р-разрядного двоичного кода У(на р-разрядный код Х(с образованием произведения разрядности

2р и собирается в n + р двоично-разрядный код частичного произведения Х.У(на сумматоре.

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

55 числении Z, когда в один и тот же момент времени на одном сумматоре формируется частичное произведение X.У))1, а на другом сумматоре формируется сумма частичных произведений Z) =2 -12 Р+ 2У, где Zo =О, Z=Z».

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

Младших р-разрядов суммы для выполнения по окончании умножения округления результатов до fl разрядов.

При округлении используется симметричность величин, меньших 2 — и, относительно величины 2 ", Единичный сигнал округления вырабатывается, если отбрасываемая часть результата ЛZ удовлетворяет условию 2 " " < A Z < 2 ", и не вырабатывается, если — 2 " < h Z < 2 " . Это дает при округлении разные знаки ошибок, которые могут скомпенсироваться. Так как величина

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

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

Устройство содержит регистры 1 и 2 соJ ответственно множимого и множителя, к блоков 31...3» умножения, сумматор 4 элементарных произведений, 4 сумматор частичных произведений, регистр 6 частичных произведений, регистр 7 результа, блок 8 микропрограммного управления, третий элемент ИЛИ 9, первый 10 и второй 11 элементы И, первый элемент ИЛИ 12, RS-триггер 13, второй элемент ИЛИ 14, четвертый

15 и третий 16 элементы И, счетный триггер

17 и пятый элемент И 18.

Регистр 1 множимого — п-разрядный, предназначен для хранения множимого Х.

Регистр 2 множителя — сдвиговый, иразрядный, причем сдвиг осуществляется в сторону младших разрядов на р разрядов, предназначен для хранения множителя У, Блоки 31...3» умножения имеют формат

РхР 2р и предназначены для вычисления очередного элементарного произведения

XiYj (i, j = 1...к), В качестве умножителей могут быть применены однотактные матричные или ПЗУ с прошитой таблицей умножения в 2-р-ичной системе счисления.

Сумматор 4 элементарных произведений — двувходовый, п-разрядный, предназначен для формирования старших и разрядов частичных произведений У(.X, (n+

+р)-разрядный регистр 6 частичных произ1753471 ведений предназначен для хранения частичного произведения Yj X.

Блок 8 микропрограммного управления формирует временную диаграмму, приведенную на фиг, 2, и может быть реализован 5 в виде совокупности счетчика микрокоманд и элемента памяти микрокоманд, в котором записано (— + 5) микрокоманд в соответсти р ьии с временной диаграммой. Тактовая час- 10 тота выбрана по максимальной задержке одного из функциональных элементов устройства (для данной схемы сумматора 5 частичных произведений).

RS-триггер 13 предназначен для запо-. 15 минания результата анализа отбрасываемой,части результата умножения (кроме старшего разряда) на наличие в ней хотя бы одной единицы.

Счетный триггер 17 предназначен для 20 формирования единичного сигнала округления через раз, если отбрасываемая часть результата равна величине h,Z = 2 " ", причем смена состояния триггера 17 происходит по заднему фронту единичного сигнала 25 на его входе.

Устройство работает следующим образом, В исходном состоянии регистры 1, 2, 6 и 7 обнулены (на фиг. 1 цепи сброса и пита- 30 ния не показаны). По сигналу блока 8 микропрограммного управления (на выходе 20) множимое Х и множитель Y принимаются на регистр 1 множимого и регистр 2 множителя соответственно, а RS-триггер сбрасывается 35 в "0".

В каждом цикле умножения Х на очередные р разрядов Y на управляющие входы поступают сигналы так,.как это показано на

n40 фиг, 2. Число циклов умножения равно К= —. р

В первом (j + 1) цикле по сигналу на выходе 21 блока 8 микропрограммного.управления на множителях 31...3К происходит формирование к элементарных произведе- 45 ний Х У1-1, l 1, 2...„к, а по сигналу на выходе

19 блока 8 они "собираются" на сумматоре

4 и частичное произведение записывается на регистр 6, одновременно происходит сдвиг множителя на р разрядов в регистре 50

2, В последующих циклах происходит умножение Х на очередные р разрядов Y c одновремейным сложением частичного произведения с содержанием регистра 7; 55 сдвинутыми на р разрядов в сторону младших разрядов с помощью косой передачи на сумматоре 5 по сигналу на выходе 21 блока8, а затем сборка очередного частичного произведения на сумматоре 4 и.прием его в регистр 6 с одновременным сдвигом на р разрядов содержимого регистра 2.

В каждом цикле умножения, начиная с второго, по сигналам на выходе 22 блока 8 производится анализ младших р разрядов полученной на регистре 7 суммы частичных произведений на наличие хотя бы одной единицы, Результат анализа запоминается RSтриггером, Это позволяет избежать аппаратурных затрат - на хранение всей отбрасываемой части результата умножения.

После завершения сложения на сумматоре 5 в последнем цикле (j = к) на регистре

7 оказывается и + р старших разрядов кода, произведения.

Затем по сигналу на выходе 23 блока 8 производйтся "анализ содержимого младших разрядов регистра 7 и вырабатывается сигнал округления; который по cuirналу на выходе 19 блока 8 через третий элемент

ИЛИ 9 принимается в регистр 6, Затем по сигналу на выходе 21 блока 8 на сумматоре

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

Пусть и = 8 и р = 2, Пусть в результате выполнения последовательности операций умножения получилась следующая последовательность двоичных кодов Ъ. Пусть после первого умножения получается код Z< =

0,0110 1100, 1100 0010. Тогда в процессе умножения выходной сигнал RS-триггера 13 принимает единичное значение, так как в семи младших разрядах срабатываемой части была хотя бы одна единица, а в регистре

7 по окончании умножения окажется (п+ р =

10)-разрядный код Z> = 0,0010 1100, 11.

По сигналу на выходе 23 блока S на выходе первого элемента И 10 появляется единичный сигнал, так как на его"вход посту- . пает единичный сигнал íà n + 1 - 9 разряда регистра 7, а затем на выходе четвертого элемента И 15 появляется единичный сигнал, так как на его входы поступают единичные сйгналы с выходов RS-триггера 13 и первого элемента И 10, а на выходе элемента И 18 единичный сигйал отсутствует, так как на его вход (независимо от состояния триггера 17) с выхода элемента И 16 поступает не единичный сигнал, потому что на его инверсном входе не нулевой сигнал. По единичному сигналу с элемента И 15 на выходе элемента ИЛИ 14 формируется единичный

1753471 сигнал округления, поступающий через элемент ИЛИ 9 на регистр 6, в который он принимается по сигналу на выходе 19 блока

8, По сигналу на выходе 21 блока 8 происходит коррекция результата на сумматоре 5 и в регистре 7 получают совокупность сигналов; представляющих в младших разрядах код округленного результата: Z> = 0,0110 о.

1101. Ошибка округления равна Лу1

=+0,000000000011 1110.

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

22 = 0,0010 1010,0010 0010, В прбцеСсе умножения выходной сигнал RS-триггера 13 принимает единичное

Значение, а в регистре 7 по окончании умножения оказывается (n + р = 10)-разрядный код Zz = 0,0010 1010, 00, Для этого кода сигнал округления не формируется, так как на единичные входы элементов И 15 и 18 из и+ 1 = 9 разряда регистра 7 поступает нулевой сигнал. Результат округления равен

22 = 0,0010 1010, а. ошибка округления

ЛZz = -G,OOOO 0000 0010 0010, Пусть после третьего умножения получается код

Z3 = 0,1010 0111, 1000 0000, По окончанйй умножения выходной сигнал RS-триггера 13 остается нулевым, à в регистре 7 оказывается код 2з = 0,1010 0111

10. Для этого кода по сигналу на выходе 23 блока 8 на выходе элемента И 10 появляется единичный сигнал, так как на его вход поступает единичный сигнал из n + 1 = 9 разряда регистра 7. Затем на выходе элемента И 18 появляется единичный сигнал, так как на его второй вход с триггера 17 поступает единичный сигнал (делаем допущение, что в исходном состоянии триггер 17 находится в единйчном состоянии), и на первый вход также пост пает единичный сигнал с выхода элемента И 16, который возникает потому, что на его инверсный вход поступает нулевой сигнал с триггера 13 и на прямой вход поступает едйничный сигнал с элемента И

10, На выходе элемента И 15 единичный сигнал отсутствует, так как íà его второй вход поступает нулевой сигнал с триггера

13. Таким образом, по единичному сигналу с выхода элемента И 18 на выходе элемента

MJlM 14 формируется единичный сигнал округления; поступающий через элемент ИЛИ

9 в регистр 6. Результат округления равен

Ь = 0,1010 1000, а ошибка округления Л2з

= +G,GGG0 ОООО 10000000. По заданному фронту единичного сигнала с выхода элемента И 16, поступающему на счетный вход триггера 17, последний приводится в нулевое состояние, 40

Пусть после четвертого умножения пол- учается код

Z4 = 0,0010 001 1 1000 0000, По окончании операции умножения вы5 ходной сигнал RS-триггера 13 остается нулевым а в регистре оказывается код

24 = 0,0010 0011 10.

Для этого кода сигнал округления не формируется, так как на .второй вход эле10 мента И 15 с выхода RS-триггера 13 поступает нулевой сигнал, и на второй вход элемента И 18 с триггера 17 поступает нулевой сигнал, так как триггер 17 в предыдущем такте округления переведен в нулевое со15 стояние. Результат округления равен Z4

=0,0010 0011, а ошибка округления 624 =

=-0,0000 0000 1000 0000, По заднему фронту единичного сигнала с выхода элемента И 16, поступающему на счетный вход триггера 17, 20 последний переводится в единичное состояние.

Рассуждая аналогично, запишем результаты округления и значения ошибок для . последовательности:

25 Zs = 0,0001 1001 1000 0000 = 0,0001 1001

10;

Ее = 0,1000 0000 0010 0100 = 0,1000 0000

00;

Z7 = 0,0011 1 100 1000 0000 = 0,0011 1100

30 10;

2э = 0,1011 1011 1010 0111 = 0,1011 1011

10;

Zs0 = 0,0001 1010;

Ze = 0,1000 0000;

35 Zq = 0,0011 1100;

2э = 0,1011 1100;

Л Zs = +0,0000 0000 1000 0000;

Л Z6 = -0,0000 0000 0010 0100;

Л27 = -0,0000 0000 1000 0000;

ЛZB = +0,0000 0000 0101 1001.

Суммарная абсолютная ошибка приведенного примера Л m = Л Zt составит

i =1 величину

Ьп = 0,0000 0000 0101 б001.

При работе прототипа при выполнении этой последовательности операций умножения при использовании и-разрядного ре50 зультата суммарная абсолютная ошибка составит величину

Атц = 0,0000 001 1010 1111,. т.е, суммарная абсолютная ошибка в этом случае значительно больше, Формула изобретения

Устройство для умножения, содержащее регистры множимого и множителя, к блоков умножения (где к такое, что кр у р, п — разрядность операндов, кр - входная. разрядность блоков умножения), сумматор

1753471

&MXt.tlat t.t олокр

gnpabnettt.t s.1П

48mL oQmttgt:- драя элементарных произведений, регистр частичных произведений, сумматор частичных произведений, регистр произведения и блок микропрограммного управления, причем первый вход каждого блока умножения 5 соединен с выходом соответствующих р разрядов регистра множимого, а второй вход — с выходом младших р разрядов регистра множителя, выход старших р разрядов

i-го блока умножения (I = 1, ..., к) соединен с 10 первым входом соответствующих р разрядов сумматора элементарных произведений, выход младших р разрядов j-ro блока умножения (I = 2, ..., к) соединен с вторым входом (pj - р)-го разряда сумматора элемен- 15 тарных произведений, выход которого соединен с информационным входом и старших разрядов регистра частичных про- . изведений, (информационный вход млад-ших р разрядов которого соединен с 20 выходом р младших разрядов первого блока умножения; а выход — с первым входом сумматора частичных произведений, втОрой вход которого соединен с выходом регистра произведения, информационный вход кото- 25 рого Соединен с выходом сумматора частичных произведений, входы записи регистров множимого и множителя соединены с первым выходом блока микропрограммного управления, второй выход которого соединен 30 с входом сДвига регистра множителя, входом суммирования сумматора элементарных произведений и входом записи регистра частичных произведений, третий выход блока микропрограммного управле- 35 ния соединен с входами расширения выдачи к блоков умножения, входом суммирования сумматора частичных произведейий и входом записи регистра результата, о т л и ч а ю щ е е с я тем, что, с целью 40 повышени точности при получении и-разрядного результата за счет устранения систематического смещения в общей ошибке вычислений, в него введены три элемента

ИЛИ, пять элементов И, счетный триггер и

RS-триггер, причем выход (и + 1)-го разряда регистра произведения соединен с первыми входами первого и второго элементов И, вторые входы которых соединены соответственно с четвертым и пятым выходами блока микропрограммного управления, выходы

I-x разрядов регистра произведения соединены соответствующими (р - 1)-ми входами первого элемента ИЛИ ((= n + 2, ..., n + р), р -й вход которого соединен с выходом второго элемента И, выход йервого элемента И вЂ” с прямым входом третьего элемента И и первым входом четвертого элемента И, выход первого элемента ИЛИ вЂ” с S-входом

RS-триггера, R-вход которого соединен с первым выходом блока управления, выход

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