Metoda Quine-McCluskey
Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . |
Metoda Quine-McCluskey (sau metoda primilor implicați ) este un algoritm dezvoltat de Willard Van Orman Quine și Edward McCluskey care este utilizat în rețele logice combinaționale pe două niveluri pentru minimizarea unei funcții booleene a n variabile . Metoda este funcțională identică cu harta Karnaugh , dar forma sa tabelară o face mai eficientă pentru crearea computerului; oferă, de asemenea, un mod determinist de a testa minimizarea unei funcții booleene.
Metoda constă din doi pași:
- Identificați toți implicații principali ai funcției.
- Întoarceți implicații principali găsiți într-un tabel pentru a obține implicații primi esențiali ai funcției.
Complexitate
Deși este mai practic decât hărțile Karnaugh pentru funcții cu mai mult de 4 variabile, metoda Quine-McCluskey are încă o gamă limitată de utilizare, deoarece problema rezolvată de algoritm ( satisfacția booleană ) este NP-dificilă : timpul de rulare crește exponențial pe măsură ce numărul de intrări crește. Se poate arăta că pentru o funcție de n variabile limita superioară a numărului de implicați primi este de 3 n / n . Dacă n = 32 pot exista mai mult de 6,5 * 10 15 implicați primi. Prin urmare, funcțiile cu un număr mare de variabile booleene trebuie reduse la minimum cu metode euristice, cum ar fi Espresso minimizator logic euristic.
Metodă
Metoda constă din două faze principale: căutarea primilor implicați și căutarea ulterioară a acoperirii optime. Considerăm minimizarea sub forma sumei de produse (numită și SOP, din acronimul englez sum of products ), dar totul este ușor extensibil la forma de produs de sume (sau POS, produs de sume ).
În prima fază, simplificarea tipului se aplică sistematic:
adică proprietatea distributivă a produsului în raport cu suma, unde P indică orice termen al produsului (mintermine). Evident, metoda poate fi extinsă și la funcții care nu sunt complet specificate și la circuite cu mai multe ieșiri. Prima fază constă din pașii:
- pentru a tabela toate mintermele funcției în formă binară, în ordine crescătoare ca și pentru tabelul adevărului;
- comparați toți termenii în mod exhaustiv: termenii care diferă cu un singur bit sunt simplificați (distanță de Hamming unitară) și marcați, deoarece au contribuit la crearea unui implicant;
- apoi creați un nou tabel cu toți termenii de produs marcați care ies din primul tabel și repetați pasul 2);
- procesul se încheie atunci când nu se mai pot face reduceri.
În momentul construirii tabelului este ușor de văzut că nu trebuie neapărat să comparăm toți termenii între ei, ci de fapt numai acei termeni adiacenți care diferă doar cu un bit 1. Apoi grupăm în tabel termenii care au un număr egal de 1 în minterm.
Exemplu
Să fie dată următoarea funcție:
Pasul 1: tabelul principalilor implicați
| abcdnbsp; | ||
|---|---|---|
| 0 0 0 1 | 1 | ... |
| 1 0 0 1 | 9 | ... |
| 1 0 1 1 | 11 | ... |
| 1 1 0 0 | 12 | ... |
| 1 1 0 1 | 13 | ... |
| 1 1 1 0 | 14 | ... |
| 1 1 1 1 | 15 | ... |
Pasul 2: comparație
Vedem din tabel că mintermin 1 ar trebui comparat numai cu mintermin 9, care are două 1s în produsul său și nu cu celelalte care diferă cu doi biți. Comparând minterminul 1 cu acel 9, vedem că acestea diferă doar pentru primul bit: primul rând al tabelului următor trebuie să fie -001 simplificând primul bit. Comparația 1 cu 12 nu este compatibilă, deoarece cele două termene nu diferă cu un singur bit. Viceversa 9 este comparat cu 11 și 13, dar nu cu 14, iar 12 este comparat cu 13 și 14, dar nu cu 11. În cele din urmă, 11, 13, 14 sunt comparate cu 15. Rezultatul final este prezentat în tabelul următor.
| abcdnbsp; | ||
|---|---|---|
| - 0 0 1 | 1.9 | ... |
| 1 0 - 1 | 9.11 | ... |
| 1 - 0 1 | 9.13 | ... |
| 1 - 1 1 | 11.15 | ... |
| 1 1 0 - | 12.13 | ... |
| 1 1 - 0 | 12.14 | ... |
| 1 1 - 1 | 13.15 | ... |
| 1 1 1 - | 14.15 | ... |
Pasul 2: reducere mai mare
Desigur, trebuie să reducem din nou cât mai mult posibil. În acest caz, putem compara doar 9.11 cu 13.15 care diferă pentru al doilea bit și 12.13 cu 14.15 care diferă doar pentru al treilea bit:
| abcdnbsp; | ||
|---|---|---|
| 1 - - 1 | 9,11,13,15 | ... |
| 1 1 - - | 12,13,14,15 | ... |
Pasul 3: selectarea primilor implicați
În acest moment nu sunt posibile alte reduceri. Principalii implicați sunt:
Acoperire
A doua fază se referă la alegerea optimă a implicaților. Pentru a face acest lucru, construim un tabel numit tabel de acoperire care constă dintr-o matrice în care indicii de rând reprezintă primii implicați identificați, în timp ce indicii de coloană reprezintă toți termenii. a funcției. Elementele tabelului de acoperire sunt casete marcate cu 1 s și implicantul acoperă mintermin j-th, altfel sunt 0. Alternativ, pur și simplu folosiți un „x” pentru a le identifica doar pe cele din tabel.
1 9 11 12 13 14 15 ------------------------------- P0 | xx | P1 | xxxx | P2 | xxxx | -------------------------------
Exemplu
ABCD f
m0 0 0 0 0 0
m1 0 0 0 1 0
m2 0 0 1 0 0
m3 0 0 1 1 0
m4 0 1 0 0 1
m5 0 1 0 1 0
m6 0 1 1 0 0
m7 0 1 1 1 0
m8 1 0 0 0 1
m9 1 0 0 1 -
m10 1 0 1 0 1
m11 1 0 1 1 1
m12 1 1 0 0 1
m13 1 1 0 1 0
m14 1 1 1 0 -
m15 1 1 1 1 1
Din tabel puteți obține forma canonică a funcției sub forma sumei de produse (disjuncte) pur și simplu prin adăugarea mintermenii cu ieșire „1“ (dar omițând cele cu care nu - mi pasă de ieșire „-“):
Funcția, desigur, nu este în formă minimă. Deci, pentru a-l minimiza, toate mintermurile cu ieșirea "1" sunt afișate pe o masă (inclusiv cele cu care nu le pasă ca ieșire), ordonându-le în clase în funcție de numărul de "1" prezent în fiecare mintermin:
Numărul reprezentării binare „1” Mintermin
--------------------------------------------
1 m4 0100
m8 1000
--------------------------------------------
2 m9 1001
m10 1010
m12 1100
--------------------------------------------
3 m11 1011
m14 1110
--------------------------------------------
4 m15 1111
În acest moment, puteți începe să combinați minterms unul cu celălalt. Dacă două mintermi, care aparțin unor clase diferite, au o distanță de Hamming egală cu 1 (adică diferă pentru o singură variabilă), atunci pot fi unite, inserând o nu-i pasă în variabila non-comună. Termenele care nu pot fi combinate între ele sunt indicate în exemplu cu un asterisc („*”). Odată ce toți implicații ordinului 4 au fost epuizați, trecem la posibila simplificare a celor de ordinul 3, unde în acest caz minterms-urile cu distanță de Hamming egală cu 2 sunt unite împreună. La sfârșit ajungem la următoarele masa:
Implicanți de ordinul 4 | Implicanți de ordinul III | Implicanți de ordinul II
------------------------------- | ------------------ -------- | -------------------------
Numărul de "1" Mintermine | |
------------------------------- | ------------------ -------- | -------------------------
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 principalilor implicați
Odată finalizată căutarea primilor implicați, aceștia sunt raportați într-un tabel special, scriind implicații pe linii și mintermini pe coloane.
| 4 | 8 | 9 | 10 | 11 | 12 | 14 | 15 | ||
| m (4,12) * | X | X | -100 | ||||||
| m (8,9,10,11) * | X | X | X | X | 10-- | ||||
| m (8,10,12,14) | X | X | X | X | 1-0 | ||||
| m (10,11,14,15) * | X | X | X | X | 1-1- |
Pentru a continua alegerea acoperirii, se aplică următoarele criterii:
- Dominanta rândului: Rândul i domină rândul j dacă Pi implicant acoperă toate mintermele pe care Pj implicant le acoperă plus cel puțin unul.
- Dominanta coloanei: Coloana i domină coloana j dacă mintermul mj este acoperit de aceiași implicați ca m este acoperit plus cel puțin unul.
- Alegerea implicantului esențial: se spune că un implicant este esențial dacă un markup dintr-o coloană este acoperit într-un singur rând. În acest caz, implicatul este adăugat la setul de coperte și rândul și toate coloanele în care există un marcaj al implicatului sunt șterse. În exemplu, primul implicant este esențial, deoarece este singurul care acoperă mintermul 4. Același lucru este valabil pentru a doua implicare care acoperă minterminul 9 și pentru al patrulea implicant care acoperă mintermul 15.
În acest caz, al treilea prim implicant poate fi acoperit de al doilea, primul și al patrulea, deci nu este esențial. În unele cazuri, există situații de hărți ciclice în care nu există condiții de dominanță sau esențialitate, pentru care trebuie utilizate alte proceduri de simplificare. Un mod sistematic și eficient este reprezentat de metoda Petrick . În acest exemplu, primii implicați esențiali implică toate mintermele, deci nu este nevoie să combinăm implicații esențiali și neesențiali și obținem următoarea ecuație:
Ecuațiile rezultate sunt funcțional echivalente cu ecuația inițială:
