Minimizarea algebrică a funcțiilor logice

MINIMIZAREA ALGEBRICA A FUNCTIILOR LOGICE

Aceasta metoda este utilizabila, in principiu, pentru minimizarea functiilor scalare ori vectoriale cu un numar arbitrar de variabile. Metoda se poate utiliza pentru programarea unui calcul automat de minimizare. Minimizarea are loc in doi pasi:

(1) stabilirea implicantilor primi, si

(2) calculul acoperirii minimale pentru functia respectiva.

Metoda utilizeaza scrierea binara a mintermilor functiei si printr-o ordonare judicioasa faciliteaza gasirea implicantilor adiacenti dar si calculul implicantilor de ordin superior rezultati.

Intr-o prima abordare vor fi prezentate principalele repere ale metodei aplicate functiilor scalare. Acestea vor facilita mult intelegerea metodei in cazul general, functiilor booleene vectoriale.

Minimizarea functiilor scalare prin metoda Quine-McCluskey

Generarea multimii implicantilor primi. In calculul implicantilor primi, descris in cele ce urmeaza, mintermii functiei sunt numiti implicanti, sau cuburi, de ordinul 0 ai functiei. In timp ce, implicantii care rezulta prin reducerea unei variabile sau a doua sau mai multor variabile, sunt implicanti de ordinul unu, respectiv de ordinul doi ori superior. Calculul implicantilor primi se efectueaza considerand atat mintermii functiei cat si mintermii neprecizati ai acesteia (daca exista).

Intr-o prima etapa se calculeaza pentru fiecare implicant de ordinul 0 al functiei ponderea acestuia. Prin ponderea unui implicant se intelege numarul de unitati din reprezentarea binara a respectivului implicant.

Astfel, spre exemplu, implicantii (de ordinul 0), 0101 si 1101 au ponderea 2, respectiv 3, iar implicantii -1-1 si 01-0 au ponderea 2 (ordinul 2), respectiv 1 (ordinul 1).

Toti implicantii de acelasi ordin si avand aceeasi pondere sunt grupati in aceiasi clasa.

Pe durata calculului implicantilor primi, implicantii de ordine diferite, chiar daca au aceiasi pondere, fac parte din clase distincte.

Procesul de calcul al implicantilor primi incepe prin asezarea implicantilor initiali (adica implicantii de ordinul 0) care au aceeasi pondere, intr-o aceeasi clasa. Clasele sunt intotdeauna etichetate prin valoarea ponderii implicantilor lor.

Etapa a doua, iterativa, este dedicata gasirii implicantilor de ordin superior (implicantii rezultati prin contopirea a doi implicanti adiacenti).

Termenii adiacenti se gasesc intotdeauna printre implicantii de acelasi ordin din doua clase succesive.

PROIECTAREA LOGICA

Bunaoara, printre implicantii claselor 0 si 1, dar si printre implicantii claselor 2 si 3 etc, de ordinul 0. Situatia este similara pentru ordinele superioare 1, 2 etc.

Astfel, se va cerceta sistematic adiacenta termenilor dintre clasa 0 si clasa 1, apoi adiacenta dintre termenii claselor 1 si 2 etc. Se incepe ordonat cu implicantii clasei cu cea mai mica pondere, daca acestia exista (clasa 0, spre exemplu, daca aceasta este nevida).

Este util de remarcat faptul ca, implicantii clasei 1-a, spre exemplu, sunt cercetati mai intai in raport cu adiacenta fata de implicantii clasei 0 (venind dinspre aceasta), iar apoi sunt cercetati in raport cu adiacenta fata de implicantii clasei a 2-a. Fireste, daca respectivele clase sunt nevide.

Adiacenta, este definita, astfel : doi implicanti sunt adiacenti daca si numai daca difera prin valoarea unui singur rang cu valoare binara, in rest cei doi implicanti fiind identici.

Deindata ce doi implicanti se dovedesc adiacenti, este creat un implicant de ordin imediat superior. Implicantii adiacenti respectivi sunt, fiecare in parte, marcati. Marcajul implicantilor adiacenti semnifica faptul ca ambii au un succesor (reprezentant) de ordin superior.

Implicantul de ordin imediat superior este stocat intr-o clasa, cu pondere corespunzatoare, de implicanti de acelasi ordin.

Daca s-au identificat doi implicanti adiacenti din clasele a 3-a si a 4-a, de ordinul 0, se va genera un implicant care va fi din clasa a 2-a, dar de ordinul 1, spre exemplu.

Odata incheiat ciclul prin care s-au cercetat implicantii de ordinul zero se continua cu implicantii de ordin 1 (toti acesti implicanti au o variabila redusa) daca exista cel putin doua clase succesive nevide.

Criteriul adiacentei acestora este, in principiu acelasi, cu mentiunea ca doi implicanti apartinand unor clase consecutive, de ordinul 1, trebuie sa aiba, suplimentar, variabila redusa corespunzator aceluiasi rang. Adiacenta implicantilor de ordinul al doilea, sau mai mare, se extinde similar, impunandu-se ca rangurile variabilelor reduse sa coincida. Pentru rangurile cu valori binare (nereduse) se mentine acelasi criteriu : sa existe un singur rang prin care sa difere.

Aceasta etapa, de stabilirea a adiacentelor si de producere a implicantilor de ordin superior este, asa cum s-a mai mentionat, iterativa. Fiecare iteratie va fi reluata, cu clasele implicantilor de ordin superior, atata vreme cat se pot genera implicanti de ordin superior celor existenti la inceputul iteratiei. Procesul iterativ se incheie atunci cand nu se mai pot genera implicanti de ordin superior.

In acel moment, multimea implicantilor de ordin maxim (de la care incepand, nu s-au mai generat implicanti superiori acestora) reunita cu multimea tuturor implicantilor, din ordinele inferioare, nemarcati (inclusiv implicantii de ordin zero nemarcati), formeaza multimea implicantilor primi pentru functia respectiva.