Karnaugh-Karte - Karnaugh map

Ein Beispiel für eine Karnaugh-Karte. Dieses Bild zeigt tatsächlich zwei Karnaugh-Maps: für die Funktion ƒ mit Minterms (farbige Rechtecke) und für ihr Komplement mit Maxterms (graue Rechtecke). Im Bild bedeutet E () eine Summe von Minterms, die im Artikel als bezeichnet wird .

Die Karnaugh-Map ( KM oder K-Map ) ist eine Methode zur Vereinfachung von Ausdrücken der Booleschen Algebra . Maurice Karnaugh führte es 1953 als Verfeinerung von Edward W. Veitchs Veitch-Diagramm von 1952 ein , das eine Wiederentdeckung von Allan Marquands logischem Diagramm von 1881 alias Marquand-Diagramm war, jedoch mit einem Fokus jetzt auf seine Nützlichkeit für Schaltkreise. Veitch-Karten werden daher auch als Marquand-Veitch-Diagramme und Karnaugh-Karten als Karnaugh-Veitch-Karten ( KV-Karten ) bezeichnet.

Die Karnaugh-Karte reduziert die Notwendigkeit umfangreicher Berechnungen, indem sie die Mustererkennungsfähigkeit des Menschen nutzt. Es ermöglicht auch die schnelle Identifizierung und Beseitigung potenzieller Race-Conditions .

Die erforderlichen booleschen Ergebnisse werden aus einer Wahrheitstabelle auf ein zweidimensionales Gitter übertragen, wobei in Karnaugh-Maps die Zellen im Gray-Code geordnet sind und jede Zellenposition eine Kombination von Eingabebedingungen darstellt. Zellen werden auch als Minterms bezeichnet, wobei jeder Zellenwert den entsprechenden Ausgabewert der booleschen Funktion darstellt. Optimale Gruppen von Einsen oder Nullen werden identifiziert, die die Terme einer kanonischen Form der Logik in der ursprünglichen Wahrheitstabelle darstellen. Diese Begriffe können verwendet werden, um einen minimalen booleschen Ausdruck zu schreiben, der die erforderliche Logik repräsentiert.

Karnaugh-Maps werden verwendet, um die logischen Anforderungen der realen Welt zu vereinfachen, sodass sie unter Verwendung einer minimalen Anzahl von Logikgattern implementiert werden können. Ein Produktsummenausdruck (SOP) kann immer unter Verwendung von UND-Gattern implementiert werden , die in ein ODER- Gatter einspeisen , und ein Produktsummen-Ausdruck (POS) führt zu ODER-Gattern, die ein UND-Gatter speisen. Der POS-Ausdruck liefert ein Komplement der Funktion (wenn F die Funktion ist, ist sein Komplement F'). Karnaugh-Maps können auch verwendet werden, um logische Ausdrücke im Softwaredesign zu vereinfachen. Boolesche Bedingungen, wie sie beispielsweise in bedingten Anweisungen verwendet werden , können sehr kompliziert werden, wodurch der Code schwer zu lesen und zu warten ist. Einmal minimiert, können kanonische Summen-von-Produkten und Produkt-von-Summen-Ausdrücken direkt mit UND- und ODER-Logikoperatoren implementiert werden.

Beispiel

Karnaugh-Karten werden verwendet, um die Vereinfachung von Funktionen der Booleschen Algebra zu erleichtern . Betrachten Sie beispielsweise die boolesche Funktion, die durch die folgende Wahrheitstabelle beschrieben wird .

Wahrheitstabelle einer Funktion
  EIN 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
fünfzehn 1 1 1 1 0

Es folgen zwei verschiedene Notationen, die dieselbe Funktion in der nicht vereinfachten Booleschen Algebra beschreiben, unter Verwendung der Booleschen Variablen A , B , C , D und ihrer Umkehrungen.

  • Wo sind die zuzuordnenden Minterms (dh Zeilen mit Ausgabe 1 in der Wahrheitstabelle).
  • Wo sind die maxterms , die abgebildet werden sollen (dh Zeilen, die eine Ausgabe von 0 in der Wahrheitstabelle haben).
K-Map auf einem Torus und in einer Ebene gezeichnet. Die punktmarkierten Zellen grenzen aneinander.
K-Map-Konstruktion. Anstelle der Ausgabewerte (die Werte ganz rechts in der Wahrheitstabelle) zeigt dieses Diagramm eine dezimale Darstellung der Eingabe ABCD (die Werte ganz links in der Wahrheitstabelle), daher ist es keine Karnaugh-Abbildung.
In drei Dimensionen kann man ein Rechteck zu einem Torus biegen.

Konstruktion

Im obigen Beispiel können die vier Eingabevariablen auf 16 verschiedene Arten kombiniert werden, so dass die Wahrheitstabelle 16 Zeilen hat und die Karnaugh-Map 16 Positionen hat. Die Karnaugh-Karte ist daher in einem 4 × 4-Raster angeordnet.

Die Zeilen- und Spaltenindizes (die oben und unten auf der linken Seite der Karnaugh-Karte angezeigt werden) sind im Gray-Code statt in binärer numerischer Reihenfolge geordnet. Gray-Code stellt sicher, dass sich zwischen jedem Paar benachbarter Zellen nur eine Variable ändert. Jede Zelle der vollständigen Karnaugh-Abbildung enthält eine binäre Ziffer, die die Ausgabe der Funktion für diese Kombination von Eingaben darstellt.

Gruppierung

Nachdem die Karnaugh-Karte erstellt wurde, wird sie verwendet, um eine der einfachsten möglichen Formen – eine kanonische Form – für die Informationen in der Wahrheitstabelle zu finden. Benachbarte Einsen in der Karnaugh-Karte stellen Möglichkeiten dar, den Ausdruck zu vereinfachen. Die Minterms ('Minimalterms') für den endgültigen Ausdruck werden durch Einkreisen von 1er-Gruppen in der Karte gefunden. Minterm-Gruppen müssen rechteckig sein und eine Fläche haben, die eine Zweierpotenz ist (dh 1, 2, 4, 8...). Minterm-Rechtecke sollten so groß wie möglich sein und keine Nullen enthalten. Gruppen können sich überlappen, um jede Gruppe größer zu machen. Die optimalen Gruppierungen im Beispiel unten sind durch die grünen, roten und blauen Linien gekennzeichnet, und die roten und grünen Gruppen überlappen sich. Die rote Gruppe ist ein 2 × 2-Quadrat, die grüne Gruppe ist ein 4 × 1-Rechteck und der Überlappungsbereich wird in Braun angezeigt.

Die Zellen werden oft mit einer Abkürzung bezeichnet, die den logischen Wert der Eingaben beschreibt, die die Zelle abdeckt. AD würde zum Beispiel eine Zelle bedeuten, die den 2x2-Bereich abdeckt, in dem A und D wahr sind, dh die Zellen mit den Nummern 13, 9, 15, 11 im obigen Diagramm. Andererseits würde A D die Zellen bedeuten, in denen A wahr und D falsch ist (dh D ist wahr).

Das Gitter ist toroidal verbunden, sodass sich rechteckige Gruppen über die Kanten wickeln können (siehe Bild). Zellen ganz rechts sind tatsächlich 'angrenzend' zu denen ganz links, in dem Sinne, dass sich die entsprechenden Eingabewerte nur um ein Bit unterscheiden; ebenso die ganz oben und die ganz unten. Daher kann A D ein gültiger Begriff sein – er umfasst die Zellen 12 und 8 oben und wird nach unten umbrochen, um die Zellen 10 und 14 einzuschließen – ebenso wie B D , das die vier Ecken umfasst.

Lösung

Diagramm mit zwei K-Maps. Die K-Map für die Funktion f(A, B, C, D) wird als farbige Rechtecke dargestellt, die Minterms entsprechen. Der braune Bereich ist eine Überlappung des roten 2×2-Quadrats und des grünen 4×1-Rechtecks. Die K-Map für die Umkehrung von f wird als graue Rechtecke dargestellt, die maxterms entsprechen.

Nachdem die Karnaugh-Karte erstellt und die angrenzenden Einsen durch rechteckige und quadratische Kästchen verbunden wurden, können die algebraischen Minterms gefunden werden, indem untersucht wird, welche Variablen in jedem Kästchen gleich bleiben.

Für die rote Gruppierung:

  • A ist gleich und in der gesamten Box gleich 1, daher sollte es in der algebraischen Darstellung des roten Minterms enthalten sein.
  • B behält nicht den gleichen Zustand bei (er verschiebt sich von 1 auf 0) und sollte daher ausgeschlossen werden.
  • C ändert sich nicht. Es ist immer 0, daher sollte sein Komplement, NOT-C, eingeschlossen werden. Daher sollte C enthalten sein.
  • D ändert sich, ist also ausgeschlossen.

Somit ist der erste Minterm im booleschen Produktsummenausdruck A C .

Bei der grünen Gruppierung behalten A und B den gleichen Zustand bei, während sich C und D ändern. B ist 0 und muss negiert werden, bevor es eingeschlossen werden kann. Der zweite Term ist daher A B . Beachten Sie, dass es akzeptabel ist, dass sich die grüne Gruppierung mit der roten überlappt.

Ebenso ergibt die blaue Gruppierung den Begriff BC D .

Die Lösungen jeder Gruppierung werden kombiniert: Die normale Form der Schaltung ist .

Somit hat die Karnaugh-Karte eine Vereinfachung von

Diese Vereinfachung hätte man auch durch sorgfältige Anwendung der Axiome der Booleschen Algebra herleiten können , aber die Zeit dafür wächst exponentiell mit der Anzahl der Terme.

Invers

Die Umkehrung einer Funktion wird auf die gleiche Weise gelöst, indem stattdessen die Nullen gruppiert werden.

Die drei Terme, die die Umkehrung abdecken, werden alle mit grauen Kästchen mit unterschiedlichen farbigen Rändern dargestellt:

  • braun : A B
  • Gold : A C
  • blau : BCD

Dies ergibt die Umkehrung:

Durch die Anwendung der Gesetze von De Morgan kann das Produkt von Summen bestimmt werden:

Ist egal

Der Wert von für ABCD = 1111 wird durch ein "egal" ersetzt. Dadurch wird der grüne Term vollständig entfernt und der rote Term größer. Es ermöglicht auch, dass sich der blaue inverse Term verschiebt und größer wird

Karnaugh-Maps ermöglichen auch eine einfachere Minimierung von Funktionen, deren Wahrheitstabellen " egal "-Bedingungen enthalten. Eine "egal"-Bedingung ist eine Kombination von Eingaben, deren Ausgabe dem Designer egal ist. Daher können "egal"-Bedingungen in jede rechteckige Gruppe aufgenommen oder aus ihr ausgeschlossen werden, je nachdem, was sie größer macht. Sie sind normalerweise auf der Karte mit einem Bindestrich oder einem X gekennzeichnet.

Das rechte Beispiel ist das gleiche wie das obige Beispiel, jedoch wurde der Wert von f (1,1,1,1) durch ein "egal" ersetzt. Dadurch kann sich der rote Begriff ganz nach unten ausdehnen und entfernt somit den grünen Begriff vollständig.

Daraus ergibt sich die neue Minimumgleichung:

Beachten Sie, dass der erste Term nur A ist , nicht A C . In diesem Fall hat egal einen Begriff weggelassen (das grüne Rechteck); vereinfacht einen anderen (den roten); und die Renngefahr entfernt (Entfernung des gelben Begriffs, wie im folgenden Abschnitt über Renngefahren gezeigt).

Der umgekehrte Fall wird wie folgt vereinfacht:

Durch die Anwendung der Gesetze von De Morgan kann das Produkt von Summen bestimmt werden:

Renngefahren

Beseitigung

Karnaugh-Maps sind nützlich, um Race-Conditions zu erkennen und zu eliminieren . Rassengefahren sind mit einer Karnaugh-Karte sehr leicht zu erkennen, da eine Rassenbedingung bestehen kann, wenn Sie sich zwischen einem beliebigen Paar benachbarter, aber nicht zusammenhängender Regionen bewegen, die auf der Karte umschrieben sind. Aufgrund der Natur der Gray-Codierung hat benachbart jedoch eine spezielle Definition, die oben erläutert wurde – wir bewegen uns tatsächlich auf einem Torus und nicht auf einem Rechteck, das sich um die Oberseite, Unterseite und die Seiten wickelt.

  • Im obigen Beispiel liegt eine potenzielle Race Condition vor, wenn C 1 und D 0 ist, A 1 ist und B von 1 auf 0 wechselt (vom blauen Zustand in den grünen Zustand übergeht). Für diesen Fall wird die Ausgabe so definiert, dass sie unverändert auf 1 bleibt, aber da dieser Übergang nicht durch einen bestimmten Term in der Gleichung abgedeckt wird, besteht ein Potenzial für einen Glitch (ein kurzzeitiger Übergang der Ausgabe auf 0).
  • Im selben Beispiel gibt es einen zweiten potentiellen Störimpuls, der schwieriger zu erkennen ist: Wenn D 0 ist und A und B beide 1 sind, wobei C von 1 auf 0 wechselt (vom blauen Zustand in den roten Zustand übergeht). In diesem Fall wird der Glitch vom oberen Rand der Karte nach unten übertragen.
Race Hazards sind in diesem Diagramm vorhanden.
Obiges Diagramm mit hinzugefügten Konsensbegriffen, um Rassengefahren zu vermeiden.

Ob tatsächlich Störungen auftreten, hängt von der physischen Natur der Implementierung ab, und ob wir uns darum kümmern müssen, hängt von der Anwendung ab. Bei getakteter Logik reicht es aus, dass sich die Logik rechtzeitig auf den gewünschten Wert einpendelt, um die Zeitgabefrist einzuhalten. In unserem Beispiel betrachten wir keine getaktete Logik.

In unserem Fall würde ein zusätzlicher Term von die potenzielle Wettlaufgefahr eliminieren, indem er zwischen den grünen und blauen Ausgangszuständen oder blauen und roten Ausgangszuständen überbrückt: Dies wird als gelber Bereich angezeigt (der sich von unten nach oben rechts umläuft .) Hälfte) im nebenstehenden Diagramm.

