Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–1
Prawa ł czno ci i przemienno ci dodawania
a + b + c + d + e + f + g + h + i + … = { [ ( a + b ) + ( c + d ) ] + [ ( e + f ) + ( g + h ) ] } + { [ ( i + …
a + b + c + d + e + f + g + h + i + … = [ ( a + b + c ) + ( d + e + f ) + ( g + h + i ) ] + [ ( …
prawo ł czno ci dodawania w systemie pozycyjnym
∑
∑
∑
∑
−
−
=
−
−
=
−
−
=
−
−
=
+
+
+
=
+
+
+
=
+
+
+
1
1
1
1
...)
(
...
...
k
m
i
i
i
i
i
k
m
i
i
i
k
m
i
i
i
k
m
i
i
i
c
b
a
c
b
a
C
B
A
β
β
β
β
dodawanie wieloargumentowe jednopozycyjne – suma w systemie pozycyjnym
i
m
i
m
i
i
i
i
i
i
i
u
u
u
u
c
b
a
β
β
β
β
β
)
...
(
...)
(
)
(
)
2
(
2
)
1
(
1
)
0
(
+
+
+
+
+
=
+
+
+
•
suma jest wielocyfrowa (co najmniej dwucyfrowa)
ł czno i przemienno dodawania w systemie pozycyjnym
∑ ∑
∑ ∑
∑ ∑
−
−
=
=
−
−
−
=
=
=
−
−
=
=
=
=
+
+
+
1
0
)
(
1
1
)
(
1
1
)
(
)
(
)
2
(
)
1
(
)
(
...
n
q
i
m
r
r
r
r
i
i
n
q
i
k
p
p
i
i
k
p
n
q
i
i
p
i
k
u
x
x
X
X
X
β
β
β
β
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–2
Dodawanie wieloargumentowe jednopozycyjne w systemach naturalnych
i
m
i
m
i
i
i
i
i
i
i
u
u
u
u
x
x
x
β
β
β
β
β
)
...
(
...)
(
)
(
)
2
(
2
)
1
(
1
)
0
(
)
3
(
)
2
(
)
1
(
+
+
+
+
=
+
+
+
przy tym
}
1
,...,
1
,
0
{
,
)
(
)
(
−
∈
β
j
i
j
i
u
x
suma k składników mo e by m-cyfrowa
1
)
1
(
)
1
(
1
0
1
1
)
(
)
(
−
≤
−
=
−
≤
⇒
−
≤
≤
∑
∑
=
=
m
k
j
k
j
j
i
j
i
k
x
x
β
β
β
β
]
1
)
1
(
[
log
+
−
=
β
β
k
m
β
β
β
β
β
β
11
...
11
1
...
)
1
/(
)
1
(
2
1
=
+
+
+
=
−
−
≤
−
−
m
m
m
k
→
je li liczba składników jest
≤
β
+1
, suma jest dwucyfrowa i wynosi
β
β
β
β
β
<
−
+
+
+
≤
−
+
+
+
=
+
+
+
r
x
x
x
r
x
x
x
r
u
v
i
i
i
i
i
i
i
i
)
1
(
)
2
(
)
1
(
)
1
(
)
2
(
)
1
(
1
...
0
gdy
}
...
,
{
}
,
{
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–3
Dodawanie wieloargumentowe w systemach naturalnych (1)
dodawanie mo na wykona dwuetapowo:
•
obliczy wielopozycyjne sumy przej ciowe na ka dej pozycji
(w dowolnej kolejno ci – s niezale ne)
•
doda liczby wielocyfrowe skomponowane z sum przej ciowych
→
je li liczba argumentów k
≤
β
+1
(11
β
) sumy przej ciowe s dwucyfrowe
(0)
x
k–1
x
k–2
…
x
–m+3
x
–m+2
x
–m+1
x
–m
(0)
y
k–1
y
k–2
…
y
–m+3
y
–m+2
y
–m+1
y
–m
…
…
…
…
…
…
…
…
+
(0)
z
k–1
z
k–2
…
z
–m+3
z
–m+2
z
–m+1
z
–m
(0)
u
k–1
u
k–2
u
–m+3
u
–m+2
u
–m+1
u
–m
v
k
v
k–1
v
k–2
v
–m+3
v
–m+2
v
–m+1
s
k
s
k–1
s
k–2
s
–m+3
s
–m+2
s
–m+1
s
–m
→
je li liczba argumentów k >
β
+1
(11
β
)
dodawanie mo na wykona rekurencyjnie
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–4
Dodawanie wieloargumentowe w systemach naturalnych (2)
→
je li liczba argumentów k >
β
+1,
to dodawanie mo na wykona etapami
(0)
(0)
a
k–1
a
k–2
…
a
–m+3
a
–m+2
a
–m+1
a
–m
(0)
(0)
b
k–1
b
k–2
…
b
–m+3
b
–m+2
b
–m+1
b
–m
(0)
(0)
c
k–1
c
k–2
…
c
–m+3
c
–m+2
c
–m+1
c
–m
(0)
(0)
d
k–1
d
k–2
…
d
–m+3
d
–m+2
d
–m+1
d
–m
…
…
…
…
…
…
…
…
…
>
β
+1
a
rg
u
m
e
n
tó
w
+
(0)
(0)
p
k–1
p
k–2
…
p
–m+3
p
–m+2
p
–m+1
p
–m
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
(0)
(0)
(0)
x
k–1
(0)
x
k–2
…
(0)
x
–m+3
(0)
x
–m+2
(0)
x
–m+1
(0)
x
–m
(0)
(1)
x
k–1
(1)
x
k–2
…
(1)
x
–m+3
(1)
x
–m+2
(1)
x
–m+1
(1)
x
–m
(0)
(2)
x
k–1
(2)
x
k–2
…
(2)
x
–m+3
(2)
x
–m+2
(2)
x
–m+1
(2)
x
–m
(0)
(0)
≤
β
+1
a
rg
.
+
…
…
…
…
…
…
…
…
…
…
(0)
u
k+1
(0)
u
k
(0)
u
k–1
(0)
u
k–2
…
(0)
u
–m+3
(0)
u
–m+2
(0)
u
–m+1
(0)
x
–m
2
a
rg
…
(1)
u
k
(1)
u
k–1
(1)
u
k–2
…
(1)
u
–m+3
(1)
u
–m+2
(1)
u
–m+1
…
s
k
s
k
s
k–1
s
k–2
s
–m+3
s
–m+2
(0)
u
–m+1
(0)
x
–m
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–5
Sumatory przechowuj ce przeniesienie (CSA)
sumator (k,m) – układ obliczaj cy m-pozycyjn sum k liczb jednocyfrowych
]
1
)
1
(
[
log
+
−
=
β
β
k
m
)
0
(
)
1
(
)
1
(
..
i
i
m
i
u
u
u
−
(k,m)
(k,m)
(k,m)
(k,m)
)
0
(
1
)
1
(
1
)
1
(
1
..
−
−
−
−
i
i
m
i
u
u
u
)
1
(
1
−
+
−
m
m
i
u
)
1
(
−
−
m
m
i
u
)
1
(
2
−
+
−
m
m
i
u
)
2
(
2
)
1
(
2
−
−
i
i
x
x
)
1
(
2
−
−
m
i
u
..
...
)
2
(
)
1
(
)
(
)
2
(
)
1
(
m
k
i
k
i
k
i
i
i
x
x
x
x
x
−
+
..
...
)
2
(
1
)
1
(
1
)
(
1
)
2
(
1
)
1
(
1
m
k
i
k
i
k
i
i
i
x
x
x
x
x
−
−
+
−
−
−
−
Struktura sumatora CSA zbudowanego z sumatorów (k,m)
∑ ∑
∑ ∑
∑ ∑
−
−
=
=
−
−
−
=
=
=
−
−
=
=
=
=
+
+
+
1
0
)
(
1
1
)
(
1
1
)
(
)
(
)
2
(
)
1
(
)
(
...
n
q
i
m
r
r
r
r
i
i
n
q
i
k
p
p
i
i
k
p
n
q
i
i
p
i
k
u
x
x
X
X
X
β
β
β
β
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–6
Struktura dwójkowych sumatorów CSA
)
6
(
)
5
(
)
4
(
)
3
(
)
2
(
)
1
(
i
i
i
i
i
i
x
x
x
x
x
x
)
6
(
1
)
5
(
1
)
4
(
1
)
3
(
1
)
2
(
1
)
1
(
1
−
−
−
−
−
−
i
i
i
i
i
i
x
x
x
x
x
x
)
6
(
1
)
5
(
1
)
4
(
1
)
3
(
1
)
2
(
1
)
1
(
1
+
+
+
+
+
+
i
i
i
i
i
i
x
x
x
x
x
x
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
Skala redukcji operandów w wielopoziomowym drzewie CSA
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–7
Sumatory (k, m) w systemach dwójkowych
β
=2
⇒
1
2
−
≤
m
k
,
)
1
(
log
2
+
=
k
m
•
elementarny sumator (3,2) – sumator 1-bitowy
•
licznik (k,m) – binarny sumator (k,m)
o
– koduje liczb jedynek z k wej na m wyj ciach
o
– drzewo (3,2) lub projekt indywidualny, np. licznik (4,3)
)
(
)
(
)
0
(
v
z
y
x
u
⊕
⊕
⊕
=
)
)(
(
)
)(
(
)
)(
(
)
1
(
y
x
v
z
v
x
z
y
v
z
y
x
u
+
⊕
+
+
⊕
+
+
⊕
=
xyzv
u
=
)
2
(
•
reduktor (k,2) – koduje liczb jedynek z k wej na 2 wyj ciach sumy
i pewnej liczbie wyj przeniesie (kumulacja przeniesie )
k > 3 operandów wej ciowych ⇒ redukcja w układzie wielopoziomowym
•
kolumny reduktorów (k,2) o wagach 2
i
– kumulacja przeniesie
•
drzewo – gał zie liczników (3,2) o wagach 2
i
i redukcja przeniesie
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–8
Liczniki jedynek (k, m) i reduktory (k, 2)
c
i+1,i
c
i+2,i
c
i,i–2
s
i+1
s
i
)
7
(
)
6
(
)
5
(
)
4
(
)
3
(
)
2
(
)
1
(
i
i
i
i
i
i
i
x
x
x
x
x
x
x
(3,2)
(3,2)
(3,2)
(3,2)
(4,3)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
)
7
(
)
6
(
)
5
(
)
4
(
)
3
(
)
2
(
)
1
(
i
i
i
i
i
i
i
x
x
x
x
x
x
x
Licznik (7,3)
Reduktor (7,2)
(3,2)
s
i+2
s
i+1
s
i
c
i,i–1
c
i+1,i
c
i+2,i
s
i+1
s
i
c
i,i–2
c
i,i–1
)
4
(
)
3
(
)
2
(
)
1
(
i
i
i
i
x
x
x
x
Reduktor (4,2)
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–9
Sumowanie k operandów n-pozycyjnych (CSA)
Pojedynczy układ (3,2) redukuje dokładnie jeden operand 1-bitowy
→
do redukcji k operandów n-bitowych potrzeba n(k–2) układów (3,2)
→
k
L
operandów na poziomie L ⇒
2
/
1
L
L
L
k
k
k
+
≤
+
na poziomie L+1
•
jeden poziom CSA redukuje 3 operandy do 2 – skala redukcji 3/2
•
dwa poziomy CSA redukuj 4 operandy do 2 – skala redukcji
2
•
trzy poziomy CSA redukuj 6 operandów do 2 – skala redukcji
3
3
L
L
L
k
)
(
2
)
2
(
2
2
3
≤
≤
(lepsza ocena)
L
L
L
k
)
(
2
)
3
(
2
2
3
3
≤
≤
(L
≥
3)
Redukcja liczby operandów w wielopoziomowej strukturze CSA
liczba poziomów L
1
2
3
4
5
6
7
8
9
10
2
L
)
2
/
3
(
3
4
6 10 15 22 34 51 76 115
maksymalna liczba operandów
3
4
6
9 13 19 28 42 63 94
L
L
44224957
,
1
2
)
3
(
2
3
⋅
≅
⋅
3
5
6
9
13 18 26 38 54 78
L
L
41421356
,
1
2
)
2
(
2
⋅
≅
⋅
3
4
6
8
12 16 23 32 46 65
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–10
Konstrukcja wielopoziomowego sumatora CSA (1)
Wytworzenie poprawnej sumy k argumentów n-bitowych (wyrównaj krótsze!)
wymaga k-krotnego rozszerzenia zakresu (log k dodatkowych bitów):
1
2
)
1
2
(
...
0
1
2
,...,
,
0
log
2
1
2
1
−
<
−
≤
+
+
+
≤
⇒
−
≤
≤
+
k
n
n
k
n
k
k
X
X
X
X
X
X
•
oszacowanie szeroko ci –
k
n
w
log
+
=
•
liczba elementów sumatora CSA – n ( k–2)
•
oszacowanie gł boko ci –
3
log
)
1
(log
3
1
3
log
1
log
−
≤
≤
−
−
k
L
k
•
czas dodawania –
n
L
T
log
2
4
+
≥
Konstrukcja sumatora jest rekurencyjna:
1. przył cz po 3 sygnały wej ciowe o tej samej wadze do wej modułu (3,2)
2. sygnały nieprzył czone przeka na ni szy poziom CSA
3. wytwórz wyj cia wszystkich modułów (3,2) (lub (2,2)) – maj ró ne wagi!
4. zbierz sygnały o tych samych wagach
5. powtarzaj 1–4 dopóki liczba sygnałów o jakiej wadze przekracza 2.
6. doł cz szybki sumator ko cowy (CLA, PPA, COSA,...)
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–11
Konstrukcja wielopoziomowego sumatora CSA (2)
przykład – 7 argumentów 4-bitowych (w=3+3, L=4)
p
o
z
i
o
m
4
–
w
e
j
ś
c
i
a
w
y
j
ś
c
i
a
p
o
z
i
o
m
4
–
s
u
m
a
t
o
r
y
2
0
2
1
2
2
2
3
2
4
p
o
z
i
o
m
4
–
w
e
j
ś
c
i
a
p
o
z
i
o
m
3
–
w
e
j
ś
c
i
a
w
y
j
ś
c
i
a
p
o
z
i
o
m
4
–
s
u
m
a
t
o
r
y
p
o
z
i
o
m
4
–
w
e
j
ś
c
i
a
p
o
z
i
o
m
3
–
w
e
j
ś
c
i
a
w
y
j
ś
c
i
a
p
o
z
i
o
m
4
–
s
u
m
a
t
o
r
y
w
y
j
ś
c
i
a
p
o
z
i
o
m
3
–
s
u
m
a
t
o
r
y
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–12
Konstrukcja wielopoziomowego sumatora CSA (3)
p
o
z
i
o
m
4
–
w
e
j
ś
c
i
a
p
o
z
i
o
m
3
–
w
e
j
ś
c
i
a
w
y
j
ś
c
i
a
p
o
z
i
o
m
4
–
s
u
m
a
t
o
r
y
w
y
j
ś
c
i
a
p
o
z
i
o
m
3
–
s
u
m
a
t
o
r
y
p
o
z
i
o
m
2
–
w
e
j
ś
c
i
a
p
o
z
i
o
m
2
–
s
u
m
a
t
o
r
y
p
o
z
i
o
m
4
–
w
e
j
ś
c
i
a
p
o
z
i
o
m
3
–
w
e
j
ś
c
i
a
w
y
j
ś
c
i
a
p
o
z
i
o
m
4
–
s
u
m
a
t
o
r
y
w
y
j
ś
c
i
a
p
o
z
i
o
m
3
–
s
u
m
a
t
o
r
y
p
o
z
i
o
m
2
–
w
e
j
ś
c
i
a
p
o
z
i
o
m
2
–
s
u
m
a
t
o
r
y
w
y
j
ś
c
i
a
p
o
z
i
o
m
1
–
w
e
j
ś
c
i
a
p
o
z
i
o
m
1
–
s
u
m
a
t
o
r
y
w
y
j
ś
c
i
a
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–13
Konstrukcja wielopoziomowego sumatora CSA
od góry (top-down)
od dołu (bottom-up) – drzewo Wallace’a
liczba operandów
struktura
liczba operandów
struktura
N = N
0
(N
0
/3)
∗
(3,2)
L
k
L
−1
< N < k
L
(N
−
k
L
−1
)
∗
(3,2)+
(N
0
/3)
∗
2+|N
0
|
3
=N
1
(N
1
/3)
∗
(3,2)
L
−1
k
L
−2
+ k
L
−2
/2 = k
L
−1
k
L
−1
/3
∗
(3,2)+|k
L
−1
|
3
… …
… …
…
… …
… …
(6/3)
∗
2+0=4
1+1
∗
(3,2)
2
3 + 3/2 = 4 = k
2
3/2
∗
(3,2)+1
(4/3)
∗
2+1=3
1
∗
(3,2)
1
2 + 3/2 = 3 = k
1
2/2
∗
(3,2)
redukcja od poziomu L,
łatwiejsza konstrukcja drzewa
kumulacja operandów od poziomu 1
2
/
1
L
L
L
k
k
k
+
=
+
, k
0
= 2
L
operandy struktura
operandy struktura
operandy
struktura
7
21
7
∗
(3,2)
27
9
∗
(3,2)
20…27 1…8
∗
(3,2)+…
6
7
∗
2=14 2+4
∗
(3,2)
9
∗
2=18
6
∗
(3,2)
8
∗
2+3=19
6
∗
(3,2)+1
5
4
∗
2+2=10 1+3
∗
(3,2)
6
∗
2=12
4
∗
(3,2)
6
∗
2+1=13
4
∗
(3,2)+1
4
3
∗
2+1=7 1+2
∗
(3,2)
4
∗
2=8 2+2
∗
(3,2)
4
∗
2+1=9
3
∗
(3,2)
3
2
∗
2+1=5 2+1
∗
(3,2)
2
∗
2+2=6
2
∗
(3,2)
2
∗
3=6
2
∗
(3,2)
2
1
∗
2+2=4 1+1
∗
(3,2)
2
∗
2=4 1+1
∗
(3,2)
2
∗
2=4
1
∗
(3,2)+1
1
1
∗
2+1=3
1
∗
(3,2)
1
∗
2+1=3
1
∗
(3,2)
1
∗
2+1=3
1
∗
(3,2)
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–14
Dwójkowe sumatory wieloargumentowe (CSA)
(3,2)
v
0
x
0
y
0
z
0
(2,2)
(3,2)
v
1
x
1
y
1
z
1
(3,2)
(3,2)
v
2
x
2
y
2
z
2
(3,2)
(3,2)
v
3
x
3
y
3
z
3
(3,2)
FA
FA
FA
FA
s
0
s
1
s
2
s
3
s
4
s
5
Czteropozycyjny sumator czterooperandowy CSA
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–15
Dwójkowe sumatory wieloargumentowe (CSA)
(3,2)
v
0
x
0
y
0
z
0
(2,2)
(3,2)
v
1
x
1
y
1
z
1
(3,2)
(3,2)
v
2
x
2
y
2
z
2
(3,2)
(3,2)
v
3
x
3
y
3
z
3
(3,2)
s
0
s
1
s
2
s
3
s
4
s
5
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
sumator
ko
ń
cowy
Czteropozycyjny sumator czterooperandowy CSA
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–16
Dwójkowe sumatory wieloargumentowe U2 (CSA)
Wytworzenie poprawnej sumy k argumentów n-bitowych (wyrównaj krótsze!)
wymaga k-krotnego rozszerzenia zakresu (log k dodatkowych bitów):
1
log
2
1
1
log
1
2
1
1
2
...
2
1
2
,...,
,
2
−
+
−
+
−
−
<
+
+
+
≤
−
⇒
−
≤
≤
−
k
n
k
k
n
n
k
n
X
X
X
X
X
X
Rozszerzenie zakresu o m = log
2
k pozycji
•
doł czenie m bitów rozszerzenia lewostronnego
o
wada: wiele argumentów stałych (bity rozszerzenia)
o
drzewo CSA (k+m)-bitowe
•
zamiana argumentów na dodatnie z korekcj , zgodnie z zale no ci
∑
∑
−
=
−
−
−
−
=
−
−
+
−
+
−
=
+
−
2
0
1
1
1
2
0
1
1
2
2
)
1
(
2
2
2
k
i
i
i
k
k
k
k
i
i
i
k
k
x
x
x
x
→
zakodowanie stałej
−
n 2
k
−1
(na m+k bitach {r
k+m
−1
, … , r
k
−1
, 0, 0,…, 0})
√
znaczna redukcja liczby stałych bitów
√
prostsze drzewo CSA
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–17
Zliczanie jedynek w słowie n-bitowym
(prawie) trzykrotna redukcja na I poziomie sumatora
•
je li n=3k, to na II poziomie jest k operandów 2-bitowych
•
je li n
≠
3k, to na II poziomie jest n/3 operandów 2-bitowych
Parametry układu (bez 2-bitowego sumatora wyj ciowego)
•
liczba modułów CSA – n–2
•
liczba poziomów CSA – 1+ liczba poziomów redukcji n/3 operandów,
czyli
1
3
log
)
1
3
/
(log
3
1
1
3
log
1
3
/
log
+
−
≤
≤
+
−
−
n
L
n
•
liczba bitów wyniku – log
2
n
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–18
Liczniki wielokolumnowe
)
,
,
,...,
(
0
1
1
m
k
k
k
s
−
Dodawanie operandów o rosn cych wagach (k
i
o wadze
β
i
, i = 0,1,…,s)
suma na m pozycjach – wektor o l składowych:
– jednooperandowa s-pozycyjna suma o wadze
0
2 ,
– wielooperandowe przeniesienie wektorowe o wagach operandów (2
s
)
i
Warunek zakodowania wyniku na m pozycjach
∑
−
=
−
≥
−
1
0
)
1
(
1
s
i
i
i
m
k
β
β
β
w systemie dwójkowym
∑
−
=
≥
−
1
0
2
1
2
s
i
i
i
m
k
warunek realizowalno ci licznika (k, k, ..., k, m)
)
1
2
(
1
2
−
≥
−
s
m
k
m
≤
2s ⇒ suma k operandów s-pozycyjnych jest najwy ej 2-operandowa
)
1
2
(
1
2
1
2
2
−
≥
−
≥
−
s
m
s
k
⇒
1
2
+
≤
s
k
Sumatory CSA
© Janusz Biernat, 09-06-Sumatory CSA.doc, 2 pa
ź
dziernika 2006
CSA–19
Parametry optymalnych liczników s-kolumnowych
s
1
2
3
4
5
6
7
m=2s
2
4
6
8
10 12 14
k
3
5
9
17 33 65 129
2
2
2
2
2
a)
b)
s
i
2
i
2 +1
s
i
2 +3
c
i
2 +4
c
i
2 +2
c
i
2
i
2 +1
i
2 +2
i
2 +3
i
2 +4
2
2
2
2
2
s
s
c
c
s
i
3
i
3 +1
i
3 +2
i
3 +4
i
3 +3
i
3
i
3 +1
i
3 +2
i
3 +4
i
3 +3
2
i
2
t
i
2
u
i
2
v
i
2
w
i
2
x
i
2
y
i
2
z
i
2
2
i
2 +1
i
2 +1
t
i
2 +1
u
i
2 +1
v
i
2 +1
w
i
2 +1
x
i
2 +1
y
i
2 +1
z
2
i
2
i
3 +1
3
t
i
3
i
3 +1
t
u
u
v
v
w
w
x
x
y
y
z
z
2
i
3 +2
t
u
v
w
x
y
z
i
3 +2
i
3
i
3 +1
i
3 +2
i
3
i
3 +1
i
3 +2
i
3
i
3 +1
i
3 +2
i
3
i
3 +1
i
3 +2
i
3
i
3 +1
i
3 +2
i
3
i
3 +1
i
3 +2
Schemat dodawania w układach: a) (7,7,5), b) (7,7,7,5)