Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

1 

Algorytm dodawania i odejmowania 

 

c

k−2

 

x

1

 

s

1

 

c

2

 

 y

1

 

s

k−1

 

c

k−1

 

c

k

 

 y

k−1

 

x

k−1

 

FA/FS

 

x

0

 

s

0

 

c

0

 

c

1

 

 y

0

 

s

k−2

 

 y

k−2

 

x

k−2

 

FA/FS

 

FA/FS

 

FA/FS

 

 

 

Schemat dodawania/odejmowania binarnego 

 

dodawanie (X+Y) 

odejmowanie (X–Y) 

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

c

y

x

y

x

c

y

x

y

x

c

c

y

x

s

)

(

)

(

1

+

+

=

⊕

+

=

⊕

⊕

=

+

 

i

i

i

i

i

i

i

i

i

i

i

i

i

i

i

c

y

x

y

x

c

y

x

y

x

c

c

y

x

s

)

(

)

(

1

⊕

+

=

⊕

+

=

⊕

⊕

=

+

 

Propagacja przeniesienia  

•  obliczenie sumy/ró nicy na pozycji i wymaga przeniesienia z pozycji i−1 
•  czas wytworzenia sumy/ró nicy – stały od chwili ustalenia przeniesienia 
•  gwarantowany czas wykonania dodawania/odejmowania zale y od 

najdłu szego czasu przesłania zmiany przeniesienia

 z pozycji najni szej 

•  czas sekwencyjnego dodawania/odejmowania n-pozycyjnego – nT 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

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 tymczasowych 

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

– tworzenie wariantowych sum dla bloków 2

i

 kolejnych pozycji 

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

– równoległe wytwarzanie alternatywnych sum cz ciowych 

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

– korekcja sum blokowych przeniesieniami  

•  obliczanie i korekcja sum tymczasowych (ELM) 

 

Składanie sum redundantnych 

•  nadmiarowa reprezentacja argumentów (SD) → dodawanie dwuetapowe 

 
Teoretycznie osi galny czas dodawania/odejmowania n-pozycyjnego: T log

2

n

 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

3 

Wytwarzanie i propagacja przeniesie  w dodawaniu 

Funkcja przeniesienia mo e mie  jedn  z równowa nych form 

i

i

i

i

i

i

i

i

i

i

i

c

y

x

y

x

c

y

x

y

x

c

)

(

)

(

1

+

+

=

⊕

+

=

+

 

poniewa  a+b=a⊕b+ab (OR(a,b) = XOR(a,b) + ab). Składowymi wyra enia s : 

 

•  funkcja wytwarzania (generowania) przeniesienia, okre laj ca warunki 

przy których przeniesienie wyj ciowe c

i

+1

=1 niezale nie od c

i

:  

i

i

i

y

x

g =

, 

•  funkcja półsumy, która tak e okre la warunki przekazywania (propagacji) 

przeniesienia (

i

i

y

x ≠

⇒ 

i

i

c

c

=

+1

): 

i

i

i

y

x

h

⊕

=

 

W wyra eniach na przeniesienie mo e j  zast pi   

•   (nadmiarowa) funkcja przekazywania przeniesienia (

i

p

– f. wygaszania) 

i

i

i

y

x

p

+

=

 

UWAGA: 
W wyra eniach na przeniesienie funkcje p

#

 i h

#

  

s  wzajemnie zamienne. 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

4 

Wytwarzanie i propagacja przeniesie  w odejmowaniu 

Funkcja po yczki (przeniesienia wstecznego) mo e mie  jedn  z form 

i

i

i

i

i

i

i

i

i

i

i

c

y

x

y

x

c

y

x

y

x

c

)

(

)

