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

(5 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ си ф овичиГровые М.Про жи мого втор 4 8 часчес, с.63 тво СС 1978,МНОЖ НИЯ ЧИ рога 7 маиру Бута. ринГровой вы- . начено для ых дополнийти примего блока в ся кци редназ воичн жет на ционно(54) УСТРОЙСТВО ДЛЯ УСЕЛ(57) Изобретение относитчислительной технике, иумножения и-разрядных дтельных кодов чисел и монение в качестве опера высокопроизводительных машинах и мах. Цел ь изобретения - расширение циональных возможностей устройст счет реализации операции умножения полнительном коде путем введения ройство, содержащее регистры мно 1 и множителя 2, умножители 3, сумм элементарных произведений, регистр тичных произведений, регис произведений и блок 6 микроп раммного управления, бло формирования константы и су торэ-вычитателя 5, Произведение фор ется по обобщенному алгоритму Работа устройства организована по ципу конвейера, 1 з,п. Г-лы, 3 ил,Изобретение относится к цифровой вы- ментарных произведений, выход старших р числительной технике и предназначено для разрядов 1-го умножителя ( = 1, 2, .К) подумножения и-разрядных двоичных допол- ключен к первому входу соответствующих р нительных кодов чисел и может найти при- разрядов сумматора элементарных произменение в качестве операционного блока в 5 ведений, выход которогосоединен с входом высокопроизводительных машинах и систе- соответствующих разрядов регистра частичных произведений, выход которого соеИзвестно устройство для умножения чи- динен с входом соответствующих разрядов сел, представленных в дополнительном ко- регистра частичных произведений, вход де, содержащее регистры операндов, 10 разрешения сдвига регистра множителя, сумматор и группу элементов И. входы разрешения выдачи умножителей,Недостатком устройства является его вход разрешения суммирования элементарниэкое быстродействие, что объясняется ных произведений, вход разрешения реги- большим числом циклов умножения (всего стра частичных произведений, входы15 разрешения записи и разрешения сдвига и циклов, так как используется модифици- регистра произведения соединены с соотрованный алгоритм Бута). Этот же недоста- ветствующими выходами блока управления, ток у устройства., реализующего алгоритм введены блок формирования константы, Бута (всего и циклов). сумматор-еычитатель, причем выходы младНедостатком устройства, реализующе ших р+1 разрядое регистра множителя соего умножение дополнительных кодов явля- динены с информационным входом блока ется необходимость коррекции сформиро- формирования константы, выход старшего ванного кода произведения, что снижает (знакового).разряда регистра множителя собыстродействие устройства. единен с управляющим входом блока фор- .Наиболееблизким к предлагаемому яв мирования константы, первый выход ляется устройство для умножения чисел, со- которого (р разрядов) соединен с входом держащее регистры множимого и второго сомножителя каждого умножителя, множителя, К умножителей формата р х второй выход(р разрядов) соединен с старх р + 2 р (где К такое,.что Кр Ъ и, и - шимирразрядамивтороговходасумматора разрядность.операндов), комбинационный 30 элементарных. произведений, а третий.высумматор элементарных произведений(да- ход с входом режима сумматора-вычитателее употребляется сумматор элементарных ля, выход регистра частичных произведений произведений) накапливающий сумматор соединен с входом второго слагаемого сумчастичных произведений (Фактически вклю- матора-вычитателя, выход которого соедичающий в себя регистр частичных проиэее нен с входом регистра произведения, выход дений, сумматор, регистр произведения) и которого соединен с входом первого слагаблок управления. емого сумматора-вычислителя, синхронизиНедостатком устройства является рующий вход блока формирования узостьфункциональныхвозможйостей(реа- константы и вход разрешения суммировализована операция умножениядвоичныхко ния соединены с соответствующими выходов модулей чисел). Целью изобретения дами блокауправления.является расширение функциональных воз- Снабжение устройства для умножения можностей устройства путем реализации чисел блоком формирования константы, операции умножения в дополнительных ко- сумматором-еычитателем, соединение вы 45 ходов младших р+1 разрядов регистра мноПоставленная цельдостигается тем,что жителя с информационным входом блока е устройство для умножения чисел, содер- формирования константы, соединение выжащее регистры множимого и множителя, К хода старшего(знакового) разряда регистра умножителейформатархр=2 р,гдеКтакое, множимого с управляющим входом блока чо К ри, и - разрядность операндов, р 3, 50 формирования константы, соединение его сумматор элементарных произведений, ре- первого выхода (р разрядов) с входом второгистр и блок управления, причем вход пер- го сомножителя каждого умножителя, втового сомножителя каждого умножителя с рого выхода (р разрядов) со старшими р выходом соответствующих р разрядов реги- разрядами второго входа сумматора элестра множимого, вход младших р разрядов 55 ментарных произведений, третьего выхода регистра частичных произведений соеди- свходомрежимэсумматора-вычитателягсоненсвыходомрмлэдшихразрядовпервого единение выхода регистра частичных проумножителя,выходмладшихрразрядов)-го изведений с входом второго слагаемого умножителя= 2; 3, ,К) подключен к вто- сумматора-еычитателя, соединение его вырому входу(р)-р)-х разрядов сумматора эле- хода с входом регистра произведения, сое1714595динение выходов (и+р) старших разрядов Пустьп-раэрядноемножимоеХип-разрегистра произведения с входом первого рядный множитель У лежат в диапазоне 0,слагаемогосумматора вычитателя, соедине и представлены в дополнительном коде,ние управляющего входа блока формирова- т.е.ния константы и входа разрешения 5 Х=Х 1,Х 2,ХЗХП(Х 1-знаковыйразряд);.Суммирования сумматора-вычитателя с со- У = у 1, у 2. узуо (У 1 - знаковый разряд),ответствующими выходами блока управле- иния обеспечивает возможность реализации. ПрзводитсЯ К = - циклов УмноженивРоперации умножения в дополнительных ко- В и идах и конвейеризацию процесса умножеР р1) цикле вычислЯютсния, причем в каждом цикле работы С 1 "(2 рур/р+1+2 р урр+22 ур+устройства осуществляется умножение + ур 1+ ур 1+) 2 р;множимого на очередные.р разрядов мно- г-Х С;жителя на основе анализа очередных р+1, р г =г 2 Р+Е,3 Разрядов множителя и не требуется пре После К-го цикла Е - есть дополнительобраэования кодов сомножителей в прямые ный код произведения ХфУ, причем 260, 1).коды и дополнительный коррекции сформи- . Докажем, что обобщенный алгоритм Бурованного кода произведения для получе- та позволяет получить дополнительный кодния верного дополнительного кода . произведения двух сомножителей, предпроиэведения. 20 ставленных в дополнительном коде.Кроме того, указанные отличительные Пусть Ъ - содержимое накопителя попризнаки позволяют повысить быстродей- сле 1-го шага, множитель У = у 1 У 2 У уп+1,ствие устройства по сравнению с извест- имеет в исходном состоянии уп+1 = О, Ео - О.ным за счет сокращения числа циклов - Тогда пообобщенномуалгоритму БутауМНОжЕНИя И СОВМЕщЕНИя ВО ВРЕМЕНИ ПРО Е 1=-2 р уп-р+1+2" ул-р+2+ +2 уп-+цЕССОВ ВЫЧИСЛЕНИЯ ЧаСтИЧНЫХ И ЭЛЕМЕНтар- + уп+ уо+1 Х 2 р = -2 р уп-р+1+ 2 р ул-р+2ных произведений, + 2 у+ уп Х 2 Р, так как уп+1 = О. (1)Известен алгоритм Бута умножения чи-Выражения для следующих Едомножимсел в дополнительном коде с анализом двухна соответствующую степень двойки, Полочередных (у, у 1+1) разрядов множителя У. В 30 учим следующую систему равенств;исходном состоянии У=О, у+1=О, произво-1г 2 -1дится и циклов умножения, В )-м и =. и, и- "-2 - р 12 Уп-(2 р)+ "+ Ул.р+, Е=Е 2 +Складывая систему равенств(2) и сокрагде С - константа, вычисляемая на основе щая подобщая подобные, получаютанализа значений очередных р+1 разрядовУ;Рр) Лк = - 71+ Ц 2 р) 2 хУ 1 - -й разряд множителя У, дополнительный двоичный код которого у 1 у 2, . х 2 У 1+ "+ Уп-р+ уп-р+1 Х 2 рУл Ул+1;21 - частичное произведение в дополни- Подставив вместо Е 1 значение (1) и раэтельном коде;делив на (2 Р), получаютк-гУ - накопитель частичных произведе Ек = -у 1+ - У 21ний;2Х - множимое + ,Х 2,В известном устройстве используется (2 )модифицированный алгоритм Бута с анали- перейдя к и =К р, получаютзом трех очередных(у 1-1; У 1; у+1) разрядов У, 50 ук:+ 1 + + 1 Х 2в котором константа С формируется соглас 2 к = -у 1+ - у 2 +,+ - Ул Х 2но известной таблице за и циклов. а это есть истинный допониельный код2Е ХУ,Работа предлагаемого устройства осно- На фиг,1. приведена структурна схемавана на обобщенном алгоритме Бута, в ко устройства для умножения чисел; на фиг,2 -тором за. цикл аналиэи ются +13Р Ч Рую сЯ Р 1. РЭ относительная временнаядиаграммасигнаРазрядов множителя. В обобщенном алго- лов на выходах блока у ралов на выходах лака управления при раборитме бутависходномсостоянииЕ=О,уп+1= те устройства; на фиг,З - блокформирования константы.Устройство содержит регистр множимого 1 и множителя 2, К умножителей форматар х р -2 р 313 к, сумматор 4 элементарныхпроизведений, сумматор-вычитатель 5 частичных произведений, блок 6 управления, 5блок 7 формирования константы, регистр 8частичных произведений, регистр 9 проиэиведения, причем выходы 1-й (1 = 1, ., К-. - )рр-разрядной группы регистра множимого 1 10соединен с входом первого сомножителясоответствующего умножителя 3, вход второго сомножителя умножителей 3 соединенс первым выходом блока 7 (выход 13), выходстаршего разряда множимого 1 соединен с 15управляющим входом блока 7 информаци-,онный вход 12 которого соединен с вцходом(р+1) младших разрядов множителя 2, второй выход блока 7 (выход 14) соединен сстаршими р-разрядами второго входа сумматора 4, вход младших р разрядов регистра 8 соединен с выходом младших разрядовумножителя 31, выход младших разрядов1-го умножителя Д - 2.К) подключен к второму входу (р 1-р)-х разрядов сумматора 4, 25выход старших разрядов 1-го умножителя(1 " 1.,К) подключен к первому входу соответствующих разрядов сумматора 4, выходкоторого соединен с входом соответствующих разрядов регистра В, выход последнего 30соединен с входом второго слагаемого сумматора 5, вход режима которого соединен стретьим выходом блока 7, выход сумматора5 соединен с входом регистра 9, выход которого соединен с входом первого слагаемого 35сумматора 5, вход разрешения сдвига множителя 2, вход разрешения записи регистра8, вход разрешения сдвига регистра 9 соединены с выходом 1 О блока 6, выход 11соединен с синхронизирующим входом блока 7, входом разрешения выдачи умножителей 3, входом разрешения суммированиясумматора 5 и входом разрешения записирегистра 9.Регистр множимого 1, п-разрядный, 45предназначен для хранения множимого Х,представленного в дополнительном коде:лХ = - х 1+ х 21=,2 50Регистр множителя 2, п+1 разряднцй,предназначен для хранения множителя У,представленного в дополнительном коде Уи- - у 1+ Р у 21, причем сдвиг осущеет=2. %вляется в сторону младших разрядов на рразрядов,Умножители 313 к предназначены длявычисления очередных элементарных произведений Х /С;/ 1- 1,К, где Х; - код образованный 1-й группой р разрядов кодаХ; С 1 - р - разрядный код модуля величиныС 1. Умножители имеют по два информационных р-разрядных входа и 2 р-разрядные информационные выходы. Умножители могутбыть реализованы, например, в виде однократного матричного умножителя или в видеПЗУ с прошитой таблицей умножения прямых кодов положительных чисел в вторичной системе счисления,Сумматор 4 элементарных произведений - двухвходовой, п-разрядный, предназначен для формирования, старших иразрядов частичного произведения(С 1) Х; )1,2 К,Регистр 9 частичных произведенийпредназначен для организации конвейера и.в нем хранится частичное произведение(С 1)Х в дополнительном коде.Сумматор-вычитатель 5 частичныхпроизведений двухвходовой, и+р разрядный, предназначен для формирования суммы 71 частичных произведений Х С 11, причемна вход режима поступает знак величины С 1,1 = 1, 2 К, Иэ блока 7 формирования константы и при.значении знакаС 1- О проиЭЭОдится сложение, а при знаке 61 .:1вычитаниеБлок 7 формирования константы пред"назначен для формирования модуля кон-,.станты (С 1) в прямом коде (выход 13),поправки (выход 14) и знака С 1 на основеанализа очередных р+1 разрядов множителя,Пример реализации блока 7 приведенна фиг,З, где 12.1, 12,2,12.р, 12,р+1 - вы"ходы младших р+1 разрядов регистра множителя. 13 - р-разрядный выход модуляконстанты, 14 - р-разрядный выход поправки, 15 - р-раэрядный сумматор-вычитатель,предназначенный для формирования прямого кода модуля константы.По алгоритмуС 1 =2 ур 1-р+1+ 2 ур 1-р+2 +,+р.1 р+ 2 урИ + уй + Ур 1+1В обозначенияхфиг.З) имеютС 2 р 1 ур+1+.2 р ур+ +2 уз+у 2+у 1.Для получения /Сl при ур+1 = О необходимо к коду числа ур+1 уру 2 прибавить у 1 вмладший разряд, а при ур+1 " 1, то же самое и взять допои нител ьн ый код.Кроме того, на фиг,3 показаны р-разрядный вычитатель 16, предназначенный для формирования поправки, которая образуется следующим образом: произведение Х/С/при умножений вдополнительном коде, рри отрицательном Х, т.е, Х 1 = 1, имеет вид 1- -/С/Х, а получаемый результат был бц (1- -Х)/С= С-С/Х,т.е, необходимапоправ. ка 1-С/, а это дополнительный код от /С 1/;1714595 10 юСигнал 21: У/С / г2/ ЯМ 4 0 00 14 1011 ИТТ 75 Яб поправк/Ся/ игнал 20: 8 1111 0000 000 причем поправка подается на старшие р разрядов входа второго слагаемого сумматора 4, так как имеет такой вес и именно эти входы свободныот слагаемых умножителей 31,3 к, элемент И 17, группа р элементов И 18 вместе с элементом 17 предназначена для обнуления поправки при положительном Х и синхронизации ее выдачи, двухсту. пенчатый СО-триггер 19, предназначенный для организации конвейера.Блок 6 управления имеет два выхода.10 и 11 и формируют временную диаграмму (фиг.2), Блок управления может быть реализован, в частности, в виде блока микропрограммного управления, содержащего счетчик адреса микрокоманды и ПЗУ микрокоманд, в котором записано 2 - + 1р. микрокомэнд в соответствии с временной диаграммой (фиг.2).Регистр 9 произведения, 2 и-разрядный сдвиговый, причем сдвиг осуществляется в сторону младших разрядов на р разрядов.При выполнении операции умножения устройство работает следующим образом;В исходном состоянии в регистре 1 находится множимое Х, в регистре.2 в старших и разрядах множитель У, в младшем разряде 0(уп+1 =О), регистры 8 и 9 обнулены (фиг,1, цепи сброСа, синхронизации и питания.не показаны);Устройство работает циклически. поипринципу конвейера. Всего - циклов, Вркаждом осуществляется вычисление очередкого Ц-го) и+р-разрядного . частичного произведения (первая ступень конвейера) и добавление к сумме частичных пРоизведений предыдущего 0-1) частичного произведения (вторая ступень конвейера):В первом= - ) цикле по сигналу 21ирзапиСывается знак С 1 в триггер 19, на умно 3, + 0100 0001 3 0011 1100 жителях 313 к формируются К элементарных произведений Х/С 1/= 1 К, которые складываются на сумматоре 4, на суммато-. ре-вычитателе складываются нули, По сигналу 20 содержимое регистра 2 множителя сдвигается на р разрядов в сторону младших разрядов, на регистр 8 записывается первое частичное произведение,В последующих циклах по сигналу 21 "0 записывается знак С 1 в триггер 19, на умно- жителях 313 к формируются К элементарных произведений Х/С/ = 1К, которые складываются на сумматоре 4, на сумматоре-вычитателе 5 складываются очередные 15 частичные произведения, в регистре 9 накэпливается произведение. По сигналу 20 сдвигается содержимое регистров множимого 2 и произведения 9 на р разрядов в сторону младших разрядов, на регистр 8 20 записывается сформированное на сумматоре 4 частичное произведение,и После завершения К (К = - ) циклов неробходим еще один сигнал 20, по нему вхоло стую срабатывают умножители и блок 7 формирования константы, последнее частичное произведение сложится с содержимым регистра 9, на который пишутся старшие разряды произведения. 2. Таким 30 образом на регистре произведения оказывается (2 и)-разрядный дополнительный код произведения, дополненный да 2 п-знаковым разрядом, т,е. произведение 357 = Л 1 Е 1 22" Е 2 п.1 2 ВРассмотрим пример умножения для и=8, р =4.Пусть (Х)д = 1,100 1101 51 2 ) 40 (У)д = 0,001 1011 (+27 2 ) Дополняя (У)д 0 справа, получают (Уд = = 0001 10110 Анализируемая группа 10110, /С,/ 0001 10 О114 11 О1111 100 1010 2"йцикл поправкаХ /С,/ Так как знак С = 1, то на сумматоре 5 вычитают В 9 ОООО ОООО ООООК 8 111 0000 0001аа аЧГТИГацТаааа а/а К 8 1111 1001 1010к 9 ОООО 0000 1111 1111 Сигнал 21: К 9 0000 ОООО 1113кв 11 1 ОО 010аа аТ,ТГЧ аа а 1"Т 1 а 11 Г аа 1 а-14 ф 41 Е ) - -1377 2 = -5127 2у у.23Оценим аппаратурные затраты на достижение поставленной цели по отношениюк прототипу.Пусть прототип реализован как устройство для умножения и-разрядных двоичныхчисел, тогда объем оборудования. прототипа 40можно оценить какЧо Чумн + Чв + Чзм,где Чумн - объемоборудования умножителей;Чв - объем оборудования регистров 45множителя 1, множимого 2, произведения 9и частичного произведения 8;Чзм - объем оборудования сумматоровэлементарных и частичных произведений,Эти величины, проанализировав воз можные варианты реализации, можно оценить следующим образом, приняв заединицу измерения логический элемент типа И-НЕК,2 2 Р+1 55Чв =20 п+ 4 р;Чзм =2 Ои+ 10 р,Тогда Чо = К 2 Р + 40 и+ 14 р..Объем оборудования заявляемого устройства Чз= Чо+ЕЧ,ДЧ Чфк+ЛЧв,где Чфк - объем оборудования блока формирования константы 7;Л Чв - дополнительный объем оборудо-вания регистров 2, 8Чэк = 21 р+ 5, ЬЧв 20Тогда ЬЧ 21 р+ 25,Оценим относительное увеличение объема оборудования прототипа для и 32, р= 0,01,Чт.е. увеличение объема оборудования на 1позволяет выполнить операцию умножениянад числами в дополнительном коде, По.сравнению с аналогом в предлагаемом устройстве число циклов умножения уменьаеи ино на величину -- в , р 3 3, что свиде 2 Ртельствует о более высоком быстродействии предлагаемого устройства.Формула изобретения1, Устройство для умножения чисел, содержащее регистры множимого и множителя, К умножителей формата р х р -2 р(где Ктакое, что К р ъ и, и - разрядность операмСигнал 20: К 2 0 0000 ОООО Анализируемая группа 00011дов, р ) 3), сумматор элементарных. произведений, регистр частичных произведений, регистр произведений и блок микропрограммного управления, причем вход первогосомножителя каждого умножителя соединен с выходом соответствующих р разрядов регистра мйожимого, вход младших р разрядов регистра частичных произведений соединен с выходом р младших разрядов первого умножителя, выход младших р разрядов 1-го умножителя= 2, 3,., К) соединен с вторым входом (р) - р)-х разрядов сумматора элементарных произведений, выход старших р разрядов 1-го умножителя (1 = 1, 2,.;., К)соединен с первым входом соответствующих р разрядов сумматора элементарных произведений, выход которого соединен с информационным входом соответствующих разрядов регистра частичных произведений, вход разрешения сдвига регистра множителя, вход разрешения записи регистра частичных произведений и вход разрешения сдвига регистра произведений соединены .с первым выходом блока микропрограммного управления, второй выход которого соединен с входами разрешения выдачи умножителей, входом разрешениясуммирования элементарных произведений и входом разрешения записи регистра произведения, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем реализацииоперации умножения в дополнительном коде., в него введены блок формирования константы и сумматор-вычитатель, причем выход младших р+1 разрядов регистра множителя соединены с информационным (р+1)-разрядным входом блока формирования константы, выход старшего знакового разряда регистра множимого соединен с управляющим входом блока формирования, константы, первый и второй р-разрядные выходы которого соединены соответственно с входом второго сомножителя каждого умножителя и входом старших р разрядов второго слагаеМого сумматора элементарных произведений, а третий выход - с входом режима сумматора-вычитэтеля, выход регистра частичных произведений - с входом второго слагаемого сумматора-.вычитателя, выход которого соединен с информационным входом регистра произведения, выход которого соединен с входом первого слагаемого сумматора-вычитателя, синхровход блока формирования константы и вход разрешения суммирования сумматора-вычитэтеля соединены с вторым выходом блока микропрограммного управления,2, Устройство по п.1, о т л и ч а ю щ е ес я тем, что блок формирования константы содержит сумматор-вычитатель, вычитатель, элемент И, группу из р элементов И и триггер, причем вход первого разряда информационного(р+1)-разрядного входа блока соединен с входом переноса заема сумматора-вычитателя; р-разрядный вход второго слагаемого которого соединен соответственно с входами р разрядов, начиная с второго информационного (р+1)-разрядного входа блока, вход (р+1)-го разряда информационного входа блока соединен с входом режима сумматора-вычитателя и информационным входом триггера, выход сумматора-вцчитателя соединен .с входом вычитаемого вычитателя, выходы которого соединены с первыми входами соответствующих элементов И группы, вторые входы которых соединены с выходом элемента И, первый вход которого соединен с упраеляющим входом блока, синхровход которого соединен с вторым входом элемента И и синхровходом триггера, вход первого слагаемого и вход уменьшаемого сумматора-вычитателя. соединены с входом логического .нуля, выходы суммэтора-вычитателя, элементов И группы и выход триггера соединены соответственно с первым и вторымр-разрядными выходами и третьим выходом45 ,блока,1714595 ФГ Г13.,01 ЮСоставитель А.Бобровский Редактор М.Бланар Техред М.Моргентал Корректор В.Гирня Заказ 694 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5