Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–1 

Szybko  dodawania (odejmowania) 

 

 

c

k

−2

 

x

1–m

 

s

1–m

 

c

2–m

 

y

1–m

 

s

k

−1

 

c

k

−1

 

c

k

 

y

k

−1

 

x

k

−1

 

FA/FS

 

x

–m

 

s

–m

 

c

–m

 

c

1–m

 

y

–m

 

s

k

−2

 

y

k

−2

 

x

k

−2

 

FA/FS

 

FA/FS

 

FA/FS

 

Schemat dodawania / odejmowania wielopozycyjnego  

 

Propagacja przeniesienia  

• 

wykonanie działania na pozycji i  wymaga przeniesienia z pozycji i

−

1 

• 

czas wytworzenia sumy (ró nicy) – stały od chwili ustalenia przeniesienia 

• 

gwarantowany czas wykonania dodawania lub odejmowania zale y od 

najdłu szego czasu przesłania zmiany przeniesienia z pozycji najni szej 

 
Czas dodawania n-pozycyjnego (czas dodawania jednopozycyjnego T = 2) 

2 log

2

n

≤

T

Σ

≤

2 n  

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–2 

Przyspieszanie dodawania dwuargumentowego 

 

Skracanie czasu propagacji przeniesie   

• 

antycypacja przeniesie  (carry look-ahead adder, CLA) 

• 

wytwarzanie przeniesie  równoległych (parallel prefix adder, PPA) 

• 

skracanie  cie ki propagacji przeniesienia (carry skip adder, CSKA) 

 

Składanie sum blokowych 

• 

składanie sum warunkowych (conditional sum adder, COSA) 

o 

tworzenie wariantowych sum dla bloków 2

i

 kolejnych pozycji 

• 

sumator z przeł czaniem sum cz ciowych (carry-select adder, CSLA) 

o 

równoległe wytwarzanie alternatywnych sum cz ciowych 

• 

składanie sum korygowanych (carry-increment adder, CIA) 

o 

korekcja sum blokowych przeniesieniami 

 

Składanie sum redundantnych 

• 

nadmiarowa reprezentacja argumentów (SD) 

→

 dodawanie dwuetapowe 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–3 

Sumator z antycypacj  przeniesie  (carry look-ahead adder, CLA) 

Funkcja przeniesienia  

i

i

i

i

i

i

i

i

i

i

i

c

y

x

y

x

c

y

x

y

x

c

)

(

)

(

1

+

+

=

⊕

+

=

+

 

• 

w obliczaniu przeniesienia funkcje OR (x

i

+ y

i

) i XOR (x

i

⊕

y

i

) s  zamienne 

 

• 

funkcja wytwarzania (generowania) przeniesienia  

1

=

=

i

i

y

x

 ⇒ przeniesienie wyj ciowe 

1

1

=

+

i

c

 

i

i

i

y

x

g

=

, 

• 

funkcja półsumy  

i

i

i

y

x

h

⊕

=

 

precyzyjnie okre la warunek przekazywania (propagacji) przeniesienia: 

i

i

y

x

≠

⇒ 

i

i

c

c

=

+

1

, ale funkcja OR jest prostsza, wi c przyjmuje si  

 

• 

funkcja przekazywania (propagacji) przeniesienia (

i

p – f. wygaszania) 

i

i

i

y

x

p

+

=

 

 

• 

w wyra eniach na przeniesienie funkcje p

#

 mo na zast pi  funkcjami h

#

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–4 

Funkcje przeniesie  w sumatorach CLA 

 

Funkcje c

#

 mo na rozwija  wzgl dem kilku kolejnych pozycji 

 

i

i

i

i

c

p

g

c

+

=

+

1

 

i

i

i

i

i

i

i

c

p

p

g

p

g

c

1

1

1

2

+

+

+

+

+

+

=

 

i

i

i

i

i

i

i

i

i

i

i

c

p

p

p

g

p

p

g

p

g

c

1

2

1

2

1

2

2

3

+

+

+

+

+

+

+

+

+

+

+

=

 

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

c

p

p

p

p

g

p

p

p

g

p

p

g

p

g

c

1

2

3

1

2

3

1

2

3

2

3

3

4

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

=

 

 

• 

zło ono  funkcji c

#

 ro nie z kwadratem zasi gu s 

• 

bariera technologiczna – ograniczona liczba wej  bramki 

 

)

(

...

...

...

)

(

1

1

2

1

1

1

1

1

1

i

i

i

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

s

i

c

p

g

p

p

p

g

p

p

g

p

g

c

p

g

p

g

c

p

g

c

+

+

+

+

+

=

=

+

+

=

+

=

+

−

+

+

−

+

−

+

+

−

+

+

+

−

+

−

+

−

+

+

+

+

+

+

+

+

 

 

)

,

,...,

,

(

)

,

,...,

,

(

)

,

,...,

,

(

)

,

,...,

,

