Minimizarea functiilor logice folosind diagrame Veitch-Karnaugh

Minimizarea functiilor logice folosind diagrame Veitch-Karnaugh

Reprezentarea functiilor logice nu este unica, aceeasi functie logica putând avea mai multe reprezentari. Prin urmare aceeasi functie logica poate fi implementata cu diverse scheme si diverse circuite de comutare. Din multimea variantelor de implementare a unei functii logice unele pot fi preferate în raport cu altele din diverse motive: simplitate, economicitate, fiabilitate, etc. Pentru a alege expresia minima a unei functii logice trebuie folosit un criteriu de performanta. Dintre criteriile de performanta existente mai frecvent utilizate sunt urmatoarele:

numar minim de litere în expresia functiei logice;

numar minim de termeni în forma normala a functiei;

numar minim de capsule integrate necesare la implementarea functiei.

Criteriul numarului minim de litere în expresia functiei logice este utilizat mai des în schemele cu relee unde numarul de litere este egal cu numarul de contacte folosite.

Forma normala disjunctiva sau conjunctiva se foloseste atunci când se cere viteza mare de lucru. Formele normale se implementeaza cu circuite de comutare plasate pe doua nivele obtinându-se intârzieri minime în propagarea semnalelor.

În schemele cu circuite integrate costul global al instalatiei este, în general, proportional cu numarul capsulelor integrate, de unde rezulta cerinta de a minimiza numarul capsulelor folosite.

În cele ce urmeaza se va considera minimizarea functiilor logice în forma normala. O expresie normala a unei functii este minima daca contine un numar minim de termeni, cu conditia sa nu existe o alta expresie normala cu acelasi numar de termeni, dar cu un numar mai mic de litere.

1. Minimizarea functiilor logice folosind diagrame Veitch-Karnaugh

1.1. Minimizarea functiilor logice în forma normala disjunctiva

Cunoscând ca la reprezentarea functiilor logice prin diagrame Veitch-Karnaugh se introduce valoarea logica “1” în celulele diagramei corespunzatoare combinatiilor de valori ale variabilelor functiei pentru care aceasta ia valoarea “1”, metoda minimizarii cu diagrame Veitch-Karnaugh urmareste gruparea acestor celule într-un numar minim de configuratii rectangulare de dimensiuni cât mai mari si exprimarea acestor grupari sub forma unor produse logice al acelor variabile care în cadrul gruparii nu-si schimba valoarea.

Pentru prezentarea metodei se vor defini în prealabil notiunile de implicatie, implicant, implicant prim si implicant prim esential, folosindu-ne pentru aceasta de functiile si definite în fig.2.5.

Implicatia: se zice ca o functie f ‘ implica o alta functie f “ daca pentru orice combinatie a variabilelor pentru care f ‘ ia valoarea logica 1, f “ ia deasemenea valoarea logica 1.

De exemplu functia implica functia

Implicant: un produs în care apar una sau mai multe variabile este un implicant al unei functii daca implica functia. De exemplu produsele: sunt implicanti ai functiei , iar produsele sunt implicanti ai functiei

Implicant prim: un implicant care nu este continut într-un implicant format din mai putine variabile se numeste implicant prim. De exemplu a.e este implicant prim al functiei în timp ce nu este implicant prim deoarece el îl implica pe a.e care are mai putine variabile.

Implicant prim esential: este un implicant prim care acopera un produs standard neacoperit de alti implicanti primi. De exemplu este implicant prim esential al functiei deoarece este singurul implicant prim care acopera produsul standard , în timp ce nu este implicant prim esential al lui întrucât produsele standard si sunt acoperite atât de implicantul prim cât si de implicantul prim

Observatii ce stau la baza minimizarii cu diagrame Veitch-Karnaugh:

a)     Expresia minimala a unei functii logice este o suma de implicanti primi. Daca expresia unei functii logice contine un implicant care nu este implicant prim atunci acesta poate fi înlocuit cu implicantul prim care îl contine si care are mai putine variabile.

b)     Orice functie logica poate fi exprimata ca o suma de produse astfel încât fiecare produs corespunde unei grupari de celule în diagrama Veitch-Karnaugh si fiecare celula, care corespunde unei combinatii de valori ale variabilelor pentru care functia ia valoarea logica 1, este continuta în cel putin o grupare.

c)      Implicantii primi esentiali intra toti în expresia minimala a functiei.

Tinând cont de aceste observatii minimizarea se realizeaza în doua etape:

1)     Se determina implicantii primi esentiali.

2)     Celulele în care este înscris 1 logic si care nu sunt acoperite de implicanti primi esentiali se includ în grupari cât mai mari astfel încât numarul de implicanti primi care se adauga sa fie cât mai mic.

Exemplu: minimizarea functiilor si definite în fig.2.5.

(2.11)

1.2. Minimizarea functiilor logice în forma normala conjunctiva

Minimizarea functiilor logice în forma normala conjunctiva urmeaza aceleasi reguli ca si pentru forma normala disjunctiva. În continuare se vor redefini notiunile de implicatie, implicata, implicata prima si implicata prima esentiala pe baza functiilor si definite în fig.2.6.

Implicatia: se considera ca o functie f ‘ implica o alta functie f “ daca pentru orice combinatie a variabilelor pentru care f “ ia valoarea “0” f ‘ ia deasemenea valoarea “0”. De exemplu functia implica functia

Implicata: o suma în care apar una sau mai multe variabile este o implicata a unei functii daca functia o implica. De exemplu , sunt implicate ale functiei

Implicata prima: o implicata a unei functii care nu este continuta într-o alta implicata formata din mai putine variabile este implicata prima. De exemplu este o implicata prima a functiei în timp ce nu este implicata prima deoarece este implicata de

Implicata prima esentiala: este o implicata prima care acopera o suma logica standard neacoperita de alte implicate prime. De exemplu este implicata prima esentiala în timp ce nu este implicata prima esentiala întrucât sumele logice standard si sunt acoperite si de implicatele prime si respectiv

Minimizarea se realizeaza în doua etape:

1)     Se determina implicatele prime esentiale;

2)     Daca ramân celule în care este inscris “0” neacoperite de implicatele prime esentiale, acestea se includ în grupari cât mai mari astfel ca numarul de implicate prime care se adauga sa fie cât mai mic.

Exemplu: minimizarea functiilor si definite în fig.2.6.

(2.12)

1.3. Minimizarea functiilor incomplet definite

Minimizarea functiilor incomplet definite este importanta întrucât, de cele mai multe ori, în cazul comenzilor secventiale, se întâlnesc situatii de nedefinire. Luarea în considerare a combinatiilor de valori ale variabilelor pentru care functia nu este definita conduce la obtinerea unor forme normale minime.

Pentru exemplificare se considera cele trei functii definite prin diagramele Veitch din fig.2.7 si 2.8.

În urma analizarii celor trei functii se observa ca pentru prima functie este avantajos sa se considere ca functia ia valoarea logica “0” pentru combinatiile indiferente, pentru cea de a doua ca ia valoarea logica “1”, iar pentru cea de a treia pentru unele combinatii se va considera f=1, iar pentru altele f=0.

(2.13)

Pentru minimizarea functiilor incomplet definite se parcurg aceleasi etape ca si la functiile complet definite, dar cu urmatoarele precizari:

1)     Pentru determinarea multimii implicantilor primi se considera ca functia ia valoarea logica “1” pentru combinatiile indiferente.

2)     Pentru determinarea unei acoperiri minime a functiei în tabelul implicantilor primi nu se introduc produsele (respectiv sumele) standard corespunzatoare combinatiilor indiferente.