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

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

<>981996

Союз Сюеетскни

Социалистическмк

Республик (6t) Дополнительное к авт. свид-ву(22) Заявлено 18.07. 80 (21) Ю61300/18-24 с присоединением заявки ¹(23) ПриоритетОпубликовамо 15.1282.Бюллетень М146

И1) И. Кл.

G 06 F 7/52

Государственный комитет

СССР ио делам изобретений н открытий

f33 УДЙ 681.325 (088. 8) Дата опубликования описаиия15. 12. 82 (72) Ав ор

Ю И Нежевенко

ЧИСЕЛ

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

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

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

Быстродействие этого устройства также невелико.

Наиболее близким к изобретению яв» 25 ляется устройство для умножения двоичных чисел, содержащее регистры множимого и множителя,пераллельныя сумма- тор, :лок анализа разрядов, счетчик, дешифратор, два блока формиро- ЗО

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

И, вторые входы которых подключены соответственно к нулевому и единичному выходам второго триггера, а выходы соединены соответственно с управляющими входами первого и второго блоков формирования импульсов считывания, информационные входы которых соединены с соответствующими выходами регистра множителя, а выходы соединены с входами. блока сдвига и с нулевым вхоцом первого триггера, ецинич» ный вход которого соединен с шиной запуска устройства, с управляющим входом блока анализа разрядов и вхоjqoM элемента задержки, выход которого подключен к первым входам четвер981996 того и пятого элементов И, вторые входы которых соединены соответст.венно с единичным и нулевым выходами третьего триггера, а выходы подключены к нулевому входу третьего триггера и соответственно к единичному и 5 нулевому входам второго триггера, к управляющим входам первого и второго блоков управления, информационные входы которых соединены соответственно с выходами регистров множимого 10 и множителя, а выходы соединены с входами параллельного сумматора, соединенными с выходами блока сдвига, входы которого соединены с соответствующими выходами регистра множимого, выходы регистра множителя подключены к входам блока анализа разрядов, выход которого подключен к единичному входу третьего триггера, входы регистров сомножителей являются входами устройства, а выходы параллельного сумматора - выходами устройства (3) .

Данное устройство производит анализ множителя на преобладанйе в нем единиц или нулей и осуществляет умножение соответственно с использованием прямого или обратного кодов множимого. Вследствие жесткого разделения сомножителей на множитель и множимое быстродействие устройства уменьшается при приближении к равенству нулей и единиц в множителе.

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

Цель достигается тем, что устройство для умножения двоичных чисел,содержащее регистр множителя, регистр глножимого, параллельный сумматор, блок анализа разрядов, блок сдвига, 4О два блока управления, генератор тактовых импульсов, два блока формирования импульсов считывания, элемент задержки, пять элементов И, счетчик, дешифратор, три триггера, причем выход генератора тактовых импульсов со" единен с первым входом первого элемента И, второй вход которого соединен с единичным выходом нулевого триггера, а выход соединен с входом счетчика и управляющим входом дешифратора, информационные входы которого соединены с разрядными выходами счетчика, а выход дешифратора подключен к первым входам второго и третьего элементов И, вторые входы которых подключены соответственно к нулевому и единичному выходам второго триггера, а выходы соединены соответственно с управляющими входами первого и второго блоков формирования импульсов считывания, информационные входы которых соединены с соответствующими выходами регистра множителя, а выходы соединены с входами блока сдвига и с нулевым входом первого триггера, 65 единичный вход которого соединен с шиной запуска устройства и с входом элемента задержки, выход которого подключен к первым входам четвертого и пятого элементов И, вторые входы которых соединены соответственно с нулевым и единичным выходами третьего триггера, а выходы подключены к нулевому входу третьего триггера и . соответственно к единичному и нулевому входам второго триггера, к управляющим входам первого и второго бло-. ков управления, соответственно, информационные входы которых соединены соответственно с выходами регистров глножимого и множителя, а выходы соединены соответственно с входами параллельного сумматора, соединенными с соответственно с выходами блока сдвига, входы которого соединены с соответствующими выходами регистра ! множимого, первый управляющий выход блока анализа разрядов подключен к единичноиу входу третьего триггера, выходы параллельного сумматора являются выходами устройства, содержит коммутатор сомножителей, причем первая группа его выходов подключена к соответствующим разрядным входам регистра множителя, вторая группа выходов подключена к соответствующим разрядным входам регистра множимого, первая группа информационных выходов блока анализа разрядов подключена соответственно к первым информационным входам первой и второй групп коммутатора сомножителей, вторая группа информационных выходов блока анализа разрядов соединена соответственно со вторыми информационными входами первой и второй групп коммутатора сомножителей, второй управлякщий выход блока анализа разрядов подключен к второму и первому управляющим входам первой и второй группы коммутатора сомножителей соответственно, третий управляющий выход блока анализа раэрядов подключен к второму и первому управляющим входам первой и второй группы коммутатора сомножителей соответственно, выход элемента задержки подключен к входу разрешения коммутатора сомножителей, первые и вторые информационные входы блока анализа разрядов соединены соответственно с входами первого и второго операндов устройства. Кроме того, блок анализа разрядов содержит два регистра, два преобразователя двоичного кода в уплотненный, элемент сравнения, два элемента ИЛЙ, причем первые и вторые информационные входы блока соединены соответственно с входами первого и второго регистров, выходы которых подключены соответственно к входам первого и второго преобразователей двоичного кода в уплотненный и к первой и второй группе информацион-.