Der Begriff ist redundante hinsichtlich der statischen Logik des Systems, aber eine solche redundante oder Konsensus Begriffe werden häufig benötigt race freie dynamische Leistung zu gewährleisten.

In ähnlicher Weise muss dem Inversen ein zusätzlicher Term von hinzugefügt werden, um ein weiteres potenzielles Race-Hazard zu eliminieren. Die Anwendung der De Morganschen Gesetze erzeugt ein weiteres Produkt des Summenausdrucks für f , jedoch mit einem neuen Faktor von .

Beispiele für 2-Variablen-Karten

Im Folgenden sind alle möglichen 2-Variablen, 2 × 2 Karnaugh-Maps aufgeführt. Aufgelistet sind jeweils die Minterms als Funktion und die Race-Hazard-free ( siehe vorheriger Abschnitt ) Minimum-Gleichung. Ein Minterm ist als Ausdruck definiert, der die minimalste Ausdrucksform der zugeordneten Variablen liefert. Alle möglichen horizontalen und vertikalen miteinander verbundenen Blöcke können gebildet werden. Diese Blöcke müssen die Größe der Potenzen von 2 haben (1, 2, 4, 8, 16, 32, ...). Diese Ausdrücke erzeugen eine minimale logische Abbildung der minimalen logischen Variablenausdrücke für die abzubildenden binären Ausdrücke. Hier sind alle Blöcke mit einem Feld.

