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.

GA3
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.

GB3
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.