(

1

i

i

s

i

s

i

i

i

i

s

i

s

i

i

i

s

i

s

i

i

i

i

s

i

s

i

s

i

h

g

h

g

P

c

h

g

h

g

G

p

g

p

g

P

c

p

g

p

g

G

c

+

+

+

+

+

+

+

+

+

+

+

=

=

+

=

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–5 

Moduł sumatora z antycypacj  przeniesie  (CLA) 

 

 

c

i+4 

c

i+3 

c

i+2 

c

i+1 

y

i

 

x

i

 

y

i+3

 

x

i+3

 

y

i+2

 

x

i+2

 

y

i+1

 

x

i+1

 

c

i

 

s

i+3 

s

i+2 

s

i+1 

s

i 

CLA

 

c

i+4 

g

i

 

p

i

 

g

i+3

 

p

i+3

 

g

i+2

 

p

i+2

 

g

i+1

 

p

i+1

 

 

Czterobitowy sumator CLA 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–6 

Ła cuch sumatorów z antycypacj  przeniesie  (CLA) 

 

s

15:12

 

c

12

 

c

16

 

y

15:12

 

x

15:12

 

s

11:8

 

c

8

 

y

11:8

 

x

11:8

s

7:4

 

c

4

 

y

7:4

 

x

7:4

 

s

3:0

 

0 

y

3:0

 

x

3:0

 

CLA 

CLA 

CLA 

CLA 

 

Sumator zbudowany z kaskady bloków CLA 

 

 

G,P 

G,P 

G,P 

G,P 

s

15:12

 

c

12

 

c

16

 

y

15:12

 

x

15:12

 

s

11:8

 

c

8

 

y

11:8

 

x

11:8

s

7:4

 

c

4

 

y

7:4

 

x

7:4

 

s

3:0

 

0 

y

3:0

 

x

3:0

 

CLA 

CLA 

CLA 

CLA 

CLG 

 

Sumator CLA z blokiem wytwarzania przeniesie  CLG 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–7 

Propagacja i generowanie przeniesie  – intuicje (1) 

AB

c

o

u

t

c

i

n

 

 

c

out

=1 je li: 

• 

c

in

=1 jest przesyłane przez blok AB do wyj cia c

out

 

• 

wewn trz bloku AB jest wytwarzane c

out

=1, za  c

in

 jest dowolne 

 
 

A

B

c

o

u

t

c

i

n

c

m

 

 

c

out

=1 je li: 

• 

c

in

=1 jest przesyłane przez blok B do c

m

 a nast pnie przez blok A do c

out

 

• 

wewn trz bloku A jest wytwarzane c

out

=1, za  c

m

 jest dowolne 

• 

wewn trz bloku B jest wytwarzane c

m

=1,  

a nast pnie przez blok A jest przekazywane do c

out

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–8 

Propagacja i generowanie przeniesie  – intuicje (2) 

 

G

BA

 

G

A

 

 

1

P

A

 

G

B

 

1

1

G

DC

 

G

C

 

 

P

C

 

G

D

 

1

 

 

 

 

P

BA

 

P

A

 

P

B

 

1

1

P

BA

 

P

A

 

P

B

 

1

1

P

DC

 

P

C

 

P

D

 

1

1

1

1

 

B

in

BA

BA

B

in

B

A

B

A

A

out

c

P

G

c

P

P

G

P

G

c

/

/

+

=

+

+

=

 

D

in

DCBA

DCBA

D

in

DC

BA

DC

BA

BA

out

c

P

G

c

P

P

G

P

G

c

/

/

+

=

+

+

=

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–9 

Funkcje grupowej antycypacji przeniesie  

Wyznaczanie funkcji 

przekazywania (propagacji) przeniesienia P 

przez bloki sumatora (iloczyn) jest działaniem ł cznym (asocjacyjnym) 

)

(

)

(

C

B

A

C

B

A

CBA

P

P

P

P

P

P

P

=

=

 

Wyznaczanie funkcji wytwarzania (generowania) przeniesienia G 

w bloku sumatora jest tak e działaniem ł cznym (asocjacyjnym) 

C

B

A

B

A

A

C

BA

BA

C

B

B

A

A

CB

A

A

CBA

G

P

P

G

P

G

G

P

G

G

P

G

P

G

G

P

G

G

+

+

=

+

=

=

+

+

=

+

=

)

(

)

(

 

Funkcje rekursywnie skojarzone – takie, które opisuje operator asocjacyjny 

•

 

y

i

= x

i

•

y

i–1

,         y

0

= x

0

 

Wyznaczanie funkcji rekursywnie skojarzonej – problem prefiksowania 

 

Funkcje G,P s  rekursywnie skojarzone przez wektorowy operator asocjacyjny 

)

,

(

)

,

(

)

,

(

)

,

(

B

A

B

A

A

B

B

A

A

BA

BA

P

P

G

P

G

P

G

P

G

P

G

+

=

•

=

 

)

,

(

)

,

(

)

,

(

)

,

(

C

C

B

B

A

A

CBA

CBA

P

G

P

G

P

G

P

G

•

•

=

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–10 

Funkcje wytwarzania przeniesie  i sum 

Dla dowolnego bloku sumatora pomi dzy pozycjami i oraz k (k

≥

s

≥

i ): 

i

k

i

k

i

k

c

P

G

c

,

,

1

+

=

+

 

przy tym  

s

i

k

s

k

s

k

i

G

P

G

G

,

,

1

,

1

,

+

+

+

=

, 

k

s

s

i

k

i

P

P

P

,

1

,

,

+

=

. 

Poniewa  

k

k

k

k

k

y

x

g

G

=

=

,

 i 

k

k

k

k

k

y

x

p

P

+

=

=

,

 (lub 

k

k

k

k

k

y

x

h

P

⊕

=

=

,

), wi c  

i

k

i

j

j

k

k

k

k

i

g

p

g

p

g

G

∏

+

=

−

+

+

+

=

1

1

,

...

, 

∏

=

=

k

i

j

j

k

i

p

P

,

, 

Je li c

0

= 0, to warto  sumy s

i

 zale y tylko od warto ci funkcji G

0,i

−

1

 oraz h

i 

1

,

0

−

⊕

=

⊕

=

i

i

i

i

i

G

h

c

h

s

 

– schemat wyznaczania funkcji G

0,i

 i P

0,i

 mo na optymalizowa  

– wszystkie funkcje G

0,i

 i P

0,i

 mo na wyznaczy  w sekwencji log

2

n działa  

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–11 

Sumatory prefiksowe (PPA) 

sumator prefiksowy – parallel prefix adder, PPA 

 

1

,

0

−

⊕

=

i

i

i

G

h

s

 

 

x

k–1

y

k–1

s

k–1 

GP 

x

i

y

i

x

i–1

y

i–1

x

0

y

0

s

i 

s

i–1 

s

0 

 

 

Blok GP – wytwarzanie warto ci przeniesie   c

i

= G

0,i–1 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–12 

Sumator uniwersalny (1) 

Je li c

0

  nie jest ustalone to  

)

(

0

1

,

0

1

,

0

c

P

G

h

c

h

s

i

i

i

i

i

i

−

−

+

⊕

=

⊕

=

 

Aby unikn

 wielokrotnego rozgał zienia sygnału c

0

 w strukturze prefiksowej 

mo na uzupełni  sumator o blok wej ciowy CSA, redukuj c w ten sposób jeden 
sygnał na pozycji najmniej znacz cej.  
 

c

wy

c

we

=

0

c

0

y

0

x

0

y

1

x

1

y

2

x

2

y

3

x

3

y

k

–

3

x

k

–

3

y

k

–

2

x

k

–

2

y

k

–

1

x

k

–

1

sumator PPA

 

 
Wnoszone opó nienie w kategoriach AT jest takie samo jak w realizacji funkcji 
G

0,i–1

+P

0,i–1

 c

0

, ale nie wyst puje problem rozgał zienia sygnału c

0

 (faktycznie 

T

XOR

 < T

AND-OR

). 

 
Podobne rozwi zanie mo na zastosowa  w uniwersalnym sumatorze U2.  

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–13 

Sumator uniwersalny (2) 

Je li c

0

  nie jest ustalone to  

)

(

0

1

,

0

1

,

0

c

P

G

h

c

h

s

i

i

i

i

i

i

−

−

+

⊕

=

⊕

=

 

Aby unikn

 konieczno ci korekcji c

i

 w sytuacji gdy c

0

 nie jest znane z góry, 

mo na potraktowa  c

0

 jako funkcj  generowania przeniesienia z pozycji „–1”, 

g

–1

= c

0

, gdy jednocze nie p

–1

= 0, i wtedy wszystkie funkcje  P

–1,i 

= 0 oraz: 

)

(

[

1

1

1

1

,

0

1

,

0

−

−

−

−

−

+

+

⊕

=

c

p

g

P

G

h

s

i

i

i

i

] 

wi c sumy trzeba oblicza  jako: 

1

,

1

1

1

,

1

1

,

1

)

(

−

−

−

−

−

−

−

⊕

=

+

⊕

=

⊕

=

i

i

i

i

i

i

i

i

G

h

c

P

G

h

c

h

s

 

To oznacza,  e graf prefiksowy musi obejmowa  n+1 pozycji. W szczególno ci: 

0

,

1

1

1

,

1

0

,

1

1

1

1

,

1

1

0

0

,

1

1

0

0

0

,

1

   

,

   

,

−

−

−

−

−

−

−

−

=

+

=

=

+

=

P

p

P

G

p

g

G

p

p

P

g

p

g

G

 

To rozwi zanie jest szybsze ni  poprzednie, a problemem jest szybka realizacja 
(3 poziomy logiczne) funkcji: 

0

0

1

0

1

1

1

,

1

c

p

p

g

p

g

G

+

+

=

−

. 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–14 

Tworzenie funkcji G,P 

• 

regularne struktury dla n = 2

k

,  

• 

w innych przypadkach przyj

 k = int log

2

2n i usun

 zb dne gał zie grafu 

 
 

• 

Ladner-Fischer (Sklansky) 

– tworzenie funkcji G i P dla par, czwórek, ósemek, ... s siednich bitów 
 

• 

Kogge-Stone 

– optymalizacja ze wzgl du na liczb  rozgał zie  
 

• 

Brent-Kung  

– optymalizacja dla struktur CMOS  
 

• 

Han-Carlson 

– tworzenie funkcji G i P dla par, czwórek, ósemek, ... s siednich bitów 
poczynaj c od bitu parzystego, potem doł czenie nieparzystych  

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–15 

Przekształcenie prefiksowe Ladnera-Fischera (Sklansky) dla funkcji G,P 

 
Poziom 0 (i = 0, 1, … , n

−

1) 

G

0,0

 

P

i,i

= x

i

⊕

y

i

,       G

i,i

= x

i

y

i

 

 

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1) 

G

0,1

 

(G

2i,2i+1

, P

2i,2i+1

) = ( G

2i+1,2i+1

, P

2i+1,2i+1

)

l

(G

2i,2i

, P

2i,2i

)  

 

Poziom 2 (i = 0, 1, … , 2

−

2

n

−

1; s = 2, 3)

   

G

0,3

, G

0,2

 

(G

4i,4i+s

, P

4i,4i+s

) = ( G

4i+2,4i+s

, P

4i+2,4i+s

)

l

( G

4i,4i+1

, P

4i,4i+1

) 

 

Poziom 3 (i = 0, 1, … , 2

−

3

n

−

1; s = 4, 5, 6, 7)  

G

0,7

, …, G

0,4

 

(G

8i,8i+s

, P

8i,8i+s

) = ( G

8i+4,8i+s

, P

8i+4,8i+s

)

l

( G

8i,8i+3

, P

8i,8i+3

) 

 

Poziom 4 (i = 0, 1, … , 2

−

4

n

−

1; s = 8, 9, …, 15)  

G

0,15

, …, G

0,8

 

(G

16i,16i+s

, P

16i,16i+s

) = ( G

16i+8,16i+s

, P

16i+8,16i+s

)

l

( G

16i,16i+7

,P

16i,16i+7

)  

… 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–16 

Przekształcenie prefiksowe Kogge-Stone’a dla funkcji G,P 

 
Poziom 0 (i = 0, 1, … , n

−

1) 

G

0,0

 

P

i,i

= x

i

⊕

y

i

,       G

i,i

= x

i

y

i

 

 

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1) 

G

0,1

 

(G

i,i+1

, P

i,i+1

) = ( G

i+1,i+1

, P

i+1,i+1

)

l

(G

i,i

, P

i,i

)  

 

Poziom 2 (s = 0, 1;  i = 0, 1, … , n

−

2

2

) 

G

0,s+2

= G

s+1,s+2

+ P

s+1,s+2

G

0,s  

( G

0,3

) , G

0,2

 

(G

i,i+3

, P

i,i+3

) = ( G

i+2,i+3

, P

i+2,i+3

)

l

(G

i,i+1

, P

i,i+1

)   

G

0,3

 

 

Poziom 3 (s = 0, 1, …, 2

2

−

1;  i = 0, 1, … , n

−

2

3

) 

G

0,s+4

= G

s+1,s+4

+ P

s+1,s+4

G

0,s

 

(G

0,7

) , G

0,6

, G

0,5

, G

0,4

 

(G

i,i+7

, P

i,i+7

) = ( G

i+4,i+7

, P

i+4,i+7

)

l

(G

i,i+3

, P

i,i+3

)   

G

0,7

 

 

Poziom 4 (s = 0, 1, …, 2

3

−

1;  i = 0, 1, … , n

−

2

4

) 

G

0,s+8

= G

s+1,s+8

+ P

s+1,s+8

G

0,s

 

(G

0,15

) , … …, G

0,8

 

(G

i,i+15

, P

i,i+15

) = ( G

i+8,i+15

, P

i+8,i+15

)

l

(G

i,i+7

, P

i,i+7

)   

G

0,15

 

… 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–17 

Przekształcenie prefiksowe Brenta-Kunga dla funkcji G,P 

 
Poziom 0 (i = 0, 1, … , n

−

1) 

G

0,0

 

P

i,i

= x

i

⊕

y

i

,       G

i,i

= x

i

y

i

 

 

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1) 

G

0,1

 

(G

2i,2i+1

, P

2i,2i+1

) = ( G

2i+1,2i+1

, P

2i+1,2i+1

)

l

(G

2i,2i

, P

2i,2i

)  

 

Poziom 2 (i = 0, 1, … , 2

−

2

n

−

1)  

G

0,3

 

(G

4i,4i+3

, P

4i,4i+3

) = ( G

4i+2,4i+3

, P

4i+2,4i+3

)

l

(G

4i,4i+1

, P

4i,4i+1

)  

 

Poziom 3 (i = 0, 1, … , 2

−

3

n

−

1)  

G

0,7

 

(G

8i,8i+7

, P

8i,8i+7

) = ( G

8i+4,8i+7

, P

8i+4,8i+7

)

l

(G

8i,8i+3

, P

8i,8i+3

)  

… 

Poziom m = log

2

n (T = 2

m

−

2

) 

(G

0,3T

−

1

, P

0,3T

−

1

) = ( G

2T,3T

−

1

, P

2T,3T

−

1

)

l

(G

0,2T

 −

1

, P

0,2T

 −

1

)  

G

0,3T

 

(G

0,n

−

1

, P

0,n

−

1

) = ( G

2T,n

−

1

, P

2T,n

−

1

)

l

(G

0,2T

 −

1

, P

0,2T

 −

1

)  

G

0,n

−

1

 

… 
Poziom m+r  (i = (0), 1, … , 2

2

−

1, R = 2

m

−

2

−

s

),  r = 1, … , m

−

2  

(G

0,iR

−

1

, P

0,iR

−

1

) = ( G

2R,iR

−

1

, P

2R,iR

−

1

)

l

(G

0,2R

 −

1

, P

0,2R

 −

1

)  

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–18 

Przekształcenie prefiksowe Han’a-Carlson’a dla funkcji G,P 

Poziom 0 (i = 0, 1, … , n

−

1) 

G

0,0

 

P

i,i

= x

i

⊕

y

i

,       G

i,i

= x

i

y

i

 

 

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1) 

G

0,1

 

(G

2i,2i+1

, P

2i,2i+1

) = ( G

2i+1,2i+1

, P

2i+1,2i+1

)

l

(G

2i,2i

, P

2i,2i

)  

 

Poziom 2 (i = 0, 1, … , 2

−

2

n

−1

)   

G

0,3

 

(G

2i,2i+3

, P

2i,2i+3

) = ( G

2i+2,2i+3

, P

2i+2,2i+3

)

l

(G

2i,2i+1

, P

2i,2i+1

)  

 

Poziom 3 (s = 0, 1;   i = 0, 1, … , 2

−

3

n

−

1) 

(G

2i,2i+7

, P

2i,2i+7

) = ( G

2i+4,2i+7

, P

2i+4,2i+7

)

l

(G

2i,2i+3

, P

2i,2i+3

)  

G

0,2s+5

= G

2s+1,2s+5

+ P

2s+1,2s+5

G

0,2s  

G

0,7

, G

0,5

 

 

Poziom 4 (s = 0, 1, …, 2

2

−

1;  i = 0, 1, … , 2

−

3

n

−

1) 

(G

2i,2i+15

, P

2i,2i+15

) = ( G

2i+8,2i+15

, P

2i+8,2i+15

)

l

(G

2i,2i+7

, P

2i,2i+7

)  

G

0,2s+9

= G

2s+1,2s+9

+ P

2s+1,2s+8

G

0,2s

  

G

0,15

, G

0,13

, G

0,11

, G

0,9

 

 

... 
Poziom log

2

n+1  (i = 0, 1, … , 2

−

1

n

−

1) 

G

0,2i

= G

2i,2i

+ P

2i,2i

G

0,2i

−

1

 

G

0,2i

, … , G

0,4

, G

0,2

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–19 

Prefiksowe schematy generowania i propagacji przeniesienia (PPA) 

 

 

 

15  14  13  12  11  10 

9 

8 

7 

6 

5 

4 

3 

2 

1 

0 

4 

3 

2 

1 

0 

 

 

Graf prefixowy  (Sklansky / Ladner-Fischer) 

 

 

15  14  13  12  11  10 

9 

8 

7 

6 

5 

4 

3 

2 

1 

0 

4 

3 

2 

1 

0 

 

Graf prefixowy (Kogge & Stone) 

 

 

15  14  13  12  11  10 

9 

8 

7 

6 

5 

4 

3 

2 

1 

0 

4 

3 

2 

1 

0 

5 

6 

 

Graf prefixowy (Brent–Kung) 

 

 

15  14  13  12  11  10 

9 

8 

7 

6 

5 

4 

3 

2 

1 

0 

4 

3 

2 

1 

0 

5 

 

Graf prefixowy – (Han & Carlson) 

¤

 – wytwarzanie funkcji G

i,i

= g

i

  oraz  P

i,i

= p

i

  