(

1

+

+

=

⊕

+

=

+

 

poniewa  a+b=a⊕b+ab (OR(a,b)=XOR(a,b)+ab). Składowymi wyra enia s : 

 

•  funkcja wytwarzania (generowania) po yczki, okre laj ca warunki przy 

których po yczka z wy szej pozycji c

i

+1

=1 niezale nie od c

i

:  

i

i

i

y

x

g =

, 

•  funkcja półró nicy, która okre la te  warunki przekazywania (wstecznej 

propagacji

) po yczki (

i

i

y

x =

⇒ 

i

i

c

c

=

+1

): 

i

i

i

y

x

h

⊕

=

 

W wyra eniach na po yczki mo e j  zast pi   

•   (nadmiarowa) funkcja przekazywania po yczki (

i

p

– f. wygaszania) 

i

i

i

y

x

p

+

=

 

UWAGA: 
W wyra eniach na po yczki funkcje p

#

 i h

#

  

s  wzajemnie zamienne. 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

5 

Propagacja i generowanie przeniesie  – intuicje (1) 

HL

c



c





 

 

c

out

=1 je li: 

•  c

in

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

out

 

•  wewn trz bloku HL jest wytwarzane c

out

=1, za  c

in

 jest dowolne 

 

H

L

c





c



c

 

 

c

out

=1 je li: 

•  c

in

=1 jest przesyłane przez blok L do c

m

 

a nast pnie przez blok H do c

out

 

•  wewn trz bloku H jest wytwarzane c

out

=1, za  c

m

 jest dowolne 

•  wewn trz bloku L jest wytwarzane c

m

=1,  

a nast pnie przez blok H jest przekazywane do c

out

 

 

Uwaga

: Analogiczne zale no ci mo na poda  dla po yczek w odejmowaniu 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

6 

Propagacja i generowanie przeniesie  – intuicje (2) 

 

G

HL

=1 

G

H

=1 

 

1

P

H

=1 

G

L

=1 

1

1

G

F

=1 

 

 

P

HL

=1 

P

H

=1 

P

L

=1 

1

1

P

HL

=1 

P

H

=1 

P

L

=1 

1

1

P

F

=1 

1

1

1

G

HLF

=1 

P

HLF

=1 

 

L

in

hl

HL

L

in

L

H

L

H

H

out

c

P

G

c

P

P

G

P

G

c

+

=

+

+

=

 

F

in

HLF

HLF

F

in

F

HL

F

HL

HL

out

c

P

G

c

P

P

G

P

G

c

+

=

+

+

=

 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

7 

Funkcje grupowej antycypacji przeniesie  

Wyznaczanie funkcji przekazywania (propagacji) przeniesienia P 

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

F

L

H

F

L

H

HLF

P

P

P

P

P

P

P

=

=

 

Wyznaczanie funkcji wytwarzania (generowania) przeniesienia G 

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

F

L

H

L

H

H

F

HL

HL

F

L

L

H

H

LF

H

H

HLF

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 

L

H

L

H

H

L

L

H

H

HL

HL

P

P

G

P

G

P

G

P

G

P

G

+

=

•

=

 

F

F

L

L

H

H

HLF

HLF

P

G

P

G

P

G

P

G

•

•

=

 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

8 

Funkcje wytwarzania przeniesie  i sum 

Dla dowolnego bloku sumatora pomi dzy pozycjami i oraz k (k ≥ s ≥ i ): 

i

i

k

i

k

k

c

P

G

c

:

:

1

+

=

+

 

przy tym  

i

s

s

k

s

k

i

k

G

P

G

G

:

1

:

1

:

:

+

+

+

=

, 

i

s

s

k

i

k

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

i

k

g

p

g

p

g

G

∏

+

=

−

+

+

+

=

1

1

:

...

, 

∏

=

=

k

i

j

j

i

k

p

P

:

, 

– schemat wyznaczania funkcji G

i

:0

 i P

i

:0

 mo na optymalizowa  

– wszystkie funkcje G

i

:0

 i P

i

:0

 mo na wyznaczy  w sekwencji log

2

n

 działa  

Warto  sumy s

i

 zale y od h

i

, warto ci funkcji G

i−

1:0

, P

i−

1:0

 oraz c

0

:  

)