981996 ных выходов блока, прямоте вь1- которые содержат нули во множителей ходы первого и второго преобразова- (начиная с младшего разряда) П т елей двоичного кода в уплотненный ченное таким образом число является

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

Выходом элемента сравнения, второй 2О алгоритм). ход соединен с четвертым выходом лемента сравнения, а выход подклю- Устройство работает следующим об:чеи к первому управляющему выходу блока. После приема сомножителей на шиИа фиг. 1 представлена схема уст-. ны приема. операндов 23 и 24 в любом .Ройства для умножения двоичных чисел; порядке по анне запуска 25 поступает на фиг. 2 — схема блока анализа раз- импульс запУска Устройства, который в устанавливает в единичное состояние устройство содержит регистр мно- триГгер 7, тем саввам Разрешая прожимого 1, блок сдвига 2, генератор хождение через элемент и 4 .импульсов

TaRToBhix импульсов 3< элемент И 4, reaepaTopa 3 на счетчик 5 и дешифсчетчик 5, дешифратор 6,. триггеры 7

/и 8 элеуррнты И 9 и 10 триггер 11 Работа блока анализа разрядов 21

:элементы и 12 и 13 блоки управления (Фиг. 2) заключается в определении . ч

Считыванием 14 и 15 регистр множите- из двух сомножителей числа с наименьля 16, параллельный сумматор 17, блохин шим количеством информационных едиt формирования импульсов считывания . ниц или нулей с тем чтобы выбранное

