Устройство для умножения двух @ -разрядных чисел Советский патент 1988 года по МПК G06F7/52 

/f .S JS JS

l/fl i/g j,

FHHr-4

СЛ

vi

rtOiV,

rt

CO

x

СЛ

oo

Изобретение относится к области вычислительной техники и может быть использовано в быстродействующих устройствах цифровой обработки сигналов асинхронного типа. Цель изобрете- ния - повышение быстродействия Для этого в устройство для умножения, содержащее матрицу из элементов И 1, блок 2 элементов ШШ, регистр 3 мно- ж1-1теля, регистр 4 множимого, накапливающий сумматор 5, блок 6 последовательного опроса значащих разрядов сомножителя, блок 10 сравнешш кодов, блок 11 ситскроршзации, элементы И 12, 13 и элемент ИЛИ 14, введены блок 7 последовательного опроса значащих разрядов сомножителя и входные коммутаторы 8, 9 с соответствующими cвязя я : о 6 ил „

V /# / //«t/

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

асинхронного типа для получения произведения двух двоичных чисел, пред- ставленщ ш параллельным кодом „

изобретения является повышение быстродействия

На фиг о 1 изображена схема устрой ства для умнолсения двух п-разрядных чисетт (для п 4)| на фиг о 2 схема первого (второго) блока последовательного опроса значащих разрядов сомнояситепя на фиг,, 3 - схема первого (второго) входного коммутатора| на фиг о 4 - схема блока сравнения кодов на фиг о 5 - структз/рная схема блока синхрошгзац ш| на фиг б -

