curs_cid_7.pdf

Zoltan Hascsi

Circuite şi Sisteme Digitale

– cursul 7 –

Circuite combinaţionale complexe

Circuite şi Sisteme Digitale cursul 7 2Zoltan Hascsi

• Sumatorul• Metrici de circuit• Comparatorul• Circuitul de deplasare• Înmulţitorul


Adunarea

• Baza de numeraţie:– sumator binar– sumator zecimal (în cod BCD etc.)

• Reprezentarea numerelor– cu semn şi modul– în complement faţă 2

• Adunarea se face de regulă în binar pentru numere reprezentate în complement faţă de 2

1 0 1 0 1 1 0 10 1 1 0 0 1 1 1

0

1

0

1

0

1

1

0

0

1

1

1

0

1

0

1• Algoritmul clasic de adunare adună mai întâi biţii LSB, apoi cei de rang imediat superior ş.a.m.d.

ab

s


Semisumatorul (half adder - HA)

• {c,s} = a + b c – carry (transport); s – sum (sumă)

ATENŢIE!sumă aritmetică




a0 0 0 00 1 0 11 0 0 1 1 1 1 0

b c s

c = a·bs = a·b + a·b = a ⊕ b

ATENŢIE!sumă logică

(SAU)




a b

HA

c s

a0 0 0 00 1 0 11 0 0 1 1 1 1 0

b c s

c s

a b

c = a·bs = a·b + a·b = a ⊕ b


Sumatorul complet (full adder - FA)

• {c,s} = a + b + ci

a0 0 0 0 00 0 1 0 10 1 0 0 1 0 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1

b c sci

a b

FAc ci

s

c = a·b + a·ci + b·ci = a·b + (a ⊕ b)·ci

s = a ⊕ b ⊕ ci

a b

HA

HA

s

ci

c

c s

s

c

ci – carry in (transportul de la bitul de rang inferior)


Sumatorul de n biţi

• S = A + B + c0

• Cea mai simplă implementare corespunde algoritmului clasic de adunare: legarea în cascadă a sumatoarelor complete de 1 bit: sumator cu propagarea transportului.

• {ci+1,si} = ai + bi + ci

an-1 bn-1 a1 b1 a0 b0

a bcic

s

a bcic

s

a bcic

s

s1 s0

cn-1 c2 c1cn c0

sn-1


Sumatorul de 4 biţi

wire [3:0] a,b,s;wire c_in, c;assign {c,s} = a + b + c_in;

a3 b3 a2 b2 a1 b1 a0 b0

a bcic

s

a bcic

s

a bcic

s

a bcic

s

s3 s2 s1 s0

c3 c2 c1c4 c0


Propagarea transportului

• ripple = val• Transportul dinspre LSB poate afecta suma biţilor MSB!• Întârzierea sumatorului cu propagarea transportului este

proporţională cu numărul de sumatoare legate în cascadă: Tpp ~ n

a3 b3 a2 b2 a1 b1 a0 b0

a bcic

s

a bcic

s

a bcic

s

a bcic

s

s3 s2 s1 s0

c3 c2 c1c4 c0


Transport

generare propagare

ci+1 = ai·bi + (ai ⊕ bi)·ci

a bcic

s

ai bi

ci+1 ci


ci+1 = ai·bi + (ai ⊕ bi)·ci

ci+1 = Gi + Pi·ci

generare: Gi = ai·bi

propagare: Pi = ai ⊕ bi

• c1 = G0 + P0ci

• c2 = G1 + P1c1

• c3 = G2 + P2c2

• c4 = G3 + P3c3

Transport

a bcic

s

ai bi

si

ci+1 ci

= G1 + P1G0 + P1P0ci

= G2 + P2G1 + P2P1G0 + P2P1P0ci

= G3 + P3G2 + P3P2G1 + P3P2P1G0 ++ P3P2P1P0ci


Sumator rapid de 4 biţi

a3 a2 a1 a0b3 b2 b1 b0

ci

c

s3 s2 s1 s0


Sumator simplu de 4 biţi

ci

c

a3 a2 a1 a0b3 b2 b1 b0

