Устройство для суммирования м-чисел

 

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных вычислительных устройствах. Целью изобретения является повышение быстродействия. Цель достигается за счет введения в устройство, содержащее в каждом разряде преобразователь 1 двоичного кода в код количества единиц и сумматор 3 по модулю два, доаолнительно (N+K-1) элементов И-ИЛИ 2, где N-разрядность слагаемых, K-количество входных переносов, а также новых связей. Данное устройство реализует параллельный способ суммирования и по числам, и по разрядам, вырабатывая одновременно переносы во все разряды, которые складываются на сумматорах по модулю два с поразрядными суммами. 5 ил.ю 5 табл.

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

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

РЕСПУБЛИН (19) (11): (51)5 С 06 F 7/50

r р. S; г щ,", !

ЧЕ1:",,,Е „д I (ОПИСАНИК ИЗОБРКТЕНИЯ

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ П1НТ СССР

1 (21 ) 4211 885/24-24 (22) 05.02.87 (46) 23 .02.90. Бюл. У 7 (7! ) Одесский политехнический институт (72) О.Н. Паулин, 3.В. Полянский, Н.И. Синегуб и И.В. 01уликов (53) 681.325(088.8) (56) Авторское свидетельство СССР . У 1068932, кл. G 06 F 7/50, 1981.

Авторское свидетельство СССР ф 1159013, кл. G 06 F 7/50, 1983.

2 (54) УСТРОЙСТВО ППЯ СУММИРОВАНИЯ И

ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть исполь зовано в высокопроизводительных вычислительных устройствах. Целью изобретения является повышение быстродействия, Цель достигается за счет введения в устройство, содержащее в каждом разряде преобразователь 1 двоичного кода в код количе ства единиц и сумматор 3 IIo модулю два, дополнительно (11+К-1 ) элементов И-ИЛИ 2, где N — - разрядность слагаемых, К вЂ” количество входных переносов, а также новых связей.

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

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

Целью изобретения является повышение быстродействия устройства для суммирования М чисел.

На фиг. 1 приведена структурная схема ус тройс тв а, на фиг . 2-5 — ч етырехразрядное устройство суммирования четырех чисел.

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

Элементы И-ИЛИ образуют блок 8 формирования параллельных переносов P -P> где N — разрядность слагаемых.

На фиг ° 2 показано, что с целью оптимизации элементов И-ИЛИ выходы преобразователей 1 могут быть объеди- З5 нены внутри преобразователя. Каждый преобразователь 1 имеет также выход нечетности кода, соединенный с вхо-:

I дом S. соответствующего сумматора по

1 40 модулю два.

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

На входы преобразователей ходов (IIK) 1; i-ro разряда (i = 1,N) посту- 45 пают сигналы М слагаемых А, кроме тогт), на ПК 1 первых К разрядов поступают сигналы входных одноразрядных переносов Е ° . ПК 1 вырабатывает L .

1 1 1 сигналов симметрич еских функций, образующих совокупность С, в том числе

1 сигнал частичной суммы S .. Сигналы

С.выходов PK 1; поступают на соот" ветствующие входы элементов И-ИЛИ 2, причем на элемент j-го разряда (j

2, N) поступают определенные сигналы из совокупностей сигналов С, С . На выходах элементов И-ИЛИ 2 образуются сигналы переносов Р во

2-й, ° ..„N-й разряды, а также выходных переносов ь в (N+1)-й,..., (N+K)-й разряды, Сигналы Р,и 8

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

Преобразователь 1, представляет собой комбинационную схему с М+1 (сли х 4 К) либо (если i ) K) входами и L;, выходами, К определяется формулой

К+1

М „„= 2 — К-1

Где М ws1cc — максимальное количество слагаемых, при котором количество выходных переносов еще равно К.

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

m имеется ровно а единиц (символ ()

m означает числа сочетаний из m по а), иначе говоря, значение СФ определяется только количеством а 1 » в наборах ее аргументов. Число а будем называть индексом СФ.