временные диаграммы управляюугих сит- налов блока склх1эонизации (а - на входе блока синхронизагщг-ц б, в, rj, д - соответственно на первом, втором, третьем и четвертом выходах блока синхронизации5 е на выходе Конец устройствао

Устройство для умнолсения двух гт-разрядных чисел (фиг о 1) содержит матрицу из п2 элементов И 1, (2п-3)-- разрядньй блок 2 элементов ИЛИ, п разряднь й регистр 3 множителяj п-разряднья регистр 4 множимого, :(2п-1)-разрядный накагшивакщий сумматор 5э первый блок 6 последовательного опроса значащих разрядов сомножителя, второй блок 7 последовательного опроса значащих разрядов со- мноядателя, первьй входной коммутатор 8, второй входной коммутатор 9 блок 10 сравнения кодов, блок 11 синхронизации, первьй элемент И 12, второй

Блок 10 сравнения кодов (с|щг, содержит первую группу из п элем тов И 26, первую группу из п три ров 27; вторую группу из ()-г элемента И 28, схему 29 сравнени вторую группу из триггеров 30. т группу из (п-1)-го элемента И 31

45

50

элемент И 13;, элемент ИЛИ 145 вход 15 четвертую группу из п элементов

первого сомножителя устройства, вход

16 второго сомножителя устройства,

вход 17 устройства9 выход 18 произве;дения устройства и выход 19 Конец

устройства

Первьй (второй) блок 6(7) последовательного опроса (фиг о 2) значащих разрядов сомножителя содержит первую группу из п элементов И 265 вторую группу из п элементов И 21, rp-jmny из элементов ИЛИ 22 и группу из п элементов 23 задержки, причем первые входы элементов И 20 и 21 групп являются соответственно первой и второй группами информационных входов блока 6(7). выходы элементов И 20

55

И 32р причем первые входы элемен ТЛ 26 и 32 групп соответственно о зуют первую и вторую группы инфо ционных входов блока 10, выходам Меньше-т авно и Больше которо являются соответственно первьй и рой выходы схемы 29 сравнения, в рые входы элементов И 26 и 32 гр соединены между собой и являются рым управляющим входом блока 10, ходы элементов И 26 к 32 групп с нены соответственно с асинхронны входами установки в единичное со яние триггеров 27 и 30 групп, вх синхронизации которых соединены ду собой и являются третьим упра

5 0

5

О

5

0

являются выходами группы блока 6(7) и соединены через соответствующие элементы 23 задержки группы с первыми входами соответствующих элементов ИЛИ 22 группы, вторые входы которых соединены с выходами соответствующих элементов И 21 группы, вторые входы которых объединены с вторыми входами соответствующ11; элементов И 20 группы и подключены к входам предыдущих элементов ИЛИ 22 группы, управлякш151е вход и выход блока 6(7) соединены соответственно с вторым входом младшего элемента И 20 группы и с вькодом старшего элемента ИЛИ 22 группы.

Первый (второй) входной коммутатор 8(9) (фиг о 3) содержит группу из п элементов И 24 и группу из п элементов ШШ 25, npi-гчем первые входы элементов Ш1И 25 группы образуют соответственно первую группу информа- тдаоннык входов коммутатора 8(9)з информационными выходами которого являются соответственно выходы элементов ИЛИ 25 группы, вторые входы элементов ШШ 25 которой соединены соответственно с выходаГ Ш элементов И 24 группы, вторые входы КОТОРЬК образуют соответственно вторую гр:лтпу ин- формационньпс входов комгугутатора 8(9) первые входы элементов И 24 группы соединены между собой и являются управляющим входом коммутатора 8(9)

Блок 10 сравнения кодов (с|щг,4) содержит первую группу из п элементов И 26, первую группу из п триггеров 27; вторую группу из ()-го элемента И 28, схему 29 сравнения вторую группу из триггеров 30. третью группу из (п-1)-го элемента И 31

И 32р причем первые входы элементов ТЛ 26 и 32 групп соответственно образуют первую и вторую группы информационных входов блока 10, выходами Меньше-т авно и Больше которого являются соответственно первьй и второй выходы схемы 29 сравнения, вторые входы элементов И 26 и 32 групп соединены между собой и являются вторым управляющим входом блока 10, выходы элементов И 26 к 32 групп нены соответственно с асинхронными входами установки в единичное состояние триггеров 27 и 30 групп, входы синхронизации которых соединены между собой и являются третьим управляЮ1ЩМ входом блока 10, первым управляющим входом которого являются соединенные меяоду собой асинхронные входы установки в нулевое состояние триггеров 27 и 30 групп, синхронные входы установки в нулевое состояние текущих триггеров 27 и 30 и синхронные входы установки в единичное состояние последующих триггеров 27 и

30групп, выходы, соответствующие каждой паре триггеров, элементов И 28 и 29 групп соединены соответственно между собой, первые входы элементов И 28 и 31 групп, соответствующие каждой паре триггеров, соединены соответственно с прямыми выходами текущих триггеров 27 и 30 групп, инверсные выходы последующих тригге- .ров которых соединены соответственно .с вторыми входами элементов И 28 и

31групп, соответствующие каждой паре триггеров, прямые выходы триггеров 28 и 31 групп-соединены соответственно с первой и второй группами информационных входов схемы 29 сравнения

Блок 11 синхронизации содержит формирователь 33 импульса, элемент НЕ 34, группу из (п+1) элементов 35 задержки и элемент ИЛИ 36, причем вход блока 11 соединен с входом формирователя 33 импульса, выход которого соединен с входами последовательно соединенных элементов 33 задержки, выход формирователя 33 импульса- соединен с входом элемента НЕ 34, выход которого является первым выходом блока 11, вторым выходом которого является выход первого элемента 35 задержки группы, выходы с второго элемента 35 задержки по п-й элемент 35 задержки которой соединены соответственно с входами элемента ИЛИ 36, выход которого является третьим выходом блока 11, четвертым выходом которого является выход последнего элемента 35 задержки группы

Работа устройства для умножения двух п-разрядных чисел заключается -в следующем

Операнды сомножителей, поступающие по входам 15 и 16 первого сомножителя и второго сомножителя устрой-

10

25

ся преобразование кодов операндов из позиционной двоичной системы счисления в код унитарного счисления, срав нение этих кодов и вьработка соответ ствующих сигналов Больше или Мень ше-равно, Если количество единиц в коде первого сомножителя, поступающего на вторую группу информационных входов блока 10 и на информацион ные входы регистра 3 множителя, мень ше или равно количеству единиц в коде второго сомножитепя, поступающего на первую группу информационных вхо15 дов блока 10 и на информационные вхо ды регистра 4 многа мого, то на выходе Меньше-равно блока 10 формируется сигнал, Даниьй сигнал, поступая на управля ощий вход второго входного

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

Кроме того, этот сигнал, поступая на первый вход первого двухвходового элемента И 12, обеспечивает прохождение импульса с четвертого выхода блока 11 синхронизации на управля- кщий вход первого блока 6 последовательного опроса значащих разрядов сомножителя Этим самым обеспечивает ся последовательньй, начиная с младш

,, го разряда, опрос значащих разрядов первого .сомножителя, хранимого в регистре 3 ffloжитeля. Если триггер младшего разряда регистра 3 множителя находится в единичном состоянии, то импульс, поступакнций на управляющий вход первого блока 6 последовательного опроса значащих разрядов сомножителя появляется на информационном выходе младшего разряда блока -6о Под действием этого импульса, открывающего по вторым входам элемен ты И первой строки матрицы, формируется первое частичное произведение В этом случае, когда блок 10 вьраба- тывает управляюащй сигнал Меньшеrt

30

40

45

50

равно первое и еледукщие частичные произведения представляют собой соответственно несдвинутЫй и сдвинутый на требуемое число разрядов влево ства, одновременно записьшаются соот- 55 °Д второго сомножителя, хранящийся ветственно в регистры 3 и 4 ffloжитe- в регистре 4 множимого Сформирован- ля и множимого, а также в блок 10 ное таким образом первое частичное сравнения кодов После записи операн- произведение через элементы ИЛИ бло- дов в блок 10 в последнем производит- ка 2 элементов ИЛИ поступает на вхо0

5

ся преобразование кодов операндов из позиционной двоичной системы счисления в код унитарного счисления, сравнение этих кодов и вьработка соответствующих сигналов Больше или Меньше-равно, Если количество единиц в коде первого сомножителя, поступающего на вторую группу информационных входов блока 10 и на информационные входы регистра 3 множителя, меньше или равно количеству единиц в коде второго сомножитепя, поступающего на первую группу информационных вхо5 дов блока 10 и на информационные входы регистра 4 многа мого, то на выходе Меньше-равно блока 10 формируется сигнал, Даниьй сигнал, поступая на управля ощий вход второго входного

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

Кроме того, этот сигнал, поступая на первый вход первого двухвходового элемента И 12, обеспечивает прохождение импульса с четвертого выхода блока 11 синхронизации на управля- кщий вход первого блока 6 последовательного опроса значащих разрядов сомножителя Этим самым обеспечивается последовательньй, начиная с младше го разряда, опрос значащих разрядов первого .сомножителя, хранимого в регистре 3 ffloжитeля. Если триггер младшего разряда регистра 3 множителя находится в единичном состоянии, то импульс, поступакнций на управляющий вход первого блока 6 последовательного опроса значащих разрядов сомножителя появляется на информационном выходе младшего разряда блока -6о Под действием этого импульса, открывающего по вторым входам элементы И первой строки матрицы, формируется первое частичное произведение. В этом случае, когда блок 10 вьраба- тывает управляюащй сигнал Меньшеrt

0

0

5

0

равно первое и еледукщие частичные произведения представляют собой соответственно несдвинутЫй и сдвинутый на требуемое число разрядов влево 5 °Д второго сомножителя, хранящийся в регистре 4 множимого Сформирован- ное таким образом первое частичное произведение через элементы ИЛИ бло- ка 2 элементов ИЛИ поступает на входы накапливающего сумматора 5 для накопления соответствующей частичных произведенийо После задержки на один такт работы устройства в блоке 6 последовательного опроса значащих разрядов сомножителя импуль производит опрос следукщего, более старшего, разряда регистра 3 множителя .Плительность первого такта работы устройства так же, как и всех следуюищх, определяется с учетом времени выполнения операции суммирования в накапливакщем сумматоре 5„ Если триггер маадшего или любого другого разряда регистра 3 множителя находится в нулевом состоянии, то- и myльc без задержки на один такт работы устройства в первом блоке б последовательного опроса значащих разрядов сомнохсителей производит опрос следующего более старшего разря да регистра 3 множителя о Далее таким же образом, последовательно один за другим производится анализ состо™ Я1ШЯ остальнь Х, более старших разрядов регистра 3 мнолсителя, и устройство работает аналогично Появление имт1ульса на выходе 19 устройства Конец J поступающего через элемент ШЕ- 14 с управляющего выхода блока 6 означаетJ что процесс умножения .зако чен и в нака}1ливающем сумматоре 5 сформировалось соответствующее про- изведениВо

Если количество единиц в коде первого сомножителя, поступающего на вторую группу информатдионных входов блока 10 и на информационные входы регистра 3 множителя, больше количества единиц, чем в коде второго сомножителя, поступающего на первую группу информационных входов блока 10 и на информационные входы регистра 4 множимого5 то на выходе Больше блока 10 формируется сигнал. Данный ,сигнал, поступая на управлягаций вход первого входного коммутатора 8, обеспечивает коммутацию прямых информационных выходов .регистра 3 множителя, через первьй входной коммутатор 8 с соответствующими строками матрицы элементов И I l«

Кроме этого, этот сигнал, поступая на первьй вход второго элемента И 13, обеспечивает прохождение импульса с четвертого выхода блока 11 синхронизации на управлянядий вход

95816

второго блока 7 последовательного опроса значаищх разрядов сомножителя о Этим самым обеспечивается последова- тельньй, начиная с младщего разряда, опрос значащих разрядов второго сомножителя, хранимого в регистре 4 множимого о Если триггер младшего раз- ,ряда регистра 4 множимого находится 10 в единичном состоянии, то и myльC5

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

15 младщего разряда блока 1, Под действием этого управляющего импульса, открывающего по первым входам логические элементы И первой диагонали матрицы элементов И 1, формируется пер20 вое частичное произведение. В этом случае, когда блок 10 вырабатьшает сигнал на выходе Больше первое и следующие частичные произведения представляют собой соответственно несдви- нутьм и сдвинутые на требуемое число разрядов влево код первого со1 шоясите ля, хранящегося в регистре 3 мнояси- теля о Сформг срованные тар;им образом первое частичное произведение, как

30 и при выработке блоком 10 сигнала на выходе Меньше-равно, через элементы ИЛИ блока 2 элементов ИЛИ поступает на входы накапливающего сумматора 5 для накопления соответствуюисий

35 суммы частичных произведенийс, Далее устройство работает, как и при вьра- ботке блоком 10 сигнала на выходе Меньше-равно j, однако при этом анализируются более cTapiime ра зряды ре-

40 гистра 4 множимого о

Работа первого 6 (второго 7) блока последовательного опроса значащих разрядов сомнолмтеля (фиг 2) заключается в следзтащемо

25

Импульс опроса значащих разрядов сомноясителя, формируемый блоком 11 синхронизации через первьй 12 (второй 13) элемент И, поступает на входы первых элементов И 20 и 22 групп элементов И Если триггер младшего разряда регистра 3 множителя (множимого 4) находится в единичном состоянии, то импульс появляется на выходе первого элемента И 20 и разрешает суммирование первого частичного произведения на накапливающем сумматоре 5 Кроме этого, данньй импульс, задержанньй на один такт в

7

первом элементе 23 задержки группы через первый элемент liJIH 22 группы поступает в следующий разряд множителя (множимого)о Поскольку триггер младшего разряда множителя (множимого) находится в единш ном состоянии, первый элемент И 21 группы не пропускает импульс на вход первого элемента И1И 22 группЫо Если триггер младшего разряда 3 множителя (множимо - го 4) находится в нулевом состоянии, то импульс через первый элемент И 21 группы и элемент ИЛИ 22 группы посту пает в следующий разряд, минуя эле менты задерлжи на такт работы устройства е В остальных разрядах первьй (второй) блок 6(7) последовательного опроса значащих разрядов сомнолштеля работает аналогично о

Работа блока 10 (фиг, 4) заключается в следующемо

Операнды сомножителей, доступа- юяще на первую и вторую группы инфор- мапионных входов блока 10, под действием импульса Прием сомно кителей формируемого блоком 11 синхро1ШзациИ

записываются в триггеры 27 и 30 груп- д вом выходе блока 11 синхронизации

пЫо Перед записью информации триггеры 27 и 30 групп и myльcoм Установка в ноль, форг-шруемого блоком 11 синхронизации, переводятся в нулевое состояние Связи между элементами И 28 группы и триггерами 27 группы, а также между элементами И 31 группы и тpиггepa iи 30 группы под действием импульсов Сдвиг кодов сомножителя, формируемого блоком 11 синхронизации обеспечивают преобразование кодов, операндов из позиционной двоичной системы счисления в код унитарного счисления, у которого все единицы располагаются рядом, начиная со старшего разряда Это происходит следующим образом. Если i+1-й-триггер 27, например, находится в нулевом состоянии, а триггер 27 - в единтгном состоянии, то i-й элемент И 28 открывается в единичный сигнал с его выхода устанавливает i+1-й триггер 27 в единичное, а i-й триггер 27 в нулевое состоя1шео Таким образом, за

(п-1) импульсов Сдвиг кодов СОМНО ЖИ

телей устанавливается такое состояние триггеров 27, при котором все единицы кода операнда находятся в старших разрядах, а нули кода

15

39581

в мпадших разрядах о Аналогичные преобразования с кодом второго операнда выполняются в группе триггеров 30„ Далее преобразованные коды сомножителей поступают на схему 29 сравнения Если кал1тчество единиц в коде первого сомножителя меньше или равно количеству единиц в коде второго со- 10 шожителя, то на выходе Меньше-равно блока 10 формируется сигнал о В противном случае на выходе Боль5

5

0

ше блока 10 формируется сигнал. Для организации синхронной работы отдельных блоков в устройстве умноже шя используется блок 11 синхронизации (фиг „ 5), Работа блока 11 синхронизации начинается с поступлением на его управляющий вход по входу Пуск 17 устройства сигнала (фиг. 6а),

Под действием этого сигнала блок 11 синхронизации фор ирует следз ющую последовательность управляющих импульсов;

- упраапяющий иьтульс Установка в ноль триггеров блока 10 и накап- .ливающего сумматора 5, данный управляющий импульс вырабатывается на пер5

0

g

множителей

5

0

(фиг о 66);

-управляющий импульс Прием сов регистры множителя 3 и множимого 4, а также в Яблока 10, данньй управляющий импульс вырабатывается на втором выходе блока 11 синхронизации фиг, 6в);

