Устройство для умножения чисел
Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел, удобных для изготовления с применением БИС, и является усовершенствованием изобретения по авт. св. № 1322265. Целью изобретения является повышение быстродействия устройства за счет сокращения длительности такта. Устройство содержит регистр 1 множимого, блоки 2 вычисления разрядных значений произведения, две группы буферных регистров 3,4,блок 5 приведения и нововведенные лп дополнительных блоков 8 приведения.4 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ ПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 4 фь 0 (л) 4 17 (61) 1322265 (21) 4775567/24 (22) 29,12.89 (46) 07,07.92. Бюл. N. 25 (71) Научно-исследовательский институт электронных вычислительных машин (72) А.А.Шостак и В.B.ßñêåâè÷ (53) 681.325(088.8) (56) Авторское свидетельство СССР N 1322265, кл. G 06 F 7/52, 1985. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано при „„SU „„1746377 А2 разработке быстродействующих устройств умножения чисел, удобных для изготовления с применением БИС, и является усовершенствованием изобретения по авт. cs. N 1322265, Целью изобретения является повышение быстродействия устройства за счет сокращения длительности такта. Устройство содержит регистр 1 множимого, блоки 2 вычисления разрядных значений произведения, две группы буферных регистров 3,4, блок 5 приведения и нововведенные m дополни.т ельных блоков 8 приведения. 4 ил, 1746377 40 Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел, представленных в любой позиционной системе счислений, и является усовершенствованием основного изобретения по авт, св. ¹ 1322265. Особенно эффективно его применение при использовании БИС и СБИС. Известно устройство для умножения чисел, содержащее регистр множимого, и блоков вычисления разрядных значений произведения (и — число разрядов множимого), и буферных регистров первой группы, и буферных регистров второй группы и блок приведения, в состав которого входят узел суммирования и реглстр задержки, причем вход множимого i-го блока вычисления разрядных значений произведения (.= 1,...n) соединен с выходом i-го разряда регистра множимого, вход множителя — с входом множителя устройства, вход первого слагаемого — с выходом i-ro буферного регистра первой группы, вход второго слагаемого — с выходом (i + 1)-го буферного регистра второй группы, выходы старшего и младшего, разрядов i-ro блока вычисления разрядных значений произведения соединены соответственно с входами I-x буферных регистров первой и второй групп, выход первого буферного регистра второй группы соединен с входом первого слагаемого узла суммирования, вход второго слагаемого которого соединен с выходом регистра задержки, вход которого соединен с выходом переноса узла суммирования, выход суммы которого является выходом устройства, Это устройство предназначено для перемножения чисел в любой позиционной системе счисления с основанием N > 2, в частности. в в-ично кодированной системе счисления с основанием И=к (в-ичные разряды группируются по к, где к — целое число и больше единицы), причем блоки вычисления разрядных значений произведения формируют на своих выходах старшие и младшие разряды произведения в многорядном коде, а блок приведения преобразует этот многорядный код в однорядный результат. С целью повышения быстродействия устройства необходимо стремиться к сокращению задержки на блоках вычисления разрядных значений произведения. что достигается увеличением рядности формируемых на их выходах разрядных произведений. Однако при этом возрастает задержка на блоке приведения, что ограничивает быстродействие устройства и является его недостатком. Цель изобретения — повышение быстродействия устройства за счет выполнения преобразования многорядного кода разрядов произведения, формируемых на выходе первого буферного регистра второй группы, е однорядные разряды результата с помощью нескольких блоков приведения, задержка на каждом из которых согласована с задержкой на блоках вычисления разрядных значений произведения. Поставленная цель достигается тем, что устройство для умножения чисел содержит m дополнительных блоков приведения (m = 1,2,3...), состоящих из узла суммирования, регистра задержки и буферного регистра, причем в каждом дополнительном блоке приведения выход буферного регистра соединен с входом первого слагаемого узла суммирования, вход второго слагаемого которого соединен с выходом регистра задержки; вход которого соединен с выходом переноса узла суммирования, выход суммы узла суммирования j -го дополнительного блока приведения (j = 2,...,m) соединен с входом буферного регистра (j - 1-ro дополнительного блока приведения, вход буферного регистра m-ro дополнительного блока приведения соединен с выходом суммы узла суммирован я блока приведения, выход суммы узла суммирования первого дополнительного блока приведения является выходом устройства. На фиг.1 изображена структурная схема устройства для умно>кения чисел; на фиг.2 — массив слагаемых для случая двоично-кодированной 2 - 256 - ричной системы счисления (в=2,к=-8), которыи суммируется каждым блоком вычисления разрядных значений произведения до тех пор, пока на его выходах не получатся старшая и младшая цифры разрядного произведения в шестирядно л коде; на фиг.3 — процесс суммирования массива слагаемых фиг.2 в каждом блоке вычисления разрядных значений произведения на фиг.4 — процесс приведения шестирядного кода разрядов произведения, формируемых на выходе первого буферного регистра второй группы, к двухрядному коду в блоке г риведения с учетом содержимого его регистра задержки, Устройство для умножения чисел (фиг.1) содержит A-ðàçðëäíûé регистр 1 множимого, n блоков 2 вычисления разрядных значений произведения, и буферных регистров 3 первой группы, и буферных регистров 4 второй группы, блок 5 приведения. состоящий из узла 6 суммирования и регистра 7 задержки, m дополнительных блоков 8 приведения (m = 1,2,3...), состоящих из узла 9 суммирования, регистра 10 задер>к,и и by1746377 F=XY+A+ В, 55 где Х,Y — значения множимого и множителя на соответствующих входах блока 2; А, — значения первого и второго слагаемых блока 2 соответственно. ферного регистра 11. вход 12 коррекции, вход 13 множителя устройства и выход 14 устройства, В ход множимого i-го блока 2 (I : 1,...п) соединен с выходом 15 i-го разряда регистра 1, вход множителя — с входом 13 5 множителя устройства, вход первого слагаемого — с выходом i-го регистра 3, вход второго слагаемого — с выходом (i + 1)-ro регистра 4, выход 16 старшего разряда i-ro блока 2 соединен с входом I-го регистра 3, 10 выход 17 младшего разряда — с входом i-ro регистра 4, вход второго слагаемого и-го блока 2 соединен с входом 12 коррекции устройства, выход первого регистра 4 соединен с входом первого слагаемого узла 6 15 суммирования, вход второго слагаемого которого соединен с выходом регистра 7 задержки, вход которого соединен с выходом 18 переноса узла 6 суммирования, выход 19 суммы которого соединен с входом буфер- 20 ного регистра 11 m-ro блока 8 приведения, в каждом блоке 8 выход 20 буферного регистра 11 соединен с входом первого слагаемого узла 9 суммирования, вход второго слагаемого которого соединен с выходом 25 регистра 10 задержки, вход которого соединен с выходом 21 переноса узла 9 суммирования, выход 22 суммы узла суммирования -ro блока 8 в (i= 2,...,m) соединен с входом буферного регистра 11 j - 1)-го блока 8, вы- 30 ход 22 узла 9 суммирования первого блока 8 подключен к выходу 14 устройства, Совокупность I-ro блока 2 вычисления разрядных значений произведения и i-x буферных регистров 3 и 4 может быть конст- 35 руктивно выполнена в виде единого модуля 23, реализованного. например, как большая интегральная схема. В этот модуль можно включить соответствующий разряд регистра 1 множимого, чем обеспечивается луч- 40 шая однородность структуры устройства. В устройстве регистр 1 множимого, буферные регистры 3 и 4, регистры 7 и 10 задержки блоков 5,8 приведения соответственно, а также буферные регистры 11 бло- 45 ков 8 могут быть пристроены на двухтактных синхронных 0-триггерах (цепи синхронизации и установки в исходное состояние на чертеже условно не показаны). Каждый блок 2 вычисления разрядных 50 значений произведения является комбинационной схемой, выполняющей следующую функцию: На фиг.2 для случая двоична кодированной 2 -256- ричной системы счисления и e . 8 предложении, что старшая и младшая цифры разрядного произведения блока 2 формируются в шестирядном коде, приведен массив слагаемых, который суммируется каждым блоком 2 вычисления разрядных значений произведения устройства. Первое слагаемое А блока 2 изображено знаками "+", второе слагаемое  — знаками "X", а массив частичных произведений, образующийся в блоке 2 в результате перемножения сомножителей Х, Y. изображен в виде матрицы точек. Фиг.3 иллюстрирует процесс суммирования в блоке 2 массива слагаемых, показанного на фиг.2. Суммирование осуществляется по так называемому "экономичному" алгоритму сворачивания пятнадцатирядного кода к шестирядному с использованием одноразрядных двоичных сумматоров и полусумматоров. Те двоичные разряды слагаемых массива, которые обрабатываются одним и тем же одноразрядным двоичным сумматором или полусумматорами, обведены овальной линией, Как видно на фиг.3 преобразование исходного пятнадцатирядного кода к шестирядному осуществляется на три шага I-ill. В результате этого на выходах 16 и 17 блока 2 формируются„в шестирядном коде старшая и младшая 2"256-ричные цифры его разрядного произведения, На реализацию блока 2 в рассматриваемом с,.учае гребуе. ся 64 двухвходовых элемен,ов И (для формирования частичных произведений множимого X ua множитель Y), 64 одноразрядных двоичных сумматоров и 10 полусумматоров, Блок 5 предназначен для преобразования многорядного кода результата, формируемого s процессе умножения в первом буферном регистре 4 второй группы, к коду меньшей рядности. Рядность информации на выходе узла 6 суммирования блока 5 зависит от скорости, с которой должно быть выполнено это преобразование и которая должна быть согласована со скоростью вычисления разрядных произведений блоками 2. T.е. блок 5. в состав которого входят узел 6 суммирования и регистр 7 задержки, должен осуществлять преобразование информации за число шагов, м .:ьшее или равное числу шагов блока 2 разрядных значений произведения. На фиг.4 изображен процесс суммирования в узле 6 массива слагаемых, образованного шестирядным кодом произведения сомножителей (этот код поступает с выхода первого регистра 4) и двухрядных кодом информации, хранимой в регистре 7 задержки, Алгоритм сворачивания и условные обозна1746377 чения аналогичны используемым на фиг.3. Как видно из фиг.4, преобразование восьмирядного кода к двухрядному осуществляется за три шага I-III, что обеспечивает задержку на блоке 5, равную задержке на блоке 2. В этом случае для реализации узла 6 суммирования требуется 32 одноразрядных двоичных сумматоров. Каждый блок 8 предназначен для приведения многорядного кода информации. хранящейся в его буферном регистре 11 и регистре 10 задержки к коду меньшей рядности (для первого блока 8 — к однорядному коду результата) на выходе 32 узла 9 суммирования. Блоки 8 содержат по узлу 9 суммирования, регистру 10 задержки и буферному регистру 11, причем каждый узел 9 суммирования должен обеспечивать задержку на преобразование кодов, меньшую или равную задержке на блоках 2 вычисления разрядных значений произведения. В рассматриваемом примере в устройстве используется один блок 8 приведения, в котором в качестве узла 9 суммирования используется 8-разрядный двухвходовой сумматор с ускоренным переносом. Устройство для умножения чисел работает следующим образом. В исходном состоянии буферные регистры 3 и 4, регистр 7 задержки блока 5 приведения, регистры 1, задержки и буферные регистры 11 дополнительных блоков 8 приведения обнулены, в регистре 1 множимого хранится без знака и-разрядный 2"-ичный код множимого (n.ê — разрядный двоичный код множимого). Здесь предполагается, что множимое и множитель представлены в двоично-кодированной 2"-ичной системе счисления. т.е. каждый разряд как множимого, так и множителя представляет собой набор из к двоичных цифр. Умножение в устройстве осуществляется за 2n+m тактов. В каждом из и первых тактов работы устройства на его вход 13 поступает параллельно к двоичных разрядов множителя, начиная с младших разрядов, При этом в i-M блоке 2 вычисления разрядных значений произведения осуществляется умножение к двоичных разрядов множимого, поступающих на его вход множимого с выхода 15 i-го разряда регистра 1, на.к двоичных разрядов множителя, поступающих на его вход множителя с входа 13 устройства, и прибавление к k младшим двоичным разрядам получившегося при этом 2.к разрядного произведения через входы первого и второго слагаемых блока 2 соответственно старшего разряда произведения i-ro блока 2, сформированного в предыдущем такте и 15 хранимого в -м регистре 3 и младшего разряда произведения (i + 1)-го блока 2, сформированного в предыдущем также и хранимого в (i + 1)-м регистре 4. Сформированные -м блоком 2 старший и младший разряды произведения в многорядном коде с его выходов 16 и 17 в конце каждого такта записываются соответственно в i-тые буферные регистры 3 и 4. Одновременно с работой блоков 2 вычисления разрядных значений произведения работают и блоки 5 и 8 приведения, которые осуществляют последовательное преобразование многорядного кода, формируемого в процессе умножения в первом буферном регистре 4 (исходная информация для блока 5 приведения), а также получаемого в процессе приведения и хранимого в регистрах 10 и 11 соответствующих блоков 8 приведения. В 20 конце каждого такта в регистры 10 и 11 записываются результаты вычислений соответствуюших блоков 5 и 8 приведения. После выполнения и первых тактов работы устройства на его вход 13 множителя 25 поступает нулевая информация и далее осуществляется еще дополнительно (n+ m) тактов, в течение которых из устройства выводится с соответствующим преобразованием информация, хранимая в буферных 30 регистрах 3 и 4. а также в регистрах 7 и 10 задержки блоков 5 и 8 приведения и буфер,ных регистров 11 блоков 8. Вывод 2.п разрядного и роизведения в устройстве осуществляется через его выход 14 в парал35 лельно-последовательном коде по к двоичных разрядов в каждом такте, начиная с (m + 1)-ro такта работы устройства (в первых m . тактах работы устройства младший разряд результата последовательно переписыва40 ются с соответствующим преобразованием из первого буферного регистра 4 в буферные регистры 11 m блоков 8 приведения). В рассмотренном случае на вход 12 коррекции устройства во всех его 2n + m тактах 45 подавалась нулевая информация. В тех же случаях, когда требуется получить округленное и-разрядное произведение, необходимо в первом такте работы устройства на его вход 12 коррекции подать к-разрядный дво50 100,....000 ичный код Это позволяет К осуществить округление без дополнительных временных затрат. Используя определенным образом вход 12 коррекции 55 устройства можно одновременно выполнять в нем операцию умножения и-разрядных числе с подсуммированием к и старшим разрядам произведения некоторого и -разрядного слагаемого или группы слагаемых. Вход 12 устройства может быть также эф10 1746377 Устройство для умножения чисел, по авт. св. N 11332222226655, о т л и ч а ю щ е е с я тем, 5 что, с целью повышения быстродействия, оно содержит m дополнительных блоков приведения (m = 1,2,3,...), состоящих каждый из узла суммирования, регистра задержки и буферного регистра, причем в каждом до10 полнительном блоке приведения выход буферного регистра соединен с входом первого слагаемого узла суммирования, вход второго слагаемого которого соединен с выходом регистра задержки, вход которо15 ro соединен с выходом переноса узла сум мирования, выход суммы узла суммирования j -го дополнительного блока приведения (j = 2,...m) соединен с входом буферного регистра (j — 1)-го дополнитель20 ного блока приведения, вход буферного регистра m-ro дополнительного блока приведения — с выходом суммы узла суммирования блока приведения, выход суммы узла суммирования первого дополнительного 25 блока приведения является выходом устройства, +++ 1 + ++ ++.++ . +++++ ++++++ +++++++ Х ХХ ХХХХХ ХХХ ХХХХХ ХХХ ХXX.XX X, X Q Х, Х Х Х, : ХХ Хх ХХ Х ХХАХXXX> е е ° е е е е е ° е э е е е е е ° 4 4 Е 4 е Е Е ° ° 4 ° е е ° е фективно использован для введения коррекции по знакам при умножении чисел в дополнительном коде, Следует особо отметить, что умножение и-разрядных в устройстве (как и в известном) может быть выполнен и за (и+ 1) тактов, если после выполнения и-ro такта содержимое буферных регистров 3 и 4, регистра 7 задержки блока 5, регистров 10 задержки и буферных регистров 11 блоков 8 подать для окончательного суммирования на соответствующие входы быстродействующего многовходового блока суммирования (на фиг.1 такой блок суммирования и соответствующие связи показаны штриховой линией).. Технико-зкономическое преимущество устройства для умножения чисел в сравнении с прототипом заключается в его более высоком быстродействии (при вычислении и роизведе н и я 64-раз рядн ых сомножителей. представленных в двоично-кодированной 2 - ричной системе счисления и в предложении, что старшие и младшие цифры разрядных произведений формируются в шестирядном коде, устройство примерно в 1,8 раз быстрее известного). Формула изобретения 1746377 :BEI0EIE ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° :ooooIj 0:: ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° Э ° ° Ф ° ° ° Ф ° ° ° ° ° ° ° ° е ° e ° е ° ° % ° е ° ° е ° ° ° ° Э ° Ф ° Ф ° ° O ° ° ° ° Ф ° Ф ° ° ° ° Ф ° ° Ф Е ° ° ° ° О ° ° ° Ф ° ° 1 е ° ° е 4 ° ° ° ° ° 4 ° ° ° ° ° ° /8 Ю Составитель А.Шостэк Техред M.Ìîðãåèòàë Корректор Н.Милюкова Редактор Н.Химчук Заказ 2395: Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушскэя наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 Ф Ф ° Ф ° ° 4 ° Ф е ° ° ° ° ° Ф ° Э ° Ф O O O ° ° ° ° ° ° Ф ° В ВП В EIR В0 ВВВВВЯЩ 
