I. IMPLEMENTAREA CIRCUITELOR NUMERICE CU PORI LOGICE. II. MINIMIZAREA FUNCIILOR LOGICE I IMPLEMENTAREA CU PORI MINIMIZAREA PORTILOR SI-NU

1. PORI LOGICE

Cnd se trece de la formele fnd, fnc i de la modelele acestora pe baz de operatori NOT, AND, OR, NOR, NAND, la implementrile reale pe baz de circuite electronice pentru operatorii logici se folosete, n exprimare, termenul de poart logic. Pentru realizarea unei funcii de comutaie se pot utiliza circuite de comutaie elementare, care realizeaz funciile elementare, ca de pild porile logice I-NU (NAND), SAU (OR), NU (NOT), I (AND) etc. Prin referirea tuturor circuitelor logice cu termenul de poart logic apare un abuz de limbaj care, totui, are o justificare din punct de vedere al transferului semnalului (variabile logice binare) prin circuit. Reprezentarea modului de realizare a funciei de comutaie a unui circuit numeric folosind pori logice se realizeaz sub forma unui graf orientat numit schem logic. n nodurile acestui graf sunt reprezentate simbolic porile logice care realizeaz funciile Denumire Funcie Simbol Tabel de Tabel de definiie elementare asupra variabilelor de intrare, respectiv adevr asupra ieirilor altor pori x f x f logice, x f = x 0 1 L H reprezentate de arcele grafului. f = Inversor (NOT) Simbolurile folosite pentru reprezentarea circuitelor de comutaie0 elementare i a x 1 H L funciilor realizate de acestea sunt prezentate mai jos: f x1 x1 x2 f x2 x1Poart I (AND)

f = x 1 x2

x2

f=x 1x2

0 0 1 1

0 1 0 1

0 0 0 1 f 0 1 1 1 f 1 1 1 0 f 1 0 0 0

L L

L L

L L L

H H x2 L H L H x2 L H L H x2 L H L H

H H x1 L L H H x1 L L H H x1 L L H H

H f L H H H f H H H L f H L L L

xPoart SAU (OR)

f = x1 + x 2

1

x2 x1 x2

f=x 1+x2

x1 0 0 1 1 x1 0 0 1 1 x1 0 0 1 1

x2 0 1 0 1 x2 0 1 0 1 x2 0 1 0 1

Poart I-NU (NAND)

f = x x2

1

f = x x2

1

Poart SAU-NU (NOR)

f = x1+ x2

x1 x2

f = x1+ x2

1

x1 SAU EXCLUSIV (XOR)

f = x

1

x1 x2 x2

f = x1 x 2

0 0 1 1 x1 0 0 1 1

x2 0 1 0 1 x2 0 1 0 1

f 0 1 1 0 f 1 0 0 1

x1 L L H H x1 L L H H

x2 L H L H x2 L H L H

f L H H L f H L L H

SAU EXCLUSIV NU (NXOR)

f = x

1

x1 x 2 x2

f = x1 x 2

Funciile de comutaie realizate de un circuit numeric pot fi reprezentate, aa cum am m-ai spus, printr-o schem logic. Finalitatea analizei unui circuit numeric creeaz posibilitatea descrierii funcionale formale a circuitului respectiv. Aplicaiile acestei descrieri se refer la: Determinarea comportamentului circuitului pentru diverse combinaii ale intrrilor; Dezvoltarea unor structuri logice distincte, cu acelai comportament logic; Adoptarea descrierii logice a circuitului dat, n vederea implementrii cu alte tipuri standardizate de circuite logice; Utilizarea descrierii funcionale la analiza unor sisteme logice de o mai mare complexitate, care includ circuitul dat. Fiind dat schema logic a unui circuit numeric se poate obine descrierea formal a acestui circuit n mai multe moduri, unul fiind acela n care pornind de la intrri spre ieire se construiesc inductiv expresiile logice care descriu funcional fiecare circuit elementar. Complexitatea soluiei este proporional cu dimensiunea circuitului analizat. Exemplu: Se d schema logic a circuitului numeric din figura 1.1 i se cere reprezentarea funciei sale de transfer. Figura 1.1 Circuit logic combinaional Aplicnd metoda menionat, rezult:a b c d a a b

