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