Устройство для вычисления сумм произведений

Устройство для вычисления сумм произведений

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СУММ ПРОИЗВЕДЕНИЙ по авт.св.№905814, отличающееся тем, что, с целью повышения быстродействия при нахождении произведения одиночных пар операндов, в него введены элемент НЕ, элемент И-НЕ, коммутатор , причем вход элемента НЕ соединен с шиной управления устройства , а выход - с первым входом элемента И-НЕ, второй вход которого соединен с шиной тактовых импульсов устройства, вход элемента НЕ соеди нен с первым управляющим входом каждого (i,j)-ro вычислительного элемента матрицы, управляющим входом коммутатора, выход элемента PIHE соединен с вторым управляющим входом каждого (i,j)-ro вычислительного элемента матрицы, с вторым управляющим входом накапливающего сумматора, с управляющими входами первого и второго регистров операнда, управляющими входами первого, второго, третьего триггеров , первый и второй информационные выходы накапливающего сумматора соединены соответственно с первым и вторым входами коммутатора, выход которого является выходом устройства , а в каждый

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

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

PECflYEiËÈH (19) (1И

3(SD G 06 F 7 52

Э "- ъ > .

;> >>ц

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

К ABTOPCH0MV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

; (61 ) 905814 (21) 3483444/18-24 (22) 17.08.82 (46) 23 ° 11.83. Бюл. М 43 (72) В.П.Денисенко, Г.N.Ëóöêèé, A.Н.Долголенко и A.Ã.Çàñûïêèí (53) 681.325(088.8) (56) 1.авторское свидетельство СССР, 9 905814, кл. G 06 F 7/52, 1980 (прототип), (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

СУММ ПРОИЗВЕДЕНИЙ по авт.св.9905814, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия при нахождении произведения одиночных пар операндов, в него введены элемент НЕ, элемент И-НЕ, коммутатор, причем вход элемента НЕ соединен с шиной управления устройства, а выход — с первым входом элемента И-НЕ, второй вход которого соединен с шиной тактовых импульсов устройства, вход элемента НЕ соеди> нен с первым управляющим входом каждого (i ) -го вычислительного элемента матрицы, управляющим входом коМмутатора, выход элемента ИНЕ соединен с вторым управляющим входом каждого (i,))-ro вычислительного элемента матрицы, с вторым управляющим входом накапливающего сумматора, с управляющими входами первого и второго регистров операнда, управляющими входами первого, второго, третьего триггеров, первый и второй информационные выходы накапливающего сумматора соединены соответственно с первым и вторым входами коммутатора, выход которого является выходом устройства, а в каждый (i )-ый вычислительный элемент введены второй, третй,четвертый, пятый элементы И, первый, второй, третий и четвертый элементы ИЛИ, причем первый вход второго элемента И, управляющие входы первого, второго триггера, триггера поразрядной суммы и триггера переноса объединены и являются вторым управляющим входом (i,J )го вычислительного элемента, второй вход второго элемента И, первые входы третьего, четвертого и пятого элементов И объединены и являются первым управляющим входом (i,J)-го вычислительного элемента, второй вход третьего элемента И соединен с информационным входом триггера поразрядной суммы, второй вход чет.вертого элемента И соединен с информационным входом триггера переноса, второй вход пятого элемента И соедй- нен с информационным входом второго триггера, выход второго элемента И и выход первого триггера соединены соответственно с первым и вторьпл входами первого элемента ИЛИ, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с выходом четвертого элемента ИЛИ и является вторым выходом (i,j)-ro вычислительного элемента, выход первого элемента ИЛИ является первым выходом (i,j)-ro вычислительного элемента, выход второго элемента ИЛИ соединен с входом поразрядной суммы одноразрядного сумматора, вход переноса которого соединен с выходом третьего элемента ИЛИ, выход третьего элемента И и выход триггера поразрядной суммы соединены соответственно с первым и вторым входами второго элемента ИЛИ, выход четвертого элемента И и выход триггера переноса соединены соответственно с первым и вторым входами третьего элемен:та ИЛИ, выход пятого элемента И и выход второго триггера соединены

;соответственно с первым и вторым входами четвертого элемента MfIH, 1056184 а в накапливающий сумматор введен (п + 2 ) разрядный сумматор, причем выходы второй группы сумматоров и (и + 2) разрядного сумматора явялются соответственно первым и вторым информационным выходами накапли. вающега сумматора, первый и второй информационные входы (и + 2) разрядного сумматора соединены соответственно с информационными входами

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

По основному авт.св. Р 905814 известно устройство для вычисления сумм произведений, содержащее матрицу вычислительных элементов, которая 10 содержит и+1 строк, первые три строки имеют 2n+1 вычислительных элементов, каждая последующая строка матрицы имеет на один вычислительный элемент меньше, последняя строка содержит n+3 вычислительных элемен-. тов, (и + 1)-разрядные первый и второй регистры операнда (где п — разрядность операндов), первую и вторую группу элементов И-НЕ, накапливающий сумматор, причем первая входная шина соединена с информационными входами первого регистра операнда, вторая входная шина соединена с информационными входами второго регистра операнда, выходы значащих Разрядов первого регистра операнда и второго регистра операнда соответственно соединены с первыми входами элементов И-HE первой и второй групп, вторые входы элементов И-НЕ первой группы соедине-ЗО ны с выходом знакового разряда второго регистра операнда, вторые входы элементов И-НЕ второй группы соединены с выходом знакового разряда пеРвого регистра операнда, первые и 35 вторые информационные входы накапли. вающего сумматора соответственно соединены с1(п + 2 ) младшими выходами и с (n+2) старшими выходами вычислительных элементов последней строки матрицы, первый управляющий вход накапливанлцего сумматора под-. ключен к шине установки в ноль, выходы накапливающего сумматора соединены с выходной шиной устРойства, 45 шина тактовых импульсов соединена с управляющим входом накапливающего сумматора, с управляющим входом сумтретьего и четвертого регистров, входы сброса второго, третьего и четвертого регистров объединены и являются первым управляющим входом накапливающего сумматора, тактовые входы первого, второго, третьего и четвертого регистров объединены и являются вторым управляющим входом накапливающего сумматора. матора, с управляющим входом каждого вычислительного элемента матрицы, с управляющими входами первого и второго регистров операндов, первый, второй, третий триггеры, первый и второй выходы каждого (i,1)ro вычислительного элемента (i= 1

n g = 2,...>2п) соединены соответственно с первым входом (i +1, -1)-ro вычислительного элемента и вторым входом (i+1, j+1)-го вычислительного элемента, а выходы поразрядной суммы и переноса соответственно с входом поразрядной суммы (i +1, j)-roi.вычислительного элемента и входом переноса (i +1, (j-1)-го вычислительного элемента, лервый выход каждого (i,))-го вычис;лительного элемента (i = 1,2,...,п „

j = l) соединен с вторым входом (i + 1,j)-ro вычислительного эле)мента, а выход поразрядной суммыс входом поразрядной суммы(i+1, j ) -ro вычислительного элемента, выход переноса (i,g)-ro вычислительного элемента (i = 1, 2, 1 = 2п.+.1) соединен с входом переноса (i+ 1, j ) -го вычислительного элемента, вход переноса (2п+1)-го вычислительного элемента второй строки матрицы соединен с выходом первого триггера, вход переноса (2п+1)-го вычислительного элемента третьей строки матрицы соединен с выходом второго триггера, информационный вход которого соединен с выходом третьего триггера, управляющие входы первого, второго и третьего триггеров объединены и подключены к шине тактовых импульсов, первые и вторые входы вычислительных элементов нечетных столбцов первой строки матрицы поразрядно связаны соответственно с выходами второго и первого регистров операнда, первые и вторые входы .вычислительных элементов четных столбцов первой строки матрицы поразрядно связаны соо.рветственно с tl младшими выходами первого регистра операнда

1056184

25 и с П старшими выходами второго регистра операнда, входы поразрядной суммы и переноса вычислительных элементов с первого по Л -ый столбец первой строки матрицы поразрядно соединены соответственно с выходами элементов И-НЕ второй группы и с выходами элементов И-HE первой группы, а входы поразрядной суммы и пе,реноса вычислительных элементов остальных столбцов первой строки мат- 10 рицы соответственно с выходом знакового разряда первого разряда второго регистра операнда, которые соответственно соединены с входами первого и третьего триггеров, а каждый вычислительный элемент содержит полусумматор, элемент И, первый, второй триггеры, триггер переноса и триггер поразрядной суммы, причем тактовые входы первого, второго триггеров, триггеров поразрядной суммы и переноса объединены и являются управляющим входом вычислительного элемента, информационный вход первого триггера является первым входом вычислительного элемента, информационный вход второго тригге ра является вторым входом вычислительного элемента, информационные входы триггеров поразрядной суммы и переноса являются соответственно входами поразрядной суммы и переноса вычислительного элемента, выход первого триггера соединен с первым входом элемента И и является первым выходом вычислительного элемента, 35 выход второго триггера соединен с вторым входом элемента И и является вторым .выходом вычислительного ,элемента, выход элемента И соединен с первым входом полусумматора, вто- 40 рой и третий входы которого соединены соответственно с выходами триггеров поразрядной суммы и переноса, первый выход полусумматора является выходом переноса вычислительного 45 элемента, второй выход полусумматора является выходом поразрядной суМмы вычислительного элемента, а накапливающий сумматор содержит первую гРУппУ из (и+1од2Н+2) полУсУмматоров, aTopyro группу Hs (n+logN+1)разрядный регистр, третий и четвер,тый (и+2)-разрядные регистры, причем тактовые входы первого, второго третьего и четвертого регистров объединены и являются вторым управ:ляющим входом накапливающего сумматора, информационные входы третьего и четвертого регистров являются 60 соответственно вторым и первым информаицонными входами накапливающе го сумматора, (n+1) младшие разряды третьего и четвертого регистров поразрядно соедийены соответственно . 65 с первыми и вторыми входами соответствующих (n+1)-ых младших подусумматоров первой группы, старшие разряды третьего и четвертого регистров соответственно соединены с первым и вторым входами (log>N+1)го полусумматора первой группы, третьи входы (n+log<Н+1) старших полусумматоров первой группы соединены поразрядно с выходами второго регистра, выходы (n+log l младших и выходы (n+log ными входами первого регистра, выходы (и+lоg>И+1) полусумматоров второй группы йоразрядно соединены с информационными входами второго регистра и являются выходами накапливаксцего сумматора, вход установки в ноль первого регистра является первым управляющим входом накаплива" кщего сумматора (1) .

С помощью этого устройства возможно нахождение (n+log N. 1) старших разрядов суммы произведений Н пар операндов, представленных дополнительным кодом, при этом на каждом следующем такте на входы устройства может быть принята новая пара сомножителей (n — разряднссть операндов). Для получения на 2-ыходах устройства результата с распространен« ными переносами на его входы в течение (n+log2 N) тактов должны быть поданы нулевые сомножителя..При этом операнды новой пос). довательности на входы устройстьа могут подаваться на (n+loggN+1)-ом такте.

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

2 ма предыдущей пары. !

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

Поставленная цель достигается тем, что в устройство вводятся элемент НЕ, элемент H-HE, коммутатор, причем вход элемента НЕ соединен с шиной управления устройства, а выход — с первым входом элемента И-НЕ, второй вход которого соединен с шиной тактовых импульсов устройства, вход элемента НЕ соединен с первым управляющим входом

1056184 каждого (:;,J)-го вычислительного элемента матрицы, управляющим входом.коммутатора, выход элемента ИНЕ соединен с вторым управляющим входом каждого (,))-ro вычислитель ного элемента матрицы, с вторым

5 управляющим входом накапливающего сумматора, с управляющими входами первого и второго регистров операнда, управляющими входами первого, второго, третьего триггеров, первый и второй информационные выходы накапливающего сумматора соединены.соотверственно с первым и вторым входами коммутатора, выход которого является выходом устройства, а в каж-15 дый (.-,,!)-ый вычислительный элемент вне ..."-ы второй, третий, четвертый, пятый элементы И, первый, второй, третий и четвертый элементы ИЛИ, причем первый вход второго элемента И, управляющие входы первого, второго триггера,.триггера поразрядной суммы и триггера переноса объединены и являются вторым управляющим входом (i,g)-ro вычислительного элемента, второй вход второго элемента И, первые входы третьего, четвертого и пятого элементов И объединены и являются первым управляющим входом (,J)-ro вычислительного элемента, второй вход третьего элемента И соединен с информационным входом триггера поразрядной суммы, второй вход четвертого элемента И соединен с информационным входом триггера переноса, второй вход пятого элемента И соединен с информационным входом второго триггера, выход второго элемента И и выход первого триггера соединены соответственно с первым и вторым 40 входами. первого элемента ИЛИ, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с выходом четвертого элемента ИЛИ и является вторым выходом (i,j )-го вычислительного элемента, выход второго элемента ИЛИ соединен с входом поразрядной суммы одноразрядного сумматора, вход переноса которого соединен с выходом третьего элемента ИЛИ, выход третьего элемента И и выход тригге ра поразрядной суммы соединены соотверственно с первым и вторым входами второго элемента ИЛИ, выход четвертого элемента И и выход триггера переноса соединены соответственно с первым и вторым входами третьего элемента ИЛИ,выход пятого элемента И и выход второго триггера соединены соответственно с первым и вто- 60 рым входами четвертого элемента ИЛИ, а в накапливающий сумматор введен (n+2) разрядный сумматор, причем выходы второй группы сумматоров и

;(n+2) разрядного сумматора являются g$ соответственно первым и вторым информационными выходами накапливающего сумматора, первый и второй информационные входы (n+2) разрядного сумматора соединены соответственно с информационными входами третьего и четвертого регистров, входы сброса второго, третьего и четвертого регистров объединены и являются первым управляющим входом накапливакщего сумматора, тактовые входы первого, второго, третьего и четвертого регистров объединены и являются вторым управляющим входом накапливающего сумматора, На фиг. 1 изображена структурная схема предлагаемого устройства, на фиг. 2 — структурная схема вычислительного элемента, на фиг, 3 структурная схема накапливающего сумматора.

Устройство состоит из матрицы 1 вычислительных элементов, имеющей и+1 строку, причем первые три строки содержат по (2n+1)-му вычислительному элементу, а каждая последующая строка имеет на один вычислительный элемент меньше по сравнению с предыдущей, накапливающего сумматора 2,;регистров. 3 и 4 операндов, группй элементов И-HE 5 и 6, элемента И-НЕ 7, элемента HH 8.и коммутатора 9. Одноразрядный элемент 1 содержит одноразрядный сумматор 10, элемент И 11, триггеры 12 и 13, триггер 14 поразрядной суммы, триггер 15 переноса, элементы И 16-19, элементы ИЛИ 20-23.

Накапливающий сумматор 2 содержит регистры 24-27, группы одноразрядных сумматоров 28 и 29 и (n+2) разрядный сумматор 30. Кроме того, в устройстве имеется тактовая шина 31, шина 32 установки в "0", шины 33 и 34 операндов, управляющая шина 35, выходная шина 36 и триггеры 37-39.

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

При наличии на управляющей шине 35 логического "0" устройство принимает на каждом такте новую пару операндов, при этом элементы И 16-19 в вычислительных элементах 1 заперты "низким" управляющим уровнем, а выходы второй группы сумматоров 28 через коммутатор 9 поступают на выходную шину 36.

При наличии на управляющей шине 35 уровня логический "1" сигнал с выхода элемента HE 8 поступает на вход элемента И-НЕ 7 и запрещает поступление тактирующих импульсов на все триггеры и регистры устройстве. Тем самым он запрещает прием информации в триггеры 12-15

1056184 каждого (i,J)-ro вычислительного элемента матрицы 1 и регистры 24-27 накапливающего сумматора 2. Одновременно этот сигнал, поступая на первые входы элементов И 16-19 каждого вычислительного элемента матрицы 1 разрешает распространение сумм и переносов в матрице 1 вычислительных элементов и накапливающем сумматоре 2. Содержимое регистров 3 и 4 (где находится пара сомножителей A и В в дополнительном двоичном коде) передается на элемент И 11, на первый вход которого будет подан код Ь а b,... а„

ИЛИ 21, а также через элементы И 18 и ИЛИ 22 на входы сумматоров 10 вычислительных элементов первой строки через группы элементов И-НЕ

5 и 6 поступят удвоенные обратные коды содержимого регистров 3 и 4 °

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

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

Формирование произведения в виде поразрядных сумм и переносов происходит в результате их распространения с i-ой строки íà i+1 строку и т.д. до последней строки матрицы вычислительных элементов. Причем распространение переносов i-ой строки матрицы 1 вычислительных элементов к i+1 строке матрицы 1 осу- ществляется через элементы И 16 и

ИЛИ 20 со сдвигом на один разряд вле. во, а через элементы И 19 и ИЛИ 23— со сдвигом на разряд вправо, что обеспечивает формирование всех и+1 частичных произведений. С выходов последней строки матрицы 1, содержащей n+3 вычислительных элементов, значения (n+2)-ых старших поразрядных сумм и переносов, представляющих и+2 старших разряда произведения, поступают на первые и вторые входы (n+2)-ых разрядного сумматора 30 и с его выходов после распрос. транения переноса произведение пары операндов через коммутатор 9 поступает на выходную шину 36, при этом коммутатор 9 пропускает информацию с выходов (и+2) разрядного сумматора 30 при "высоком" уровне на шину 35. Длительность такта в известном устройствене может быть меньше суммы задержек распростране- ния сигнала через триггер (t y ), одноразрядный сумматор („) и эле мент И (t>< ) вычислительного элемента.

10 Я>+ щ+ 4 °

При использовании элементов 155 серии эти задержки соответственно составляют: с = 20 нс, с,; — 15 нс, 8 нс, а минимальное время так15 та tr = 43 нс.

Таким образом, в известном устройстве на выходе матрицы 1 вычисли. тельных элементов через Tq = (и+1)

xt появится произведение пары операндов в виде поразрядных сумм и переносов, Для получения произведения пары операндов с распространенными переносами необходимы еще n+2 такта работы накапливающего сумматора, при этом новые операнды на выходы устройства принимать нельзя.

Таким образом, при разряд ности операндов и = 16 на выходе устройства произведение появится через (2и+3) такта или через 1505 нс 1,5 мкс.

В предлагаемом устройстве задержка распространения сигнала через вычислительный элемент состоит из суммы задержек на двух элементах И (2t >), элементе ИЛИ (шщ одноразрядного сумматора (1 „„).

40 При его реализации на элемейтах

155 серии задержка распространения сигнала через одноразрядный элемент составит с = 2ti + t e+,„„= 2 8 + 8 +

45 +8 + 15 = 39 (нс) и 8 н

Так как матрица 1 вычислительных элементов состоит из (n+1)-ой строки

1 t

Г то через Т, = (и+1 ) ° t на ее выходе появится произведение пары операндов в виде поразрядных сумм и переносов. Это время составляет Т (16 + 1) 39 = 663 нс.

Для получения произведения с распространенными переносами необходимо поразрядные суммы и переносы подать на 18 разряд (при и = 16), сумматор с групповым переносом, реализованный на 5-ти микросхемах

Н155ИПЩ и одной микросхеме К155ИП4, О0 при этом время задержки распространения сигнала составит T = 90 нс.

Общее время умножения пары операндов,таким образом, в предлагаемомустройстве составляет 753 нс:0,75 мкс, что

65 в 2 раза меньше, чем в известном.

1056184, 9

Результат без коррекции

Дополнительные коды А и В

Коррекция

Сомножители

А и В

АхВ АхВ

А 0 В 0

А 0).В 0

А О; В 0

A 0) В О

=4-2В-2A+AB

П р и м е ч а н и е. При А 0 и В 0 на выходах матрицы 1 вычислительных элементов. будет результат -2В -2A,+АВ, так как четверка представляет собой перенос в несуществующий разряд.

А> В

1+(1-1) у

A i 1+ (1-В)

1+-(1-А); 1+(1-B)! (1+(1-A)) xB = 2В-AB

Ax(1+ (1-B)) =2A — AB (1+(1-х)) х (1 (1-в)2

+2 (1-B)

+2 (1-A)

+2A +2В

1056184

1056184

1056184

Составитель Л.Медведева

Техред Л.Лч

Корректор A. Ильин

Редактор A Êoýîðèç

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4

Заказ 9307/42 Тираж 706 Подписное

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

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