(

0

0

:

1

0

:

1

c

P

G

h

c

h

s

i

i

i

i

i

i

−

−

+

⊕

=

⊕

=

 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

9 

Sumator z antycypacj  przeniesie  (carry look-ahead adder, 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

+

+

+

+

+

+

+

+

+

+

+

=

=

+

=

 

 

Uwaga

: Analogiczne zale no ci mo na poda  dla po yczek w odejmowaniu 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

10 

Moduł sumatora z antycypacj  przeniesie  (CLA) 

 

 

c

i

 

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

 

s

i

+3 

s

i

+2 

s

i

+1 

s

i

 

CLA

 

g

i

 

p

i

 

g

i

+3

 

p

i

+3

 

g

i

+2

 

p

i

+2

 

g

i

+1

 

p

i

+1

 

P

i

+4:i 

G

i

+4:i 

 

 

Czterobitowy sumator CLA z sygnałami G,P dla bloku CLG 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

11 

Wielomodułowy sumatorów z antycypacj  przeniesie  (CLA) 

 

c

0

 

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

 

y

3:0

x

3:0

 

CLA 

CLA 

CLA 

CLA 

 

Sumator zbudowany z kaskady bloków CLA 

 

 

GP

3:0

GP

7:4

GP

11:8

 

GP

15:12

c

0

 

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

 

y

3:0

x

3:0

 

CLA 

CLA 

CLA 

CLA 

CLG 

 

Sumator CLA z blokiem wytwarzania przeniesie  CLG 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

12 

Sumatory prefiksowe (PPA) 

sumator prefiksowy – parallel prefix adder, PPA 

blok GP – wytwarzanie warto ci wszystkich przeniesie  

0

0

:

1

0

:

1

c

P

G

c

i

i

i

−

−

+

=

 

)

(

0

0

:

1

0

:

1

c

P

G

h

c

h

s

i

i

i

i

i

i

−

−

+

⊕

=

⊕

=

 

 

 

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 

c

0

 

 

Je li c

0

=0, to c

i

=G

i

–1:0

 i wtedy  

0

:

1

−

⊕

=

⊕

=

i

i

i

i

i

G

h

c

h

s

, w przeciwnym razie 

problem: silne rozgał zienie sygnału przeniesienia wej ciowego c

0

 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

13 

Sumator prefiksowy z redukcj  rozgał zienia 

Aby unikn

 rozgał ziania sygnału c

0

 w obliczaniu 

0

0

:

1

0

:

1

c

P

G

c

i

i

i

−

−

+

=

 mo na: 

a) doł czy  blok wej ciowy CSA, redukuj cy sygnał c

0

 

c

wy

c

we

=

c

y

x

y



x



y



x



y



x



y

k





x

k





y

k





x

k





y

k





x

k





sumator PPA













































 

b) potraktować c

0

 jako funkcję generowania przeniesienia z pozycji „–1”:  

g

–1

= c

0

, zaś c

–1

= 0. Wtedy w sumatorze obejmującym n+1 pozycji mamy:  

)

(

1

:

0

1

:

1

1

:

1

1

:

1

−

−

−

−

−

+

⊕

=

⊕

=

⊕

=

G

P

G

h

G

h

c

h

s

i

i

i

i

i

i

i

i

 

co jest równowaŜne zastąpieniu sygnału g

0

 przez  

0

0

0

1

0

0

1

:

0

*

0

c

p

g

g

p

g

G

g

+

=

+

=

=

−

−

 

Tworzenie alternatywnego sygnału p

0

 jest zbędne, bo c

–1

= 0, więc 

*

0

1

g

c =

. 

W obu wersjach opóźnienie T jest takie jak w realizacji funkcji G

i

–1:0

+P

i

–1:0

 c

0

.  

 

Podobne rozwiązania moŜna zastosować w uniwersalnym sumatorze U2.  

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

14 

Zasady konstrukcji sieci prefiksowej GP 

Węzeł sieci GP realizuje funkcje  

)

,

(

)

,

(

)

,

(

)

,

