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

4 СД

О

Изобретение относится к вычислительной технике и может быть использовано при конструировании многопроцессорных систем с программируемой архитектурой.

Цель изобретения - повышение быстродействия модуля умножения полей,

На фиг. 1 изображена схема модуля умножения полей;, на фиг. 2 - блок

суммированияj на фиг. 3 - временные диаграммы тактовых импульсов.

Модуль умножения полей (фиг. 1) содержит первый информационный вход

Iмодуля,.табличный блок 2 формирова ния произведения, второй информационный вход 3 модуля, первый блок 4 умножения на один разряд, элемент И 5, блок 6 суммирования, второй блок 7 умножения на один разряд, регистр 8, третий информационный вход 9 модуля, четвертый информационный вход

10 модуля, пятый информационный вход

IIмодуля, первый 12, второй 13 и третий 14 выходы модуля, первый 15, второй 16, третий 17 и четвертый тактовые входы модуля.

Блок 6 суммирования (фиг. 2) содержит сумматор 19, группу усилителей 20, элементы И 21-23, элементы И-ИЛИ 24-26, элементы ИЛИ-НЕ 27-29, элемент ИЛИ 30, триггеры 31-33, усилители 34 и 35. Усилители 20, 34 и 35 являются управляемыми, с треста- бипьными выходами.

Обозначения на временных диаграммах (фиг. 3) соответствуют обозначениям на фиг . 1 .

Умножение полей производится по сдующему алгоритму. Все поле X делитс на группы .,Х 2-. .X(f, аналогично и поле ,У1.. .У ; , где

X Xi-2 +Xi-2 +...Х,,

Тогда

S Г X.Y.

I

ut ш

Эта операция реализуется рекурентно, т.е.

W

Sy S,-.,(Y. Lx,

причем So 0; j 1,2,.,. .N. ее

Таким образом, при умножении полей необходимо перемножать группы Х,-У, с учетом веса группы X. просуммиро вать полученные произведения и реэуль Q

5 0

5

30 с

0

5

0

е

Tat сложить с. текущей суммой S;., . Для повышения быстродействия количество множителей должно быть равным N.

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

Рассмотрим работу одного модулятора умножения попей (фиг. 1).

Для уменьшения времени пробега переноса при суммировании использован код с опережением переноса. Код с о пережением переноса жестко связан с двоичной системой счисления и не изменяет характер представления чисел. Формируется он следующим образом. Поле разбивается на одинаковые группы по К разрядов каждая (К - разрядность процессорных элементов, используемых для суммирования). При сложении групп в младший разряд всегда добавляется перенос, кроме последней группы. Для того, чтобы результат был верен во всех группах, кроме первой, вводятся старшие дополнительные разряды, куда записывается 1 со значком минус. Если перенос из группы есть, то он суммируется со значением дополнительного разряда (), в противном случае дополнительньй разряд остается без изменения. Максимальное значение в дополнительных разрядах образуется, когда суммируются группы, в дополнительных разрядах которых стоят -1, тогда ;in -1-1-1 -3 (третья -1 добавляется опережающего переноса, который вводится в младший разряд старшей группы при суммировании). Чтобы перенос Пне накапливался, вводится второй такт суммирования, точнее, вычитания переносов. При вычитании переносов дополнительные разряды обнуляются. Нетрудно проверить, что при вычитании в дополнительном разряде может возникнуть либо -1, либо О, т.е. второй такт суммирования переводит результат вновь в код опережающий перенос.

Произведение Р., учитывая, что Xj и У| записаны в коде опережающий перенос, можно записать сле- дуюшрм образом:

Р;( П,, (Х;)+П,.(У,-)(Х,) -(У).

Так как П iO,-1 J, то Р может содержать только один дополнительный разряд. Произведение группы множимого на группу множителя дает произведение длиной в две группы, причем в

старшей группе дополнительный разряд может содержать не меньше -1, т.е. Пр. {-1,0,1 1, а дополнительный разряд в младшей группе всегда равен нулю.

Значащие разряды множимого с первого информационного входа 1 модуля поступают на первый вход блока 2, а значащие разряды множителя со второго информационного входа 3 модуля поступают на второй вход табличного блока 2 формирования произведения, где происходит их перемножение. Одновременно множимое поступает на вход блока 4 умножения на один разряд, на второй вход которого поступает значение дополнительного разряда множителя. Аналогично для множителя, значащая часть которого поступает на блок 7 умножения на один разряд, на второй вход которого поступает значение дополнительного разряда множимого. На выходах блоков умножения на один разряд появляется либо нуль, либо дополнительный код числа на входе в зависимости от значения второго входа (0,-1). При взятии дополнения знак числа интерпретируется, как -1, и является дополнительным разрядом. Если в дополнительных разрядах и множимого, и множителя стоят -1, то их произведение дает +1, и, следовательно, -1 в дополнительном разряде одного из произведений следует убрать. В качестве такового выбрано произведение множимого на дополнительный разряд множителя. Факт наличия двух 1 в дополнитель- ных разрядах множимого и множителя определяется на злементе И 5.

Суммирование осуществляется в два этапа. На первом этапе складываются значение, хранимое в регистре 8, и

значения произведений с вькодов блоков 4 и 7 умножения на один разряд. Здесь возможны три случая при сложении: 0,-1,. Чтобы избежать накопления положительного переноса на втором щаге суммирования (суммирование значений, получаемых с выхода блока 2) в младший разряд старшего блока сум шрования добавляется перенос, если в дополнительном разряде младшего

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

либо О, После суммирования осуществляется сдвиг в сторону младших разрядов путем перезаписи содержимого регистров 8 из старших разрядов в младшие разряды. Одновременно на входы 3 всех модулей умножения поступает новая группа разрядов множителя. Процесс повторяется столько раз, на

сколько групп разбито поле множителя.

Рассмотрим, как выполняется суммирование и формируется.значение дополнительного разряда в блоке 6 суммирования, работающем в коде опере-

жающий перенос (фиг. 2). Сумматор 19 - Обычный комбинационный четырех- входовой сумматор. Выход старшего разряда интерпретируется как перенос

с весом

110 d

, а перенос из старшего

разряда интенпретируется как перенос с весом 2. Элементы Й-ИЛИ 26-24 соответственно, формируют значение дополнительного разряда (-2,-1,+1), которые запоминаются в триггерах 3133. Значение -1, кроме того, переписывается в дополнительный разряд регистра 8. Если в дополнительных разрядах нет отрицательных величин, то во втором такте суммирования в старшую группу передается +1, а в данной группе в дополнительном раз- ряде фиксируется -1 по входу (цепь состоит из элемента И 22 и трехстабильного усилителя 35), что не позволяет переносу бежать дальшей данной группы. Значение -2 может возникнуть только на первом шаге суммирования. На втором шаге складывают ся только три положительных: числа, поэтому обязательно будет существовать положительный перенос, в противном случае это будет означать, что из группы может возникнуть перенос с весом 2 , что невозможно.

Во втором такте возможно образова

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

группы), Нетрудно заметить, что эта операция эквивалентна операции запоминания переноса,Таким образом, все возможные переносы после выполнения двух тактов суммирования оказываются отработанными.

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

Модуль умножения полей, содержащий табличный блок форшрования произведения, блок суммирования и per гистр, причем входы разрядов первого и второго сомножитепей табличного блока формирования произведения сое- динену соответственно с входами значащих разрядов первого и второго информационных входов модуля, вькоды значащих разрядов блока суммирования соединены с входами значащих разрядов регистра, первой и второй тактовые модуля соединены соответственно с входом синхронизации и разрешения сложения блока суммирования, входы разрядов третьего информационного входа модуля соединены с входами разрядов первого слагаемого блока суммирования, входы разрядов второго и третьего слагаемых которого соединены соответственно с выходами старших разрядов табличного блока формирования произведения и с выходами значащих разрядов регистра, вькоды младших разрядов табличного блока формирования произведения являются первым выходом модуля, о т л и ч щ и и с я тем, что, с целью повьше- ния быстродействия, он содержит первый и второй блоки умножения на один разряд и элемент И, причем выходы Значащих разрядов и выход дополнительного разряда регистра являются вторым выходом модуля, третий выход которого соединен с выходом переноса блока суммирования, четвертый информационный вход которого соединен с входом переноса блока суммирования, входы разрядов первого и четвертого слагаемых которого соединены соответственно с выходами значащих разрядов первого и второго блоков умножения на один разряд, входы разрядов первых сомножителей которых соединены соответственно с входами значагщ х. разрядов первого и второго информационных входов модуля, вход дополнительного разряда второго информацион10 ного входа модуля соединен с входом второго сомножителя, первого блока умножения на один разряд и с первым входом элемента И, второй вход которого соединен с входом второго сомно-

15 жителя второго блока умножения на один разряд и с входом дополнительного разряда первого информационного входа модуля, входы значащих разрядов и дополнительного разряда пято20.ro информационного входа которого соединены соответственно с входами значащих и дополнительного разрядов .Ьегистра,. выход элемента И соединен

25

с входом блокировки первого блока умножения на один разряд, вькоды допол- нительньк разрядов первого и второго бло-ков умножения на один разряд и выход дополнительного разряда регистра соединены соответственно с входами а ю- 30 дополнительньк разрядов слагаемьк

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

35

40

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

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

с входом блокировки первого блока умножения на один разряд, вькоды допол нительньк разрядов первого и второго бло-ков умножения на один разряд и выход дополнительного разряда регистра соединены соответственно с входами дополнительньк разрядов слагаемьк

V 7 fi8

llJr

Изобретение относится к вычислительной технике и может быть использовано при реализации в многопроцессорных системах операций умножения полей. Целью изобретения ярляется повьшение быстродействия. Эта цель достигается тем, чТо в модуль умножения полей, содержащий табличный блок 2 формирования произведения, блок 6 суммирования и регистр 8, введены блоки 4, 7 умножения на один разряд и злемент И 5 с соответствующими связями. Умножение в модуле производится в коде опережающий перенос. 3 ил. 1 (Л

Составитель А.Клюев Редактор A.Резин Техред М.Ходанич

I J 11

n f-(

2 f9

V

20

Фие.5

Корректор Г.Решетник