s3 s2 s1 s0


Sumator rapid de 4 biţi

a3 a2 a1 a0b3 b2 b1 b0

ci

c

s3 s2 s1 s0


Sumator simplu de 4 biţi

ci

c

a3 a2 a1 a0b3 b2 b1 b0

s3 s2 s1 s0


Metrici

• Metricile cele mai folosite în evaluarea parametrilor circuitelor logice:– mărimea circuitului arie/cost/putere– adâncimea circuitului viteză– fan-in-ul porţilor logice utilizate biblioteca de porţi– fan-out-ul arie/cost/curent


Metrici - size

• Size – mărime• Este numărul de porţi logice ale circuitului.• Aria ocupată de circuit este corelată cu numărul de porţi.• Pentru o estimare mai bună a ariei trebuie folosite porţi

logice de acelaşi fel (NAND şi NOR cu 2 intrări), sau redefinit parametrul size ca sumă a fan-in-urilor tuturor porţilor logice.


Metrici - size

ripple carry adderS = 20S = 40

carry lookahead adderS = 26S = 68

nr. porţi

nr. porţi × nr intrări

a3 b3 a2 b2 a1 b1 a0 b0a3 b3 a2 b2 a1 b1 a0 b0

ci

c

s3 s2 s1 s0

ci

c

s3 s2 s1 s0


Metrici - depth

• Depth – adâncime• Este lungimea celei mai lungi căi de la intrare la ieşire,

exprimată în număr de porţi logice parcurse.• Estimează întârzierea circuitului, sau timpul de

propagare pe calea cea mai lentă.• Pentru a compara lungimea diferitelor căi, porţile logice

trebuie să fie (aproape) identice ca întârziere.• Dacă porţile logice au o întârziere tP şi adâncimea

circuitului este D, timpul de propagare estimat pentru întreg circuitul este aproximativ:

D · tP


Metrici - depth

ripple carry adderD = 9

carry lookahead adderD = 4

ci

a3 b3 a2 b2 a1 b1 a0 b0

c

s3 s2 s1 s0

ci

c

s3 s2 s1 s0

a3 b3 a2 b2 a1 b1 a0 b0


Metrici – fan-in

• Fan-in• Numărul de intrări ale porţii logice.• Porţile logice MOS au un număr de tranzistoare şi o arie

proporţionale cu numărul de intrări. Numărul maxim de intrări este limitat (la 4 – 8) pe considerente electrice şi de tehnologie.

• Porţile logice care necesită fan-in mare sunt descompuse într-o reţea de porţi cu fan-in mai mic.


Metrici – fan-in

ripple carry adderFImax = 2

carry lookahead adderFImax = 5


ci

c

s3 s2 s1 s0

ci

c

s3 s2 s1 s0


Metrici – fan-out

• Fan-out• Numărul de (intrări de) porţi logice conectate la ieşirea

unei porţi.• Este o estimare a încărcării capacitive a ieşirii porţii.• O estimare mai precisă trebuie să ţină cont şi de traseele

prin care sunt conectate acele porţi.• Dacă fiecare intrare comandată contribuie cu o

capacitate Cp şi fan-out-ul porţii este F, încărcarea capacitivă a ieşirii este aproximativ:

F · Cp

• Pentru a nu afecta timpul de propagare al porţii, aceasta se dimensionează pentru curenţi de sarcină mai mari.


Metrici – fan-out

ripple carry adderFOmax = 2

carry lookahead adderFOmax = 7


ci

c

s3 s2 s1 s0

ci

c

s3 s2 s1 s0


Compromisul arie-viteză

• Circuitele structurate sunt lente– minimizarea globală presupune mai multe nivele de porţi logice

• Circuitele rapide sunt mari:– fiecare funcţie minimizată separat → multe porţi logice– fan-in mare → porţi logice mari– fan-out mare → tranzistoare mari capabile să suporte curenţi

mari


ScăzătorA B• A – B = A + (-B) = A + B + 1

• Adunarea cu 1 nu necesită un sumator separat – se foloseste intrarea de transport! A

SB ci 1

