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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (! 9) (I () (я)л G 06 F 7/52

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (Г0СПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ вЂ” — — л — — — — т

I I

5 (21 4922876/24 (22 29,03.91 (46 23,03.93, Бюл, ¹ 11 (71) Научно-исследовательский институт электронных вычислительных машин (72 А.А.Шостак и В.В.Яскевич (56 Авторское свидетельство СССР

¹ 322265, кл. G 06 F 7/52, 1985.

Авторское свидетельство СССР

¹ 1746377, кл, G 06 F 7/52, 1989. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел, удобных для изготовления с применением БИС и СБИС. Цель изобретения — сокращение аппаратурных затрат устройства. Устройство содержит регистр t мMнHоo)жKи мMоoг оo, п блоков 2 вычисления разрядных значений произведения (и — разрядность множимого), л буферных регистров 3 и m блоков 4 приведения с новой организацией связей. 5 ил.

О (гд

Ф

1803914

F = X*Y+ А+ В, двоичных сумматора.

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

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

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

Предлагаемое устройство умножения чисел содержит (фиг, 1) и -разрядный регистр 1 множимого, и блоков 2 вычисления разрядных значений произведения, и буферных регистров 3 первой группы и rn блоков приведения (m = 1, 2, 3, „;), вход 5 множителя устройства, вход 6 коррекции устройства и.выход 7 устройства. Вход множителя i-го блока 2 (i = 1, ..., n) соединен с входом 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 коррекции которого соединен с входом второго слагаемого п-го блока 2.

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

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

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

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

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

 — знаками "х", а массив частичных произведений, образующийся в результате перемножения сомножителей X и У, изображен в виде матрицы точек. Фиг, 4 иллюстрирует процесс суммирования в блоке 2 массива слагаемых, показанного на фиг. 3. При этом учитывают, что процесс подсуммирования второго слагаемого B в блоке 2 начинается после того, как данный массив будет сформирован в соседнем старшем блоке 2 (момент поступления второго слагаемого из соседнего старшего блока 2 и вывод сформированного младшего разряда произведения данного блока 2 показаны, а сами поступаемый и передаваемый массивы обведены сплошными контурами), Суммирование осуществляется по так называемому алгоритму сворачивания Дхуркадаса с использованием одноразрядных двоичных сумматоров, Те двоичные разряды слагаемых массива, которые обрабатываются одним и тем же одноразрядным двоичным сумматором, обведены овальной линией.

Процесс суммирования можно условно разделить надва этапа: на первом этапе суммируется массив частичных произведений сомножителей X u Y и первое слагаемое А, в результате чего на выходе 10 блока 2 формируется шестирядный код его младшего разряда (второе слагаемое В для соседнего младшего блока 2), а на втором этапе к старшему разряду результата блока 2 подсуммируется второе слагаемое В из соседнего старшего блока 2. В результате на выходе 9 блока 2 формируется шестирядный код старшего разряда. Как видно из фиг, 4, на первом этапе осуществляется преобразование тринадцатирядного кода к шестирядному за два шага 1-II, на втором этапе восьмирядный код приводится к шестирядному за один шаг ill. Для реализации такого блока 2 требуется 64 двухвходовых элемента И (для формирования частичных произведений сомножителей) и 64 одноразрядных

1803914

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

Каждый блок 4 предназначен для приведения многорядного кода информации на с оем входе к коду меньшей рядности на с оем выходе 12 (для m-ro блока 4 — к одно- 10 р дному коду результата). Блок 4 может бфть реализован как показано на фиг. 2,а. В э;ом случае каждый блок 4 содержит узел 13 с ммирования, регистр 14 задержки и буф рный регистр 15, причем узел 13 должен 15 о еспечивать задержку на преобразование к дов, меньшую или равную задержке на локах 2 вычисления разрядных значений и оизведения. В рассматриваемом пример каждый блок 4 должен выполнять преоб- 20 р зование не более чем за три шага, и этому в устройстве требуется два блока 4 и иведения. На фиг. 5 изображен процесс су мирования в узле 13 первого блока 4 м ссива слагаемых, представляющего из 25 себя шестирядный код, хранящийся, в буферном регистре 15 этого блока 4 и двухрядну1о информацию, хранимую в регистре 14 задержки этого блока 4. Преобразование исходного восьмирядного кода к двухрядно- 30 му осуществляется за три шага с использованием 23 одноразрядных двоичных сумматоров, В качестве узла 13 суммирования второго блока 4 используется восьмираэрядный двухвходовой сумматор с 35 ускоренным переносом., Буферные регистры 15 и регистры 14 заДержки блоков 4 могут быть реализованы на синхронных двухтактных D-триггерах с 40 ! вхфдами установки в нулевое состояние.

; Несколько другой пример построения бл ков 4 показан на фиг. 2,б. В состав блока

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

В целях упрощения на структурных схемаХ условно не показаны цепи установки в нулевое состояние регистров 3, 14, 15 и цепи синхронизации всех регистров устройства, однако, можно отметить, что имеется 50 общая цепь синхронизации регистров 3, 14 и 1 5, а цепь установки в нулевое состояние этих регистров соединена с цепью синхронизации регистра 1, Совокупность блока 2 и соответствую- 55 щего ему регистра 3 может быть конструктивно выполнена в виде операционного моДуля (на фиг. 1 показан штрихпунктирной ливией), реализованного, например, как большая интегральная схема.

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

В исходном состоянии буферные регистры 3 и регистры 14 и 15 блоков 4 обнулены, в регистре 1 хранится без знака и-разрядный

2 -ичный код множимого (n*k-разрядный двоичный код). Здесь предполагается, что множимое и множитель представлены в двоична-кодированной 2 -ичной системе

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

k этом в i-м блоке 2 осуществляется умножение k двоичных разрядов множителя, поступающих на его вход множителя с входа 5 устройства, на k двоичных разрядов множимого, поступающих на его вход множимого с выхода 8 i-го разряда регистра 1, и прибавление к младшим двоичным разрядам получившегося при этом 2 -разрядного

k произведения старшего 2 -ичного разряда

k -го блока 2, сформированного в предыдущем такте и поступающего на вход первого слагаемого с выхода 11 i-го регистра 3, а к старшим двоичным разрядам — младшего

2 -ичного разряда (I+ 1)-го блока 2, сформиk рованного в этом же такте и поступающего на вход второго слагаемого i-го блока 2 r. выхода 10 (i + 1)-ro блока 2. Причем, как видно из фиг, 4, подсуммирование второго слагаемого в блоке 2 осуществляется после того, как сформирован его младший разряд результата, который при дальнейших преобразованиях не изменяется, Сформированный

i-M блоком 2 старший разряд произведения в многорядном коде записывается в i-й буферный регистр 3. Одновременно с работой блоков 2 вычисления разрядных значений произведения в блоках 4 приведения осуществляется преобразование по конвейерному принципу многорядного кода младшего разряда результата, формируемого на выходе 10 первого блока 2, к однорядному коду на выходе 7 устройства.

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

1803914

7 в параллельно-последовательном коде по

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

В рассматриваемом случае на вход 6 устройства во всех 2n + m тактах его работы 10 подавалась информация. Если же требуется подсуммировать к вычисляемому произведению дополнительные слагаемые, например, при введении коррекции по знакам при умножении чисел, представленных в допол- 15 нительном коде, то необходимо подать на вход 6 требуемую информацию, что обеспечит подсуммирование без дополнительных временных затрат, Следует особо отметить, что умножение 20 и-разрядных чисел в предлагаемом устрой-, стве (как и в известном) может быть выполнено и за (n + 1) тактов, если после выполнения и-го такта содержимое буферных регистров 3 и результаты блоков 5 по- 25 дать для окончательного суммирования на соответствующие входы быстродействующего многовходового блока суммирования (на фиг. 1 такой блок суммирования и соответствующие связи показаны штриховыми 30 линиями), Произведем сравнение предлагаемого устройства и устройства-прототипа no аппаратурным затратам на их реализацию, используя известные способы построения 35 узлов и блоков на двух-, трех- и четырехвходовых элементах И, ИЛИ, НЕ, которые обозначим как эквивалентные вентили (Э B).

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

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

Срм = 2 * n * k * Стр = 1152 ЭВ.!

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

ПрИВЕдЕНИя (Сбп ):

С = Срм+ Сб + Сбр + Сбп

B блоках вычисления разрядных значений произведения, как показано на фиг. 3, преобразуется исходный пятнадцатирядный код в шестирядный за три шага с использованием 64 одноразрядных двоичных сумматоров и 10 полусумматоров, наиболее экономичные схемы которых содержат

Сс = 9 ЭВ и Спс = 4 ЭВ соответственно.

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

Сби = n * (k + 64 * Сс + 10 * C„) = 5540 (ЭВ).

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

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

Сбп = (32 * Сс+ 3 * Стр) + (Ссум+

+Стр + 2 * k * Стр) = 574 (Э B) Таким образом, аппаратурные затраты на реализацию известного устройства составляют:

С "= 1152+ 5440+ 6912+ 574 = 14078 (ЭВ).

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

1803914

10 произведения (Сб"), и буферных регистров (Сбр ) И даа бЛОКа ПрИВЕдЕНИя (Сбп").

С Р = Срм + Сб + Сбр" + C ïп

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

И и 64 одноразрядных двоичных сумматоров, т.е.

Сб" = п * (k + 64 * Сс) = 5120 (Э В).

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

Сбр" = n * 40 * Стр = 2880 (Э В), Пусть блоки приведения реализованы как показано на фиг. 2,а. Первый блок приведения содержит, как показано на фиг. 5, 21 одноразрядный двоичный сумматор, а также регистр задержки для хранения трех двоичных разрядов информации и буферный регистр для хранения 34 двоичных разрядов информации (при реализации блока приведения как показано на фиг, 2,а) или 16 двоичных разрядов инфоомации(при реализации блока приведения как показано на фиг. 2,6). Второй блок приведения содержит восьмиразрядн ый двухвходовый сумматор, аналогичный сумматору прототипа (Cay„), одноразрядный регистр задержки и буферный регистр для хранения 16 двоичных разрядов информации (при реализации блока приведения как показано на фиг. 2,а) или 8 двоичных разрядов информации (при реализации блока приведения как показано на фиг, 2,6). С учетом этого

Сбп = (21 * Сс + 3 * Стр + 34 * Стр) +

+ (Ссум + Стр + 16 * Стр) = 771 (Э В).

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

С" Ред" = 1152 - 5120+ 2880 771 = 9923 (Э В), Таким образом, аппаратурные затраты в предлагаемом устройстве будут в

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

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

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

Технико-экономическое преимущество предлагаемого устройства умножения чисел по сравнению с известным заключается в меньших аппаратурных затратах (при вычислении произведения 64-разрядных двоичных сомножителей, представленных в двоично-кодированой 2 = 265-ричной сисО теме счисления и в предположении, что блоки вычисления разрядных значений произведения формируют на своих выходах шестирядный код информации, предлагаемое устройство имеет в 1,4 раза меньше аппаратуры, чем известное) при одинаковом быстродействии.

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

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

=1, ..., n) соединен с входом множителя устройства, вход множимого — с выходом I-го разряда регистра множимого, вход первого слагаемого — с выходом i ão буферного регистра, вход старшего разряда i-го блока вычисления разрядных значений произведения соединен с входом i-го буферного регистра, выход j-го блока приведения (j = 1, ..., m - 1) соединен с входом (j + 1)-го блока приведения, выход m-го блока приведения соединен с выходом устройства, вход коррекции которого соединен с входом второго слагаемого и-го блока вычисления разрядных значений произведения, о т л и ч а ющ е е с я тем, что, с целью сокращения аппаратурных затрат устройства, в нем выход младшего разряда I-ro блока вычисления разрядных значений произведения соединен с входом второго слагаемого (I1)-го блока вычисления разрядных значений произведения (! = 2, ..., и), выход младшего разряда первого блока вычисления разрядных значений произведения соединен с входом первого блока приведения, 1803914

1803914

+++++++++

+++++++++

+++++++

+++++++

-+ -++ ++

+ ++ у ° ф 4 ° Ф б ф

° 4 ° а б ° ° 4

° ° Ф ° ° ° 4

Ф g Ф 4 ° б б

° 4 ° Ф ° Ф ° °

Ф ° Ф 4 Ф ° °

Ф 4 Ф ф б ° ° Ф

° ° б Ф б ° 4 °

ХхХХМХхХ

XXXXXX хх тххх

x>. xxxx смх

ХХ Х

1803914

:П

° °

:00000

:00 о о

0 о о

1803914

° °

° ° Ф °

° °

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

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

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

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

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