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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств универсальных и специализированных цифровых вычислительных машин Целью изобретения является сокращение аппаратурных затрат и повышение быстродействия. Устройство содержит регистры сомножителей 1,2, две группы элементов И 3,4, блок 5 суммирования, элемент НЕ 6, триггеры 7,8, группу элементов ИЛИ 9 и динамический регистр 10, Устройство реализует алгоритм умножения чисел, начиная с младших разрядов в прямом коде в соответствии с выражением А-В ;- (a4(BL;+1) + 1;(A L;)), i 1,п, А Г i1n где i l,n, A , а0...а„)п, В {b,,Ь,...bnj - разряды сомножителей , L - сдвиг влево. Коды сомножителей поступают последовательным кодом, частичные произведения и результат умножения формируются параллельным кодом. Результат произведения получается за 2п тактов. 1 ил. Q « (Л

„.SU„„1735843

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

ШИМ

РЕСПУБЛИК (з1)з С 06 F 2

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

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

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

ПО ИЭОБРЕТЕНИЯВ И СТНРЫТИЯМ

ПРИ ГННТ СССР

1 (21) 4722410/24 (22) 05.06.89 (46) 23.05.92. Бюл. 19 (71) Институт кибернетики им. В.M. Глушкова (72) l0.Я. Ледянкин (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М 1481744, кл. С 06 F 7/52, 1987.

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

8 1203512, кл. G 06 F 7/52, 1984. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ и-РАЗ"

РЯДНИХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств универсальных и специализированных цифровых вычислительных машин, Целью изобретения являетИзобретение относится к вычислительной технике и может быть исполь, зовано при построении арифметичес: ких устройств универсальных и специализированных цифровых вычислительных машин, Известны устройства, содержащие регистры множимого и мнояителя, сумматор, группу элементов И, матрицу модулей.

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

2 ся сокращение. аппаратурных затрат и повышение быстродействия. Устройство содержит регистры сомножителей 1,2, две группы элементов И 3,4, блок 5 суммирования, элемент НЕ 6, триггеры .7,8, группу элементов ИЛИ 9 и динамический регистр 10, Устройство реализует алгоритм умножения чисел, начиная с младших разрядов в прямом коде в соответствии с выражением и

А В + i (а {ВТ.;+,) + 1,(A I.,)), I где z = 1,п, 1 = (ад, а,...ад и, В = (Ъ|,Ъ,...Ъ„ — разряды сомножителей, L — сдвиг влево. Коды сомножителей поступают последовательным кодом, частичные произведения и результат умножения формируются парал" лельным кодом. Результат произведения получается за 2п тактов. 1 ил. (Ф

Известно устройство для умножения Ql чисел, содержащее (и+1) и поразрядные QQ сдвиговые регистры первого и второго Дь сомножителей, первую из (n+1)-го и вторую из (и-1)-ro группы элементов

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

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

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

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

i-го разряда регистра первого сомножителя сое 1инен с первым входом i-го элемента И первой группы (i=1,...,n) выход )-го разряда регистра второго сомножителя соединен с первым входом

j-го элемента И второй группы (j=1, ...,n-1) .

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

Зп тактОв (и-тактов на формирование .. частичных произведений и 2п тактовна прогон переносов иэ младшего 2п-го разряда в старший) и задержанный на и тактов процесс получения младшего

2п-го разряда кода результата. Это связано с тем, что и младших разрядов частичного произведения кода результата формируют на последнем и-м такте, когда введены старший и младший соответственно разряды регистров первого и второго сомножите лей. После этого требуется выполнить

2п тактов для прогона переносов из младших разрядов блока суммирования в старшие.

735843

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

Для достижения поставленной цели в устройство введены элемент. НЕ, два триггера, группа из и элементов

ИЛИ, и-й элемент И второй группы и

10 п ðàçðÿäíûé динамический регйстр, выход i-ro разряда которого соединен с входами синхронизации -х разрядов регистров первого и второго сомножителей, выход и-го разряда регистра второго сомножителя соединен с первым входом n-ro элемента И второй группы, информационный вход первого триггера и информационный разрядный вход регистра первого сомножителя

20 соединены с входом" первого сомножителя устройства, вход второго сомножителя которого соединен с информационным разрядным входом регис1ра второго сомножителя и информационным входом второго триггера, выход которого соединен с вторыми входами элементов И первой группы, выходы которых соединены с первыми входами соответствующих элементов ИЛИ группы, вторые входы которых соединены с выходами соответствующих элементов И второй груп- пы, вторые входы которых соединены с выходом первого триггера, вход синхронизации которого соединен с входами синхронизации второго тригге35 ра и устройства, с третьими входами элементов И второй группы,и входом элемента НЕ, выход которого соединен с третьими входами и элементов И первой группы, выход i-ro элемента ИЛИ

40 группы соединен с i-м входом и-разрядного блока суммирования, выходы которого соединены с выходами результата устройства.

Введенные блоки и элементы с их

45 связями обеспечивают умножение двух чисел, представленных последовательным кОдОм младшими разрядами Вперед, . с организацией за и тактов всех частичных произведений параллельным споM собом с формированием младшего 2п-го разряда кода результата на первом такте умножения, когда в устройство .введены младшие и-е разряды сомножителей, После формирования всех частич55 ных произведений, т.е. через и тактов следует выполнить и тактов для полу" чения результата умножения (после формирования переносов в старший разряд).

На чертеже представлена схема устройства.

Устройство содержит и-разрядные регистры первого 1 и второго 2 сомножителя, первую 3 и вторую 4 группы элементов И, блок 5 суммирования, инвертор 6, первый 7 и второй 8 триггеры, и-разрядные группы элементов

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

При работе устройства младшими разрядами вперед одновременно поступают i-e (i=1,n) разряды кодов сомножителей соответственно множимого (А) и множителя (В). Одновременно на выходе i-го разряда динамического регистра 10 вырабатывают сигнал управления, который поступает на вход синхронизации i-x разрядов регистра обоих сомножителей и разрешает ввод значений поступивших бит сомножителей в i-e разряды регистров первого

1 и второго 2 сомножителей, На сигнале управления с входа 11 синхронизации устройства, i разряды обоих регистров сомножителей, а также оба триггера 7 и 8 установят в состоянии соответствующих бит сомножителей. Работу устройства начинают с подачи младших п-х разрядов, Первые входы х-х (i=1 и) элементов И первой 3 и второй 4 групп поразрядно подключены к i-м (i=i,n) выходам регистров первого 1 и второго 2 сомножителей, вторые входы элементов И объединены и подключены к выходам второго 8 и первого 7 соответственно триггеров устройства, а третьи входы - к входу 11 синхронизации устройства через инвертор 6 непосредственно, а выходы элементов

И первой 3 и второй 4 групп поразрядно, через первый и второй соответственно входы элементов ИЛИ группы 9 подключены к i-м (i=1,n) входам блока 5 суммирования.! 735843 передачу в блок 5 суммирования 1-х частичных произведений, сформированных в обоих регистрах сомножителей.

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

5 суммирования частичных произведений, сформированных в регистрах первого 1 и второго 2 сомножителей, выходы которых соединены с первыми входами элементов И. Таким образом, частичные произведения от кода множимого (А), сформированного на регистре

2О первого 1 сомножителя, заносят в блок 5 суммирования на противофазе (c) и при единичном состоянии текуще" го i-го разряда кода множителя во втором триггере Я, а частичные произведения от кода множителя (В), сформированного в регистре второго сомножителя 2, заносят в блок 5 суммирования на фа.зе (() и при единичном состоянии текущего i-ro разряда кода множимого в первом триггере 7. зо

Работа устройства начинается, когда на вход 11 синхронизации (тактовый вход) устройства подают фазу ()

) на которой всегда заносят текущие разряды кодов сомножителей в первый 7 и второй 8 триггеры, а также в регистры первого 1 и второго 2 сомножителей, При такой организации связей в течение всей процедуры умножения

40 будет иметь место отставание в занесении частичного произведения от кода множителя, сформированного в регистре второго 2 сомножителя, так как в этот момент каждый элемент И 4 ф5 группы элементов по третьему входу будет открыт сигналом с входа tl синхронизации устройства, а выходы с регистра второго 2 сомножителя отражают состояние регистра до момен$Q та переключения, т.е. состояние предыдущего -ro такта.

Состояния текущих i- разрядов кодов множимого (А) и множителя (В),. которые запомнены на один такт в пе- первом 7 и втором 8 триггерах устройства на i такте работы через вторые входы первой 3 и второй 4 групп элементов И разрешают или запрещают

Устройство реализует новый алгоритм умножения чисел младшими разрядами вперед. Запишем процедуру формирования частичного произведения от кода множимого (4ПА;) и множителя (4ПВ ) при умножении двух чисел А В в виде матрицы

1735о4 а Ь„(-) (a.b„

a„((b> )Ln).ã = О

Ь„{(Я„)Ь„)2 = а; b 2 г< -и

2 у Р., и (b„„„ a,,(-,Ь„,,Ь„)

"3 д.g (а„,а„,,а ) л a,(-,b,...,b„) . а

Ь, (а,а,. ° . «aÄ) л а (-,b,,...,b„)

"" (Ь (а„, а <,...,а „) {-, b„) (a „,,а„) }2

) 2 и

А В 2 (а;(Вь;,) + Ь;(А L )) i f,п, а

««О

I где L; — сдвиг на i раэрядов влево А ia а

В . (Ь «Ь««; ° ° «b„j Ь! 2, bz 2 ° ° ° ° «b„2 ««} а(BL>«) 2, i nо;

Ь..(А1.;) 2, i - й«о.

О...«а„)= а, 2, а, 2 ...,,а„ ° 2 )

Сформируем частичные произведения О смотрим конкретный пример: А В по укаэанному правилу. Для этого рас- = 0,101x0,011 = 0,001111 = 15/64

0.001111 в котором первым частичным произведением на каждом такте стоит ЧПВ„ (от кода множителя), а на втором - ЧПА (от кода множимого). Из примера видно отставание во вводе ЧПА, "и ЧПВ „, Блок 5 суммирования состоит иэ и комбинационных, например, одноразрядных сумматоров, у которых в каждом -м один вход подключен к выходу со" ответствующего i-го разряда груп-.. пы элементов ИЛИ 9, второй входк выходу переноса сумматора данного ,- разряда, третий вход - к выходу результата предыдущего (старшего, (i+1)-ro i=2,n) разряда. Выход результата младшего разряда блока суммирования может быть подключен к наружному выходу устройства (или к входу регистра сдвига, если в устройстве предусмотрено запоминание всех 2 разрядов кода результата умножения чисел А В).

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

35 разряда кода результата на первом такте операции умножения. В течение первых и"тактов вырабатывают все п-.÷àñòè÷íûå произведения и получают младшие разряды результата . Последу"

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

Введение триггеров, элементов

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

Формула изобретения устройство для умножения и-раз-: рядных чисел, содержащее и-разрядные

173584 регистры первого и второго сомножителей, первую и вторую группу из и и п-1 элементов И соответственно и и-разрядный блок суммирования (n5 разрядность сомножителей), причем выход i-го разряда регистра первого сомножителя соединен с первым входом i-го элемента И первой группы (i 1,...,n), выход j-ro разряда регистра второго сомножителя соединен с первым входом j-ro элемента

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

И первой. группы „ выходы которых соедйнены с первыми входами соответствующих элементов ИЛИ группы, вторые входы которых соединены C выходами соответствующих элементов И второй группы, вторЬ|е входы которых соединены с выходом первого триггера, вход синхронизации которого соединен с входами синхронизации второго триггера и устройства, с третьими входами элементов И второй группы и входом элемента НЕ, выход которого соединен с третьими входами и элементов И первой группы, выход i-го элемента ИЛИ группы соединен с i-м входом и-разрядного блока суммирования, выходы которого соединены с выходами результата устройства.

1735843

Составитель Ю. Ледянкин

Техред Л,Олийнык Корректор H. Самборская

° а Фа »юа ° Ю

Тираж Подписное комитета по изобретениям и открытиям при ГЕНТ СССР

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

Редактор Л. Гратилло

Заказ 1816

ВНИИПИ Государственного

113035, Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 191