• Sumatorul binar în complement faţă de doi poate fi folosit atât pentru adunări cât şi pentru scăderi.

• C, intrare de control:C = 0 → S = A + BC = 1 → S = A - B

A B

AS

B ci

C


ScăzătorA B• A – B = A + (-B) = A + B + 1

• Adunarea cu 1 nu necesită un sumator separat – se foloseste intrarea de transport! A

SB ci 1

AS

B ci

A B

• Sumatorul binar în complement faţă de doi poate fi folosit atât pentru adunări cât şi pentru scăderi.

• C, intrare de control:C = 0 → S = A + BC = 1 → S = A - B

Cinversor comandat

B ⊕ 0 = BB ⊕ 1 = B


Algoritmul de comparare

• Algoritmul clasic comparănumerele bit cu bit, începând cu bitul cel mai semnificativ şi se încheie fie când s-a găsit o poziţie în care biţii numerelor diferă (inegalitate), fie după ce s-au comparat toţi biţii.

00

a 1 1 0 1 1 0 1a > b

0 1 0b 0 1 1 1

0 1 0 00 1 1 0

a 1 1 0 1a < b

b 0 1 1 1

0 0 1 0 1 1 0 10 0 1 0 1 1 0 1

aa = b

b


Comparatorul de un bit

g = a > b g: greater thane = a == b e: equall = a < b l: less than

a0 0 0 1 00 1 0 0 11 0 1 0 01 1 0 1 0

b g e l

g = a·be = a·b + a·b = a ⊕ bl = a·b


Comparatorul de 4 biţi

• Algoritmul clasic de comparare începe cu biţii cei mai semnificativi.

a3 b3 a2 b2 a1 b1 a0 b0

a b a b a b a b


Deplasarea - shift

• deplasare la stânga

• biţii semnificativi se pierd!

• rotire

• deplasare la dreapta

• deplasare aritmetică la dreapta

0 0 0 1 0 1 1 10 1 0 1 1 1 0 0

1 1 1 0 0 1 0 1

0 0 0 1 0 1 1 10 1 1 1 0 0 0 0

0 0 0 1 0 1 1 10 0 0 0 0 1 0 1

0 0 0 1 0 1 1 10 1 1 1 0 0 0 1

1 0 0 1 0 1 1 1

bit de semn clonat


Circuitul de deplasare

• S = 0 transfer y = x

x7 x6 x5 x4 x3 x2 x1 x0

y7 y6 y5 y4 y3 y2 y1 y0

s



• S = 0 transfer y = x• S = 1 deplasare stânga cu un bit y = x << 1

x7 x6 x5 x4 x3 x2 x1 x0

0s

y7 y6 y5 y4 y3 y2 y1 y0



• S = 0 transfer y = x• S = 1 deplasare stânga cu un bit y = x << 1• S = 2 deplasare stânga cu 2 biţi y = x << 2

x7 x6 x5 x4 x3 x2 x1 x0

00

y7 y6 y5 y4 y3 y2 y1

s

y0



• S = 0 transfer y = x• S = 1 deplasare stânga cu un bit y = x << 1• S = 2 deplasare stânga cu 2 biţi y = x << 2• S = 3 deplasare stânga cu 3 biţi y = x << 3• ş.a.m.d y = x << S

x7 x6 x5 x4 x3 x2 x1 x0

000

y7 y6 y5 y4 y3 y2 y1

s

y0



• S = 0 transfer y = x• S = 1 deplasare stânga cu un bit y = x << 1• S = 2 deplasare stânga cu 2 biţi y = x << 2• S = 3 deplasare stânga cu 3 biţi y = x << 3• ş.a.m.d y = x << S

0s 0 0 0 0 0 0 0 0



• rotirea se obţine aducând biţii cei mai semnificativi pe intrările corespunzătoare ale multiplexoarelor biţilor cei mai puţin semnificativi.

• selecţie paralelă → multiplexoarele au decodorul comun

s

DE

C 3

:8

0



• circuit de deplasare logaritmic cu MUX 2:1• y = x · 2S = x · 24·S[2]+2·S[1]+S[0] = x · 24·S[2] · 22·S[1] · 2S[0]

