5- und 6-Variablen-Karnaugh-Diagramme meistern für effizientes Logikdesign

Je mehr kombinatorische Logik wächst, desto größer wird das Karnaugh-Diagramm. Zu wissen, wann ein 5- oder 6-Variablen-Diagramm angemessen ist – und wie man seine Zellen interpretiert und gruppiert – kann die Logiknutzung in FPGA- und ASIC-Designs drastisch reduzieren.

Altera (jetzt Teil von Intel) untersuchte Tausende von Kundendesigns, um typische Fan-In-Größen zu verstehen. Die resultierende Verteilung war fast flach von zwei bis sechs Eingängen, mit einem klaren Peak bei fünf. In der Praxis nutzen die meisten Schaltungen nicht mehr als sechs Eingänge, und das durchschnittliche Design passt bequem in fünf.

Alteras eigene Daten, extrahiert aus seiner Bibliothek von Kundendesigns, unterstützen den Wert von Heterogenität. Durch Untersuchung von Logik-Kegeln, Abbildung auf LUT-basierte Knoten und Sortierung nach der Anzahl der Eingänge, die an jedem Knoten optimal wären, fand Altera heraus, dass die Verteilung der Fan-Ins nahezu flach zwischen zwei und sechs Eingängen lag, mit einem schönen Peak bei fünf.

Unten ist ein klassisches Fünf-Variablen-Karnaugh-Diagramm.

Fünf-Variablen-K-Diagramm (Reflexions-Karte)

Der ältere Reflexionsstil beschriftet die Oberseite (und bei einer 6-Variablen-Karte die Seite) der Karte mit vollem Gray-Code. Der Gray-Code wird um die Mitte der Karte gespiegelt – eine Konvention, die in vielen klassischen Texten zu finden ist. Ein neueres, bevorzugtes Layout wird als Nächstes gezeigt.

Overlay-Version des K-Diagramms

Die Overlay-Karte besteht aus zwei identischen 4-Zellen-Unterkarten, die nur durch das höchstsignifikante Bit der 3-Bit-Adresse oben unterschieden werden. Die Nummerierung unterscheidet sich von der Reflexionskarte: Wenn die höchstsignifikante Ziffer ignoriert wird, erscheint die Sequenz 00, 01, 11, 10 in beiden Unterkarten. Die acht-Bit-Sequenz ist kein Gray-Code, aber das zweistellige Suffix 01, 10 ist es.

Wenden wir das Fünf-Variablen-Diagramm auf ein reales Problem an: Entwerfen Sie eine Schaltung, die einen 5-Bit-binären Eingang (A = MSB, B, C, D, E) akzeptiert und einen logischen HIGH ausgibt, wann immer die Binärzahl prim ist.

Die Primzahlen im 5-Bit-Bereich sind (1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31). Markieren Sie eine 1 in jeder entsprechenden Zelle, gruppieren Sie dann die Einsen. Beenden Sie mit dem Schreiben des vereinfachten Ausdrucks.

In der Reflexionskarte erstreckt sich die 4-Zellen-Gruppe A'B'E über zwei Spiegelpaare, während die 2-Zellen-Gruppe AB'DE als gespiegeltes Paar erscheint. Bei Verwendung der Overlay-Karte suchen Sie nach Spiegelbildern über die beiden Hälften hinweg.

Out = A'B'E + B'C'E + A'C DE + A'C D'E + ABCE + AB'DE + A'B'C'D

Unten ist die Overlay-Version desselben Ausdrucks.

Beim Vergleich der beiden Karten verschieben sich einige Zellen, da das Adressierungsschema unterschiedlich ist. Das Überlagern einer Hälfte auf die andere offenbart überlappende Gruppen, die die Vereinfachung leiten. Beispielsweise deckt die 4-Zellen-Gruppe A'B'E das Muster ABCDE = 00xx1 ab, was bedeutet, dass A, B und E fest auf 0,0,1 sind, während C und D variieren.

Ein Beispiel für ein Sechs-Variablen-Karnaugh-Diagramm folgt. Durch mentales Stapeln der vier Unterkarten können wir eine 4-Zellen-Gruppe identifizieren, die Out = C'F' implementiert.

Zur Illustration der 6-Variablen-Karte betrachten Sie einen 3-Bit-Magnitudenkomparator, der drei Ausgänge erzeugt: gleich, größer-als und kleiner-als. Der Komparator nimmt zwei 3-Bit-Eingänge A₂A₁A₀ und B₂B₁B₀ entgegen. Zur Vereinfachung lösen wir nur den A > B-Ausgang.

6-Variablen-K-Diagramm

Die untenstehende Overlay-Karte unterstützt die Vereinfachung der Logik für den A > B-Ausgang eines 3-Bit-Komparators. Der binäre Adresscode oben und entlang der linken Seite ist kein vollständiger 3-Bit-Gray-Code, aber die 2-Bit-Codes jeder der vier Unterkarten sind Gray.

Wo immer ABC XYZ übersteigt, wird eine 1 eingetragen. Die Karte wird entsprechend gefüllt.

Die Gruppierung folgt diesen Richtlinien:

• Eine Gruppe von 16 Zellen
• Zwei Gruppen von 8 Zellen
• Vier Gruppen von 4 Zellen

Die 16-Zellen-Gruppe AX' belegt die untere rechte Unterkarte. Zwei 8-Zellen-Gruppen werden durch Überlagern identischer 4-Zellen-Muster aus der oberen und unteren Unterkarte gebildet. Vier 4-Zellen-Gruppen erscheinen in der Karte; jede liefert einen Produktterm. Die finale Summenprodukt-Reduktion enthält sieben Terme.

Beim Zählen der 1s gibt es 28 Einsen. Vor der Reduktion würde der SOP 28 Produktterme mit je sechs Eingängen enthalten. Das K-Diagramm kollabiert dies auf sieben Produktterme mit vier oder weniger Eingängen – eine dramatische Vereinfachung.

Der Verdrahtungsplan wird weggelassen, aber hier ist die Stückliste für einen 3-Bit-Magnitudenkomparator (A > B) mit 4-TTL-Logikfamilien-Komponenten:

• 1 × 7410 Triple 3-Eingangs-NAND-Gatter (AX', ABY', BX'Y')
• 2 × 7420 Dual 4-Eingangs-NAND-Gatter (ABCZ', ACY'Z', BCX'Z', CX'Y'Z')
• 1 × 7430 8-Eingangs-NAND-Gatter (für den finalen 7-Term-Ausgang)

Zusammenfassung

• Boolesche Algebra, Karnaugh-Diagramme und CAD sind essenzielle Werkzeuge für Logikvereinfachung.
• Eine minimal-kostige Lösung verwendet die wenigsten Gatter mit den wenigsten Eingängen.
• Venn-Diagramme helfen, Boolesche Ausdrücke zu visualisieren, bevor sie in K-Diagramme übersetzt werden.
• K-Diagramm-Zellen sind in Gray-Code organisiert, was Redundanzen offenbart, die Vereinfachung ermöglichen.
• Summenprodukt (SOP) Ausdrücke werden typischerweise als UND-Gatter realisiert, die ein einzelnes ODER-Gatter speisen.
• SOP kann mit NAND-NAND-Logik realisiert werden, indem UNDs und ODERs durch NANDs ersetzt werden.
• Produktsummen (POS) ist seltener, kann aber mit ODER-Gattern realisiert werden, die ein einzelnes UND-Gatter speisen, basierend auf den 0s der Karte (Maxtermen).