Metode de minimizare a functiilor logice

Metode de minimizare a functiilor logice

            Simplificarea si implicit minimizarea functiilor logice nu este o problema pur teoretica ci depinde in mare si de tehnologia adoptata. Pe de alta parte alegerea circuitului optim din punct de vedere tehnologic este dictata de aspecte tehnice si economice ca:

            - intarzierea maxima impusa semnalelor pentru parcurgerea circuitelor logice;

            - problema hazardului ce reclama renuntarea la forma minimala si adoptarea solutiilor care elimina hazardul;

            - simplificarea constructiei in vederea unei depanari usoare.

            Criteriile de minimizare care s-au impus sunt:

            - reducerea numarului de variabile;

            - reducerea numarului de termeni;

            - reducerea pe ansamblu a variabilelor si termenilor astfel ca suma lor sa fie minima.

            Metode de minimizare pot fi grupate in:

                        - metode grafice;

                        - metode algebrice, dintre care se va prezenta in continuare Metoda diagramei Veitch-Karnaugh.

Metoda diagramei Veitch-Karnaugh

            Aceasta metoda se aplica functiilor logice exprimate sub forma canonica cat si a celor exprimate sub forma elementara. Metoda presupune parcurgerea a doua faze:

            1. Alcatuirea diagramei si introducerea termenilor functiei in casutele diagramei;

            2. Minimizarea propriu-zisa care rezolva doua probleme:

- reducerea numarului de termeni;

- reducerea numarului de variabile din termenii functiei.

            Prima faza comporta doua etape:

            - Etapa I. Se alcatuieste diagrama sub forma de linii si coloane suplimentate cu o linie si o coloana index. Casutele diagramei sunt in numar de 2ⁿ unde n este numarul de variabile. Diagrama Veitch-Karnaugh pentru doua variabile este prezentata in figura 3.1. Fiecare celula reprezinta o combinatie binara a variabilelor de intrare. De exemplu celula aflata pe randul unu coloana unu are valoarea binara 00 ceea ce corespunde expresiei  iar celula aflata in dreapta jos are valoarea 11 corespunzatoare lui AB.

Figura Error! No text of specified style in document..1. Diagrama Veitch-Karnaugh pentru doua variabile.

Pentru n 3 se obtine diagrama cu 8 celule din figura 3.2. Valorile corespunzatoare variabilei C se gasesc pe coloana din stanga iar valorile corespunzatoare variabilelor A si B se gasesc pe primul rand. In celulele diagramei se inscriu cele 8 combinatii posibile intre variabilele de intrare.

Figura Error! No text of specified style in document..2. Diagrama Veitch-Karnaugh pentru trei variabile.

Pentru n 4 se obtine diagrama:

Figura Error! No text of specified style in document..3. Diagrama Veitch-Karnaugh pentru patru variabile.

            - Etapa II. Termenii functiei canonice  complet determinate se introduc sub forma 1 sau 0 in celulele diagramei pana ce acestea se completeaza. Se introduce un 1 in celula daca termenul produs corespunzator combinatiei care caracterizeaza celula exista in expresia functiei si un 0 daca acesta lipseste. Daca functia este nedeterminata cu o nedeterminare de ordinul "r" adica exista r stari pentru care nu se cunoaste valoarea binara atunci in compartimentele necompletate se introduce variabila X care poate sa fie "1" sau  "0". Starile nedeterminate sunt numite si stari indiferente, arbitrare sau redundante. Variabilei X i se atribuie valoarea "1" sau "0" dupa cum contribuie sau nu la formarea de grupe cat mai compacte de "1" (pentru termenii SOP) sau de "0" (pentru termenii SOP) si in numar egal cu o putere a lui 2.

            Faza a doua

            Se marcheaza prin linii continue sau intrerupte respectiv se delimiteaza suprafetele care contin celule care contin "1" (pentru forma SOP), intr-un numar egal cu 2^x unde x 1n-1 pe principiul compartimentelor adiacente. Aceasta etapa rezolva problema reducerii numarului de termeni prezenti in forma initiala si care vor intra in forma minimala elementara. Se mentioneaza ca acelasi "1" poate fi introdus in mai multe grupe in virtutea legilor de idempotenta.

            In etapa urmatoare se transforma termenii canonici marcati anterior in termeni elementari cu mai putine variabile. Numarul de variabile dintr-un termen elementar va fi egal cu n-x.

            Variabila sau variabilele care se suprima se stabilesc astfel: daca in dreptul compartimentelor cu inregistrari de "1" sau "x" grupate pe principiul casutelor adiacente, o variabila sau un grup de variabile isi modifica valoarea, atunci variabila sau grupul de variabile se suprima deoarece valorile functiei nu depind de valoarea acestei variabile. Daca exista mai multe posibilitati de grupare a inregistrarilor de "1" si "x" atunci rezulta mai multe solutii. Dintre solutiile obtinute se retine functia elementara cu numarul cel mai mic de variabile sau solutii in care suma termenilor si a variabilelor este minima. Este indicat ca minimizarea sa se faca atat prin gruparea zonelor de "1" cat si prin gruparea zonelor de "0" si in continuare compararea solutiilor. Daca zonele de "0" sunt in numar mai mic decat zonele de "1" si mai compacte se va opera cu aceste inregistrari.

            Daca elementele logice disponibile sunt de tipul SAU-NU (NOR) atunci se opereaza cu zonele de "0" adica se obtine forma conjunctiva elementara. Daca elementele logice disponibile sunt de tipul SI-NU (NAND) se grupeaza inregistrarile de "1" adica se obtine forma disjunctiva elementara.

            Exemplu: Fie functia F de 4 variabile A, B, C, D data de tabelul de adevar din figura 3.4 :

cu termenii redundanti: si

O exprimare alternativa pentru functia de mai sus este data  de folosirea expresiilor termenilor de tip  produs care intra in definirea functiei: F = P₀ + P₂ + P₃ + P₅ + P₁₀ + P₁₅, cu termenii redundanti: P₇, P₈ si P₁₁.  Unde P₀ reprezinta termenul , P₂ , etc. Implementarea directa a funcției are ca rezultat circuitul din figura 3.5

Figura Error! No text of specified style in document..5. Implementarea funcției F neminimizate.

            Pentru minimizarea funcției se poate folosi metoda diagramei Veitch-Karnaugh.

            Rezolvare: Pentru n 4 rezulta 2⁴ celule astfel:

Figura Error! No text of specified style in document..6. Diagrama Veitch-Karnaugh pentru functia F.

            Se marcheaza termenii "1" in diagrama. Se cauta sa se grupeze locatiile adiacente ce contin "1" in asa fel incat sa fie acoperiti toti termenii de "1", gruparile sa aiba suprafata cat mai mare pentru ca termenul ce corespunde gruparii sa fie cat mai simplu si sa fie cat mai putine grupari pentru a avea cat mai putini termeni. Fiecare celula ocupata de "1" trebuie sa faca parte cel putin dintr-o grupare dar poate fi inclusa in mai multe. Tipuri de grupari posibile: de o locatie, doua locatii pe o linie sau coloana, patru locatii pe linie, coloana sau patrat, opt locatii in dreptunghiuri 4x2 sau 2x4 locatii. Grupand 2^m celule vecine ocupate de unitati se elimina m variabile. Gruparile obtinute sunt prezentate in figura 3.7. Se considera ca fiind celule vecine si cele aflate la extremitati. Astfel sunt vecine celulele de pe coloanele extreme (1 si 4), celulele de pe liniile 1 si 4 precum si celulele aflate in cele 4 colturi.

Figura Error! No text of specified style in document..7. Gruparile realizate pe principiul vecinatatii.

            S-au obtinut 3 grupari deci forma minimizata va contine 3 termeni, iar numarul variabilelor din fiecare termen este n-m. Astfel se obtine forma minimizata:

Figura Error! No text of specified style in document..8. Implementarea functiei F sub forma SOP.

            Functia F poate fi transformata in continuare in vederea utilizarii unui singur tip de porti prin aplicarea teoremelor lui De Morgan. Astfel se obtine:

Figura Error! No text of specified style in document..9. Implementarea functiei F cu circuite SI-NU.

            Se poate observa ca circuitele inversoare au fost inlocuite cu circuite SI-NU avand intrarile legate impreuna.

            De obicei pentru a reduce numarul de capsule utilizate se prefera utilizarea unui singur tip circuite cu acelasi numar de intrari. Functia F poate fi rescrisa folosind legile de asociativitate:

            Operatia SI dintre cei doi termeni ai primei paranteze poate fi efectuata utilizand un circuit SI-NU urmat de un inversor realizat cu un circuit SI-NU. In mod similar se poate judeca si in cazul celei de a doua paranteze. Astfel functia F devine:

Figura Error! No text of specified style in document..10. Implementarea functiei F cu circuite SI-NU cu doua intrari.