Устройство для умножения @ -разрядных чисел
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ П-РАЗРЯДНЫХ ЧИСЕЛ, содержащее регистры множимого и множителя, матрицу элементов И, группу элементов ШШ, накапливающий сумматор, группу элементов И и комбинационный сумматор, причем выходы разрядов регистра множимого, подключены к первым входам элементов И соответствующих столбцов матрицы, прямые выходы разрядов регистра множителя соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с вторыми входами элементов И соответствующих строк матрицы, выход первого элемента И первой строки матрицы соединен с входом первого разряда накапливающего сумматора, выход элемента И п-й строки матрицы соединен с входом
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИК ао 4 С 06 Р 7/52
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К ABTOPCHOMY СВИДЕТЕЛЬСТБУ (21) 3499219/24-24 (22) 14.10.82 (46) 23.11.85. Вюл.¹ 43 (71) Минский радиотехнический институт (72) I.Ã-.Лопато и А.А.Шостак (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 482740, кл. Ci 06 F 7/52, 1973;
Авторское свидетельство СССР
¹ 623204, кл. 6 06 F 7/52, 1977.
Авторское свидетельство СССР № 985783, кл. G 06 F 7/52, 1981. (54) (57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ
h-РАЗРЯДНЫХ ЧИСЕЛ, содержащее регистры множимого и множителя, матрицу элементов И, группу элементов ИЛИ, накапливающий сумматор, группу элементов И и комбинационный сумматор, причем выходы разрядов регистра множимого подключены к первым входам элементов И соответствующих столбцов матрицы, прямые выходы разрядов регистра множителя соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с вторыми входами элементов И соответствующих строк матрицы, выход первого элемента И первой строки матрицы соединен с входом первого разряда накапливающего сумматора, выход n-ro элемента И П-й строки матрицы соединен с входом (2 -1).-го разряда накапливающего сумматора, „SU „1193667 A выходы элементов И )-й диагонали матрицы (q, = 2,..., 2 п-2 ) соединены с входами(< -.1}-го элемента ИЛИ группы, выход р-го элемента ИЛИ группы (p=I,..., 2n-3 ) соединен с входом (р+1 )-го разряда накапливающего сумматора, второй вход каждого элемента И группы соединен с выходом соответствующего разряда комбинационного сумматора, вход переноса которого соединен с входом начала операции устройства, инверсные выходы разрядов регистра множителя подключены к первым входам соответствующих разрядов комбинационного сумматора, O о т л н ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит группу элементов задержки и элемент ИЛИ, а накаплива- C ющий сумматор выполнен в виде сумматора с запоминанием переносов, при этом выход t --го элемента И группы ((=1,...,n-1.) через соответствующий элемент задержки группы соединен с вторым входом(1+1 )-го разряда KoM бинационного сумматора, выход переноса которого подключен к первому входу элемента ИЛИ, выход h-го элемента И группы через соответствующий элемент задержки группы соединен с вторым входом элемента ИЛИ, выход которого подключен к входу управления приведением переносов на-. капливающего сумматора и выходу кон ца,операции устройства. и „и ьН рп
См см»
-- ср
Первая составляющая в приведенном выражении определяет среднее
SO число суммирований, выполняемых в устройстве на сумматоре 3, предполагая, что появление нулей и единиц в разрядных множителях равновероятно. Вторая составляющая характеризу55 ет задержку, которую вносит в общее время выполнения операции сумматор
4 (сигнал, который в начале выполнения операции поступает на вход 10
1 1
Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения асинхронного типа.
Цель изобретения — повышение быстродействия устройства.
На чертеже изображена структурная схема предлагаемого устройства для умножения Jn-разрядных чисел (для случая = 4 ).
Устройство содержит регистр 1 множимого, регистр 2 множителя, накапливающий сумматор 3 (выполненный в виде сумматора с запоминанием переносов ), комбинационный сумматор
4, группу элементов ИЛИ 5, матрицу элементов И 6, группу элементов И 7>> группу элементов 8 задержки, .элемент
ИЛИ 9, вход 10 начала операции, выход 11 конца операции.
Устройство работает следующим образом.
Пусть требуется умножить и-разрядное множимое Х Hà и-разрядный множитель К Y4YР27„= 1010. В исходном состояний в регистре 1 множимого хранится двоичный код числа
Х без знака, в регистре 2 множителя — двоичный код числа Y без знака, сумматор 3 обнулен.
Работа устройства начинается с момента подачи на вход 10 сигнала начала операции умножения (этот сигнал подается на вход 10 только один раз в начале операции, а появление сигнала на выходе 11 сигнализи рует об окончании операции умноже- . ния чисел1 После этого на выходе сумматора 4 формируется результат
С = С4СЗС С = 0101+0000+0001 = 0110 (первое слагаемое равно инверсному значению множителя У; второе слага-. емое поступает с выходов элементов
8 задержки, третье слагаемое есть значение входного переноса сумматора 4 ). Так как только С <-Y > = 1, то ца выходе элемента И 7 формируется управляюпдй сигнал, который производит передачу соответствующим образом сдвинутого множимого с выходов элементов И 6 второй строки матрицы через элементы ИЛИ 5 в сумматор 3.
Этот управляющий сигнал поступает на вход элемента 8 задержки и не меняет своего значения на протяжении всего времени суммирования первого частичного произведения в сумматоре
3. По истечении времени, равного вре193667 2 мени суммирования первого частичного произведения в сумматоре 3, на выходе элемента 8> задержки появляется сигнал, который, поступая на соответS ствующий вход сумматора 4, образует его второе слагаемое 0100. При этом на выходе сумматора 4 формируется результат С = С 1С С С„ = 01 01+0100+
+0000 = 1001, в результате чего на выходе элемента И 74 формируется. управляющий сигнал (так как только
С4 74 = 1), который производит передачу соответствующим образом сдвинутого множимого с выходов элементов И 6 четвертой строки матрицы через элементы ИЛИ 5 на входы сумматора 3. Этот управляющий сигнал поступает на вход элемента 8 задерж4 ки и не меняет своего значения на протяжении всего времени суммирования второго частичного произведения в сумматоре 3. По истечении этого времени на выходе элемента 84 задержки появляется сигнал, который через . элемент ИЛИ 9 поступает на вход управления приведением переносов сумматора 3, разрешая суммирование в нем запоминающих переносов с целью формирования результата в од30 норядном коде, а также подается на выход 11, сигнализируя об окончании выполнения в нем операции умножения двух чисел.
Среднее время умножения двух и-разрядных двоичных чисел в устрой-. стве примерно равно
40 ън где t „— время суммирования и-разрядных чисел в сумматоре
3 с запоминанием переносов;
1 — время, необходимое на суммирование -разрядных чисел в сумматоре 4 с распространением переносов.
1193667
Составитель В.Березкин
Редактор С.Саенко Техред Ж.Кастелевич Корректор Г.Решетник
Тираж 709 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д.4/5
Заказ ?316/52
Филиал ППП "Патент", r.ужгород, ул.Проектная,4 и который в дальнейшем осуществляет передачу соответствующим образом сдвинутых множимых в сумматор 3, в процессе умножения фактически должен
I один раз пройти через весь сумматор 4 ).
