Digitale Schaltungen - K-Map-Methode
In den vorherigen Kapiteln haben wir die Booleschen Funktionen mithilfe von Booleschen Postulaten und Theoremen vereinfacht. Es ist ein zeitaufwändiger Prozess und wir müssen die vereinfachten Ausdrücke nach jedem Schritt neu schreiben.
Um diese Schwierigkeit zu überwinden, Karnaughführte eine Methode zur einfachen Vereinfachung von Booleschen Funktionen ein. Diese Methode ist als Karnaugh-Kartenmethode oder K-Kartenmethode bekannt. Es ist eine grafische Methode, die aus 2 n Zellen für 'n' Variablen besteht. Die benachbarten Zellen unterscheiden sich nur in der Einzelbitposition.
K-Maps für 2 bis 5 Variablen
Die K-Map-Methode eignet sich am besten zum Minimieren der Booleschen Funktionen von 2 Variablen auf 5 Variablen. Lassen Sie uns nun die K-Maps für 2 bis 5 Variablen nacheinander diskutieren.
2 Variable K-Map
Die Anzahl der Zellen in 2 Variablen-K-Map beträgt vier, da die Anzahl der Variablen zwei beträgt. Die folgende Abbildung zeigt2 variable K-Map.
Es gibt nur eine Möglichkeit, 4 benachbarte Min-Terme zu gruppieren.
Die möglichen Kombinationen der Gruppierung von 2 benachbarten Min-Termen sind {(m 0 , m 1 ), (m 2 , m 3 ), (m 0 , m 2 ) und (m 1 , m 3 )}.
3 Variable K-Map
Die Anzahl der Zellen in 3 Variablen K-Map beträgt acht, da die Anzahl der Variablen drei beträgt. Die folgende Abbildung zeigt3 variable K-Map.
Es gibt nur eine Möglichkeit, 8 benachbarte Min-Terme zu gruppieren.
Die möglichen Kombinationen der Gruppierung von 4 benachbarten Min-Termen sind {(m 0 , m 1 , m 3 , m 2 ), (m 4 , m 5 , m 7 , m 6 ), (m 0 , m 1 , m 4 , m 5 ), (m 1 , m 3 , m 5 , m 7 ), (m 3 , m 2 , m 7 , m 6 ) und (m 2 , m 0 , m 6 , m 4 )}.
Die möglichen Kombinationen der Gruppierung von 2 benachbarten Min-Termen sind {(m 0 , m 1 ), (m 1 , m 3 ), (m 3 , m 2 ), (m 2 , m 0 ), (m 4 , m 5 ) (m 5 , m 7 ), (m 7 , m 6 ), (m 6 , m 4 ), (m 0 , m 4 ), (m 1 , m 5 ), (m 3 , m 7 ) und ( m 2 , m 6 )}.
Wenn x = 0 ist, werden aus 3 variablen K-Karten 2 variable K-Karten.
4 Variable K-Map
Die Anzahl der Zellen in 4 Variablen K-Map beträgt 16, da die Anzahl der Variablen vier beträgt. Die folgende Abbildung zeigt4 variable K-Map.
Es gibt nur eine Möglichkeit, 16 benachbarte Min-Terme zu gruppieren.
Es sei R 1 , R 2 , R 3 und R 4 die minimalen Terme der ersten Reihe, zweiten Reihe, dritten Reihe bzw. vierten Reihe. In ähnlicher Weise repräsentieren C 1 , C 2 , C 3 und C 4 die minimalen Terme der ersten Spalte, zweiten Spalte, dritten Spalte bzw. vierten Spalte. Die möglichen Kombinationen der Gruppierung von 8 benachbarten Min-Termen sind {(R 1 , R 2 ), (R 2 , R 3 ), (R 3 , R 4 ), (R 4 , R 1 ), (C 1 , C 2 ) , (C 2 , C 3 ), (C 3 , C 4 ), (C 4 , C 1 )}.
Wenn w = 0 ist, werden 4 variable K-Map zu 3 variablen K-Map.
5 Variable K-Map
Die Anzahl der Zellen in 5 Variablen K-Map beträgt zweiunddreißig, da die Anzahl der Variablen 5 beträgt. Die folgende Abbildung zeigt 5 variable K-Map.
Es gibt nur eine Möglichkeit, 32 benachbarte Min-Terme zu gruppieren.
Es gibt zwei Möglichkeiten, 16 benachbarte Min-Terme zu gruppieren. dh Gruppierung von min-Termen von m 0 bis m 15 und m 16 bis m 31 .
Wenn v = 0 ist, werden aus 5 variablen K-Karten 4 variable K-Karten.
In den vor allem K-Maps haben wir ausschließlich die Min-Terms-Notation verwendet. Ebenso können Sie ausschließlich die Max-Notation verwenden.
Minimierung von Booleschen Funktionen mit K-Maps
Wenn wir die Kombination von Eingaben betrachten, für die die Boolesche Funktion '1' ist, erhalten wir die Boolesche Funktion, die sich in befindet standard sum of products Formular nach Vereinfachung der K-Map.
Wenn wir die Kombination von Eingaben betrachten, für die die Boolesche Funktion '0' ist, erhalten wir in ähnlicher Weise die Boolesche Funktion, die sich in befindet standard product of sums Formular nach Vereinfachung der K-Map.
Folge diesen rules for simplifying K-maps um eine Standard-Produktsumme zu erhalten.
Wählen Sie die entsprechende K-Map basierend auf der Anzahl der in der Booleschen Funktion vorhandenen Variablen aus.
Wenn die Boolesche Funktion als Summe der minimalen Termform angegeben wird, platzieren Sie diese an den jeweiligen minimalen Termzellen in der K-Map. Wenn die Boolesche Funktion als Summe der Produktform angegeben wird, platzieren Sie diejenigen in allen möglichen Zellen der K-Map, für die die angegebenen Produktbegriffe gültig sind.
Überprüfen Sie, ob die maximale Anzahl benachbarter Gruppen gruppiert werden kann. Es sollten Zweierpotenzen sein. Beginnen Sie mit der höchsten Zweierpotenz und der niedrigsten Zweierpotenz. Die höchste Leistung entspricht der Anzahl der in der K-Map berücksichtigten Variablen und die niedrigste Leistung ist Null.
Jede Gruppierung gibt entweder einen wörtlichen oder einen Produktbegriff an. Es ist bekannt alsprime implicant. Der Hauptimplikant soll seinessential prime implicant, wenn mindestens eine einzelne '1' nicht mit anderen Gruppierungen abgedeckt ist, sondern nur mit dieser Gruppierung.
Notieren Sie alle Hauptimplikanten und wesentlichen Hauptimplikanten. Die vereinfachte Boolesche Funktion enthält alle wesentlichen Primimplikanten und nur die erforderlichen Primimplikanten.
Note 1 - Wenn für eine Kombination von Eingaben keine Ausgänge definiert sind, werden diese Ausgabewerte mit dargestellt don’t care symbol ‘x’. Das heißt, wir können sie entweder als '0' oder '1' betrachten.
Note 2- Wenn auch keine Begriffe vorhanden sind, platzieren Sie 'x' in den jeweiligen Zellen der K-Map. Betrachten Sie nur das nicht interessierende 'x', das für die Gruppierung der maximalen Anzahl benachbarter Elemente hilfreich ist. Behandeln Sie in diesen Fällen den Wert "egal" als "1".
Beispiel
Lasst uns simplify die folgende Boolesche Funktion, f(W, X, Y, Z)= WX’Y’ + WY + W’YZ’ mit K-Map.
Die angegebene Boolesche Funktion ist in Form von Produkten zusammengefasst. Es hat 4 Variablen W, X, Y & Z. Wir benötigen also4 variable K-map. Das4 variable K-map Die folgenden Angaben entsprechen den angegebenen Produktbedingungen.
Hier werden 1s in den folgenden Zellen der K-Map platziert.
Die Zellen, die dem Schnittpunkt von Zeile 4 und den Spalten 1 und 2 gemeinsam sind, entsprechen dem Produktterm. WX’Y’.
Die Zellen, die dem Schnittpunkt der Zeilen 3 und 4 und der Spalten 3 und 4 gemeinsam sind, entsprechen dem Produktbegriff. WY.
Die Zellen, die dem Schnittpunkt der Zeilen 1 und 2 und der Spalte 4 gemeinsam sind, entsprechen dem Produktterm. W’YZ’.
Es gibt keine Möglichkeit, 16 benachbarte oder 8 benachbarte zu gruppieren. Es gibt drei Möglichkeiten, 4 benachbarte zu gruppieren. Nach diesen drei Gruppierungen ist keine einzige mehr als nicht gruppiert. Wir müssen also nicht nach einer Gruppierung von 2 benachbarten suchen. Das4 variable K-map mit diesen drei groupings ist in der folgenden Abbildung dargestellt.
Hier haben wir drei Hauptimplikanten WX ', WY & YZ'. Alle diese Hauptimplikanten sindessential aus folgenden Gründen.
Zwei (m8 & m9)Gruppierungen der vierten Reihe werden von keiner anderen Gruppierung abgedeckt. Nur die Gruppierung der vierten Zeile deckt diese beiden ab.
Einzelne (m15)der quadratischen Gruppierung wird von keiner anderen Gruppierung abgedeckt. Nur die quadratische Gruppierung deckt diese ab.
Zwei (m2 & m6)der Gruppierung der vierten Spalte werden von keiner anderen Gruppierung abgedeckt. Nur die Gruppierung der vierten Spalte deckt diese beiden ab.
deshalb, die simplified Boolean function ist
f = WX’ + WY + YZ’
Folge diesen rules for simplifying K-maps um Standardprodukt der Summenform zu erhalten.
Wählen Sie die entsprechende K-Map basierend auf der Anzahl der in der Booleschen Funktion vorhandenen Variablen aus.
Wenn die Boolesche Funktion als Produkt der Form der Max-Terme angegeben ist, platzieren Sie die Nullen an den jeweiligen Max-Termzellen in der K-Map. Wenn die Boolesche Funktion als Produkt der Summenform angegeben wird, platzieren Sie die Nullen in allen möglichen Zellen der K-Map, für die die angegebenen Summenbegriffe gültig sind.
Überprüfen Sie, ob die maximale Anzahl benachbarter Nullen gruppiert werden kann. Es sollten Zweierpotenzen sein. Beginnen Sie mit der höchsten Zweierpotenz und der niedrigsten Zweierpotenz. Die höchste Leistung entspricht der Anzahl der in der K-Map berücksichtigten Variablen und die niedrigste Leistung ist Null.
Jede Gruppierung ergibt entweder einen Literal- oder einen Summenbegriff. Es ist bekannt alsprime implicant. Der Hauptimplikant soll seinessential prime implicant, wenn mindestens eine einzelne '0' nicht mit anderen Gruppierungen abgedeckt ist, sondern nur mit dieser Gruppierung.
Notieren Sie alle Hauptimplikanten und wesentlichen Hauptimplikanten. Die vereinfachte Boolesche Funktion enthält alle wesentlichen Primimplikanten und nur die erforderlichen Primimplikanten.
Note- Wenn auch keine Begriffe vorhanden sind, platzieren Sie 'x' in den jeweiligen Zellen der K-Map. Betrachten Sie nur das nicht interessierende 'x', das für die Gruppierung der maximalen Anzahl benachbarter Nullen hilfreich ist. Behandeln Sie in diesen Fällen den Wert "egal" als "0".
Beispiel
Lasst uns simplify die folgende Boolesche Funktion, $ f \ left (X, Y, Z \ right) = \ prod M \ left (0,1,2,4 \ right) $ unter Verwendung der K-Map.
Die angegebene Boolesche Funktion ist ein Produkt der Max-Termform. Es hat 3 Variablen X, Y & Z. Wir benötigen also 3 Variablen K-Map. Die angegebenen Max-Terme sind M 0 , M 1 , M 2 und M 4 . Die 3variable K-map In der folgenden Abbildung sind Nullen dargestellt, die den angegebenen Max-Termen entsprechen.
Es gibt keine Möglichkeit, 8 benachbarte Nullen oder 4 benachbarte Nullen zu gruppieren. Es gibt drei Möglichkeiten, zwei benachbarte Nullen zu gruppieren. Nach diesen drei Gruppierungen gibt es keine einzige Null mehr, die nicht gruppiert ist. Das3 variable K-map mit diesen drei groupings ist in der folgenden Abbildung dargestellt.
Hier haben wir drei Hauptimplikanten X + Y, Y + Z & Z + X. Alle diese Hauptimplikanten sind essential weil eine Null in jeder Gruppierung von keiner anderen Gruppierung abgedeckt wird, außer von ihren einzelnen Gruppierungen.
deshalb, die simplified Boolean function ist
f = (X + Y).(Y + Z).(Z + X)
Auf diese Weise können wir die Booleschen Funktionen mit der K-Map-Methode leicht auf bis zu 5 Variablen vereinfachen. Für mehr als 5 Variablen ist es schwierig, die Funktionen mit K-Maps zu vereinfachen. Weil die Anzahl dercells in K-Map bekommt doubled durch Einfügen einer neuen Variablen.
Aufgrund dieser Überprüfung und Gruppierung benachbarter Einsen (Min-Terme) oder benachbarter Nullen (Max-Terme) wird dies kompliziert. Wir werden diskutierenTabular method im nächsten Kapitel, um die Schwierigkeiten der K-Map-Methode zu überwinden.