Ein Block kann am unteren, oberen, linken oder rechten Rand des Diagramms fortgesetzt werden. Das kann sogar über den Rand des Diagramms hinausgehen, um die Variablen zu minimieren. Dies liegt daran, dass jede logische Variable jeder vertikalen Spalte und horizontalen Reihe entspricht. Eine Visualisierung der k-Map kann als zylindrisch betrachtet werden. Die Felder an den Rändern links und rechts grenzen aneinander, und die oberen und unteren grenzen aneinander. K-Maps für vier Variablen müssen als Donut- oder Torusform dargestellt werden. Die vier Ecken des von der k-Map gezeichneten Quadrats sind benachbart. Für 5 und mehr Variablen werden noch komplexere Karten benötigt.

Verwandte grafische Methoden

Zugehörige grafische Minimierungsmethoden umfassen:

  • Marquand-Diagramm (1881) von Allan Marquand (1853–1924)
  • Veitch-Diagramm (1952) von Edward W. Veitch (1924–2013)
  • Mahoney-Karte ( M-map , Bezeichnungsnummern , 1963) von Matthew V. Mahoney (eine reflexionssymmetrische Erweiterung von Karnaugh-Karten für eine größere Anzahl von Eingaben)
  • Reduzierte Karnaugh-Map (RKM)-Techniken (ab 1969) wie Infrequent Variables , Map- Entered Variables (MEV), Variable- Entered Map (VEM) oder Variable- Entered Karnaugh Map (VEKM) von GW Schultz, Thomas E. Osborne , Christopher R Clare, J. Robert Burgoon, Larry L. Dornhoff, William I. Fletcher, Ali M. Rushdi und andere (mehrere aufeinanderfolgende Karnaugh-Kartenerweiterungen basierend auf variablen Eingaben für eine größere Anzahl von Eingaben)
  • Minterm-Ring-Karte (MRM, 1990) von Thomas R. McCalla (eine dreidimensionale Erweiterung von Karnaugh-Karten für eine größere Anzahl von Eingaben)

Siehe auch

Anmerkungen

Verweise

Weiterlesen

Externe Links