(a b)+(c d)c d

Figura 1.2 Funcia ce descrie circuitul logic combinaional Sinteza unei funcii logice combinaionale cu pori logice presupune ca o prim etap, minimizarea funciei astfel nct circuitul combinaional obinut s fie de o complexitate ct mai redus. n cazul sintezei funciei combinaionale cu pori I-NU se aplic o dubl complementare funciei date (nu i schimb valoarea) i se utilizeaz teoremele De Morgan, obinndu-se o expresie care conine numai operaii I-NU; fiecrei astfel de operaie i va

2

corespunde n schema logic cte o poart I-NU avnd attea intrri cte variabile are fiecare termen produs logic din expresia logic obinut.Exemplul 1. S se determine funcia F pentru urmtorul circuit utiliznd tabela de adevr.

Se completeaz tabela de adevr corespunztoare circuitului. A0 0 0 0 1 1 1 1

B0 0 1 1 0 0 1 1

C0 1 0 1 0 1 0 1

AB1 1 0 0 1 1 1 1

C1 0 1 0 1 0 1 0

F = AB + C1 1 1 0 1 1 1 1

Exemplul 2. S se realizeze diagrama de semnal pentru funcia f fiind date

variaiile de semnal de mai jos. Circuitul ce descrie funcia f este reprezentat n figura alturat.A B C f

Din circuit rezult funcia f = A + B + C . Tabelul de adevr va fi: A0 0 0 0 1 1 1 1

B0 0 1 1 0 0 1 1

C0 1 0 1 0 1 0 1

f = A+ B+ C0 0 0 0 0 0 1 0

Funcia va avea diagrama de semnal ca n figura de mai jos.A B C f

3

2. MINIMIZAREA FUNCIILOR LOGICE

Algebra boolean se folosete la analiza i sinteza dispozitivelor numerice (circuite de comutaie). ntre gradul de complexitate al circuitului i cel al funciei care l descrie exist o legtur direct. Aceasta este motivaia pentru care, n etapa de sintez a circuitelor de comutaie, dup definirea acestora, urmeaz n mod obligatoriu etapa de minimizare a funciei, avnd drept scop obinerea unor forme echivalente mai simple (forma minim). Soluia minim obinut n urma minimizrii ar trebui s fie cea mai avantajoas (economie de pori logice, obinerea unei scheme mai fiabile, mai ieftine). n realitate nu este ntotdeauna aa. De exemplu, dorina de a obine un sistem uor depanabil poate duce la obinerea unei soluii neminimale, dar care prezint proprieti interesante de simetrie i regularitate. Prin aplicarea metodelor de minimizare (de simplificare) se ajunge la expresii minimale sub forma unor SAU -uri de I -uri (reuniune minimal) ori a unor I -uri de SAU uri (intersecie minimal). - reducerea numrului de minimizrii sunt: Criteriile utilizate n vedereavariabile; - reducerea numrului de termeni; - reducerea pe ansamblu a variabilelor i termenilor, astfel ca suma lor s devin minim. Minimizarea const n principal n transformarea formelor canonice i a formelor elementare parial simplificate n forme elementare minimale. Metodele de minimizare pot fi grupate n metode algebrice i metode grafice.Minimizarea grafic se bazeaz pe proprietatea de adiacen a codului binar

