Dan NICULA
ELECTRONIC
˘
A DIGITAL
˘
A
Carte de ˆınat¸˘atur˘a 2.0
Editura Universit˘at¸ii TRANSILVANIA din Bra¸sov
ISBN 978-606-19-0563-8
2015
Lect¸ia 7
Sinteza circuitelor logice combinat¸ionale
7.1 Not¸iuni teoretice
Orice circuit logic combinat¸ional poate implementat cu port¸i NAND pe dou˘a nivele logice.
Metodologia de implementare const˘a ˆın parcurgerea urm˘atoarelor etape:
Se reprezina funct¸ia ˆın diagram˘a V-K.
Se minimizeaz˘a funct¸ia sub form˘a de sum˘a de produse (SOP).
Fiecare produs (AND) se implementeaz˘a cu o poart˘a NAND, cu un num˘ar de intr˘ari egal cu num˘arul de termeni
ˆın produs. La intrarea port¸ilor se aplic˘a variabilele de intrare, negate sau ne-negate. Aceste port¸i reprezina
primul nivel de port¸i NAND.
Suma (OR) se implementeaz˘a cu o poart˘a NAND cu un num˘ar de intr˘ari egal cu num˘arul de produse din sum˘a.
La intr˘arile port¸ii se aplic˘a ie¸sirile port¸ilor NAND ale primului nivel logic. Aceast˘a poart˘a reprezint˘a al doilea
nivel de port¸i NAND.
Ca exemplu, funct¸ia F (A, B, C) =
(1, 3, 6, 7) se minimizeaz˘a sub forma F (A, B, C) = A· B +A· C. Implementarea
direct˘a (cu port¸i AND ¸si OR) ¸si transformarea ˆıntr-o structur˘a pe dou˘a nivele de port¸i NAND sunt prezentate ˆın figura
7.1.
Justificarea analitic˘a este:
F (A, B, C) = A · B + A · C = A · B + A · C = A · B · A · C
Figura 7.1 Funct¸ie logic˘a: implementare AND-OR, implementare NAND-NAND.
7.2 Pentru cei ce vor doar a promoveze examenul
1. Minimizat¸i funct¸iile logice ¸si implementat¸i-le cu port¸i NAND pe dou˘a nivele logice.
88 LECT¸ IA 7. Sinteza circuitelor logice combinat¸ionale
a) F
a
=
(3, 5, 6, 7)
b) F
b
=
(0, 2, 4, 6, 7)
c) F
c
=
(0, 4, 6, 7, 8, 14, 15)
d) F
d
=
(3, 7, 9, 10, 11, 15)
e) F
e
=
(0, 2, 6, 8, 10, 13)
2. Proiectat¸i un circuit de ”vot majoritar” cu 3 intr˘ari ¸si implementat¸i-l cu port¸i NAND pe dou˘a nivele, dup˘a
minimizarea funct¸iei. Ie¸sirea circuitului are valoarea logic˘a a majorit˘at¸ii intr˘arilor.
Solut¸ie
Tabelul de adev˘ar al circuitului ”vot majoritar” este:
V
2
V
1
V
0
VOT
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Diagrama V-K asociat˘a funct¸iei este prezentat˘a ˆın figura 7.2, al˘aturi de implementarea cu port¸i NAND a funct¸iei
V OT .
a) b)
Figura 7.2 Funct¸ia ”vot majoritar”: a) diagrama V-K, b) implementare cu port¸i NAND.
Din tabelul de adev˘ar se determin˘a diagrama V-K ¸si se minimizeaz˘a funct¸ia obt¸inˆandu-se expresia:
V OT = V
2
· V
1
+ V
2
· V
0
+ V
1
· V
0
Se observ˘a a dac˘a dou˘a din cele trei variabile sunt egale cu 1, exist˘a o conjunct¸ie a dou˘a intr˘ari egal˘a cu 1, ceea
ce determin˘a V OT = 1.
7.3 Pentru cei ce vor a ˆınvet¸e
1. Minimizat¸i funct¸iile logice ¸si implementat¸i-le cu port¸i NAND pe dou˘a nivele logice.
a) F
a
=
(0, 2, 4, 7)
b) F
b
=
(1, 3, 6, 7)
c) F
c
=
(1, 2, 4, 7)
d) F
d
=
(1, 2, 3, 4, 5)
e) F
e
=
(0, 2, 5, 8, 10, 13, 14)
f) F
f
=
(4, 5, 6, 7, 10, 11)
g) F
g
=
(2, 5, 7, 9, 11, 13, 15)
h) F
h
=
(4, 6, 9, 11, 12, 14)
i) F
i
=
(0, 3, 5, 6, 9, 10, 12, 15)
Solut¸ie
a) Diagrama V-K asociat˘a funct¸iei F
a
=
(0, 2, 4, 7) este prezentat˘a n figura 7.3-a). Forma minim˘a a funct¸iei
7.3. Pentru cei ce vor a ˆınvet¸e 89
F
a
a) b)
Figura 7.3 F
a
, problema 1-a: a) diagrama V-K, b) implementare cu port¸i NAND.
este:
F
a
= B · C + A · C + A · B · C
Implementarea cu port¸i NAND este prezentat˘a ˆın figura 7.3-b).
Costul implement˘arii este:
2 port¸i NAND × 2
2 port¸i NAND × 3
3 port¸i NOT × 1
Total: 7 port¸i cu un num˘ar total de 13 intr˘ari.
c) Pentru funct¸ia F
c
=
(1, 2, 4, 7) diagrama V-K (figura 7.4-a) este ˆın form˘a de tabl˘a de ¸sah”, forma minim˘a
fiind FCND:
F
c
= A · B · C + A · B · C + A · B · C + A · B · C
F
c
a) b) c)
Figura 7.4 F
c
, problema 1-c: a) diagrama V-K, b) implementare cu port¸i NAND, c) implementare cu port¸i XOR.
Se observ˘a a F
c
poate implementat˘a c o singur˘a poart˘a XOR de 3 intr˘ari:
F
c
= A B C
e) Diagrama V-K asociat˘a funct¸iei F
e
=
(0, 2, 5, 8, 10, 13, 14) este prezentat˘a n figura 7.5-a).
F
e
a) b)
Figura 7.5 F
e
, problema 1-e: a) diagrama V-K, b) implementare cu port¸i NAND.
90 LECT¸ IA 7. Sinteza circuitelor logice combinat¸ionale
Forma minim˘a a funct¸iei este:
F
e
= B · C · D + A · C · D + B · D
Implementarea cu port¸i NAND este prezentat˘a ˆın figura 7.5-b).
Costul implement˘arii este:
1 poart˘a NAN D × 2
3 port¸i NAND × 3
3 port¸i NOT × 1
Total: 7 port¸i cu un num˘ar total de 14 intr˘ari.
i) Se observ˘a a diagrama V-K asociat˘a funct¸iei F
i
=
(0, 3, 5, 6, 9, 10, 12, 15) este ˆın form˘a de tabl˘a de ¸sah”
¸si se poate implementa cu o poart˘a XOR sub forma:
F
i
= A B C D
2. Minimizat¸i funct¸iile logice incomplet definite ¸si implementat¸i-le cu port¸i NAND. Evaluat¸i ”costul” implemenarilor.
Propunet¸i solut¸ii de eliminare a hazardului combinat¸ional ¸si evaluat¸i costurile suplimentare ale acestora.
a) F
a
=
(1, 3, 5, 9, 14, 15) + d(4, 6, 12, 13)
b) F
b
=
(0, 3, 4, 5, 6, 7, 9, 12, 14, 15) + d(10)
c) F
c
=
(0, 1, 5, 7, 9, 10, 14) + d(3, 8)
d) F
d
=
(2, 6, 7, 9, 10) + d(0, 8)
e) F
e
=
(5, 6, 7, 8, 9, 10, 13, 14, 15) + d(0, 11)
f) F
f
=
(1, 2, 3, 5, 7, 10, 13, 14, 15) + d(6, 8)
Solut¸ie
a) Diagrama V-K asociat˘a funct¸iei F
a
este prezentat˘a ˆın figura 7.6. Funct¸ia minimizat˘a cu diagrama V-K este:
F
a
Figura 7.6 F
a
, problema 26-a: diagrama V-K ¸si implementare cu port¸i NAND.
F
a
= C · D + A · B + A · B · D
Pentru a obt¸ine expresia funct¸iei doar cu port¸i NAND se aplic˘a Teorema lui De Morgan:
F
a
= C · D + A · B + A · B · D = C · D · A · B · A · B · D
Costul implement˘arii este:
2 port¸i NAND × 2
2 port¸i NAND × 3
3 port¸i NOT × 1
Total: 7 port¸i cu un num˘ar total de 13 intr˘ari.
Din diagrama V-K se observ˘a a nu exist˘a suprafet¸e disjuncte adiacente. Deci, funct¸ia nu are hazard combinat¸ional.
d) Diagrama V-K asociat˘a funct¸iei F
d
este prezentat˘a ˆın figura 7.7.
Funct¸ia minimizat˘a cu diagrama V-K este:
F
d
= I + II + III = B · D + A · B · C + A · B · C
Pentru a obt¸ine expresia funct¸iei doar cu port¸i NAND se aplic˘a Teorema lui DeMorgan:
F
d
= B · D + A · B · C + A · B · C = B · D · A · B · C · A · B · C
Costul implement˘arii este:
1 poart˘a NAN D × 2
3 port¸i NAND × 3
7.3. Pentru cei ce vor a ˆınvet¸e 91
F
d
Figura 7.7 F
d
, problema 26-d: diagrama V-K ¸si implementare cu port¸i NAND.
4 port¸i NOT × 1
Total: 8 port¸i cu un num˘ar total de 15 intr˘ari.
Din diagrama V-K se observ˘a a suprafet¸ele I ¸si II sunt suprapuse, ˆıns˘a suprafet¸ele I ¸si III sunt disjuncte dar
adiacente. Rezult˘a a funct¸ia poate prezenta hazard combinat¸ional. Eliminarea hazardului combinat¸ional se
poate face prin ad˘augarea unei suprafet¸e IV prezentat˘a ˆın figura 7.8.
F
d
Figura 7.8 F
d
, problema 26-d: diagrama V-K ¸si implementare cu port¸i NAND, ar˘a hazard combinat¸ional.
Funct¸ia ar˘a hazard combinat¸ional devine:
F
d
= I + II + III + IV = B · D + A · B · C + A · B · C + A · C · D
3. a se implementeze funct¸ia: F (A, B, C, D) =
(1, 3, 4, 5, 7, 10, 11, 12, 14, 15) cu dou˘a nivele de port¸i logice OR-
AND ar˘a a produce hazard static.
Solut¸ie
Circuitele combinat¸ionale implementate pe dou˘a nivele logice OR-AND (sau NOR-NOR), implementeaz˘a pe
primul nivel logic implicant¸i primi, iar pe al doilea nivel logic se al˘atur˘a implicant¸ii primi ˆıntr-o poart˘a OR.
Acest tip de implementare a funct¸iilor minimizate poate produce hazard combinat¸ional static 0 deoarece ie¸sirea
lor 0 (sinteza formei canonice conjunctive a funct¸iei se face pe baz˘a de 0) poate genera un glitch (semnal de
scurt˘a durat˘a) aand starea logic˘a 1 ˆın cazul ˆın care o variabil˘a de intrare comut˘a, dac˘a pentru anumite valori
constante ale celorlalte variabile funct¸ia se reduce la forma: X · X = 0.
Pe baza diagramei V-K prezentate ˆın figura 7.9-a, se obt¸ine expresia minim˘a ˆın form˘a canonic˘a conjunctiv˘a:
F = (A + C) · (A + D) · (B + C + D)
4. Implementat¸i cu port¸i NAND urm˘atoarele funct¸ii cu eliminarea hazardului combinat¸ional.
a) F
a
(A, B, C) =
(1, 3, 4, 5)
b) F
b
(A, B, C) =
(1, 2, 3, 5)
c) F
c
(A, B, C) =
(0, 2, 3, 4, 6)
d) F
d
(A, B, C , D) =
(0, 1, 2, 5, 6, 7, 15)
e) F
e
(A, B, C , D) =
(0, 1, 5, 7, 8, 9, 14, 15)
f) F
f
(A, B, C , D) =
(2, 3, 8, 9, 10, 11)
92 LECT¸ IA 7. Sinteza circuitelor logice combinat¸ionale
a) b) c)
d) e)
Figura 7.9 a) Diagrama V-K, minimizare cu hazard combinat¸ional, b) Implementare OR-AND, cu hazard combinat¸ional
c) Diagramele temporale, d) Diagrama V-K, minimizare ar˘a hazard combinat¸ional, e) Implementare OR-AND, ar˘a hazard
combinat¸ional (problema 3).
Solut¸ie
a) F
a
(A, B, C) = I + II + III = A · B + A · C + B · C = (A · B) · (A · C) · (B · C)
5. Proiectat¸i un circuit de conversie a cifrelorˆın baza 10, reprezentate pe 4 bit¸i BCD (Engl. ”Binary Code Decimal”),
ˆın codurile corespondente pentru comanda unui afi¸saj cu 7 segmente. Combinat¸iile binare care nu au asociat un
num˘ar ˆın baza 10 vor determina stingerea tuturor segmentelor. Repetat¸i problema cu toate cele 16 combinat¸ii
de intrare.
ˆ
In cazul intr˘arilor 10-15, segmentelor vor afi¸sa simbolul asociat ˆın baza 16: a, b, c, d, e, f. Comparat¸i
costurile celor dou˘a implement˘ari ¸si explicat¸i diferent¸ele.
6. Implementat¸i urm˘atoarea funct¸ie utilizˆand port¸i XOR ¸si AND:
F = A · B · C · D + A · B · C · D + A · B · C · D + A · B · C · D
Solut¸ie
Din diagrama V-K, prezentat˘a ˆın figura 7.11-a reiese a forma canonic˘a a funct¸iei este ¸si form˘a minim˘a.
Implementarea cu port¸i NAND pe dou˘a nivele necesit˘a:
4 port¸i NOT ¸si,
5 port¸i NAND x 4
Total: 9 port¸i cu 24 de intr˘ari.
Alternativa de implementare se bazeaz˘a pe observat¸ia a diagrama V-K are o form˘a particular˘a de simetrie, ceea
ce sugereaz˘a o implementare cu port¸i XOR. Prin prelucr˘ari algebrice, se pune funct¸ia ˆıntr-o form˘a simplificat˘a
pe baza operatorului XOR:
F = A ·B · C · D +A· B · C · D+A· B ·C · D+A·B ·C · D = (A ·B · C ·D +A· B · C · D)+(A· B ·C · D+A· B ·C · D) =
7.3. Pentru cei ce vor a ˆınvet¸e 93
a) b)
Figura 7.10 Problema 4-a: diagrama V-K ¸si structura de port¸i NAND cu eliminarea hazardului combinat¸ional.
A·B·(C ·D+C·D)+A·B· ( C ·D+C ·D) = A·B·(C D )+A·B·(C D) = (CD)·(A·B+ A·B) = (C D)·(AB)
Rezult˘a circuitul prezentat ˆın figura 7.11-b.
a) b)
Figura 7.11 a) Diagrama V-K, b) circuitul pentru problema 6.
7. Proiectat¸i un circuit logic pe dou˘a nivele de p ort¸i NAND care a implementeze ar˘a hazard combinat¸ional funct¸ia:
F (A, B, C, D) =
(0, 2, 4, 5, 6, 7, 8, 10, 11, 15).
Solut¸ie
a) b)
Figura 7.12 Diagrame V-K asociate funct¸iei referite la problema 7. Minimizare ar˘a hazard combinat¸ional.
Diagrama V-K asociat˘a funct¸iei este prezentat˘a ˆın figura 7.12-a. Funct¸ia minimizat˘a este:
F = I + II + III = A · B + B · D + A · C · D
Pentru eliminarea hazardului combinat¸ional mai trebuie definite suprafet¸e suplimentare, conform figurii 7.12-b.
F = I + II + III + IV + V + V I = A · B + B · D + A · C · D + A · D + B · C · D + A · B · C
Implementarea pe dou˘a nivele de p ort¸i NAND se face conform expresiei:
F = A · B + B · D + A · C · D + A · D + B · C · D + A · B · C = A · B · B · D · A · C · D · A · D · B · C · D · A · B · C
Circuitul este prezentat ˆın figura 7.13.
94 LECT¸ IA 7. Sinteza circuitelor logice combinat¸ionale
Figura 7.13 Circuit pe dou˘a nivele de port¸i NAND, implementare a funct¸iei referite de problema 7.
7.4 Pentru cei ce vor a devin˘a profesioni¸sti
1. Proiectat¸i un circuit generator de paritate de 3 bit¸i ¸si un circuit verificator de paritate de 4 bit¸i, utilizˆand regula
parit˘atii pare.
Solut¸ie
Generatorul de paritate par˘a prezina la ie¸sire 1 dac˘a la intrare sunt un num˘ar impar de bit¸i egali cu 1 ¸si 0 dac˘a
la intrare sunt un num˘ar par de bit¸i egali cu 1. Aceast˘a funct¸ionalitate este realizat˘a de o poart˘a logic˘a XOR:
EV EN = I
2
I
1
I
0
Eroarea de paritate verific˘a paritatea datelor recept¸ionate ˆımpreun˘a cu bitul de paritate. Dac˘a suma celor 4 bit¸i
este un num˘ar par, verificarea este corect˘a, altfel se semnaleaz˘a eroare de paritate:
ERR
ev en
= I
2
I
1
I
0
EV EN
Circuitele sunt prezentate ˆın figura 7.14.
Figura 7.14 Generator ¸si verificator de paritate par˘a de 3 bit¸i.
2. a se implementeze un circuit logic combinat¸ional care produce conversia numerelor de la 0 la 15 exprimate ˆın
cod binar ˆın reprezentarea acestora ˆın cod Gray.
Solut¸ie
Tabelul de adev˘ar al convertorului din cod binar ˆın cod Gray este:
7.4. Pentru cei ce vor a devin˘a profesioni¸sti 95
Cod Binar Cod Gray
B
3
B
2
B
1
B
0
G
3
G
2
G
1
G
0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 1
0 0 1 1 0 0 1 0
0 1 0 0 0 1 1 0
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 1
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 0 1 1 1 0 1
1 0 1 0 1 1 1 1
1 0 1 1 1 1 1 0
1 1 0 0 1 0 1 0
1 1 0 1 1 0 1 1
1 1 1 0 1 0 0 1
1 1 1 1 1 0 0 0
Diagramele V-K asociate ie¸sirilor circuitului G
[3:0]
(B
[3:0]
) sunt prezentate ˆın figura 7.15.
G
3
G
2
G
1
G
0
Figura 7.15 Diagramele V-K pentru convertorul binar-Gray pe 4 bit¸i.
Dup˘a minimizarea funct¸iilor, se obt¸in ecuat¸iile:
G
3
= B
3
G
2
= B
3
· B
2
+ B
3
· B
2
= B
3
B
2
G
1
= B
2
· B
1
+ B
2
· B
1
= B
2
B
1
G
0
= B
1
· B
0
+ B
1
· B
0
= B
1
B
0
Circuitul rezultat, implementat cu port¸i XOR, este prezentat ˆın figura 7.16. Se observ˘a faptul a se poate obt¸ine
o implementare iterativ˘a, posibil de extins p entru conversia din cod binar ˆın cod Gray a numerelor reprezentate
pe mai mult¸i bit¸i. Generalizˆand relat¸iile, se pot scrie ecuat¸iile conversiei din binar ˆın cod Gray, pentru N bit¸i
astfel:
G
N1
= B
N1
G
i
= B
i+1
B
i
, pentru i [(N 2), ..., 0]
3. a se implementeze un circuit logic combinat¸ional care produce conversia din cod Gray pe 4 bit¸i ˆın cod binar.
96 LECT¸ IA 7. Sinteza circuitelor logice combinat¸ionale
Figura 7.16 Implementarea convertorului numerelor din binar ˆın cod Gray pe 4 bit¸i, cu port¸i XOR.
Solut¸ie
Tabelul de adev˘ar al convertorului din cod binar ˆın cod Gray este prezentat la problema 2. Diagramele V-K
asociate ie¸sirilor circuitului G
[3:0]
(B
[3:0]
) sunt prezentate ˆın figura 7.17.
B
3
B
2
B
1
B
0
Figura 7.17 Diagramele V-K pentru convertorul din cod Gray pe 4 bit¸i ˆın cod binar.
Dup˘a minimizarea funct¸iilor, se obt¸in ecuat¸iile:
B
3
= G
3
B
2
= G
3
· G
2
+ G
3
· G
2
= G
3
G
2
= B
3
G
2
B
1
= G
3
· G
2
· G
1
+ G
3
· G
2
· G
1
+ G
3
· G
2
· G
1
+ G
3
· G
2
· G
1
= G
3
G
2
G
1
= B
2
G
1
B
0
= G
3
· G
2
· G
1
· G
0
+ G
3
· G
2
· G
1
· G
0
+ G
3
· G
2
· G
1
· G
0
+ G
3
· G
2
· G
1
· G
0
+
+ G
3
· G
2
· G
1
· G
0
+ G
3
· G
2
· G
1
· G
0
+ G
3
· G
2
· G
1
· G
0
+ G
3
· G
2
· G
1
· G
0
=
= G
3
G
2
G
1
G
0
= B
1
G
0
Circuitul rezultat, implementat cu port¸i XOR, este prezentat ˆın figura 7.18. Se observ˘a faptul a se poate obt¸ine
o implementare iterativ˘a, posibil de extins p entru conversia din cod Gray ˆın cod binar a numerelor reprezentate
pe mai mult¸i bit¸i. Generalizˆand relat¸iile, se pot scrie ecuat¸iile conversiei din cod Gray ˆın cod binar, pentru N
bit¸i astfel:
B
N1
= G
N1
B
i
= B
i+1
G
i
, pentru i [(N 2), ..., 0]
7.4. Pentru cei ce vor a devin˘a profesioni¸sti 97
Figura 7.18 Implementarea convertorului din cod Gray pe 4 bit¸i ˆın binar, cu port¸i XOR.