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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК Р 7/52 ТЕН ВИДЕТЕЛ ЬСТВ АВТОРСКО льнце - М3 ф(Л 4 ъ 4 ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКНТ СССР ИСАНИЕ ИЗ 21) 4829140/2422) 29,05.90(72) А.И.Бобровский и В.НсМарчук (56) Карцев М.А Брик В,А. Вычислите системы и синхронная арифметика. Радио и связь, 1981, с. 180-182,Авторское свидетельство СССР М 754412, кл, 6 06 Р 7/52, 1978. 54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ 57) Изобретение относится к цифровой вычислительной технике и может найти поименение в высокопроизвовительных машинах 53 1753471 А и системах, Целью изобретения является повышение точности при получении и-разрядного результата засчет устранения систематического смещения в общей ошибке вычислений. Новым в устройстве, содержащем резисторы 1 и 2 множимого и множителя, К блоков 3 умножения, сумматоры 4 и 5 элементарных и частичных произведений, регистр 6 частичных произведений, регистр 7 результата и блок 8 микропрограммного управления, является введение трех элементов ИЛИ 9, 12, 14, пяти элементов И 10, 11, 15, 16, 18 и двух триггеров 13, 17, Устройство работает по принципу конвейера. 2 ил,Изобретение относится к цифровой вычислительной технике, предназначено для умножения чисел, представленных в двоичной системе счисления, и может найти применение в качестве операционного блока в высокопроизводительных вычислительных машинах и системах.Целью изобретения является повышение точности при получении а-разрядного результата за счет устранения систематического смещения в общей ошибке вычислений.В устройстве операнды положительные числа представляются в виде А = а 12а 1 б(0,1), где А = а 1 а 2а - двоичный и-разрядный код числа А, Выполнение операции умножения в устройстве основано на таблично-алгоритмическом методе умножения, Процесс умножения конвейериэирован за счет совмещения во времени получения элементарных произведений и накопления суммы частичных произведений.иПусть Х =х 2 и У,Г у 21=1множимхое и мйожитель соответственно, где хь у 1 - значение 1-х разрядов кодов сомножителей. Тогда для представления точного результата 2 = Х. У требуется 2 п-разрядный двоичный код.Процесс вычисления произведения Е запишется в виде в/ . л/2 = 2 (У 2, х 1 (2 х 1 х 2 х)=1 1=1где х 1 = х 1 х+1х+р- 1-я двоично-кодированная цифра кода множимого в канонической позиционной системе счисления с основанием р = 2 Р;У 1 у 1 у 1+р- )-я двоично-кодированная цифра кода множителя.Таким образом, процесс умножения состоит из однотипных повторяющихся циклов, Во время очередного )-го цикла 1-еи/участичное произведение У =, Х 12 р вычисляется на - = к умножителях, выполнярющих операцию умножения р-разрядного двоичного кода У на р-разрядный код Х с образованием произведения разрядности 2 р и собирается в и + р двоично-разрядный код частичного произведения Х.У 1 на сумматоре.Наличие регистра частичных произведений при соответствующем управлении позволяет организовать конвейер при вы 10 15 20 25 30 35 40 45 50 55 числении 2, когда в один и тот же момент времени на одном сумматоре формируется частичное произведение Х,У+1, а на другом сумматоре формируется сумма частичных произведений 2 =21-12 р+2 У, где Хо =О, 2=7.После получения каждой суммы частичных произведений производится анализ Младших р-разрядов суммы для выполнения по окончании умножения округления результатов до и разрядов.При округлении используется симметричность величин, меньших 2 - и, относительно величины 2", Единичный сигнал округления вырабатывается, если отбрасываемая часть результата ЛЕ удовлетворяет условию 2 " "Л 22 ", и не вырабатывается, если - 2 "ЬЕ2 " , Это дает при округлении разные знаки ошибок, которые могут скомпенсироваться. Так как величина 2 " в этом случае симметрична самой себе, то единичный сигнал округления вырабатывается через раз, что позволит менять знаки ошибок, которые будут компенсировать друг друга.На фиг. 1 приведена функциональная схема устройства для умножения; на фиг, 2 - относительная временная диаграмма сигналов на выходах блока управления при работе устройства,Устройство содержит регистры 1 и 2 сохответственно множимого и множителя, к блоков 313 умножения, сумматор 4 элементарных произведений, 4 сумматор частичных произведений, регистр 6 частичных произведений, регистр 7 результа, блок 8 микропрограммного управления, третий элемент ИЛИ 9, первый 10 и второй 11 элементы И, первый элемент ИЛИ 12, ЯЯ-триггер 13, второй элемент ИЛИ 14, четвертый 15 и третий 16 элементы И, счетный триггер 17 и пятый элемент И 18.Регистр 1 множимого - п-разрядный, предназначен для хранения множимого Х.Регистр 2 множителя - сдвиговый, и- разрядный, причем сдвиг осуществляется в сторону младших разрядов на р разрядов, предназначен для хранения множителя У,Блоки 313 умножения имеют формат РхР 2 р и предназначены для вычисления очередного элементарного произведения ХУ (1, ) = 1 к), В качестве умножителей могут быть применены однотактнце матричные или ПЗУ с прошитой таблицей умножения в 2-р-ичной системе счисления.Сумматор 4 элементарных произведений - двувходовый, п-разрядный, предназначен для формирования старших и разрядов частичных произведений У 1.Х, (и+ +р)-разрядный регистр 6 частичных произведений предназначен для хранения частичного произведения У Х.Блок 8 микропрограммного управленияформирует временную диаграмму, приведенную на фиг, 2, и может быть реализован 5в виде совокупности счетчика микрокоманди элемента памяти микрокоманд, в которомзаписано ( - + 5) микрокоманд в соответстирьии с временной диаграммой. Тактовая частота выбрана по максимальной задержкеодного из функциональных элементов устройства (для данной схемы сумматора 5 частичных произведений).ВЯ-триггер 13 предназначен для запоминания результата анализа отбрасываемой,части результата умножения (кроместаршего разряда) на наличие в ней хотя быодной единицы.Счетный триггер 17 предназначен для 20формирования единичного сигнала округления через раз, если отбрасываемая частьрезультата равна величине Л Е = 2 " 1, причем смена состояния триггера 17 происходит по заднему фронту единичного сигнала 25на его входе.Устройство работает следующим образом,В исходном состоянии регистры 1, 2, 6и 7 обнулены (на фиг. 1 цепи сброса и питания не показаны). По сигналу блока 8 микропрограммного управления (на выходе 20)множимое Х и множитель У принимаются нарегистр 1 множимого и регистр 2 множителясоответственно, э РЗ-триггер сбрасывается 35в "0".В каждом цикле умножения Х на очередные р разрядов У на управляющие входыпоступают сигналы так,.как это показано наи 40фиг, 2. Число циклов умножения равно К= - .рВ первом 0 + 1) цикле по сигналу навыходе 21 блока 8 микропрограммного.управления на множителях 313 к происходитформирование к элементарных произведений ХУ, 1 1, 2 к, а по сигналу на выходе19 блока 8 они "собираются" на сумматоре4 и частичное произведение записываетсяна регистр 6, одновременно происходитсдвиг множителя на р разрядов в регистре 502,В последующих циклах происходит умножение Х на очередные р разрядов У содновремейным сложением частичногопроизведения с содержанием регистра 7; 55сдвинутыми на р разрядов в сторону младших разрядов с помощью косой передачи насумматоре 5 по сигналу на выходе 21 блока 8, а затем сборка очередного частичногопроизведения на сумматоре 4 и.прием его в регистр 6 с одновременным сдвигом на рразрядов содержимого регистра 2.В каждом цикле умножения, начиная свторого, по сигналам навыходе 22 блока 8производится анализ младших р разрядовполученной на регистре 7 суммы частичныхпроизведений на наличие хотя бы однойединицы,Результат анализа запоминается ЙЯтриггером, Это позволяет избежать аппэратурных затрат - на хранение всейотбрасываемойчасти результата умножения,После завершения сложения на сумматоре 5 в последнем цикле 0 = к) на регистре7 оказывается и + р старших разрядов кода,произведения."Затем по сигналу на выходе 23 блока 8производйтся "анализ содержимого младших разоядов регистра 7 и вырабатываетсясигнал округления; который посигналу навыходе 19 блока 8 через третий элементИЛИ 9 принимается в регистр 6, Затем посигналу на выходе 21 блока 8 на сумматоре5 производится сложение содержимого регистра 6 с содержимым регистра 7, сдвинутым с помощью косой передачи. Врезультате округлений и-разрядный результат оказывается в и младших разрядов регистра 7,Рассмотрим процесс округления болееподробно,Пусть п = 8 и р = 2, Пусть в результатевыполнения последовательности Операцийумножения получилась следующая последовательность двоичных кодов Ъ. Пусть послепервого умножения получается код У 1 = 0,0110 1100, 1100 0010. Тогда в процессе умножения выходной сигнал ВЯ-триггера 13 принимает единичное значение, так как в семи младших разрядахсрабатываемой части была хотя бы одна единица, а в регистре7 по окончании умножения окажется (и+ р =10)-разрядный код Е 1 = 0,0010 1100, 11.По сигналу на выходе 23 блока 8 навыходе первого элемента И 10 появляетсяединичный сигнал, таккак на его"вход посту- .пает единичный сигнал на и+ 1 - 9 разрядарегистра 7, а затем на выходе четвертого элемента И 15 появляется единичный сигнал, так как на его входы поступаютединичные сйгналы с выходовЗ-триггера 13 и первого элемента И 10, а на выходе элемента И 18 единичный сигйал отсутствует, так как на его вход независимо от состояния триггера 17) с выхода элемента И 16 поступает не единичный сигнал, потому что на его инверсном входе не нулевой сигнал. По единичному сигналу с элемента И 15 на выходе элемента ИЛИ 14 формируется единичныйсигнал округления, поступающий через элемент ИЛИ 9 на регистр 6, в который он принимается по сигналу на выходе 19 блока 8, По сигналу на выходе 21 блока 8 происходит коррекция результата на сумматоре 5 и в регистре 7 получают совокупность сигналов; представляющих в младшихразрядах код округленного результата: 21 = 0,0110о.1101. Ошибка округления равна Лг 1 =+0,000000000011 1110.Пусть после второго умножителя получается код2 г = О,ОО 10 1010,0010 0010,В прбцеСсе умножения выходной сигнал ВЯ-триггера 13 принимает единичное Значение, а в регистре 7 по окончании умножения оказывается (и + р = 10)-разрядный код 2 г = 0,0010 1010, 00, Для этого кода сигналокругления не формируется, так как нэ единичные входы элементов И 15 и 18 из и+ 1 = 9 разряда регистра 7 поступает нулевой сигнал. Результат округления равен 2 г = 0,0010 1010, а. ошибка округления Д 2 г = -О,ОООО ОООО ОО 1 О ОО 10,Пусть после третьего умножения получается код2 з = 0,1010 0111, 1000 ОООО,По окончанйй умножения выходной сигнал ВЯ-триггера 13 остается нулевым, а в регистре 7 оказывается код 2 з = 0,1010 0111 10, Для этогокода по сигналу на выходе 23 блока 8 на выходе элемента И 10 появляется единичный сигнал, так как на его вход поступает единичный сигнал из и + 1 = 9 разряда регистра 7, Затем на выходе элемента И 18 появляется единичный сигнал, так как на его второй вход с триггера 17 поступает единичный сигнал (делаем допущение, что в исходном состоянии триггер 17 находится в единйчном состоянии), и на первый вход также пбступает единичный сигнал с выхода элемента И 16, который возникает потому, что на его инверсный вход поступает нулевой сигнал стриггера 13 и на прямой вход поступает едйничный сигнал с элемента И 10, На выходе элемента И 15 единичный сигнал отсутствует, так как на его второйвход поступает нулевой сигнал с триггера 13. Таким образом, по единичному сигналу с выхода элемента И 18 на выходе элемента ИЛИ 14 формируется единичный сигнал округления; поступающий через элемент ИЛИ 9 в регистр 6. Результат округления равен 2 з = 0,1010 1000, а ошибка округления Л 2 з = +О,ОООО ОООО 10000000. По заданному фронту единичного сигнала с выхода элемента И 16, поступающему на счетный вход триггера 17, последний приводится в нулевое состояние, 40 Пусть после четвертого умножения пол-учается код24 = 0,0010 0011 1000 0000По окончании операции умножения вы 5 ходной сигнал ВЯ-триггера 13 остается нулевым а в регистре оказывается код24 = О 0010 0011 10.Для этого кода сигнал округления неформируется, так как на второй вход эле 10 мента И 15 с выхода ВЯ-триггера 13 поступает нулевой сигнал, и на второй входэлемента И 18 с триггера 17 поступает нулевой сигнал, так как триггер 17 в предыдущемтакте округления переведен в нулевое со 15 стояние. Результат округления равен 24=-0,0000 0000 1000 0000, По заднему фронтуединичного сигнала с выхода элемента И 16,поступающему на счетный вход триггера 17,20 последний переводится в единичное состояние.Рассуждая аналогично, запишем результаты округления и значения ошибок для .последовательности;25 25 = 0,0001 1001 1000 0000 = 0,0001 100110;26 = 0,1000 0000 0010 0100 = 0,1000 0000ОО;27 = 0,0011 1100 1000 0000 = 0,0011 110030 10;2 э = 0,1011 1011 1010 0111 = 0,1011 101110;25,= о,ооо 1 101 о,26 = 0,1000 0000;35 2 = 0,0011 1100;2 э = 0,1011 1100;625 = +0,0000 ОООО 1000 0000;Л 26 = 0,0000 0000 0010 0100;Л 27 = -0,0000 0000 1000 0000;Л 2 в =+0,0000 0000 0101 1001,Суммарная абсолютная ошибка приведенного примера Ь пз = Ь Ъ составит=145 величинуЬп = 0,0000 ОООО 0101 б 001.При работе прототипа при выполненииэтой последовательности операций умножения при использовании и-разрядного ре 50 зультата суммарная абсолютная ошибкасоставит величинуАтц = 0,0000 001 1010 1111,.т.е, суммарная абсолютная ошибка в этомслучае значительно больше,Формула изобретенияУстройство для умножения, содержащее регистры множимого и множителя, кблоков умножения (где к такое, что кр у р,п - разрядность операндов, кр - входная.разрядность блоков умножения), сумматорэлементарных произведений, регистр частичных произведений, сумматор частичных произведений, регистр произведения и блок микропрограммного управления, причем первый вход каждого блока умножения 5 соединен с выходом соответствующих р разрядов регистра множимого, а второй вход - с выходом младших р разрядов регистра множителя, выход старших р разрядов -го блока умножения ( = 1, , к) соединен с 10 первым входом соответствующих р разрядов сумматора элементарных произведений, выход младших р разрядов )-го блока умножения (1 = 2, ., к) соединен с вторым входом (р - р)-го разряда сумматора элемен тарных произведений, выход которого соединен с информационным входом и старших разрядов регистра частичных про- . изведений,информационный вход млад-. ших р разрядов которого соединен с 20 выходом р младших разрядов первого блока умножения; а выход - с первым входом сумматора частичных произведений, втОрой вход которого соединен с выходом регистра произведения, информационный вход кото рого Соединен с выходом сумматора частичных произведений, входы записи регистров множимого и множителя соединены с первым выходом блока микропрограммного управления, второй выход которого соединен 30 с входом сдвига регистра множителя, входом суммирования сумматора элементарных произведений и входом записи регистра частичных произведений, третий выход блока микропрограммного управле ния соединен с входами расширения выдачи к блоков умножения, входом суммирования сумматора частичных произведейий и входом записи регистра результата,отличаю щееся тем,что, с целью 40Г Ьы 1 одь блокд упрабпе в. повышения точности при получении и-разрядного результата за счет устранения систематического смещения в общей ошибке вычислений, в него введены три элемента ИЛИ, пять элементов И, счетный триггер и ВЯ-триггер, причем выход (и + 1)-го разряда регистра произведения соединен с первыми входами первого и второго элементов И, вторые входы которых соединены соответственно с четвертым и пятым выходами блока микропрограммного управления, выходы 1-х разрядов регистра произведения соединены соответствующими (р - 1)-ми входами первого элемента ИЛИ (г,= и + 2, , и + р), р-й вход которого соединен с выходом второго элемента И, выход йервого элемента И - с прямым входом третьего элемента И и первым входом четвертого элемента И, выход первого элемента ИЛИ - с Я-входом ЯЯ-триггера, В-вход которого соединен с первым выходом блока управления, выход ЯЯ-триггера соединен с инверсным входом третьего элемента И и вторым входом четвертого элемента И, третий вход которого соединен с четвертым выходом блока микрбпрограммного управления и первым входом пятого элемента И, выход третьего элемента И - с входом счетного триггера ивторым входом пятого элемента И, третий вход которого соединен с выходом счетного триггера, выходы четвертого и пятогО элементов И соединены с входами второго элемента ИЛИ, выход которого соединен с первым входом третьего элемента ИЛИ, выход младшего разряда первого блока умножения соединен с вторым входом третьего элемента ИЛИ, выход которого соединен с входом младшего разряда регистра частичных произведений,