На вход ПК 1, поступают сигналы М слагаемых А; = х„...,х „„)., и входного переноса E; = х„(для i c K) .

М+1,1

Из этих переменных ПК 1; формирует СФ вида Р1(a,, а... ), аргументами которых являются индексы а,, а,..., обозначим В,. = F 1 для M+1 переменных i-ro разряда и 13. = Р, для М переменных.

Объединение индексов в F основано на следующем свойстве СФ: Р(а„, а z,...) =

= у(а )+ (р. )+..., т ° е., на вазможности разложения СФ на простейшие .

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

50

5 154521 щенной -дизъюнктивной нормальной форме так при M=4, ¹4 СФ В(4) равна B(4)= — + XI X X,X,X5 + X, Х,,Х Х, 5

Х1Х,Х Х4Х + Х1Х Х Х4Х5.

Особым случаем функции В либо D является СФ S; = F (1,2,..., R), т.е. частичная сумма i — го разряда. Если

M — четно, то

M+1 для 1,2,...,К-го разряда 10

M-1 для К+1,К+2,. ;,N-I î разряда если М нечетно, то R = M для всех разрядов, Отметим, что функции S явля- 15

l ются функциями нечетности.

Сигналы СФ, сформированные ПК 1.

1 (i = 2, Ы) образуют совокупность С

1 а также сигнал 8.. На выходе элемен\ тов И-ИЛИ 2 с первого по (N-1)-й фор- 2О мируктся сигналы функций переноса

Р,..., PI KoTopbIe IIocT BIoT HB Входы сумматоров 3 по модулю два с 2-го до N-ro разрядов соответственно, на выходах которых формируются сигналы результирующих сумм 5 . . -= -S, O+ P

"1 1

Сигнал S = S, формируется непосредственно в ПК 1, что упрощает схему для первого разряда. На выходах элементов И-ИЛИ 2 с N"ãî по (11+К-1)-й формируются сигналы выходных переНОСОВ 0 > ° ° ° у 0 !

Принцип формирования функций переносов P и С1 покажем на частном, но практически важном примере построения четырехраэрядного(И= 4) сумматора четырех слагаемых (M=4), у которого число К внешних переносов равно 2 (Е, Е, Q Р51 02

В табл.1-5 приведены значения раз- 40 рядных индексов для функций переноса

Р -Р соответственно.

В приведенных ниже табл.1-5 в столбцах помещены индексы СФ Э (для третьего и четвертого разрядов) и В (для первых двух разрядов), сумма которых для P. по некоторой строке

1 с учетом веса разряда дает перенос в

i-й разряд. Например, для переноса в четвертый разряд по первой строке (табл.3) имеем 2 2 + 4- 2О = 8 либо 2 2" + 5. 2 = 9, Аналогично. составлены и остальные строки данной и всех других таблиц, так что множе,ство строк данной таблицы является результатом перебора всех возможных вариантов получения .l переноса в соответствующий разряд.

6 6

В общем случае таблица значений разрядных индексов для P. (2 4i i N+K)

1 составляется следующим образом. Последовательно перебираются значения индексов от О до M+1 (до М для i ) K) в столбце первого разряда при фиксированных значениях индексов в старших разрядах, затем увеличивается на единиц значение индекса во втором разряде при фиксированных значениях индексов старших разрядов и снова производится перебор всех возможных значений индексов в первом разряде, и т,.д. до тех пор, пока во втором разряде не будут перебраны все возможные значения индексов, затем увеличивается на единицу значение индекса в третьем разряде и производится перебор значений индексов в первом и втором разрядах в последовательности, описанной ранее. Описанная процедура выполняется вплоть до заполнения в последнем столбце таблицы для P,(êîличество столбцов равно i-1, если

i 4 N, и равно N в остальных случаях) последнего значения индекса, равного М, !

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

