AK1-7-09 Szybkie sumatory.pdf

(515 KB) Pobierz

Microsoft Word - AK1-7-09 Szybkie sumatory.doc

Szybkie sumatory

Algorytm dodawania i odejmowania

x k −1

y k −1

x k −2

y k −2

x 1

y 1

x 0

y 0

c k

FA/FS

c k −1

FA/FS

c k −2

c 2

FA/FS

c 1

FA/FS

c 0

s k −1

s k −2

s 1

s 0

Schemat dodawania/odejmowania binarnego

dodawanie (X+Y)

odejmowanie (X–Y)

s

i

=

x

i

Å

y

i

Å

c

i

s

i

=

x

i

Å

y

i

Å

c

i

c

i

+

1

=

x

i

y

i

+

(

x

i

Å

y

i

)

c

i

c

i

+

1

=

x

i

y

i

+

(

x

i

Å

y

i

)

c

i

=

x

i

y

i

+

(

x

i

+

y

i

)

c

i

=

x

i

y

i

+

(

x

i

Å

y

i

)

c

i

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

© Janusz Biernat , AK1-7-09 Szybkie sumatory.doc, 23 wrze

nia 2009

FAST– 1

321134713.088.png

321134713.099.png

321134713.110.png

321134713.121.png

321134713.001.png

321134713.012.png

321134713.023.png

321134713.034.png

321134713.042.png

321134713.043.png

321134713.044.png

321134713.045.png

321134713.046.png

321134713.047.png

321134713.048.png

321134713.049.png

321134713.050.png

321134713.051.png

321134713.052.png

321134713.053.png

321134713.054.png

321134713.055.png

321134713.056.png

321134713.057.png

321134713.058.png

321134713.059.png

321134713.060.png

321134713.061.png

321134713.062.png

321134713.063.png

321134713.064.png

321134713.065.png

321134713.066.png

321134713.067.png

321134713.068.png

321134713.069.png

321134713.070.png

321134713.071.png

321134713.072.png

321134713.073.png

321134713.074.png

Szybkie sumatory

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

© Janusz Biernat , AK1-7-09 Szybkie sumatory.doc, 23 wrze

nia 2009

FAST– 2

321134713.075.png

321134713.076.png

Szybkie sumatory

Wytwarzanie i propagacja przeniesie w dodawaniu

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

c

+

1

=

x

y

i

+

(

x

i

Å

y

i

)

c

i

=

x

i

y

i

+

(

x

i

+

y

i

)

c

i

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 :

g =

i

x

i

y

i

,

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

przeniesienia (

x ¹ ⇒

i

y

i

c =

i

+1

c

i

):

h

i

=

x

i

Å

y

i

W wyra eniach na przeniesienie mo e j zast pi

• (nadmiarowa) funkcja przekazywania przeniesienia (

p – f. wygaszania)

p

i

=

x

i

+

y

i

UWAGA:

W wyra eniach na przeniesienie funkcje p # i h # s wzajemnie zamienne.

© Janusz Biernat , AK1-7-09 Szybkie sumatory.doc, 23 wrze

nia 2009

FAST– 3

i

i

321134713.077.png

321134713.078.png

321134713.079.png

Szybkie sumatory

Wytwarzanie i propagacja przeniesie w odejmowaniu

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

c

i

+

1

=

x

i

y

i

+

(

x

i

Å

y

i

)

c

i

=

x

i

y

i

+

(

x

i

+

y

i

)

c

i

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 :

g =

i

x

i

y

i

,

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

propagacji ) po yczki (

x = ⇒

i

y

i

c =

i

+1

c

i

):

h

i

=

x

i

Å

y

i

W wyra eniach na po yczki mo e j zast pi

• (nadmiarowa) funkcja przekazywania po yczki (

p – f. wygaszania)

p

i

=

x

i

+

y

i

UWAGA:

W wyra eniach na po yczki funkcje p # i h # s wzajemnie zamienne.

© Janusz Biernat , AK1-7-09 Szybkie sumatory.doc, 23 wrze

nia 2009

FAST– 4

321134713.080.png

321134713.081.png

321134713.082.png

Szybkie sumatory

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

© Janusz Biernat , AK1-7-09 Szybkie sumatory.doc, 23 wrze

nia 2009

FAST– 5

321134713.083.png

321134713.084.png

321134713.085.png

321134713.086.png

321134713.087.png

321134713.089.png

321134713.090.png

321134713.091.png

321134713.092.png

321134713.093.png

321134713.094.png

321134713.095.png

321134713.096.png

321134713.097.png

321134713.098.png

321134713.100.png

321134713.101.png

321134713.102.png

321134713.103.png

321134713.104.png

321134713.105.png

321134713.106.png

321134713.107.png

321134713.108.png

321134713.109.png

321134713.111.png

321134713.112.png

321134713.113.png

321134713.114.png

321134713.115.png

321134713.116.png

321134713.117.png

321134713.118.png

321134713.119.png

321134713.120.png

321134713.122.png

321134713.123.png

321134713.124.png

321134713.125.png

321134713.126.png

321134713.127.png

321134713.128.png

321134713.129.png

321134713.130.png

321134713.131.png

321134713.002.png

321134713.003.png

321134713.004.png

321134713.005.png

321134713.006.png

321134713.007.png

321134713.008.png

321134713.009.png

321134713.010.png

321134713.011.png

321134713.013.png

321134713.014.png

321134713.015.png

321134713.016.png

321134713.017.png

321134713.018.png

321134713.019.png

321134713.020.png

321134713.021.png

321134713.022.png

321134713.024.png

321134713.025.png

321134713.026.png

321134713.027.png

321134713.028.png

321134713.029.png

321134713.030.png

321134713.031.png

321134713.032.png

321134713.033.png

321134713.035.png

321134713.036.png

321134713.037.png

321134713.038.png

321134713.039.png

321134713.040.png

321134713.041.png

Plik z chomika:

Inne pliki z tego folderu:

AK1-8-09-Sumatory CSA i multyplikatory.pdf (432 KB)
AK1-7-09 Szybkie sumatory.pdf (515 KB)
AK1-6-09-FP-2 + NUM.pdf (659 KB)
AK1-5-09-Systemy resztowe.pdf (319 KB)
AK1-4-09-Dzielenie.pdf (518 KB)

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin