Множительное устройство Советский патент 1983 года по МПК G06F7/52 

Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств для умножения чисел, представленных в двоично-десятичной системе счисления. Известно множительное устройство, содержащее накопитель (блок формирования произведения) и осуществляквдее умножение множимого Хна множитель 1| у„.,. у , причем в предварительно очищенный накопитель множимоех прибавляется у, раз, затем оно адви гается влево на один разряд и вновьприбавляется в накопитель у, раз и так до тех пор, пока не будут обработаны все разряды множителя ij Г . Недостатком устройства является низкое быстродействие, особенно при умножении десятичных чисел. Так, для перемножения двух н -разрядных десятичных чисел в известном устройстве требуется время, примерно ра.вно . см Де tev - время суммирования двух и -разрядных десятичных чи сел, Здесь предполагалось, что цифры О, 1,2,..., 9 появляются во всех разрядах множителя у с равной вероятностью. Известно однотактное множительное устройство, содержащее П -разрядные регистры множимого и множителя, матрицу из и одноразрядных умножителей и множество одноразрядных сумматоров для суг/1г шрования разрядных произве-. дений 2 . Хотя устройство и отличается высоКИМ быстродействием, однако оно имее следующие существенные недостатки. Во-первых, на этом устройстве.нельзя наряду с умножением десятичных чисел выполнять улшожение и двоичных чисел а поэтому оно не может найти широк1эго применения в современных ЭВМ общего назначения, использующих как десятичную, так и двоичную систему счисления З. Во-вторых, устройство требует для своей реализации очень большого объема оборудования. Наиболее близким к изоЬретению является множительное устройство, со держащее и -разрядный регистр множителя 1м -разрядность десятичных сомножителей), (и + 1) -разрядный ..регистр множимого со схемой удвоения, блок сдвига, блок суммирования и блок управления, причем входы блока управления соедв нены с выходами регшзтрамножителя, а выходы подключены к управляющим входам регистров множимого и множителя, а также к управляющим входам блока сдвига с соответствующими входами блока суммирования, выход которого является выходом устройства М . В известном устройстве реализуется алгоритм десятично-двоичного умножения двоично-десятичных чисел 5j и ; |Время перемножения двух и -разрядных десятичных чисел примерно равно С ,.в/ , где t (4j - время суммирования двух 2ii -разрядных десятичных ч чисел, ebifli время, затрачиваемое на выделение единиц/из двоично-десятичного кода множителя , tq - время выполнения удвоения (умножения на два) множимого в регистре множимогоJ 1,5-и- составляющая,определяющая среднее число единиц в двоично. десятичном коде множителя, Известное устройство при несущест-, венных изменениях может быть исполь-; I зовано и для умножения двоичных чи- ; сед. Поэтому в дальнейщем будем предполагать, что оно позволяет перемножать наряду с десятичными числами и двоичные. Основным недостатком известного устройства является относительно низ- кое быстродействие. Цель изобретения - повышение быстродействия множительного устройства. Поставленная цель достигается/ тем, что, в множительное устройство, содержащее ti -разрядный регистр ьшожителя (п - разрядность десятичных .сомножителей г { -разрядный регнотр множимого со схемой удвоения, блок суммирования, выход которого является выходом устройства, введены матрица из (и t О 1 узлов тетрадного умножения г 2 и узлов тетрадного суммирования, 2п буферных регистров, 2 И коммутаторов и 2ч узлоВ , преобразования двоичного кода в десятичный, причем перв;ыё входы узлов тетрадного умножения матрицы соеди-- нены с выходами соответствующих тбтрад регистра множимого, а вторые входы - с выходами младших разрядов соответствующих тетрад регистра множителя, входы узлов тетрадного суммирования соединены с выходами соответствующих буферных регистров и узлов тетрадного умножения, а выходы соединены с входами соответствукяцих буферных регистров и узлов преобразования двоичного кода в десятичный, а также с первыми входами соответствующих коммутаторов, выходы узлов преобразования двоичного кода вдесятичный соединены с вторыми входами соответствукяцих коммутаторов, выходы которых соединены с равновесовыми входами блока суммирования управляющие входы коммутаторов и блока суммирования, а также, первый управлякнций вход регистра множимого

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

. На фиг.1 приведена структурная схема предлагаемого множительного i устройcTBaj на фиг.2 и 3 - возможные варианты реализации узла тетрад- ного суммирования,. Ю

Устройство содержит фиг. ц разрядный регистр 1 множителя (и {разрядность десятичных сомножителей) , П 4 1)-разрядный регистр 2 множимого со схемой удвоения (схема удвоения 15 не показана , матрицу 3 из(И4)n узлов 4 тетрадного умножения, 2п узлов 5 тетрадного суммирования, 2м буферных регистров &, 2 и узлов 7 . преобразования двоичного кода в де- 20 сятичный, 2 коммутаторов 8, блок 9 суммирования, вход 10 режима работы устройства, вход 11 синхронизации и выход 12 устройства. Первые входы узлов 4 тетрадного умножения матрицы 3 25

.соединены с выходами соответствующих тетрад регистра 2 множимого, а вторые входы соединены с выходами младших разрядов соответствующих тетрад регистра 1 множителя, входы узлов 5 ,« тетрадного суммирования соединены- с выходами соответствующих буферных регистров б и узлов 4 тетрадного умножения, а выходы соединены с входами соответствующих буферных регистров 6 и узлов 7 преобразования двоичного кода в деся5гичный, а также с первыми входами соответствующих коммутаторов 8, выходы УЗЛОВ 7 преобразования двоичного кода в десятичный 7 соедине1Ны с вторыми входами соответствующих 40 коммутаторов 8, выходы которых соединены с равновесовыми входами блокЭ;-9 суммирования, управляквдие входы коммутаторов 8 и блока 9 суммирования, а также первый управляющий вход ре- 45 гистра 2 множимого соединены с входом 10 режима работы устройства, управляющие входы буферных регистров б и регистра 1 множителя, а также второй управляющий вход регистра 2 50 1« ножимого соединены с входом 11 сйнт хронизации устройства.

Вход 10 режима работы предназначен для настройки устройства на умножение двоичных или десятичных к сел. Так,например, если на этом присутствует высокий потенциалу;

устройство выполняет умножение двоичных чисел, S противном случае оно настраивается на перемножение деся- , тичных чисел. Вход 11 устройства яв.ляется синхронизирующим. По сигналу на этом входе осуществляются одновременно сдвиг информации на один двоичный разряд в тетрадах регистра 1 .множителя в сторону их младших 65

разрядов, удвоение содержимого регистра 2 множимого и .прием информации в буферные регистры 6 устройства. Регистр.1 множителя может быть построен на двухтактных синхрбнных D-триггерах. В нем должны быть предусмотрены цепи сдвига информации на один двоичный разряд в направлении к младшим .разрядам либо во всех двоичных разрядах, либо только в двоичных разрядахтетрад. Регистр 2 множимого -(ni--) -разрядный. Дополнительнйй () -ый разряд (тетрада) введен с целью устранения искажения информации в регистре 2 множимого пос ле выполнения в нем многократного уявоения (содержимое регистра 2 множимого в процессе умножения три раза удваивается, т.е. в результате оно умножается на восемь). Этот регистр, так же как и регистр 1 множителя, может быть реализован на двухтактных синхронных D -триггерах. Схема удвоения в регистре 2 может быть-разработана как в известном устройстве.В узлах 4 тетрадного умножения матрицы 3 формируются произведения содержимого соответствующей тетрады регистра 2 множимого на значение младшего разряда соответствующей

.тетрады регистра 1 множителя. Каждый: узел 4 может быть реализован на четырех двухвходовых элементах И.

Все узлы 5 «тетрадногосуммирования являются узлагли комбинационного типа. В каждом такте работы устройства в этих узлах осуществляется cyм 1иpoвaние тетрадных произведений, сформированных в данном такте на выходах соответствующих узлов 4 тетрадного умножения, и прибавление к получившемуся при этом результату содержимого соответствующего буферного регистра 6, сфоргушрованного на предыдущем такте работы устройства. Так как в узлги 5 тетрадного суглмирования, расположенных в разных весовых позициях, суш/мруется разное число тетрадных произведений, схемные структуры их будут несколько отличаться (это справедливо в отношении буферных регистров 6, узлов 7 преобразования двоичного кода в десятичный и коммутато;ров 8) . Поэтому детально рассмотрим схеглные структуры узлов, расположенных только во второй весовой позиции (первая весовая позиция имеет наименьший вес) . Рассмотрение схемной структуры узла 5 тетрадного суммирования будет вестись совместно с анализом схемной структуры буферного регистра 6. Первоначально оценим минимальную разрядность буферного регистра б. Она должна определяться при условии что устройство обрабатывает двоичные операнды, так как при умножении десятичных чисел разрядность буферного регистра может быть и мен шей . В верхнем узле 7 тетрадного ум ножения, расположенном на второй ве совой позиции, в течение первых тре тактов работы устройства формируютс следующие максимально возможные зна чения тетрадных произведений 1-111, 1111 и 1111 (сумма этих произведени равна 101101), в то время, как в ни нем узле 4 образуются произведения nil, 1110 и 1100 (их сумма равна 101001). Здесь не учитывались тетра ные произведения, которые формируют ся в последнем (четвертом) такте работы устройства, так как в этом такте в буферный регистр 6 не произ водится запись информации. Итак, на выходе узла 5 тетрадного суммирован в третьем- такте работы устройства н может быть сформирован результат, превышающий значение 101101+101001 1010110, а следовательно, разрядность буферного регистра б может быть выбрана равной семи. Аналогичн можно показать, что при умножении десятичных чисел достаточно исполь.|3овать шестйраз рядный буферный регистр б. С учетом Э.ТОГО на фиг.2 пр ведена функциональная схема, узла 5 тетрадного суммирования совместно со схемой буферного регистра б, который включает семь двухтактных синхронных D -триггеров 15. Узел тетрадного суммирования 5 содержит четыре одноразрядных двоичных сумматора 13 и шёстиразрядный двоичный комбинационный сумматор 14 с ускоренным образованием разрядных пере. носов. По шинам 16 и 17 на входы узла 5 тетрадного суммирования поступают произведения, сформированны на выходах соответственно верхнего - и нижнего узлов 4 тетрадного умножения. В каждом такте работы устрой ства в узле 5 тетрадного суммирования производится сложение трех слагаемых: первого тетрадного произведения, поступающего по шинам 16-; . второго тетрадного произведения,подаваемого по шинам 17; содержимого буферного регистра 6. Получившийся при этом в узле 5 результат записывается в буферный регистр б с разрешения сигнала на входе11 синхронизации устройства (в последнем четвертом такте работы устройства запись информации в буферный, регист б не производится). Вариант реализации узла 5 (фиг.З позволяет обеспечить более высокое быстродействие устройства для умножения чисел. Согласно этому варианту узел 5 тетр.адного суммирования содержит каскад 18 одноразрядных двоичных сумматоров 13, на выходе которого сум1«1а тетрадных произведений формируется в двухрядном коде /разрядные суммы записываются в верх НИИ ряд триггеров 15 регистра 6, а , разрядные переносы - в нижний ряд триггеров 15). Более высокое оыстродействие узла 5 тетрадного суммирования обеспечивается тем, что в первых трех тактах работы устройства в нем не осуществляется приведение двухрядного.кода в однорядный (на что, как правило, требуется существенное время), и только в последнем такте работы устройства двухрядный код приводится к однорядному на комбинационном сумматоре 19 с ускоренным образованием разрядных переносов. Подобным образом могут быть разработы другие схемные структуры узлов 5 тетрадного суммирования. Результаты, оформленные на выходах узлов 7 преобразования двоичного кода в десятичный, используются в устройстве только в десятичного умножения. Эти узлы предназначены для «реобр азования двоичного кода, сформированного на выходе соответствующего узла 5 тетрадного суммирования в последнем такте работы устройства., в двоично- десятичный код (н пример, в код 8421). Они могут быть построены с использованием быстродействующих ПЗУ по таблицам истинности известными методами . Для определенности детально рассмотрим синтез узла 7, расположенного НА второй весовой позиции устройства. Сначала необходимо определить/ , к.акое максимальное значение двЬичного кода должен -преобразовывать этот узел. При этом будем руководствоваться следующим, В верхнем узле 4 тетрадного умножения, расположенном на второй весовой позиции, в течение четырех тактов работы устройства при умножении десятичных чисел могут формироваться следующие максимально возможные значения тетрадных произведений: 0000, 1001, 1001 и 1001,, в то время, как в нижнем узле 4 могут сформироваться только такие хлзксимально возможные произведения:0000,, 1001, 1000 и ОНО (приведенные максимальные значения тетрадных произведений возможны в устройстве только тогда, когда две 1лпадшие цифры множимого равны девяти - код 1001), а две младшие цифры множителя равны семи -(код Olllj. Ввиду этого на выходе узла 5 тетрадного сумгМрования, расположенного на второй весовой позиции, после выполнения четырех тактов не может быть образовано значение двоичного кода, превышающее величину 110010, так как 1001+1001+1,001+1001+1000+0110 (116010)2 (50),(о , А .поэтому узел 7 преобразования двоичного кода в десятичный может быть построен на ПЗУ емкостью в пятьдесят одно семиразрядное двоичное слово. Так, например, если на адресный вход ПЗУ подавать

двоичный код 001111, на его выходе должен формироваться двоично-десятичный код 011.0101, численно равный десятичному коду,- поступающему на адресный вход ПЗУ. Узел 7, расположенный на второй весовой позиции, впрочем как и другие узлы 7 устрой.ства, можно реализовать и на основе

широко применяемых интегральных схем серии К155, в этой серии имеется специальный элемент ПР7 преобразоваНИН Д5ОИЧНОГО кода в десятичный 7j. Коммутаторы 8 в режиме двоичного У1лножения осуществляют подключение к входам блока 9 суммирования -выходов узлов 5 тетрадного суш шрования а в режиме десятичного умножения выходов узлов 7 преобразования двоичного кода в десятичный.

Таким образом, в предлагаемом устройстве узлы 5 и 7, а также буферные регистры 6 и коммутаторы 8, расположенные на разных весовых позициях, будут иметь и разные схемные структуры. При необходимости обеспечения однородности структуры устройства можно ограничиться детальным анализом и синтезом только узлов 5 и 7, буферного регистра 6 и коммутатора 8, расположенных на И -ой весовой позиции, причем эта совокупность может быть конструктивно выполнена в виде единого модуля, используемого на всех весовых позициях устройства и реализованного, например, как большая интегральная схема (на фиг.1этот модуль отмечен штриховыми линиями).

Блок 9 предназначен для окончательного суммирования результатов,

.сформированных на выходах узлов 5 тетрадного суммирования (в режиме ; двоичного умножения или узлов 7 пре образования двоичного кода в десятичный (в режиме десятичного умноуке 1ля} , после выполнения четырёх татов работы устройства. Предполагается, что этот блок комбинационного типа. На его выходе, являющемся и выходом 12 устройства, формируется 2ц -разрядное произведение при умножении десятичных чисел и 8ц-разрядное произведение при умножении двоичных чисел. Схемная структура блока 9 суммирования зависит о разрядности перемножаемых чисел.Так при умножении двухразрядных десятич ных и восьмиразрядных двоичных чисел в качестве блока 9 суммирования

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

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

Множительное устройство работает следующим образом.

Для определенности рассмотрим режим десятичного умножения. В исходном состоянии в регистре 1 множителя хранится Ц -разрядный .множитель, в регистре 2 множимого - П -разрядное множимое, буферные регистры 6 обнулены (здесь не рассматриваются знаки сомножителей, а также предполагается , что сомножители представлены в прямом коде). На входе 10 режима работы устройства присутствует низкий потенциал, означакяг{Ий, что устройство настроено на умножение десятичных чисел. При этом в регистре 2 множимого включены цепи удвоения его содержимого, выходы уз.лов 7 преобразования двоичного кода в десятичный подключены через коммутаторы 8 к соответствующим входам блока 9 суммирования, который, в свою очередь, настроен на суммирование десятичных чисел,

В первом такте работы устройства в узлах 4 матрицы 3 формируются тетрадные произведения, которые в дальнейшем суммируются с учетом занимаемых ими весовых позиций в соответствующих узлах 5 тетрадного суммирования. Первь5й такт работы устройства заканчивается с приходом на вход 11 устройства первого синхроимпульса, по которому производятся одновременно запись результатов с выходов узлов 5 в соответствующие буферные регистры, сдвиг информации на один двоичный разряд в направлении младших разрядов в тетрадах регистра 1 множителя и удвоение содержимого регистра 2 множимого. :

Во втором и третьем тактах устройство работает аналогично.

Основное отличие в работе устройства в четвертом последнем такте состоит в том, что на вход 11 устройства не поступает синхроимпульс, а результаты, сформированные на выхода узлов 5 Тетрадного суммирования, после предварительного их преобразовани в узлах 7 через коммутаторы 8 поступают на соответствующие входы блока суммирования, на выходе которого и формируется окончательное 2г1-разряд ное произведение.

Итак, независимо от разрядности ,перемножаемых чисел, окончательный, результат формируется за; четыре такта, а время умножения двух о -разрядных десятичных чисел составляет вели чину, примерно равную Tl -i4+ -5 2V4 -l-5 tj+tg iq, где tp - задержка информации- в узле с порядковш номером Р- (предполагается, что t и ti 4,-2 , что вполне реально). При умножении двоичных чисел основные отличия в работе устройства состоят в том, что в регистре 2 мнозкимого удвоение его содержимого фактически сводится к простому сдвигу в нем информации на один двоичный разряд влево, блок 9 суммирования на страивается на суммирование двоичных чисел и в последнем (четвертом) такте работы устройства результаты,сфор мированные на выходах узлов 5 тетрад ного суммирования, минуя узлы 7 преобразования двоичного кода в десятич ный, передаются через коглмутаторы 8 на соответствующие входы блока 9 сум мирования. Время умножения .четырех Поразрядных двоичных чисел составляе величину . 3-( В известном устройстве время умножения двух .Ц -разрядных десятичных чисел примерно р авно TS.. в то время, как в предлагаемом уст-, ройстве оно составляет, величину TS 3-i-t4 5 2Ut.4+lg+t7Vt8+-tg. Пусть 11 8, t 14 € ,, tuA8 6(J , 4 , , i2 tt|ABx 6-,7 8- И i9 2tcM 281), где задержка на одном логическом элементе. Тогда , в то время, как t 79, т.е. предлагаемое устройст-; во имеет примерно в 3,5 раза болае высокое быстродействие, чем известное. Умножение двоичных чисел в известном устройстве производится за время (ж . , . 1 ,, а в предлагаемом устройстве это время примерно равно Tf 3(,)H4H5Hg4i. Тогда с учетом принятых допущений получаем, что v.TjV.TtJ:, ,а следовательно, умножение двоичных чисел в предлагаемом устройстве выполняется примерно в 5,2 разабыстрее, чем в известном. Итак, технико-экономическое преимущество предлагаемого множительного устройства в сравнении с известным состоит в значительно более высоком быстродействии. Так, например, перемножение восьмиразрядных десятичных чисел выполняется в нем примерно в 3,5 раза быстрее, чем в известном устройстве. При умножении же двоичных чисел обеспечивается еще больший выигрыш в быстродействии. Так, умножение 52-разрядных Двоичных чисел производится примерно в 5,2 раза быстрее. Вместе и тем, столь существенно увеличениебыстродействия устройства достигается при умеренных затраtax используемого в нем оборудования, так как умножение десятичных чисел выполняется в основном на том же оборудовании, что и двоичных чисел.

/ 7/ 4Г

A ,лпЛ tenA

77

/;

,/7

МНОЖИТЕЛЬНОЕ УСТРОЙСТВО, .; содержащее и -разрядный регистр множителя (И -разрядность десятичных сомножителей) , (и -1)-разрядный регистр множимого со схемой удвоения, блок суммирования, выход которого является выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит MaTjiHцу из(и t () ttузлов тетрадного умножения, 2 И узлов тетрадного суммирования , 2 d буферных регистров, 2 И коммут.аторов и 2tiузлов преобразования двоичного кода в десятичный, причем первые входы узлов тетрадного умножения матрицы соединены с выходами соответствующих тетрад регистра множимого, а вторые входы - с выходами младних разрядов соответствующих регистра множителя, входы узлов тетрадного суммирования соединены с (Л выходами соответствующих буферных регистров и узлов тетрадного умножения, а выходы соединены с входами соответствующих буферных регистров и узлов преобразования двоичного кода в десятичный, а также с первыми входами соответствующих коммутаторов, выходы узлов преобразования двоично- : го кода в десятичный соединены с втосд рыми входагли соответствующих коммутаторов, выходы которых соединены с оо равновесовыми входами блока суммирования, управляющие входы коммутаторов и блока cy лмиpoвaния, а также первый управляющий вход регистра множимого 1 ,соединены с входом режима работы устройства, управляющие входы буферных регистров и реги.стра множителя, а также второй управляющий вход регистра множимого соединены с входом синхронизации устройства.

js u u

Tr Tr Tr I

/

L 5U 41

л I

/J j- 7J Г « p

-л/л 41 r y

/

ЙЙ./

16

17

18

.w

I 1

ф ф ф

ffir yj/fff 7 If /(Offftyofffrnff f

76

75

f

/7

u f

Г- fJ

г- fJ

ji

J

ff

/cf

x«f

/«f

Z«J