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

Г

L

-

Ј

Ф I

Т

1

J

(Л

С

Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел, удобных для изготовления с применением БИС и СБИС. Цель изобретения - сокращение аппаратурных затрат устройства. Устройство содержит регистр 1 множимого, п блоков 2 вычисления разрядных значений произведения (п - разрядность множимого), п буферных регистров 3 и m блоков 4 приведения с новой организацией связей. 5 ил.

5

Ц

4

12

Ь

7

00

о

со о

Ј

. ®иг.1

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

Целью изобретения является сокращение аппаратурных затрат.

На фиг, 1 приведена структурная схема предлагаемого устройства умножения чисел; на фиг. 2 - два варианта блока приведения; на фиг. 3 для случая двоично-кодированной 2 256-ричной системы счисления (Ь 2, к 8) приведен массив слагаемых, который суммируется каждым блоком счисления разрядных значений произведения до получения на его выходе шестирядного кода произведения; на фиг. 4 - процесс суммирования массива слагаемых фиг, 3 в каждом блоке вычисления разрядных значений произведения; на фиг. 5- процесс приведения шестирядного кода разряда произведения, формируемого на выходе младшего разряда первого блока вычисления разрядных значений произведения, к двухрядному коду в первом блоке приведения с учетом содержимого его регистра задержки.

Предлагаемое устройство умножения чисел содержит (фиг. 1) п -разрядный регистр 1 множимого, п блоков 2 вычисления разрядных значений произведения, п буферных регистров 3 первой группы и m блоков приведения (т 1, 2, 3, ..;), вход 5 множителя устройства, вход 6 коррекции устройства и.выход 7 устройства. Вход множителя i-ro блока 2 О 1, ..., п) соединен с входом 5 устройства, вход множимого - с выходом 8 1-го разряда регистра 1, вход первого слагаемого - с выходом 11 1-го регистра 3, вход второго слагаемого - с выходом 10 младшего разряда (i+ 1)-го блока 2, выход 9 старшего разряда i-ro блока 2 соединен с входом i-ro регистра 3, выход 10 первого блока 2 соединен с входом первого блока 4, выход 12 j-ro блока 4, выход 12 m-ro блока 4 соединен с выходом 7 устройства, вход 6 коррекции которого соединен с входом второго слагаемого n-го блока 2.

Рассмотрим функциональное назначение и реализацию узлов и блоков предлагаемого устройства.

Регистр 1 предназначен для хранения значения n-разрядного множимого и может быть реализован на синхронных двухтактных D-триггерах.

Блоки 2 предназначены для вычисления разрядных значений произведения соответствующих разрядов множимого и множителя с учетом двух дополнительных слагаемых,

при этом на его выходах 9 и 10 формируются соответственно старший и младший разряды числа

F + A + B,

На фиг. 3 для случая двоично-кодированной 2 256-ричной системы счисления (b 2, k 8) в предположении, что на выходах

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

обозначено знаками +, второе слагаемое В - знаками х, а массив частичных произведений, образующийся в результате перемножения сомножителей X и Y, изображен в виде матрицы точек. Фиг. 4 иллюстрирует

процесс суммирования в блоке 2 массива слагаемых, показанного на фиг. 3. При этом учитывают, что процесс подсуммирования второго слагаемого В в блоке 2 начинается после того, как данный массив будет сформирован в соседнем старшем блоке 2 (момент поступления второго слагаемого из соседнего старшего блока 2 и вывод сформированного младшего разряда произведения данного блока 2 показаны, а сами поступаемый и передаваемый массивы обведены сплошными контурами), Суммирование осуществляется по так называемому алгоритму сворачивания Дхуркадаса с использованием одноразрядных двоичных

сумматоров. Те двоичные разряды слагаемых массива, которые обрабатываются одним и тем же одноразрядным двоичным сумматором, обведены овальной линией. Процесс суммирования можно условно разделить на два этапа: на первом этапе суммируется массив частичных произведений сомножителей X и Y и первое слагаемое А, в результате чего на выходе 10 блока 2 формируется шестирядный код его младшего