(

L

H

L

H

H

L

L

H

H

HL

HL

P

P

G

P

G

P

G

P

G

P

G

+

=

•

=

 

Zasada konstrukcji struktury GP: 

integracja funkcji G

H

 i P

H

 oraz G

L

 i P

L

 obejmujących sąsiadujące bloki H i L: 

•  bloki H i L 

powinny być styczne 

 

•  bloki H i L 

nie mogą być rozdzielone

  

•  bloki H i L mogą mieć część wspólną – funkcje G

HL

 i P

HL

 są nadmiarowe 

 

 

 

 

 

 

 

integracja nadmiarowa 

integracja optymalna 

integracja błędna 

 

•  regularne struktury dla n = 2

k

 wejść (pozycji), 

•  w innych przypadkach przyjąć k = int (1+log

2

n

) i usunąć zbędne gałęzie 

(sieć integrującą 2

k

–1

 pozycji połączyć siecią integrującą pozostałe wejścia) 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

15 

Przekształcenie prefiksowe Ladnera-Fischera (Sklansky’ego)*  

minimalna liczba elementów 

 
 

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

1:0

 

(G

2i+1:2i

, P

2i+1:2i

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

3:0

, G

2:0

 

(G

4i+s:4i

, P

4i+s:4i

) = ( G

4i+s:4i+2

, P

4i+s:4i+2

) l ( G

4i+1:4i

, P

4i+1:4i

) 

 

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

− 3

n−

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

G

7:0

, …, G

4:0

 

(G

8i+s,8i

, P

8i+s,8i

) = ( G

8i+s,8i+4

, P

8i+s,8i+4

) l ( G

8i+3,8i

, P

8i+3,8i

) 

 

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

− 4

n−

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

G

15:0

, …, G

8:0

 

(G

16i+s,16i

, P

16i+s,16i

) = ( G

16i+s,16i+8

, P

16i+s,16i+8

) l ( G

16i+7,16i

, P

16i+7,16i

) 

… 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

16 

Przekształcenie prefiksowe Kogge-Stone’a*  

minimalizacja rozgał zie  

 

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

1:0

 

(G

i

+1:i

, P

i

+1:i

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

s

+2:0

= G

s

+2,s+1

+ P

s

+2,s+1

G

s

:0 

( G

3:0

) , G

2:0

 

(G

i

+3:i

, P

i

+3:i

) = ( G

i

+3,i+2

, P

i

+3,i+2

)l (G

i,i

+1

, P

i,i

+1

)   

G

3:0

 

 

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

2

−1;  i = 0, 1, … , n−2

3

) 

G

s

+4:0

= G

s

+1,s+4

+ P

s

+1,s+4

G

s

:0

 

(G

7:0

) , G

6:0

, G

5:0

, G

4:0

 

(G

i

+7:i

, P

i

+7:i

) = ( G

i

+7,i+4

, P

i

+7,i+4

)l (G

i

+3:i

, P

i

+3:i

)   

G

7:0

 

 

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

3

−1;  i = 0, 1, … , n−2

4

) 

G

s

+8:0

= G

s

+8,s+1

+ P

s

+8,s+1

G

s

:0

 

(G

15:0

) , … …, G

8:0

 

(G

i

+15:i

, P

i

+15:i

) = ( G

i

+15,i+8

, P

i

+15,i+8

)l (G

i

+7:i

, P

i

+7:i

)   

G

15:0

 

… 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

17 

Przekształcenie prefiksowe Brenta-Kunga* 

optymalizacja struktury CMOS 

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

1:0

 

(G

2i+1:2i

, P

2i+1:2i

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

3:0

 

(G

4i+3:4i

, P

4i+3:4i

) = ( G

4i+3:4i+2

, P

4i+3:4i+2

) l ( G

4i+1:4i

, P

4i+1:4i

) 

 

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

− 3

n−

1)  

G

7:0

 

(G

8i+7:8i

, P

8i+7:8i

) = ( G

8i+7:8i+4

, P

8i+7:8i+4

) l ( G

8i+3:8i

, P

8i+3:8i

) 

… 

Poziom m = log

2

n

 (T = 2

m−

2

) 

(G

3T−1:0

, P

3T−1:0

) = ( G

3T −1:2T

, P

3T −1:2T

)l (G

2T −1:0

, P

2T −1:0

)  

G

3T:0

 

(G

0,n−1:0

, P

n−

1:0

) = ( G

n−

1:2T

, P

n−

1:2T

)l (G

2T −1:0

, P

2T −1:0

)  

G

n −

1:0

 

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

2

−1, R = 2

m−

2−s

),  r = 1, … , m−2  

(G

iR−

1:0

, P

iR−

1:0

) = ( G

iR−

1: 2R 

, P

iR−

1: 2R

)l (G

2R −1:0

, P

2R −1:0

)  

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

18 

Przekształcenie prefiksowe Han’a-Carlsona*  

najpierw integracja rozł cznych par 

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

1:0

 

(G

2i+1:2i

, P

2i+1:2i

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

3:0

 

(G

2i+3:2i

, P

2i+3:2i

) = ( G

2i+3:2i+2

, P

2i+3:2i+2

) l ( G

2i+1:2i

, P

2i+1:2i

) 

 

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

− 3

n−

1,  s = 0, 1)  

(G

2i+7:2i

, P

2i+7:2i

) = ( G

2i+7:2i+4

, P

2i+7:2i+4

) l ( G

2i+3:2i

, P

2i+3:2i

) 

G

2s+5:0

= G

2s+5,2s+1

+ P

2s+5,2s+1

G

2s:0  

G

7:0

, G

5:0

 

 

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

2

−1;  i = 0, 1, … , 2

− 3

n−

1) 

(G

2i+15:2i

, P

2i+15:2i

) = ( G

2i+15:2i+8

, P

2i+15:2i+8

) l ( G

2i+7:2i

, P

2i+7:2i

) 

G

2s+9:0

= G

2s+9,2s+1

