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

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

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

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

представляются в виде А 2)

числа

i 1

ai6{0,1}, где А at 32 ... а - двоичный п-раз- рядный код числа А. Выполнение операции умножения в устройстве основано на таблично-алгоритмическом методе умножения, Процесс умножения конвейеризирован за счет совмещения во времени получения элементарных произведений и накопления суммы частичных произведений.

Пусть X J х| 21 и Y - $ -

1

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

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

п/р

п/р

п/рп/р

2 2 (Yj J x,(2p)- X2p)-J

где xi xtxi+i ... xi+p-1 - i-я двоично-кодированная цифра кода множимого в канонической позиционной системе счисления с основанием q 2Р;

Yj yjyn-p-i - j-я двоично-кодированная цифра кода множителя.

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

п/р

частичное произведение Yj V выJ i

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

ющих операцию умножения р-разрядного двоичного кода YJ на р-разрядный код Xi с образованием произведения разрядности 2р и собирается в п + р двоично-разрядный код частичного произведения X. YJ на сумма- торе.

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

0

д

5

0

числении Z, когда в один и тот же момент времени на одном сумматоре формируется частичное произведение X.Y|fi, а на другом сумматоре формируется сумма частичных произведений Zj Zj-i2 p + 2Yj, где Zo О, Z ZK.

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

При округлении используется симметричность величин, меньших 2 - п, относительно величины . Единичный сигнал округления вырабатывается, если отбрасываемая часть результата AZ удовлетворяет условию AZ , и не вырабатыва5

0

5

0

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

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

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

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

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

Блоки 3i...3 умножения имеют формат РхР 2р и предназначены для вычисления очередного элементарного произведения XiYj (I, j 1...к). В качестве умножителей могут быть применены однотактные матричные или ПЗУ с прошитой таблицей умножения в 2-р-ичной системе счисления.

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

Блок 8 микропрограммного управления формирует временную диаграмму, приведенную на фиг. 2, и может быть реализован в виде совокупности счетчика микрокоманд и элемента памяти микрокоманд, в котором

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

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

Счетный триггер 17 предназначен для формирования единичного сигнала округления через раз, если отбрасываемая часть результата равна величине AZ , причем смена состояния триггера 17 происходит по заднему фронту единичного сигнала на его входе.

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

В исходном состоянии регистры 1, 2, б и 7 обнулены (на фиг 1 цепи сброса и питания не показаны). По сигналу блока 8 микропрограммного управления (на выходе 20) множимое X и множитель Y принимаются на регистр 1 множимого и регистр 2 множителя соответственно, а RS-триггер сбрасывается в О.

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

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

В первом (j + 1) цикле по сигналу на выходе 21 блока 8 микропрограммного управления на множителях 3i...3K происходит формирование к элементарных произведений XiYj-1, f 1,2к, а по сигналу на выходе

19 блока 8 они собираются на сумматоре 4 и частичное произведение записывается на регистр 6, одновременно происходит сдвиг множителя на р разрядов в регистре

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

регистр 6 с одновременным сдвигом на р разрядов содержимого регистра 2.

В каждом цикле умножения, начиная с второго, по сигналам на выходе 22 блока 8

производится анализ младших р разрядов полученной на регистре 7 суммы частичных произведений на наличие хотя бы одной единицы,

Результат анализа запоминается RS0 триггером. Это позволяет избежать аппаратурных затрат на хранение всей отбрасываемой части результата умножения.

После завершения сложения на сумма5 торе 5 в последнем цикле 0 к) на регистре 7 оказывается п + р старших разрядов кода произведения

Затем по сигналу на выходе 23 блока 8 производится анал из содержимого млад0 ших разрядов регистра 7 и вырабатывается сигнал округления, который по сигналу на выходе 19 блока 8 через третий элемент ИЛИ 9 принимается в регистр 6. Затем по сигналу на выходе 21 блока 8 на сумматоре

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

Рассмотрим процесс округления более подробно.

Пусть п 8 и р 2 Пусть в результате выполнения последовательности операций

5 умножения получилась следующая последовательность двоичных кодов Zi. Пусть после первого умножения получается код Zi 0,0110 1100, 1100 0010. Тогда в процессе умножения выходной сигнал RS-триггера 13

0 принимает единичное значение, так как в семи младших разрядах срабатываемой части была хотя бы одна единица, а в регистре 7 по окончании умножения окажется (п + р 10)-разрядный код Zi 0,0010 1100, 11.

5 По сигналу на выходе 23 блока 8 на выходе первого элемента И 10 появляется единичный сигнал, так как на его вход поступает единичный сигнал на п + 1 9 разряда регистра 7, а затем на выходе четвертого

0 элемента И 15 появляется единичный сигнал, так как на его входы поступают единичные сигналы с выходов RS-триггера 13 и первого элемента И 10, а на выходе элемента И 18 единичный сигнал отсутствует, так

