Устройство для умножения
Изобретение относится к цифровой вычислительной технике и предназначено для умножения и сдвига чисел, представленных в двоичной системе счисления, и может найти применение в высокопроизводительных вычислительных машинах и системах. Цель изобретения состоит в расширении функциональных возможностей за счет выполнения операции сдвига путем введения блока формирования параметров сдвига, двух блоков поворота кода, коммутатора, счетчика и изменения связей. 6 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и/р я/р
Z= g (У1 > Х (2Р ) )(2Р), i=1 i=1 (21) 4699058/24 (22) 04.04.89 (46) 23.08.91, Бюл. М 31 (72) А,И,Бобровский, Ж.Б.Ерема-Еременко, И.А,Лезин, B.Н.Марчук и И.С.Тищишин (53) 681,325(088.8) (56) Авторское свидетельство СССР
М 798820, кл. G 06 F 7/38, 1978.
Авторское свидетельство СССР
N 754412, кл, G 06 F 7/52, 1978, (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ
Изобретение относится к цифровой вычислительной технике и предназначено для умножения и сдвига чисел, представленных в двоичной системе счисления, и может найти применение в качестве операционного блока в высокопроизводительных вычислительных машинах и системах.
Целью изобретения является расширение функциональных возможностей устройства эа счет выполнения операции сдвига.
В устройстве операнды положительные числа. представляются в виде А= ; ai2 .
-1
i 1
aiE. {О, 1}, где А = а1а2...а двоичный и-разрядный код числа А. Выполнение операции умножения в предлагаемом устройстве, так же как и в известном, основано на таблично-алгоритмическом методе умножения, одНако в отличие от известного в предлагаемом устройстве процесс умножения конвейеризован за счет совмещения во времени получения элементарных произве... SU,, 1672441 Al (57) Изобретение относится к цифровой вычислительной технике и предназначено для умножения и сдвига чисел, представленных в двоичной системе счисления, и может найти применение в высокопроизводительных вычислительных машинах и системах. Цель изобретения состоит в расширении функциональных воэможностей за счет выполнения операции сдвига путем введения блока формирования параметров сдвига, двух блоков поворота кода. коммутатора, счетчика и изменения связей. 6 ил. дений и накопления суммы частичных изведений. и л
Пусть Х= g xi2 и Y= у 2 множи
i =1 i =1 и множитель соответственно, где хь yi — значение i-x разрядов кодов сомножителей.
Тогда для представления точного результата Z = X Y требуется 2п-разрядный двоичный код.
Процесс вычисления произведения 2 запишется в виде где Х = х xi+1...õi+ -1 — i-я двоично-кодированная цифра кода множимого в канонической позиционной системе счисления с основаниемq =2;
Yi = yi ye+1...yi+p-1 — i-я двоично-кодированняа цифра кода множителя.
1672441
Таким образом, процесс умножения состоит из однотипных повторяющихся циклов. Во время очередного j-го цикла -e
П/У частичное произведение Yi, Xi 2 " выi =1 и числяется на — = К умножителях, выполр няющих операцию умножения р-разрядного двоичного кода У на р-разрядный двоичный код Xi с образованием произведения разрядности 2р и "собирается" в ni р двоично-разрядный код частичного произведения Х У на сумматоре.
Наличие регистра частичных произведений при соответствующем управлении позволяет организовать конвейер при вычислении Z, когда в один и тот же момент времени на одном сумматоре формируется частичное произведениде XYi+>, а на другом сумматоре формируется сумма частичных произвдений 7; =- Zi-1 2 " + XYi, причем Zo =О, Z--Zs.
Выполнение операции сдвига в устройстве основано на том, что операция сдвига влево аналогична умножению сдвигаемого двоичного кода на соответствующую степень числа 2.
Пусть d — число сдвигов (т.е. число разрядов, на которое необходимо сдвинуть двоичный код), Тогда сдви влево будет аналогичен умножению сдвигаемого кода на число 2 . При большом d умножение произd водить не выгодно иэ-за большого числа циклов умножения. Поэтому цвоичный код числа сдвигов дешифрируется и полученныи унитарный код разбивается на группы по р разрядов. Пусть в г-й группе р разрядов (г = 1,...,)2 /р(, где )а(— ближайшее к а целое, такое, что а )а(, С- разрядность числа сдвигов б) есть I (наэовем эту группу р разрядов параметром сдвига С). тогда производится умножение на r-ю группу р разрядов с помощью аппаратуры умножителя и r-1 (это число назовем параметром сдвига М, М
= г- 1) аппаратный сдвиг на р разрядов.
Число сдвигов M на р разрядов отслеживается с помощью счетчика и выполняется на сдвиговом регистре, который может быть реализован, например, с помощью косой передачи.
Сдвиг вправо аналогичен сдвигу влево повернутого кода. Поворотом кода бдует называть преобразование следующего вида.
Пусть двоичный и-разрядный код числа B имеет вид В = bib „.b>, то да после поворота он имеет вид В*=0,...b2 01
Поэтому при сдвиге вправо сдвигаемый код необходимо повернуть, произвести
55 сдвиг влево и снова повернуть полученный код.
На фиг.1 приведена гтруктурная схема вычислительного устройс.тва; на фиг,2 — пример реализации блока поворота кода; на фиг.3 — пример реализации блока формирования параметров сдвигов; на фиг,4-6 — относительные временные диаграммы сигналов на выходах блока микропрограммного управления при работе устройства
Устройство содержит (см. фиг.1) регистры множимого 1 и множителя 2, умножители
31-3к, сумматор 4 элементарных произведений, сумматор 5 частичных произведений, блок 6 формирования параметров сдвига, блок 7 микропрограммного результата. счетчик 8, второй блок 9 поворота кода, коммутатор 10 регистры 11 и 12 частичного произведения и результата соответственно, первый блок 13 поворота кода. выходы 1424 блока 7, входы 25 адреса первой микрокоманды, тактовый вход 26 и вход 27 окончания операции блока 7, вход 28 числа сдвигов устройства.
Блок поворота кода 9 (13) содержит (см.фиг.2) содержит первую 29 и вторую 30 группы элементов И, группу элементов ИЛИ
31.
Блок 6 формирования параметров сдвига (см. фиг,3) содержит дешифратор 32, первую 33 и вторую 34 группы элементов ИЛИ, шифратор 35.
Счетчик 8 предназначен для подсчета выполняемых сдвигов на р разрядов и циклов умножения и выда <и сигнала о завершении выполнения операций.
Блок 9 поворота кода предназначен для передачи на регистр множимого 1 множимои го или сдвигаемого кода X= g х,2 в норi =1 мальном виде или с поворотом в зависимости от направления сдвига.
Коммутатор 10 предназначен для передачи на регистр множителя 2 множителя или параметра сдвига С.
Регистр множимого 1 предназначен для хранения множимого или сдвигаемого кода X.
Регистр множителя 2 сдвиговый. и-разрядный, причем сдвиг осуществляется в сторону младших рдазрядов на р разрядов.
Предназначен для хранения множителя Y или параметра сдвига С.
Умножители Çi...3ê предназначены для вычисления очередного элементарного произведения XiYi, i = 1,...,К, имеют два р-разрядных входа и 2р-разрядный выход.
Сумматор 4 элементарных произведений -двуухвходовый, п-разрядный, предназ5
1672441 начни Qfl<) ф(эРг1(<Рп(3:эн)1Я cT<1PI Сумматор 5 частичных пооиэнедении днухвходоный, п<р-разрядный. предназнз- <п чен для сложения двух слзгзеглых Регистр результата 12 — n-I-p-разрядный сдвиговый, причем сдвиг осу<цестнляется l3 сторону старших разрядов. 11редназначен для хранения результзтон умножения или 15 сдига, Блок поворота кодл 13 предназначен для выдачи результата i, НоМ виде или с <)o <)1, i о если:.! BL1( осуществлялся Bllpnno. При вь<полн<эн(<и оп ".;<ци(1 (г.<ножения устройство рзбо < з<..т (1< .; ющим образом, В исходном состоя«и регистры 1, 2. 11, 12 обнулены (на ф(1(.1 цнии сброса и питания не показаны). По си(налзм блока 7 (на выходах 16, 17, 13, 24 18) r.)I В каждом цикле углножения Х на очереднь е р разрядон нз y()pB( В первом (j -- 1) цикле по сигналу на выходе 21 бло< з 7 нз умножителях 3!...3v, происходит формиронзг<ие I< элег",ентарных произведений Xi Y! —, I = 1, 2 ..K, а ио сигна лу наа выходе 20 блока 7 они "ccF. ираются" на суглматоре 4 31 час» ое про згедение запись<нается на ре< и<.<1 1, одг о(эрегленг<(э происходит сдн(<г мно<кителя на р разрядов 45 в регистре vk В последующих циклах происходит умножение Х нз очер".;1 <не р рлэрядо(э Y c однонременныгл сложениег. частичного произведения с содержа;иег",,".егистра 12, сдвинутыгл нз р р;эзрядов в ..орону младших разрядов с поr . )n<,üþ косой передачи на сумматоре 5 по си(н1. у I
В кл кдпм L <1< k CL1I НаЛЗМ НЗ НЬ ХОДЕ 15 (<рОИСХОдИт СчЕт цИКлен IIB с <ет После завершения слож<.I 12 оказывается и р clзршис разрядов хода произведения з нз ре(истре 2 и-р млздшис разряд()н K()дл прпизнедения. Об окончании операции угл)<ожег<3<я сигнализирует счет <èv.. При ныполl В исходном ссс)(<янин регист<)ы 1, 2, 11, 12 обнулены. Нз упр Г!о сигналам блока 7 на выходах (16, 17 18, 23, 2-1 I сдвиг;3(.глый код <врез блок поворота кода 9 в нормалhilîм ниде ириниглзется нз регистр 1. на ре Вг<тем по сигналу на выходе 21 блока управления 7 на ум<<ожи<елях 31.Д3к происходит <1<ормировл(<ие К элемен зрных произ(<еден)<й Х, С, 11, 2,...,,V,, з по си(нзлу на выходе 20 блока 7 они "собирз<отся" на сумматоре 4 и частичное ироизьч)дение ззпол<инзетсч нз регистр(. 11. Затем ио си(нзлу на выходе 21 происходит сложение частичного произведения с нулем и запоминание результата на регистре 12. l1o сигналам нз выходе 15 происходит не()Г»одимое число сдви(он влево нз р разрядов с одновременной иода <еи си(нзлов нз с I IpL< выполнении оиеpi цl<и сдг<ига нпра«о н;3 управляющие входьi иогтупз<от сигналы г;)к К<3К 3TQ показано ><,«1 ci ;I )<злам (16, 17.?3, 24. 18) .днигземыи код че1) .з блок 9 поворота кодл с поворотом ир(1 <имзется в регистр 1 Далее процесс повторчетгя аналогично сдвигу влево. По окончании операции сдни(з результат сниглается с регистра 12 через блок 13 rkof!opo a кода и с поворотом кода. Формула изобрет.ния Устройство для умножe«L< содержащее регистры глножиглого и глножителя. К у(<ноя ителей (К = и/р, где i) разрядность операндов, р — количест<<о )д«онременно обрабатываемых разрядов оп .рзндз), сумглатор элементарных пр . (3(:ден)<й, ре1672441 гистр частичных произведений, сумматор частичных произведений, регистр произведения и блок микропрограммного результата, причем вход первого сомножителя каждого умножителя соединен с выходом соответствующих р разрядов регистра множимого, а вход второго сомножителя — с выходом р младших разрядов регистра множителя, входы разрядов первого слагаемого сумматора элементарных произведений соединен соответственно с выходами р старших разрядов каждого умножителя, выходы р младших разрядов j-го умножителя (j = 2...,К) соединены соответственно с входами (pj - р)-х разрядов второго слагаемого сумматора элементарных произведений, выходы р младших разрядов первого умножителя соединены соответственно с входами р младших разрядов регистра частичных произведений, входы последующих разрядов которого соединены с выходами соответствующих разрядов сумматора элементарных произведений, а выход — с входом первого слагаемого сумматора частичных произведений, вход второго слагаемого которого соединен с выходом регистра результата, информационный вход которого соединен с выходом сумматора частичных произведений, вход разрешения суммирования которого соединен с входом записи регистра результата, управляющим входом К умножителей и первым выходом блока микропрограммного управления. второй выход которого соединен с входом записи регистра множимого и первым входом записи регистра множителя, вход сдвига которого соединен с входом записи регистра частичных произведений, входом разрешения суммирования сумматора элементарных произведений и третьим выходом блока микропрограммного управления, четвертый выход которого соединен с входом сдвига регистра результата, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональ10 40 ных возможностей за счет выполнения операции сдвига, в него введены блок формирования параметров сдвига, первый и второй блоки поворота кода, коммутатор и счетчик, вход установки которого соединен с пятым выходом блока микропрограммноro управления и первым выходом блока формирования параметров сдвига, второй выход которого соединен с первым информационным входом коммутатора, второй информационный вход которого соединен с входом множителя устройства. а выход — с первым информационным входом регистра множителя, второй информационный вход которого соединен с выходом р младших разрядов регистра результата, а второй вход записи — с шестым выходом блока микропрограммного управления, второй выход которого соединен с информационным входом счетчика, счетный вход и выход которого соединены соответственно с седьмым выходом и входом окончания операции блока микропрограммного управления, восьмои и девятьiA выходы которого соединены соответственно с первым и вторым управляющими входами коммутатора, выход регистра результата соединен с информационным входом первого блока поворота кода, выход которого соединен с выходом устройства, а первый и второй управляющие входы — соответственно с десятым и одиннадцатым выходами блока микропрограммного управления и первым и вторым управляющими входами второго блока поворота кода. информационный вход которого соединен с входом множимого устройства, а выход — с информационным входом регистра множимого, вход кода операции и управляющий вход устройства соединены соответственно с входом адреса первой микрокоманды и тактовым входом блока микропрограммного управления, вход блока формирования параметров сдвига соединен с входом числа сдвигов устройства. 1672441 Выходы блока упааоЛЕНОЯ 19. 16 18 МгпомаГпическое дреня Фиг. 9 1672441 Й одь ба а улоодлсния 14 16 17 18 19 21 22 24 Фиг 5 ° Ф Вьподы йл Owo у раВлеииа 15 ! 17 19 22 Abno omuvecroe dptn11 < Составитель Е.Мурзина Техред М.Моргентал Корректор А.Осауленко Редактор А.Бер Заказ 2840 Тираж 376 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при f KHT СССР 113035. Москва. Ж-35, Раущская наб., 4/5 Производствен го-издательский комбинат "Патент", г. Ужгород, ул.Гагарина. 101