Полученные таким образом таблицы обладают некоторой избыточностью и допускают минимизацию описания схемы сумматора за счет объединения строк, в которых индексы отличаются только в одном столбце при этом для СФ с соседними значениями индексов по данному столбцу возможно склеивание исходных переменных. Для функции В (4,5) при М=4 получаем В (4,5) = х1х х х +

+Х1Х тХ Ь? 5 + Х Х Х 4Х 5 + Х1ХЗХ4Х 5 +

+ x x x x . Совокупность индексов

0-5 для первых двух разрядов и 0-4 для третьего и четвертого разрядов в таблицах соответствует тождественной единице, независимо от значений других переменных.

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

В приведенном на фиг.2 примере элементы И-ИЛИ заменены элементами

154521 g

И-ИЕ в результате эквивалентного преобразов ания логических функ ций .

Строка ф о Р м у л а изобретения 5

Таблица!

Разряд

2,3

Устройство для суммирования M чисел, содержащее в каждом разряде преобразователь двоичного кода в код

1О количества единиц и в каждом разряде. кроме младшего, сумматор по,модулю два, выход которого является выходом суммы данного разряда устройства, входы каждого преобразователя двоичНого кода в код количества единиц соединены с входами соответствующего разряда слагаемых устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, устрой- 20 ство содержит (N+K-1 ) элементов И-ИЛИ, где М вЂ” разрядность слагаемых, И

К+1

2 -К-I, образующих блок формирования параллельных переносов, причем каждый преобразователь двоичного ко- 25 о да в код количества единиц содержит выходы по числу значений кода количества единиц, а также выход нечетности кОда, который в каждом разряде устройства, кроме младшего разряда, соединен с первым входом сумматора по модулю два того же разряда, выходы элементов И-ИЛИ с первого по (N-l)-й сОединены с вторыми входами соотватствующих сумматоров по модулю два, а выходы элементов И-ИЛИ с N-ro noi (Я+К-1)-й соединены с выходами переносов устройства, в каждом 1-м разряде (i=2,..., N+Y.) входы каждой группы И элемента И.-HJIH соединены с выходами преобразователей двоичного кода в код количества единиц разрядов с первого по (i-1)-f для i

1 t (B,) R 2 ф О, где R — поразряд- 45

k s ная операция И; 1 — номер выхода пре6бразователя двоичного кода в код количества единиц, j = О,...., 1 L число входов преобразователя;  — вес 50

j-го выхода К вЂ” го преобразователя„

В -= О,..., Ь, дополнительные входы преобразователей двоичного кода в код количества единиц с первого по К-й соедйнены с входами переноса устройства, выходом суммы младшего разряда устройства является выход нечетности преобразователя двоичного кода в код количества еднниц этого разряда.

Таблица 2

Строка

Разряд

2

4

5

О

2

3

4,5

2-5

0-3

0-3

0,l

4,5

2-5

Таблица 3

Разряд

Строка (1

Таблица 4

Строка

Разряд

2

3 4

О

О

О

О О

1

2

4

2

4,5

4,5

2-5

4,5

2-5

0-5

4,5

1 О 2

2 О 3

3 О 4,5

4 1 . О

5 1 1

6 1 2,3

7 1 4

8 1 5

9 2 О,l

l0 2 2

11 2 3

12 3 О

13 3 1

14 3 4

15 3 5

16 4 2

17 4 3

18 4 4,5

4,5

2-5

0-5

4,5

2-5

0-5

0-3

0,l

0-5

0-3

О,!

0-3

О,!

4,5

2-5

4,5

2-5

0-5

1545216

Разряд

Строка

Разряд

11родолжение табл. 4

Продолжение табл.4

1 1

46

47

48

49

4,5

2-5

0-5

0-5

4,5

2-5

0-5

0-5

Таблица5

С Грока

Разряд

) l

П р и м е ч а н и е.

2-5; 0-3 и т;п. обозначан т пере° числение индекссв

2,3,4,5, 0,1,2,3; ..

