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

 

Изобретение относится к вычислительной технике и может быть использовано при умножении чисел в системе счисления с двоичным основанием или основанием, равным целой ступени двух. Цель изобретения - повышение быстродействия , достигается за счет формирования за один такт группы частичных произведений р-х (k-разрядных) сомнооо о СП 05 05

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

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

РЕСПУБЛИК (19) (11) (51)4 G 06 F 7/52 н

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТ8ЕННЫИ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К ASTOPCHOMY СВИДЕТЕЛЬСТВУ (2 i) 3975355/24-24 (22) 15.11.85 (46) 23.04.87. Бюл. У 15 (71) Институт кибернетики им.В.M.Глушкова (72) А.Ф, Кургаев и В.Н.Опанасенко (53) 681.325 (088.8) (56) Авторское свидетельство СССР

У 1185328, кл. G 06 F 7/52, 1984.

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

В 1233136, кл. С 06 Р 7/52, 1984. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано при умножении чисел в системе счисления с двоичным основанием или основанием, равным целой ступени двух.

Цель изобретения — повышение быстродействия, достигается за счет формирования за один такт группы частичных произведений р-х (k-разрядных) сомно1305657 жителей. Устройство содержит регистры 1-3 множимого, множителя и произведения, две группы мультиплексоров

4 и 5, d умножителей 6, где d =

=log n/k+1, n — разрядность сомножителей,4+1)-входовый сумматор 7, три группы элементов И 8-10,демультиплексор 11, два элемента И 12и 13, триггер

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

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

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

4 и 5, группу умножителей 6, сумматор

7, третья, йервая и вторая группы элементов И 8-10, демультиплексор 11, два элемента И 12 и 13, триггер 14, буферный регистр 15, группу элементов ИЛИ 16 и блок 17 микропрограммного управления, первая и вторая группы выходов 18 и 19, первый и второй входы 20 и 21 блока 17, третья группа выходов 22 блока 17, третий, четвертый и пятый выходы 23-25 блока 17, выход Готовность", вход "Çàïóñê" и тактовый вход ТИ, входы Л и В множимого и множителя, выход С результата. !

Структурная схема блока 17 управления (фиг. 2) содержит элемент И 26, элементы 27 и 28 задержки, схему 29 сравнения с константой, триггер 30, счетчик 31, блок 32 микропрограммной памяти, регистр 33 микрокоманд и две группы элементов И 34 и 35. ментов ИЛИ 16,, блок 17 микропрограммного управления с управляющими входами "Запуск",, тактовый вход, упракляющий выход Готовность . Повышение быстродействия устройства достигнуто за счет введения 2(d-1) дополнительных мультиплексоров, (d-1) дополнительных умножителей, увеличение (до d+1) числа входов сумматора. 4 ил.

Выходы регистра 1, объединенные в группы по k-двоичных разрядов, каждая из которых представляет собой р-й разряд (р = 2 ), соединены с информйФ

5 ционными входами первой группы мультиплексоров 4. Выходы регистра 2, объединенные также в группы no k-двоичных разрядов, подключены к информационным входам второй группы мульти10 плексоров 5.

Каждый из умножителей 6 имеет два

k-разрядных (двоичных) входа и 2kразрядный выход. Причем количество . умножителей в группе определяется из

15 соотношения с! = 1ор тп+1, где m = n/k, п — разрядности сомйожителей.

Каждый из мультиплексоров 4 и 5

20 имеет тп = n/k (р-х входов k-разрядных (двоичных) чисел и р-й выход.

Сумматор с запоминанием 7 имеет (d+1) р-х входов °

Демультиплексор 11 со стробирова25 нием имеет р-й вход и (2m-1) р-х выходов.

После подачи управляющего сигнала

"Запуск" прямой выход триггера 30 устанавливается в единичное состояние и и разрешает передачу ТИ в блок 17.

ТИ разрешает выдачу управляющих сигналов 18-22, 24 и 25 очередной микрокоманды, которые формируют сумму

d-частичных произведений и результат запоминается в сумматоре 7. Элемент

З5 27 задержки разрешает выдачу управляющих сигналов 22 и 23, которые управляют записью результата частичного произведения в буферный регистр 15 и регистр 3 произведения по заднему

40 фронту импульса. Г и — время за31 держки, формируемое на элементах 27 и 28 задержки соответственно.

1305667

Таблица состояний блока 32 микропрограммной памяти является микропрограммой для примера умножения двух

16-разрядных чисел для случая k=4 ф

Э

m=4, р=2, d=3. При этом принято, что сомножители

A=a„2+a 2 +а Г +а 2

B=b„2 +Ь 2 +b) 2 +а, ?

10 а произведение

С = а„Ь„2 + (а,b,+Ь,а ) 2 + (а„Ьз + а Ь + азЬ„) 2 " + (а„Ь++ 15

+ а Ь + азЬ + а Ь,) 2 + (а Ь, +

+ азЪ .+ а Ь2) 2

Устройство работает следующим образом.

В исходном состоянии в регистрах 1 и 2 содержатся прямые положительные коды множимого и множителя, в буферном регистре 9 установлен "0". Микропрограмма записана в блоке 32 микро. программной памяти в виде последовательности микрокоманд, адреса которых следуют в естественном порядке и формируются с помощью счетчика 31.

Сигнал нЗапуск" устанавливает триггер 30 в единичное состояние и счетчик 31 — в исходное состояние, которому соответствует первая микрокоманда на выходе блока 32 микропрограммной памяти.

