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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК ЯО 1444(51) Р 2 ОПИСАНИЕ ИЗОБРЕТЕНИ 21) 22) 46) 71) ьс ст 53 В 88 раэСУДАРСТВЕННЫЙ КОМИТЕТ СССРОДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ТОРСКОМУ СВИДЕТЕЛЬСТВ 4287369/24-2420.07.8715.12.88. Бюп. Ф 46Таганрогский радиотехническитут им. В.Д.КалмыковаВ.Е.Золотовский и Р.В.Коробк681. 3 (088 . 8)Авторское свидетельство СССР9755, кл. С 06 Р 7/52, 1984.торское свидетельство СССР109, кл . С 06 Г 7/52, 1978.(54) МОДУЛЬ УМНОЖЕНИЯ ПОЛЕЙ(57) Изобретение относится к вычистельной технике и может быть исползовано при реализации в многопроцесорных системах операций умноженияполей, Целью изобретения являетсяповьппение быстродействия. Эта цельдостигается тем, что в модуль умножения полей, содержащий табличныйблок 2 формирования произведения,блок 6 суммирования и регистр 8, вдены блоки 4, 7 умножения на одинряд и элемент И 5 с соответствующисвязями. Умножение в модуле произвдится в коде "опережающий перенос"1444 756 Изобретение относится к вычислительной технике и может быть использовано при конструировании многопроцессорных систем с программируемойархитектурой,Цель изобретения - повышение быстродействия модуля умножения полей.На фиг. 1 изображена схема модуляумножения полей;. на Фиг, 2 - блоксуммирования; на фиг. 3 - временныедиаграммы тактовых импульсов.Модуль умножения полей (Фиг. 1)содержит первый информационный вход1 модуля,.табличный блок 2 формирования произведения, второй информационный вход 3 модуля, первый блок 4 умножения на один разряд, элемент И 5,блок 6 суммирования, второй блок 7умножения на один разряд, регистр 208, третий информационный вход 9 модуля, четвертый информационный вход10 модуля, пятый информационный вход11 модуля, первый 12, второй 13 итретий 14 выходы модуля,первый 15, 25второй 16, третий 17 и четвертый тактовые входы модуля.Блок 6 суммирования (фиг, 2) содержит сумматор 19, группу усилителей 20, элементы И 21-23, элементы 30И-ИЛИ 24-26, элементы ИЛИ-НЕ 27-29,элемент ИЛИ 30, триггеры 3 1-33, усилители 34 и 35. Усилители 20, 34 и35 являются управляемыми, с трестабильными выходами.35Обозначения на временных диаграммах (фиг. 3) соответствуют обозначениям на фиг. 1.Умножение полей производится по следующему алгоритму, Все поле Х делится 40на группы .Х=Х,=Х Х, аналогично иполе У=У,УУ , где и - (и 1Х=Х 2+Х 2 +Х 2 Тогдаю еЯ = ХУ=2; Х,У, 2 2 Эта операция реализуется Рекурент но, т.е,й причем Б = 0; 1 = 1,2,И.55Таким образом, при умножении полей необходимо перемножать группы Х;У;, с учетом веса группы Х,. просуммировать полученные произведения и реэультат сложить с текущей суммой БДля повышения быстродействия количество множитслей должно быть равным М.Модуль умножения полей работаетсл едующим обр а з ом.Рассмотрим работу одного модулятора умножения полей (фиг. 1).Для уменьшения времени пробегапереноса при суммировании использованкод с опережением переноса. Код сопережением переноса жестко связанс двоичной системой счисления и неизменяет характер представления чисел,Формируется он следующим образом. Поле разбивается на одинаковые группыпо К разрядов каждая (К - разрядностьпроцессорных элементов,используемыхдля суммирования), При сложении группв младший разряд всегда добавляетсяперенос, кроме последней группы, Длятого, чтобы результат бып верен вовсех группах, кроме первой, вводятсястаршие дополнительные разряды, куда записывается "1" со значком минус.Если перенос из группы есть,то онсуммируется со значением дополнительного разряда (-1+1=0), в противномслучае дополнительный разряд остается без изменения. Максимальное значение в дополнительных разрядах образуется, когда суммируются группы, вдополнительных разрядах которых стоят"-1", тогда И= - 1-1-1=-3 (третьядобавляется из-"за опережающего переноса, который вводится в младший разряд старшей группы при суммировании),Чтобы перенос 11.не накапливался, вводится второй такт суммирования, точнее, вычитания переносов, При вычитании переносов дополнительные разряды обнуляются, Нетрудно проверить,что при вычитании в дополнительномразряде может возникнуть либо "-1",либо "О", т.е, второй такт суммирования переводит результат вновь в код"опережающий перенос",Произведение Р учитывая,что Х и У записаны в коде "опережающий перенос", можно записать следующим образом: Р ( П П +П .(Х,)+П (У,) (Х) (У ) Так как П= 0,-13, то Р; может содержать только один дополнительный разряд. Произведение группы множимого на группу множителя дает произведение длиной в две группы, причем вз 14старшей группе дополнительный разрядможет содержать не меньше "-1", т.е.Пр. = -1,0,1 , а дополнительный разряд в младшей группе всегда равеннулю.Значащие разряды множимого с первого информационного входа 1 модуляпоступают на первый вход блока 2, азначащие разряды множителя со второго информационного входа 3 модуля поступают на второй вход табличногоблока 2 формирования произведения,где происходит их перемножение. Одновременно множимое поступает навход блока 4 умножения на один разряд, на второй вход которого поступает значение дополнительного разрядамножителя. Аналогично для множителя,значащая часть которого поступает наблок 7 умножения на один разряд, навторой вход которого поступает значение дополнительного разряда множимого. На выходах блоков умножения наодин разряд появляется либо нуль,либо дополнительный код числа навходе в зависимости от значения второго входа (0,-1). При взятии дополнения знак числа интерпретируется,как "-1", и является дополнительнымразрядом. Если в дополнительных разрядах и множимого, и множителя стоят"-1", то их произведение дает "+1",и, следовательно, -1 в дополнительном разряде одного из произведенийследует убрать. В качестве таковоговыбрано произведение множимого надополнительный разряд множителя,Факт наличия двух " 1" в дополнитель-ных разрядах множимого и множителяопределяется на элементе И 5,Суммирование осуществляется в дваэтапа. На первом этапе складываютсязначение, хранимое в регистре 8, изначения произведений с выходов блоков 4 и 7 умножения на один разряд,Здесь возможны три случая при сложении; 0,-1,+1, Чтобы избежать накопления положительного переноса на втором шаге суммирования (суммирование значений, получаемых с выхода блока 2) в младший разряд старшего блока суммирования добавляется перенос, если в дополнительном разряде младшего хранится "О" или "+1", Одновременно, чтобы сумма не изменилась, н дополнительный разряд младшего блока суммирования добавляется "-1", в результате.чего там фиксируется, либо "-1", 44756 2530 35 4550 5 10 15 20 либо "О". После суммирования осуществляется сдвиг в сторону младших разрядов путем перезаписи содержимого регистров 8 из старших разрядов в младшие разряды. Одновременно на входы 3 всех модулей умножения поступает новая группа разрядов множителя. Процесс повторяется столько раз, на сколько групп разбито поле множителя.Рассмотрим, как выполняется суммирование и формируется. значение дополнительного разряда в блоке 6 суммирования, работающем в коде "опережающий перенос" (фиг, 2). Сумматор 19 - "обычный комбинационный четырехвходовой сумматор. Выход старшего разряда интерпретируется как перенос с весом "20", а перенос из старшего разряда интенпретируется как перенос с весом "2 ", Элементы И-ИЛИ 26-24 соответственно формируют значение дополнительного разряда (-2,-1,+1),которые запоминаются в триггерах 3133. Значение "-1", кроме того, переписывается в дополнительный разрядрегистра 8, Если в дополнительныхразрядах нет отрицательных величин,то во втором такте суммирования встаршую группу передается "+1", а в даннои группе в дополнительном разряде фиксируется "-1" по входу у (цепь состоит из элемента И 22 и трехстабильного усилителя 35), что не позволяет переносу бежать дальшей анной группы. Значение "-2" может озникнуть только на первом шаге суммирования. На втором шаге складывают" ся только три положительныХ числа,поэтому обязательно будет существо вать положительный перенос, в противном случае это будет означать, что из группы может возникнуть перенос с весом "2 ", что невозможно.Во втором такте возможно образование положительного переноса "+1". В этом случае он должен быть передан в старшую группу, Так как следующий шагсдвиг, то перенос запоминается и на следующем шаге в первом такте суммирования добавляется в младший разряд собственной группы (это эквивалентно прибавлению "1" в перенос старшей группы) . Нетрудно заметить, что эта операция эквивалентна операции запоминания переноса, Таким образом, все возможные переносы после выполнения двух тактов суммирования оказываются отработанными,5 1444Формула изобретения Модуль умножения полей, содержащий табличный блок формирования про 6 изведения, блок суммирования и регистр, причем входы разрядов первого и второго сомножителей табличного блока формирования произведения соединены соответственно с входами зна чащих разрядов первого и второго информационных входов модуля, выходы значащих разрядов блока суммирования соединены с входами значащих разрядов регистра, первый и второй так товые входы модуля соединены соответственно с входом синхронизации и разрешения сложения блока суммирования, входы разрядов третьего информационного входа модуля соединены с входа ми разрядов первого слагаемого блока суммирования, входы разрядов второго и третьего слагаемых которого соединены соответственно с выходами старших разрядов табличного блока формирования произведения и с выходами значащих разрядов регистра, выходы младших разрядов табличного блока формирования произведения являются первым выходом модуля, о т л и ч а ю- З 0 щ и й с я тем, что, с цельюповышения быстродействия, он содержит первый и второй блоки умножения на один разряд и элемент И, причем выходы значащих разрядов и выход дополни тельного разряда регистра являются вторым выходом модуля, третий выход которого соединен с выходом переноса блока суммирования, четвертый информационный вход которого соединен с 40 входом переноса блока суммирования, входы разрядов первого и четвертого слагаемых которого соединены соответ 756 6ственно с выходамй значащих разрядов первого и второго блоков умножения на один разряд, входы разрядов первых сомножителей которых соединены соответственно с входами значащих разрядов первого и второго информационных входов модуля, вход до 1 толнительного разряда второго информационного входа модуля соединен с входом второго сомножителя, первого блока умножения на один разряд и с первым входом элемента И, второй вход которого соединен с входом второго сомножителя второго блока умножения на один разряд и с входом дополнительного разряда первого информационного входа модуля, входы значащих разрядов и дополнительного разряда пятого информационного входа которого соединены соответственно с входами значащих и дополнительного разрядовегистра выход элемента И соединен с входом блокировки первого блока умножения на один разряд, выходы дополнительных разрядов первого и второго блаков умножения на один разряд и выход дополнительного разряда регистра соединены соответственно с входами дополнительных разрядов слагаемых блока суммирования, выход дополнительного разряда которого соединен с входом дополнительного разряда региетра, второй тактовый вход модуля соединен с входами разрешения первого и второго блоков умножения на один разряд, третий тактовый вход модуля соединен с входом разрешения табличного блока формирования произведения и с входом разрешения выдачи переноса блока суммирования, вход разрешения выдачи результата которого соединен с четвертым тактовым входом модуля.аказ 6506/47 Тираж 704 ВНИИПИ Государственно по делам изобретений 113035, Москва, Ж, Ракомитета СССР открытий кая наб., д. 4/