5 как на его вход (независимо от состояния триггера 17) с выхода элемента И 16 поступает не единичный сигнал, потому что на его инверсном входе не нулевой сигнал. По единичному сигналу с элемента И 15 на выходе элемента ИЛИ 14 формируется единичный

сигнал округления, поступающий через элемент ИЛИ 9 на регистр б, в который он принимается по сигналу на выходе 19 блока 8. По сигналу на выходе 21 блока 8 происходит коррекция результата на сумматоре 5 и в регистре 7 получают совокупность сигналов, представляющих в младших разрядах код округленного результата: Zi° 0,0110 1101. Ошибка округления равна Az1 +0,000000000011 1110.

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

22 0,0010 1010:00100010.

В процессе умножения выходной сигнал RS-триггера 13 принимает единичное Значение, а в регистре 7 по окончании умножения оказывается (п + р 10)-разрядный код Z21 0,0010 1010, 00. Для этого кода сигнал округления не формируется, так как на единичные входы элементов И 15 и 18 из п + 1 9 разряда регистра 7 поступает нулевой сигнал. Результат округления равен 22° 0,0010 1010, а ошибка округления AZ2 - -0,0000 0000 0010 0010.

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

23 0,1010 0111, 10000000,

По окончании умножения выходной сигнал RS-триггера 13 остается нулевым, а в регистре 7оказывается код2з1 0,10100111 10. Для этого кода по сигналу на выходе 23 блока 8 на выходе элемента И 10 появляется единичный сигнал, так как на его вход поступает единичный сигнал из п + 1 9 разряда регистра 7. Затем на выходе элемента И 18 появляется единичный сигнал, так как на его второй вход с триггера 17 поступает единичный сигнал (делаем допущение, что в исходном состоянии триггер 17 находится в единичном состоянии), и на первый вход также поступает единичный сигнал с выхода элемента И 16, который возникает потому, что на его инверсный вход поступает нулевой сигнал с триггера 13 и на прямой вход поступает единичный сигнал с элемента И 10. На выходе элемента И 15 единичный сигнал отсутствует, так как на его второй вход поступает нулевой сигнал с триггера 13. Таким образом, по единичному сигналу с выхода элемента И 18 на выходе элемента ИЛИ 14 формируется единичный сигнал округления, поступающий через элемент ИЛИ 9 в регистр 6. Результат округления равен 7з° 0,1010 1000, а ошибка округления Д2з +0 ,0000 0000 10000000. По заданному фронту единичного сигнала с выхода элемента И 16, поступающему на счетный вход триггера 17, последний приводится в нулевое состояние.

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

24 0,00100011 10000000.

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

241 0,0010 0011 10.

Для этого кода сигнал округления не формируется, так как на второй вход эле- мента И 15 с выхода RS-триггера 13 поступает нулевой сигнал, и на второй вход элемента И 18 с триггера 17 поступает нулевой сигнал, так как триггер 17 в предыдущем такте округления переведен в нулевое со- стояние. Результат округления равен ° 0,0010 0011, а ошибка округления AZ4 -0,0000 0000 1000 0000, По заднему фронту единичного сигнала с выхода элемента И 16, поступающему на счетный вход триггера 17, последний переводится в единичное состояние.

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

25 0,0001 1001 10000000 0,0001 1001 10;

26 0,1000 0000 0010 0100 0,1000 0000 00;

27 0,0011 110010000000 0,0011 1100 10;

28 0,101t 1011 10100111 0,1011 1011 10;

25° 0,0001 1010; 2е° 0,1000 0000; 2г 0,0011 1100; 28° 0,1011 1100; A 2g +0,0000 0000 1000 0000; А 2е -0,0000 0000 0010 0100; А27 -0,0000 0000 1000 0000; А2в +0,0000 0000 0101 1001.

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

i 1

A2i

составит

величину

Am 0,0000 0000 0101 0001. При работе прототипа при выполнении этой последовательности операций умножения при использовании n-разрядного результата суммарная абсолютная ошибка составит величину

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

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

элементарных произведений, регистр частичных произведений, сумматор частичных произведений, регистр произведения и блок микропрограммного управления, причем первый вход каждого блока умножения соединен с выходом соответствующих р разрядов регистра множимого, а второй вход - с выходом младших р разрядов регистра множителя, выход старших р разрядов i-ro блока умножения (1 1,..., к) соединен с первым входом соответствующих р разрядов сумматора элементарных произведений, выход младших р разрядов j-ro блока

умножения (I 2к) соединен с вторым

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

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

первого элемента ИЛИ (t п + 2п + р),

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

Изобретение относится к цифровой вычислительной технике и может найти применение в высокопроизводительных машинах 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