Metoda Quine-McCluskey

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 28 martie 2021; verificările necesită 23 de modificări .

Metoda Quine –McCluskey este o  metodă tabelară pentru minimizarea funcțiilor booleene propusă de Willard Quine și îmbunătățită de Edward McCluskey . Este o încercare de a scăpa de neajunsurile metodei lui Quine .

Algoritm de minimizare

  1. Termenii (conjunctiv în cazul SDNF și disjunctiv în cazul SKNF ) pe care este definită funcția de algebră logică (FAL) se scriu ca echivalenți binari;
  2. Acești echivalenți sunt împărțiți în grupuri, fiecare grupă include echivalenți cu un număr egal de unu (zero);
  3. Se face o comparație perechi a echivalenților (termenilor) din grupurile vecine pentru a forma termeni de ranguri inferioare;
  4. Este alcătuit un tabel în care titlurile rândurilor sunt termenii inițiali, iar titlurile coloanelor sunt termenii de ranguri scăzute;
  5. Sunt plasate etichete care reflectă absorbția termenilor de ranguri superioare (termeni inițiali) și apoi se realizează minimizarea conform metodei lui Quine .

Caracteristici

Specificul metodei Quine-McCluskey în comparație cu metoda Quine este de a reduce numărul de comparații perechi pentru lipirea lor. Reducerea se realizează datorită împărțirii inițiale a termenilor în grupuri cu un număr egal de uni (zero). Acest lucru face posibilă excluderea comparațiilor care, evident, nu dau lipire.

Deși mai practică decât hărțile Karnaugh atunci când vine vorba de mai mult de patru variabile, metoda Quine-McCluskey are, de asemenea, limitări ale domeniului de aplicare, deoarece timpul de rulare al metodei crește exponențial odată cu creșterea datelor de intrare. Se poate arăta că pentru o funcţie de n variabile limita superioară a numărului de implicanţi principali este 3 n / n . Dacă n = 32 pot exista mai mult de 6,5 * 10 15 . Vezi și problema de transcomputing .

Funcțiile cu un număr mare de variabile trebuie reduse la minimum cu o euristică potențial sub-optimală . Astăzi, algoritmul euristic de minimizare espresso este standardul mondial de facto [1] .

Exemplu

Pasul 1: găsiți implicanții principali

Fie dată funcția folosind următorul tabel de adevăr :

#
0 0 0 0 0 0
unu 0 0 0 unu 0
2 0 0 unu 0 0
3 0 0 unu unu 0
patru 0 unu 0 0 unu
5 0 unu 0 unu 0
6 0 unu unu 0 0
7 0 unu unu unu 0
#
opt unu 0 0 0 unu
9 unu 0 0 unu unu
zece unu 0 unu 0 unu
unsprezece unu 0 unu unu unu
12 unu unu 0 0 unu
13 unu unu 0 unu 0
paisprezece unu unu unu 0 unu
cincisprezece unu unu unu unu unu

Se poate scrie cu ușurință SDNF prin simpla însumare a mintermilor (ignorând termenii incomplet definiți ), unde funcția ia valoarea 1.

Pentru optimizare, scriem termenii, inclusiv cei care corespund stărilor indiferente, în următorul tabel:

Cantitatea 1 Minterm Reprezentare binară
unu M4 0100
M8 1000
2 M9 1001
M10 1010
M12 1100
3 M11 1011
M14 1110
patru M15 1111

Acum puteți începe să combinați mintermii unul cu celălalt, adică să efectuați operația de lipire. Dacă doi mintermi diferă doar într-un caracter care se află în aceeași poziție în ambele, înlocuim acest caracter cu „-”, ceea ce înseamnă că acest caracter nu contează pentru noi. Termenii care nu pot fi combinați în continuare sunt notați cu „*”. Când trecem la implicanții de rangul doi, interpretăm „-” ca a treia valoare. De exemplu: -110 și -100 sau -11- pot fi combinate, dar nu -110 și 011-. (Sugestie: comparați „-” mai întâi.)

Cantitatea "1" Minterms | Implicanți de nivel 1 | Implicanți de nivelul 2 ------------------------------------|-------------- ------- ----|--------------------- 1 m4 0100 | m(4,12) -100* | m(8,9,10,11) 10--* m8 1000 | m(8,9) 100- | m(8,10,12,14) 1--0* -------------------------------| m(8,10) 10-0 |---------------------- 2 m9 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-* m10 1010 |-------------------------| m12 1100 | m(9,11) 10-1 | -------------------------------| m(10,11) 101- | 3 m11 1011 | m(10,14) 1-10 | m14 1110 | m(12,14) 11-0 | ------------------------------------|-------------- ------- ----| 4 m15 1111 | m(11,15) 1-11 | | m(14,15) 111- |

Pasul 2: tabelul principal implicant

Când nu mai este posibilă o combinație suplimentară, construim un tabel de implicanți primi. Aici luăm în considerare doar acele ieșiri ale funcției care contează, adică nu acordăm atenție stărilor incomplet definite.

patru opt 9 zece unsprezece 12 paisprezece cincisprezece
m(4,12) X X -100
m(8,9,10,11) X X X X zece--
m(8,10,12,14) X X X X 1--0
m(10,11,14,15) X X X X 1-1-

Principiul de selecție implicant este același ca în metoda lui Quine . Implicanții simpli care sunt nuclee sunt afișați cu caractere aldine. În acest exemplu, nucleele nu acoperă toți mintermii, caz în care poate fi efectuată o procedură suplimentară de simplificare a tabelului (vezi metoda lui Petrik ). Avem următoarea opțiune:

Note

  1. ↑ VP Nelson ea, Digital Circuit Analysis and Design , Prentice Hall, 1995, pag. 234

Link -uri