¡

 – przekazywanie G oraz P 

l

 – operator prefiksowy (G

BA

,P

BA

) = (G

B

,P

B

)

l

(G

A

,P

A

)  

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–20 

Charakterystyki grafów prefiksowych 

Ladner-Fischer   – log

2

n poziomów logicznych, minimum elementów GP 

nierównomierne obci

enia (Sklansky) 

Kogge & Stone   – log

2

n poziomów logicznych, wi cej elementów GP, 

rozło ona obci

alno  wyj  

Brent-Kung  

– >log

2

n poziomów logicznych, mniej elementów GP,  

stała obci

alno  wyj  

Han & Carlson  – >log

2

n poziomów logicznych, najmniej elementów GP, 

najmniejsza obci

alno  wyj  

Parametry sieci GP jako elementy PPA 

Typ struktury 

liczba ogniw GP  liczba poziomów  obci

enie 

przeł czenia 

RCA 

2

/

3

 n  

n – 1 

2 

n /2 

Ladner-Fischer 

½ n log

2

n  

log

2

n 

n /2 

¼ n log

2

n  

Brent-Kung 

2n – n log

2

n –2 

2 log

2

n – 2 

log

2

n + 1  ~ 

3

/

8

 n log

2

n  

Kogge & Stone 

n log

2

n – n + 1 

log

2

n  

2 

½ n log

2

n  

Han & Carlson 

½ n log

2

n 

log

2

n + 1 

2 

¼ n log

2

n  

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–21 

Sumy warunkowe – koncepcja 

L 

i

i

y

x

+

  1+0  0+0  1+1  1+0  0+1  1+1  1+0  0+1 

0 

0

1

+

i

c  

0 

0 

1 

0 

0 

1 

0 

0 

 

0

:i

i

s

 

1 

0 

0 

1 

1 

0 

1 

1 

 

1

1

+

i

c  

1 

0 

1 

1 

1 

1 

1 

— 

 

1

:i

i

s

 

0 

1 

1 

0 

0

 

1 

0 

— 

1 

0

2

2

+

i

c

 

0 

 

1 

 

1 

 

0 

 

 

0

2

:

1

2

i

i

s

+

 

1 

0 

0 

1 

0 

0 

1 

1 

 

1

2

2

+

i

c

 

0 

 

1 

 

1 

 

— 

— 

 

1

2

:

1

2

i

i

s

+

 

1 

1 

1 

0 

0 

1 

— 

— 

2 

0

4

4

+

i

c

 

0 

 

 

 

1 

 

 

 

 

0

4

:

3

4

i

i

s

+

 

1 

1 

0 

1 

0 

0 

1 

1 

 

1

4

4

+

i

c

 

0 

 

 

 

— 

— 

— 

— 

 

1

4

:

3

4

i

i

s

+

 

1 

1 

1 

0 

— 

— 

— 

— 

 

3

0

:

7

s

 

1 

1 

1 

0 

0 

0 

1 

1 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–22 

Sumator sum warunkowych (conditional sum adder, COSA) 

Tworzenie alternatywnych sum jedno-, dwu-, cztero-, o mio-, ...-bitowych 
 
Poziom 0 – sumy i przeniesienia warunkowe dla osobnych bitów (

i = 0,1,...) 

0

:

0

:

2

0

i

i

i

i

i

i

s

c

y

x

+

=

+

+

  oraz  

1

:

1

:

2

1

i

i

i

i

i

i

s

c

y

x

+

=

+

+

 

}

,

{

}

,

{

1

:

0

:

:

i

i

i

i

i

i

i

i

i

i

y

x

y

x

s

s

≡

⊕

=

=

s

  

}

,

{

}

,

{

1

1

0

1

1

i

i

i

i

i

i

i

y

x

y

x

c

c

+

=

=

+

+

+

c

 

 

Poziom p  (|| – zło enie wektorów) 

– warunkowe sumy 

α

ri

r

ri

2

,

1

2

2

−

+

s

 i przeniesienia 

α

)

1

(

2

+

i

r

c

 grup r = 2

p

 bitów, 

– dla  i = 0,1,...,n·2

–p



−

1 

α

α

α

α

ri

r

ri

r

ri

r

ri

r

ri

r

ri

r

ri

r

ri

ri

r

ri

c

c

2

,

1

2

1

2

,

1

2

2

2

1

2

,

1

2

2

2

2

,

1

2

2

||

]

)

1

