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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

tlgl SU (111 3 4 (512 4 G 06 F 7/52

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4240211/24--24 (22) 05.05.87 (46) 23,11.88, Вюл. № 43 (72) A.Ì. Романов и В.В. Джус (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ -1103667 кл. G 06 Р 7/52, 1982.

Авторское свидетельство СССР № 991418, кл. G 06 Р 7/52, 1981. (54) УСТРОЙСТВО ДЛЯ УМНОЖВНИЯ ДВУХ

n""РАЗРЯДНЫХ ЧИСЕЛ (57) Изобретение относится к области вычислительной техники и может быть использовано в быстродействующих устройствах цифровой обработки сигналов асинхронного типа. Цель изобретения — повышение быстродействия. Для этого в устройство для умножения, содержащее матрицу иэ элементов И 1, блок 2 элементов ИЛИ, регистр 3 множителя, регистр 4 множимого, накапливающий сумматор 5, блок 6 последовательного опроса значащих разрядов сомножителя, блок 10 сравнения кодов, блок 11 синхронизации, элементы И 12, 13 и элемент ИЛИ 14, введены блок 7 последовательного опроса значащих разрядов сомножителя и входные коммутаторы 8, 9 с соответствующими связями . 6 ил.

1439581

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

Целью изобретения является повышение быстродействия. 10

На фиг. 1 изображена схема устройства для умножения двух и-разрядных чисел (длл а =-. 4); на фиг. 2 — схема первого (второго) блока последовательного опроса значащих разрядов сомножителя. на фиг, 3 - схема первого (второго) входного коммутатора; на фиг. 4 - схема блока сравнения кодов; на фиг. 5 — структурная схема блока синхронизации; на фиг, 6 — 20 временные диаграммы управляющих сигналов блока синхронизации (а — на входе блока синхронизации, б, в, г,, ц - соответственно на первом, втором, третьем и четвертом выходах 25 блока синхронизации, е — на выходе

"Конец" устройства.

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

10 сравнения кодов, блок 11 синхронизации, первый элемент И 12, второй элемент И 13, элемент ИЛИ 14, вход 15 первого сомножителя устройства, вход

i 6 второго сомножителя устройства, вход 17 устройства, выход 18 произведения устройства и выход 19 "Конец" устройства.

Первый (второй) блок 6(7) последовательного опроса (фиг. 2) значащих

S0 разрядов сомножителя содержит первук> группу из и элементов И 20, вторую группу из и элементов И 21, группу из элементов ИЛИ 22 и группу из и элементов 23 задержки, причем первые входы элементов И 20 и 21 групп явллются соответственно первой и второй группами информационных входов блока 6(7), выходы элементов И 20 являются выходами группы блока 6(7) и соединены через соответствующие элементы 23 задержки группы с первыми входами соответствуюищх элементов ИЛИ 22 группы, вторые входы которых соединены с выходами соответствующих элементов И 21 группы, вторые входы которых объединены с вторыми входами соответствующих элементов И 20 группы и подключены к входам предыдущих элементов ИЛИ 22 группы, управляющие вход и выход блока

6(7) соединены соответственно с вторым входом младшего элемента И 20 группы и с выходом старшего элемента

ИЛИ 22 группы.

Г!ервый (второй) входной коммута— тор 8(9) (фиг. 3) содержит группу из и элементов И 24 и группу из п элементов ИЛИ 25, причем первые вхоpbE элементов ИЛИ 25 группы образукт соответственно пер y;o группу- информационных входов коммутатора 8(9), информационными выходами которого являются соответственно выходы элементов ИЛИ 25 группы вторые входы элементов ИЛИ 25 которой соедине.;.ы соот-. ветственно с выхоцами эле ентав И 24 группы вторые входы которых образуют соответственно вторую группу информационньм входов коммутатора 8(9), первые вхоцы элементов И 24 группы соединены межцу собой и являются управляющим входом ко мутатора 8(9).

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

И 32, причем первые входы элементов

И 26 и 32 групп соответственно образуют первую и вторую группы информационных входов блока 10, выходами

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

30 групп, выходы, соответствующие каждой паре триггеров, элементов И

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

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

Блок 11 синхронизации содержит формирователь 33 импульса, элемент

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

НЕ 34, выход которого является первым выходом блока l1 вторым выходом которого является выход первого элемента 35 задержки группы, выходы с второго элемента 35 задержки по и-й элемент 35 задержки которой соединены соответственно с входами элемента ИЛИ 36, выход которого является третьим выходом блока 11, четвертым выходом которого является выход последнего элемента 35 задержки группы.

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

-в следующем.

Операнды сомножителей, поступамцие по входам 15 и 16 первого сомножителя и второго сомножителя устройства, одновременно записываются соответственно в регистры 3 и 4 множителя и множимого, а также в блок 10 сравнения кодов. После записи операндов в блок 10 в последнем производит39581

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

1 роме того, этот сигнал, поступая на первый вход первого двухвходового элемента И l 2 обеспечивает прохождение импульса с четвертого выхода блока 11 синхронизации на управляющий вход первого блока 6 последовательного опроса значащих разрядов сомножителя. Этим самым обеспечивается последовательный, начиная с младшег о разряда, опрос значащих р а зряд ов первого сомножителя, хранимого в регистре 3 множителя. Если триггер младшего разряда регистра 3 множителя находится в единичном состоянии, то импульс, поступающий на управляющий вход первого блока 6 последовательного опроса значащих разрядов сомножителя появляется на информационном выходе младшего разряда блока б. Под действием этого импульса, открывающего по вторым входам элементы И первой строки матрицы, формируется первое частичное произведение.

В этом случае, когда блок 10 вырабатывает управляющий сигнал "Меньшеравно" первое и следующие. частичные произведения прецставляют собой соответственно несдвинутый и сдвинутый на требуемое число разрядов влево код второго сомножителя, хранящийся в регистре 4 множимого. Сформированное таким образом первое частичное произведение через элементы ИЛИ блока 2 элементов ИЛИ поступает на вхо1439581

35

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

КрОме этО1 О этот сигнал пОсту"" пая на первый вход второго элемента

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

L... частичных произведений. После задержки на адин такт работы устройства в блоке 6 последовательнога опроса значащих разрядов сомножителя импульс производит опрос следующего, более старшего, разряда регистра 3 множителя. Длительность первого такта 10 рабаты устройства так же, как и всех следующих, определяется с учетом времени выполнения операции суммирования в накапливающем сумматоре 5. Если триггер мпадшего или любого дру- 15 гого разряда регистра 3 множителя находится в нулевом состоянии, таимпульс без задержки на один такт рабаты устройства в первом блоке 6 последовательного спроса значащих 20 разрядов сомножителей праизводит опрос следующего более старшего разряда регистра 3 множителя, Далее таким же образом, последовательна один за другим,. производится анализ состояния остальньх, более старших разрядов регистра 3 множителя, и устройство работает аналогично. Появление импульса па выходе 19 устройства

"Ко1 ец". nocтупающега через элемент 30

ИЗБ! 14 с управляющего выхода блока 6 означает, чта процесс умножения закончен и в накапливающем сумматоре 5 сформировалось соответствующее npovsaeqezz. второго блока 7 последовательного опроса значащих разрядов сомножителя.

Этим самым обеспечивается последовательный, начиная с младшего разряда, опрос значащих разрядов второго сомножителя, хранимого в регистре 4 множимого. Если триггер мпадшего раз,ряда регистра 4 множимаго находится в единичном состоянии, та импульс, поступающий на управляющий вход второго блока 7 последовательного апроса значащих разрядов сомножителя появляется на информационном выходе мпадшего разряда блока 7. Под действием этого управляющего импульса, открывающего по первым входам логические элементы И первой диагонали матрицы элементов И 1, формируется первое частичное произведение, 3 этом случае, когда блок "0 вырабатывает сигнал на выходе "Больше" первое и следующие частичные произведения представляют собой соответственно несдвинутый и сдвинутые на требуемое число разрядов влево код первого сомножителя, хранящегося в регистре 3 множителя. Сформираваннь|е таким Образам первое частичное произведение„ как и при выработке блоком 10 сигнала на выходе Меньше-равно", через элементы ИИ блока. 2 элементов ИЛИ поступает на входы накапливающего сумматора 5 для накопления саатветствуюший суммы частичных произведений. Далее устройство работает, как и при выработке блоком 10 сигнала на выходе

"Меньше-равнои, однако при этом анализируются более старшие разряды регистра 4 мналжмого.

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

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

7 1439

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

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

S81 8 в младших разрядах, Аналогичные преобразования с кодом второго операнда выполняются в группе триггеров 30.

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

В противном случае на выходе "Больше" блока 10 формируется сигнал, Для организации синхронной работы отдельных блоков в устройстве умножения используется блок 11 синхронизации (фиг. 3) . Работа блока 11 синхронизации начинается с поступлением на

его управляющий вход по входу "Пуск" l7 устройства сигнала (фиг. 6а) .

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

Операнды сомножи галей, поступающие на первую и вторую группы информационных входов блока 10, под действием импульса "Прием сомножителей формируемого блоком 11 синхронизации. записываются в триггеры 27 и 30 группы. Перед записью информации триггеры 27 и 30 групп импульсом "Установка в ноль", формируемого блоком 11 синхронизации, переводятся в нулевое состояние. Связи между элементами

И 28 группы и триггерами 27 группы, а также между элементами И 31 группы и триггерами 30 группы под действием импульсов Сдвиг кодов сомножителя", формируемого блоком 11 синхронизации, обеспечивают преобразование кодов операндов из позиционной двоичной системы счисления в код унитарного счисления, у которого все единицы располагаются рядом, начиная со старmего разряда. Это происходит следующим образом. Если i+1-й- триггер 27, например, находится в нулевом состоянии, а i-й триггер 27 — в единичном состоянии, то i-и элемент И 28 открывается в единичный сигнал с его выхода устанавливает i+1-й триггер 27 в единичное, а i-й триггер 27 в нулевое состояние. Таким образом, за (и-1) импульсов "Сдвиг кодов сомножителей" устанавливается такое состояние триггеров 27, при котором все единицы кода операнда находятся в старших разрядах, а нули кода—

25 управляющий импульс "Установка в ноль" триггеров блока 10 и накапливающего сумматора 5, данный управляющий импульс вырабатывается на первом выходе блока 11 синхронизации (фиг. 6б) — управляющий импульс Прием сомножителей" в регистры множителя 3 и множимого 4, а также в триггеры блока 10, данный управляющий импульс вы35 рабатывается на втором выходе блока

11 синхронизации фиг, бв); — управляющие импульсы Сдвиг кодов сомножителей" в триггерах бло40 ка 10, данные управляющие импульсы вырабатываются на третьем выходе блока 1 l синхронизации для случая

n = 4 (фиг. 6г); — управляющий импульс "Orrpoc зна45 чащих разрядов сомножителей" в первом или втором блоке 6 и 7 последовательного опроса значащих разрядов сомножителей, данный импульс вырабатывается на четвертом выходе блока 11 синхронизации (фиг. 6д), Кроме перечисленных импульсов, на фиг, бе изображена временная диаграмма, которая отображает импульс, формируемый на выходе 19 устройства.

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

Устройство для умножения двух и-разрядных чисел, содержащее матри9 1439 цу из п элементов И, (2п-3)-разрядный блок элементов ИЛИ, и-разрядный регистр множителя, и-разрядный регистр множимого, (2n-1)-разрядный накапливающий сумматор, первый блок последовательного опроса значащих разрядов сомножителя, элемент ИЛИ, первый и второй элементы И, блок сравнения кодов и блок синхронизации, 10 причем прямые и инверсные выходы разрядов и-разрядного регистра множителя соединены соответственно с информационными входами первой и второй групп первого блока последова- t5 тельного опроса значащих разрядов сомножителя, входы первого и второго сомножителей устройства соединены соответственно с входами разрядов и-разрядных регистров множителя и множимо- 20

ro, первая и вторая группы информационных входов блока сравнения кодов соединены соответственно с входами второго и первого сомножителей устройства, вход Пуск которого соединен с входом запуска блока синхронизации, первый выход которого соединен с входом обнуления накапливающего сумматора и с первым управляющим входом блока сравнения кодов, выхо- 30 ды "Меньше-равно" и "Больше" которого соединены соответственно с первыми

) входами первого и второго элементов И, второй выход блока синхронизации соединен с вторым управляющим входом З5 блока сравнения кодов и с входами разрешения приема п-разрядных регистров множителя и множимого, третий выход блока синхронизации соединен с третьим управляющим входом блока срав-40 нения кодов, четвертый выход блока синхронизации соединен с вторыми входами первого и второго элементов И„ выходы разрядов с второго по (2п-2) -й матрицы из nÐ элементов И соединены 45 с соответствующими входами (2n-3)-разрядного блока элементов ИЛИ, выходы которого соединены с соответствующими входами разрядов (2п-1)-разрядного накапливающего сумматора, входы пер- 50 вого и (2п-1)-го разрядов которого

581

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

1439581

1439581

Составитель А. Клюев

Техред M.Ходанич Корр ект ор H ° Kop on ь

Редактор A. Ворович

Заказ 6078/48 Тираж 704 Подпис ное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Гаушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4