reflectat (Gray) cu ajutorul cruia se numeroteaz liniile i coloanele diagramei Karnaugh. n vederea minimizrii se aleg suprafeele maxime (subcuburi) formate din constitueni ai unitii, respectiv din constitueni ai lui 0, suprafee (subcuburi) avnd ca dimensiune un numr de ptrate (compartimente) egal ntotdeauna cu puteri ale lui 2. Aceste suprafee vor corespunde termenilor canonici, termenii vecini fiind adiaceni (difer printr-un singur bit). Ca urmare, n - se lor se vor grupri de compartimente (subcuburi) + x sunt puteri urma gruprii realizeaz reduce variabilele pe baza relaiei: x 1 x 2care1 x 2 = x 1 . ale lui 2. Un m compartiment Metoda de minimizare: poate fi membru al mai multor suprafee. O suprafa cu 2 celule - vecine va elimina 2m variabile de intrare. se scriu ecuaiile corespunztoare fiecrei suprafee, obinndu-se astfel - termenii elementari. se realizeaz forma normal disjunctiv minim (fnd) prin nsumarea termenilor elementari obinui prin gruparea constituenilor lui 1 sau forma normal conjunctiv minim (fnc) prin nmulirea termenilor elementari obinui prin gruparea de constitueni forma 0; funciile minimale booleene, este util s n proiectare, pentru a se obine ai lui minimal a unei funcii obinute sunt identice, ele se diferind numai prin forma de prezentare. minimizeze ambele forme canonice, fnd i fnc. Apoi, n funcie de disponibilitatea componentelor i de numrul de conexiuni care rezult, se poate alege forma minimal a funciei booleene care va fi implementat.

4

2.1 Minimizarea funciilor logice utiliznd diagrama Karnaugh

O diagram Karnaugh pentru o funcie boolean de n variabile se deseneaz sub forma unui ptrat sau dreptunghi mprit n 2n compartimente. Diagrama Karnaugh este organizat astfel nct dou compartimente vecine pe o linie sau pe o coloan corespund la doi termeni canonici care difer numai printr-o singur variabil, care apare n unul adevrat, iar n cellalt negat (la dou n-pluri adiacente). Se consider vecine i compartimentele aflate la capetele opuse ale unei linii, respectiv coloane. Diagrama Karnaugh se noteaz fie indicnd domeniul fiecrei variabile, fie indicnd pe linie i coloan n-uple de zerouri i uniti corespondente unui compartiment din diagram i ordinea variabilelor. C 00 01 11 10 A Diagramele Karnaugh pentru funcii de 3, 4 variabile sunt:0 1 AB a0 a1 a2 a3 a6 a7 a4 a5 C a0 a1 a2 a3 a6 a7 a4 a5 B

AB CD 00 01 11 10

00 a0 a1 a3 a2

01 a4 a5 a7 a6

11 a12 a13 a15 a14

10 a8 a9 a11 a10

A a0 a1 a3 a2 a4 a5 a7 a6 B a12 a13 a15 a14 a8 a9 a11 a10 D

C

Exemplul 3.

S se exprime funcia F dat prin tabel de adevr, cu fnd, fnc i diagram

Karnaugh.A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 110+

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

F 0 1 1 0 1 1 0 1 1 1 1 0 0 0 0 1

M0 m1 m2 M3 m4 m5 M6 m7 m8 m9 m10 M11 M12 M13 M14 m15

fnd= P 1+ P 2+P 4+P 5+ P 7+ P 8+ P 9+ P15=

P

15=m 1+m 2+m 4+m 5+m 7+m 8+m 9+m 10+m

= ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + + ABCD + ABCD + ABCD fnc= S 0S 3S 6S 11S 12S 13S 14= M 0M 3M 6M 11M 12M 13M 14= = D) A

( (+ B + C + D) D)