(

[

−

+

+

−

+

+

+

−

+

+

−

+

−

+

=

s

s

s

s

, 

0

2

2

2

1

2

2

2

)

1

(

2

)

1

(

r

ri

r

ri

r

ri

r

ri

i

r

c

c

c

c

c

+

+

+

+

+

−

+

=

α

α

α

 

Ko cowy wynik sumowania powstaje na poziomie k = log

2

n  (r = 2

k

). 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–23 

Schemat sumatora sum warunkowych 

 

s

0

 

s

1

 

s

2

 

s

3

 

c

7

 

L 0 

x

1

y

1

ΣΣΣΣ

0/1

 

s

0

 

s

1

 

c

0

 

c

1

 

x 

y

1 0

1 0

x

2

y

2

x

0

y

0

ΣΣΣΣ

0/1

 

x

3

y

3

ΣΣΣΣ

0/1

 

ΣΣΣΣ

0/1

 

1  0 

1  0 

x

4

y

4

x

5

y

5

ΣΣΣΣ

0/1

 

ΣΣΣΣ

0/1

 

1  0 

1  0 

x

6

y

6

x

7

y

7

ΣΣΣΣ

0/1

 

ΣΣΣΣ

0/1

 

1 0

1 0

1  0 

1  0 

1  0 

1  0 

1 0

1 0

1 0

1 0

1  0 

1  0 

1 0

L 1 

L 2 

L 3 

s

4

 

s

5

 

s

6

 

s

7

 

ΣΣΣΣ

0/1

 

1

0

0 

0 

1 

1 

 

O miobitowy sumator sum warunkowych 

T = 2 log

2

2 n ,  A = ½ (n log

2

n + 2n log

2

n)= 3n log

2

n 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–24 

Sumator sterowany przeniesieniem (CSLA) 

Sumator multipleksowany sterowany przeniesieniem (carry-select adder) 

wybór 

i

k -pozycyjnych sum warunkowych zale nie od przeniesienia 

 

x

m,l

y

m,l

x

l,k

y

l,k

x

k,i

y

k,i

x

i,

y

i,

0

0

x

m,l

y

m,l

x

l,k

y

l,k

x

k,i

y

k,i

s

m,l

s

l,k

s

k,i

s

i, 0

0

0

0

CPA

CPA

CPA

MPX

CPA

CPA

MPX

CPA

CPA

MPX

0

1

0

s

m,l

1

s

l,k

1

s

k,i

1

s

m,l

s

l,k

s

k,i

c

m +1

 

 

Schemat logiczny sumatora multipleksowanego sterowanego przeniesieniem 

 
Sumy blokowe obliczane jednocze nie ⇒ wy sze bity

→

wi ksze bloki 

Opó nienie – > 2

n

2   (optymalna liczba bloków – około 

n

2 ) 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–25 

Sumator z przeskokiem przeniesie  (CSKA) 

Suma w bloku s-bitowym zale y od przeniesienia wej ciowego (carry-in).  

propagacja przeniesienia przez cały blok 

→

 „przeskok” przeniesienia 

 

x

n,m

y

n,m

s

P

n,m

c

n

n,m

+1

CPA

x

m,l

y

m,l

s

P

m,l

c

m

m,l

+1

CPA

x

l,k

y

l,k

s

P

l,k

c

l

l,k

+1

CPA

x

j,i

y

j,i

s

P

j,i

c

j

j,i

+1

CPA

x

i,

y

i,

s

c

i

i,

+1

CPA

0

0

0

c

0

...

c

k+1

P

i, 0

 

 

Schemat sumatora z przeskokiem przeniesie  CSKA (carry-skip adder) 

 
Opó nienie wnoszone przez sumator CSKA zale y od 
– czasu wytworzenia przeniesienia w bloku, w którym zaczyna si  propagacja, 
– czasu wytworzenia sumy w bloku ,w którym ko czy si  propagacja, 
– czasu przeskoku przeniesienia przez bloki wewn trzne. 
l jednakowych bloków k-bitowych (n = kl) opó nienie wyniesie  

 

δ

δ

δ

]

2

2

[

2

]

4

2

[

)]

1

(

2

)

1

[(

1

0

−

≥

−

+

=

−

+

−

+

−

=

∆

−

n

k

n

k

k

l

k

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–26 

Analiza szybko ci sumatora z przeskokiem przeniesie  

Czas dodawania: 

• 

czas wytworzenia przeniesienia na wyj ciu u–go bloku wej ciowego 

• 

czas przeskoku przeniesienia przez [v

−

(u+1)] bloków  

• 

czas wytworzenia sumy od ustalenia przeniesienia na wej ciu bloku v  

 

δ

)]

1

(

)

1

(

)

1