18 и 19, элемент задержки 20, блок число затем использовать в качестве анализа разрядов 21, коммутатор . множителя. При этом используются сомножителей 22, шины операщ1ов 23, преОбразоватЕли двоичного кода в Уп24 шину запуска 25. Блок анализа 46 лотненный 27 и 28,осуществляющие разрядов содержит регистр 26,преобсдвиг единиц в сомножителях к граниразоватепи двоичного кода в уплот„Це РазРЯДной сетки, на.пРЯьмх выхо-. ненный 27 и 28, элемент сравнения . дах таким обРазом полУчаютсЯ коды, 29 элементы ИЛИ ЗО и 31, выход .;-содержащие единицы в крайних позициях первого н второго Регистров 32 и 33 45 .количество 1(oTo Рав"о "."слУ един"ц

:аервый управляю и од блока 34 в исходном коде, на инверсных же торой и третий упраВлякие .вакх выходах преОбразователей папучаются лока 35 и 36, регяст 37 коды, содержащие единицы в крайних позициях, количество которых равно .Предложенное устройство реализует числу нулей в исходном коде. Полусладующие алгоритмы умножения двоич- ченные кодй поступают на входы эленых чисел. Берут два "и"-разрядных мента сравнения 29, где определяются двоичных числа и выбирают в качестве . какой из кодов меньше, т.е. какой множителя число с наименьшим количе- из сомножителей будет выбран как мноством единиц или нулей. житель и какой алгоритм будет приме.Если количество единиц в множителе нен. С выхода элемента ИЛИ 31 снима-. больше количества нулей, то для по- ется сигнал .преобладания количества лучения произведения берут прямой единиц над количеством нулей в мнокод множимаво, справа от которого, жителе. С прямого выхода 35 элемента приписывается столько нулей, сколько ИЛИ 30 снимается сигнал испальзоваразрядов содержит множитель. Из полу- ® ния первого сомножителя как мйожитеченного числа последовательно вычита- ля, с выхода 36 - второго сомножитеют прямой код множимого и прямой код ля как множителя. чисел, полученных путем сдвига мно- После прихода импульса запуска жимого влево на число разрядов, на (шина 25), задержанного на элементе единицу меньше номеров тех разрядов,. Ю задержки 20, в коммутатор сомножите981996 лей 22 и в зависимости от сочетания выходных импульсов элемента ИЛИ 30 коммутатор сомножителей 22 производит распределение и считывание исходных, чисел, равное записанным в регистры.

26 и 37, в регистры множимого 1 и множителя 16 соответственно или информация регистров 26 и 37 считывается в регистр множителя 16 и множимого 1 соответственно., После анализа множителя в блоке анализа разрядов 21 выделяется управ ляющий импульс, который подается на единичный вход триггера 8, размещаю . щий прохождение импульса запуска, задержанного на элементе задержки 20, 15 либо через элемент И 9 (если число единиц во множителе больше„ чем нулей) либо через элемент И 10 (в протинном случае), В первом случае импульс запуска с 20 выхода элемента И 9 поступает на блок управления считыванием 14, считывая значения прямого кода множимого с регистра множимого 1 в "и" старших разрядов сумматора 17. Одновременно 25 прямой код множимого,инвертируясь для вычитания, считывается в "и" младших разрядов сумматора 17.

При этом одновременно на все единичные вхбды "n" старший разрядов щ сумматора 17 с задержкой, равной времени установления переходных процессов в этих разрядах, проходит импульс который считывал значение множимого.

Тем самым проводится вычитание из значений прямого кода множимого,сдвинутого влево íà "n" разрядов, значений несдвинутого прямого кода множимого. Одновременно импульс запуска устанавливает в нуль триггер 8 .

Во втором случае импульс запуска с выхода элемента И 10 поступает на блок управления считыванием 15,считывая значения прямого кода Множителя с регистра множителя 16 в "и" старших разрядов сумматора 17 и значение об- 45 атного кода множителя в "n младших азрядов сумматора 17. С приходом импульса на единичные входы старших азрядов сумматора 17 выполняется операция вычитания из значения прямо- 50 го кода множителя, сдвинутого íà "n" разрядов влево, значений несдвинутого прямого кода множителя, а также подтверждается установка триггера 8 в нулевое состояние. 55

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

12 соответственно на блоки формирования импульсов считывания 18 или 19. 65

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

И 12 (в обратном случае) поступает соответственно на вход. либо Длока формирования импульсов считывания 18, либо блока 19, которые управляются регистром множителя 16.

В первом случае данный импульс, последовательно проходя через элементы И сквозного переноса блока 18; управляемые с единичным выходов разрядов регистра 16, отыскивает первый, находящийся в нулевом состоянии разряд блока 18, устанавливает его в единичное состояние и поступает с выхода блока 18, соответствующего перебрасываемому разряду на вход блока сдвига 2. С помощью блока 2 импульс считывает в сумматор 17 значения прчмого кода множимого, сдвинутого влево на число разрядов, на единицу меньше номеров тех разрядов, которые содержат нули во множителе.

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

18, в соответствии с изложенным принципом получения произведения по первому алгоритму.

Во втором случае импульс, последовательно проходя через элементы И сквозного переноса блока 19, управляемяе с нулевых выходов разрядов регистра 16, отыскивает первый находящийся в единичном состоянии разряд блока 19, перебрасывает его в нулевое состояние и поступает с выходной шины блока 19, соответствующей перебрасываемому разряду, на вход блока сдвига 2. С помощью этого блока импульс считывает в сумматор 17 значения обратного кода множимого сдвинутого влево на-число разрядов, на единицу меньше номеров тех разрядов,которые содержат единицы во множителе.

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

19, в соответствии с. изложенным принцийом получения произведения по второму алгоритму.

981996

Следующий импульс с дешифратора

6, поступая на вход блока 18 или 19, проводит аналогичные действия. Блоки 18 и 19 работают до тех пор, пока не будут установлены в единичное состояние все разряды блока 18 в первом случае, либо в нулевом состоянии все разряды блока 19 во втором случае.При этом очередной импульс с выхода дешифратора б, пройдя сквозным переносом через элементы H блоков 18 или 1О

19, поступает на триггер 7 для установки его в нулевое состояние, тем самым прекращая работу устройства.

Произведение двух сомножителей формируется на сумматоре 17. t5

Предлагаемое устройство для умно. жения двоичных чисел позволяет повысить быстродействие устройств данного класса за счет выбора из двух сомножителей в качестве множителя числа 2п с минимальным количеством единиц или нулей.

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

1. Устройство для умножения двоич- 25 ных чисел, содержащее регистр множи теля, регистр множимого, жраллельный сумматор, блок анализа Разрядов блок сдвига, два блока управления, генератор тактовых импульсов, два блока формирования импульсов считывания, |элемент задержки, пять элементов Й, счетчик, дешифратор, три триггера, причем выход генератора тактовых импульсов соединен с первым входом пер- З5 вого элемента И, второй вход которого соединен с единичным выходом первого триггера, а выход соединен с входом счетчика и управляющим входом дешифратора, информационные входы которого 4Q соединены с различными выходами счетчика, а выход дешифратора подключен к первым входам второго и третьего элементов И, вторые входы которых подключены соответственно к нулевому и 4$ единичному выходам второго триггера, а выходы соединены соответственно с управляющими входами первого и второго блоков ФОрмирования импульсов счи-, тывания, информационные входы которых 5О соединены с соответствующими выходами . регистра множителя, а выходы соединены с входами блока сдвига и с нулевым входом первого триггера единичный вход которого соединен с шйной запуска устройства и с входом элемента задержки, выход которого подключен к первым входам четвертого и пятого элементов

И, вторые входы которых соединены соответственно с нулевым и единичным выходами третьего триггера, а выходы под- ключены к нулевому входу третьего триггера и соответственно к единичному и нулевому входам второго триггера, к управляющим входам первого и второго блоков управления соответственно. ез информационные входы которых соединены соответственно с выходами регистров множимого и множителя, а выходы соединены с соответствующими входами параллельного сумматора, соединенными с соответствующими выходами блока сдвига, входы которого соединены ссоответствук цими выходами регистра множимого, первый управляющий выход блока .анализа разрядов подключен к единичному входу третьего триггера, выходы параллельного сумматора являются выходами устройства„ о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, устройство содержит коммутатор сомножителей, причем первая группа его выходов подключена к соответствующим . разрядным входам регистра множителя, вторая группа выходов подключена к соответствукс им разрядным входам регистра множимого, первая группа информационных выходов блока анализа разрядов подключена соответственно к первым ийформациониым входам первой и второй rpynn коммутатора сомножителей, вторая группа информационных выходов блока анализа разрядов соединена со вторыми информационными вхо дами первой и второй групп коммута zopa сомножитеЛей соответственно,вто,рой управляющий выход блока анализа разрядов п6дключен к первому и второму управляющим входам первой и второй группы коммутатора сомножителей соответственно, третий управляющий выход блока анализа разрядов пЬдключен к второму и первому управляющим входам первой и второй группы коммутатора сомножителей соответственно, выход элемента задержки подключен к входу разрешения коммутатора сомножителей, первые и вторые информационные входы блока анализа

° ° азрядов соединены соответственно с, ходами первого и второго операндов стройства.

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

12

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

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

Источники информации

3 принятые во внимание прн экспертиэе

1. Авторское свидетельство СССР

° 9 273520,кл. G 06 F 7/52, 1971.

2. Авторское свидетельство СССР

10 9 478305, клС 06 F 7/52, 1973.

3. Авторское свидетельство СССР

В 482741,, кл.G 06 F 7/52, 1973 (прототип), 981996

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

Редактор М.Товтин Техред A,Ач Корректор Н. Король

Заказ 9712/68 Тираж 731 Подписное

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

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

Филиал ППЛ "Патент", г. ужгород, ул. Проектная, 4