(A+

B+ C+ A+ B+ C+ D

)( A + B + C + D)( A + B + C + D)( A + B + C + D)( A + B + C +5

Diagrama KarnaughAB CD 00 01 11 10

00 0 1 0 1

01 1 1 1 0

11 0 0 1 0

10 1 1 0 1

Exemplul 4. S se minimizeze i s se implementeze cu pori funcia:

F = P 3+ P 7+ P 8+ P 9+ P

12+

P

13

+P15

Pentru a minimiza funcia trebuie mai nti s completm tabelul de adevr (15=1111). n Se observ c corespunztor.tabelul de adevr funcia F v-a fi de 4 3, P 7, P 8, P deoarece P 15, iar n termen este 1 la: P variabile 9, P12, 13 i ultimul rest P este 0. este P15A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 F 0 0 0 1 0 0 0 1 1 1 0 0 1 1 0 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

AB CD

00 0 0 1 0

01 0 0 1 0

11 1 1 1 0

10 1 1 0 0

00 01 11 10

Din diagrama Karnaugh rezult c: F = AC + ABD + ACD

6

Exemplul 5.

S se minimizeze funcia: F = P 0+ P 2+ P 8+ P10

Tabelul de adevr corespunztor funciei i diagrama Karnaugh sunt:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 F 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0

CD

AB

00 01 11 10

00 1 0 0 1

01 0 0 0 0

11 0 0 0 0

10 1 0 0 1

Din diagrama Karnaugh se obine: F = B D

2.2. Diagrame Karnaugh pentru funcii incomplet definite

Funciile incomplet definite sunt cele care n anumite puncte ale domeniului de definiie pot lua valoarea 0 sau valoarea 1. Avem dou posibiliti: - combinaii de intrare pentru care funcia are valori indiferente (nedefinite); - combinaii ale variabilelor care nu pot s apar din punct de vedere fizic; n aceste situaii trebuie studiat dac combinaiile sunt susceptibile s se produc n urma unei manevre false sau n urma unui defect de funcionare; pentru a evita funcionarea greit, n locaiile corespunztoare se din valori pentru Valorile nespecificate precum i locaiile corespunztoareimpundiagrama Karnaugh se funcie, numesc indiferente sau arbitrare sau redundante. Ele se noteaz cu x i vor fi considerate n astfel nct s nu se perturbe funcionarea normal. timpul minimizrii ca avnd valoarea 1 sau 0, n funcie de situaie, pentru a se obine o minimizare ct mai bun.

7

Exemplul 6. S se minimizeze i s se exprime cu ajutorul funciei I-NU funciile:

,P a. F 1 = P 1+ P 5+ P 9+ P 13 cu termenii redundani P 2, P 3, P 6, P 7, P10,14, P15; P b.11 F 2 = P 3+ P 7+ P 8 + P 10+ P 11 + P 15 cu termenii redundani P 1, P 9, P 13; c. F 3 = P 0+ P 2+ P 4+ P 6 + P 8 + P 10+ P 12+ P 13+ P 14 cu termenii redundani P P 5, P 7, P11, P15. a.AB CD 00 01 11 10 00 0 1 x xde Morgan

1,

P3,

01 0 1 x x

11 0 1 x x

10 0 1 x x

F= D

F = D

D F

b.AB CD 00 01 11 10

00 0 x 1 0

01 0 0 1 0

11 0 x 1 0

10 1 x 1 1

F = C D+ A B C D B

de

Morgan

F = C D + A B = C D A

B

F

A

c.AB CD 00 01 11 10

00 1 x x 1

01 1 x x 1

11 1 1 x 1

10 1 0 x 1

F= B+ D

de

Morgan

F = B + D = B

B

D

F

D

8

2.3. Extragerea unei funcii logice din diagrame Karnaugh n care au fost introdu-se, pe lng valori, i funcii logice.

Algoritmul de extragere comport dou etape: 1. se extrage funcia logic introducnd valoarea 0 n locaiile n care se afl funcii logice; 2. la funcia astfel obinut se sumeaz logic (OR) funcia obinut prin reintroducerea n tabel a funciilor; suprafeele se vor defini astfel nct s cuprind aceeai funcie iar valoarea lor se va nmuli logic (AND) cu produsul asociat suprafeei.Exemplul 7. Se consider funcia dat prin tabelul de adevr:

A 0 0 1 1

B 0 1 0 1

F C

C0 0

Implementarea cu diagram Karnaugh i minimizare conduce la:BA 0 1 0 C 1 0 0

C

- pas 1 - se consider C = 0 i rezult:A B 0 1 0 0 1 0 0

C

F1 = ABC

-

pas 2 - se consider C = 1 i rezult:A B 0 1 0 C 0 1 0 0

F2 = ABC

Astfel nct funcia va fi n final de forma:F= F1

+ F

2

= A B C + A B C

9

Exemplul 8. Se consider funcia dat prin tabelul de adevr: A 0 0 1 1 B 0 1 0 1 F C

C0 1

Implementarea cu diagram Karnaugh i minimizare conduce la:BA 0 1 0 C 1 0 1

C

- pas 1 - se consider C = 0 i rezult:A B 0 1 0 0 1 0 1

C

F1 = BC

-

pas 2 - se consider C = 1 i rezult:A B 0 1 0 C 0 1 0 1

F2 = A B C + A B

Astfel nct funcia va fi n final de forma:F= F1

+ F

2

= B C + A B C + A B

Pentru implementarea hardware a unor astfel de circuit logice analizate se pot folosi circuite integrate TTL (Tranzistor Tranzistor Logic) care pot fi identificate prin nscrisul de pe capsul, care conine un grup de litere ce reprezint (prescurtat) numele firmei productoare i un grup de cifre, care indic tipul circuitului integrat ai crui parametri se regsesc n cataloagele de circuite integrate ale firmelor productoare. Tipurile de circuite integrate ce conin pori I-NU sunt: 404 - 6 pori inversoare cu o intrare 400 - 4 pori I-NU" cu 2 intrri 410 - 3 pori I-NU" cu 3 intrri 420 (440) - 2 pori I-NU" cu 4 intrri 430 - o poart I-NU" cu 8 intrri Un parametru electric al ieirii unei pori logice integrate, care trebuie luat n considerare la implementarea unui circuit numeric este factorul de ncrcare la ieire (FE) 10 care

exprim numrul de intrri pe care le poate comanda o ieire a unei pori. Definirea factorului de ncrcare la intrarea unei pori (FI) i la ieirea unei pori (FE) se face plecnd de la valorile curenilor corespunztori tensiunilor limit admii la intrare respectiv tensiunilor limit garantate la ieire pentru cazul cel mai defavorabil. n cazul porilor I-NU standard, factorul de ncrcare la ieire este 10 (circuitul 420) i 20 dac poarta este de putere (circuitul 440). Intrrile porilor logice TTL nefolosite nu se recomand s fie meninute neconectate, deoarece pot colecta tensiuni de zgomot. Aceste intrri pot fi conectate la un potenial neutru, care s nu influeneze logica funciei de ieire, la mas - 0", la +5V tensiunea de alimentare a circuitului prin intermediul unei rezistene de 1 k , sau la o intrare folosit dac factorul de ncrcare la ieire (FE) a porii permite acest lucru:

Figura 1.3 Moduri de conectare a intrrilor neutilizate a unui circuit integrat TTL Porile TTL nu admit conectare n scurtcircuit a dou sau mai multe ieiri, motivul fiind apariia posibilitii ca o singur poart s aib ieirea la 0" i toate celelalte la 1". n acest caz poarta care are la ieire 0" preia curenii de sarcin (Is) ai celorlalte pori (figura 1.4) ceea ce conduce la creterea nivelului de tensiune, pentru 0", existnd i posibilitatea distrugerii tranzistoarelor etajului de ieire (T 11) datorit curenilor mari: (n-1)Is.

Figura 1.4 Conectarea n scurtcircuit a ieirilor a n pori TTL Conectarea n scurtcircuit a ieirilor porilor logice este admis n cazul utilizrii circuitelor cu colector deschis (cnd rezistena de colector, R n, a etajului de ieire este calculat i adugat de utilizator), sau a circuitelor de tip trei stri (figura 1.5):

11

Circuit 4125 - 4 pori neinversoare trei stri

A 0 0 1 1 Circuit 4126 - 4 pori neinversoare trei stri

I 0 1 0 1

E 0 1 nalt impedan nalt impedan

A 0 0 1 1

I 0 1 0 1

E nalt impedan nalt impedan 0 1

Figura 1.5 Pori logice trei stri Se observ din tabelul de funcionare al acestor circuite c funcie de valoarea binar a semnalului de autorizare A, ieirea este identic cu intrarea sau trece n starea de nalt impedan. Necesitatea realizrii funciei logice cablate prin legarea n scurtcircuit a ieirilor porilor, apare frecvent n sistemele de calcul n care circulaia informaiei se realizeaz prin magistrale de informaie (BUS), figura 1.5.

D i - date transmise pe magistral O i - date recepionate de pe magistral DIEN- comand de transmisie/recepie date

Figura 1.5 Utilizarea circuitelor trei stri pentru conectarea la magistrala de informaie

12

S se implementeze cu pori I-NU, pori I-SAU-NU funciile de mai jos preciznd tipul i numrul de circuite integrate TTL necesare, funcia:Exemplul 9.

F= Sinteza funciei cu pori I-NU:X1

(2,3,8,9,12,13)

X X X0 00 3 2 0 0001 11 10

01

11

10

00 4 1

13

12

0 1

0 1

5

0 0

7

0 0 0

6

12

13

15

18

19

011

10

F1min = X 1 X 2 X 3 + X 1 X3 Schema logic cu pori I-NU: F1min = X 1 X 2 X 3 + X 1 X 3 = X 1 X 2 X 3 X 1 X 3

Dac variabilele de la intrarea circuitului nu sunt disponibile n forma negat se poate obine urmtoarea implementare posibil:X12 1 13 9 10 3 4 5 5 6 4 3 6 11 12

X21 2

X3

8

404

410

13

Sinteza funciei cu pori I-SAU-NU:X X 1 X0 3 00 X200 01 11 10 01 11 10

0 0 1

00 4 1

13

12

0 1

5

0 0

7

0 0

6

12

13

15

14

1

8

1

09 11

010

F1min = X 1 X 3 + X 2 X 3 + X 1 X 3 Schema logic cu pori I-SAU-NU: F1min = X 1 X 3 + X 2 X 3 + X 1 X 3

Nedispunnd de variabile complementate, se poate obine circuitul: 454 404 X X3 1 1 4 5 13 2 3 4 5 9 10 8 2 1

X2

F2 ( X0 ,X 1 ,X ,X 2

)3 = ( )3

0,1,2,3,4,8,9,10,11) i N{5} =