+ P

2s+9,2s+1

G

2s:0  

G

15:0

, G

13:0

, G

11:0

, G

9:0

 

 

... 
Poziom log

2

n

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

− 1

n−

1) 

G

2i:0

= G

2i:2i

+ P

2i:2i

G

2i−1:0

 

G

2i:0

, … , G

4:0

, G

2:0

 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

21 

Sumator ELM – koncepcja* 

Obliczona wartość początkowa sumy h

i

= s

i:i

 na moŜe ulec zmianie, jeśli c

i

=1.  

Niech s

i:r

 oznacza tymczasow  sumę na pozycji i z uwzględnieniem wszystkich 

wcześniejszych wejść x

#

, y

#

, począwszy od wejścia x

r

, y

r

. Mamy:  

)

(

,

0

0

:

1

0

:

1

0

:

:

1

:

c

H

G

h

s

G

h

s

i

i

i

i

r

i

i

r

i

−

−

−

+

⊕

=

⊕

=

 

Z rekurencyjnego powiązania funkcji G

i:j

 wynika dalej, Ŝe (i>r>j):  

,

))

(

(

)

(

:

1

:

1

:

1

:

:

1

:

1

:

1

:

1

:

:

1

:

1

:

1

:

1

:

1

:

1

:

j

r

r

i

r

i

r

i

j

r

r

i

r

i

r

i

r

i

j

r

r

i

r

i

r

i

r

i

i

j

i

i

j

i

G

H

G

s

G

H

G

G

s

G

H

G

G

G

h

G

h

s

−

−

−

−

−

−

−

−

−

−

−

−

−

⊕

=

+

⊕

⊕

=

=

+

⊕

⊕

⊕

=

⊕

=

 

Metodą indukcji moŜna pokazać, Ŝe 

j

i

j

i

j

i

i

j

i

j

i

H

H

G

h

H

G

:

:

1

:

1

:

:

=

=

−

−

, skąd mamy: 

.

,

:

1

:

1

:

:

:

1

:

j

r

r

i

r

i

j

i

r

i

i

r

i

G

H

s

s

G

h

s

−

−

−

⊕

=

⊕

=

 

przy tym bitami końcowej sumy są s

i

=s

i

:0

. 

 
PoniewaŜ powyŜsze funkcje są niezaleŜne, więc moŜliwe jest wytworzenie 
sumy końcowej w strukturze zawierającej log

2

n

 poziomów. 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

22 

Sumator ELM – korekcja sum tymczasowych* 

Z podanych zaleŜności wynika zasada konstrukcji sumatora, podobna jak PPA 
 

 

 s

6

 

 s

5

 

 s

4

  

 s

3

 

 s

2

 

 s

1

  

 s

0

  

 s

7

  

s

k

+1:i

  

 x

7

       y

7

 

g

7

    h

7

  

GP

k

:j+1

  GP

j

:i

 

3 

2 

1 

GP

k

:i

 

s

k

+1:j

   GH

j

–1:i

 

 x

6

       y

6

 

g

6

    h

6

  

 x

5

       y

5

 

g

5

    h

5

  

 x

4

       y

4

 

g

4

    h

4

  

 x

3

       y

3

 

g

3

    h

3

  

 x

2

       y

2

 

g

2

    h

2

  

 x

1

       y

1

 

g

1

    h

1

  

 x

0

       y

0

 

g

0

    h

0

  

 c

8

 

 

 

Schemat sumatora ELM (strukturze Ladnera-Fischera) 

 
Powiązania sum moŜna takŜe zrealizować w strukturze Kogge’a-Stone’a. 

 

 

Szybkie sumatory 

© Janusz Biernat

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

23 

Sumy warunkowe – koncepcja (Sklansky) 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

24 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

25 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

26 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

27 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

28 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

29 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

30 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

31 

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

, AK1-7-09 Szybkie sumatory.doc, 4 listopada 2009

 

 

FAST–

32 

Szybkość działania i złoŜoność sumatorów 

Charakterystyki AT  

•  sumator pełny 1-bitowy 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 kaskadowy 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 PPA – A

≈

5n+3n log n , T

≈

3 + 2 log n →  A T

≈

3n log

2

n

+14n log n 

– log n poziomów GP, opóźnienie przeniesienia  2 log n 

•  sumator COSA – A = 3n log n, T = 2 + 2 log n →  A T

≈

6 n log

2

n

 

– 2×RCA, log n poziomów MPX, opóźnienie przeniesienia 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