curs_cid_7.pdf
Post on 20-Dec-2015
8 Views
Preview:
TRANSCRIPT
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
Circuite şi Sisteme Digitale cursul 7 3Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 4Zoltan Hascsi
Semisumatorul (half adder - HA)
• {c,s} = a + b c – carry (transport); s – sum (sumă)
ATENŢIE!sumă aritmetică
Circuite şi Sisteme Digitale cursul 7 5Zoltan Hascsi
Semisumatorul (half adder - HA)
• {c,s} = a + b c – carry (transport); s – sum (sumă)
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)
Circuite şi Sisteme Digitale cursul 7 6Zoltan Hascsi
Semisumatorul (half adder - HA)
• {c,s} = a + b c – carry (transport); s – sum (sumă)
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
Circuite şi Sisteme Digitale cursul 7 7Zoltan Hascsi
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)
Circuite şi Sisteme Digitale cursul 7 8Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 9Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 10Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 11Zoltan Hascsi
Transport
generare propagare
ci+1 = ai·bi + (ai ⊕ bi)·ci
a bcic
s
ai bi
ci+1 ci
Circuite şi Sisteme Digitale cursul 7 12Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 13Zoltan Hascsi
Sumator rapid de 4 biţi
a3 a2 a1 a0b3 b2 b1 b0
ci
c
s3 s2 s1 s0
Circuite şi Sisteme Digitale cursul 7 14Zoltan Hascsi
Sumator simplu de 4 biţi
ci
c
a3 a2 a1 a0b3 b2 b1 b0
s3 s2 s1 s0
Circuite şi Sisteme Digitale cursul 7 15Zoltan Hascsi
Sumator rapid de 4 biţi
a3 a2 a1 a0b3 b2 b1 b0
ci
c
s3 s2 s1 s0
Circuite şi Sisteme Digitale cursul 7 16Zoltan Hascsi
Sumator simplu de 4 biţi
ci
c
a3 a2 a1 a0b3 b2 b1 b0
s3 s2 s1 s0
Circuite şi Sisteme Digitale cursul 7 17Zoltan Hascsi
• Sumatorul• Metrici de circuit• Comparatorul• Circuitul de deplasare• Înmulţitorul
Circuite şi Sisteme Digitale cursul 7 18Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 19Zoltan Hascsi
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.
Circuite şi Sisteme Digitale cursul 7 20Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 21Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 22Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 23Zoltan Hascsi
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.
Circuite şi Sisteme Digitale cursul 7 24Zoltan Hascsi
Metrici – fan-in
ripple carry adderFImax = 2
carry lookahead adderFImax = 5
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
Circuite şi Sisteme Digitale cursul 7 25Zoltan Hascsi
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.
Circuite şi Sisteme Digitale cursul 7 26Zoltan Hascsi
Metrici – fan-out
ripple carry adderFOmax = 2
carry lookahead adderFOmax = 7
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
Circuite şi Sisteme Digitale cursul 7 27Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 28Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 29Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 30Zoltan Hascsi
• Sumatorul• Metrici de circuit• Comparatorul• Circuitul de deplasare• Înmulţitorul
Circuite şi Sisteme Digitale cursul 7 31Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 32Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 33Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 34Zoltan Hascsi
• Sumatorul• Metrici de circuit• Comparatorul• Circuitul de deplasare• Înmulţitorul
Circuite şi Sisteme Digitale cursul 7 35Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 36Zoltan Hascsi
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
Circuite şi Sisteme Digitale cursul 7 37Zoltan Hascsi
Circuitul de deplasare
• 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
Circuite şi Sisteme Digitale cursul 7 38Zoltan Hascsi
Circuitul de deplasare
• 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
Circuite şi Sisteme Digitale cursul 7 39Zoltan Hascsi
Circuitul de deplasare
• 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
Circuite şi Sisteme Digitale cursul 7 40Zoltan Hascsi
Circuitul de deplasare
• 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
Circuite şi Sisteme Digitale cursul 7 41Zoltan Hascsi
Circuitul de deplasare
• 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
Circuite şi Sisteme Digitale cursul 7 42Zoltan Hascsi
Circuitul de deplasare
• 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]
Circuite şi Sisteme Digitale cursul 7 43Zoltan Hascsi
Circuitul de deplasare
• 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
Circuite şi Sisteme Digitale cursul 7 44Zoltan Hascsi
Circuitul de deplasare
• 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
Circuite şi Sisteme Digitale cursul 7 45Zoltan Hascsi
Circuitul de deplasare
• 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
Circuite şi Sisteme Digitale cursul 7 46Zoltan Hascsi
Circuitul de deplasare
• 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
Circuite şi Sisteme Digitale cursul 7 47Zoltan Hascsi
Barrel shifter
`
Circuite şi Sisteme Digitale cursul 7 48Zoltan Hascsi
Barrel shifter
`
Circuite şi Sisteme Digitale cursul 7 49Zoltan Hascsi
• Sumatorul• Metrici de circuit• Comparatorul• Circuitul de deplasare• Înmulţitorul
Circuite şi Sisteme Digitale cursul 7 50Zoltan Hascsi
Î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
Circuite şi Sisteme Digitale cursul 7 51Zoltan Hascsi
Î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
Circuite şi Sisteme Digitale cursul 7 52Zoltan Hascsi
Î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
Circuite şi Sisteme Digitale cursul 7 53Zoltan Hascsi
Î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
Circuite şi Sisteme Digitale cursul 7 54Zoltan Hascsi
Î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
Circuite şi Sisteme Digitale cursul 7 55Zoltan Hascsi
Î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
Circuite şi Sisteme Digitale cursul 7 56Zoltan Hascsi
Î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
Circuite şi Sisteme Digitale cursul 7 57Zoltan Hascsi
Î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
top related