« poprzedni punkt  następny punkt »


3. Minimalizacja z wykorzystaniem map Karnaugha

W procesie projektowania układów cyfrowych wykorzystuje się różne kryteria optymalizacji układu. Tutaj za kryterium optymalizacji przyjmiemy minimalizację liczby bramek potrzebnych do zrealizowania funkcji boolowskiej. Znane są różne metody rozwiązywania takiego zadania optymalizacji. Niżej zostanie przedstawiona prosta metoda, określana czasami jako metoda graficzna, wykorzystująca mapy Karnaugha. Metoda ta jest użyteczna wtedy, gdy mamy do czynienia z funkcjami co najwyżej pięciu zmiennych. Przy większej liczbie zmiennych trzeba korzystać z innych metod, których opisy można znaleźć w literaturze. Metody te są wykorzystywane w programach wspomagających proces projektowania.

Podstawą dla wszystkich metod minimalizacji funkcji boolowskich jest tak zwana reguła sklejania

(Można zauważyć, że jest to ta sama reguła, z której korzystaliśmy wyżej przy sprowadzaniu funkcji do postaci kanonicznej.) Regułę tę słownie można wyrazić następująco: jeżeli dwa iloczyny tych samych argumentów różnią się tylko na jednej pozycji (to znaczy w jednym iloczynie występuje argument a w drugim jego negacja), to sumę tych iloczynów można zastąpić iloczynem pozostałych argumentów. Na przykład . Zauważmy, że do realizacji funkcji o postaci z lewej strony równania potrzeba pięć bramek, podczas gdy do realizacji funkcji o postaci z prawej strony równania potrzeba tylko dwóch bramek.

W graficznej metodzie minimalizacji zakładamy, że funkcja jest przedstawiona za pomocą mapy Karnaugha. Pamiętamy, że w mapie Karnaugha opisy dwóch sąsiednich pól (kratek) różnią się na jednej pozycji. W regule sklejania dwa iloczyny mają różnić się na jednej pozycji. Kojarząc te dwa fakty ze sobą można zauważyć, że jeżeli w mapie Karnaugha znajdziemy dwie jedynki w sąsiednich polach to odpowiadające im iloczyny można ze sobą skleić, co w efekcie prowadzi do uproszczenia funkcji. Na rysunku II.12 pokazano przykład minimalizacji funkcji boolowskiej. Sklejane pola zostały zaznaczone odpowiednimi symbolami. Każdej sklejanej parze jedynek odpowiada iloczyn (niepełny) w minimalnej postaci funkcji.

Rys. II.12. Przykład minimalizacji funkcji boolowskiej

Regułę sklejania można wykorzystywać wielokrotnie. Jeżeli na przykład w tablicy Karnaugha wystąpi czwórka sąsiednich jedynek to można je skleić ze sobą eliminując dwie zmienne. Podobnie można skleić ze sobą ósemki sąsiednich jedynek, eliminując trzy zmienne itd. W efekcie można powiedzieć, że sklejaniu podlegają pary, czwórki, ósemki itd. sąsiednich komórek. Poszczególne jedynki mogą wchodzić równocześnie do różnych sklejanych grup. Na rysunku II.13 pokazano przykłady sklejania różnych grup jedynek.

Rys. II.13. Przykłady sklejania różnych grup jedynek. a) Funkcja trzech zmiennych, b) funkcja czterech zmiennych

Procedurę minimalizacji funkcji boolowskiej przedstawimy na przykładzie minimalizacji funkcji czterech zmiennych.

Krok 1. Przedstawić funkcję w postaci mapy Karnaugha;

Krok 2. Znaleźć bloki sąsiadujących jedynek:

2a. sprawdzić czy istnieje blok szesnastu jedynek. Jeżeli tak, to f = 1 i koniec procedury;

2b. zaznaczyć każdą ósemkę sąsiadujących jedynek;

2c. zaznaczyć każdą czwórkę sąsiadujących jedynek, która nie zawiera się w większym zaznaczonym bloku;

2d. zaznaczyć każdą dwójkę sąsiadujących jedynek, która nie zawiera się w większym zaznaczonym bloku;

2f. zaznaczyć każde pole zawierające jedynkę, które nie zawiera się w większym zaznaczonym bloku.

Krok 3. Wybrać końcowy zestaw bloków spełniających następujące warunki:

3a. każde pole zawierające jedynkę znajduje się w co najmniej jednym zaznaczonym bloku;

3b. liczba bloków jest najmniejsza, przy czym wśród wszystkich zbiorów spełniających ten warunek, zapis funkcji odpowiadający wybranemu zbiorowi zawiera najmniej symboli zmiennych.

Powyższa procedura daje rozwiązanie optymalne przy założeniu, że korzystamy z funkcji sumy iloczynów i dążymy do realizacji za pomocą możliwie małej liczby bramek o możliwie najmniejszych liczbach wejść.

Przykład

Znaleźć minimalną postać funkcji

Na rysunku II.14 pokazano mapę Karnaugha funkcji oraz zaznaczono sklejane grupy. Zwróćmy uwagę na możliwość sklejania grupy jedynek znajdujących się w czterech narożnikach.

Rys. II.14. Mapa Karnaugha funkcji z przykładu

Ostatecznie minimalna postać funkcji wygląda następująco

Wyżej pokazano sposób minimalizacji funkcji na zasadzie sklejania grup jedynek. W podobny sposób można wykonać minimalizację funkcji w wyniku sklejania grup zer. Tym razem każdą sklejoną grupę zer zapisujemy w postaci sumy zanegowanych argumentów przypisanych odpowiednim wierszom i kolumnom tablicy Karnaugha. Ostatecznie, zminimalizowaną funkcję zapisujemy w postaci iloczynu sum. Na rysunku II.15 pokazano przykład minimalizacji przy sklejaniu zer.

Rys. II.15. Przykład minimalizacji funkcji na zasadzie sklejania zer

Można postawić pytanie, czy w czasie minimalizacji sklejać jedynki czy zera. W zasadzie powinno się zrobić obie minimalizacje i wybrać rozwiązanie lepsze. W przykładach z rysunków II.14 i II.15 minimalizowana była ta sama funkcja. Realizacja z rysunku II.14 wymaga użycia 8 bramek (trzywejściowa suma, trzywejściowy iloczyn, dwa dwuwejściowe iloczyny, cztery negacje). Realizacja z rysunku II.15 wymaga również użycia 8 bramek (trzywejściowy iloczyn, dwie trzywejściowe sumy, dwuwejściowa suma, cztery negacje). Jednak suma symboli argumentów jest mniejsza w rozwiązaniu z rysunku II.14 (siedem wobec ośmiu), co w konsekwencji oznacza mniejszą łączną liczbę wejść bramek. Ostatecznie rozwiązanie z rysunku II.14 jest lepsze.


« poprzedni punkt  następny punkt »