разряда (второе слагаемое В для соседнего младшего блока 2), а на втором этапе к старшему разряду результата блока 2 подсумми- руется второе слагаемое В из соседнего старшего блока 2. В результате на выходе 9

блока 2 формируется шестирядный код старшего разряда. Как видно из фиг. 4, на первом этапе осуществляется преобразование тринадцатирядного кода к шестирядно- му за два шага I-II, на втором этапе

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

Буферные регистры 3 предназначены для хранения старших разрядов разрядных произведений, формируемых соответствующими блоками 2, и могут быть реализованы на синхронных двухтактных D-триггерах с вводами установки в нулевое состояние.

Каждый блок 4 предназначен для приведения многорядного кода информации на сбоем входе к коду меньшей рядности на своем выходе 12Ддля rn-го блока 4 - к одно- родному коду результата). Блок 4 может быть реализован как показано на фиг. 2,а. В этом случае каждый блок 4 содержит узел 13 суммирования, регистр 14 задержки и бу- форный регистр 15, причем узел 13 должен of еспечивать задержку на преобразование кедов, меньшую или равную задержке на Йлоках 2 вычисления разрядных значений произведения. В рассматриваемом примере каждый блок 4 должен выполнять преоб- ргзование не более чем за три шага, пс этому в устройстве требуется два блока 4 приведения; На фиг. 5 изображен процесс суммирования в узле 13 первого блока 4 мг ссива слагаемых, представляющего из себя шестирядный код, хранящийся, в бу- ф« рном регистре 15 этого блока 4 и двухрядную информацию, хранимую в регистре 14 задержки этого блока 4. Преобразование исходного восьмирядного кода к двухрядно- му| осуществляется за три шага с использо- ва|нием 23 одноразрядных двоичных сумматоров. В качестве узла 13 суммирования второго блока 4 используется восьми- ра зрядный двухвходовой сумматор с ускоренным переносом.

, Буферные регистры 15 и регистры 14 задержки блоков 4 могут быть реализованы на синхронных двухтактных D-триггерах с входами установки в нулевое состояние.

| Несколько другой пример построения блЬков 4 показан на фиг. 2,6. В состав блока 4 входят те же узлы, однако буферный ре- 15 размещается на выходе блока 4.

В целях упрощения на структурных схемах условно не показаны цепи установки в нулевое состояние регистров 3, 14, 15 и цепи-синхронизации всех регистров устройства, однако, можно отметить, что имеется общая цепь синхронизации регистров 3, 14 и 1|5, а цепь установки в нулевое состояние этИх регистров соединена с цепью синхронизации регистра 1.

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

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

В исходном состоянии буферные регистры 3 и регистры 14 и 15 блоков 4 обнулены, в регистре 1 хранится без знака п-разрядный 2 -ичный код множимого (п к-разрядный двоичный код). Здесь предполагается, что множимое и множитель представлены в двоично-кодированной 2k-H4HOu системе счисления, т.е. каждый разряд как множимого, так и множителя представляет собой набор из к двоичных цифр. Блок 4 построен как показано на фиг. 2,а). Умножение в устройстве осуществляется за 2n + m тактов.

В каждом из п первых тактов работы устройства на его вход 5 поступает параллельно k двоичных разрядов множителя, начиная с младшего 2k-H4Horo разряда. При этом в i-м блоке 2 осуществляется умножение k двоичных разрядов множителя, поступающих на его вход множителя с входа 5 устройства, на k двоичных разрядов множимого, поступающих на его вход множимого с выхода 8 i-ro разряда регистра 1, и прибавление к младшим двоичным разрядам получившегося при этом 2k-paspflAHoro произведения старшего 2k-H4Horo разряда i-ro блока 2, сформированного в предыдущем такте и поступающего на вход первого слагаемого с выхода 11 i-ro регистра 3, а к старшим двоичным разрядам - младшего 2k-n4Horo разряда (i + 1)-го блока.2, сформированного в этом же такте и поступающего на вход второго слагаемого i-ro блока 2 с выхода 10 (i + 1)-го блока 2. Причем, как видно из фиг. 4, подсуммирование второго слагаемого в блоке 2 осуществляется после того, как сформирован его младший разряд результата, который при дальнейших преобразованиях не изменяется. Сформированный i-м блоком 2 старший разряд произведения в многорядном коде записывается в i-й буферный регистр 3. Одновременно с работой блоков 2 вычисления разрядных значений произведения в блоках 4 приведения осуществляется преобразование по конвейерному принципу многорядного кода младшего разряда результата, формируемого на выходе 10 первого блока 2, к однорядному коду на выходе 7 устройства.

