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

Авторыобретен А.И.Березенко, Ф.Л. Гладыш, С.Е.Калинин, 3."НМврялин,А.М.Репвтюк и Е.М.Репетюкь 71) Заявитель 4) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ДВОИЧНЫХ ЧИСЕЛ15 п риц сумм дов),разряд Изобретение относится к. вычислительной технике и может найти нрименение в электронных вычислительных машинах и быстродействую;их процессорах обработки данных.Известно устройство, содержащее три ступени логических ячеек, на основе которых возможны построения умножителей любой разрядности 111.Недостатком устройства является широкая номенклатура модулей для построения умножителей с расширенной разрядностью сомножителей, а также низкая степень интеграции модулей, что обуславливает неэфФективность реализации их в виде больших интегральных схем (БИС),Наиболее близким к изобретению о техническому решению является устройство, содержащее матрицу Йх к(М) полных одноразрядных сумматоров (где Й - разрядность операнмат у ЙхЙ элементов И, 2 М ный атор, причем выход переноса полного одноразрядного сумма"тора )-го столбца 1-й строки соединен с входом переноса полного одноразрядного сумматора (+1)-го столбца (1+1)-й строки, где 1=1М М=2(Й), 1=1 выход уммы а,Ь"го полного одноразрядного сумматора соединен с входом сумин (а+1)", Ь-го полного одноразрядного сумматора (гдеа=1М" 1, Ь=2 И"1), выход пе"реноса полного одноразрядного сумматора (М)-й строки с-го столбцасоединен с входом переноса полногоодноразрядного сумматора 1-й строки(с+1)"го столбца, где С= М,первые входы элементов И соединенысоответственно с разрядными входными шинами множимого устройства, вторые входы элементов И соединены соответственно с разрядными входнымишинами множителя устройства, выходыэлементов И (Ч+1)-й диагонали матрицы элементов И (где (=1,2 Й"2)соединены соответственно с входамю.У1 , и=1 1 пгИ), где. К и для- :- бли,"я, ом Я 1,жайшее целое меньшее или равное -а и- вес разряда произведения, 3 ыходы 2 Й-разрядного сумматора являют"ся выходами устройства 23,Недостатками этого устройства яв-,ляются:- избыточное количество основныхи дополнительных выводов устройства;- недостаточное быстродействие;-. отсутствие возможности вынесения из устройства 2 Й-разрядного сумматора в качестве внешнего автономного узла, что позволяет сэкономитьколичество выводов в устройстве.Цель изобретения - расширениеФункциональных возможностей за счетвыполнения операции суммирования 2 Й-разрядного слагаемого, повышение быстродействия.Поставленная цель достигаетсятем, что в устройство введены 2 Кэлементов памяти, причем выход переноса полного одноразрядного сумматора (Й)-й строки д-го столбцасоединен с входом переноса полногоодноразрядного сумматора (Й)-йстроки (4+1)-го столбца (где д==И/2-1И), выход переноса пол"ного одноразрядного сумматора (К-З)"йстроки е-го столбца соединен с входом сумма полного одноразрядногосумматора (Й)"й строки (е+1)"гостолбца (где е=И/2,.И"3), выходы выходных полных одноразрядныхсумматоров соединены соответственно с входами (2 Й) старпих элементов памяти, выход элемента Ипервой диагонали матрицы элементовИ соединен с входом младшего элемента памяти, выходы 2 Й элементовпамяти соединены соответственнос входами первой группы 2 К"разрядного сумматора, входы второй группы которого являются входами суммирования устройства, вход переносаполного одноразрядного сумматорапоследней строки (И/2+1)-го столбца является входом округления устройства.На фиг. 1 представлена функциональная схема восьжразрядного устройства для умножения двоичных чисел,на фиг. 2 - то же, матрицы умножения, на фиг 3 - структурная схе" 8282 4 ма иллюстрирующая работу устройства.Устройство содержит элементы е И 1, матрицу 2 полных одноразрядныхсумматоров 3, 2 Й-разрядный сумматор 4, шины 5 множимого, шины 6множителя, вход 7 управления, входы8 суммирования, вход 9 округления,выходы 1 О .устройства, элементы 11 1 р памяти.Устройство для умножения шестнадцатиразрядных чисел состоит изчетырех модулей умножителей 12-15восьмиразрядных чисел, каждый из 1 которых содержит матрицу 16, включающую элементы И, регистры 17,шестнадцатиразрядный сумматор 4,выходной регистр 8, выход 9 переноса и вход 20 управления. Матрица6, регистр 17 и сумматор 4 разделены, пунктиром на старшую и младшую части.В устройстве выход переноса полного одноразрядного сумматора 3 1 -гостолбца 1-й строки соединен с входом переноса полного одноразрядногосумматора 3 (+1)"го столбца (+1)"йстроки где =1М-, М=2(К),1=1К выход суммы а,б"го полного одноразрядного сумматора 3 соединен с входом суммы (а+1), б-гополного сумматора 3 (где а=1К, Ь=2И"1), выход переносаполного одноразрядного сумматора3 (К"1)-й строки С-го столбца соефф динен с входом переноса полного одноразрядного сумматора 3 Й-й строки(с+1)-го столбца где с=М/2. ,М первые входы элементов Исоединенысоответственно с разрядными вход 4 рщми шинами 5 множимого устройства, вторые входы элементов Исоединены соответственно с разряднымивходвами шинами 6 множителя устройства выходы элементов И(с+1)"й ф диагонали матрицы элементов И(где с 12 К) соединены соответственно с входами первых К полныходноразрядных сумматоров 3 Ч-го стол 1у бца (где Ч=1И), где К= п для.П1 й1 ф- ближайшее целое меньшееП 71или равное и/2, а и - вес разрядапроизведения, выходы Й-разрядного "И сумматора 4 являются выходами Оустройства, выход переноса полногоодноразрядного сумматора 3 (К)-йстроки д-го столбца, соединен с938282 6 норазрядном сумматоре 3. б, Для И=8 разрядов это составит 4 Т.По первому такту, поступающему10 на вход 7, полученные произведеР 7 1 Э гф . Юния Р., Р, Р, Р, о запоминаются в регистрах 17. С выходоврегистров 1 произведения поступаютна соответствующие входы сумматоров1 з 4 с сдвигом влево частичных произведений, обусловленным алгоритмомперемножения. При сложении частичных произведений в сумматорах 4 сиг.нал переноса с выхода 19 образуетро ся только в сумматоре 4 модуля 14.Сигнал переноса на выходе 19 модуля 13 отсутствует, так как в немпроизводится сложение старшей части произведения, сформированной мо 23 дулем 12, и младшей части произведения, формируемой модулем 13.При этом в выходном сумматоре4 устройства при формировании произ.ведения сигнал переноса отсутствущ ет. В устройстве сигнал переносавозникает в выходном сумматоре 4только в момент сложения частичныхпроизведений при объединении модулей, при этом сигнал переноса с выхо33да 19 модуля 14 поступает на вход 8модуля 15.По второму такту на входе 20 результат сложения в виде тридцатидвухразрядного произведения запоминается в регистре 18. При поступленииновых операндов с темпом, равнымодному такту работы устройства, полный цикл работы повторяется,Объединение модулей осуществля 45ется подключением выходов 10 старших разрядов произведения модуля12 к входам 8 модуля 13, при этомвыходы 10 модуля 13 соединены с входами 8 модуля 14 и т.д.В отличие от известного в предла"фф гаемом устройстве .существует направленность передачи данных промежуточных вычислений при объединениимодулей и отсутствует обратнаясвязь между модулями, что позволя- И ет легко организовать конвейерныйпринцип вычисления.Конвейерная структура шестнадцатиразрядного умножителя, составленвходом переноса полного одноразрядного сумматора 3 (й" 1)-й строки(0+1)-го столбца (где с 1 цМ/2"1М), выход переноса полного одноразрядного сумматора 3 (М)-й стро.ки е-го столбца соединен с входомсуммы полного одноразрядного сумматора 3 (й)-й строки (е+1)-го столца (где е=М/2 М"3), выходы выходных полных одноразрядных сумматоров 3 соединены соответственно свходами (2 й) старших элементов11 памяти, выход элемента И 1 первойдиагонали матрицы элементов И 1 соединен с входом младшего элемента 11памяти, выходы 2 М элементов 11 па-. мяти соединены соответственно с входами первой группы 2 й-разрядногосумматора 4, входы 8 второй группы которого являются входами суммирования устройства, вход переносаполного одноразрядного сумматорапоследней строки (М/2+1)-го столбца является входом 9 округленияустройства,Реализация устройства может бытьвыполнена в виде модуляВ матрице2 полных одноразрядных сумматоров 3непосредственно выполняется перемножение двух М-разрядных чисел,которая может быть выделена в видеавтономного устройства, а 2 К-разрядный сумматор 4 может быть либовключен в состав устройства умножения при его реализации в виде БИС сцелью исключения дополнительного оборудования при объединении модулей,либо выделен из БИС с целью экономии выводов.Введение элементов 11 памяти всочетании с размещением дополнительных входов по краям матрицы 1позволяет легко осуществить конвейерный режим умножения при объединении модулей с целью расширенияразрядной сетки сомножителей.Работа устройства иллюстрируется примером выполнения перемножения шестнадцатиразрядных чисел вконвейерном режиме.На вход модуля 12 поступают Х 1 Ои У разряды сомножителей, на вход1-0модУлЯ 1 3 Х г о и У 1 8 р на вход модУля 14 Х о и У 15 8 и на вход модуля15 Х 8 и У 1.8. В каждой матрице 16на элементах И выполняется логическое умножение разрядов сомножителей, после чего непосредственнов матрице 2 полных одноразрядных сумматоров 3 выполняется поразрядное сложение логических проиэведений и распространение сигнала переноса вдоль матрицы 2 за время, равное 2(М)Т где С - . время распространения сигнала в полном одФормула изобретения 7 9382 ная из восьмиразрядных модулей, требует равенства временвях соотношений в ступенях конвейера. Поэтому, с целью выравнивания переходного процесса в ступенях, сумматоры 4 5 могут быть выполненыпо схеме с груп" повым переносом.Таким образом, в результате новой организации связей в матрице полных одноразрядвюх сумматоров, введе- О ния дополнительных входов в 2 Мразрядный сумматор, общее количество выходов и входов становится на два меньше, чем в известном устройстве, уменьшается время умножения на вре- И мя задержки одноразрядного сумматора, осуществлен конвейерный принцип умножения при объединении модулей, получена возможность дополнительного сложения в Й-разрядном умножите- щ ле 2 Й-разрядного числа с 2 Й-разрядным произведением.При объединении модулей получена возможность уменьшения времени умножения. 23Модульная структура устройства для умножения позволяет ориентировать реализацию устройства в виде БИС; Устройство для умножения двоич, ных чисел, содержащее матрицу Йх. к(М" 1) полных одноразрядных сумматоров (где М - разрядность операндов ), матрицу МАЙ элементов И, 2 М" разрядный сумматор,спричем выход переноса полного одноразрядного сумматора 1-го столбца соединен с входом переноса полного одноразрядного сумматора (1+1)-го столбца, где1М"1, М(М"1), выход сумьы аЬ-оо полного одноразрядного сумматора соединен с входом суммы (а+1) Ь"го полного одноразрядногосумматора (где а 1Й"1, Ь 2 М), выход переноса полного одноразрядного сумматора (Й" 1) -й строки50 с-го столбца соединен с входом переноса полного одноразрядного сумматора Й-й строки (с+1)-го столбца, где С И/2 М"1), первые входы элв" ментов И соединены соответственно с разрядами входными шинами множи- фф 82 8мого устройства, вторые входы элементов И соединены соответственно сразрядными входными шинами множителя устройства, выходы элементовИ (ц+1)-й диагонали матрицы эле"ментов И (где пщ 12 Й+1) соединены соответственно с входамипервых К полных одноразрядных сум.маторов Ч-го столбца (где Ч=11лп=М), где К- пе для,3-1 - блипм ыжайшее целое меньшее или равноеи/2, а и - вес разряда произведения, выходы 2 Й-разрядного сумматора являются .выходами устройства,о т л и ч а ю щ е е с я тем, что,с целью расширения функциональныхвозможностей за счет выполненияоперации суммирования 2 М-разрядного слагаемого, повышения быстродействия в устройство введены 2 М элементов памяти, причем выход переноса полного одноразрядного сумматора (Й"2)-й строки 4-го столбцасоединен с входом переноса полногоодноразрядного сумматора (Й)"йстроки (д+1)-го столбца (где О=М/2-1,.,М), выход переноса полногоодноразрядного сумматора (Й)-йстроки е-го столбца соединен с входом сумма полного одноразрядногосумматора (Й"1)"й строки (е+1)-гостолбца (где е=М/2 И-З), выходы выходных полных одноразрядныхсумматоров соединены соответственнос входами (2 Й) старших элементовпамяти, выход элемента И первой диагонали матрицы элементов И соединен с входом младшего элемента памяти, выходы 2 М элементов памятисоединены соответственно с входамипервой группы 2 М"разрядного сумматора входы второй группы которогоявляются входами суммирования устройства, вход переноса полного одноразрядного сумматора последнейстроки (М/2+1)-го столбца являетсявходом округления устройства.Источники информации,принятые во внимание при экспертизе1 Патент США У 3914589,кл. С 06 Г 7/39, опублик. 1975.2. Патент США В 3752971,кл. С Об Р 7/39, опублик, 1975938282 Составитель Л.Медведеваактор Н.Джуган Техред И. Гайду Корректор аказ 44 тент , г. Ужгород, ул. Проектная Филиал ППП 73 Тираж 73ВНИИПИ Государственногопо делам изобретений и113035, Москва, М, Р Подписноекомитета СССРоткрытийшская наб д. 4/