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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ щ 981996 Сфез СюеетскниСоциалистическмкРеспублик(61) Дополнительное к авт. свид-ву- (22) Заявлено 18,07. 80 (21) 2961300/18-24 с присоединением заявки йф(23) ПриоритетОпубликоввно 15,1282.Бюллетень йф 1 46 ИМ,Кп.ф С 06 Р 7/52 Государственный комитет СССР ио делам изобретений н открытийДата опубликования описания 15. 12. 82(72) Авор Ю.И. Нежевенко ЧИСЕЛ 10 3 Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств.Известно устройство для умножения чисел в обратном коде, содержащее сумматор, регистры сомножителей и результата, блок Формирования сигналов прямой и инверсной передачи множимого в сумматор, блок совпадения нулевого значения, блок коррекции младшей час ти произведения, триггер, блоки совп дения и неравнозначности 111 . Данное устройство обладает невысо ким быстродействиемИзвестно также устройство для умножения чисел, содержащее блок хранения порядка множимого, множительный блок, регистры сомножителей, блоки обнаружения метки и последней циФры множителя 2 .Быстродействие этого устройства также невелико.Наиболее близким к изобретению яв 2 ляется устройство для умножения двоичных чисел, содержащее регистры множимого и множителя,пераллельный сумма" тор, :лок анализа разрядов, счетчик, дешифратор, два блока Формиро:вания импульсов считывания, два блокауправления считыванием, блок сдвига,генератор, элемент задержки, пятьэлементов И, три триггера, причем выход,генератора соединен с первым входом первого элемента И, второй входкоторого соединен с единичнымвыходомпервого триггера, а выход соединенс входом счетчика и управляющим входом дешиФрйтора, инФормационные входы которого соединены с разряднымивыходами счетчика, а выходы дешнфратора подключены к первым входам второго элемента И и третьего элементаИ, вторые входы которых подключенысоответственно к нулевому и единичному выходам второго триггера, а выходы соединены соответственно с управляющими входами первого и второго блоков Формирования импульсов считывания, инФормационные входы которыхсоединены с соответствующими выходамирегистра множителя, а выходы соединены с входами. блока сдвига и с нулевым вхоцом первого триггера, ециничный вход которого соединен с шинойзапуска устройства, с управляющимвходом блока анализа разрядов и вхо)дом элемента задержки, выход которого подключен к первым входам четвер 981996того и пятого элементов И, вторые входы которых соединены соответст.венно с единичным и нулевым выходами третьего триггера, а выходы подключены к нулевому входу третьего триггера и соответственно к единичному и 5 нулевому входам второго триггера, к управляющим входам первого и второго блоков управления, информационные входы которых соединены соответственно с выходами регистров множимого 10 и множителя, а выходы соединены с входами параллельного сумматора, соединенными с выходами блока сдвига, входы которого соединены с соответствующими выходами регистра множимого, выходы регистра множителя подключены к входам блока анализа разрядов, выход которого подключен к единичному входу третьего триггера, входы регистров сомножителей являются входами устройства, а выходы параллельного сумматора - выходами устройства 3 .Данное устройство производит анализ множителя на преобладанйе в нем единиц или нулей и осуществляет умножение соответственно с использованием прямого или обратного кодов множимого. Вследствие жесткого разделения сомножителей на множитель и множимое быстродействие устройства уменьшается при приближении к равенству нулей и единиц в множителе.Цель изобретения - повышение быст- родействия устройства. 35Цель достигается тем, что устройство для умножения двоичных чисел,со. держащее регистр множителя, регистр множимого, параллельный сумматор, блок анализа разрядов, блок сдвига, 40 два блока управления, генератор тактовых импульсов, два блока формирования импульсов считывания, элемент задержки, пять элементов И, счетчик, дешифратор, три триггера, причем выход генератора тактовых импульсов со" единен с первым входом первого элемента И, второй вход которого соединен с единичным выходом нулевого триггера, а выход соединен с входом счетчика и управляющим входом дешифра" тора, информационные входы которого соединены с разрядными выходами счетчика, а выход дешифратора подключен к первым входам второго и третьего элементов И, вторые входы которых подключены соответственно к нулевому и единичному выходам второго триггера, а выходы соединены соответственно с управляющими входами первого и второго блоков формирования импульсов считывания, информационные входы которых соединены с соответствующими выходами регистра множителя, а выходы соединены с входами блока сдвига и с нулевым входом первого триггера, 65 единичный вход которого соединен сшиной запуска устройства и с входомэлемента задержки, выход которогоподключен к первым входам четвертогои пятого элементов И, вторые входы которых соединены соответственно с нулевым и единичным выходами третьего триггера, а выходы подключены к нулевому входу третьего триггера и. соответственно к единичному и нулевому входам второго триггера, к управляющим входам первого и второго бло-. ков управления, соответственно, информационные входы которых соединены соответственно с выходами регистров множимого и множителя, а выходы соединены соответственно с входами параллельного сумматора, соединенными с соответственно с выходами блока сдвига, входы которого соединены с соответствующими выходами регистрамножимого, первый управляющий выход блока анализа разрядов подключен к едияичноиу входу третьего триггера, выходы параллельного сумматора являются выходами устройства, содержит коммутатор сомножителей, причем пер" вая группа его выходов подключена к соответствующим разрядным входам регистра множителя, вторая группа выходов подключена к соответствующим разрядным входам регистра мяожимого, первая группа информационных выходов блока анализа разрядов подключена соответственно к первым информационным входам первой и второй группкоммутатора сомножителей, вторая группа информационных выходов блока анализа разрядов соединена соответственно со вторыми информационными входами первой и второй групп коммутатора сомножителей, второй управлякщий выход блока анализа разрядов подключен к второму и первому управляющим входампервой и второй группы коммутатора сомножителей соответственно, третийуправляющий выход блока анализа раэрядов подключен к второму и первому управляющим входам первой и второй группы коммутатора сомножителей соответственно, выход элемента задержки подключен к входу разрешения коммутатора сомножителей, первые и вторые информационныЕ входы блока анализа разрядов соединены соответственно с входами первого и второго операндов устройства. Кроме того, блок анализа разрядов содержит два регистра, два преобразователя двоичного кода в уплотненный, элемент сравнения, два элемента ИЛЙ, причем первые и вторые информационные входы блока соединены соответственно с входами первого и второго регистров, выходы которых подключены соответственно к входам первого и второго преобразователей двоичного кода в уплотненный и к первой и второй группе информацион-,981996ных выходов блока, пряные вй" которые содержат нули во множителейходы первого и второго преобразова- (начиная с младшего разряда) Пт елей двоичного кода в уплотненный ченное таким образом число являетсяподключены соответственно к входам, произведением двух чисел п йвух чисел первыйпервого и второго чисел элемента алгоритм).сравнения, инверсные выходы первого ф Если количество нулей во множитеи второго преобразователей двоичного ле больше количества единиц, то длякода в уплотненный подключены соот- получения произведения берут прямойя, справа от которого ветственно к входам третьего и чет- код множителя справа от т првертого чисел элемента сравнения,пер- приписывается столько нулей, скольковый вход первого элемента ИЛИ под". 10 разрядов содержит множимое. Из полуключен к первому выходу элемента срав- ченного числа последовательно вычи нения, второй его вход подключен к тают прямой код множителя и обратныйтретьему выходу элемента сравнения, код чисел, полученных путем .сдвигапрямой выход первого элемента ИЛИ сое- множимого влево на число )разрядов.,динен со вторым управляющим выходом 5 на единицу меньше номеров тех разря 1 блока, а инверсный выход первого эле- дов, которые содержат единицы во мномента ИЛИ соединен с третьим улравля- жителе (начиная с младшего разряда). щцим выходом блока, первый вход вто- . Полученный результат является произфого элемента ИЛИ соединен с третьим ведением двух сомножителей второй аыходом элемента сравнения, второй 2 О алгоритм).ход соединен с четвертым выходомлемента сравнения, а выход подклю- Устройство работает следующим обчеи к первому управляющему выходуразом.блока. После приема сомножителей на шиНа Фиг 1 предоставлена схема уст ы приема олераццов 23 и 24 в любом .Ройства для умножения двоичных чисел; порядке по шине запуска 25 поступает на Фиг. 2 - схема блока анализа Раз- импульс запуска устройства, который рядов. Устанавливает в единичное состояниеУстройство содержит регистр мно- триГгер 7, тем садним разрешая прожимого 1, блок сдвига 2, генератор .хождение через элемент И 4 .импульсов тактовых импульсов 3, элемент И 4,генератора 3 йа счетчик 5 и дешиФ- счетчик 5, дешиФратар б, триггеры 7Ратор б.и 8, элементы И 9 и 10, триггер 11, .Работа блока анализа разрядов 21 :элементы и 12 и 13,. блоки управления Фиг. 2) заключается в определении, "Считыванием 14 и 15 Регистр множите- из двух сомножителей числа с наименьля 16, параллельный сумматор 17, блоки Зз шим количеством инФормационных едиУФормирования импульсов считывания ниц или нулей с тем, чтобы выбранное 18 и 19, элемент задержки 20, блок число затем использовать в качествеанализа разрядов 21, коммутатор . множителя. При этом используются сомножителей 22, шины операщ 1 ов 23 преОбразоватЕли двоичного кода в уп шину запуска 25. Блок анализа 46 лотненный .27 и 28,осуществляющие разрядов содержит регистр 2 б,преоб- сдвиг единиц в сомножителях к граниразоватеаи двоичного кода в уплот- Це РазрЯДной сетки, на пРЯиюх выхо-. ненный 27 и 28, элемент сравнения . дах таким обРазом полУчаютсЯ коды, 29, элементы ИЛИ ЗО и 31, вымол содержащиеединицывкрайнихпозициях, пеРвого н второго регистров З 2 и 33, 45 количествокоорыхравночислуединиц :первый управляющий выход блока 34в исходном коде, на инверсных же торой и третий упраВлякщие,в ходы выхоДах лреОбразователей получаютсялока 35 и 36, Регистр 37, коды, содержащие единицы в крайнихпозициях, количество которых равно.Предложенное устройство реализует. числу нулей в исходном коде. Полусладующие алгоритмы умножения .двоич- ченные кодй поступают на входы эленых чисел. Берут два флфф-разрядных мента сравнения 29, где определяются двоичных числа и выбирают в качестве . какой из кодов меньше, т.е. какой множителя число с наименьшим количе- из сомножителей будет выбран как мноством единиц или нулей. житель и какой алгоритм будет приме.Если количество единиц в множителе нен. С выхода элемента ИЛИ 31 снима- больше количества нулей, то для пО- ется сигнал преобладания количества лучения произведения берут прямойединиц над количеством нулей в мнокод множимаво, справа от которого , жителе. С прямого выхода 35 элемента приписывается столько нулей, сколькоИЛИ 30 снимается сигнал использоваразрядов содержит множитель, Из полу- ф ния первого сомножителя как мйожитеченного числа последовательно вычита- ля, с выхода 36 - второго сомножитеют прямой код множимого и прямой код ля как множителя. чисел, полученных путем сдвига мно- После прихода импульса запуска жимого влево на число разрядов, на шина 25), задержанного на элементе единицу меньше номеров тех разрядов Ю задержки 20, в коммутатор сомножите 981996лей 22 и в зависимости от сочетаниявыходных импульсов элемента ИЛИ 30коммутатор сомножителей 22 производитраспределение и считывание исходных,чисел, равное записанным в регистры26 и 37, в регистры множимого 1 имножителя 16 соответственно или информация регистров 26 и 37 считываетсяв регистр множителя 16 и множимого 1соответственно., После анализа множителя в блоке 10анализа разрядов 21 выделяется управ ляющий импульс, который подается наединичный вход триггера 8, размещаю .щий прохождение импульса запуска, задержанного на элементе задержки 20, 15либо через элемент И 9 (если числоединиц во множителе больше чем нулей) либо через элемент И 10 (в протинном случае),В первом случае импульс запуска с 2 Овыхода элемента И 9 поступает наблок управления считыванием 14, считывая значения прямого кода множимогос регистра множимого 1 в "и" старшихразрядов сумматора 17. Одновременно 25прямой код множимого,инвертируясьдля вычитания, считывается в "и"младших разрядов сумматора 17,При этом одновременно на все единичные вхбды "и" старший разрядов ЗОсумматора 17 с задержкой, равной вре"мени установления переходных процессов в этих разрядах, проходит импульскоторый считывал значение множимого,Тем самым проводится вычитание иззначений прямого кода множимого,сдвинутого влево на "и" разрядов, значений несдвинутого прямого кода множимого. Одновременно импульс запускаустанавливает в нуль триггер 8.Во втором случае импульс запускас выхода элемента И 10 поступает наблок управления считыванием 15,считывая значения прямого кода Множителяс регистра множителя 16 в "и" старшихразрядов сумматора 17 и значение обатного кода множителя в "и младшихазрядов сумматора 17. С приходомимпульса на единичные входы старшихазрядов сумматора 17 выполняетсяоперация вычитания из значения прямого кода множителя, сдвинутого на "и"разрядов влево,значений несдвинутогопрямого кода множителя, а также подтверждается установка триггера 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, в соответствии с. изложенным принцийом получения произведения по второму алгоритму.Следующий импульс с дешифратора б, поступая на вход блока 18 или 19, проводит аналогичные действия. Блоки 18 и 19 работают до тех пор, пока не будут установлены в единичное состояние все разряды блока 18 в первом случае, либо в нулевом состоянии все разряды блока 19 во втором случае.При этом очередной импульс с выхода дешифратора б, пройдя сквозным переносом через элементы И блоков 18 или 1 О 19, поступает на триггер 7 для установки его в нулевое состояние, тем самым прекращая работу устройства. Произведение двух сомножителей формируется на сумматоре 17. 15Предлагаемое устройство для умно. жения двоичных чисел позволяет повысить быстродействие устройств данного класса за счет выбора из двух сомножителей в качестве множителя числа 2 р с минимальным количеством единиц или нулей. формула изобретения1, Устройство для умножения двоич ных чисел, содержащее регистр множителя, регистр множимого, параллельный сумматор, блок анализа Разрядов блок сдвига, два блока управления, генератор тактовых импульсов, два блока Формирования импульсов считывания, элемент задержки, пять элементов Й, счетчик, дешифратор, три триггера, причем выход генератора тактовых импульсов соединен с первым входом пер- З 5 вого элемента И, второй вход которого соединен с единичным выходом первого триггера, а выход соединен с входом счетчика и управляющим входом дешифратора, информационные входы которого 49 соединены с различными выходами счет-. чика, а выход дешифратора подключен к первым входам второго и третьего элементов И, вторые входы которых подключены соответственно к нулевому и 4 единичному выходам второго триггера, а выходы соединены соответственно с управляющими входами первогЬ и второго блоков ФОрмирования импульсов счи-, тывания, информационные входы которых 5 О соединены с соответствующими выходами регистра множителя, а выходы соединены с входами блока сдвига и с нулевым входом первого триггера единичный вход которого соединен с шйной запуска устройства и с входом элемента задержки, выход которого подключен к первым входам четвертого и пятого элементов И, вторые входы которых соединены соответственно с нулевым и единичным выходами третьего триггера, а выходы под- ключены к нулевому входу третьего триггера и соответственно к единичному и нулевому входам второго триггера, к управляющим входам первого и второго блоков управления соответственно, Ю информационные входы которых соединены соответственно с выходами регистров множимого и множителя, а выходысоединены с соответствующими входамн параллельного сумматора, соединенными с соответствующими выходами блокасдвига, входы которого соединены с .соответствущцими выходами регистрамножимого, первый управляющийвыход блока .анализа разрядов подключен к единичному входу третьеготриггера, выходы параллельного сумматора являются выходами устройствао т л и ч а ю щ е е с я тем, что,с целью повышения быстродействия,устройство содержит коммутатор сомножителей, причем первая группа его выходов подключена к соответствующим , разрядным входам регистра множителя,. вторая группа выходов подключена ксоответствукцим разрядным входам регистра множимого, первая группа информационных выходов блока анализа разрядов подключена соответственно к первым ийформациониым входам первой и второй групп коммутатора сомножителей, вторая группа информационныхвыходов блока анализа разрядов сое" динена со вторыми информационными входами первой и второй групп коммутатора сомножитеЛей соответственно,вто,рой управляющий выход блока анализа разрядов подключен к первому и втоРомууправляющим входам первой и второй группы коммутатора сомножителей соответственно, третий управляющий выход блока анализа разрядов пЬдключен к второму и первому управляющим входам первой и второй группы коммутатора сомножителей соответственно, выход элемента задержки подключен к входу разрешения коммутатора сомножителей, первые и вторые информационные входы блока анализаазрядов соединены соответственно с , ходами первого и второго операндовстройства.2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что, блок анализа разрядов содержит два регистра, два преобразователя двоичного кода в уплотненный, элемент сравнения, два элемента ЙЛИ, причем первые и вторые информационные входы блока соедийены соответственно с входами первого и второго регистров, выходы которых подключены соответственно к входам первого и второго преобразователей двоичного кода в уплотненный и к первой и второй группе информационных выходов блока, пряьне выходы первого и второго преобразователей двоичного кода в уплотненный. подключены соответственно к входам первого и второго чисел элемента срав. кения, инверсные выходы первого и второго преобразователей двоичногокода в уплотненный подкпючены соответственно к входамтретьего н четвертого чисел элемента сравнения,йервый вход первого элемента ИЛИ подключен к первому выходу элементасравнения, второй его вход подключен ктретьему ааходу элемента сравнения,пря мой выход первого элемента ИЛИ соединенсо вторым управлящним выходом блока,а инверсный выход первого элементаИЛИ соединен с третьим управлявицимВыходом блока, первый вход второгоэлемента ИЛИ соединен с третьим выходом элемента сравнения, второй вход соединен с четвертык выходомэлемента сравнения, а выход подключенк первому управляющему выходу блока,Источники информации,3 принятые во внимание прн экспертиэе 1. Авторское свидетельство СССР9 273520,кл. С 06 Р 7/52, 1971.2. Авторское свидетельство СССР 0 Е 478305, кл,С 06 Р 7/52, 1973.3. Авторское свидетельство СССРВ 482741 кл.С 06 Р 7/52, 1973 прототип)Заказ 9712/68 Тираж 731 ВНПППИ Государственного по делам изобретений 113035, Москва, Ж, РаушПодписноекомитета СССРоткрытийскан наб д 4/5 филиал ППЛ "Патент", г. ужгород, ул. Проектная, 4 Составитель А. КлюевРедактор М.Товтин Техред А.Ач Корректор Н, К