Устройство для суммирования м-чисел
Иллюстрации
Показать всеРеферат
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных вычислительных устройствах. Целью изобретения является повышение быстродействия. Цель достигается за счет введения в устройство, содержащее в каждом разряде преобразователь 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