• y = ((x · 2S[0]) · 22·S[1]) · 24·S[2]

• numărul de niveluri egal cu logaritmul deplasării maxime

0s[0]

0s[1]

0s[2]



• S = 0 transfer

00

0

00 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0

0



• S = 1 deplasare stânga cu un bit

0

00

00

1

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

LSB



• S = 2 deplasare stânga cu 2 biţi

00

0

00 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 11

0



• S = 6 deplasare stânga cu 6 biţi

0

0

0

1

0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

0

1

1 1 1 1 1 1 1 1

MSB


Barrel shifter

`


Înmulţirea

A · B = A · (2n-1 · bn-1 + ... + 21 · b1 + 20 · b0)

= A · 2n-1 · bn-1 + ... + A · 21 · b1 + A · 20 · b0

• Tabla înmulţirii bit cu bit:

a0 0 00 1 01 0 0 1 1 1

b a·bA1 1 0 1

1 0 1 11 1 0 11 1 0 11 1 0 1

B1 1 0 1

1 1 0 10 0 0 0

1 1 0 1• Înmulţirea unui număr cu un bit:

b = 0 → A · 0 = 0b = 1 → A · 1 = A

A·B1 0 0 0 1 1 1 1


Înmulţitor

A · B = (A · 2n-1 )· bn-1 + ... + (A · 21)· b1 + (A · 20 )· b0

B

b0 b1 b2 bn-2 bn-1

A

A·BAD

D

AD

D

AD

D

AD

D

n n+1 n+2 n+3 2n-1

SH

L

SH

L

SH

L

2n-1 2n

SH

L

n+2 n+3


Înmulţitor

• prin asociativitate: A · 2n+i = (A · 2n+i-1 ) · 2• se deplasează cu un bit la stânga (înmulţire cu 2)

rezultatul deplasării din etapa anterioară.

bn+i

AD

D n+i+1

n+i

SH

L

n+i

n+i-1

• circuitul de deplasare este este o simplă conexiune între intrare şi ieşire.

x0x1

xn+i-2

y0y1y2

yn+i-2yn+i-1

xn+i-3

0


Înmulţitor

• b = 0 → Y = X · 0 = 0• b = 1 → Y = X · 1 = X

bn+i

AD

D n+i+1

n+i

SH

L

n+i

n+i-1

yn+i-1y2y1y0

x2x1x0 x2n+i-1

bn+i


Înmulţitor

• b = 0 → Y = X · 0 = 0• b = 1 → Y = X · 1 = X

bn+i

AD

D n+i+1

n+i

SH

L

n+i

n+i-1

• Pentru biţii cei mai puţin semnificativi care în urma deplasării deînmulţitului vor fi 0 poarta ŞI nu e necesară.

yn+i-1y2y1y0

x2x1 x2n+i-1

bn+i

0


Înmulţitor

• Adunarea a două numere de n+i biţi poate produce rezultate de n+i+1 biţi.

• Transportul de la ieşirea sumatorului este cel mai semnificativ bit al sumei.

bn+i

AD

D n+i+1

n+i

SH

L

n+i

n+i-1

• Toate numerele sunt în complement faţă de 2.

y2y1

x2s0

c

s1s2

sn+i-1

y0

yn+i-1

y2

y1

yn+i

n+i

n+i

B

A


Înmulţitor

• Adunarea în cascadă a produselor parţiale este lentă.• Adâncimea şi timpul de propagare sunt proporţionale cu

numărul de biţi al înmulţitorului.

b0 b1 b2 bn-2 bn-1

A

A·BAD

D

AD

D

AD

D

AD

D

n n+1 n+2 n+3 2n-1

SH

L

SH

L

SH

L

2n-1 2n

SH

L

n+2 n+3


Înmulţitor mai rapid

• Adunarea produselor parţiale se poate face în paralel, folosind un arbore de sumatoare, având o adâncime proporţionala cu logaritmul numărului de biţi, log2n:

ADD ADD

ADD

ADD ADD

ADD

ADD

curs_cid_7.pdf

Documents