-управляюпще импульсы Сдвиг кодов сомножителей в триггерах блока 10, данные управляющие импульсы вьграбатываются на третьем выходе блока 11 синхронизапди для случая

п 4 (фиг о 6г);

-управляющий импульс Опрос значащих разрядов сомножителей в первом или втором блоке 6 и 7 последовательного опроса значащих разрядов сомножителей, данный импульс вырабатывается на четвертом выходе блока 11 синхронизации (фиг„ 6д),

Кроме перечисленных импульсов, на фиг, бе изображена временная диаграмма, которая отображает импульс, формируемьй на выходе 19 устройства о

Формула изобретения

Устройство для умножения двух п-разрядных чисел, содержащее матри цу из п элементов И, (2п-3)-разряд-соединены с вькодами соответствующих

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

g накапливающего сумматора являются выходом произведения устройства, о т- личающееся тем, что, с целью повышения быстродействия, оно содержит второй блок последовательно- 10 го опроса значапщх разрядов сомножителя, первьй и второй входные коммутаторы, причем выходы группы первого блока последовательного опроса значащих разрядов сомножителя и прямые вы15 ходы разрядов п-разрядного регистра множителя соединены соответственно с информационными входами первой и второй групп первого входного коммутатора, выходы разрядов которого сорядньк регистров множителя и множимо- 20 единены с входами элементов И соотго, первая и вторая группы информационных входов блока сравнения кодов соединены соответственно с входами второго и первого сомножителей устройства, вход Пуск которого соединен с входом запуска блока синхронизации, первый выход которого соединен с входом обнуления накапливающего сумматора и с первым.управляющим входом блока сравнения кодов, выходы Меньше-равно и Больше которого соединены соотБвтственно с первыми входами первого и второго элементов И, второй выход блока синхронизации соединен с вторым управлякищм входом блока сравнения кодов и с входами разрешения приема п-разрядных регистров множителя и множимого, третий вьг- ход блока синхронизации соединен с

третьим управляющим входом блока срав-40 с первыг-i входом элемента ИЛИ, выход нения кодов, четвертьй выход блокаи второй вход которого соединены со-

синхронизации соединен с вторыми входами первого и второго элементов И, выходы разрядов с второго по (2п-2)-й Матрицы из п элементов И соединены с соответствующими входами (2п-3)-раз рядного блока элементов ИЛИ, выходы которого соединены с соответствующими входами разрядов (2п-1)-разрядного накапливающего сумматора, входы пер- вого и (2п-1)-го разрядов которого

разрядов матрицы из п элементов И, выходы разрядов (2п-1)-разрядного

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

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

0

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

Фи8.3

ДЛ

g

I

-Эа