r6i11iy
Bibliografie
1. Circuite de comutare aplicate in calculatoarele electronice, V. Pop,
Volker Popovici, ed. Facla, 1976
2. Circuite integrate digitale, Gh. Stefan, I. Draghici, T. Muresan, E. Barbu,
EDP, 1983
3. De la poarta TTL la microprocesor, I. Sztojanov s.a., ET, 1987
4. Proiectarea cu circuite logice MSI si LSI standard, T.R. Blakeslee, ET, 1988
5. Circuite integrate digitale, Gh. Stefan, V. Bistriceanu, Probleme, proiectare,
EDP, 1992
6. Circuite integrate digitale, Gh. Stefan, V. Bistriceanu, Probleme, proiectare,
Ed. Albastra, 2000
7. Automatizari discrete in industrie, Culegere de probleme, N. Spranceana,
R. Dobrescu, Th. Borangiu, ET, 1978
8. Sisteme numerice cu circuite integrate, Culegere de probleme, Sanda Maican,
ET, 1980
9. Analiza si sinteza dispozitivelor numerice, I.A. Letia, Indrumator
de laborator, I.P. Cluj-Napoca, 1985
10. Analiza si sinteza dispozitivelor numerice, A. Netin, O. Cret, Indrumator
de laborator, UT Press. Cluj-Napoca, 1998
Curs 1
CAPITOLUL I
ELEMENTE DE ALGEBRA BOOLEANA
1.1. Generalitati
Transferul, prelucrarea si pastrarea datelor numerice sau nenumerice in
interiorul unui calculator se realizeaza prin intermediul circuitelor de comutare.
Aceste circuite se caracterizeaza prin faptul ca prezinta doua stari stabile
care se deosebesc calitativ intre ele. Starile sunt puse in corespondenta
cu valorile binare “0” si “1” sau cu valorile logice
“adevarat” si “fals” (din acest motiv se mai numesc
si circuite logice). Pornind de la aceste considerente, un domeniul al logicii
matematice, (stiinta care utilizeaza metode matematice in solutionarea
problemelor de logica) numit “algebra logicii” si-a gasit o larga
aplicare in analiza si sinteza circuitelor logice. Algebra logicii opereaza
cu propozitii care pot fi adevarate sau false. Unei propozitii adevarate i se
atribuie valoarea “1”, iar unei propozitii false i se atribuie valoarea
“0”. O propozitie nu poate fi simultan adevarata sau falsa, iar
doua propozitii sunt echivalente d.p.d.v. al algebrei logice, daca simultan
ele sunt adevarate sau false. Propozitiile pot fi simple sau compuse, cele compuse
obtinandu-se din cele simple prin legaturi logice de tipul conjunctiei
Ù, disjunctiei Ú sau negatiei Ø.
Bazele algebrei logice au fost puse de matematicianul englez George Boole (1815-1864)
si ca urmare ea se mai numeste si algebra booleana. Ea a fost conceputa ca o
metoda simbolica pentru tratarea functiilor logicii formale, dar a fost apoi
dezvoltata si aplicata si in alte domenii ale matematicii. In 1938
Claude Shannon a folosit-o pentru prima data in analiza circuitelor de
comutatie.
1.2. Definirea axiomatica a algebrei booleene
Algebra booleana este o algebra formata din:
- elementele A0,1S;
- 2 operatii binare numite SAU si SI, notate simbolic + sau Ú si ×
sau Ù;
- 1 operatie unara numita NU negatie, notata simbolic sau Ø.
Operatiile se definesc astfel:
SI SAU NU
0 × 0 = 0 0 + 0 = 0 0 = 1
0 × 1 = 0 0 + 1 = 1 1 = 0
1 × 0 = 0 1 + 0 = 1
1 × 1 = 1 1 + 1 = 1
Axiomele algebrei booleene sunt urmatoarele:
Fie o multime M compusa din elementele x1, x2,…xn, impreuna cu operatiile
× si +. Aceasta multime formeaza o algebra daca:
1) Multimea M contine cel putin 2 elemente distincte x1 ¹ x2 (x1,x2I
M);
2) Pentru " x1 I M, x2 I M avem: x1 + x2 I M si x1 × x2 I M
3) Operatiile × si + au urmatoarele proprietati: a. sunt comutative x1 × x2 = x2 × x1 x1 + x2 = x2 + x1 b. sunt asociative x1 × (x2 × x3) = (x1 × x2) × x3 x1 + (x2 + x3) = (x1 + x2) + x3 c. sunt distributive una fata de cealalta x1 × (x2 + x3) = x1 × x2 + x1 × x3 x1 + (x2 × x3) = (x1 + x2) × (x1 + x3)
4) Ambele operatii admit cate un element neutru cu proprietatea: x1 + 0 = 0 + x1 = x1 x1 × 1 = 1 × x1 = x1 unde 0 este elementul nul al multimii, iar 1 este elementul unitate al multimii.
5) Daca multimea M nu contine decat doua elemente, acestea trebuie sa
fie obligatoriu elementul nul 0 si elementul unitate 1; atunci pentru "
x I M exista un element unic notat cu x cu proprietatile: x × x = 0 principiul contradictiei x + x = 1 principiul tertului exclus x este inversul elementului x.
In definirea axiomatica a algebrei s-au folosit diferite notatii. In
tabelul urmator se dau denumirile si notatiile specifice folosite pentru diverse
domenii:
Matematica Logica Tehnica
Prima lege de compozitiex1 + x2 Disjunctiex1 Ú x2 SAUx1 + x2
A doua lege de compozitiex1 × x2 Conjunctiex1 Ù x2 SIx1 ×
x2
Elementul inversx NegareØx NUx
1.3. Proprietatile algebrei booleene
Plecand de la axiome se deduc o serie de proprietati care vor forma reguli
de calcul in cadrul algebrei booleene. Aceste proprietati sunt:
1) Principiul dublei negatii x = x dubla negatie duce la o afirmatie
2) Idempotenta x × x = x x + x = x
3) Absorbtia x1 × (x1 + x2) = x1 x1 + (x1× x2) = x1
4) Proprietatile elementelor neutre x × 0 = 0 x × 1 = x x + 0 = x x + 1 = 1
5) Formulele lui De Morgan x1 × x2 = x1 + x2 x1 + x2 = x1 × x2
Aceste formule sunt foarte utile datorita posibilitatii de a transforma produsul
logic in suma logica si invers.
Formulele pot fi generalizate la un numar arbitrar de termeni: x1 × x2 × … × xn = x1 + x2 + … + xn x1 + x2 + … + xn = x1 × x2 × … × xn
6) Principiul dualitatii -; daca in axiomele si proprietatile algebrei
booleene se interschimba 0 cu 1 si + cu ×, sistemul de axiome ramane
acelasi, in afara unor permutari.
Verificarea proprietatilor se poate face cu ajutorul tabelelor de adevar si
cu observatia ca doua functii sunt egale daca iau aceleasi valori in toate
punctele domeniului de definitie. Prin tabelul de adevar se stabileste o corespondenta
intre valorile de adevar ale variabilelor si valoarea de adevar a functiei.
Obs. Comutativitatea si asociativitatea pot fi extinse la un numar arbitrar,
dar finit, de termeni, indiferent de ordinea lor.
1.4. Functii booleene
O functie f: Bn ® B, unde B = A0,1S se numeste functie booleana. Aceasta
functie booleana y = f(x1, x2,…,xn) are drept caracteristica faptul ca
atat variabilele cat si functia nu pot lua decat doua valori
distincte, 0 sau 1. Functia va pune in corespondenta fiecarui element
al produsului cartezian n dimensional, valorile 0 sau 1. Astfel de functii sunt
utilizate pentru caracterizarea functionarii unor dispozitive (circuite) construite
cu elemente de circuit avand doua stari (ex.: un intrerupator inchis
sau deschis, un tranzistor blocat sau in conductie; functionarea unui
astfel de circuit va fi descrisa de o variabila booleana xi).
1.4.1. Functii booleene elementare
Revenim la forma generala a unei functii booleene de n variabile: y = f(x1, x2,…,xn)
Domeniul de definitie este format din m = 2n puncte. Deoarece in fiecare
din aceste puncte functia poate lua doar valorile 0 si 1 rezulta ca numarul
total al functiilor booleene de n variabile este N = 2m.
Vom considera in continuare functiile elementare de 1 variabila. Pentru
n = 1 avem m = 2 si N = 4. Functia are forma y = f(x) si cele 4 forme ale ei
se gasesc in tabelul urmator:
fi x 0 1 Reprezentare Denumire f0 0 0 0 Constanta 0 f1 0 1 x Variabila x f2 1 0 x Negatia lui x f3 1 1 1 Constanta 1
La fel se pot realiza toate functiile cu ajutorul unor functii de baza. Acestora
le vor corespunde si niste circuite logice elementare, cu ajutorul carora se
poate realiza practic orice tip de circuit. Tinand cont de faptul ca circuitele
logice de comutatie au 2 stari stabile LOW (L) si HIGH (H), asignand lui
L 0 si lui H 1 se poate intocmi un tabel al functiilor elementare.
Denumire Functie Simbol Tabel de adevar Tabel de definitie
Inversor -; NOT f = x x f = x x f 0 1 1 0 x f L H H L
Poarta SI -; AND f = x1 × x2 x1x2 f=x1×x2 x1 x2 f0 0 00 1 01
0 01 1 1 x1 x2 fL L LL H LH L L H H H
Poarta SAU -; OR f = x1 + x2 x1x2 f=x1+x2 x1 x2 f0 0 00 1 11 0 1 1 1 1
x1 x2 fL L LL H HH L H H H H
Poarta SI-NU -; NAND f = x1 × x2 x1x2 f=x1×x2 x1 x2 f0 0 10
1 11 0 1 1 1 0 x1 x2 fL L HL H HH L H H H L
Poarta SAU-NU -; NOR f = x1 + x2 x1x2 f=x1+x2 x1 x2 f0 0 10 1 01 0 0 1
1 0 x1 x2 fL L HL H LH L L H H L
SAU EXCLUSIV -; XOR f = x1 + x2 x1x2 f=x1 + x2 x1 x2 f0 0 00 1 11 0 1 1
1 0 x1 x2 fL L LL H HH L H H H L
COINCIDENTA f = x1 × x2 x1x2 f=x1 × x2 =x1 + x2 x1 x2 f0 0 10 1
01 0 0 1 1 1 x1 x2 fL L HL H LH L L H H H
1.4.2. Reprezentarea functiilor booleene
Exista doua moduri de reprezentare a functiilor booleene: grafica si analitica.
1. Modalitati grafice - se caracterizeaza printr-o reprezentare intuitiva, usor
de retinut, dar sunt inadecvate pentru functii booleene cu un numar de variabile
mai mare decat 4;
2. Modalitati analitice - sunt mai greoaie, dar permit metode automate, deci
algoritmi de simplificare a functiei; se folosesc in general pentru functii
booleene cu numarul variabilelor mai mare decat 5.
1.4.2.1. Modalitati de reprezentare grafica
Modalitatile de reprezentare grafica sunt: tabel de adevar, diagrama Karnaugh,
schema logica, diagrama de timp.
1. Tabel de adevar -; se marcheaza intr-un tabel corespondenta dintre
valorile de adevar ale variabilelor de intrare si valoarea de adevar a functiei,
in fiecare punct al domeniului de definitie.
Pentru o functie cu n variabile de intrare vom avea 2n combinatii.
Exista situatii in care, pentru anumite combinatii ale variabilelor de
intrare, valoarea functiei nu este specificata. Aceste functii se numesc incomplet
definite. In tabel, in locul in care functia nu este specificata,
se noteaza cu “X”. Daca o functie booleana este incomplet definita
pentru “m” combinatii ale variabilelor de intrare se pot defini
2m functii noi prin alegerea arbitrara a valorilor incomplet definite.
2. Diagrama Karnaugh
O diagrama Karnaugh pentru o functie booleana de n variabile se deseneaza sub
forma unui patrat sau dreptunghi impartit in 2n compartimente. Fiecare
compartiment este rezervat unui termen canonic al functiei, respectiv unuia
dintre varfurile cubului n dimensional din reprezentarea geometrica a
functiei (2n n-uple ale functiei).
Diagrama Karnaugh este organizata astfel incat doua compartimente
vecine pe o linie sau pe o coloana corespund la doi termeni canonici care difera
numai printr-o singura variabila, care apare in unul adevarata, iar in
celalalt negata (la doua n-pluri adiacente). Se considera vecine si compartimentele
aflate la capetele opuse ale unei linii, respectiv coloane.
Diagrama Karnaugh se noteaza fie indicand domeniul fiecarei variabile,
fie indicand pe linie si coloana n-uple de zerouri si unitati corespondente
unui compartiment din diagrama si ordinea variabilelor. Prima notatie se foloseste
in cazul in care se reprezinta functia prin forma ei canonica sau
normala. A doua notatie se foloseste in cazul in care functia se
reprezinta prin tabel de adevar. Pentru a putea reprezenta usor functii exprimate
in mod conventional prin indicii termenilor canonici se poate nota fiecare
compartiment cu indicele termenului corespondent, tinand cont de o anumita
ordine a variabilelor.
Exemple:
1) Diagrama Karnaugh pentru functia de 2 variabile: f(x1, x2) = x1×x2 + x1×x2
x2 x1 0 1 x2 x1 0 1
0 x1x2 x1x2 0 0 1 x2 1 x1x2 x1x2 1 1 0 x1 sau x1
00 01 11 10 x2
Obs. Numerotarea liniilor si coloanelor se face in cod Gray (cod binar
reflectat)
Cod binar direct Cod Gray
0000 0000
0001 0001
0010 0011
0011 0010
0100 0110
0101 0111
0110 0101
0111 0100
1000 1100
1001 1101
1010 1111
1011 1110
1100 1010
1101 1011
1110 1001
1111 1000
2) Diagrama Karnaugh pentru functia de 3 variabile: y = f(x1,x2,x3)
Domeniul de definitie este format din 23 = 8 puncte si reprezinta varfurile
unui cub cu latura 1: x1
001 101
011 111
000 100 x3
010 110 x2
Diagramele Karnaugh corespunzatoare pot fi reprezentate astfel: x2
x1 x2x3 00 01 11 10
0 0 1 3 2 x1 1 4 5 7 6 x3 sau
x3 x1x2 x3 0 1
00 0 1
01 2 3 x2 x1 11 6 7
10 4 5
3) Diagrama Karnaugh pentru functia de 4 variabile: y = f(x1,x2,x3,x4) x4 x1x2 x3x4 00 01 11 10
00 0 1 3 2
01 4 5 7 6 x2 x1 11 12 13 15 14
10 8 9 11 10 x3
Prin sageti am marcat vecinatatile punctului de coordonate 0010.
4) Diagramele Karnaugh pentru functii de mai mult de 4 variabile se construiesc
din diagrame de 4 variabile considerate ca diagrame elementare.
3. Schema logica -; reprezentare cu ajutorul simbolurilor circuitelor logice.
4. Diagrama de timp -; reprezentare utila pentru studiul unor forme tranzitorii
de hazard in circuitele logice. Se reprezinta functii logice in
a caror evolutie intervine timpul.
Exemplu: f = x1×x2
x1 x2 f
Curs 2
1.4.2.2. Modalitati de reprezentare analitica
1) Formele canonice
Fie o functie booleana f(x), unde x = (x1,x2,…,xn). Se defineste numarul
i = x1×20 + x2×21 + … + xn×2n-1 ca numar de combinatii.
Exemplu: x1 x2 x3 f
0 0 0
0 0 1
0 1 0 ® i = 0×22 + 1×21 + 0×20 = 2
0 1 1
Fie functia Pi definita pe Bn ® B, deci Pi : Bn ® B
Pi(x1,x2,…,xn) = 1 daca numarul de combinatii este i
0 in caz contrar
Aceasta functie se numeste constituent al unitatii. Se poate arata ca orice
functie booleana data prin tabelul de adevar se poate scrie ca o suma de constituenti
ai unitatii. f(x1, x2,…,xn) = Pi1 + Pi2 + … + Pip = S Pij i,jIM1 unde M1 = multimea tuturor combinatiilor argumentelor pentru care functia ia
valoarea 1. Aceasta forma de scriere se numeste forma canonica disjunctiva FCD,
iar termenii constituenti se numesc termeni canonici conjunctivi sau mintermi
(se mai numeste si forma suma de produse).
Functia booleana se mai poate scrie si sub forma Si : Bn ® B unde B = A0,1S.
Si(x1,x2,…,xn) = 0 daca numarul de combinatii este i
1 in caz contrar
Se poate demonstra ca orice functie booleana poate fi adusa la forma: f(x1, x2,…,xn) = Si1 × Si2 × … × Siq = P Sij i,jIM0 unde M0 = multimea tuturor combinatiilor argumentelor pentru care functia ia
valoarea 0. Aceasta forma de scriere se numeste forma canonica conjunctiva FCC,
iar factorii constituenti se numesc termeni canonici conjunctivi sau maxtermi
(se mai numeste si forma produs de sume).
Se poate demonstra ca Si = Pi.
Algoritmi de obtinere a formelor canonice pe baza tabelului de adevar sau a
diagramei Karnaugh:
FCD
- se determina toate combinatiile variabilelor pentru care valoarea functiei
este 1;
- se scriu mintermii corespunzatori (o variabila apare nenegata daca are valoarea
1 si negata daca are valoarea 0);
- se insumeaza mintermii obtinuti anterior.
FCC
- se determina toate combinatiile variabilelor pentru care valoarea functiei
este 0;
- se scriu maxtermii corespunzatori prin insumarea variabilelor (o variabila
apare nenegata daca are valoarea 0 si negata daca are valoarea 1);
- se inmultesc maxtermii obtinuti anterior.
Exemplu: x1 x2 x3 f
0 0 0 0
0 0 1 1 mintermul este x1×x2×x3
0 1 0 0 maxtermi sunt (x1+x2+x3)×(x1+x2+x3)
Trecerea dintr-o forma canonica in alta se poate face in doua moduri:
- cu ajutorul tabelului de adevar;
- prin aplicarea dublei negatii si a teoremelor lui De Morgan.
Teorema lui Shannon
Complementul unei functii booleene se obtine prin complementarea fiecarei variabile
si interschimbarea operatorilor SI cu SAU si reciproc. f(x1,x2,…,xn)+,× = f(x1,x2,…,xn)×,+
Teorema de expansiune
Fie functia booleana f(x1,x2,…, xi-1, xi, xi+1,…,xn) care se expandeaza
dupa variabila xi. Avem atunci: f(x1,x2,…, xi-1, xi, xi+1,…,xn) = xi×f(x1,x2,…, xi-1,
1, xi+1,…,xn) + xi×f(x1,x2,…, xi-1, 0, xi+1,…,xn)
Functia duala este: f = axi + f(x1,x2,…, xi-1, 0, xi+1,…,xn)i×axi + f(x1,x2,…,
xi-1, 1, xi+1,…,xn)i
2) Forma elementara
La formele canonice ale functiilor booleene termenii contin toate variabilele
independente de intrare, negate sau nenegate. Termenii formei elementare nu
contin toate variabilele de intrare. Aceasta forma se obtine din formele canonice
prin minimizare.
3) Forma neelementara
Forma neelementara contine variabile sau grupuri de variabile comune mai multor
termeni. Se obtine din celelalte forme prin aplicarea algebrei booleene. Este
folosita la implementarea functiilor logice deoarece permite reducerea numarului
de intrari in circuitele logice. Are dezavantajul maririi numarului de
nivele logice.
1.4.3. Minimizarea functiilor booleene
Algebra booleana se foloseste la analiza si sinteza dispozitivelor numerice
(circuite de comutatie). Intre gradul de complexitate al circuitului si
cel al functiei care il descrie exista o legatura directa. Aceasta este
motivatia pentru care, in etapa de sinteza a circuitelor de comutatie,
dupa definirea acestora, urmeaza in mod obligatoriu etapa de minimizare
a functiei, avand drept scop obtinerea unor forme echivalente mai simple
(forma minima).
Solutia minima obtinuta in urma minimizarii ar trebui sa fie cea mai avantajoasa
(economie de porti logice, obtinerea unei scheme mai fiabile, mai ieftine).
In realitate nu este intotdeauna asa. De exemplu, dorinta de a obtine
un sistem usor depanabil poate duce la obtinerea unei solutii neminimale, dar
care prezinta proprietati interesante de simetrie si regularitate.
Prin aplicarea metodelor de minimizare (de simplificare) se ajunge la expresii
minimale sub forma unor SAU-uri de SI-uri (reuniune minimala) ori a unor SI-uri
de SAU-uri (intersectie minimala).
Criteriile utilizate in vederea minimizarii sunt:
- reducerea numarului de variabile;
- reducerea numarului de termeni;
- reducerea pe ansamblu a variabilelor si termenilor, astfel ca suma lor sa
devina minima.
Minimizarea consta in principal in transformarea formelor canonice
si a formelor elementare partial simplificate in forme elementare minimale.
Metodele de minimizare pot fi grupate in metode algebrice si metode grafice.
1.4.3.1. Minimizarea grafica
1. Diagrama Karnaugh
Minimizarea se bazeaza pe proprietatea de adiacenta a codului binar reflectat
(Gray) cu ajutorul caruia se numeroteaza liniile si coloanele diagramei Karnaugh.
In vederea minimizarii se aleg suprafetele maxime (subcuburi) formate
din constituenti ai unitatii, respectiv din constituenti ai lui 0, suprafete
(subcuburi) avand ca dimensiune un numar de patrate (compartimente) egal
intotdeauna cu puteri ale lui 2. Aceste suprafete vor corespunde termenilor
canonici, termenii vecini fiind adiacenti (difera printr-un singur bit). Ca
urmare, in urma gruparii lor se vor reduce variabilele pe baza relatiei:
x1×x2 + x1×x2 = x1.
Metoda de minimizare:
- se realizeaza grupari de compartimente (subcuburi) care sunt puteri ale lui
2. Un compartiment poate fi membru al mai multor suprafete. O suprafata cu 2m
celule vecine va elimina 2m variabile de intrare.
- se scriu ecuatiile corespunzatoare fiecarei suprafete, obtinandu-se
astfel termenii elementari.
- se realizeaza forma disjunctiva minima (FDM) prin insumarea termenilor
elementari obtinuti prin gruparea constituentilor lui 1 sau forma conjunctiva
minima (FCM) prin inmultirea termenilor elementari obtinuti prin gruparea
de constituenti ai lui 0; functiile minimale obtinute sunt identice, ele diferind
numai prin forma de prezentare.
Pentru a se obtine forma minimala a unei functii booleene este util sa se minimizeze
ambele forme canonice, FCC si FCD. Apoi, in functie de disponibilitatea
componentelor si de numarul de conexiuni care rezulta, se poate alege forma
minimala a functiei booleene care va fi implementata.
Exemplu: f(x1,x2,x3,x4) = S (3, 7, 8, 9, 12, 13, 15)
x4 x1x2 x3x4 00 01 11 10
00 0 0 1 0
01 0 0 1 0 x2 x1 11 1 1 1 0
10 1 1 0 0 x3
Pentru FDM a functiei se obtin doua variante, dupa cum se aleg suprafetele pentru
minimizare: fFDM1 = x1×x3 + x1×x3×x4 + x1×x2×x4 sau fFDM2 = x1×x3 + x1×x3×x4 + x2×x3×x4
Implementarea cu porti de tip SI-NU arata astfel:
fFDM1 = x1×x3 + x1×x3×x4 + x1×x2×x4 = = x1×x3
× x1×x3×x4 × x1×x2×x4
Minimizarea functiei negate va fi: fFDM = x1×x3 + x3×x4 + x1×x2×x3
La fel se procedeaza si la minimizarea functiei prin folosirea constituentilor
de 0: x4 x1x2 x3x4 00 01 11 10
00 0 0 1 0
01 0 0 1 0 x2 x1 11 1 1 1 0
10 1 1 0 0 x3
Forma minimizata conjunctiva a functiei FCM este: fFCM = (x1+x3)×(x3+x4)×(x1+x2+x3)
2. Diagrame Karnaugh pentru functii incomplet definite
Functiile incomplet definite sunt cele care in anumite puncte ale domeniului
de definitie pot lua valoarea 0 sau valoarea 1. Avem doua posibilitati:
- combinatii de intrare pentru care functia are valori indiferente (nedefinite);
- combinatii ale variabilelor care nu pot sa apara din punct de vedere fizic;
in aceste situatii trebuie studiat daca combinatiile sunt susceptibile
sa se produca in urma unei manevre false sau in urma unui defect
de functionare; pentru a evita functionarea gresita, in locatiile corespunzatoare
se impun valori pentru functie, astfel incat sa nu se perturbe functionarea
normala.
Valorile nespecificate precum si locatiile corespunzatoare din diagrama Karnaugh
se numesc “indiferente” sau “arbitrare” sau “redundante”.
Ele se noteaza cu “x” si vor fi considerate in timpul minimizarii
ca avand valoarea 1 sau 0, in functie de situatie, pentru a se obtine
o minimizare cat mai buna.
x4 x1x2 x3x4 00 01 11 10
00 x 1
01 x 1 x x2 x1 11 1 1 1
10 1 x 1 x x3
Ca sa minimizam functia in FDM consideram ca x au valoarea 1 si grupam
acesti x numai cu valorile de 1, nu si intre ei (o grupare intre
ei nu are nici o semnificatie).
Se obtine: fFDM = x1×x2 + x2×x3 + x1×x4 + x2×x4
Obs. In cazul functiilor incomplet definite, functia complementara simplificata
prin grupari de 0 nu coincide intotdeauna cu complementul functiei.
3. Diagrame Karnaugh cu expresii a. Superpozitia functiilor booleene
Fie o functie booleana f(X) cu X = (x1,x2,…, xi, xi+1,…,xn). Daca
consideram X1 = (x1,x2,…, xi) si X2 = (xi+1,…,xn) si daca functia
f(X) poate fi scrisa ca o functie f(X) = f3af1(X1), f2(X2)i atunci spunem ca
f(X) a fost obtinuta prin superpozitia functiilor f1(X1) si f2(X2).
Daca X1ÇX2 = F atunci avem o superpozitie disjuncta, iar daca X1ÇX2
¹ F avem o superpozitie nedisjuncta. x1 f xn
Dupa superpozitie avem: x1 f1 xi f3 f xi+1 f2 xn b. Decompozitia functiilor booleene
Daca se da o functie booleana si un set de functii se cere sa se realizeze o
“spargere” a functiei booleene. S-a reusit decompozitia functiei
booleene daca: f = fm afm-1(Xm-1), fm-2(Xm-2),…,f1(X1),X0i unde Xi I X
Daca f poate fi scrisa ca f = f2af1(X1),X0i decompozitia este simpla. m-1
Decompozitia este nedisjuncta daca: ÇXi = F i=j m-1
Decompozitia este disjuncta daca: ÇXi ¹ F i=j
Exemplu: f(x1,x2,x3,x4) = S(0, 2, 3, 7, 9, 10, 11, 14) x4 x1x2 x3x4 00 01 11 10
00 1 1 1
01 1 x2 x1 11 1
10 1 1 1 x3 fFDM = x1×x2×x4 + x1×x3×x4 + x1×x3×x4 +
x1×x2×x4 = x2(x1 × x4) + x3(x1 + x4) =
= x2×G + x3×G unde G = x1 + x4 si deci f se poate scrie: f = f2aG(x1,x4), x2,x3i
Pornind de la aceasta forma pentru f, facem o minimizare. f = x2×G + x3×G = x2×G×(x3 + x3) + x3×G×(x2
+ x2) =
= x2x3G + x2x3G + x2x3G + x2x3G = x2x3 + x2x3G + x2x3G
Diagrama Karnaugh corespunzatoare este: x2 x3 0 1
0 G 1 x2 1 0 G x3
In general o diagrama Karnaugh cu “n” expresii (sau variabile)
are 2n locatii. Prin inglobarea in diagrama a “m” expresii
(variabile) dimensiunea diagramei se reduce, numarul de locatii devenind 2n-m.
Pentru a minimiza o functie prin diagrame Karnaugh cu expresii se fac urmatorii
pasi:
1) se considera toate variabilele din diagrama ca si cum ar fi 0 si se formeaza
suprafete (subcuburi) cu constituentii lui 1;
2) se considera toate locatiile cu 1 indiferente si se formeaza suprafete (subcuburi)
cu variabilele inglobate;
3) se considera intersectia variabilelor inglobate cu gruparile obtinute
in pasul 2;
4) se face reuniunea termenilor din pasii 1 si 3;
5) pentru mai mult de o variabila inglobata se trateaza pe rand
conform pasilor 1 - 4 numai cate o variabila, celelalte fiind considerate
0, iar apoi se scrie reuniunea tuturor termenilor obtinuti.
Exemplu:
Sa se minimizeze functia cu variabile inglobate: x1 x2x3 00 01 11 10
0 a+b 1 c
1 1 1 x
Pasul 1. x1 x2x3 00 01 11 10
0 1
1 1 1 x
Se obtine x2×x3 + x1×x3
Pasul 2 si 3. x1 x2x3 00 01 11 10
0 a+b x c
1 x x x
Se obtine c×x2 + (a+b)×x1×x3
Pasul 4. f = x2×x3 + x1×x3 + c×x2 + (a+b)×x1×x3
Curs 3
1.4.3.2. Minimizarea algebrica
Minimizarea algebrica a functiilor booleene se face cu ajutorul teoremelor algebrei
booleene.
In cazul in care numarul de variabile este mai mare decat
6 se utilizeaza metoda de minimizare Quine-Mc Cluskey. Aceasta metoda are avantajul
ca algoritmul este usor de implementat pe calculator. Pentru prezentarea metodei
vom lua ca exemplu functia: f = S (0, 2, 3, 5, 7, 8, 10, 11, 13, 15)
Etapele de minimizare sunt:
1. Se grupeaza termenii canonici astfel incat termenii din fiecare
grupa sa contina acelasi numar de 1, respectiv 0.
TC x1 x2 x3 x4
0 0 0 0 0
2 0 0 1 0
8 1 0 0 0
3 0 0 1 1
5 0 1 0 1
10 1 0 1 0
7 0 1 1 1
11 1 0 1 1
13 1 1 0 1
15 1 1 1 1
2. Se compara fiecare termen dintr-o grupa cu toti cei din grupa urmatoare,
aplicand relatia de reducere: x1×x2 + x1×x2 = x1. Se grupeaza
termenii care difera printr-o singura variabila (o singura pozitie binara).
Termenul obtinut prin combinare va contine pe pozitia respectiva semnul -.
Comparare Rezultatul compararii
intre x1 x2 x3 x4
0, 2 0 0 - 0
0, 8 - 0 0 0
2, 3 0 0 1 2, 10 - 0 1 0
8, 10 1 0 - 0
3, 7 0 - 1 1
3, 11 - 0 1 1
5, 7 0 1 - 1
5, 13 - 1 0 1
10, 11 1 0 1 7, 15 - 1 1 1
11, 15 1 - 1 1
13, 15 1 1 - 1
In continuare se repeta procedeul de comparare pana cand nu
mai este posibila nici o reducere.
Comparare Rezultatul compararii
intre x1 x2 x3 x4
0, 2, 8, 10 - 0 - 0
2, 3, 10, 11 - 0 1 3, 7, 11, 15 - - 1 1
5, 7, 13, 15 - 1 - 1
Termenii rezultanti, (0, 2, 8, 10), (2, 3, 10, 11), (3, 7, 11, 15) si (5, 7,
13, 15) se numesc implicanti primi IP.
3. Se aleg acei implicanti primi IP care asigura acoperirea minimala a termenilor
canonici TC. Pentru aceasta se construieste un tabel de acoperire, in
care pe coloane se noteaza termenii canonici TC, iar pe linii implicantii primi
IP. In intersectii se noteaza acei termeni canonici TC acoperiti de fiecare
implicant prim IP.
IP TC 0 2 3 5 7 8 10 11 13 15
0, 2, 8, 10 x x x x
2, 3, 10, 11 x x x x
3, 7, 11, 15 x x x x
5, 7, 13, 15 x x x x
Unii dintre implicantii primi sunt implicanti primi esentiali pentru ca acopera
cel putin un termen canonic al functiei, care nu este acoperit de alt implicant
prim. Implicantii primi esentiali vor face parte in mod obligatoriu din
expresia minimizata a functiei. In cazul nostru implicanti primi esentiali
sunt (0, 2, 8, 10) si (5, 7, 13, 15). Pentru termenii canonici care au ramas
neacoperiti, 3 si 11, se observa ca pot fi alesi 2 implicanti primi, (2, 3,
10, 11) si (3, 7, 11, 15), deci exista 2 solutii de minimizare. f = (0, 2, 8, 10) + (5, 7, 13, 15) + (2, 3, 10, 11) = x2x4 + x2x4 + x2x3 si f = (0, 2, 8, 10) + (5, 7, 13, 15) + (3, 7, 11, 15) = x2x4 + x2x4 + x3x4
1.4.4. Minimizarea sistemelor de functii booleene
Sistemele de functii booleene sunt exprimate prin f: Bn ® Bm unde B =A0,
1S. Argumentele pot fi de n variabile si sunt mai multe functii de acest tip:
f1, f2,…, fm.
Pentru a minimiza sistemele de functii se cauta implicanti primi pentru f1,
f2,…, fm si pentru produsele f1×f2, f1×f3…, f1×fm,
… f1×f2×f3,…, f1×f2×f3×f4,…,
… f1×f2×…×fm. Solutia aleasa pentru implementarea
sistemului de functii booleene va fi cea care va fi cea mai avantajoasa din
punct de vedere al circuitelor disponibile si al pretului.
Exemplu: f1(x1,x2,x3) = S (1, 5, 6, 7) f2(x1,x2,x3) = S (1, 4, 5, 6) f3(x1,x2,x3) = S (0, 2, 5, 6, 7)
1. Calculam functiile produs: f1×f2 = S (1, 5, 6) f1×f3 = S (5, 6, 7) f2×f3 = S (5, 6) f1×f2×f3 = S (5, 6), identica cu f2×f3
2. Determinam implicantii primi din functiile simple si din produsele determinate
la punctul 1. Pentru determinarea implicantilor primi se folosesc diagrame Karnaugh
in care se iau toate acoperirile posibile.
Pentru f1: x1 x2x3 00 01 11 10
0 1
1 1 1 1
Pentru f2: x1 x2x3 00 01 11 10
0 1
1 1 1 1
Pentru f3: x1 x2x3 00 01 11 10
0 1 1
1 1 1 1
Pentru f1×f2: x1 x2x3 00 01 11 10
0 1
1 1 1
Pentru f1×f3: x1 x2x3 00 01 11 10
0
1 1 1 1
Pentru f2×f3 si f1×f2×f3: x1 x2x3 00 01 11 10
0
1 1 1
3. Construim un tabel in care capetele de linii vor reprezenta functiile,
iar coloanele vor fi implicantii primi.
Functia Implicanti primi
Indici Expresii Notatii f1 1,56,75,7 x2x3x1x2x1x3 -- f2 1,54,54,6 x2x3x1x2x1x3 -ih f3 0,22,66,75,7 x1x3x2x3x1x2x1x3 gf- f1×f2 1,56 x2x3x1x2x3 e f1×f3 5,76,7 x1x3x1x2 dc f2×f3 = f1×f2×f3 56 x1x2x3x1x2x3 ba
4. Se noteaza IP pe coloana a patra din tabel incepand cu ultimul,
iar cei care apar dublati nu se mai noteaza.
5. Se construieste un tabel al acoperirilor functiilor f1, f2, f3.
Notatii Indicii Functia de unde au rezultat f1 f2 f3
1 5 6 7 1 4 5 6 0 2 5 6 7 a 6 f1×f2×f3 x x x b 5 f1×f2×f3 x x x c 6, 7 f1×f3 x x x x d 5, 7 f1×f3 x x x x e 1, 5 f1×f2 x x x x f 2, 6 f3 x x g 0, 2 f3 x x h 4, 6 f2 x x i 4, 5 f2 x x
6. Determinam acoperirile optime ale functiilor f1, f2, f3.
A(f1) = e,c + e,d,a = A1 + A2 cu e implicant prim esential
A(f2) = e,h + e,i,a = B1 + B2 cu e implicant prim esential
A(f3) = g,c,b + g,c,d, + g,f,d + g,a,d = C1 + C2 + C3 + C4 cu g implicant prim
esential
7. Se scriu toate acoperirile posibile pentru sistemul de functii si se alege
acea acoperire care realizeaza conditiile de pret minim si disponibilitate de
piese. Se face tabelul pentru acoperiri:
Acoperiri Elementele acoperirii Numar de termeni Cost
A1B1C1 e,c,h,g,b 5 11
A1B1C2 e,c,h,g,d 5 10
A1B1C3 e,c,h,g,f,d 6
A1B1C4 e,c,h,g,a,d 6
A1B2C1 e,c,i,a,g,b 6
A1B2C2 e,c,i,a,g,d 6
A1B2C3 e,c,i,a,g,f,d 7
A1B2C4 e,c,i,a,g,d 6
A2B1C1 e,d,a,h,g,c,b 7
A2B1C2 e,d,a,h,g,c 6
A2B1C3 e,d,a,h,g,f 6
A2B1C4 e,d,a,h,g 5 11
A2B2C1 e,d,a,i,g,c,b 7
A2B2C2 e,d,a,i,g,c 6
A2B2C3 e,d,a,i,g,f 6
A2B2C4 e,d,a,i,g 5 11
Avem acoperiri minimale cu 5 termeni. Pentru a calcula costul unei acoperiri
se face suma costurilor implicantilor primi din acoperirea considerata. Costul
unui implicant prim de n variabile din care lipsesc r variabile este n-r, pentru
ca fiecare variabila prezenta necesita un contact, o legatura. n-1
C = S gr ×(n-r) r=0 unde gr este numarul subcuburilor din care lipsesc r variabile.
Pentru acoperirea A1B1C2, care are elementele e,c,h,g,d, avem costul:
2
C = S gr ×(3-r) = g0×3 + g1×2 + g2×1 = 0×3 + 5×2
+ 0×1 = 10 r=0 e = x2x3 c = x1x2 h = x1x3 g = x1x3 d = x1x3
Minimizarea sistemului de functii va fi: f1 = x2x3 + x1x2 f2 = x2x3 + x1x3 f3 = x1x3 + x1x3 + x1x2 = x1x2 + x1 + x3
Datorita reducerii corelate a sistemului de functii apar porti comune mai multor
functii.
Curs 4
CAPITOLUL II
CIRCUITE LOGICE COMBINATIONALE
2.1. Definitii
Circuitele logice combinationale, CLC, sunt un caz particular al sistemelor
secventiale finite sau al automatelor finite, numite automate de grad 0.
Circuitele logice combinationale se caracterizeaza prin faptul ca variabilele
de iesire sunt independente de timp si de starea interna, fiind determinate
numai de variabilele de intrare (starea variabilelor de intrare la momentul
considerat).
Legatura dintre starea iesirii si starea intrarii unui CLC este realizata de
functia de transfer. x1 y1 x2 y2
CLC
xn ym
Oricare functie de iesire y (y1, y2,…, ym) este functie de toate variabilele
de intrare (x1, x2,…, xn). Un CLC se poate descrie astfel: y1 = f1(x1, x2,…, xn) y2 = f2(x1, x2,…, xn)
ym = fm(x1, x2,…, xn)
Functiile se vor exprima in forma canonica disjunctiva FCD sau in
forma canonica conjunctiva FCC.
Independenta fata de timp presupune ca o data cu modificarea variabilelor de
intrare se modifica simultan si variabilele de iesire. Din punct de vedere practic,
datorita intarzierilor produse de circuitele logice si de conexiuni,
modificarea simultana nu este posibila. Ca urmare, pe durata procesului tranzitoriu
de stabilire a variabilelor de iesire, vectorul iesirilor poate lua valori intermediare
diferite de valoarea finala, ceea ce conduce la fenomenul de hazard combinational,
de care trebuie sa se tina cont la proiectarea unui sistem numeric.
In general, la circuitele logice combinationale, vom face abstractie de
proprietatile fizice ale portilor logice, de faptul ca un impuls teoretic difera
de unul real. Vom analiza aceste fenomene doar in cazul hazardului combinational.
2.2. Analiza circuitelor logice combinationale
In cadrul analizei CLC se pleaca de la cunoasterea schemei logice a circuitului
si se urmareste stabilirea functionarii acestuia. Stabilirea expresiei variabilei
de iesire se face de la intrare la iesire, urmarind transformarile variabilelor
de intrare.
Definim ca numar de nivele al unui CLC numarul maxim de porti dintre intrari
si iesiri. Numerotarea nivelelor se face de la iesire inspre intrare. x5 x1 x2 y1 x3 x4 y2 x6 x7
4 3 2 1
Circuitul logic combinational din exemplu are 4 nivele.
Exista si urmatoarea situatie de legaturi intre porti: x1 y x2
x3
Acest circuit are si legaturi inverse. Ultimele porti nu pot fi numerotate,
deci circuitul nu este un CLC.
In CLC sunt admise legaturile inverse (iesirea unei porti dintr-un nivel
inferior sa fie dusa la intrarea unei porti dintr-un nivel superior) cu conditia
ca definitia CLC sa fie respectata.
Algoritm de determinare a legaturilor inverse in CLC a. Se numeroteaza toate portile logice care au ca intrari un subset din multimea
variabilelor de intrare ale circuitului logic (de la 1 la k); b. Se numeroteaza de la k+1 portile care au ca intrari fie intrari ale circuitului,
fie iesiri ale portilor numerotate la punctul a. Daca am reusit sa numerotam
toate portile circuitului logic, acesta este fara legaturi inverse si este circuit
combinational. Daca nu am reusit numerotarea tuturor portilor logice, circuitul
este de tip secvential.
2.3. Sinteza circuitelor logice combinationale
In cadrul sintezei circuitelor logice combinationale se cunoaste functia
pe care trebuie sa o indeplineasca circuitul si se cauta sa se gaseasca
structura acestuia.
Etapele sintezei circuitelor logice combinationale sunt:
1. Enuntul problemei;
2. Alcatuirea tabelului de adevar, definirea functiei sau functiilor;
3. Minimizarea functiei sau functiilor;
4. Desenarea schemei circuitului
Exista mai multe metode de implementare a CLC, diferentiate dupa nivelul de
complexitate al circuitelor integrate folosite.
2.3.1. Sinteza CLC cu circuite integrate SSI
Circuitele integrate de tip SSI -; small scale integration -; au pana
la 50 de tranzistoare integrate pe capsula. Dintre aceste circuite fac parte
portile logice fundamentale: SI-NU (NAND), SAU-NU (NOR), NU (NOT), SI (AND),
SAU (OR), SAU-EXCLUSIV (XOR).
Dupa parcurgerea etapelor de sinteza se face implementarea functiei sau functiilor
logice cu ajutorul circuitelor integrate existente. CLC de tip SSI se folosesc
mai mult pentru adaptarea la aplicatie a circuitelor de tip MSI si LSI standardizate,
care nu satisfac cu exactitate cerintele de proiectare. Ele vor fi utilizate
acolo unde circuitele cu grad inalt de integrare nu pot fi folosite.
2.3.2. Sinteza CLC cu circuite integrate MSI
Circuitele integrate de tip MSI -; medium scale integration -; au
pana la 500 de tranzistoare integrate. Ele ofera structuri mai complexe,
disponibile ca si structuri standard.
Forma functiilor logice pe care dorim sa le implementam cu circuite de tip MSI
trebuie sa fie corelata cu circuitele disponibile. De obicei nu mai este necesara
minimizarea functiilor.
Circuite combinationale uzuale (specializate)
1. Convertoare de cod
Convertoarele de cod sunt CLC care permit trecerea dintr-un cod binar in
altul. La intrarea circuitului se aplica cuvintele unui cod si la iesire se
obtine alt cod. Convertoarele de cod fac compatibila functionarea a 2 sisteme
in care informatia este codificata in mod diferit.
Exemplu: Conversiile din cod Gray in cod binar-zecimal (BCD) si invers
1) Cod Gray ® BCD
Cuvintele de cod in cele doua coduri sunt:
Gray: gn, gn-1,…, g0
BCD: bn, bn-1,…, b0
Reguli: bn = gn g3 g2 g1 g0 b3 b2 b1 b0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 0
0 0 1 0 0 0 1 1
0 1 1 0 0 1 0 0
0 1 1 1 0 1 0 1
0 1 0 1 0 1 1 0
0 1 0 0 0 1 1 1
1 1 0 0 1 0 0 0
1 1 0 1 1 0 0 1
1 1 1 1 1 0 1 0
1 1 1 0 1 0 1 1
1 0 1 0 1 1 0 0
1 0 1 1 1 1 0 1
1 0 0 1 1 1 1 0
1 0 0 0 1 1 1 1
Se construiesc diagrame Karnaugh pentru determinarea functiilor minimizate pentru
b3, b2, b1, b0.
Diagrama Karnaugh pentru b3: g3g2 g1g0 00 01 11 10
00
01
11 1 1 1 1
10 1 1 1 1
Obtinem: b3 = g3
Diagrama Karnaugh pentru b2: g3g2 g1g0 00 01 11 10
00
01 1 1 1 1
11
10 1 1 1 1
Obtinem b2 = g2g3 + g2g3 = g2 + g3
Diagrama Karnaugh pentru b1: g3g2 g1g0 00 01 11 10
00 1 1
01 1 1
11 1 1
10 1 1
Obtinem b1 = g1g2g3 + g1g2g3 + g1g2g3 + g1g2g3 = g1(g2 + g3) + g1(g2 + g3) =
g1 + g2 + g3
Diagrama Karnaugh pentru b0: g3g2 g1g0 00 01 11 10
00 1 1
01 1 1
11 1 1
10 1 1
Obtinem b0 = g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3 + g0g1g2g3
+ g0g1g2g3 + g0g1g2g3 = g2g3(g0 + g1) + … = g0 + g1 + g2 + g3
In general: bn = gn i bi = 1 daca + S gj = 1 j=n-1
0 daca nu
2) Conversia din BCD in Gray: gn = bn gi = bi + bi+1
2. Codificatoare
Codificatoarele sunt CLC la care activarea unei intrari conduce la aparitia
unui cuvant de cod la iesire.
Exemplu: Codificator din zecimal in BCD (binar codificat zecimal)
Zecimal BCD
0 1 2 3 4 5 6 7 8 9 23 22 21 20
0 1 1 1 1 1 1 1 1 1 0 0 0 0
1 0 1 1 1 1 1 1 1 1 0 0 0 1
1 1 0 1 1 1 1 1 1 1 0 0 1 0
1 1 1 0 1 1 1 1 1 1 0 0 1 1
1 1 1 1 0 1 1 1 1 1 0 1 0 0
1 1 1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 0 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0 1 1 0 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0 0 0
1 1 1 1 1 1 1 1 1 0 1 0 0 1
Intrarile sunt active pe 0 logic. De exemplu, daca este activa (adica 0) intrarea
5, pe iesire se va obtine codul in BCD pentru 5, adica 0101.
Functiile pentru iesiri sunt:
23 = 8 × 9
22 = 4 × 5 × 6 × 7
21 = 2 × 3 × 6 × 7
20 = 1 × 3 × 5 × 7 × 9
Codificatorul prioritar este un codificator care are mai multe intrari active
simultan si la iesire se obtine cuvantul de cod care corespunde intrarii
care este cea mai prioritara. Prioritatea creste de la cifra 0 inspre
cifra 9.
3. Decodificatoare
Decodificatoarele sunt CLC la care se activeaza doar una dintre iesiri, pentru
combinatia (codul) corespunzatoare a variabilelor de intrare. Ele au functie
inversa codificatoarelor. Iesirile decodificatoarelor sunt active pe 0 logic
(functioneaza in logica negativa).
I1 y1
Circuite SI-NU
In ym
Numarul iesirilor distincte este m £ 2n.
Exemplu: Decodificator pentru 3 cifre binare.
I2 I1 I0 O7 O6 O5 O4 O3 O2 O1 O0
0 0 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 0 1
0 1 0 1 1 1 1 1 0 1 1
0 1 1 1 1 1 1 0 1 1 1
1 0 0 1 1 1 0 1 1 1 1
1 0 1 1 1 0 1 1 1 1 1
1 1 0 1 0 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1
Functiile pentru iesiri sunt: O7 = I2I1I0; O6 = I2I1I0; O5 = I2I1I0; O4 = I2I1I0;
O3 = I2I1I0; O2 = I2I1I0; O1 = I2I1I0; O0 = I2I1I0.
4. Multiplexoare
Multiplexoarele sunt CLC care permit trecerea datelor de pe una din intrari
la o iesire unica. Selectia intrarii se face printr-un cuvant de cod de
selectie numit si adresa.
I0
MUX y
In-1
sm-1 s0
Cu m linii de selectie se pot selecta 2m intrari. Functia realizata de iesire
este: y = Ik unde k este numarul de combinatii k = sm-1 × 2m-1 + … + s0 × 20
Aplicatiile cele mai importante ale MUX sunt la selectia secventiala a datelor,
conversia paralel-serie a datelor, sisteme de transmisie a datelor pe un singur
canal, implementarea circuitelor logice combinationale cu o singura iesire.
Exemple
1) I0
MUX y
I1 2 : 1
s
Multiplexorul de tip 2:1 are 2 semnale de intrare, I0 si I1, un semnal de selectie
s si o iesire y. In functie de semnalul de selectie avem pentru iesire:
y = I0 × s + I1 × s. s = 0 ® y = I0 s = 1 ® y = I1
Deci multiplexorul lasa sa treaca spre iesire semnalul de pe acea linie de intrare
corespunzatoare lui s.
2) I0
I1 MUX
I2 4 : 1 y
I3
s0 s1
Multiplexorul de tip 4:1 are 4 semnale de intrare, 2 semnale de selectie si
un semnal de iesire. Iesirea va fi: y = I0 × s0 × s1 + I1 × s0 × s1 + I2 × s0 ×
s1 + I3 × s0 × s1
Exista multiplexoare de tip 8 : 1, 16: 1, 32 : 1. Multiplexoarele integrate
au disponibile atat iesirea adevarata cat si cea negata. Ele au
si o intrare de “Enable” pentru validare, care permite o functie
SI suplimentara.
5. Demultiplexoare
Demultiplexoarele sunt CLC care permit transmiterea datelor de pe o intrare
de date comuna pe una din iesirile selectate. Selectarea iesirii se face cu
ajutorul unui cuvant de cod de selectie numit si adresa. y0
I DEMUX yn-1
sm-1 s0
Cu m linii de selectie se pot selecta 2m iesiri. Functiile de iesire sunt:
y0 = sm-1 × … × s0 × I y1 = sm-1 × … × s0 × I
y2m = sm-1 × … × s0 × I
6. Comparatoare numerice
Comparatoarele numerice sunt CLC care permit determinarea valorii relative a
doua numere binare. Comparatoarele pot fi de 1 bit sau de mai multi biti.
Exemplu: Comparator pe 1 bit
Ai y1 y2
Bi y3
Functiile de iesire sunt: y1 = Ai × Bi pentru Ai < Bi, y2 = Ai + Bi pentru Ai = Bi y3 = Ai × Bi pentru Ai > Bi
Acest circuit constituie celula de baza pentru compararea numerelor cu mai multi
biti.
7. Detectoare-generatoare de paritate
Detectoarele-generatoare de paritate sunt CLC cu rol de a determina si genera
paritatea sau imparitatea numarului de variabile de intrare egale cu 1. Bitul
de paritate este utilizat ca metoda de verificare a transferului de date. Sunt
posibile 2 situatii: a. numarul bitilor de 1 + bitul de paritate = numar par b. numarul bitilor de 1 + bitul de paritate = numar impar
Realizarea detectoarelor de paritate se bazeaza pe functia logica SAU-EXCLUSIV
(0 pentru par si 1 pentru impar).
8. Sumatoare-scazatoare
Sumatoarele si scazatoarele sunt CLC care realizeaza adunarea, respectiv scaderea
cifrelor binare.
Semisumatorul este un CLC care efectueaza suma a 2 numere binare de cate
1 bit, fara a tine cont de transportul de la bitul de semnificatie imediat inferioara.
Semisumatorul este:
A0 S0
1/2 S
B0 C0
Valorile pentru suma S0 si transportul spre rangul superior C0 sunt:
S0 = A0 × B0 + A0 × B0 = A0 + B0
C0 = A0 × B0
Sumatorul pentru bitul de rang n este:
An Sn
Cn-1 S
Bn Cn
Valorile pentru suma Sn si transportul Cn pentru rangul superior sunt:
Sn = An × Bn × Cn-1 + An × Bn × Cn-1 + An × Bn
× Cn-1 + An × Bn × Cn-1 =
= (An + Bn) × Cn-1 + (An + Bn) × Cn-1 = An + Bn + Cn-1
Cn = An × Cn-1 + Bn × Cn-1 + An × Bn
Sumatoarele pentru cuvinte binare cu mai multi biti se realizeaza prin interconectarea
sumatoarelor pentru 1 bit. Adunarea se efectueaza in paralel, iar propagarea
transportului in serie.
Semiscazatorul de 1 bit are iesirile:
D0 = A0 × B0 + A0 × B0 = A0 + B0
I0 = A0 × B0
Scazatorul complet de rangul n are iesirile:
Dn = An × Bn × In-1 + An × Bn × In-1 + An × Bn
× In-1 + An × Bn × In-1 = =(An + Bn) × In-1 + (An +
Bn) × In-1 = An + Bn + In-1
In = An × In-1 + Bn × In-1 + An × Bn
Scazatoarele pentru cuvinte binare cu mai multi biti se realizeaza prin interconectarea
scazatoarelor pentru 1 bit.
9. Unitati aritmetico-logice
Unitatile aritmetico-logice sunt CLC care realizeaza operatii de tip aritmetic
si operatii de tip logic.
Curs 5
2.3.2.1. Implementarea functiilor booleene cu circuite MSI
Circuitele integrate de tip MSI cum sunt decodificatorul DCD, demultiplexorul
DEMUX si multiplexorul MUX pot fi considerate circuite universale deoarece genereaza
in interior toti termenii canonici.
Implementarea cu DCD a unei functii booleene nu necesita operatii de minimizare.
La iesirea DCD se obtin toti termenii canonici negati ai formei canonice disjunctive
FCD ai functiei. Realizarea functiei se face cu o poarta logica de tip SI-NU,
cu un numar de intrari egal cu numarul de termeni ai functiei.
Implementarea cu MUX a unei functii booleene se bazeaza pe relatia care defineste
functionarea sa. De exemplu, pentru un MUX de tip 4:1 avem ecuatia iesirii: y = I0 × x1 × x2 + I1 × x1 × x2 + I2 × x1 ×
x2 + I3 × x1 × x2
in care se observa ca exista intrari separate pentru fiecare din cele
4 combinatii ale variabilelor de selectie x1, x2.
Daca avem o functie booleana de n variabile de intrare se pot da factor variabilele
x1 si x2 si se obtin 4 functii de n-2 variabile de intrare, care se vor conecta
la intrarile I0 -; I3 ale unui MUX de tip 4:1. Similar, cu un MUX 8:1 se
pot elimina 3 variabile de intrare, iar cu un MUX 16:1 se pot elimina 4 variabile
de intrare.
Daca avem o functie de 4 variabile se pot elimina 3 variabile prin aplicarea
lor pe intrarile de selectie ale unui MUX 8:1. La cele 8 intrari ale MUX se
vor conecta cele 8 functii de o variabila. Singurele functii posibile de o variabila
sunt: xi, xi, 0, 1. Deci putem implementa orice functie cu 4 variabile de intrare
folosind un singur MUX de 8 cai si fara porti aditionale.
Exemplu
Consideram functia: f = (0, 1, 3, 5, 9, 10, 13, 15) = x3x2x1x0 + x3x2x1x0 +
x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0
Folosim un MUX 8:1 si aplicam variabilele x2x1x0 pe intrarile de selectie. Pentru
a determina intrarile multiplexorului, I0 -; I7, vom face un tabel:
I0 x3 x2x1x0
I1 1 (x3 + x3) × x2x1x0
I2 x3 x2x1x0
I3 x3 x2x1x0
I4 0 x2x1x0
I5 1 (x3 + x3) × x2x1x0
I6 0 x2x1x0
I7 x3 x2x1x0
Implementarea functiei cu MUX este:
En x3
1 x3 x3 f
0 f
1
0 x3 s2 s1 s0
x2 x1 x0
Avantajele implementarii cu MUX:
- se poate implementa functia cu un sigur circuit de tip MUX;
- intrarea de Enable poate fi folosita ca un SI final cu intreaga functie;
- doar o singura variabila trebuie sa fie disponibila si adevarata si negata.
Dezavantajele implementarii cu MUX:
- nu se pot folosi termeni in comun in cazul minimizarii sistemelor
de functii (sisteme cu mai multe iesiri);
- nu se poate face implementarea functiilor la care numarul de termeni este
mai mare decat numarul intrarilor MUX;
- exista multe functii care pot fi implementate comod prin utilizarea de porti
logice ® MUX utilizat doar pentru functii dificile.
Procedura de implementare cu MUX se poate face plecand de la diagrama
Karnaugh. Se construieste o diagrama Karnaugh in care se defineste domeniul
intrarilor I. x3x2 x1x0 00 01 11 10
00 I0 I1 I3 I2
01 I4 I5 I7 I6
11 I4 I5 I7 I6
10 I0 I1 I3 I2
x3x2 x1x0 00 01 11 10
00 1 1 1
01 1
11 1 1
10 1 1
Variabila care variaza este x3. Configuratiile de 1 din diagrama Karnaugh indica
modul de conectare a intrarilor MUX, la x3, x3, 1 sau 0.
I0 = x3; I1 = 1; I2 = x3; I3 = x3; I4 = 0; I5 = 1; I6 = 0; I7 = x3
2.3.3. Sinteza CLC cu circuite integrate LSI
Circuitele integrate de tip LSI -; Large Scale Integration -; au peste
500 de tranzistoare integrate pe capsula. Pentru exemplificarea sintezei CLC
se descriu doua tipuri de circuite din aceasta categorie: ROM (Read Only Memory)
si PLA (Programmable Logic Array), cu varianta FPLA.
2.3.3.1. Sinteza CLC cu memorii de tip ROM
Memoria de tip ROM este numita si memorie fixa sau permanenta. Ea este nevolatila,
continutul ei nu se modifica in timpul functionarii. Structura ei este
stabilita in procesul de fabricatie sau este stabilita de utilizator prin
programare.
I0 O0
DCD Matrice
In-1 Om-1
Memoria ROM este formata din doua niveluri de porti logice: SI (un decodificator)
si SAU-NU (matricea de memorie). DCD din primul nivel primeste codurile de intrare
in binar (n este numarul intrarilor) si activeaza pentru fiecare cod o
iesire din cele 2n. Iesirile DCD se conecteaza sau nu se conecteaza la circuitele
de tip SAU-NU si astfel se memoreaza un 0 sau un 1 logic.
Vectorii de intrare in ROM se numesc adrese si reprezinta codurile in
binar ale numerelor asociate fiecarui cuvant de memorie. Iesirile sunt
de obicei “three-state” sau “open colector” pentru a
permite legarea in paralel cu iesirile altor memorii.
Avem notatiile: n = numarul de biti ai vectorului de intrare (adresa) c = numarul de cuvinte memorate in ROM ® c = 2n b = numarul de biti din fiecare cuvant
Numarul de cuvinte trebuie sa fie putere a lui 2. Modul de organizare a ROM
este specificat prin produsul c x b. Capacitatea memoriei se exprima prin numarul
total de biti memorati: C = 2n x b. Unitatea de masura pentru capacitatea memoriei
este kilobitul (1 Kb = 1024 biti).
Memoriile au o intrare de “Enable” care permite (E = 0) sau inhiba
(E = 1) functionarea ROM. Daca memoria este dezactivata, indiferent de adresare,
iesirile sunt pe semnal logic 1.
Aplicatiile mai importante ale memoriilor de tip ROM sunt:
- memorarea instructiunilor si datelor in sisteme de calcul si automate
secventiale;
- transformari de adresa si inmagazinarea instructiunilor in microprogramare;
- conversii de cod;
- generatoare de caractere;
- generare de secvente de impulsuri;
- implementarea CLC cu un numar mare de variabile de intrare si iesire.
Implementarea CLC cu un numar mare de variabile de intrare si iesire se bazeaza
pe structura interna a memoriei ROM. Pe nivelul de DCD se decodifica toti termenii
canonici. Fiecare cuvant de la intrarea matricei reprezinta de fapt un
termen canonic format din variabilele de intrare. La nivelul urmator se aduna
toti termenii din expresia oricarei functii si rezulta functia de iesire. Lista
de cuvinte din ROM este chiar tabelul de adevar al CLC. La implementarea cu
ROM nu este necesara minimizarea, deoarece sunt memorati toti termenii canonici
si sunt incluse toate posibilitatile de aparitie a acestora in functia
de iesire.
Pentru folosirea eficienta a memoriei ROM in sinteza functiilor booleene,
variabilele de intrare si iesire trebuie codate, astfel incat sa
contina cat mai multa informatie. Se poate codifica orice grup de variabile
care sunt mutual exclusive, adica doar una dintre ele poate fi activa la un
moment dat.
Pentru reducerea numarului de intrari in ROM se utilizeaza des si multiplexoarele.
Exemplu: Sa se implementeze cu ROM functiile: f0(x3,x2,x1,x0) = x3 × x2 × x1 × x0 f1(x3,x2,x1,x0) = x2 × x1 f2(x3,x2,x1,x0) = x3 × x2 × x1 × x0 + x3 × x2 ×
x0 + x3 × x2 × x0 + x2 × x1
Memoria folosita este de tipul:
x3 A3 x2 A2 16 x 4 biti x1 A1 x0 A0 CS
D3D2D1D0
f2 f1 f0
Cu A s-au notat intrarile de adrese, cu D datele si cu CS (chip select), intrarea
de Enable a circuitului.
Continutul inscris in memorie este dat in tabelul urmator:
A3 A2 A1 A0 D3 f2 f1 f0
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 0 0 0 1 0
0 1 0 1 0 0 1 0
0 1 1 0 0 1 0 0
0 1 1 1 0 1 0 0
1 0 0 0 0 1 0 0
1 0 0 1 0 0 0 0
1 0 1 0 0 1 0 1
1 0 1 1 0 0 0 0
1 1 0 0 0 0 1 0
1 1 0 1 0 1 1 0
1 1 1 0 0 1 0 0
1 1 1 1 0 1 0 0
Scopurile urmarite la implementarea cu ROM sunt:
- utilizarea unui numar minim de circuite integrate;
- folosirea integrala a capacitatii memoriei.
Pentru implementarea CLC cu memorii ROM trebuie urmarite urmatoarele etape:
- stabilirea dimensiunii memoriei necesare pentru aplicatia respectiva;
- alegerea tipurilor de circuite de tip ROM cu dimensiuni identice sau cat
mai apropiate de cele stabilite anterior;
- daca nu exista memorii cu dimensiuni identice sau apropiate de cele dorite
se fac transformari de dimensiuni (modificarea numarului de cuvinte sau numarului
de biti pe cuvant);
- stabilirea tabelului de adevar al ROM;
- reducerea dimensiunii ROM atunci cand este posibil prin utilizarea codificarii
intrarilor sau iesirilor si a multiplexarii intrarilor.
2.3.3.2. Sinteza CLC cu PLA
PLA (Programmable Logic Array) este un CLC cu doua nivele de logica programabila,
o matrice de porti SI si o matrice de porti SAU. PLA este de fapt o structura
universala, extinsa, de implementare cu 2 nivele de porti logice. Ambele matrici
sunt programabile, in procesul de fabricatie sau de catre utilizator,
conform aplicatiei concrete. PLA este o structura mobila si se utilizeaza eficient
pentru sisteme cu mai mult de 8 variabile de intrare.
Deoarece la PLA sunt programabile ambele nivele, implementarea se face pornind
de la termenii elementari ai functiei, obtinuti prin minimizarea ei.
Reprezentarea schematica a PLA cu n intrari, m iesiri si p termeni elementari
realizabili este: x1 conexiune programabila
x2
xn
Matrice
SI
1 p
1 f1 conexiune Matrice programabila SAU fm m conexiune programabila
CS
Avantajele implementarii cu PLA fata de implementarea cu ROM se refera la posibilitatea
programarii matricei SI si a complementarii variabilelor de iesire (variabilele
de iesire pot fi programate individual ca active pe 0 sau pe 1).
Aplicatii ale PLA sunt la:
- microprogramare;
- conversii de cod;
- generare de caractere;
- realizare de tabele de functii;
- implementarea automatelor secventiale.
Observatie. Exista circuite integrate cu grad si mai mare de integrare (VLSI)
utilizate in implementare. Amintim dintre acestea FPGA (Field Programmable
Gate Array).
2.4. Hazardul combinational
Datorita intarzierilor produse de circuitele logice si de firele
de legatura ale unui CLC se poate ca starea iesirii circuitului in momentul
modificarii starii variabilelor sa nu coincida cu valoarea functiei corespunzatoare
valorii intrarilor in momentul considerat. Pentru timp scurt circuitul
are o comportare gresita, numita hazard.
Exemplu f(x1,x2,x3) = x1 × x3 + x2 × x3 x1 D1 f’ x3 g D3 f x2 D2 x3 h
Diagrama Karnaugh pentru functie este: x1 x2x3 00 01 11 10
0 1 1 1
1 1
In practica intarzierile D1, D2, D3 ale portilor SI-NU nu
sunt egale, de aceea poate sa apara hazardul combinational si cand se
pune conditia ca doar o singura variabila de intrare sa se modifice la un moment
dat.
Hazardul apare atunci cand starea intrarilor x1x2x3 se modifica de la
010 la 011 sau invers.
x1
x2
x3
D1 g
D2 h
f’
f
D3 tr
D2 > D1 desi starea ar trebui sa fie nemodificata.
Dupa timpul de reactie tr = D1 + D2 va apare la iesire un impuls negativ de
durata Dt = D2 - D1 si in aceasta durata iesirea ia o valoare incorecta.
Eliminarea hazardului static se poate face in cazul in care se impune
ca la un moment dat sa se modifice starea unei singure variabile de intrare.
Pentru realizarea functiei se considera si unii termeni redundanti din diagrama
Karnaugh, astfel incat oricare doi de 1 aflati in casute adiacente
in diagrama sa fie inclusi cel putin intr-un contur luat in
considerare la sinteza schemei.
Pentru exemplul dat se va introduce in expresia functiei termenul x1x2. f = x2 × x1 + x3 × x1 + x3 × x2
x1 g D1 x3 f’ x2 h D2 D3 f x3
x1 i Dt x2
x1
x2
x3
D1 g
D2 h i
f’
f
Observatii
1. Hazardul static poate sa apara si cand D1 > D2, la schimbarea 011
in 000.
2. Proiectarea unui CLC cand se schimba mai mult decat o singura
variabila de intrare la un moment dat, fara sa apara hazard, este mai dificila
sau chiar imposibil de realizat (hazard de functie).
3. Eliminarea sigura a hazardului se poate face luand in considerare
iesirea circuitului dupa un interval de timp mai mare decat intarzierea
maxima din circuit.
Curs 6
CAPITOLUL III
CIRCUITE LOGICE SECVENTIALE
Circuitele logice secventiale, CLS, sunt automate de ordinul 1. Se obtin din
automatele de ordinul 0 (CLC) prin introducerea unor reactii (legaturi inverse).
Sunt alcatuite din circuite logice combinationale si elemente de memorare binara.
Semnalele de iesire ale CLS depind atat de combinatia semnalelor aplicate
pe intrari cat si de starea circuitului. Un CLS este caracterizat printr-o
secventa a semnalelor de iesire si o secventa a starilor elementelor de memorie,
pentru fiecare secventa a semnalelor aplicate pe intrarile circuitului.
Dupa modul de functionare (modul de transmitere a semnalelor) exista 2 categorii
principale de CLS:
1. asincrone -; comportarea este determinata de aplicarea pe intrari a
semnalelor in momente oarecare; starea circuitului depinde de ordinea
in care se schimba semnalele;
2. sincrone -; comportarea este determinata de aplicarea pe intrari a semnalelor
in momente discrete, bine determinate in timp; sincronizarea se
realizeaza cu ajutorul unor impulsuri date de un generator de tact (ceas).
Exemple de CLS: bistabili, numaratoare, registre, memorii RAM.
3.1. Circuite basculante bistabile
Definitie. Circuitele basculante bistabile (CBB sau bistabil) sunt circuite
logice secventiale care au doua stari stabile distincte. Trecerea dintr-o stare
in alta se face la aplicarea unei comenzi din exterior.
Caracteristica principala a CBB este ca sunt sisteme cu memorie (elemente de
memorie binara). Un bistabil poate pastra un timp nedefinit informatia binara
si in acelasi timp starea sa poate fi citita in orice moment. Se
asociaza uneia dintre cele 2 stari ale bistabilului functia de memorare a cifrei
binare 1 si celei de a doua stari functia de memorare a cifrei binare 0. Bistabilul
are 2 iesiri, una care pune in evidenta cifra binara memorata, numita
iesire adevarata si a doua, care pune in evidenta valoarea negata a cifrei
binare memorate, denumita iesire negata.
3.1.1. Bistabilul RS asincron (latch)
Bistabilul RS asincron are 2 intrari de comanda (de date): S (Set) si R (Reset)
si doua iesiri Q si Q (complementare).
Simbolul bistabilului RS asincron este:
S Q
R Q
Tabelul de adevar al bistabilului RS asincron este: tn tn+1
Sn Rn Qt+1
0 0 Qt
1 0 1
0 1 0
1 1 *
Din punct de vedere logic nu are sens sa se faca simultan inscrierea
si st