Kapitel2 TGDI
(:requiretuid:)
Einführung in TGDI – Kapitel 2
Autoren: Anna Wenzelburger, Moritz Fischer, Patrick Meyn
Dieses Kapitel enthält zunächst eine kurze Einleitung in logische Schaltungen. Danach widmen wir uns Boole'schen Gleichungen und den Regeln der Boole'schen Algebra. Weiterhin beschäftigen wir uns mit mehrstufiger kombinatorischer Logik, X's und Z's sowie Karnaugh Diagrammen. Zum Schluss werden noch einige kombinatorische Grundelemente vorgestellt und das Zeitverhalten von Schaltungen betrachtet.
Kombinatorische Logik
Einleitung
Eine logische Schaltung ist zusammengesetzt aus
- Eingängen
- Ausgängen
- Spezifikation der Funktion
- Spezifikation des Zeitverhaltens
Schaltungen
Schaltungen bestehen aus:
Verbindungsknoten (node)
- Eingangs-Terminals : A, B, C
- Ausgang-Terminals : Y, Z
- Internen Knoten : n1
Schaltungselementen:
- E1, E2, E3
- Jedes Schaltungselement ist wiederum eine Schaltung
Arten von logischen Schaltungen
Es gibt 2 Arten von logischen Schaltungen: kombinatorische und sequenzielle
Kombinatorische Logik
Kombinatorische Logik ist zustandslos und die Ausgänge hängen nur von den aktuellen Eingangswerten ab.
Sequenzielle Logik
Sequenzielle Logik speichert einen Zustand. Dabei hängt der Ausgangwert von den aktuellen Eingangswerten und gespeicherten Zuständen ab. Damit also auch von den vorherigen Eingangswerten.
Regeln für kombinatorische Zusammensetzung
Jedes Schaltungselement ist selbst kombinatorisch. Dabei ist jeder Verbindung der Schaltung entweder ein Eingang in die Schaltung oder an genau ein Ausgangsterminal eines Schaltungselements angeschlossen.
Die Schaltung enthält keine Zyklen. Das bedeutet, dass jeder Pfad durch die Schaltung jeden Verbindungsknoten maximal einmal besucht.
Boole'sche Gleichungen
Boole'sche Gleichungen beschreiben Ausgänge als Funktion der Eingänge. Dabei können die Eingänge selbst durch boole'sche Funktionen beschrieben sein. In diesem Fall gelten ebenfalls alle folgenden Regeln.
Grundlegende Definitionen
- Komplement: Boole'sche Variable mit einem Balken (invertiert)
- Literal: Variable oder ihr Komplement
- Implikant: Produkt von Literalen
- Minterm: Produkt (UND, Konjunktion) über alle Eingangsvariablen
- Maxterm: Summe (ODER, Disjunktion) über alle Eingangsvariablen
Disjunktive Normalform (DNF)
Die Disjunktive Normalform wird auch Sum-of-products (SOP) form genannt.
Jede Boole'sche Funktion kann in DNF formuliert werden. In einer Wahrheitswerttabelle enthält jede Zeile einen Minterm. Jeder Minterm ist die Konjunktion (also das Produkt, UND-Verknüpft) der Literale.
Dieser Minterm ist WAHR genau für diese eine Zeile. Die gesamte Funktion wird durch Disjunktionen (Summe, ODER-Verknüpfungen) der Minterme beschrieben, die am Ausgang WAHR liefern.
Die DNF wird also erstellt, indem man die Wahrheitswerttabelle betrachtet und schaut, wo der Ausgang 1 wird. In diesen Zeilen nimmt man sich die Eingangsvariablen und verknüpft deren Literale mit UNDs. Ist die Eingangsvariable 0, so geht ihr Literal negiert in den Minterm ein. Ist sie 1, ist ihr Literal im Minterm nicht negiert. Wenn mehrere Zeilen wahr geworden sind, nimmt man sich auch dort wieder die Belegung der Eingänge und verknüpft diese auch mit UNDs. Die einzelnen UND-Verknüpfungen werden dann mit ODERs verknüpft.
Konjunktive Normalform (KNF)
Die Konjunktive Normalform wird auch Products-of-sums (POS) form genannt.
Wie bei der DNF gilt auch hier: jede Boole'sche Funktion kann in KNF forumuliert werden. In einer Wahrheitswerttabelle enthält jede Zeile einen Maxterm. Jeder Maxterm ist die Disjunktion (also die Summe, ODER-Verknüpfung) der Literale.
Der Maxterm ist FALSCH genau für diese eine Zeile. Die gesamte Funktion wird durch Konjunktionen (Produkt, UND-Verknüpfung) der Maxterme beschrieben, die am Ausgang FALSCH liefern.
Die KNF wird also erstellt, indem man die Wahrheitswerttabelle betrachtet und schaut, wo der Ausgang 0 wird. In diesen Zeilen nimmt man sich die Eingänge und verknüpft deren Belegungen mit ODERs. Ist die Eingangsvariable 0, so geht ihr Literal nicht negiert in den Maxterm ein. Ist sie 1, ist ihr Literal im Maxterm negiert. Wenn mehrere Zeilen falsch geworden sind, nimmt man sich auch dort wieder die Belegung der Eingänge und verknüpft dieses auch mit ODERs. Die einzelnen ODER-Verknüpfungen werden dann mit UNDs verknüpft.
Beispiel für Boole'sche Funktion
Man schaut sich das Mittagsangebot der Mensa an. Dabei gibt es drei Ereignisse:
- Man wird dort nicht essen gehen
- Es ist nicht mehr geöffnet
- Es gibt nur Corned Beef-Variationen
Die Wahrheitswerttabelle dazu ist:
Man geht also, laut der Wahrheitswerttabelle nur in die Mensa, wenn sie geöffnet ist und es mehr als nur Corned Beef-Variatonen gibt.
DNF und KNF Formen.
Für die Wahrheitswerttabelle aus dem Beispiel oben stellen wir jetzt die DNF und die KNF auf.
Zur kurzen Erinnerung:
- DNF: die Zeilen, die WAHR sind, sind relevant
- KNF: die Zeilen, die FALSCH sind, sind relevant
Boole'sche Algebra
Axiome und Sätze sind Regeln, die hier zur Vereinfachung boole'scher Gleichungen dienen.
Sie funktionieren wie in der "üblichen" Algebra, teilweise aber auch einfacher, da die Variablen nur zwei Werte annehmen können (0 oder 1).
Axiome und Sätze haben jeweils duale Entsprechungen. Man muss dafür AND/OR und 0/1 tauschen.
T1 Neutralitätsgesetz
T2 Extremalgesetz
T3 Idempotengesetz
T4 Involution
T5 Komplentärgesetz
Sätze der Boole'schen Algebra mit mehreren Variablen
Beispiele für das Vereinfachen von Boole'schen Ausdrücken
De Morgan'sche Gesetze
Invertierungsblasen verschieben (bubble pushing)
Man kann die Blasen entweder rückwärts (vom Ausgang) oder vorwärts (vom Eingang) verschieben. Dabei ändert sich die Art das Gatters. Aus einem AND wird ein OR und umgekehrt. Warum das so ist erkennt man leicht an den De Morgan'schen Gesetzen.
Wenn man rückwärts verschiebt, hat man erst nur eine Blase am Ausgang. Daraus entstehen Blasen an allen Eingängen.
Beim Verschieben vorwärts müssen an allen Eingängen Blasen gewesen sein. Nach dem Verschieben gibt es nur eine Blase am Ausgang.
Was ist die boole'sche Funktion dieser Schaltung?
Wir verschieben vom hinteren NAND die Blase nach vorne. Dadurch erhalten wir ein OR mit je einer Blase am Ausgang.
Die Bubbles an den Ausgängen der NANDS und an den Eingängen des ORs heben sich gegenseitig auf (T4 Involution). Also ist die boole'sche Funktion dieses Gatters:
Regeln für das Verschieben von Invertierungsblasen
Man beginnt am Ausgang und arbeitet sich in Richtung der Eingänge vor. Dabei schiebt man die Blasen am Ausgang Richtung Eingang. Wenn man eine Blase verschiebt, so vertauscht man die Art des Gatters. Aus einem AND wird ein OR und umgekehrt. Man versucht dabei Blasen auszulöschen. Dies funktioniert, wenn zwei Blasen auf einer Leitung sind. Wenn der Eingang eine Blase hat, versuche den Ausgang ebenfalls mit einer Blase zu versehen und umgekehrt.
So löst man hier die Blasen auf:
Von Logik zu Gattern
Gatterlogik ist eine zweistufige Logik. Sie besteht aus ANDs, welche wiederum durch ORs verknüpft sind (vgl. DNF).
Das untere Beispiel beschreibt:
Lesbare Schaltpläne
Es gibt ein paar Konventionen, die das Lesen von Schaltplänen erleichtern und die deswegen auch eingehalten werden sollten:
- Eingänge sind auf der linken (oder oberen) Seite des Schaltplans
- Ausgänge sind auf der rechten (oder unteren) Seite des Schaltplans
- Gatter sollten von links nach rechts angeordnet werden (In seltenen Fällen, von oben nach unten)
- Gerade Verbindungen sind leichter lesbar als abknickende. Gerade lange Verbindungen sind daher besser zu lesen als kurze abknickende.
Regeln für Schaltpläne
- Drähte an T-Kreuzungen sind stets verbunden
- Sich überkreuzende Drähte werden durch Punkte als verbunden markiert
- Sich überkreuzende Drähte ohne Punkte sind nicht verbunden
Schaltungen mit mehreren Ausgängen
Es existieren auch Schaltungen mit mehreren Ausgängen. Ein einfaches Beispiel dafür ist ein Prioritäts-Encoder.
Bei diesem wird genau ein Ausgang entsprechend dem höchstwertigen gesetzten Eingangsbit auf TRUE gesetzt. Z.B. ist A3 = 1 so ist, unabhängig von der Belegung der anderen Eingänge, nur der Ausgang Y3 = 1 und alle anderen Yi = 0. Ist A3 = 0 und A2 = 1 so ist die Belegung von A1 und A0 irrelevant und nur Y2 = 1. Ein solches Verhalten, bei dem von einer Gruppe von Leitungen nur jeweils eine mit 1 und die anderen mit 0 belegt sind, wird auch als one-hot bezeichnet.
Somit ergibt sich für einen Prioritäts-Encoder mit 4 Ein- und Ausgängen folgende Wahrheitstabelle.
Folgende Schaltung realisiert dieses Verhalten.
Don't Cares, konkurrierende Treiber und der hochohmige Zustand
Ignorierbare Bits ("Don't Cares")
An der Wahrheitswerttabelle des Prioritäts-Encoders erkennt man sehr schön die ignorierbaren Bits. So bald A3 gesetzt ist, ist es egal, ob A2, A1 oder A0 auch gesetzt sind. Diese Bits können also ignoriert werden.
Konkurrierende Treiber: X
Es kann eine Konfliktsituation entstehen, bei der in einer Schaltung eine Leitung/Ausgang gleichzeitig auf 0 und auf 1 getrieben wird.
Dabei liegt der Analogwert irgendwo dazwischen (Spannungsteilung). Die Spannung kann einer 0 oder einer 1 entsprechen, oder im verbotenen Bereich dazwischen (siehe Störabstände) liegen. Diese Spannung kann auch mit der Betriebsspannung, Temperatur, Rauschen usw. variieren. Dies verursacht einen sehr hohen Energieverbrauch (Kurzschluss).
Ein Treiberkonflikt ist fast immer ein Entwurfsfehler und sollte unbedingt behoben werden!
Vorsicht! Das X steht sowohl für "don't care" und für Treiberkonflikt. Dies ist aber nicht das gleiche! Man muss den Kontext betrachten, um die korrekte Bedeutung zu erkennen.
Hochohmiger Ausgang: Z
Der hochohmige Ausgang Z wird auch offen, ungetrieben, floating, open oder high-impedance genannt.
Dieser kann 0 oder 1 sein, oder irgendwo dazwischen liegen, da die Leitung keinen aktiven Treiber besitzt.
Tristate-Busse
Hochohmige Knoten können zu Tristate-Bussen verschaltet werden.
- Tristate bedeutet, dass es 3 Zustände gibt. Nämlich 0, 1 und Z.
- Ein Bus ist ein System zur Datenübertragung zwischen mehreren Teilnehmern über einen gemeinsamen Übertragungsweg. Die Teilnehmer sind hier nicht an der Datenübertragung zwischen anderen Teilnehmern beteiligt.
Bei Tristate-Bussen gibt es viele verschiedene Treiber, von denen aber zu jedem Zeitpunkt immer nur genau einer aktiv ist. Die nicht aktiven Treiber sind hochohmig (Z).
Karnaugh Diagramme (Karnaugh maps)
Boole'sche Ausdrücke können durch Zusammenfassen minimiert werden. Dies ist oft sinnvoll, um Schaltungen kleiner/platzsparender zu halten. Dabei stellt ein Karnaugh-Diagramm die Zusammenhänge zwischen den einzelnen Ein-/und Ausgängen graphisch dar. Sie bilden einen Ausgangspunkt für eine Minimierung.
Daran erkennt man zum Beispiel folgende Vereinfachung:
Das Karnaugh-Diagramm liest man wie folgt:
- An der senkrechten Seite sind die Werte von C eingetragen. In der ersten Zeile ist C = 0 und in der zweiten Zeile gilt C = 1.
- Horizontal findet man die Werte von A und B. Dabei teilen sich A und B immer ein Kästchen. Darüber stehen die Belegungen. Also 00, wenn A = 0 und B = 0l sind. Die erste 0 steht für die Belegung von A und die zweite für die von B.
Wenn jetzt in der Wahrheitswerttabelle ein Ausgang WAHR geworden ist, so trägt man diese 1 in das Diagramm ein:
- In der ersten Zeile wird Y wahr für:
. Also schaut man im Diagramm, wo diese Belegung zutrifft und trägt dort eine 1 ein. (Hier das erste Kästchen in der ersten Zeile)
- In der zweiten Zeile wird Y wahr für
. Also schaut man wieder im Diagramm, wo diese Belegung zutrifft und trägt dort eine 1 ein. (Hier das erste Kästchen in der zweiten Zeile)
Es ist wichtig, dass die Beschriftung des Diagramms stimmt. Wie man an unserem Beispiel erkennen kann, ändert sich bei der horizontalen Beschriftung immer nur ein Bit. Es kommt nicht vor, dass 00 neben 11 steht. Wenn man dies nicht beachtet, funktioniert die Minimierung nicht.
Minimierung mit Karnaugh Diagrammen
Um die Schaltung zu minimieren, markiert man alle 1en in benachbarten Plätzen und bildet viereckige Bereiche. Dabei steht jedes zusammenhängende Gebiet für einen Implikanten.
Wenn in einem markierten Gebiet Literale sowohl normal als auch als Komplement auftauchen, so fallen diese Literale weg.
Karnaugh Diagramm mit drei Eingängen
Karnaugh Diagramm: Definitionen
- Das Komplement ist eine Variable mit Balken (invertierter Wert):
- Ein Literal ist eine Variable oder auch ihr Komplement
- Ein Implikant ist ein Produkt (UND-Verknüpfung) von Literalen
- Ein Primimplikant ist der Implikant der größten zusmammenhängenden viereckigen Fläche im Karnaugh-Diagramm
Minimierungsregeln für Karnaugh-Diagramme
- Jede 1 in einem K-Diagramm muss mindestens einmal markiert werden.
- Jeder viereckige Bereich hat als Seitenlänge eine Zweierpotenz an Flächen
- Jeder Bereich muss so groß wie mögliche sein (Primimplikant)
- Ein Bereich darf um die Ränder des K-Diagramms herum reichen. Deswegen ist es auch wichtig, dass die Beschriftung des Diagramms sich immer nur um 1 Bit unterscheidet. Man kann sich das Karnaugh-Diagramm also auch wie die Fläche eines Torus vorstellen.
- Ein "don't care" (X) darf markiert werden, wenn es die Fläche größer macht
- Das Ziel ist es, möglichst wenige Primimplikanten zur Abdeckung aller 1en zu haben
Karnaugh-Diagramm mit vier Eingängen
So sieht dann ein Karnaugh-Diagramm mit vier Eingängen aus:
Jetzt werden die Einträge minimiert:
Und so sieht das ganze mit "don't cares" aus:
Hier sieht man, dass "don't cares" markiert wurden. Allerdings nur, um Blöcke zu vergrößern. Alle, die keinen Block vergrößern wurden nicht markiert.
Kombinatorische Grundelemente
Multiplexer und Dekodierer (Decoders) sind zwei häufig verwendete kombinatorische Grundelemente.
Multiplexer (Mux)
Ein Mulitplexer wählt einen von N Eingängen aus und verbindet ihn mit dem Ausgang. Dabei gibt es einen log2N-bit breiten Selektoren-Eingang (auch Steuereingang, engl. select input).
Implementierung von Multiplexern
Man kann Multiplexer aus Logikgattern oder aus Tristate-Buffern implementieren.
Aus Logikgattern:
Dafür wird die Disjunktive Normal Form (SOP) verwendet.
Aus Tristate-Buffern:
Verwendet N Tristates für N-Eingangs-Mux. Diese Schalten zu jeder Zeit genau einen Tristate-Buffer durch. Der Rest ist Z.
Logikfunktionen aufgebaut aus Multiplexern
Verwende Mux als Wertetabelle (look-up table)
Man kann die Größe eines Multiplexers reduzieren
Dekodierer (Decoder)
Ein Dekodierer hat N Eingänge und 2N Ausgänge.
Bei den Ausgängen gilt "one-hot". Das heißt, dass zu jedem Zeitpunkt nur genau ein Ausgang 1 sein darf.
Implementierung von Dekodierern
Logik aufgebaut aus Dekodierern
Hierbei werden Minterme mit ODER verknüpft
Zeitverhalten (Timing)
Unter Zeitverhalten versteht man das Verhalten einer Schaltung in Relation zur Zeit. Interessant ist für uns die Verzögerung (delay), die zwischen einer Änderung am Eingang bis zur Änderung des Ausgangs besteht.
Wie können schnelle Schaltungen gebaut werden?
Ausbreitungs-(propagation) und Kontaminationsverzögerung (contamination delay)
Die Ausbreitungsverzögerung 
ist die maximale Zeit, die es dauert bis sich eine Änderung am Eingang am Ausgang auswirkt.
Die Kontaminationsverzögerung 
ist die minimale Zeit, die es dauert bis sich eine Änderung am Eingang am Ausgang auswirkt.
Mögliche Ursachen für Verzögerung sind:
Warum können und unterschiedlich sein?
- Unterschiedliche Verzögerungen für steigende und fallende Flanken
- Mehrere Ein- und Ausgänge mit unterschiedlich langen Verzögerungen
- Schaltungen werden
Kritische (lange) und kurze Pfade
Hier sieht man, dass der Pfad, ausgehend von D, sehr viel kürzer ist als der kritische Pfad. Dadurch können am Ausgang Y falsche Werte anliegen, bis die Daten über den kritischen Pfad am letzten AND angekommen sind.
Störimpulse (glitches)
Störimpulse treten auf, wenn eine Änderung eines Eingangs mehrere Änderungen des Ausgangs verursacht.
Diese können durch geeignete Entwurfsdisziplinen entschärft werden. Dabei können diese aber noch auftreten, richten jetzt aber keinen Schaden mehr an.
Man kann diese auch durch synchronen Entwurf beheben. (mehr dazu in einem späteren Kapitel)
Glitches sollten im Vorfeld erkannt werden. Man erkennt sie im Timing-Diagramm.
Was pasiert, wenn A = 0, C = 1 und B fällt von 1 auf 0?
Treten in einem Karnaugh-Diagramm einer Schaltung Bereiche auf, die aneinander grenzen, also nicht überlappen, ist dies ein Indiz dafür, dass es an dieser Stelle zu einem glitch kommen kann. In diesem Fall die Änderung der Belegung des Eingangs B.
Man beseitigt den glitch, indem man eine zusätzliche Implikante in die Schaltungsfunktion aufnimmt, die die beiden aneinander grenzenden Bereiche miteinander verbindet:
Warum Störimpulse beachten?
Störimpulse verursachen keine Probleme bei synchronem Entwurf. In der Regel gibt es aber auch dort Fehlerquellen (mehr dazu in Kapitel 3).
Störimpulse sollten aber erkannt werden. Entweder beim Debugging einer Schaltung im Simulator oder mit dem Oszilloskop.
Nicht alle Störimpulse können beseitigt werden. Es kann z.B. oft nicht vermieden werden, dass mehrere Eingänge gleichzeitig schalten.
Selbsttest