8

11 !

13

14 .15

l6

17

18

19

21

22

23

24

26

27

28

29

31

32

33

34

36

37

38

39

41

42

:43

44

О

О

О

1

1

1

1

1

1

2

2

2

2

3

3

2

3

3

4

4

3

0

О !

1

3 .3

Э

4 4

О

1

2

2

3

О

О

О

1

3

4

1

2

2-5

0-5

4,5

2-5

0-5

0-3

0,1

0-5

0-3

О,!

О

О,l

О

3

4,5

3

2-5

0,5

0-5

4,5

2-5

0-5

4,5

2-5

0-5

0-5

0-5

0-3

0,l

0-5

0-3

0,1

0-5

0-5

0-3

0,1

0-5

0-3

0,1

0-3

0,1

0-5

0-3

0,1

0-3

0,1

4,5

2-5

4,5

2-5

0-5

4,5

2-5

4,5

2-5

2

4

6

8

l0

1)

12

l3

14

16

17

18

19

21

22!

1

2

2

2

2

2

3

3

3

Э

3

4

i

2

2

3

4

О

О

О

1

2-4

0-4

4 4,5

5 2-5

2 4,5

3 2-5

4,5 0-5

4 4,5

5 2-5

2 4,5

3 2-5

4,5 0-5

0 4,5

1 2-5

2-5 4-5

0-5 0-5

2 4,5

3 2-5

4,5 0-5

О 4,5

1 2-5

2,5 0-5

0-5 0-5

0-5 0-5

1545216

С4-4

С4- У

СУ-5

С2-,У

C/-с

cf-6.

С4-4

СУ-Р

Г4-5

С2-4

С4С4-6

СУ-6

Л-2

ГВ-,У а-6

С/- 4

С4-2

СУ -Z

С2-7 с4-2

cS-4 с2-4

Г/-4

С4-2

CJ-4 сМ

С/-К с4-г

СУ-4

CZ-Ю

С4 -2

СИ

С2-2

cr-4

r4 -г

ГИ

С2-Я

cr-4.

Г4;2

СИ

С2-/2

С4-г 9 и-к

С4-У

ГВ-2 сг-4

cr-4

СЫ г2-5

C/-К

Г4-У

СУ-2

Г2-/

c4-Z

СИ

Г2-2

C/-4

С4 -3

CJ-Ð

Гг-Я си

Г4-Я сз-z

ГР-/2

C4-S

ГИ

Г2-/r с4-3

СУ-5

С2-4

С/-5

С4-У

СЯГ2- 7 с/-2 и-з

СУ-6

С2-В

С4-J

cZ-6

С2-4

cr-5

С4-.У

СУ-6

С2-5

c/- Р

С4-4

СЫ

С2- /

С4-4

СЯ

42-6 с/ 5

С4-4

СУ;У

С2-7

С4-4

Г5-4

С2-В с4-4

С.У-4

С2-4

Cf-5 (4-4

С5-4 с2-S

cr-z

С4-4

СВ-5

С2-2

С/-5

1545216

С45

С5-2

Сг-В

С4-5

СУ-2 с2-4 с/-5

c4-S

СУ-2 с2C/-2

С4-5

СУ-,У

Г2-2

cr-5

С4-5 си с2-.У

Cf-2

С4-5

СУ-S

С2-b

cr-4

С5С2- 7

Cf-6

С4С5-Е

С2-4

С/-4

С4СУ-Е

Ю

Cf-6

С4-5

СМ

С2/

4-6

СИ

С2cf-4

Л-8

СИ

С2-7

СМ с4С5-4 сг-4

Cf-4 с4-6

С2-5

cf-6

С4-6

cS-4

С2-/

С4-б

СУ-5 4

С8-Р

С/-У

С4аS сгС/-6

С4с2

1545216

Составитель А. Степанов

Редактор Н. Лазаренко Техред М.Ходаиич

Корректор В, Гирняк

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

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

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

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