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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 7 А 2 17 9) ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ПИСАНИЕ ИЗ РЕТЕНИ ТОРСКОМУ СВИДЕТЕЛЬС разработке быстрод умножения чисел, у ния с применением шенствованием изо 1322265, Целью изо вышение быстроде счет сокращения дл ройство содержит блоки 2 вычислени произведения, две стров 3,4, блок 5 при ные и) дополни и ри ведения. 4 ил,%25довательскилительных ма.В.Яскевич инстиин етельство СССР6 Р 7/52, 1985.ДЛЯ УМНОЖЕН ЧИносится к вычислитель- быть использовано при Ъг)5 6 06 Р 7/52 ействующих устройств добных для изготовле- БИС, и является усовербретения по авт. св, М бретения является пойствия устройства за ительности такта. Устрегистр 1 множимого, я разрядных значений руппы буферных реги- ведения и нововведентельных блоков 810 15 20 25 30 35 40 50 Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел, представленных в любой позиционной системе счислений, и является усовершенствованием основного изобретения по авт, св, М 1322265. Особенно эффективно его применение при использовании БИС и СБИС.Известно устройство для умножения чисел, содержащее регистр множимого, и блоков вычисления разрядных значений произведения (и - число разрядов множимого), и буферных регистров первой группы, и буферных регистров второй группы и блок приведения, в состав которого входят узел суммирования и реглстр задержки, причем вход множимого -го блока вычисления разрядных значений произведения ( .= 1,п) соединен с выходом -го разряда регистра множимого, вход множителя - с входом множителя устройства, вход первого слагаемого - с выходом 1-го буферного регистра первой группы, вход второго слагаемого - с выходом . + 1)-го буферного регистра второй группы, выходы старшего и младшего , разрядов -го блока вычисления разрядных значений произведения соединены соответственно с входами 1-х буферных регистров первой и второй групп, выход первого буферного регистра второй группы соединен с входом первого слагаемого узла суммирования, вход второго слагаемого которого соединен с выходом регистра задержки, вход которого соединен с выходом переноса узла суммирования, выход суммы которого является выходом устройства,Это устройство предназначено для перемножения чисел в любой позиционной системе счисления с основанием М 2, в частности, в в-ично кодированной системе счисления с основанием И=к(в-ичные разряды группируются по к, где к - целое число и больше единицы), причем блоки вычисления разрядных значений произведения формируют на своих выходах старшие и младшие разряды произведения в многорядном коде, а блок приведения преобразует этот многорядный код в однорядный результат.С целью повышения быстродействияустройства необходимо стремиться к сокращению задержки на блоках вычисления разрядных значений произведения, что достигается увеличением рядности формируемых на их выходах разрядных произведений. Однако при этом возрастает задеожка на блоке приведения, что ограничивает быстродействие устройства и является его недостатком. Цель изобретения - повышение быстродействия устройства за счет выполнения преобразования многорядного кода разрядов произведения, формируемых на выходе первого буферного регистра второй группы, е однорядные разряды результата с помощью нескольких блоков приведения, задержка на каждом из которых согласована с задержкой на блоках вычисления разрядных значений произведения.Поставленная цель достигается тем, что устройство для умножения чисел содержит гп дополнительных блоков приведения (гп = 1,2,3), состоящих из узла суммирования, регистра задержки и буферного регистра, причем в каждом дополнительном блоке приведения выход буферного регистра соединен с входом первого слагаемого узла суммирования, вход второго слагаемого которого соединен с выходом регистра задержки; вход которого соединен с выходом переноса узла суммирования, выход суммы узла суммирования ) -го дополнительного блока приведения ( ) = 2,гп) соединен с входом буферного регистра ( ) - 1-го дополнительного блока приведения, вход буферного регистра гп-го дополнительного блока приведения соединен с выходом суммы узла суммирования блока приведения, выход суммы узла суммирования первого дополнительного блока приведения является выходом устройства.На фиг.1 изображена структурная схема устройства для умнокения чисел; на фиг.2 - массив слагаемых для случая двоично-кодированной 2- 256 - ричной системы счисления в=2,к=-8), которыи суммируется каждым блоком вычисления разрядных значений произведения до тех пор, пока на его выходах не получатся старшая и младшая цифры разрядного произведения в шестиряднол коде,на фиг.З - процесс суммирования массива слагаемых фиг.2 в каждом блоке вычисления разрядных значений произведения на фиг.4 - процесс приведения шестирядного кода разрядов произведения, формируемых на выходе первого буферного регистра второй группы, к двухрядному коду в блокеприведения с учетом содержимого его регистра задержки,Устройство для умножения чисел (фиг.1) содержит и-разрядный регистр 1 множимо. го, и блоков 2 вычисления разрядных значений произведения, и буферных регистров 3 первой группы, и буферных регистров 4 второй группы, блок 5 приведения, состоящий из узла 6 суммирования и регистра 7 задержки, гп дополнительных блоков 8 приведения (щ = 1,2,3), состоящих из узла 9 суммирования, регистра 10 задеркки и бу.Е=ХУ+А+ В,55 где ХУ - значения множимого и множителя на соответствующих входах блока 2;А,В - значения первого и второго слагаемых блока 2 соответственно. ферного регистра 11, вход 12 коррекции,вход 13 множителя устройства и выход 14устройства, В ход множимого -го блока 2 (: 1 п) соединен с выходом 15 -го разрядарегистра 1, вход множителя - с входом 13 5множителя устройства, вход первого слагаемого - с выходом -го регистра 3, вход второго слагаемого - с выходом ( + 1)-горегистра 4, выход 16 старшего разряда -гоблока 2 соединен с входом -го регистра 3, 10выход 17 младшего разряда - с входом -горегистра 4, вход второго слагаемого и-гоблока 2 соединен с входом 12 коррекцииустройства, выход первого регистра 4 соединен с входом первого слагаемого узла 6 15суммирования, вход второго слагаемого которого соединен с выходом регистра 7 задержки, вход которого соединен с выходом18 переноса узла 6 суммирования, выход 19суммы которого соединен с входом буферного регистра 11 е-го блока 8 приведения,в каждом блоке 8 выход 20 буферного регистра 11 соединен с входом первого слагаемого узла 9 суммирования, вход второгослагаемого которого соединен с выходом 25регистра 10 задержки, вход которого соединен с выходом 21 переноса узла 9 суммирования, выход 22 суммы узла суммирования-го блока 8 в ( = 2 т) соединен с входомбуферного регистра 11 ) - 1)-го блока 8, выход 22 узла 9 суммирования первого блока8 подключен к выходу 14 устройства,Совокупность -го блока 2 вычисленияразрядных значений произведения и -х буферных регистров 3 и 4 может быть конструктивно выполнена в виде единого модуля23, реализованного, например, как большаяинтегральная схема. В этот модуль можновключить соответствующий разряд регистра 1 множимого, чем обеспечивается лучшая однородность структуры устройства.В устройстве регистр 1 множимого, буферные регистры 3 и 4, регистры 7 и 10задержки блоков 5,8 приведения соответственно, а также буферные регистры 11 блоков 8 могут быть пристроены надвухтактных синхронных О-триггерах (цеписинхронизации и установки в исходное состояние на чертеже условно не показаны).Каждый блок 2 вычисления разрядных 50значений произведения является комбинационной схемой, выполняющей следующуюфункцию: На фиг,2 для случая двоична кодированной 2 -256- ричной системы счисления и в8предложении, что старшая и младшая цифры разрядного произведения блока 2 формируются в шестирядном коде, приведен массив слагаемых, который суммируется каждым блоком 2 вычисления разрядных значений произведения устройства. Первое слагаемое А блока 2 изображено знаками "+", второе слагаемое В - знаками "Х", а массив частичных произведений, образующийся в блоке 2 в результате перемножения сомножителей ХУ, изображен в виде матрицы точек, Фиг.З иллюстрирует процесс суммирования в блоке 2 массива слагаемых, показанного на фиг.2. Суммирование осуществляется по так называемому "экономичному" алгоритму сворачивания пятнадцатирядного кода к шестирядному с использованием одноразрядных двоичных сумматоров и полусумматоров. Те двоичные разряды слагаемых массива, которые обрабатываются одним и тем же одноразрядным двоичным сумматором или полусумматорами, обведены овальной линией, Как видно на фиг.З преобразование исходного пятнадцатирядного кода к шестирядному осуществляется на три шага - , В результате этого на выходах 16 и 17 блока 2 формируютсяв шестирядном коде старшая и младшая 2"- 256-ричные цифры его разрядного произведения, На реализацию блока 2 в рассматриваемом сучае гребуе, ся 64 двухвходовых элемен,ов И (для формирования частичных произведений множимого Х на множитель У), 64 одноразрядных двоичных сумматоров и 10 полусумматоров,Блок 5 предназначен для преобразования многорядного кода результата, формируемого в процессе умножения в первом буферном регистре 4 второй группы, к коду меньшей рядности. Рядность информации на выходе узла 6 суммирования блока 5 зависит от скорости, с которой должно быть выполнено это преобразование и которая должна быть согласована со скоростью вычисления разрядных произведений блоками 2. Т.е. блок 5. в состав которого входят узел 6 суммированияи регистр 7 задержки, должен осуществлять преобразование информации за число шагов, м ьшее или равное числу шагов блока 2 разрядных значений произведения.На фиг.4 изображен процесс суммирования в узле 6 массива слагаемых, образованного шестирядным кодом произведения сомножителей (этот код поступает с выхода первого регистра 4) и двухрядных кодом информации, хранимой в регистре 7 задержки, Алгоритм сворачивания и условные обозначения аналогичны используемым на фиг.3. Как видно из фиг,4, преобразование восьмирядного кода к двухрядному осуществляется за три шага 1-111, что обеспечивает задержку на блоке 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 к-ичный код множимого (п.к - разрядный двоичный код множимого), Здесь предполагается, что множимое и множитель представлены в двоично-кодированной 2"-ичной системе счисления, т,е. каждый разряд как множимого, так и множителя представляет собой набор из к двоичных цифр. Умножение в устройстве осуществляется за 2 п+гп тактов.В каждом из и первых тактов работы устройства на его вход 13 поступает параллельно к двоичных разрядов множителя, начиная с младших разрядов, При этом в 1-м блоке 2 вычисления разрядных значений произведения осуществляется умножение к двоичных разрядов множимого, поступающих нэ его вход множимого с выхода 15 1-го разряда регистра 1, на.к двоичных разрядов множителя, поступающих на его вход множителя с входа 13 устройства, и прибавление к к младшим двоичным разрядам получившегося при этом 2.к разрядного произведения через входы первого и второ.го слагаемых блока 2 соответственно старшего разряда произведения -го блока 2, сформированного в предыдущем такте и10 15 хранимого в -м регистре 3 и младшего разряда произведения ( + 1)-го блока 2, сформированного в предыдущем также ихранимого в ( + 1)-м регистре 4, Сформированные -м блоком 2 старший и младший разряды произведения в многорядном коде с его выходов 16 и 17 в конце каждого такта записываются соответственно в -тые буферные регистры 3 и 4, Одновременно с работой блоков 2 вычисления разрядных значений произведения работают и блоки 5 и 8 приведения, которые осуществляют последовательное преобразование многорядного кода, формируемого в процессе умножения в первом буферном регистре 4(исходная информация для блока 5 приведения), э также получаемого в процессе приведения и хранимого в регистрах 10 и 11 соответствующих блоков 8 приведения, В 20 конце каждого такта в регистры 10 и 11записываются результаты вычислений соответствуюших блоков 5 и 8 приведения,После выполнения и первых тактов работы устройства на его вход 13 множителя 25 поступает нулевая информация и далее осуществляется еще дополнительно(п+ п) тактов, в течение которых из устройства выводится с соответствующим преобразованием информация, хранимая в буферных 30 регистрах 3 и 4. а также в регистрах 7 и 10задержки блоков 5 и 8 приведения и буфер,ных регистров 11 блоков 8. Вывод 2,п разрядного ироизведения в устройстве осуществляется через его выход 14 в парал лельно-последовательном коде по к двоичных разрядов в каждом такте, начиная с (п + 1)-го такта работы устройства (в первых гл .тактах работы устройства младший разряд результата последовательно переписыва ются с соответствующим преобразованиемиз первого буферного регистра 4 в буферные регистры 11 щ блоков 8 приведения).В рассмотренном случае на вход 12 коррекции устройства во всех его 2 п + гл тактах 45 подавалась нулевая информация. В тех жеслучаях, когда требуется получить округленное и-разрядное произведение, необходимо в первом такте работы устройства на его вход 12 коррекции подать к-разрядный дво . 100 ,ОООичный код Это позволяетКосуществить округление без дополнительных временных затрат. Используя определенным образом вход 12 коррекции 55 устройства можно одновременно выполнять в нем операцию умножения и-разрядных числе с подсуммированием к и старшим разрядам произведения некоторого и -разрядного слагаемого или группы слагаемых.Вход 12 устройства может быть также эф10 1746377 Устройство для умножения чисел, поавт. св. М 1322265, о т л и ч а ю щ е е с я тем,5 что, с целью повышения быстродействия,оно содержит гп дополнительных блоковприведения (а = 1,2,3,), состоящих каждыйиз узла суммирования, регистра задержки ибуферного регистра, причем в каждом до 10 полнительном блоке приведения выход буферного регистра соединен с входомпервого слагаемого узла суммирования,вход второго слагаемого которого соединенс выходом регистра задержки, вход которо 15 го соединен с выходом переноса узла сум мирования, выход суммы узласуммирования ) -го дополнительного блокаприведения ( ) = 2,п 1) соединен с входомбуферного регистра ( ) - 1)-го дополнитель 20 ного блока приведения, вход буферного регистра т-го дополнительного блокаприведения - с выходом суммы узла суммирования блока приведения, выход суммы узла суммирования первого дополнительного25 блока приведения является выходом устройства,Х ХХ ХХХХХ ХХХ ХХХХХ Х ХХ Х ХХ.ХХ Х Х Х Х, Х Х Х, Х ХХХХХ ХХ Х ХХХХХХХХ е ее е е е еее е е еФе ее фективно использован для введения коррекции по знакам при умножении чисел в дополнительном коде,Следует особо отметить, что умножение и-разрядных в устройстве (как и в известном) может быть выполнен и за (и+ 1) тактов, если после выполнения и-го такта содержимое буферных регистров 3 и 4, регистра 7 задержки блока 5, регистров 10 задержки и буферных регистров 11 блоков 8 подать для окончательного суммирования на соответствующие входы быстродействующего многовходового блока суммирования (на фиг.1 такой блок суммирования и соответствующие связи показаны штриховой линией),.Технико-зкономическое преимущество устройства для умножения чисел в сравнении с прототипом заключается в его более высоком быстродействии (при вычислении и роизведе н и я 64-раз рядн ых сомножителей, представленных в двоично-кодированной 2 - ричной системе счисления и в предложении, что старшие и младшие цифры разрядных произведений формируются в шестирядном коде, устройство примерно в 1,8 раз быстрее известного). Формула изобретенияееееФееее ФеФе ееЭФ еееФе еФеФ еЦВВВВВИЮ ВВВВЕ И Ю Составитель А.Шостэкдактор Н.Химчук Техред М.Моргентал Корректор Н,Милюкова аказ 2395: Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открыти 113035, Москва, Ж, Раушскэя наб., 4/5 и ГКНТ СССР оизводственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101ееэФФ00 В