następny punkt »


1. Mapy Karnaugha

W poprzednim wykładzie poznaliśmy kilka sposobów reprezentowania funkcji logicznych. Teraz pokażemy jeszcze jedną metodę wykorzystującą mapy Karnaugha.

Mapa Karnaugha jest to tablica prostokątna o liczbie pól równej 2i, gdzie i= 2, 3, ... jest równe liczbie zmiennych występujących w funkcji boolowskiej. Każdemu polu tablicy jest przypisana inna kombinacja zerojedynkowa - kod pola (kratki). Sposób przypisania tych kodów poszczególnym polom jest taki, żeby kody opisujące dwa sąsiednie pola, w poziomie lub w pionie, różniły się na jednej pozycji. Kod opisujący określone pole składa się z części opisujących odpowiednio wiersz i kolumnę na przecięciu których leży pole. Zmienne funkcji boolowskiej przypisuje się odpowiednim wierszom i kolumnom mapy Karnaugha. Na rysunku II.1 pokazano przykładowe mapy Karnaugha dla 2, 3 i 4 zmiennych.

Rys. II.1. Przykładowe mapy Karnaugha dla: a) dwóch zmiennych, b) trzech zmiennych, c) 4 zmiennych

Analizując rysunek II.1 zwróćmy uwagę na sposób opisywania wierszy i kolumn. Na przykład, kolejne kolumny w mapie dla czterech zmiennych mają przypisane kody 00, 10, 11, 10. Zauważmy, że jest to inna kolejność niż wynikałoby to z typowej kolejności dla kodu dwójkowego: 00, 01, 10, 11. Dzięki takiemu sposobowi opisywania wierszy i kolumn uzyskuje się wymienioną wcześniej właściwość map Karnaugha, polegającą na tym, że sąsiednie pola (w wierszu bądź w kolumnie) są opisane kodami różniącymi się na jednej pozycji. Na rysunku II.2 zilustrowano sposób kodowania pól mapy oraz pokazano przykłady sąsiednich pól i przypisanych im kodów. Zwróćmy uwagę na to, że sąsiednimi polami w rozważanym kontekście są również pola znajdujące się na przykład w jednym wierszu po przeciwnych stronach mapy Karnaugha bądź w jednej kolumnie po przeciwnych stronach mapy.

Rys. II.2. a) Ilustracja sposobu kodowania pól mapy Karnaugha; b) przykłady sąsiednich pól

Pojęcie sąsiedztwa pól w mapie można rozszerzyć na sąsiedztwo czwórek pól. Kody sąsiadującej ze sobą czwórki pól charakteryzują się tym, że mają identyczne wartości na dwóch pozycjach, tych samych we wszystkich kodach. Na rysunku II.3 pokazano przykładowe czwórki komórek sąsiednich.

Rys. II.3. Przykłady grup czwórek sąsiadujących pól

Podobnie można rozważać grypy ośmiu sąsiednich komórek. Tym razem kody całej ósemki mają identyczną wartość na jednej pozycji, tej samej we wszystkich kodach. Przykłady grup ośmioelementowych pokazano na rysunku II.4.

Rys. II.4. Przykłady grup ósemek sąsiednich pól

Wyżej, ze względu na przejrzystość wywodu, pola wchodzące w skład poszczególnych grup zaznaczano specjalnymi symbolami. W praktyce stosowany jest inny sposób zaznaczania grup. Pokazano go na rysunku II.5.

Rys. II.5. Sposób oznaczania grup sąsiednich pól

Czasami wygodnie jest kody poszczególnych pól zapisywać w kodzie dziesiętnym. Na rysunku II.6 pokazano mapę Karnaugha dla czterech zmiennych z wpisanymi dziesiętnymi numerami pól. Warto zwrócić uwagę na ten "nietypowy" sposób numerowania pól mapy i zapamiętać go.

Rys. II.6. Mapa Karnaugha z dziesiętną numeracja pól

Zwróćmy uwagę, że ten sposób dziesiętnego numerowania pól jest słuszny przy założeniu, że kod każdego pola jest tworzony zgodnie z zasadą pokazaną na rysunku II.2 (konkatenacja kodu wiersza i kodu kolumny). Przyjęcie innej zasady (na przykład konkatenacja kodu kolumny i kodu wiersza) pociąga za sobą zmianę numeracji pól.


 następny punkt »