Eine Karnaugh-Tabelle ( ausgesprochen [ k a ʁ . N o ] ) ist eine grafische und einfache Methode, um eine logische Funktion aus ihrer Wahrheitstabelle zu finden oder zu vereinfachen . Es wird der Gray-Code (auch als reflektierte Binärdatei bezeichnet) verwendet, der die Haupteigenschaft hat, nur ein Bit zwischen zwei aufeinanderfolgenden Wörtern zu variieren (der Hamming-Abstand zweier aufeinanderfolgender Wörter des Gray-Codes ist gleich 1).
Diese Methode wurde 1953 von Maurice Karnaugh entwickelt und perfektionierte ein ähnliches Diagramm, das 1952 von Edward Veitch (in) eingeführt wurde .
Eine Karnaugh-Tabelle kann als eine bestimmte zweidimensionale Wahrheitstabelle angesehen werden, die mögliche Vereinfachungen visuell aufzeigen soll.
Nehmen wir an oder Variablen: Zum Beispiel werden wir der Identifizierung der Zeilen oder Variablen zuweisen , die anderen Variablen der Identifizierung der Spalten. Jedes Elementarfeld entspricht dann einer einzelnen Zeile und einer einzelnen Spalte, also einer einzelnen Kombination der Variablen.
Betrachten Sie den Fall einer Funktion der vier Variablen A, B, C, D, wobei die Variablen A und B den Zeilen, C und D den Spalten der folgenden Tabelle zugeordnet sind.
S. | CD | 00 | 01 | 11 | 10 |
---|---|---|---|---|---|
AB | |||||
00 | 0 | 1 | 1 | 0 | |
01 | 0 | 1 | 1 | 1 | |
11 | 0 | 1 | 1 | 1 | |
10 | 0 | 1 | 1 | 0 |
Diese Tabelle befindet sich in der Nähe des vorherigen Veitch-Diagramms. Um die angestrebten Vereinfachungen deutlicher zu machen, schlägt Karnaugh vor, für die Abfolge der Werte für C und D sowie für A und B einen Gray-Code zu verwenden , damit sich die Werte zweier aufeinanderfolgender Referenzen unterscheiden nur durch Ändern einer einzelnen Variablen und Aufdecken nützlicher Symmetrien. So :
Daher weisen wir dem Feld in Zeile 4, Spalte 2 den Wert von wann und zu . Dieser Wert kann in der Wahrheitstabelle oder durch eine zu vereinfachende Gleichung gefunden werden.
Die Werte der betrachteten Karnaugh-Tabelle entsprechen den Werten der folgenden Wahrheitstabelle:
BEIM | B. | VS | D. | S. | |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | |
0 | 0 | 0 | 1 | 1 | |
0 | 0 | 1 | 0 | 0 | |
0 | 0 | 1 | 1 | 1 | |
0 | 1 | 0 | 0 | 0 | |
0 | 1 | 0 | 1 | 1 | |
0 | 1 | 1 | 0 | 1 | |
0 | 1 | 1 | 1 | 1 | |
1 | 0 | 0 | 0 | 0 | |
1 | 0 | 0 | 1 | 1 | |
1 | 0 | 1 | 0 | 0 | |
1 | 0 | 1 | 1 | 1 | |
1 | 1 | 0 | 0 | 0 | |
1 | 1 | 0 | 1 | 1 | |
1 | 1 | 1 | 0 | 1 | |
1 | 1 | 1 | 1 | 1 |
Um die Gleichung von S zu finden, ist es einfach. Es gibt zwei Methoden:
Um eine Summe zu finden, müssen wir die Werte von S gleich 1 gruppieren . Die Anzahl der Einsen in jeder Gruppe sollte einer Potenz von 2 entsprechen. Die gebildeten Gruppen sollten so gering wie möglich sein, aber sie sollten alle Einsen enthalten . Eine 1 kann in mehr als einer Gruppe enthalten sein, es sollte jedoch keine 0 enthalten sein. Gruppen bestehen aus einer oder mehreren Spalten und einer oder mehreren Zeilen. Wenn möglich, setzen Sie sie nach gemeinsamen Eingabewerten zusammen. Beispielsweise haben Spalte 2 und Spalte 3 einen gemeinsamen Wert von D = 1. Zeile 1 und Zeile 4 haben den Wert B = 0 gemeinsam.
Gehen Sie für Tabellen mit 4 Variablen vorzugsweise in der folgenden Reihenfolge vor:
Im obigen Beispiel können wir ein Rechteck aus 8 Quadraten bilden, dann ein Quadrat aus 4 (das Rechteck aus den Spalten 2 und 3 und das Quadrat am Schnittpunkt der Zeilen 2-3 und Spalten 3-4). Das Rechteck entspricht der Gleichung "D", da in diesen beiden Spalten und nur in diesen beiden Spalten D immer gleich 1 ist. Das Quadrat entspricht der Gleichung "B · C", da in diesen Feldern und in diesen Feldern nur B = ist 1 und C = 1. S wird durch die Vereinigung der 2 Figuren dargestellt und die Gleichung von S wird erhalten: "S = D + B · C".
Diese einmal erlernte Methode ermöglicht es, auf den ersten Blick eine Gleichung zu finden, und bietet eine einfache Alternative zur Vereinfachung von Gleichungen, die schnell mühsam werden kann.
Diese Methode kombiniert nicht die " 1 ", sondern die " 0 ", um nicht eine Summe von Produkten, sondern ein Produkt von Summen zu finden.
Durch Gruppieren der Nullen finden wir S 'in Form einer Summe und durch Komplementation erhalten wir S in Form eines Produkts.
Hier Gruppierung von S 0 (oder 1 S ‚) erhalten wird S‘ = C'D ‚+ B'D‘ ist der erste Term für die 1 st Spalte und die zweiten vier Ecken. Nach De Morgans Regel ist S = (C + D) (B + D): S wird nun als Schnittpunkt von C + D, das die Spalten 1 bis 3 darstellt, und von B + D, das das Gesamtquadrat darstellt, gesehen außer den 4 Ecken.
Karnaugh-Tische / Arrays werden hauptsächlich in der Elektronik verwendet . In der Tat ermöglicht die Vereinfachung des booleschen algebraischen Ausdrucks das Speichern von Logikoperatoren ( Logikgattern ) und damit von Schaltungen. Dies spart außerdem Entwurfszeit und Geld und erhöht gleichzeitig die Zuverlässigkeit der Baugruppe.
Bei der Programmierung ermöglicht die Verwendung von Karnaugh-Tabellen, die Sequenzen komplexer Testbedingungen zu reduzieren, indem sie in Bedingungen gruppiert werden, die auf den ersten Blick nicht intuitiv sind, aber auch die effektive Komplexität des Codes (Volumen der Quelle) verringern als seine Zeit. Ausführung durch Reduzierung der Anzahl der erforderlichen Bewertungen.
Erweiterung auf teilweise definierte FunktionenManchmal ist die auszuführende Funktion nur teilweise definiert. Wenn eine Funktion beispielsweise von 4 Variablen abhängt, die die binäre Codierung einer Dezimalstelle darstellen, werden nur 10 von 16 Fällen definiert. Dann erhalten die undefinierten Zellen eine spezielle Markierung, die sich von 0 und 1 unterscheidet (zum Beispiel x oder Φ). und an die verwendeten Punkte annektierbar werden, ohne an die zu erreichenden Punkte angehängt zu werden. Wir können daher einfachere und kostengünstigere Lösungen finden, da undefinierte Fälle Teil der Möglichkeiten sind, ohne Teil der notwendigen Punkte zu sein. Wenn in unserem Beispiel 10 von 16 Fällen definiert sind, sind 2 ^ 6 = 64 vollständig bestimmte Funktionen mit unserer Funktion kompatibel, und jede Realisierung einer kompatiblen Funktion kann als Realisierung der angestrebten unvollständigen Funktion verwendet werden.