[(

)

,

(

−

+

−

−

+

−

=

∆

v

u

g

v

u

g

v

u

 

 

 

struktura  

cie ka  

opó nienie  

max  

6 bloków 

4-4-4-4-4-4 

 

(4

−

1)+4+(4

−

1) = 10 

10 

 

3-4-5-5-4-3 

5-5 

(5

−

1)+0+(5

−

1) =  8 

8 

 

2-5-6-5-4-2 

5-6-5-4 

(5

−

1)+2+(4

−

1) =  9 

9 

 

 

6-5-4 

(6

−

1)+1+(4

−

1) =  9 

9 

8 bloków 

1-2-3-6-6-3-2-1 

3-6-6-3 

(3

−

1)+2+(3

−

1) =  6 

 

 

 

6-6 

(6

−

1)+0+(6

−

1) = 10 

10 

 

1-2-4-5-5-4-2-1 

4-5-5-4 

(4

−

1)+2+(4

−

1) =  8 

8 

 

1-2-3-4-5-4-3-2 

4-5-4 

(4

−

1)+1+(4

−

1) =  7 

7 

9 bloków 

1-2-3-4-4-4-3-2-1 

2-3-4-4-4-3-2 

(2

−

1)+5+(2

−

1) =  7 

7 

 

 

3-4-4-4-3 

(3

−

1)+3+(3

−

1) =  7 

7 

 

 

3-4-4-4 

(3

−

1)+2+(4

−

1) =  7 

7 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–27 

Optymalizacja sumatora z przeskokiem przeniesie  

 

Zało enie: standardowe opó nienia prostych funkcji  

Heureza 

• 

ła cuchy optymalne: 

je li rozmiar k bloków wytwarzaj cych mniej znacz ce pozycje sumy 
jest typu  

,...,k

,

i=

g

g

i

u

i

u

2

1

  

,

1

=

1

+

−

+

+

,  to maksymalne opó nienie  

 

g

u+k

δ 

= (g

u

+ i

−

1)

δ

 +(k

−

i)

δ 

= (g

u

+ k

−

1)

δ 

; 

je li rozmiar s bloków wytwarzaj cych bardziej znacz ce pozycje sumy 
jest typu 

1

2

1

0

  

,

1

=

1

,...,s-

,

,

i=

g

g

i

v

i

v

−

−

+

+

, to maksymalne opó nienie  

 

g

v+s

δ 

= (g

v

+ i

−

1)

δ

 +(s

−

i)

δ 

= (g

v

+ s

−

1)

δ

 ; 

• 

ła cuchy nieoptymalne: 

je li skrajne bloki ła cucha nie s  skrajnymi blokami ła cuchów 
optymalnych, to tworz   cie k  krytyczn  propagacji przeniesienia.  

 
Wnioski 

• 

optymalna struktura sumatora powinna by  typu  1-2-3-...-3-2-1. 

• 

optymaln  struktur  sumatora jest tak e  „1-2-3-...-3-2-1”\”1-2-…-s”. 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–28 

Optymalizacja sumatora z przeskokiem przeniesie  - przykład 

• 

n-bitowy ła cuch optymalny 1-2-3-...-3-2-1 zawiera 

1

2

−

n

 bloków  

• 

sumator n-bitowy powinien mie  najwy ej 

1

2

−

n

 bloków 

• 

(p–1)

2

≤

n

≤

p

2

–s

2

 ⇒ sumator n-bitowy powinien mie  

≤

2(p–s) bloków   

 
Przykład

. Sumator 32-bitowy powinien mie  

≤

8 bloków (32=6

2

–2

2

) 

liczba grup  struktura sumatora 

maksymalne opó nienie  

9 

2-3-4-5-4-5-4-3-2 

(5

−

1)+1+(5

−

1) =  9 

8 

3-4-5-4-4-5-4-3 

(5

−

1)+2+(5

−

1) = 10 

8 

2-3-4-6-6-5-4-2 

(6

−

1)+2+(4

−

1) = 10 

8 

2-3-4-5-6-5-4-3 

(6

−

1)+0+(5

−

1) =  9 

 
Przykład

. Sumator 24-bitowy powinien mie  

≤

8 bloków (24=5

2

–1

2

) 

liczba grup  struktura sumatora 

maksymalne opó nienie  

8 

2-3-4-5-4-3-2-1 

(5

−

1)+0+(4

−

1) =  7 

8 

1-2-3-4-5-4-3-2 

(5

−

1)+0+(4

−

1) =  7 

7 

2-3-4-6-4-3-2 

(6

−

1)+0+(4

−

1) =  8 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–29 

Inkrementer i dekrementer 

wykonuje działanie  X

±

1 

 

→

 wystarczy ła cuch półsumatorów (HA) lub półsubtraktorów (HS) 

 
półsumator (half adder, HA) – realizuje funkcje  

i

i

i

c

x

s

⊕

=

, 

i

i

i

c

x

c

=

+

1

 

półsubtraktor (half subtracter, HS) – realizuje funkcje  

i

i

i

c

x

s

⊕

=

, 

i

i

i

c

x

c

=

+

1

 

 

 

c

k

−2

 

x

1

 

s

1

 

c

2

 

s

k

−1

 

c

k

−1

 

c

k

 

x

k

−1

 

HA/HS

 

x

0

 

s

0

 

1 

c

1

 

s

k

−2

 

x

k

−2

 

HA/HS

 

HA/HS

 

HA/HS

 

 
sumator z inkrementacj  wskutek przeniesienia (carry-increment adder, CIA 
 
układ zliczaj cy – inkrementer/dekrementer ze sprz eniem  

)

(

)

1

(

t

i

t

i

s

x

=

+

 

 

 

 

i zapami tywaniem stanu 

)

(

0

)

(

1

)

(

2

)

(

1

,

,...,

,

{

)

(

t

t

t

k

t

k

s

s

s

s

t

S

−

−

=

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc, 2 pa

ź

dziernika 2006

 

 

FAST–30 

Szybko  działania i zło ono  sumatorów 

Charakterystyki AT  

• 

sumator pełny FA – A = 7, T = 2 + 2  

→

  A T = 28 

– 2

×

XOR, 1

×

OR, 2

×

AND 

→

 opó nienie przeniesienia 2 ,   sumy 2 + 2  

 

• 

sumator RCA – A = 7n, T = 2n 

→

  A T = 14n

2

 

– n

×

FA 

→

 opó nienie przeniesienia  n

⋅

2 

• 

sumator CLA – A

≈

7n, T

≈

4 log n 

→

  A T

≈

56 n log n 

– n

×

FA 

→

 log n bloków, opó nienie przeniesienia  2

⋅

2 log n 

• 

sumator CSKA – A

≈

8n, T

≈

2

⋅

n

2

 

→

  A T

≈

32 n n  

– n

×

FA+2 n

×

MPX, 2 n  bloków 

→

 opó nienie przeniesienia  2

⋅

n

2

 

• 

sumator CSLA – A

≈

2

⋅

7n, T

≈

n

2

2

 

→

  A T

≈

39 n n  

– 2

×

RCA, 

n

2  bloków, opó nienie przeniesienia  2

⋅

n

2  

• 

sumator COSA – A = 3n log n, T = 2 log n 

→

  A T = 6 n log

2

n 

– 2

×

RCA, log n poziomów MPX, opó nienie przeniesienia 2

⋅

log n 

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa

ź

dziernika 2006

 

 

FAST–13a 

Przekształcenie prefiksowe Ladnera-Fischera (Sklansky) dla funkcji G,P 

P

i,i

= x

i

⊕

y

i

,       G

i,i

= x

i

y

i

      (i = 0, 1, … , n

−

1) 

G

0,0

 

 

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1) 

P

2i,2i+1

= P

2i+1,2i+1

P

2i,2i

 

G

2i,2i+1

= G

2i+1,2i+1

+ P

2i+1,2i+1

G

2i,2i

   

G

0,1

 

 

Poziom 2 (i = 0, 1, … , 2

−

2

n

−

1; s = 2, 3) 

P

4i,4i+s

= P

4i+2,4i+s

P

4i,4i+1

 

G

4i,4i+s

= G

4i+2,4i+s

+ P

4i+2,4i+s

G

4i,4i+1   

G

0,3

, G

0,2

 

 

Poziom 3 (i = 0, 1, … , 2

−

3

n

−

1; s = 4, 5, 6, 7) 

P

8i,8i+s

= P

8i+4,8i+s

P

8i,8i+3

 

G

8i,8i+s

= G

8i+4,8i+s

+ P

8i+4,8i+s

G

8i,8i+3

  

G

0,7

, …, G

0,4

 

 

Poziom 4 (i = 0, 1, … , 2

−

4

n

−

1; s = 8, 9, …, 15) 

P

16i,16i+s

= P

16i+8,16i+s

P

16i,16i+7

 

G

16i,16i+s

= G

16i+8,16i+s

+ P

16i+8,16i+s

G

16i,16i+7

  

G

0,15

, …, G

0,8

 

… 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa

ź

dziernika 2006

 

 

FAST–14a 

Przekształcenie prefiksowe Kogge-Stone’a dla funkcji G,P 

P

i,i

= x

i

⊕

y

i

,       G

i,i

= x

i

y

i

      (i = 0, 1, … , n

−

1) 

G

0,0

 

 

Poziom 1 (i = 0, 1, … , n

−

2) 

P

i,i+1

= P

i+1,i+1

P

i,i

,   G

i,i+1

= G

i+1,i+1

+ P

i+1,i+1

G

i,i

 

G

0,1

 

 

Poziom 2 (s = 0, 1;  i = 0, 1, … , n

−

2

2

) 

P

i,i+3

= P

i+2,i+3

P

i,i+1

 

G

0,s+2

= G

s+1,s+2

+ P

s+1,s+2

G

0,s  

G

0,3

, G

0,2

 

G

i,i+3

= G

i+2,i+3

+ P

i+2,i+3

G

i,i+1  

(G

0,3

) 

 

Poziom 3 (s = 0, 1, …, 2

2

−

1;  i = 0, 1, … , n

−

2

3

) 

P

i,i+7

= P

i+4,i+7

P

i,i+3

 

G

0,s+4

= G

s+1,s+4

+ P

s+1,s+4

G

0,s

 

G

0,7

, G

0,6

, G

0,5

, G

0,4

 

G

i,i+7

= G

i+4,i+7

+ P

i+4,i+7

G

i,i+3

 

(G

0,7

) 

 

Poziom 4 (s = 0, 1, …, 2

3

−

1;  i = 0, 1, … , n

−

2

4

) 

G

0,s+8

= G

s+1,s+8

+ P

s+1,s+8

G

0,s

 

G

0,15

, … …, G

0,8

 

… 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa

ź

dziernika 2006

 

 

FAST–15a 

Przekształcenie prefiksowe Brenta-Kunga dla funkcji G,P 

P

i,i

= x

i

⊕

y

i

,       G

i,i

= x

i

y

i

      (i = 0, 1, … , n

−

1) 

G

0,0

 

 

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1) 

G

2i,2i+1

= G

2i+1,2i+1

+ P

2i+1,2i+1

G

2i,2i

,   P

2i,2i+1

= P

2i+1,2i+1

P

2i,2i

 

G

0,1

 

 

Poziom 2 (i = 0, 1, … , 2

−

2

n

−

1) 

P

4i,4i+3

= P

4i+2,4i+3

P

4i,4i+1

, 

G

4i,4i+3

= G

4i+2,4i+3

+ P

4i+2,4i+3

G

4i,4i+1

 

G

0,3

 

 

Poziom 3 (i = 0, 1, … , 2

−

3

n

−

1) 

P

8i,8i+7

= P

8i+4,8i+7

P

8i,8i+3

, 

G

8i,8i+7

= G

8i+4,8i+7

+ P

8i+4,8i+7

G

8i,8i+3

 

G

0,7

 

… 

Poziom m = log

2

n (T = 2

m

−

2

) 

G

0,3T

−

1

= G

2T,3T

−

1

+ P

2T,3T

−

1

G

0,2T

 −

1

,   P

0,3T

−

1

= P

2T,3T

−

1

P

0,2T

−

1

, 

G

0,3T

 

G

0,n

−

1

= G

2T,n

−

1

+ P

2T,n

−

1

G

0,2T

 −

1

,     P

0,n

−

1

= P

2T,n

−

1

P

0,2T

 −

1

, 

G

0,n

 

 

Poziom m+1  (i = (0), 1, … , 2

2

−

1, R = 2

m

−

3

) 

G

0,iR

−

1

= G

2R,iR

−

1

+ P

2R,iR

−

1

G

0,2R

−

1

    

G

0,13

,G

0,9

,G

0,5

 

P

0,iR

−

1

= P

2R,iR

−

1

P

0,2R

−

1

 

 

 

Szybkie sumatory 

© Janusz Biernat, 10-06-Szybkie sumatory.doc ,2 pa

ź

dziernika 2006

 

 

FAST–16a 

Przekształcenie prefiksowe Han’a-Carlson’a dla funkcji G,P 

P

i,i

= x

i

⊕

y

i

,       G

i,i

= x

i

y

i

      (i = 0, 1, … , n

−

1) 

G

0,0

 

 

Poziom 1 (i = 0, 1, … , 2

−

1

n

−

1) 

P

2i,2i+1

= P

2i+1,2i+1

P

2i,2i

 

G

2i,2i+1

= G

2i+1,2i+1

+ P

2i+1,2i+1

G

2i,2i

 

G

0,1

 

 

Poziom 2 (i = 0, 1, … , 2

−

2

n

−1

) 

P

2i,2i+3

= P

2i+2,2i+3

P

2i,2i+1

 

G

2i,2i+3

= G

2i+2,2i+3

+ P

2i+2,2i+3

G

2i,2i+1

 

G

0,3

 

 

Poziom 3 (s = 0, 1;   i = 0, 1, … , 2

−

3

n

−

1) 

P

2i,2i+7

= P

2i+4,2i+7

P

2i,2i+3

 

G

0,2s+5

= G

2s+1,2s+5

+ P

2s+1,2s+5

G

0,2s  

G

0,7

, G

0,5

 

G

2i,2i+7

= G

2i+4,2i+7

+ P

2i+4,2i+7

G

2i,2i+3

 

 

Poziom 4 (i = 0, 1, … , 2

−

3

n

−

1) 

P

2i,2i+15

= P

2i+8,2i+15

P

2i,2i+7

 

G

2i,2i+15

= G

2i+8,2i+15

+ P

2i+8,2i+15

G

2i,2i+7

 

G

0,15

, G

0,13

, G

0,11

, G

0,9

 

... 

Poziom log

2

n+1  (i = 0, 1, … , 2

−

1

n

−

1) 

G

0,2i

= G

2i,2i

+ P

2i,2i

G

0,2i

−

1

 

G

0,2i

, … , G

0,4

, G

0,2