F3 ( X0 ,X 1,X 2 ,X

(

0,1,6,7)

Utilizarea diferitelor tipuri de circuite integrate TTL la implementarea unui circuit combinaional necesit informaii de catalog referitoare la schema logic integrat, numrul i semnificaia terminalelor circuitului, tensiuni de alimentare, etc. Spre exemplu, circuitul 400, (4 pori I-NU cu 2 intrri) are urmtoarea reprezentare:Vcc

14

13

12

11

10

9

8

a e c

b

d

1

2

3

4

5

6

f

7 GND

Figura 1.6 Circuitul logic integrat TTL 400 (Privire de deasupra circuitului - se vede nscrisul pe circuit)

a, b, c, d - pori I-NU cu 2 intrri e - cheia circuitului (o adncitur), pe o latur mic a capsulei f- terminalele circuitului VCC - Tensiunea de alimentare (curent continuu) GND - Masa (electrica) Numerotarea terminalelor circuitului se face, ca n figura 4.6 considernd

privit capsula de deasupra, cu circuitul poziionat cu cheia n stnga. Utilizarea terminalelor circuitului se face n concordan cu conexiunile interne reprezentate n schema logic a acestuia (figura 1.6). Astfel pentru pori I-NU (a), terminalele (pinii) 1, 2 sunt intrri iar 3 este ieire. Prin intermediul pinului 7 (ground) i 14 (tensiune curent continuu), circuitul se alimenteaz la tensiunea de +5V. Verificarea funcionarii circuitelor a cror funcii de transfer sunt funciile F 1, F 2, F 3 se face genernd la intrrile circuitului toate combinaiile binare distincte i comparnd valorile rezultate ale ieirilor cu cele date prin specificarea funciilor logice F 1, F 2 i F 3.