Устройство для умножения Советский патент 1985 года по МПК G06F7/52 

сумматора и регистра множителя, входы обнуления разрядов которого соединены с информационными входами соответствующих разрядов первого бу.ферного регистра, выход первогоэлемента И блока управления подключен ко входу счетчика блока управления, прямой выход первого и инверсный выход второго разрядов которого соединены

со входами элемента 1-ШИ, прямой выход второго разряда и выход переполнения второго разряда счетчика блока управления подключены соответственно ко входу управления сквозным переносом накапливающего сумматора и выходу индикации окончания . операции умножения устройства.

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, содержащее регистры множимого и множителя, матрицу элементов И, группу элементов ИЛИ, накапливающий суьматор и блок выделения младшего разряда, причем выхода разрядов регистра множимого соединены с первыми входами элементов И соответствукадих столбцов матрицы, выход j-ro эле . мента И i-й строки матрицы- (t 1,.,,, ,...,ri; n- разрядность сомножителей ), кроме первого элемента И первой строки матрицы и п-го элемента И п-й строки матрицы, подключен ко входу (t + j -2)-го элемента ИЛИ групгал, о тличающ е е с я тем, что, с целью повышения быстродействия, в устройство введены два буферных регистра и блок управления, содержащий счетчик, два элемента И и элемент ИЛИ, блок выделения младшего разряда содержит п ,зпементов И, а накашшвакщ й сумматор выполнен как сумматор с запоми- .нанием переносов, при этом входы k-ro элемента И блока выделения млад;шего разряда ( 1.,..., к-1) соединены с прямым выходом f1 +n-ro разряда регистра множителя и инверсными выходами всех предыдущих разрядов регистра множителя, входы п-го элемента И блока выделения младшего разряда соединены с инверсными выходами всех разрядов регистра множителя, прямой выход первого разряда которого подключен к информационному входу первого разряда первого буферного регистра, выход k-ro элемента И блока выделения младшего разряда подключен к информационному входу (k+l)-ro разряда первого буферного регистра, выход каяадого разряда которого соединен со вторыми входами элементов И соответствующей § строки матрицы, выход первого элемента И первой строки матрицы соединен с информационным входом первого разряда второго буферного регистра, выход р-го элемента ИЛИ группы (В,..., 2n-3j соединен с информационным входом (К+1)-го разряда второго буферного регистра, инфорСО мационный вход

Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения асинхронного типа.5

Известно устройство для умножения, содержащее регистры множимого и множителя, накапливающий сумматор, матрицу элементов И, две группы элементов ИЛИ,, две группы элементов И и О группу элементов задержки СЗ.

Недо.статком известного устройства является низкое быстродействие.

Наиболее близким по технической сущности к изобретению является уст- 15 ройство для умножения, содержащее регистры множимого и множителя, матрицу элементов И, группу элементов ИЛИ, группу элементов И, накапливающий сумматор и блок выделения мпад- 20 шего разряда, причем выходы регистра множимого соединены с первыми входами элементов И соответствующих столбцов матрицы, выход j-ro элемента И -й строки матрицы 25 i l,...,h; j l,...,n; n - разрядность сомножителейU кроме первого элемента И первой строки матрицы и п-го элемента И ,п-й строки матрицы подключены к входу (i+j-2)-rd 30 элемента ИЛИ группы, выходы элементов ИЛИ группы подключены соответственно к входам разрядов с 2-го по (2л - 2)-и накапливающего сумматора, входы Г-го и ( 1)-го разрядов которого подключены соответственно к выходам первого элемента И первой строки матрицы и р-го элемента И п-й строки матрицы, входы блока вьщеления младшего разряда соеди о нены с инверсными выходами соответствующих разрядов регистра множителя,.

а выходы соединены с первыми входами соответствующих элементов И группь1, вторые входы которых соединены с прямыми выходами соответствуюцщх разрядов регистра, множителя, а третьи входы объединены и соединены с входами синхронизации регистра множителя и накапливающего сумматора и с входом синхронизации устройства, выходы элементов И группы соединены с вторыми входами элементов И соответствующей строки матрицы и с входами обнуления соответствующих разрядов регистра множителя 2.

Недостатком известного устройства является относительно низкое бысродействие, вызванное большой длительностью его такта работы (длительность такта определяется временем Прохождения информации через группу элементов И, матрицу элементов И, группу элементов ИЛИ и временем суммирования в накапливающем сумматоре со сквозным переносом).

Цель изобретения - повьшение быстродействия устройства за счет сокращения длительности такта работы.

Поставленная цель достигается тем, что в устройство для умножения содержащее регистры множимого и множителя, матрицу элементов И, группу элементов ИЛИ, накапливающий сумматор и блок выделения младшего разряда, причем выходы разрядов регистра множимого соединены с первыми входами элементов И соответствующих столбцов матрицы, выход j-го элемента И i-й строки матрицы (i l,,..,n;j 1,..., ; n- разрядность сомножителей), кроме первого элемента И первой строки матрицы и и-го элемента И строки матрицы, подключен к входу -2)-го элемента ИЛИ группы, введены два бу ферных регистра и блок управления, содержащий счетчик, два элемента И и элемент ИЛИ, блок выделения младшего разряда содержит « элементов И, а накапливающий сумматор выполнен как сз мматор с запоминанием переносов, при этом входы эле мента И блока выд.еления младшего разряда (k 1,..., п-1) соединены с прямым выходом (1 + 1)-го разряда регистра множителя и инверсными выходами всех предьщущих разрядов регистра множителя, входы и-го элемента И блока выделения младшего разряда соединены с инверсными выхо дами всех разрядов регистра множителя, прямой выход первого разряда которого подключен к информацион ному входу первого разряда первого буферного регистра, выход It-го эле мента И блока выделения младшего разряда подключен к информационному входу (1с + 1)-го разряда первого буферного регистра, выход каждого разряда которого соединен, с вторыми входами элементов И соответствующей строки матрицы, выход первого элемента И первой строки матрицы соединен с информационным входом пе вого разряда второго буферного регистра, выход -го элемента ИЛИ ,группы (Р t,..., 2ft-3 ) соединен с ;информационным.входом (8+})-го разряда второго буферного регистра, информационный вход (2п -1)-го разря да которого подключен к выходу п-г элемента И i-и строки матрицы, выхо разрядов второго буферного регистра подключены к входам соответствующих разрядов накапливающего сумматора. выход п-го элемента И блока выделе ния младшего разряда подключен к первому входу первого элемента И блока управления, второй вход которого соединен со входом синхронизации устройства и первым входом второго элемента И блока управления второй вход Которого соеданен с выходом элемента ИЛИ блока управления а выход - со входом синхронизации буферных регистров, накапливающего сумматора и регистра множителя, вход обнуления разрядов .которого соединены с информационными входа соответствующих разрядов первого буферного регистра, выход первого элемента И блока управления подключен к входу счетчика блока управления, прямой выход первого и инверсный выход второго разрядов которого.соединены с входами элемента ИЛИ, прямой выход второго разряда и выход переполнения второго разряда счетчика блока управления подключены соответственно к входу управления сквозным переносом накапливающего сумматора и выходу индикации окончания операции умножения устройства. На фиг. 1 приведена структурная схема устройства для случая, когда на фиг. 2 - функциональная схема блока выделения млада1его разряда; на фиг. 3 - функциональная схема блока управления; на . фиг. 4 - временная диаграмма работы устройства. Устройство содержит (фиг.1) регистры 1,2 соответственно множимого и множителя, первый буферный регистр 3, второй буферный регистр 4, накапливанмций сумматор реализованный в виде комбинационного сумматора 5 и регистра 6 результата с соответствуннцими связями, матрицу 7 элементов И 8, группу 9 элементов ИЛИ JO, блок 11 выделения мпадшего разряда, блок 12 управления, вход 13 синхронизации устройства и выход 14 индикации окончания операции умножения устройства. Выхода разрядов регистра 1 множимого соединены с первыми входами элементов И 8 соответствующих столбцов матрицы 7, а выходы разрядов первого буферного регистра 3 соединены с вторыми входами элементов И 8 соответствующих строк матрицы 7, выход j-го элемента И О 1-й строки матрицы 7 строки матри1у 1 (i 1,..., 4; j 1,..., 4), кроме первого элемента И 8 первой строки матрицы 7 и четвертого элемента И 8 четвертой строки матрицы 7, подключен к входу (f-t-j -2)-го элемента ИЛИ 10 группы 9, выход первого элемента И 8 первой строки матрищя 7 соединен с информационным входом первого разряда второго буерного регистра 4, выход -го элемента ИЛИ 10 группы 9 (,...,5) соединен с информационным входом (+ )-го разряда второго буферного регистра 4, информационный вход седьмого разряда которого подключей к выходу четвертого элемента И 8 четвертой строки, матрицы 7, выходы разрядов второго буферного регистра 4 подключены к входам соот ветствующих разрядов накапливающего сумматора, прямые и инверсные выходы разрядов регистра 2 множителя соединены с входами блока 11 выделения младшего разряда, выходы кото рого подключены к информационньш входам соответствующих разрядов пер вого буферного регистра 3 и к входа обнул 1шя соответствующих разрядов регистра 2 множителя, выход окончания выделения блока 11 выделения младшего разряда соединен с первым входом блока. 12 управления, второй вход которого соединен с входом 13 синхронизации устройства, первый выход блока 12 .управления подключен к входам синхронизации буферных регистров 3 и 4, накапливающего сум матора и регистра 2 множителя, второй выход блока 12 управления подключен к входу управления сквозным переносом накапливающего сумматора, а третий выход блока 12 управления подключен к выходу 14 индикации окончания операции умножения устройства. Все регистры устройства могут быть построены на двухтактных синхронных JV-триггерах, причем в каждом разряде регистра 6 результата накапливающего сумматора используется два таких триггера (один триггер предназначен для хранения разрядных сумм сумматора 5, а другой для запом тнания его же разрядных переносов ). Сумматор 5 выполнен комбинационным типа с запо шнанием разрядных переносов и с возможность их сквозной передачи на последнем щаге умножения путем подачи соответствующего сигнала на его управля щий вход. Блок 11 выделения младшего разр да предназначен для последовательного выделения единиц г-разрядног двоичного кода множителя, начиная с его младших разрядов, хранимого в регистре 2 множителя. Он содер-жит (фиг.2) П злементов И 15 н фу ционирует в.соответствии со следую щими логическими выражениями П1 , П2.,,-, i52V4 1 где П , П., П, П. - признаки выделения соответственно первого, второго, третьего и четвертого значащих разрядов регистра 2 множителя; П признак окончания выделения значащих разрядов регистра 2 множителя; ,у. - двоичные цифры множите-- . ля у , причем возрастание индексов при буквенных обозначениях принято iB направлении старших разрядов. Этот вариант построения блока 11 выделения младшего разряда обладает иск лючительно высоким быстродействием, особенно при малых значениях разрядности обрабатываемой в устройстве информации. При больших же значениях t из-за ограниченных возможностей логических элементов целесообразно в блоке 11 использовать принцип разбиения его на группы с последовательной либо параллельной передачей между группами признаков П окончания выделения значащих разрядов в группах. Это позволяет даже при .п 56 и существующей элементной базе обеспечить время выделения значащего разряда, не превышающее величину Зг; где f- задерж- ка сигнала на одном логическом элементе. Блок 12 управления содержит (фиг.3)первый элемент И 16, второй элемент И 17, элемент ИЛИ 18 и двухразрядный двоичный счетчик 19(разрядность счетчика может быть и другой), причем первый вход . блока 12 управления соединен с первым входом первого злемента И 16, второй вход которого соединен с вторым входом блока 12 управления и с первым входом второго элемента И 17, второй вход которого соединен с sbiходом элемента ИЛИ 18, а выход является первым выходом блока 12 управления, выход первого элемента И 16 подключен к входу счетчика 19, прямой выход первого и инверсный выход второго разрядов которого соединены с входами элемента ИЛИ 18, прямой выход второго разряда н выход переполнения второго разряда счетчика 12 являются соответственно вторым и третьим выходами блока 12 управления. Устройство работает следующим образом. 7 Пусть требуется умножить п- раз рядное множимое X на п- разрядный множитель 1010. В исходно состоянии в регистре 1 множимого хранится двоичньш код числа X без знака, в регистре 2 множителя - дво ичный код числа У без знака, буферные регистры 3,4, регистр 6 результата накапливающего сумматора и сче чик 19 блока 12 управления обнулены. В первом такте работы устройства на выходе блока 1I выделения младшего разряда формируется признак выделения второго значащего ра ряда регистра 2 множителя. Первый такт заканчивается с приходом на вход 13 синхронизации устройства первого синхроимпульса, по которому на выходе второго элемента И 17 блока 12 управления формируется упр ляннций сигнал с разрешения которого по признаку устанавливается в ноль второй разряд регистра 2 множителя и записывается единица во второй разряд первого буферного регистра 3. Во втором такте работы устройства на выходе блока 1 1. выделени младшего разряда формируется признак выделения четвертого значащего разряда регистра 2 множителя, и одновременно с этим под дейст вием потенциала логической единицы, записанной во втором разряде первого буферного.регистра 3, осуществля ется передача соответствующим.обра зом сдвинутого множимого с выходов элементов И 8 второй строки матрицы 7 через элементы ИЛИ 10 группы 9 на информационные входы второго буферного регистра 4, Второй такт заканчивается с приходом на вход .13 синхронизации второго синхроимпульcaj по которому на выходе второго элемента И 17 блока 12 управления формируется управляющий сигнал, с р решения которого осуществляется за- пись информации во второй буферный регистр 4 с его информационных входов, а также по признаку устанавливается в нуль четвертый разряд регистра 2 множителя и записывается единица в четвертый разряд первого буферного регистра 3 (вто рой разряд буферного регистра 3 обн ляется, так как его триггеры работают как В - триггеры). 3 В третьем такте работы устройства на выходе окончания выделения блока I1 выделения младшего разряда формируется признак П - 1, означающий, что закончено выделение значащих разрядов регистра 2 множителя , и одновременно с этим под действием потенциала логической единицы, записанной в четвертом разряде первого буферного регистра 3, осуществляется передача соответствую1чим образом сдвинутого множимого с выходов элементов И 8 четвертой строки матрицы 7 непосредственно и через элементы ИЛИ 10 группы 9 на информационные входы второго буферного регистра 4, и, кроме этого, в сумматоре 5 в режиме запоминания переносов выполняется суммирование содержимого второго буферного регистра 4 и регистра 6 результата { с0держимое регистра 6 результата в этом такте еще равно нулю ), после чего результат сумматора 5 в двухрядном коде поступает на информационные входы регистра 6 результата. Третий такт заканчивается с приходом на вход 13 синхронизации третьего синхроимпульса, по которому на выходе первого элемента И 16 блока I2 управления формируется сигнал, устанавливающий счетчик 19 блока 12 управления в единицу, а на выходе второго элемента И )7 блока 12 управления формируется управляющий сигнал, с разрешения которого производится запись информации во второй буфернБ1й регистр 4 и в регистр 6 результата с их информационных входов. В четвертом такте работы устройства в сумматоре 5 производится суммирование в режиме запоминания переносов содержимого второго буферного регистра 4 и регистра 6 результата, после чего получившийся на его выходах результат в двухрядном коде поступает на информационные входы регистра 6 результата. Такт заканчивается с приходом на вход 13 синхронизации четвертого синхроим- пульса, по которому на выходе второго элемента И 17 блока 12 управления образуется управлякиций сигнал. с разрешения которого осуществляется запись информации в регистр 6 результата с его информационных входов, а на выходе первого элемента И 16 блока 12 управления формируется сигнал, устанавливаняций счетчик через вход счета в состояние, равное двум. По этому состоянию счет ика на втором выходе блока 12 упра ления формируется управляющий сигнал, который настраивает в дальнейшем сумматор 5 на работу в режиме сквозного переноса. В пятом такте работы устройства в сумматоре 5 выполняется суммиро вание одержимого регистра 6 резуль тата в режиме со сквозным переносом. Пятый такт заканчивается с при ходом на вход 13 синхронизации пятого синхроимпульса, по которому только на выходе первого элемента И 16 блока 12 управления формируется сигнал, устанавливающий счетчик 19 через его вход счета в состояние, равное трем. В этом такте на выходе второго элемента И 17 блока 12 управления управляющий сигнал не образуется и потому запись информации во все регистры устройства не производится. .В шестом такте продолжается процесс суммирования со сквозным переносом содержимого регистра 6 резуль тата, который был начат еще в начале пятого такта. Здесь предполагается , что к концу шестого такта на выходах сумматора 5 формируется окончательный результат в однорядном коде, которьй поступает соответствующим образом на информационные входы регистра 6 результата. Шестой такт заканчивается с приходом на вход 13 синхронизации шестого синхроимпульса, по которому на выходе второго элемента И 17 блока 12 управления формируется управляющий сигнал, с разрешения которого производится запись окончательного результата в регистр 6 результата с его информационных входов, а на выходе первого элемента И 16 блока 12 управления образуется сигнал, который, поступая через вход счета счетчика 19 сбрасывает его в нуль и вызывает на выходе переполнения счетчика 19 единичш 1Й сигнал означающий, что закончено умножение в устройстве рассматриваемых чисел. На фиг. 4 приведена упрощенн 1я временная диаграмма работы устройства при перемножении в нем рассмотренных выше чисел. На ней.через СИ обозначены синхроимпульсы, поступающие на вход 13 синхронизации устройства; сигналы УС1, УС2 и УСЗ соответствуют управляющим сигналам соответственно на первом, втором и третьем выходах блока 12 управления; признак окончания выделения, форми уемый в блоке 1 I вьщеления младшего разряда; через С 16 обозначен сигнал, который образуется на выходе первого элемента И 16 блока 12 управления в процессе работы устройства. Среднее время умножения двух М- разрядных чисел в предлагаемом устройстве, в предположении что появление нуля и единицы во всех разрядах множителя равновероятно, составляет величину Т t 4 + ор-у т т где t - длительность одного такта рйботы предлагаемого устройства. Составляющая 4 -t в приведенном выражении вызвана использованием в устройстве конвейерного принципа обработки информации, а также потерей времени на сквозную передачу переносов в сумматоре в конце выполнения операции умножения (суммирование со сквозным переносом в сумматоре может быть выполнено в течение двух тактов работы устройства). Хотя в предпагаемом устройстве для умножения двух п-разрядных двоичных чисел и требуется выполнить на четыре такта больше, чем в устройстве-прототипе, однако оно имеет значительно более высокое быстродействие, так как длительность его такта работы сведена к минимуму (длительность такта работы предлагаемого устройства опреде- ляется временем записи информации в регистры 2,3,4,6 и временем задерщки информации либо на блоке 11 выде- ления младшего разряда, либо на матрице 7 элементов И 8 и на элементах ИЛИ 10 группы 9, либо на сумматоре 5 работающем в режиме запоминания переносов,).

Д.

е

-5

«

-

«

X

./7

й/г.2

fez.J

си

yet

yet

УСЗ

с

г

„e-S-ed-. такт,

л

rLJl-TLJl