Sumatory CSA

© Janusz Biernat, Sumatory CSA, 9 stycznia 2004

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

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, Sumatory CSA, 9 stycznia 2004

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, Sumatory CSA, 9 stycznia 2004

CSA–3

Dodawanie wieloargumentowe wielopozycyjne w systemach naturalnych

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, Sumatory CSA, 9 stycznia 2004

CSA–4

Dodawanie wieloargumentowe wielopozycyjne w systemach naturalnych

→

je

śli liczba argumentów k>

β

+1

(11

β

)

dodawanie mo

żna wykonać rekurencyjnie

(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

…

…

…

…

…

…

…

…

…

±

(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)

±

…

…

…

…

…

…

…

…

…

…

(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

…

(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, Sumatory CSA, 9 stycznia 2004

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

−

−

+

−

−

−

−

∑ ∑

∑ ∑

∑ ∑

−

−

=

=

−

−

=

=

=

−

−

=

=

=

=

+

+

+

1

0

)

(

1

1

)

(

1

1

)

(

)

(

)

2

(

)

1

(

)

(

...

n

q

i

m

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

β

β

β

β

Struktura sumatora CSA zbudowanego z sumatorów (k,m)

Sumatory CSA

© Janusz Biernat, Sumatory CSA, 9 stycznia 2004

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, Sumatory CSA, 9 stycznia 2004

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, Sumatory CSA, 9 stycznia 2004

CSA–8

Liczniki (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, Sumatory CSA, 9 stycznia 2004

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)

→

na poziomie L k

L

operandów ⇒ na poziomie (L+1)





2

/

1

L

L

L

k

k

k

+

≤

+

•

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, Sumatory CSA, 9 stycznia 2004

CSA–10

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, Sumatory CSA, 9 stycznia 2004

CSA–11

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, Sumatory CSA, 9 stycznia 2004

CSA–12

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)

(2,2)

(2,2)

(2,2)

Czteropozycyjny sumator czterooperandowy CSA

Sumatory CSA

© Janusz Biernat, Sumatory CSA, 9 stycznia 2004

CSA–13

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, Sumatory CSA, 9 stycznia 2004

CSA–14

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)

Sumatory CSA

© Janusz Biernat, Sumatory CSA, 9 stycznia 2004

CSA–15

Dwójkowe sumatory wieloargumentowe U2 (CSA)

Rozszerzenie zakresu stosownie do liczby argumentów – o m = log

2

n 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})

o

redukcja stałych bitów

o

prostsze drzewo CSA