Metoda Quine’a-McCluskeya
Metoda Quine’a-McCluskeya – sposób minimalizacji funkcji boolowskich opracowany przez Willarda Van Ormana Quine’a i Edwarda J. McCluskeya. Daje rezultaty identyczne do metody tablic Karnaugh, ale w przeciwieństwie do niej, dużo łatwiej daje się zaimplementować na komputerze.
Algorytm[edytuj | edytuj kod]
Proces minimalizacji rozpoczynamy od uporządkowania zbiorów iloczynów zupełnych funkcji w taki sposób, aby poszczególne grupy zawierały iloczyny zupełne o takiej samej liczbie jedynek. Następnie porównujemy każdą kombinację należącą do danej grupy z każdą kombinacją należącą do grupy następnej. Jeżeli porównywane kombinacje różnią się od siebie tylko na jednej pozycji, to łączymy je w nową kombinację, wpisując w rozróżniające je miejsce znak „–”.
Kontynuując procedurę łączenia, usuwamy powtarzające się kombinacje; kończymy gdy nie ma możliwości dokonania dalszych łączeń. Każda kombinacja nie podlegająca dalszemu łączeniu jest nazywana implikantem prostym.
Następnie tworzymy tabelę, w której wiersze odpowiadają otrzymanym implikantom prostym, a kolumny wszystkim prawdziwym iloczynom zupełnym, przedstawionym w definicji funkcji. Analizując tabelę stawiamy znak „x” w tych polach, które leżą na przecięciu kolumny reprezentującej dany iloczyn pełny (w postaci liczby dziesiętnej) oraz wiersza odpowiadającego implikantowi prostemu, który ów iloczyn pełny zawiera.
Uproszczona funkcja, równoważna funkcji minimalizowanej, może być otrzymana w postaci sumy wybranych implikantów prostych. Wybór implikantów prostych jest przeprowadzany tak, aby pokrywały one wszystkie rozważane iloczyny pełne.
Podobieństwo do metody tablic Karnaugha[edytuj | edytuj kod]
Z teoretycznego punktu widzenia, metoda Quine’a-McCluskeya i metoda tablic Karnaugh są identyczne. Wystarczy zauważyć, że w kolejnych krokach metody Quine’a-McCluskeya organizujemy grupy odpowiednio 1,2,4,8... elementowe, tak samo jak zakreślamy możliwie największe grupy w metodzie tablic Karnaugh. Następnie wybieramy takie implikanty proste, które pokrywają nam wszystkie iloczyny pełne, tak samo jak w metodzie Karnaugh upewniamy się, że zakreślone grupy pokrywają nam wszystkie konieczne pola. Można zatem odnieść wrażenie, że mechanizm działania jest ten sam, tyle że metoda tablic Karnaugha jest „graficzna”, natomiast metoda Quine’a-McCluskeya jest „tekstowa”. Praktyka pokazuje, która metoda jest wygodniejsza w wybranej sytuacji.
Złożoność[edytuj | edytuj kod]
Wprawdzie dla funkcji powyżej czterech zmiennych metoda Quine’a-McCluskeya jest bardziej wygodna niż metoda Karnaugh, jednak zakres jej zastosowań także jest ograniczony, ponieważ problem, który rozwiązuje, jest NP-trudny: czas działania algorytmu rośnie wykładniczo z rozmiarem zadania. Pokazano, że dla n zmiennych liczba implikantów prostych funkcji ma ograniczenie górne 3n/n.
Funkcje o wielu zmiennych redukuje się więc metodami heurystycznymi, które nie gwarantują znalezienia minimum. Wśród nich faktycznym standardem jest metoda Espresso.
Przykład[edytuj | edytuj kod]
Mamy zadaną tablicę prawdy:
| A | B | C | D | 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 | x |
| 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 | x |
| m15 | 1 | 1 | 1 | 1 | 1 |
Możemy zapisać ją w postaci
Oznacza to, że funkcja czterech zmiennych o jednej wartości będzie dawała 1 dla 4,8,10,11,12 i 15, będzie niezdefiniowana dla 9 i 14, a dla reszty będzie dawała zero. Można przedstawić ją w sposób nieoptymalny jako sumę iloczynów:
6 członów iloczynowych odpowiada 6 liczbom 4,8,10,11,12,15 liczby te przedstawione binarnie to 4 = 0100, druga jest jedynką, czyli B będzie nieodwrócone, 8 = 1000 – pierwsza zmienna będzie nieodwrócona itd.
Optymalizacja[edytuj | edytuj kod]
Aby zoptymalizować, budujemy tablicę iloczynów zupełnych
| Ilość jedynek | Iloczyn zupełny | Reprezentacja binarna |
|---|---|---|
| 1 | m4 | 0100 |
| m8 | 1000 | |
| 2 | m9 | 1001 |
| m10 | 1010 | |
| m12 | 1100 | |
| 3 | m11 | 1011 |
| m14 | 1110 | |
| 4 | m15 | 1111 |
Teraz zaczynamy łączyć iloczyny zupełne z innymi, różniącymi się tylko na jednej pozycji. Pozycja na której się różnią oznaczamy znakiem myślnika/minus (-). Porządkujemy je również względem ilości jedynek. W ten sposób powstają implikanty rozmiaru 2.Jeśli któryś iloczyn nie da się połączyć z innymi, bo różni się o więcej niż jedną cyfrę od każdego – zaznaczmy go gwiazdką i nazywamy implikantem prostym. W następnym kroku łączymy te rozmiaru 2 w rozmiar 4 itd.
| Ilość jedynek | Iloczyn zupełny | Binarnie | Implikanty rozmiaru 2 | Implikanty rozmiaru 4 | ||
|---|---|---|---|---|---|---|
| 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 | – | ||
| – | – | m(8,12) | 1-00 | – | ||
| 2 | m9 | 1001 | m(9,11) | 10-1 | m(10,11,14,15) | 1-1-* |
| m10 | 1010 | m(10,11) | 101- | – | ||
| – | – | m(10,14) | 1-10 | – | ||
| m12 | 1100 | m(12,14) | 11-0 | – | ||
| 3 | m11 | 1011 | m(11,15) | 1-11 | – | |
| m14 | 1110 | m(14,15) | 111- | – | ||
| 4 | m15 | 1111 | – | – | ||
Krok 2: wybór implikantów prostych[edytuj | edytuj kod]
Robimy tabelę, gdzie wiersze to implikanty proste, które zaznaczyliśmy gwiazdką, a kolumny to liczby ze zbioru m; nie bierzemy pod uwagę liczb ze zbioru d, choć w pierwszym kroku braliśmy. Z implikantów prostych wybieramy te istotne i zaznaczamy gwiazdką.
| 4 | 8 | 10 | 11 | 12 | 15 | ⇒ | A | B | C | D | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| m(4,12)* | X | X | ⇒ | – | 1 | 0 | 0 | ||||
| m(8,9,10,11) | X | X | X | ⇒ | 1 | 0 | – | – | |||
| m(8,10,12,14) | X | X | X | ⇒ | 1 | – | – | 0 | |||
| m(10,11,14,15)* | X | X | X | ⇒ | 1 | – | 1 | – |
Wybieramy w ten sposób, że patrzymy na kolumny, które mają tylko jeden znak X. Jeśli kolumna ma tylko jeden X oznacza to że iloczyn zupełny może być przykryty tylko przez jeden implikant prosty. Ten implikant jest istotny. Pierwsza kolumna z „4” ma tylko jeden X dla m(4,12). Kolumna z „15” ma jeden X dla m(10,11,14,15). Drugi implikant prosty może być przykryty przez trzeci i czwarty, a trzeci przez pierwszy i drugi. Jeśli implikant jest istotny, musi być uwzględniony w rozwiązaniu. W niektórych przypadkach, jak powyższy przykład, implikanty istotne nie przykrywają wszystkich iloczynów zupełnych, więc należy wybrać na przykład za pomocą metody Petricka. W tym przypadku są dwa rozwiązania:
Zobacz też[edytuj | edytuj kod]
- funkcja boolowska
- implikant funkcji boolowskiej, implikant prosty
- metoda Espresso
- minimalizacja funkcji boolowskich
Linki zewnętrzne[edytuj | edytuj kod]
- Quine-McCluskey Solver – solver online pokazujący kolejne kroki
- quine_mc_cluskey_v0.2 – pogram konsolowy Public Domain w C.
- Olivier Coudert „Two-level logic minimization: an overview” INTEGRATION, the VLSI journal, 17-2, s. 97–140, October 1994. ocoudert.com. [zarchiwizowane z tego adresu (2020-05-10)]. – dokładne wyjaśnienie każdego kroku
- Computer Simulation Codes for the Quine-McCluskey Method – autorstwa Sourangsu Banerji.
- Modified Quine-McCluskey Method – autorstwa Vitthal Jadhav, Amar Buchade.
- simpogical Tutorial metod Quine-McCluskey i Petricka w pdf.
- quine-mccluskey-petrick (source-archive.zip) implementacja C++ na podstawie powyższego tutoriala.
- SourceForge qmcs (SourceForge.net) implementacja w C++.