APLICAIA 2.MINIMIZAREA FUNCIILOR LOGICE

1 2 2.1. REPREZENTAREA FUNCIILOR LOGICE PRIN FORME DISJUNCTIVE. MINIMIZAREA N FORMA DISJUNCTIV. ELIMINAREA HAZARDULUI STATIC

2.1.1. Moduri de reprezentare a funciilor logice. Forma canonic disjunctiv (FCD) i forma canonic conjunctiv (FCC)

O funcie logic poate fi reprezentat n forma analitic (operaii algebrice ntre variabile) sau n forma tabelar (tabele de adevr, diagrame Karnaugh). Pentru o funcie logic dat exist mai multe expresii analitice echivalente, dar un singur tabel de adevr i o singur diagram Karnaugh. Dintre formele analitice, cele mai folosite sunt cele disjunctive i cele conjunctive. Se spune c o funcie logic este n form disjunctiv dac expresia ei analitic este o sum de produse logice (2.1):

(2.1)

unde pi sunt produse de variabile normale sau negate ale spaiului logic Sn. n cadrul unui produs logic, numele variabilelor nu se repet. Dac toi termenii pi sunt mintermeni (adic fiecare produs conine toate variabilele, normale sau negate), atunci reprezentarea (2.1) se numete form canonic disjunctiv (FCD). Pentru un spaiu Sn , avem 2n mintermeni posibili. Mintermenii se pot scrie din cuvintele de cod corespunztoare de n bii, atribuind variabila normal pentru simbolul 1 i variabila negat pentru simbolul 0.Se spune c o funcie logic este n form conjunctiv dac expresia ei analitic este un produs de sume logice (2.2):

(2.2)

unde si sunt sume din variabile normale sau negate.Dac toi termenii si sunt maxtermeni (adic fiecare sum conine toate variabilele, normale sau negate), atunci reprezentarea (2.2) se numete form canonic conjunctiv (FCC). Pentru un spaiu Sn, avem 2n maxtermeni posibili care se pot scrie din cuvintele de cod corespunztoare de n bii, atribuind variabila normal pentru simbolul 0 i variabila negat pentru simbolul 1.Folosind proprietile algebrei logice, sau direct, din tabelul de adevr, orice funcie poate fi adus la forma canonic disjunctiv sau la forma canonic conjunctiv. Pentru o funcie logic dat FCD i FCC sunt unice. Astfel, din tabelul de adevr se poate scrie direct FCD, prin relaia (2.3), iar FCC, prin relaia (2.4):

, (2.3)

(2.4)

unde ai este valoarea funciei f din tabelul de adevr corespunztoare mintermenului mi, respectiv, bi este valoarea funciei f din tabelul de adevr corespunztoare maxtermenului Mi.

2.1.2. Minimizarea funciilor logice n forma disjunctiv Pentru o implementare eficient a unei funcii logice intereseaz ca numrul de pori logice i numrul de intrri ale porilor s fie ct mai mici. Aceste numere pot fi reduse la o form minimal, echivalent, prin mai multe metode: metoda analitic, metoda diagramelor Veitch Karnaugh, algoritmul Quine Mc Cluskey. Metoda analitic folosete proprietile algebrei logice. Acest metoda este greoaie i se aplic doar pentru expresii de ntindere mic.Metoda diagramelor Veitch Karnaugh utilizeaz diagramele bidimensionale codate ciclic (Cod Gray i pe orizontal i pe vertical) pentru reprezentarea spaiului logic Sn i a funciei logice. Dac un subspaiu al lui Sn (n care variabilele logice corespunztoare apar cu ambele valori 0 i 1) este acoperit de funcia logic respectiv (n toat zona sunt valori ale funciei egale cu 1), atunci acest subspaiu (variabilele logice respective) poate fi eliminat din expresiile mintermenilor respectivi, care se nlocuiesc cu un produs format din variabilele rmase. Acest lucru este posibil doar dac 1 urile din diagram sunt adiacente pe orizontal i/sau pe vertical (adiacent nseamn distan 1 ntre cuvintele de cod corespunztoare, adic acestea s difere ntr-un singur bit). Se vor avea n vedere grupri de cte 2k elemente, k1. Referitor la aceast metod, trebuie s se in seama de urmtoarele observaii: i) Pentru simplificri eficiente, se caut s se pun n eviden subspaii acoperite ct mai mari (grupri ct mai mari); ii) Un punct poate fi folosit n mai multe grupri; iii) Metoda este eficient n cazul funciilor cu un numr mic de variabile i nu este comod pentru proiectarea software.Algoritmul Quine Mc Cluskey este mai comod de implementat software datorit unei mai bune sistematizri. El se poate aplica pentru minimizarea funciilor cu un numr mare de variabile. Pentru alctuirea algoritmului, se pleac de la mintermenii prezeni n tabelul de adevr al funciei. Acetia se reordoneaz ntr-un alt tabel n care, pe coloana 1 se pun numele corespunztoare mintermenilor, pe coloana 2 se pun reprezentrile binare ale mintermenilor, pe coloana 3 se pun rezultatele iteraiei 1, pe coloana 4 se pun rezultatele iteraiei 2 .a.m.d.Ordonarea se face pe grupe: grupa 0 care are numai mintermeni cu variabile negate (numai 0), deci conine un singur mintermen, grupa 1 care are mintermeni cu o singur valoare de 1 (o singur variabil nenegat), grupa 2 care are dou valori de 1 .a.m.d. Se observ c dou grupe adiacente difer printr-un singur bit. Elementele fiecrei grupe sunt implicani. Un implicant este un produs logic p, cu proprietatea c, dac p = 1, atunci, valorile logice ale variabilelor corespunztoare lui p, nlocuite n f, conduc, de asemenea la f = 1. Un implicant p se numete prim dac, eliminnd o component a sa, nu mai are loc aceast proprietate. ntr-o diagram Karnaugh, implicanii primi corespund celor mai mari grupri care acoper spaiul respectiv. O form disjunctiv minimal este o sum de implicani primi. Iteraia 1 const n urmtoarele: Se consider elementul din grupa 0 a coloanei 2 i se caut un element pereche din grupa 1 a aceleai coloane care s difere de primul printr-un singur bit (evident are un 1 n plus). Acestei perechi de implicani i va corespunde un implicant n coloana urmtoare (se trece acest element n coloana 3), ce va avea n-1 variabile: cele identice din implicanii pereche, iar n locul variabilei lips se va pune simbolul . Algoritmul continu, baleind de sus n jos coloana 2, comparnd elementele din grupa i cu elementele din grupa i+1, pn la finalul coloanei. Implicanii pereche se marcheaz cu , iar implicantul rezultat prin comasare se trece n coloana urmtoare (care, de asemenea, se organizeaz pe grupe). Implicanii nepereche se marcheaz cu * i vor fi implicani primi.Se trece apoi la iteraia 2 (completarea coloanei 4), comparnd (ca mai sus) termenii din grupele adiacente din coloana 3. De acest dat, n dou grupe se compar doar termenii care conin simbolul n aceeai poziie. Procedeul continu, adaugnd coloane n dreapta pn la epuizarea posibilitilor de comparare.Evident, coloanele din dreapta vor avea din ce n ce mai puini implicani, iar ultima coloan va avea doar implicani primi.Toi mintermenii se regsesc n mulimea implicanilor primi, care, de regul, este redundant.Dup obinerea implicanilor primi, pentru a obine forma minimal a lui f se procedeaz astfel: Se observ i se marcheaz mintermenii care apar intr-un singur implicant prim. Aceti implicani se numesc implicani primi eseniali. Dintre implicanii primi rmai se selecteaz un numr minim care s acopere toi ceilali mintermeni. O form minimal a funciei logice va avea expresia obinut prin sumarea logic a implicanilor primi eseniali i a implicanilor primi selectai, obinui prin nlocuirea lui 1 cu variabila normal corespunztoare, nlocuirea lui 0 cu variabila negat i eliminarea simbolului .

2.1.3. Eliminarea hazardului static din forma minimalHazardul static n 1 poate fi prezent n cazul formelor disjunctive, atunci cnd exist dou combinaii de intrare care se deosebesc printr-o singur variabil i au, ambele, ieirile corespunztoare egale cu 1. Pentru eliminarea hazardului se pot introduce termeni suplimentari (redundani), obinnd o nou funcie logic, echivalent din punctul de vedere al comportrii ideale cu cea iniial, dar care nu mai prezint fenomenul de hazard. O metod simpl de eliminare a hazardului n 1 este metoda diagramelor Karnaugh. n acest caz, toate gruprile de 1, selectate pentru minimizare, trebuie s fie nlnuite (s nu fie separate). Termenii suplimentari introdui fa de forma minimal elimin glitch-urile, susinnd valoarea 1 pe aceast durat, i se numesc termeni de consens.

2.2. MODUL DE LUCRU. MONTAJE I REZULTATE EXPERIMENTALE

2.2.1. Tem laborator T1. ExempluSe d funcia logic n forma disjunctiv (2.5):

(2.5)i) S se fac montajul pentru funcia logic y folosind echipamentul din Anexa 1 i un modul din Anexa 2 (Fig.2.1). Pe cale experimental s se completeze tabelul de adevr dnd toate valorile posibile variabilelor de intrare. Pe baza tabelului s se scrie forma canonic disjunctiv yFCD .

Fig. 2.1. Schema de montaj pentru implementarea circuitelor logice combinaionale

Indicaie: Considernd valorile 1 ale funciei se obine (2.6):

(2.6)

ii) S se minimizeze funcia y utiliznd diagrama Karnaugh. S se fac montajul pentru forma minimizat yM a funciei folosind echipamentul din Anexa 1 i un modul din Anexa 2. Pe cale experimental s se completeze tabelul de adevr a lui yM i s se compare cu tabelul de adevr al lui y. Ce se observ?Indicaie: Dispunnd de tabelul de adevr se obine imediat diagrama Karnaugh (Fig. 2.2). Se observ c sunt dou grupri care dau cele dou produse logice din (2.7), iar forma minimizat este:

(2.7) 10 10100 x1 x0 x2110 00 0111 0 1

Fig. 2.2. Minimizarea cu ajutorul diagramei Karnaugh

iii) S se elimine hazardul static din forma minimal. S se fac montajul pentru forma minimizat fr hazard static yMC a funciei folosind echipamentul din Anexa 1 i un modul din Anexa 2. Pe cale experimental s se completeze tabelul de adevr a lui yMC i s se compare cu tabelul de adevr al lui y. Ce se observ?Indicaie: Deoarece gruprile adiacente din diagrama Karnaugh (Fig. 2.3) nu sunt nlnuite, trebuie introdus un termen de consens (evident, avnd ct mai puine variabile). Acesta este marcat cu linie ntrerupt i reprezint ultimul produs din (2.8). Astfel, forma minimal care conine termenul de consens (forma minimal fr hazard static) are expresia urmtoare:

(2.8)

1010100 x1 x0 x2110 00 0111 01

Fig. 2.3. Introducerea termenului de consens

iv) S se minimizeze funcia utiliznd algoritmul Quine Mc Cluskey.

Indicaie: Pentru aceasta, pornind de la tabelul de adevr, se completaz tabelele de mai jos. Primul (Tabelul 2.1) se refer la determinarea tuturor implicanilor primi (notai prin *) obinui prin marcarea implicanilor nepereche din algoritmul descris mai sus. n al doilea tabel (Tabelul 2.2) se selecteaz implicanii primi strict necesari pentru acoperirea tuturor mintermenilor. Se observ c mintermenul m2 este acoperit doar de implicantul prim i mintermenul m5 este acoperit doar de implicantul prim , deci aceti implicani primi sunt eseniali i vor fi necesari pentru includerea n foma minimal. Pe de alt parte cei doi implicani primi acoper mpreun mintermenii rmai, m0 i m1. Rezult c suma celor doi implicani primi eseniali reprezint forma minimal a funciei i se observ c are aceasta are expresia (2.7).

Tabelul 2.1. Determinarea tuturor implicanilor primi.MintermenReprezentare binaraEtapa I

Col.Nr123

0m0

000(0,1)00*

1m1

001(0,2)00*

2m2

010(1,5)01*

5m5

101

Tabelul 2.2. Selectarea implicanilor primi Minter. Impl.m0m1m2m5

00

XX

00

XX

01

XX

2.2.2. Tem laborator T2.Se d funcia logic n forma disjunctiv (2.9):

(2.9)i) S se fac montajul pentru funcia logic y folosind echipamentul din Anexa 1 i un modul din Anexa 2 (Fig.2.1). Pe cale experimental s se completeze tabelul de adevr dnd toate valorile posibile variabilelor de intrare. Pe baza tabelului s se scrie forma canonic disjunctiv yFCD .ii) S se minimizeze funcia y utiliznd diagrama Karnaugh. S se fac montajul pentru forma minimizat yM a funciei folosind echipamentul din Anexa 1 i un modul din Anexa 2. Pe cale experimental s se completeze tabelul de adevr a lui yM i s se compare cu tabelul de adevr al lui y. Ce se observ?iii) S se elimine hazardul static din forma minimal. S se fac montajul pentru forma minimizat fr hazard static yMC a funciei folosind echipamentul din Anexa 1 i un modul din Anexa 2. Pe cale experimental s se completeze tabelul de adevr a lui yMC i s se compare cu tabelul de adevr al lui y. Ce se observ?iv) S se minimizeze funcia utiliznd algoritmul Quine Mc Cluskey.

2.2. TEM DE CAS2.3.1. Sa se implementeze funcia logic (2.10) ntr-o form disjunctiv utiliznd pori logice integrate comerciale.

(2.10)

2.3.2. S se fac tabelul de adevr i apoi s se implementeze funcia logic (2.10) n form canonic disjunctiv utiliznd pori logice integrate comerciale.2.3.3. Utiliznd tabelul de adevr s se implementeze funcia logic (2.10) n form canonic conjunctiv utiliznd pori logice integrate comerciale.2.3.4. Utiliznd forma disjunctiv s se minimizeze funcia prin metoda diagramei Karnaugh. S se fac montajul pentru forma minimizat yM a funciei folosind pori logice integrate comerciale.2.3.5. S se elimine hazardul static din forma minimal. S se fac montajul pentru forma minimizat fr hazard static yMC a funciei folosind pori logice integrate comerciale.2.3.6. S se minimizeze funcia utiliznd algoritmul Quine Mc Cluskey. Pe baza acestui algoritm s se fac un program adecvat pentru minimizarea funciei logice.

4