Mapa Karnaugha - Karnaugh map
Mapę Karnaugh ( KM lub K mapę ) to metoda uproszczenia Boole'a wyrażeń. Maurice Karnaugh wprowadził go w 1953 roku jako udoskonalenie wykresu Veitcha Edwarda W. Veitcha z 1952 roku , który był ponownym odkryciem diagramu logicznego Allana Marquand z 1881 roku, znanego również jako diagram Marquand, ale z naciskiem na jego użyteczność w przełączaniu obwodów. Wykresy Veitcha są zatem znane również jako diagramy Marquand-Veitch , a mapy Karnaugha jako mapy Karnaugha-Veitcha ( mapy KV ).
Mapa Karnaugh zmniejsza potrzebę przeprowadzania rozległych obliczeń, wykorzystując ludzkie zdolności rozpoznawania wzorców. Pozwala również na szybką identyfikację i eliminację potencjalnych warunków wyścigu .
Wymagane wyniki logiczne są przenoszone z tabeli prawdy na dwuwymiarową siatkę, gdzie w mapach Karnaugha komórki są uporządkowane w kodzie Graya , a każda pozycja komórki reprezentuje jedną kombinację warunków wejściowych. Komórki są również znane jako minterms, podczas gdy każda wartość komórki reprezentuje odpowiednią wartość wyjściową funkcji logicznej. Zidentyfikowano optymalne grupy jedynek lub zer, które reprezentują warunki kanonicznej formy logiki w oryginalnej tabeli prawdy. Te terminy mogą służyć do napisania minimalnego wyrażenia logicznego reprezentującego wymaganą logikę.
Mapy Karnaugha służą do uproszczenia rzeczywistych wymagań logicznych, tak aby można je było zaimplementować przy użyciu minimalnej liczby bramek logicznych. Produktów suma-of-wyrażenie (SPO) zawsze może być realizowane za pomocą bramek karmienia w produkt lub bramy , a produkt-of-sum wyrażenie (POS) prowadzi do karmienia lub bramy i bramki. Wyrażenie POS podaje uzupełnienie funkcji (jeśli F jest funkcją, to jej uzupełnieniem będzie F'). Mapy Karnaugha można również wykorzystać do uproszczenia wyrażeń logicznych w projektowaniu oprogramowania. Warunki logiczne, takie jak używane na przykład w instrukcjach warunkowych , mogą być bardzo skomplikowane, co sprawia, że kod jest trudny do odczytania i utrzymania. Po zminimalizowaniu kanonicznych wyrażeń sum-of-products i product-of-sums można zaimplementować bezpośrednio przy użyciu operatorów logicznych AND i OR.
Przykład
Mapy Karnaugha służą do uproszczenia funkcji algebry Boole'a . Rozważmy na przykład funkcję Boolean opisaną w poniższej tabeli prawdy .
A | b | C | D | ||
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 1 | 0 |
2 | 0 | 0 | 1 | 0 | 0 |
3 | 0 | 0 | 1 | 1 | 0 |
4 | 0 | 1 | 0 | 0 | 0 |
5 | 0 | 1 | 0 | 1 | 0 |
6 | 0 | 1 | 1 | 0 | 1 |
7 | 0 | 1 | 1 | 1 | 0 |
8 | 1 | 0 | 0 | 0 | 1 |
9 | 1 | 0 | 0 | 1 | 1 |
10 | 1 | 0 | 1 | 0 | 1 |
11 | 1 | 0 | 1 | 1 | 1 |
12 | 1 | 1 | 0 | 0 | 1 |
13 | 1 | 1 | 0 | 1 | 1 |
14 | 1 | 1 | 1 | 0 | 1 |
15 | 1 | 1 | 1 | 1 | 0 |
Poniżej znajdują się dwie różne notacje opisujące tę samą funkcję w nieuproszczonej algebrze Boole'a, przy użyciu zmiennych Boole'a A , B , C , D i ich odwrotności.
- gdzie są mintermy do mapowania (tj. wiersze, które mają wyjście 1 w tabeli prawdy).
- gdzie są maxterms do mapowania (tj. wiersze, które mają wyjście 0 w tabeli prawdy).
Budowa
W powyższym przykładzie cztery zmienne wejściowe można łączyć na 16 różnych sposobów, więc tabela prawdy ma 16 wierszy, a mapa Karnaugha ma 16 pozycji. Mapa Karnaugh jest zatem ułożona w siatce 4 × 4.
Indeksy wierszy i kolumn (pokazane w górnej i dolnej lewej części mapy Karnaugha) są uporządkowane w kodzie Graya, a nie w binarnej kolejności numerycznej. Kod Graya zapewnia, że tylko jedna zmienna zmienia się między każdą parą sąsiednich komórek. Każda komórka kompletnej mapy Karnaugha zawiera cyfrę binarną reprezentującą wyjście funkcji dla tej kombinacji wejść.
Grupowanie
Po skonstruowaniu mapy Karnaugha służy ona do znalezienia jednej z najprostszych możliwych form — postaci kanonicznej — dla informacji w tabeli prawdy. Sąsiednie jedynki na mapie Karnaugh to okazja do uproszczenia wyrażenia. Mintermy („terminy minimalne”) dla końcowego wyrażenia można znaleźć, otaczając grupy jedynek na mapie. Grupy Minterm muszą być prostokątne i mieć obszar, który jest potęgą dwójki (tj. 1, 2, 4, 8...). Prostokąty Minterm powinny być jak największe, bez zer. Grupy mogą zachodzić na siebie, aby każda była większa. Optymalne ugrupowania w poniższym przykładzie są oznaczone zielonymi, czerwonymi i niebieskimi liniami, a grupy czerwona i zielona nakładają się na siebie. Czerwona grupa to kwadrat 2 × 2, zielona grupa to prostokąt 4 × 1, a obszar nakładania się jest oznaczony kolorem brązowym.
Komórki są często oznaczane skrótem, który opisuje logiczną wartość danych wejściowych, które pokrywa komórka. Na przykład AD oznaczałoby komórkę, która obejmuje obszar 2x2, gdzie A i D są prawdziwe, tj. komórki o numerach 13, 9, 15, 11 na powyższym schemacie. Z drugiej strony A D oznaczałoby komórki, w których A jest prawdziwe, a D jest fałszywe (czyli D jest prawdziwe).
Siatka jest połączona toroidalnie , co oznacza, że prostokątne grupy mogą zawijać się wzdłuż krawędzi (patrz rysunek). Komórki skrajnie po prawej są w rzeczywistości „sąsiadujące” z komórkami skrajnie lewymi, w tym sensie, że odpowiadające im wartości wejściowe różnią się tylko o jeden bit; podobnie są na samej górze i na dole. W związku z tym, D może być ważne określenie, że obejmuje komórki 12 i 8, w górnej części, i zawijane w dół i obejmują komórki 10 i 14, jak to B D , zawierający cztery narożniki.
Rozwiązanie
Po skonstruowaniu mapy Karnaugha i połączeniu sąsiednich jedynek prostokątnymi i kwadratowymi prostokątami, mintermy algebraiczne można znaleźć, sprawdzając, które zmienne pozostają takie same w każdym z prostokątów.
Dla czerwonej grupy:
- A jest takie samo i jest równe 1 w całym polu, dlatego powinno być uwzględnione w algebraicznej reprezentacji czerwonej mintermy.
- B nie utrzymuje tego samego stanu (przesuwa się od 1 do 0), dlatego należy go wykluczyć.
- C nie zmienia się. Jest zawsze 0, więc jego uzupełnienie, NOT-C, powinno być uwzględnione. Dlatego należy uwzględnić C.
- D się zmienia, więc jest wykluczone.
W ten sposób pierwszy minterm w logicznej sumy produktów z ekspresją jest C .
W przypadku zielonego zgrupowania A i B zachowują ten sam stan, podczas gdy C i D zmieniają się. B wynosi 0 i musi zostać zanegowane, zanim będzie można je uwzględnić. Drugim terminem jest zatem A B . Zauważ, że dopuszczalne jest, aby zielona grupa pokrywała się z czerwoną.
W ten sam sposób niebieska grupa daje termin BC D .
Rozwiązania każdej grupy są połączone: normalna forma obwodu to .
W ten sposób mapa Karnaugh poprowadziła do uproszczenia
Byłoby również możliwe wyprowadzenie tego uproszczenia przez ostrożne zastosowanie aksjomatów algebry Boole'a , ale czas potrzebny na to rośnie wykładniczo wraz z liczbą wyrazów.
Odwrotność
Odwrotność funkcji rozwiązuje się w ten sam sposób, grupując zamiast tego zera.
Wszystkie trzy terminy obejmujące odwrotność są pokazane w szarych ramkach z różnymi kolorowymi obramowaniami:
- brązowy : A B
- złoto : A C
- niebieski : BCD
Daje to odwrotność:
Poprzez wykorzystanie praw de Morgana The iloczyn sum można określić:
Nie obchodzi!
Mapy Karnaugha pozwalają również na łatwiejsze minimalizowanie funkcji, których tabele prawdy zawierają warunki „ nie obchodzi mnie to ”. Warunek „nie obchodzi mnie to” jest kombinacją danych wejściowych, dla których projektant nie dba o to, jakie są dane wyjściowe. W związku z tym warunki „nie obchodzi mnie” mogą być włączone lub wyłączone z dowolnej grupy prostokątnej, w zależności od tego, co ją zwiększa. Zazwyczaj są one oznaczone na mapie myślnikiem lub X.
Przykład po prawej jest taki sam jak powyżej, ale z wartością f (1,1,1,1) zastąpioną przez „nie obchodzi”. Pozwala to na rozszerzenie się terminu czerwonego całkowicie w dół, a tym samym całkowite usunięcie terminu zielonego.
Daje to nowe minimalne równanie:
Zauważ, że pierwszy termin to po prostu A , a nie A C . W tym przypadku nie obchodzi mnie termin (zielony prostokąt); uproszczony inny (czerwony); i usunięto zagrożenie wyścigu (usuwając żółty termin, jak pokazano w poniższej sekcji o zagrożeniach wyścigu).
Odwrotny przypadek jest uproszczony w następujący sposób:
Poprzez wykorzystanie praw de Morgana The iloczyn sum można określić:
Zagrożenia wyścigowe
Eliminacja
Mapy Karnaugh są przydatne do wykrywania i eliminowania warunków wyścigu . Zagrożenia związane z wyścigiem są bardzo łatwe do wykrycia za pomocą mapy Karnaugh, ponieważ warunki wyścigu mogą wystąpić podczas poruszania się między dowolną parą sąsiednich, ale rozłącznych regionów opisanych na mapie. Jednak ze względu na naturę kodowania Graya, sąsiednie ma specjalną definicję opisaną powyżej – w rzeczywistości poruszamy się po torusie, a nie prostokącie, owijając się wokół góry, dołu i boków.
- W powyższym przykładzie potencjalny stan wyścigu występuje, gdy C wynosi 1, a D wynosi 0, A wynosi 1, a B zmienia się z 1 na 0 (przejście ze stanu niebieskiego do stanu zielonego). W tym przypadku wyjście jest zdefiniowane tak, aby pozostało niezmienione na poziomie 1, ale ponieważ to przejście nie jest objęte określonym terminem w równaniu, istnieje potencjał usterki (chwilowe przejście wyjścia do 0).
- W tym samym przykładzie istnieje druga potencjalna usterka, która jest trudniejsza do zauważenia: gdy D wynosi 0, a A i B mają 1, przy czym C zmienia się z 1 na 0 (przejście ze stanu niebieskiego do stanu czerwonego). W tym przypadku usterka owija się od góry mapy do dołu.
To, czy usterki faktycznie wystąpią, zależy od fizycznego charakteru implementacji, a to, czy musimy się tym martwić, zależy od aplikacji. W logice taktowanej wystarczy, że logika ustali się na żądanej wartości w czasie, aby dotrzymać terminu czasowego. W naszym przykładzie nie rozważamy logiki taktowanej.
W naszym przypadku dodatkowy warunek wyeliminowałby potencjalne zagrożenie wyścigowe, łącząc stany wyjściowe zielony i niebieski lub stan wyjścia niebieski i czerwony: jest to pokazane jako żółty obszar (który owija się od dołu do góry po prawej stronie). połowa) na sąsiednim schemacie.
Termin jest zbędny pod względem statycznej logiki systemu, ale takie nadmiarowe lub uzgodnione terminy są często potrzebne, aby zapewnić dynamiczną wydajność bez wyścigu.
Podobnie, do odwrotności należy dodać dodatkowy termin, aby wyeliminować inne potencjalne zagrożenie wyścigowe. Zastosowanie praw De Morgana tworzy kolejny produkt wyrażenia sum dla f , ale z nowym współczynnikiem .
Przykłady map z 2 zmiennymi
Poniżej znajdują się wszystkie możliwe mapy Karnaugha z 2 zmiennymi i 2 × 2. Wymienione przy każdym z nich są minterms jako funkcja i minimalne równanie wolne od hazardu ( patrz poprzedni rozdział ). Minterm jest definiowany jako wyrażenie, które daje najbardziej minimalną formę wyrażenia mapowanych zmiennych. Można uformować wszystkie możliwe poziome i pionowe połączone bloki. Te bloki muszą być wielkości potęgi 2 (1, 2, 4, 8, 16, 32, ...). Te wyrażenia tworzą minimalne mapowanie logiczne minimalnych wyrażeń zmiennych logicznych dla wyrażeń binarnych, które mają być mapowane. Oto wszystkie klocki z jednym polem.
Blok może być kontynuowany w dolnej, górnej, lewej lub prawej części wykresu. To może nawet zawinąć poza krawędź wykresu, aby zminimalizować zmienną. Dzieje się tak, ponieważ każda zmienna logiczna odpowiada każdej pionowej kolumnie i poziomemu wierszowi. Wizualizację k-mapy można uznać za cylindryczną. Pola przy krawędziach po lewej i prawej stronie sąsiadują ze sobą, a góra i dół sąsiadują. Mapy K dla czterech zmiennych muszą być przedstawione w postaci pączka lub torusa. Cztery rogi kwadratu narysowanego przez k-mapę przylegają do siebie. Jeszcze bardziej złożone mapy są potrzebne dla 5 i więcej zmiennych.
Powiązane metody graficzne
Powiązane metody minimalizacji graficznej obejmują:
- Schemat Marquand (1881) Allana Marquand (1853-1924)
- Wykres Veitcha (1952) autorstwa Edwarda W. Veitcha (1924-2013)
- Mapa Mahoneya ( mapa M , oznaczenia liczb , 1963) autorstwa Matthew V. Mahoneya (symetryczne odbicia rozszerzenie map Karnaugha dla większej liczby wejść)
- Zmniejszone mapę Karnaugh (RKM) techniki (z 1969 roku), jak zmienne rzadkich , mapa wprowadzone zmienne (MeV), zmienna wprowadzone map (VEM) lub zmienne wprowadzone Karnaugh map (VEKM) GW Schultz, Thomas E. Osborne , Christopher R Clare, J. Robert Burgoon, Larry L. Dornhoff, William I. Fletcher, Ali M. Rushdi i inni (kilka kolejnych rozszerzeń mapy Karnaugha opartych na zmiennych danych wejściowych dla większej liczby danych wejściowych)
- Mapa pierścienia Minterm (MRM, 1990) autorstwa Thomasa R. McCalla (trójwymiarowe rozszerzenie map Karnaugha dla większej liczby wejść)
Zobacz też
- Algebraiczna postać normalna (ANF)
- Binarny diagram decyzyjny (BDD), struktura danych, która jest skompresowaną reprezentacją funkcji logicznej
- Minimalizator logiki heurystycznej Espresso
- Lista tematów algebry Boole'a
- Optymalizacja logiki
- Kwadrat Punneta (1905), podobny schemat w biologii
- Algorytm Quine'a-McCluskeya
- Reed-Muller ekspansja
- Schemat Venna (1880)
- Wielomian Żegalkina
Uwagi
Bibliografia
Dalsza lektura
- Katz, Randy Howard (1998) [1994]. Współczesny projekt logiki . Wydawnictwo Benjamin/Cummings . s. 70–85 . doi : 10.1016/0026-2692(95)90052-7 . Numer ISBN 0-8053-2703-7.
- Vingron, Szymon Peter (2004) [2003-11-05]. „Mapy Karnaugha”. Teoria przełączania: wgląd poprzez logikę predykatów . Berlin, Heidelberg, Nowy Jork: Springer-Verlag . s. 57-76. Numer ISBN 3-540-40343-4.
-
Wickes, William E. (1968). „3.5. Diagramy Veitcha”. Projektowanie logiki z układami scalonymi . Nowy Jork, USA: John Wiley & Sons . s. 36–49 . LCCN 68-21185 . P. 36:
[…] udoskonalenie diagramu Venna polegające na zastąpieniu kół przez kwadraty i ułożeniu w formie macierzy. Diagram Veitcha oznacza kwadraty z mintermami . Karnaugh przypisał jedynkom i zerom do kwadratów i ich etykiet oraz wydedukował powszechnie używany schemat numeracji.
- Maxfield, Clive "Max" (2006-11-29). „Logika Reeda-Mullera” . Logika 101 . Czasy EE . Część 3. Zarchiwizowane od oryginału w dniu 2017-04-19 . Źródło 2017-04-19 .
- Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977). „Sekcja 2.3”. Analiza i projektowanie sekwencyjnych systemów cyfrowych . Macmillan Prasa . Numer ISBN 0-33319266-4. (146 stron)
- Posiadacz, Michel Elizabeth (marzec 2005) [2005-02-14]. „Zmodyfikowana technika mapy Karnaugh” . Transakcje IEEE w dziedzinie edukacji . IEEE . 48 (1): 206–207. doi : 10.1109/TE.2004.832879 . eISSN 1557-9638 . ISSN 0018-9359 . S2CID 25576523 . [2]
- Cavanagh, Józef (2008). Arytmetyka komputerowa i podstawy Verilog HDL (1 wyd.). CRC Naciśnij .
- Kohawi, Zwi; Jha, Niraj K. (2009). Teoria przełączania i automatów skończonych (3 wyd.). Wydawnictwo Uniwersytetu Cambridge . Numer ISBN 978-0-521-85748-2.
Zewnętrzne linki
- Wykryj nakładające się prostokąty — Herbert Glarner.
- Wykorzystanie map Karnaugh w praktycznych zastosowaniach , Projekt projektowania obwodów do sterowania sygnalizacją świetlną.
- Samouczek K-Map dla 2,3,4 i 5 zmiennych
- Przykład mapy Karnaugh
- POCKET-PC BOOLEAN UPROSZCZENIE FUNKCJI, Ledion Bitincka — George E. Antoniou
- Rozwiązywanie problemów z mapą K