Metoda tabelaryczna Quine-McCluskeya
W poprzednim rozdziale omówiliśmy metodę K-map, która jest wygodną metodą minimalizowania funkcji boolowskich do 5 zmiennych. Jednak za pomocą tej metody trudno jest uprościć funkcje boolowskie mające więcej niż 5 zmiennych.
Metoda tabelaryczna Quine-McClukey jest metodą tabelaryczną opartą na koncepcji pierwotnych implantów. Wiemy toprime implicant jest terminem iloczynowym (lub sumarycznym), którego nie można dalej redukować, łącząc z jakimkolwiek innym wyrażeniem iloczynowym (lub sumarycznym) danej funkcji boolowskiej.
Ta metoda tabelaryczna jest przydatna do uzyskiwania pierwszych implantów poprzez wielokrotne używanie następującej tożsamości logicznej.
xy + xy '= x (y + y') = x.1 = x
Procedura metody tabelarycznej Quine-McCluskeya
Wykonaj następujące kroki, aby uprościć funkcje boolowskie za pomocą metody tabelarycznej Quine-McClukeya.
Step 1 - Ułóż podane minimalne terminy w pliku ascending orderi utwórz grupy na podstawie liczby grup obecnych w ich reprezentacjach binarnych. A więc będzieat most ‘n+1’ groups jeśli w funkcji boolowskiej występuje „n” zmiennych boolowskich lub „n” bitów w binarnym odpowiedniku terminów min.
Step 2 - Porównaj minimalne terminy obecne w successive groups. Jeśli zmiana dotyczy tylko pozycji jednego bitu, weź parę tych dwóch minimalnych członów. Umieść ten symbol „_” w innej pozycji bitu i zachowaj pozostałe bity bez zmian.
Step 3 - Powtarzaj krok 2 z nowo utworzonymi terminami, aż otrzymamy wszystkie prime implicants.
Step 4 - Sformułuj plik prime implicant table. Składa się z zestawu wierszy i kolumn. Implanty Prime można umieszczać w wierszach, a minimalne w kolumnach. Umieść „1” w komórkach odpowiadających warunkom minimalnym, które są objęte każdą główną implikacją.
Step 5- Znajdź podstawowe implanty pierwotne, obserwując każdą kolumnę. Jeśli minimalny termin jest objęty tylko jedną główną implikacją, to jestessential prime implicant. Te podstawowe implanty pierwotne będą częścią uproszczonej funkcji boolowskiej.
Step 6- Zmniejsz tabelę implikacyjną liczby pierwszej, usuwając wiersz każdej implikacji podstawowej pierwszej oraz kolumny odpowiadające warunkom minimalnym, które są objęte tą implikacją podstawową pierwszą. Powtórz krok 5 dla zredukowanej pierwotnej implikowanej tabeli. Zatrzymaj ten proces po zakończeniu wszystkich minimalnych warunków danej funkcji boolowskiej.
Przykład
Pozwól nam simplify następująca funkcja logiczna, $ f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ right) $ przy użyciu Quine-McClukeya metoda tabelaryczna.
Podana funkcja boolowska jest w sum of min termsFormularz. Ma 4 zmienne W, X, Y i Z. Podane minimalne wyrazy to 2, 6, 8, 9, 10, 11, 14 i 15. Rosnąca kolejność tych minimalnych wyrazów oparta na liczbie jedynek obecnych w ich odpowiednik binarny to 2, 8, 6, 9, 10, 11, 14 i 15. Poniższa tabela przedstawia te wartościmin terms and their equivalent binary reprezentacje.
| Nazwa grupy | Minimalne terminy | W. | X | Y | Z |
|---|---|---|---|---|---|
| GA1 | 2 | 0 | 0 | 1 | 0 |
| 8 | 1 | 0 | 0 | 0 | |
| GA2 | 6 | 0 | 1 | 1 | 0 |
| 9 | 1 | 0 | 0 | 1 | |
| 10 | 1 | 0 | 1 | 0 | |
| 11 | 1 | 0 | 1 | 1 | |
| 14 | 1 | 1 | 1 | 0 | |
| GA4 | 15 | 1 | 1 | 1 | 1 |
Podane terminy minimalne są podzielone na 4 grupy na podstawie liczby wyrażeń obecnych w ich binarnych odpowiednikach. Poniższa tabela przedstawia możliwemerging of min terms z sąsiednich grup.
| Nazwa grupy | Minimalne terminy | W. | X | Y | Z |
|---|---|---|---|---|---|
| GB1 | 2,6 | 0 | - | 1 | 0 |
| 2,10 | - | 0 | 1 | 0 | |
| 8,9 | 1 | 0 | 0 | - | |
| 8,10 | 1 | 0 | - | 0 | |
| GB2 | 6,14 | - | 1 | 1 | 0 |
| 9,11 | 1 | 0 | - | 1 | |
| 10,11 | 1 | 0 | 1 | - | |
| 10,14 | 1 | - | 1 | 0 | |
| 11,15 | 1 | - | 1 | 1 | |
| 14,15 | 1 | 1 | 1 | - |
Terminy minimalne, które różnią się tylko pozycją jednego bitu od sąsiednich grup, są łączone. Ten różny bit jest reprezentowany przez ten symbol „-”. W tym przypadku są trzy grupy, a każda grupa zawiera kombinacje dwóch minimalnych terminów. Poniższa tabela przedstawia możliwemerging of min term pairs z sąsiednich grup.
| Nazwa grupy | Minimalne terminy | W. | X | Y | Z |
|---|---|---|---|---|---|
| GB1 | 2,6,10,14 | - | - | 1 | 0 |
| 2,10,6,14 | - | - | 1 | 0 | |
| 8,9,10,11 | 1 | 0 | - | - | |
| 8,10,9,11 | 1 | 0 | - | - | |
| GB2 | 10,11,14,15 | 1 | - | 1 | - |
| 10,14,11,15 | 1 | - | 1 | - |
Kolejne grupy par terminów minimalnych, które różnią się tylko pozycją jednego bitu, są łączone. Ten różny bit jest reprezentowany przez ten symbol „-”. W tym przypadku są dwie grupy, a każda grupa zawiera kombinacje czterech minimalnych terminów. Tutaj te kombinacje 4-minutowych terminów są dostępne w dwóch wierszach. Więc możemy usunąć powtarzające się wiersze. Zmniejszona tabela po usunięciu zbędnych wierszy jest pokazana poniżej.
| Nazwa grupy | Minimalne terminy | W. | X | Y | Z |
|---|---|---|---|---|---|
| GC1 | 2,6,10,14 | - | - | 1 | 0 |
| 8,9,10,11 | 1 | 0 | - | - | |
| GC2 | 10,11,14,15 | 1 | - | 1 | - |
Dalsze łączenie kombinacji terminów minimalnych z sąsiednich grup nie jest możliwe, ponieważ różnią się one pozycją więcej niż jednobitową. W powyższej tabeli znajdują się trzy wiersze. Tak więc każdy wiersz będzie miał jedną główną implikację. Dlatego teżprime implicants są YZ ', WX' i WY.
Plik prime implicant table pokazano poniżej.
| Minimalne terminy / Prime Implicants | 2 | 6 | 8 | 9 | 10 | 11 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|
| YZ’ | 1 | 1 | 1 | 1 | ||||
| WX’ | 1 | 1 | 1 | 1 | ||||
| WY | 1 | 1 | 1 | 1 |
Pierwotne implanty umieszcza się rzędami, a minimalne terminy umieszcza się kolumnami. 1s są umieszczane we wspólnych komórkach pierwszych implikowanych rzędów i odpowiednich kolumn z terminem minimalnym.
Warunki minimalne 2 i 6 są objęte tylko jednym głównym implikacją YZ’. Więc jest to plikessential prime implicant. Będzie to część uproszczonej funkcji boolowskiej. Teraz usuń ten główny niejawny wiersz i odpowiadające mu kolumny terminów minimalnych. Poniżej przedstawiono tabelę implikacji zredukowanej liczby pierwszej.
| Minimalne terminy / Prime Implicants | 8 | 9 | 11 | 15 |
|---|---|---|---|---|
| WX’ | 1 | 1 | 1 | |
| WY | 1 | 1 |
Warunki minimalne 8 i 9 są objęte tylko jedną główną implikacją WX’. Więc jest to plikessential prime implicant. Będzie to część uproszczonej funkcji boolowskiej. Teraz usuń ten główny niejawny wiersz i odpowiadające mu kolumny terminów minimalnych. Poniżej przedstawiono tabelę implikacji zredukowanej liczby pierwszej.
| Minimalne terminy / Prime Implicants | 15 |
|---|---|
| WY | 1 |
Minimalny termin 15 jest objęty tylko jedną główną implikacją WY. Więc jest to plikessential prime implicant. Będzie to część uproszczonej funkcji boolowskiej.
W tym przykładowym problemie mamy trzy pierwotne implanty i wszystkie trzy są niezbędne. Dlatego teżsimplified Boolean function jest
f(W,X,Y,Z) = YZ’ + WX’ + WY.