Модуль умножения полей

 

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

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

СОЦИАЛИСТИЧЕСНИХ РЕаЪЬЛИК

„„SU„„ !444

А1 (51)4 С 06 Р

ОПИСАНИЕ ИЗОБРЕТЕНИ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Ъ. E

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4287369/24-24 (22) 20.07.87 (46) 15.12.88. Бюп. Ф 46 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.Е.Золотовский и P,Â.Êîðoáêîâ (53) 681. 3 (088 . 8) (56) Авторское свидетельство СССР

Ф 1229755, кл. С 06 F 7/52, 1984.

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

В 888109, кл. G 06 F 7/52, 1978. (54) МОДУЛЬ УМНОЖЕНИЯ ПОЛЕЙ (57) Изобретение относится к вычислительной технике и может быть использовано при реализации в многопроцессорных системах операций умножения полей, Целью изобретения является повьппение быстродействия. Эта цель достигается тем, что в модуль умножения полей, содержащий табличный блок 2 формирования произведения, блок 6 суммирования и регистр 8, введены блоки 4, 7 умножения на один разряд и элемент И 5 с соответствующими связями. Умножение в модуле производится в коде "опережающий перенос".

3 ил.

1444 756

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

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

На фиг. 1 изображена схема модуля умножения полей;, на фиг. 2 — блок суммирования; на фиг. 3 — временные диаграммы тактовых импульсов.

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

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

8, третий информационный вход 9 модуля, четвертый информационный вход

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

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

Блок 6 суммирования (фиг. 2) содержит сумматор 19, группу усилителей 20, элементы И 21-23, элементы 30

И-ИЛИ 24-26, элементы ИЛИ-НЕ 27-29, элемент ИЛИ 30, триггеры 31-33, усилители 34 и 35. Усилители 20, 34 и

35 являются управляемыми, с трестабильными выходами.

Обозначения на временных диаграм рах (фиг. 3) соответствуют обозначениям на фиг. 1, Умножение полей производится по сле дующему алгоритму. Все поле Х делится 40 на группы .Х=Х =Х ...X аналогично и поле У=У У ...У g, где и -(и1

Х=Х„2 +Х .2 +...X„2

Тогда и

S =XY=g ХY. 2 2

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

)= 1 причем S = О; j = 1,2,...N.

„55

Таким образом, при умножении полей необходимо перемножать группы Х;У;, с учетом веса группы Х,. просуммиро вать полученные произведения и реэуль4 тат сложить с текущей суммой $ °, .

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

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

Для уменьшения времени пробега переноса при суммировании использован код с опережением переноса. Код с опережением переноса жестко связан с двоичной системой счисления и не изменяет характер представления чисел, Формируется он следующим образом. Поле разбивается на одинаковые группы по К разрядов каждая (К вЂ” разрядность процессорных элементов, используемых для суммирования) . При сложении групп в младший разряд всегда добавляется перенос, кроме последней группы. Для того, чтобы результат бып верен во всех группах, кроме первой, вводятся старшие дополнительные разряды, куда записывается " 1" со значком минус.

Если перенос из группы есть, то он суммируется со значением дополнительного разряда (-1+1=0), в противном случае дополнительный разряд остается без изменения. Максимальное значение в дополнительных разрядах образуется, когда суммируются группы, в дополнительных разрядах которых стоят

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

Чтобы перенос П.не накапливался, вводится второй такт суммирования, точнее, вычитания переносов, При вычитании переносов дополнительные разряды обнуляются, Нетрудно проверить, что при вычитании в дополнительном разряде может возникнуть либо "-1", либо "0", т.е. второй такт суммирования переводит результат вновь в код

"опережающий перенос".

Произведение Р,, учитывая, что Х и У записаны в коде "опере1 жающий перенос", можно записать следующим образом:

Р. =(П„П„+ П„(Х;)+ П„(У; )+(X ) (У; )

Так как П= (О 1 3, то Р; может содержать только один дополнительный разряд. Произведение группы множимого на группу множителя дает произведение длиной в две группы, причем в

14447 старшей группе дополнитсльный разряд может содержать не меньше "-1", т.е.

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

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

"-1", то их произведение дает "+1", и, следовательно, "-1" в дополнительном разряде одного из произведений следует убрать. В качестве такового выбрано произведение множимого на дополнительный разряд множителя, Факт наличия двух " 1" в дополнитель- ных разрядах множимого и множителя 4р определяется на элементе И 5.

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

2) в младший разряд старшего блока суммирования добавляется перенос, если в дополнительном разряде младшего хранится "0" или "+1". Одновременно, чтобы сумма не изменилась, н дополнительный разряд младшего блока суммирования добавляется "-1", в результате.чего там фиксируется, либо "-1", 56 4 либо 0". После суммирования осуществляется сдвиг в сторону младших разрядов путем перезаписи содержимого регистров 8 из старших разрядов в младшие разряды. Одновременно на входы 3 всех модулей умножения поступает новая группа разрядов множителя.

Процесс повторяется столько раз, на сколько групп разбито поле множителя, Рассмотрим, как выполняется суммирование и формируется. значение дополнительного разряда в блоке 6 суммирования, работающем в коде "опережающий перенос" (фиг, 2). Сумматор

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

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

5 1444

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

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

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

1444756

Составитель А.Клюев

Редактор А.Ревин Техред M. Ходанич

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

Заказ 6506/47 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4