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)