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

.Ж 18039 6 06 Г 7/ ГОСУДАРСТВЕННОЕ ПАТЕНТНВЕДОМСТВО СССР(57) Изобретение относится к выч ной технике и может быть использ разработке быстродействующих умножения чисел, удобных для ния с применением БИС и СБИС. бретения - сокращение аппа затрат устройства. Устройство сод гистр 1 множимого, п блоков 2 вь разрядных значений произведени рядность множимого), л буферн ров 3 и щ блоков 4 приведени организацией связей. 5 ил. итут(541 УСТРОЙСТВО ДЛЯ ЖЕНИЯ ВТОРСКОМУ СВИДЕТЕЛЬСТВ 21 4922876/24 22 29,03.91 46 23,03,93, Бюл, М 11 71) Науч но-исследовательский и электронных вычислительных маши 72 А,А.Шостак и В.В,Яскевич 56 Авторское свидетельство СССР М 322265, кл. О 06 Р 7/52, 1985.Авторское свидетельство СССР М 1746377, кл, 6 06 Р 7/52, 1989,ислительовано при устройств изготовлеЦель изоратурных ержит речисления я (и - разых регистя с новойР=ХУ+А+В,двоичных сумматора. Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел, представленных в любой позиционной системе счисления. Особенно эффективно его применение при использовании технологии БИС и СБИС.Целью изобретения является сокращение аппаратурных затрат.На фиг, 1 приведена структурная схема предлагаемого устройства умножения чисел; на фиг. 2 - два варианта блока приведения; на фиг, 3 дляслучая двоично-кодированной 2 =256-ричной системы счисленияв(Ь = 2, К = 8) приведен массив слагаемых, который суммируется каждым блоком счисления разрядных значений произведения до получения на его выходе шестирядного кода произведения; на фиг, 4 - процесс суммирования массива слагаемых фиг, 3 в каждом блоке вычисления разрядных значений произведения; на фиг. 5 - процесс приведения шестирядного кода разряда произведения, формируемого на выходе младшего разряда первого блока вычисления разрядных значений произведения, к двухрядному коду в первом блоке приведения с учетом содержимого его регистра задержки.Предлагаемое устройство умножения чисел содержит (фиг, 1) и -разрядный регистр 1 множимого, и блоков 2 вычисления разрядных значений произведения, и буферных регистров 3 первой группы и в блоков приведения (в = 1, 2, 3, ;), вход 5 множителя устройства, вход 6 коррекции устройства и,выход 7 устройства, Вход множителя 1-го блока 2 ( = 1,и) соединен с входом 5 устройства, вход множимого - с выходом 8 1-го разряда регистра 1, вход первого слагаемого - с выходом 11 1-го регистра 3, вход второго слагаемого - с выходом 10 младшего разряда (+ 1)-го блока 2, выход 9 старшего разряда 1-го блока 2 соединен с входом 1-го регистра 3, выход 10 первого блока 2 соединен с входом первого блока 4, выход 12 )-го блока 4, выход 12 гп-го блока 4 соединен с выходом 7 устройства, вход 6 коррекции которого соединен с входом второго слагаемого п-го блока 2.Рассмотрим функциональное назначение и реализацию узлов и блоков предлагаемого устройства.Регистр 1 предназначен для хранения значения и-разрядного множимого и может быть реализован на синхронных двухтактных О-триггерах,Блоки 2 предназначены для вычисления разрядных значений произведения соответствующих разрядов множимого и множителя с учетом двух дополнительных слагаемых,10 15 20 25 30 35 40 45 50 55 при этом на его выходах 9 и 10 формируютсясоответственно старший и младший разряды числа На фиг, 3 для случая двоично-кодированной 2 = 256-ричной системы счисленияв(Ь =2, 1=8) в предположении, что на выходах 9 и 10 каждого блока 2 формируются разряды результата в шестирядном коде приведен массив слагаемых, который суммируется каждым блоком 2 вычисления разрядных значений произведения, Первое слагаемое А обозначено знаками "+", второе слагаемое В - знаками "х", а массив частичных произведений, образующийся в результате перемножения сомножителей Х и У, изображен в виде матрицы точек. Фиг, 4 иллюстрирует процесс суммирования в блоке 2 массива слагаемых, показанного на фиг. 3. При этом учитывают, что процесс подсуммирования второго слагаемого В в блоке 2 начинается после того, как данный массив будет сформирован в соседнем старшем блоке 2 (момент поступления второго слагаемого из соседнего старшего блока 2 и вывод сформированного младшего разряда произведения данного блока 2 показаны, а сами поступаемый и передаваемый массивы обведены сплошными контурами), Суммирование осуществляется по так называемому алгоритму сворачивания Дхуркадаса с использованием одноразрядных двоичных сумматоров, Те двоичные разряды слагаемых массива, которые обрабатываются одним и тем же одноразрядным двоичным сумматором, обведены овальной линией. Процесс суммирования можно условно разделить надва этапа: на первом этапе суммируется массив частичных произведений сомножителей Х и У и первое слагаемое А, в результате чего на выходе 10 блока 2 формируется шестирядный код его младшего разряда (второе слагаемое В для соседнего младшего блока 2), а на втором этапе к старшему разряду результата блока 2 подсуммируется второе слагаемое В из соседнего старшего блока 2. В результате на выходе 9 блока 2 формируется шестирядный код старшего разряда. Как видно из фиг, 4, на первом этапе осуществляется преобразование тринадцатирядного кода к шестирядному за два шага 1-П, на втором этапе восьмирядный код приводится к шестирядному за один шаг 111, Для реализации такого блока 2 требуется 64 двухвходовых элемента И (для формирования частичных произведений сомножителей) и 64 одноразрядных40 55 Буферные регистры 3 предназначены для хранения старших разрядов разрядных произведений, формируемых соответствующими блоками 2, и могут быть реализованы на синхронных двухтактных О-триггерах с входами установки в нулевое состояние.Каждый блок 4 предназначен для приведения многорядного кода информации на с оем входе к коду меньшей рядности на с оем выходе 12.(для в-го блока 4 - к однор дному коду результата). Блок 4 может бфть реализован как показано на фиг. 2,а. В эМом случае каждый блок 4 содержит узел 13 с ммирования, регистр 14 задержки и буф рный регистр 15, причем узел 13 должен о еспечивать задержку на преобразование к дов, меньшую или равную задержке налоках 2 вычисления разрядных значений и оизведения. В рассматриваемом пример каждый блок 4 должен выполнять преобр зование не более чем за три шага, и этому в устройстве требуется два блока 4 и иведения, На фиг. 5 изображен процесс су мирования в узле 13 первого блока 4 м ссива слагаемых, представляющего из себя шестирядный код, хранящийся, в буферном регистре 15 этого блока 4 и двухрядную информацию, хранимую в регистре 14 задержки этого блока 4. Преобразование исходного восьмирядного кода к двухрядному осуществляется за три шага с использованием 23 одноразрядных двоичных сумматоров, В качестве узла 13 суммировани второго блока 4 используется восьми- разрядный двухвходовой сумматор с ускоренным переносом., Буферные регистры 15 и регистры 14 задержки блоков 4 могут быть реализованы на синхронных двухтактных О-триггерах свхфдами установки в нулевое состояние., Несколько другой пример построения блков 4 показан на фиг. 2,б. В состав блока 4 входят те же узлы, однако буферный регистр 15 размещается на выходе блока 4.В целях упрощения на структурных схе- маХ условно не показаны цепи установки в нулевое состояние регистров 3, 14, 15 и цепи синхронизации всех регистров устройства, однако, можно отметить, что имеется общая цепь синхронизации регистров 3, 14 и 15, а цепь установки в нулевое состояние этИх регистров соединена с цепью синхронизации регистра 1,Совокупность блока 2 и соответствующего ему регистра 3 может быть конструктивно выполнена в виде операционного модуля (на фиг. 1 показан штрихпунктирной ливией), реализованного, например, как боЛьшая интегральная схема. 1015253 Устройство умножения работает следующим образом.В исходном состоянии буферные регистры 3 и регистры 14 и 15 блоков 4 обнулены, в регистре 1 хранится без знака и-разрядный 1(2 -ичный код множимого (п 1-разрядный двоичный код). Здесь предполагается, что множимое и множитель представлены в двоична-кодированной 2 -ичной системе)(счисления, т.е, каждый разряд как множимого, так и множителя представляет собой набор из М двоичных цифр, Блок 4 построен как показано на фиг, 2,а), Умножение в устройстве осуществляется за 2 п+ гп тактов,В каждом из и первых тактов работы устройства на его вход 5 поступает параллельно к двоичных разрядов множителя, начиная с младшего 2 -ичного разряда. Прикэтом в 1-м блоке 2 осуществляется умножение К двоичных разрядов множителя, поступающих на его вход множителя с входа 5 устройства, на 1 двоичных разрядов множимого, поступающих на его вход множимого с выхода 8 -го разряда регистра 1, и прибавление к младшим двоичным разрядам получившегося при этом 2 -разрядного произведения старшего 2 -ичного разряда1(1-го блока 2, сформированного в предыдущем такте и поступающего на вход первого слагаемого с выхода 11 -го регистра 3, а к старшим двоичным разрядам - младшего 2 -ичного разряда (1+ 1)-го блока 2, сформикрованного в этом же такте и поступающего на вход второго слагаемого 1-го блока 2 с выхода 10 ( + 1)-го блока 2. Причем, как видно из фиг, 4, подсуммирование второго слагаемого в блоке 2 осуществляется после того, как сформирован его младший разряд результата, который при дальнейших преобразованиях не изменяется, Сформированный -м блоком 2 старший разряд произведения в многорядном коде записывается в -й буферный регистр 3. Одновременно с работой блоков 2 вычисления разрядных значений произведения в блоках 4 приведения осуществляется преобразование по конвейерному принципу многорядного кода младшего разряда результата, формируемого на выходе 10 первого блока 2, к однорядному коду на выходе 7 устройства.После выполнения и первых тактов работы устройства на его вход 5 множителя поступает нулевая информация и далее осуществляется еще дополнительно (п + щ) тактов, в течение которых из устройства выводится с соответствующим преобразованием информация, хранимая в буферных регистрах 3, а также в регистрах 13, 14 блоков 4. Вывод 2 п-разрядного произведения в устройстве осуществляется через его выход1803914 55 7 в параллельно-последовательном коде поК двоичных разрядов в каждом такте, начиная с (а + 1)-го такта работы устройства (впервых тп тактах младший разряд результата последовательно передается с соответствующими преобразованиями из блока 4 вблок 4 в направлении к выходу 7 устройства),В рассматриваемом случае на вход 6устройства во всех 2 п + в тактах его работы 10подавалась информация. Если же требуетсяподсуммировать к вычисляемому произведению дополнительные слагаемые, например, при введении коррекции по знакам приумножении чисел, представленных в дополнительном коде, то необходимо подать навход 6 требуемую информацию, что обеспечит подсуммирование без дополнительныхвременных затрат,Следует особо отметить, что умножение 20и-разрядных чисел в предлагаемом устрой-,стве (как и в известном) может быть выполнено и за (и + 1) тактов, если послевыполнения и-го такта содержимое буферных регистров 3 и результаты блоков 5 подать для окончательного суммирования насоответствующие входы быстродействующего многовходового блока суммирования(на фиг. 1 такой блок суммирования и соответствующие связи показаны штриховыми 30линиями),Произведем сравнение предлагаемогоустройства и устройства-прототипа по аппаратурным затратам на их реализацию, используя известные способы построения 35узлов и блоков на двух-, трех- и четырехвходовых элементах И, ИЛИ, НЕ, которые обозначим как эквивалентные вентили (ЭВ).Пусть сравниваемые устройства предназначены для умножения 64-разрядных 40двоичных сомножителей, предназначенныхв двоично-кодированной 2 =256 ричной :.системе счисления (т.е, Ь =-8, и = 8, 1 = 8),причем на выходах блоков вычисления разрядных значений произведения формируются значения старшей и младшей цифрыпроизведения в шестирядном коде.Пусть все регистры сравниваемых устройства реализованы на синхровходы двухтактных О-триггерах, каждый из которых 50содержит Стр = 9 Э В, Тогда регистры множимого и множителя этих устройств будут содержать; Срм = 2и1 сСтр = 1152 Э В. Аппаратурные затраты на реализацию известного устройства составляют затраты на регистры множимого и множителя (Срм), на и блоков вычисления разрядных значений произведения (Сби), на две группы по ибУфеРных РегистРов (Сбр") и на Два блокаприведения (Сбп): С = С,. + Сб+ Сб,+ Сб.",В блоках вычисления разрядных значений произведения, как показано на фиг. 3, преобразуется исходный пятнадцатирядный код в шестирядный за три шага с использованием 64 одноразрядных двоичных сумматоров и 10 полусумматоров, наиболее экономичные схемы которых содержат Сс = 9 ЭВ и Спс = 4 ЭВ соответственно. Кроме того, в состав каждого блока вычисления разрядных значений произведения входит матрица из Мдвухвходовых элементов И. С учетом этого Сби = и(1 + 64Сс + 10Спс) = 5540 (Э В). Аппаратурные затраты на буферные регистры, каждый из которых хранит информацию в шестирядном коде, составляют величину Сбри = 2иК6 Стр = 6912 (ЭВ),В известном устройстве используются два блока приведения, Первый преобразует восьмирядный код в двухрядный с использованием 32 одноразрядных двоичных сумматоров (см. фиг. 4). Регистр задержки первого блока приведения хранит три двоичных разряда информации. Второй блок и рив еде н ия и рототипа и реоб разует двух- . рядный код в однорядный с использованием восьмйразрядного сумматора, построенного на основе двух четырехразрядных сумматоров, переносы в которых формируются параллельно, и на реализацию которого требуется Ссу = 248 = 96 (ЭВ). Кроме того, второй блок приведения содержит одноразрядный регистр задержки и буферный регистр для хранения двухрядного кода информации, С учетом этого Сбп = (32Сс + 3Стр) + (Ссум ++Стр + 23 сСтр) = 574 (Э В), Таким образом, аппаратурные затраты на реализацию известного устройства составляют: Си" = 1152 + 5440+ 6912 + 574 = 14078 (ЭВ). Предлагаемое устройство содержит регистры множимого и множителя (Ср), и блоков вычисления разрядных значений(Сбр ) и два блока приведения (Сбп"). С = Срм+ Сб + Сбр + Сбп Каждый блок вычисления разрядных значений произведения содержит, как показано на фиг, 3, с двухвходовых элементов И и 64 одноразрядных двоичных сумматоров, т,е. Сб" = п(1 с + 64Сс) = 5120 (Э В). На реализацию и буферных регистров,как показано на фиг, 4, требуется Сбр" = П40Стр = 2880 (Э В) Пусть блоки приведения реализованы как показано на фиг. 2,а. Первый блок приведения содержит, как показано на фиг. 5, 21 одноразрядный двоичный сумматор, а также регистр задержки для хранения трех двоичных разрядов информации и буферный регистр для хранения 34 двоичных разрядов информации (при реализации блока приведения как показано на фиг, 2,а) или 16 двоичных разрядов инфоомации(при реализации блока приведения как показано на фиг, 2,б). Второй блок приведения содержит восьмиразрядн ый двухвходовый сумматор, аналогичный сумматору прототипа (Ссум), одноразрядный регистр задержки и буферный регистр для хранения 16 двоичных разрядов информации (при реализации блока приведения как показано на фиг. 2,а) или 8 двоичных разрядов информации(при реализации блока приведения как показано на фиг, 2,б). С учетом этого Сбп = (21Сс + 3Стр + 34Стр) ++ (Ссум + Стр + 16Стр) = 771 (Э В). Аппаратурные затраты на реализациюпредлагаемого устройства составляют; Таким образом, аппаратурные затраты в предлагаемом устройстве будут в Сизв/СпРедл 14078/9923 = 1,4 раза мен ьше, чем в известном, Следует отметить, что выигрыш в аппаратуре будет еще более значителен при использовании многовходового блока суммирования (на фиг, 1 показан 5 10 15 20 25 30 35 40 45 50 55 штриховыми линиями), поскольку в известном устройстве такой блок имеет почти вдвое больше входов и соответственно больше оборудования.Следует особо отметить, что быстродействие устройства не изменяется, поскольку задержка на блоках вычисления разрядных значений произведения, определяющая длительность такта, а также количество тактов не увеличивается,Технико-экономическое преимущество предлагаемого устройства умножения чисел по сравнению с известным заключается в меньших аппаратурных затратах (при вычислении произведения 64-разрядных двоичных сомножителей, представленных в двоично-кодированой 2 = 265-ричной сисатеме счисления и в предположении, что блоки вычисления разрядных значений произведения формируют на своих выходах шестирядный код информации, предлагаемое устройство имеет в 1,4 раза меньше аппаратуры, чем известное) при одинаковом быстродействии,Формула изобретения Устройство для умножения, содержащее регистр множимого, и блоков вычисления разрядных значений произведения (и-разрядность множимого), и буферных регистров и гп блоков приведения (о = 1, 2, 3), причем вход множителя 1-го блока вычисления разрядных значений произведения (1 = =1, , и) соединен с входом множителя устройства, вход множимого - с выходом 1-го разряда регистра множимого, вход первого слагаемого - с выходом 1 -го буферного регистра, вход старшего разряда 1-го блока вычисления разрядных значений произведения соединен с входом 1-го буферного регистра, выход)-го блока приведения О = 1, , т - 1) соединен с входом О + 1)-го блока приведения, выход щ-го блока приведения соединен с выходом устройства, вход коррекции которого соединен с входом второго слагаемого и-го блока вычисления разрядных значений произведения, о т л и ч а ющ е е с я тем, что, с целью сокращения аппаратурных затрат устройства, в нем выход младшего разряда 1-го блока вычисления разрядных значений произведения соединен с входом второго слагаемого (- 1)-го блока вычисления разрядных значений произведения ( = 2, , и), выход младшего разряда первого блока вычисления разрядных значений произведения соединен с входом первого блока приведения, 1803914. Стени ректор М. Керецман аказ 1057 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытия113035, Москва, Ж, Раушскэя наб., 4/5 ГКНТ СССРПроизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 ЬУ Составитель А. Шо Техред М.Моргентал