Первый из тактирующих сигналов ТИ после прихода сигнала "Запуск" проходит элемент И 26 и поступает на вход элемента 27 задержки, а также на4О управляющий вход группы элементов И 35, разрешая передачу на выходы 18-21, 24 и 25 управляющих сигналов, соответствующих микрокоманде. После окончания сигнала ТИ на выходе элемента 27 за- 45 держки формируется управляющий сигнал, разрешающий передачу через группу элементов И 34 на выходы 22 и 23 управляющих кодов. После .окончания сигнала на выходе элемента 27 задержки формируется сигнал на выходе элемента 28 задержки, увеличивающий содержимое счетчика 31 на "1", на следующих тактах блок 17 управления аналогичным образом формирует следующие управляющие коды.

Для получения произведения однократной точности процесс умножения состоит из (m+1) циклов. В каждом из циклов выполняется перемножение в блоках 6 р-х сомножителей, суммирование в сумматоре 7 частичных произведений р-х сомножителей, запись результата суммирования с выходов сумматора 7 через группу элементов И 10 в буферный регистр 15, начиная с третьего цикла, запись младшего р-го разряда с выходов сумматора 7 в регистр 3 произведения через демультиплексор 11 в один из младших р-х разрядов.

Число тактов в цикле зависит от числа d умножителей и разрядности m сомножителей. Такт представляет собой формирование частичного произведения р-х сомножителей. Результатом работы одного цикла является формирование суммы частичных произведений, имеющих одинаковые веса. Начиная с третьего цикла, в последнем такте цикла младший р-й разряд с выхода сумматора 7 через демультиплексор 11 под управлением сигнала 22 записывается в соответствующий (начиная с младшего) р-й разряд регистра 3. Последний такт второго цикла отличается от остальных тактов тем, что k-й двоичный разряд с выхода сумматора ? через элемент И !2 под управлением сигнала

21 фиксируется в триггере 14. Первый такт третьего цикла отличается от остальных циклов тем, что на вход переноса сумматора 7 через элемент И 13 под управлением сигнала 20 поступает значение с выхода триггера 14 (это соответствует округлению результата .. произведения однократной длины с погрешностью Е = 2" ). Под управлением сигналов 18 и 19 мультиплексоры 4 и

5 выбирают соответствующие р-е разряды множимого и множителя. В умножителях 6 вычисляются и частичных произведений р-х сомножителей, поступающих на их входы с выходов мультиплексоров 4 и 5. Выходы d умножителей поспоступают на d входы сумматора 7 в каждом такте. Если такт является первым в данном цикле, на (d+1) é вход сумматора 7 поступает частичное произведение с выходов буферного регистра 15 через группу элементов И 8 под управлением сигнала 24 со сдвигом на

k-двоичных разрядов вправо (в сторону младших) и группу элементов ИЛИ 16.

Во всех остальных тактах цикла на (d+1)-й вход поступает частичное произведение с выходов буферного регистра 15 через группу элементов И 9 под

1305667

55 управлением сигнапа 25 и группу элементов ИЛИ 16. В буферный регистр 15 записывается значение с выходов сумматора 7 через группу элементов И 10.

Таким образом, через (гп+1)-циклов в регистре 3 формируется п-разрядное произведение и-разрядных сомножителей с точностью, равной половине единицы младшего разряда сомножителей.

Последний тактирующий сигнал с выхода элемента 28 задержки устанавливает счетчик 31 в состояние, соответственно которому схема 29 сравнения вырабатывает единичный сигнал, устанавливающий триггер 30 в нулевое состояние. В результате на выходе

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

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

Устройство для умножения, содержащее регистры множимого, множителя и произведения, два мультиплексора, умножитель, сумматор, три группы элементов И, триггер, буферный регистр, два элемента И, группу элементов ИЛИ, демультиплексор и блок микропрограммнОго управления, тактовый вход и вход запуска которого являются соответственно тактовым входом и входом запуска устройства, причем входы множимого и множителя устройства являются информационными входами соответственно регистров множимого и множителя, выходы которых соединены с информационными входами соответственно первого и второго мультиплексоров, выходы которых соединены с входами соответственно первого и второго сомножителей умножителя, выход которого соединен с входом первого р-го разряда сумматора, выход которого соединен с входом первого р-го разряда регистра произведения, выход которого является выходом результата устройства, выход первого двоичного (d+1) го р-го (где d = log m+1, m — число р-х разрядов сомножителей) разряда сумматора соединен с первым входом первого элемента И, выход которого соединен с входом триггера, выход которого соединен с первым входом второго элемента И, выход которого соединен. с

10 !

40 входом перечоса сумматора, выходы переноса и суммы i-го р-ro разряда которого (где i =: 1,2,...,d+1) соединены с первыми входами соответственно первых и (i+1)-х элементов И первой группы, выходы которых соединены с информационными входами буферного регистра, выходы которого соединены с первыми входами элементов И второй и третьей групп, выходы х-х элементов И второй группы и (i+1)-х элементов И третьей группы соединены соответственно с первыми и вторыми входами элементов ИЛИ группы, выходы которых соединены с входом (d+1)-го р-го разряда сумматора, выходы суммы

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

j-х мультиплексоров первой и второй групп (где j = 1,2,..., d-1) соединены с входами первого и второго сомножителей j-го умножителя группы, выход которого соединен с входом (j+1)-ro р-го разряда сумматора, управляющие входы мультиплексоров первой и второй группы соединены с соответствующими выходами первой и второй групп блока микропрограммного управления.

1305667

i 305067

1305667 ю

Ц,) . 4. ф 04 +

О

Ф ф b ъ С> гэ ач g С д

С ФФ ° с

+ ° Ъ ° ю ф ъ. >>Oh b м м И II и И

tt,C C t V

Составитель Н, Маркелова

Редактор Н, Рогулич Техред П.Олейник Корректор Е. Рошко

Заказ 1452/46 Тираж 673 Подписное

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

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

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