После выполнения п первых тактов работы устройства на его вход 5 множителя поступает нулевая информация и далее осуществляется еще дополнительно (п + т) тактов, в течение которых из устройства выводится с соответствующим преобразованием информация, хранимая в буферных регистрах 3, а также в регистрах 13, 14 блоков 4. Вывод 2п-разрядного произведения в устройстве осуществляется через его выход

7 в параллельно-последовательном коде по k двоичных разрядов в каждом такте, начиная с (т + 1)-го такта работы устройства (в первых m тактах младший разряд результата последовательно передается с соответст- вующими преобразованиями из блока 4 в блок 4 в направлении к выходу 7 устройства).

В рассматриваемом случае на вход б устройства во всех 2n + m тактах его работы подавалась информация. Если же требуется подсуммировать к вычисляемому произведению дополнительные слагаемые, например, при введении коррекции по знакам при умножении чисел, представленных в допол- нительном коде, то необходимо подать на вход 6 требуемую информацию, что обеспечит подсуммирование без дополнительных временных затрат.

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

Произведем сравнение предлагаемого устройства и устройства-прототипа по аппаратурным затратам на их реализацию, используя известные способы построения узлов и блоков на двух-, трех- и четырехвхо- довых элементах И, ИЛИ, НЕ, которые обозначим как эквивалентные вентили (ЭВ).

Пусть сравниваемые устройства предназначены для умножения 64-разрядных двоичных сомножителей, предназначенных в двоично-кодированной 2 256 ричной системе счисления (т.е. b 8, п 8, k 8), причем на выходах блоков вычисления разрядных значений произведения формиру- ются значения старшей и младшей цифры произведения в шестирядном коде.

Пусть все регистры сравниваемых устройства реализованы на синхровходы двухтактных D-триггерах, каждый из которых содержит СТр 9 ЭВ.Тогда регистры множимого и множителя этих устройств будут содержать:

CPM 2 n k CTp 11523B.

Аппаратурные затраты на реализацию известного устройства составляют затраты на регистры множимого и множителя (СРм), на п блоков вычисления разрядных значений произведения (Се), на две группы по п буферных регистров () и на два блока приведения (Gen1):

-, г И , r W 1 Г И

С Срм + Сб + Сбр + Сбп .

В блоках вычисления разрядных значений произведения, как показано на фиг. 3, преобразуется исходный пятнадцатиряд- ный код в шестирядный за три шага с использованием 64 одноразрядных двоичных сумматоров и 10 полусумматоров, наиболее экономичные схемы которых содержат Сс 9 ЭВ и Спс 4 ЭВ соответственно. Кроме того, в состав каждого блока вычисления разрядных значений произведения входит матрица из k2 двухвходовых элементов И. С учетом этого

Сби п (k2 + 64 Сс + 10 Спс) 5540 (ЭВ).

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

СбРи Стр 6912 (ЭВ).

В известном устройстве используются два блока приведения. Первый преобразует восьмирядный код в двухрядный с использованием 32 одноразрядных двоичных сумматоров (см. фиг. 4). Регистр задержки первого блока приведения хранит три двоичных разряда информации. Второй блок приведения прототипа преобразует двух-. рядный код в однорядный с использованием восьмиразрядного сумматора, построенного на основе двух четырехразрядных сумматоров, переносы в которых формируются параллельно, и на реализацию которого требуется Ссум 2 48 96 (ЭВ). Кроме того, второй блок приведения содержит одноразрядный регистр задержки и буферный регистр для хранения двухрядного кода информации, С учетом этого

Сбпи (32 Сс + 3 Стр) + (Ссум + +CTp + ) 574(3B).

Таким образом, аппаратурные затраты на реализацию известного устройства составляют:

,изв

1152 + 5440 + 6912 + 574 14078 (ЭВ).

Предлагаемое устройство содержит регистры множимого и множителя (Срм), п бло- ков вычисления разрядных значений

произведения (Сеп), п буферных регистров (Сбрп) и два блока приведения (Сбпп).

Спредл Срм + Сбп + СбРп + Сбпп.

Каждый блок вычисления разрядных значений произведения содержит, как показано на фиг. 3, k2 двухвходовых элементов И и 64 одноразрядных двоичных сумматоров, т.е.

Сбп п (k2 + 64 Сс) 5120 (ЭВ).

На реализацию п буферных регистров, как показано на фиг. 4, требуется

Сбрп п 40 СтР 2880 (ЭВ).

Пусть блоки приведения реализованы как. показано на фиг. 2,а. Первый блок приведения содержит, как показано на фиг. 5, 21 одноразрядный двоичный сумматор, а также регистр задержки для хранения трех двоичных разрядов информации и буферный регистр для хранения 34 двоичных разрядов информации (при реализации блока приведения как показано на фиг. 2,а) или 16 ДЁОИЧНЫХ разрядов информации(при реализации блока приведения как показано на фиг. 2,6). Второй блок приведения содержит восьмиразрядный двухвходовый сумматор, аналогичный сумматору прототипа (ССум), одноразрядный регистр задержки и буферный регистр для хранения 16 двоичных разрядов информации (при реализации блока приведения как показано на фиг. 2,а) или 8 дв оичных разрядов информации (при реализации блока приведения как показано на фиг. 2,6). С учетом этого

Сбпп (21 Сс + 3 СтР + 34 СтР) + + (Ссум + СТр + 16 СтР) 771 (ЭВ).

Аппаратурные затраты на реализацию предлагаемого устройства составляют:

спредл 1152 .5120 + 2880 + . 992з (эв).

Таким образом, аппаратурные затраты в предлагаемом устройстве будут в сиэв/спРедл 4078/9923 1,4 раза меньше, чем в известном. Следует отметить, что выигрыш в аппаратуре будет еще более значителен при использовании многовходо вого блока суммирования (на фиг. 1 показан

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

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

Технико-экономическое преимущество предлагаемого устройства умножения чисел по сравнению с известным заключается в меньших аппаратурных затратах (при вычислении произведения 64-разрядных двоичных сомножителей, представленных в двоично-кодированой 28 265-ричной системе счисления и в предположений, что блоки вычисления разрядных значений

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

Формула изобретения

Устройство для умножения, содержащее регистр множимого, п блоков вычисления разрядных значений произведения (n-разрядность множимого), п буферных регистров и m блоков приведения (п 1, 2, 3...), причем вход множителя i-ro блока вычисления разрядных значений произведения (I 1, ..., п) соединен с входом множителя устройства, вход множимого - с выходом 1-го

разряда регистра множимого, вход первого слагаемого - с выходом i -го буферного регистра, вход старшего разряда i-ro блока вычисления разрядных значений произведения соединен с входом i-ro буферного

регистра, выход j-ro блока приведения 0 1, ..., m - 1) соединен с входом (j + 1)-го блока приведения, выход m-го блока приведения соединен с выходом устройства, вход коррекции которого соединен с входом второго

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

:2

+ + +

+ 4- +-Ц- 4-И-И-+ + + + Ч- + + + + 4- + + + -I- + +-+

-1- + 4-4-+-Ц-+

X XX

XXX

XXX XX УXX X X X X X X X

ххххх

frl6C08l

/oУЫГ

xxxxxxxx xxxxxxxx

xx:

xxxxxx xxxx :r

10

Фиг.Ь

/

У///

/// ....

i -/ ----------V---- /7tf

, v5

Редактор О. Стенина

Составитель А. Шостак

Техред М.МоргенталКорректор М. Керецман

Заказ 1057Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5

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

V/