Digitallogik

Logische Zustände

  • Logische Variablen besitzen die Wertemenge {0,1}

  • Die technologische Umsetzung und Implementierung von logischen Zuständen {0,1} findet i.A. durch elektronische Schaltungstechnik statt.

  • Logische Funktionen werden mit Funktions- oder Wahrheitstabellen beschrieben, die alle Kombinationen von Logikwerten der Eingangsvariablen auf ein oder mehrere Ausgangswerte abbilden.

  • Den logischen Zuständen werden i.A. zwei verschiedene Spannungspegel zugeordnet, deren Werte abhängig von der Schaltungstechnologie sind.

  • Es werden keine festen Spannungswerte sondern Spannungsbreiche (Intervalle) verwendet, z.B. für die TTL-Technologie, die mit einer Versorgungsspannung von 5V betrieben wird

\[\begin{mdmathpre}%mdk 0~\rightarrow \mathid{Low}~\rightarrow [0,0.8\mathid{V}]\\ 1~\rightarrow \mathid{High}~\rightarrow [3,5\mathid{V}]~ \end{mdmathpre}%mdk \]

Logische Zustände

figlevels5

Abb. 1. Eingangs- und Ausgangsspannungsbereiche von Digitallogik abhängig von Technologie und Versorgungsspannung (Links) TTL (Rechts) CMOS [1]

Logische Zustände

  • Der Grund von Spannungsintervallen liegt in einem möglichst großen Störabstand begründet, d.h. Immunität gegen Störungen, da digitale Spannungssignale bei der Technologieumsetzung tatsächlich als analoge Signale auftreten, d.h. wert- und zeitkontinuierliche Signale.

  • Ein nicht vermeidbares Phänomen, das Signalrauschen, welches physikalisch bedingt ist, führt immer zu einer Unsicherheit des Spannungspegels von digitalen Signalen.

  • Weiterhin können sich Logikpegel nihct beliebig schnell ändern (0 → 1, 1 → 0), und es gibt immer eine Zeitspanne in der sich ein technisches Logiksignal in einem undefinierten Zustand befindet!

figlevelac1[1]

Schaltungstechnologien

Es gibt verschiedene Schaltungstechnologien, mit denen Digitallogikschaltungen auf Transistorebene realisiert werden können.

Transistor-Transistor-Logic (TTL)

Bipolare Transistortechnik mit folgenden Eigenschaften:

  • Stromgesteuerte Stromquellen
  • Spannungsversorgung: 5V
  • Moderate Verlustleistung auch ohne Schaltaktivität.
  • Schaltgeschwindigkeiten im Bereich von 5ns

CMOS

Complementary Metall Oxide Substrate → Feldeffekt-Transistortechnik, Heute dominierender Technologieprozeß mit folgenden Eigenschaften:

  • Spannungsgesteuerte Stromquellen
  • Spannungsversorgung: 1-15V
  • Geringe statische Verlustleistung, geringe dynamische Verlustleistung bei Schaltaktivität.
  • Schaltgeschwindigkeiten technologieabhängig, im Bereich 1-10ns

Schaltungstechnologien

ECL

Emitter-Coupled-Logic → bipolare Transistortechnik mit folgenden Eigenschaften:

  • Stromgesteuerte Stromquellen
  • Spannungsversorgung: NECL → -5V
  • Hohe Verlustleistung auch ohne Schaltaktivität.
  • Sehr hohe Schaltgeschwindigkeit ≤ 1ns

Logikgatter

Logische Grundfunktionen der kombinatorischen Logik

Inverter

  • Logische Negierung einer Eingangsvariable x, Boolesche Algebra:
\[y = f(x) = x = \neg x = NOT(x) \]
  • Negation: Funktionstabelle
x y=¬ x
0 1
1 0
  • Negation: Schaltsymbole, (1) → ISO, (2) → Amerika, (3) → alt

figsymneg

Logikgatter

Inverter: CMOS Transistorschaltung

CMOS: Complimentary Metal Oxide Substrate Technologie

  • Die Transistorschaltung besteht aus einem sog. N-Kanal (unten) und dazu im Verhalten komplementären P-Kanal (oben) MOS-Feldeffekttransistor, mit selbstsperrenden Verhalten.

  • Weitere elektronische Bauelemente sind zur Implementierung im Gegensatz zu der Bipolartransistortechnik nicht erforderlich.

  • Das in der Digitaltechnik gewünschte Schaltverhalten {0,1} ergibt sich aus dem analogen Übertragungsverhalten der Transistoren, d.h. der Kennlinie eines N-/P-MOSFET-Transistors.

  • Vereinfacht kann ein Transistor als steuerbarer Schalter verstanden werden. Jedoch: Ein FET Transistor ist eine spannungsgesteuerte Stromquelle.

Logikgatter

figinvcmos1

Abb. 2. Zwei komplimentäre MOSFET Transistoren bilden einen logischen Inverter

Logikgatter

CMOS Transistorschaltung

  • Ein FET-Transistor besitzt drei Anschlüsse:
Source S

Dieser Anschluss ist als Ladungslieferant zu verstehen, d.h. der Quelle für elektrische Ladungsträger, den Elektronen (neg.), oder den sog. Löchern (pos.).

Drain D

Gegenüber der Ladungsquelle befindet sich die Ladungssenke, über den ein Fluss von Ladungsträgern stattfinden kann.

Gate G

Der Gate-Anschluss beeinflusst den Ladungstransport zwischen Source und Drain-Anschluss, und ermöglicht eine spannungsgesteuerte Stromquelle.

  • Ein sog. selbstsperrender Transistor ist dadurch gekennzeichnet, dass bei einer Gate-Source-Spannung UGS=0V kein Drain-Strom fließt, man spricht von einem sperrenden Transistorzustand.

Logikgatter

  • Der andere Zustand eines Transistors ist der leitende Zustand, bei dem ein elektrischer Strom zwischen Source und Drain-Anschluss IDS fließen kann.

  • Neben den drei Anschlüssen {S,G,D} gibt einen sog. Substrat-Anschluss, der mit einem fixen Potential verbunden ist.

  • Aus Gründen der Übersichtlichkeit verwendet man vereinfachte elektronische Transistorsymbole, die im folgenden ausschließlich verwendet werden.

Elektronische Schaltsymbole von MOSFET Transistoren

figcmos1

Logikgatter

figcmos2

Abb. 3. Kennlinie UGS-UDS eines N- und P-Kanal-MOSFET Transistors

Logikgatter

figinvcirc1

Abb. 4. Experimenteller Aufbau einer Inverterschaltung mit zwei MOSFET Transistoren (N- und P-Kanal)

Logikgatter

figinv2circ1

Abb. 5. Experimenteller Aufbau einer Doppelinverterschaltung mit zwei MOSFET Transistoren (N- und P-Kanal)

Logikgatter

figttl-nand-gatewww.electrical4u.com

Abb. 6. Zum Vergleich: Standard TTL NAND Gatter mit bipolaren Transistoren

Logikgatter

Aufgaben

  1. Man kann einen Inverter mit zwei Transistoren oder einem Transistor und einem Widerstand aufbauen. Überlege, was elektrotechnisch der Vorteil und der Nachteil wären.

  2. Warum sind bipolare Transistoren gegenüber Feldeffekttransistoren in der Digitallogik unterlegen?

  3. Welchen Nachteil haben FET Transistoren (physikalisch)

  4. Wo kommen die für einen P-Kanal MOSFET benötigten negativen Steuerspannungen her?

Logikgatter

Und Gatter

Logische Funktion: Und-Verknüpfung → Konjunktion

  • Logische Verknüpfung zweier Eingangsvariablen &arr; 1-Bit Multiplizierer.
\[f(x, y) = x \wedge y = x \bullet y \]
  • Konjunktion: Funktionstabelle
x y z=f(x,y) ¬z
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
  • Konjunktion: Schaltsymbole (1) → ISO, (2) → Amerika, (3) → alt

figsymand

Logikgatter

  • CMOS Technologie ist grundsätzlich invertierend → Inverter ist Elementarzelle der CMOS Logik!

  • Daher ist einfachste Implementierung eine Und Gatters ein Nicht-Und Gatter (NAND) → 4 Transistoren

figcmos3

Abb. 7. Transistorschaltung eines NAND und AND Gatters

Logikgatter

Oder Gatter

Logische Funktion: Oder-Verknüpfung → Disjunktion

  • Logische Verknüpfung zweier Eingangsvariablen.
\[f(x, y) = x \vee y = x + y \]
  • Disjunktion: Funktionstabelle
x y z=f(x,y) ¬z
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
  • Disjunktion: Schaltsymbole (1) → ISO, (2) → Amerika, (3) → alt

figsymor

Logikgatter

figcmos4

Abb. 8. Transistorschaltung eines NOR Gatters

Logikgatter

EXOR Gatter

Logische Funktion: Exklusiv-Oder-Verknüpfung → 1-Bit-Addierer!

  • Logische Verknüpfung zweier Eingangsvariablen.
\[f(x, y) = (x \wedge \neg y) ∨ (\neg x \wedge y) = x \bullet \neg y + \neg x \bullet y = x \oplus y \]
  • EXOR Funktionstabelle
x y z=f(x,y)
0 0 0
0 1 1
1 0 1
1 1 0

Logik Simulation

  • Eine Logikschaltung besitzt Ein- und Ausgänge, d.h., beschrieben durch Vektoren X=(x1,x2,..,xn) und Y=(y1,y2,..,ym)

  • Eine Logikschaltung ist eine Netzliste aus elementaren Logikgattern (z.B. aus einer Standardbibliothek)

  • Ein Logiksimulator kann ereignisbasiert die Änderung der Ausgangssignale bei einer Änderung der Eingangssignale und allen inneren Signalen berechnen

  • Wichtig: Ein technologisches Zeitmodell für die Signalausbreitung ist erforderlich und muss vom Simulator unterstützt werden

    • Jedes elektrische Signal hat eine endliche Ausbreitungs- und Änderungsgeschwindigkeit
    • Jede Transistorschaltung und jedes Gatter fügt Verzögerungen τi in einen Signalpfad ein

RETRO Simulator

  • RTL Simulator mit Verzögerungszeitmodell

Logik Simulation

figretro1

Abb. 9. ReTro Simulator und GUI

Logik Simulation

Logiktest

figautotestdig1

Abb. 10. Allgemeiner Aufbau eines automatischen Logiktesters (Äquivalenztest mit Funktionstabelle)

Logik Simulation

  • Ein Pulsgenerator zusammen mit einer Look-up Tabelle (LUT) erzeugen die Testmuster und steuert den Test.
    • Ein Pulsgenerator kann auch aus einem Binärzähler (n-Bit) aufgebaut werden
    • Die Look-up Tabelle definiert die Abbildung aller möglichen Muster der n-Bit Eingangssignale auf m-Bit Ausgangssignale → erwartetes Ergebnis

  • Das Eingabemuster wird gleichzeitig auf die LUT und die zu testende Schaltung (DUT, Dvice under Test) gegeben

  • Ein Komparator oder bei m=1 ein EXOR Gatter wird verwendet um das Ergebnis zu evaluiren

  • Ein nachfolgendes Register “sampled” das Vergleichsergebnis (Assertion true/false)

    • Warum ist ein Register erforderlich?

Logik Simulation

Aufgaben

  1. Implementiere die Boolesche Gleichung eines EXOR Gatters in ReTro mit elementaren Logikgattern

  2. Füge die Schaltung in eine Testumgebung ein (siehe Abb. 10), um die Wahrheitstabelle testen zu können.

Logik Simulation

Lösung

Boolesche Algebra

Definition Boolesche Algebra

  • Systeme logischer Variablen sind über logische Funktionen verknüpft. Die Funktion einer digitallogischen Schaltung, deren Ausgangswerte nur von den aktuellen Eingangswerten abhängen, wird durch boolesche Algebra beschrieben.

Die Boolesche Algebra besteht aus drei Operationen:

Disjunktion
Oder-Verknüpfung von n Eingangswerten zu einem Ausgangswert,
\[a=e_1+e_2+e_3+ .. +e_n \]
Konjunktion
Und-Verknüpfung von n Eingangswerten zu einem Ausgangswert,
\[a=e_1 \bullet e_2 \bullet e_3 \bullet .. \bullet e_n \]
Negation
Invertierung eines booleschen Wertes ¬e

Boolesche Algebra

  • Boolesche Werte besitzen eine Wertmenge {0,1}.

  • Boolesche Funktionen bilden n Variablen (n-dimensionaler Vektor) auf m Ergebniswerte (m-dimensionaler Vektor) ab:

\[f : B^n \rightarrow B^m \]

  • I.A. ist m=1, d.h. Verwendung von skalaren booleschen Funktionen.

  • Jede m-dimensionale Boolesche Funktion kann in einen Satz aus m skalaren Funktionen zerlegt werden (ohne weitere Transformation)

\[\begin{gathered} f(a,b,c) = \left( {\begin{array}{*{20}{c}} {a + b + c} \\ {a + \neg b + c} \\ {\neg a + b + c} \end{array}} \right) \Leftrightarrow \hfill \\ {f_1}(a,b,c) = a + b + c \hfill \\ {f_2}(a,b,c) = a + \neg b + c \hfill \\ {f_3}(a,b,c) = \neg a + b + c \hfill \\ \end{gathered} \]

Boolesche Algebra

  • Die Eingangsvektoren können graphisch bis n ≤ 3 dargestellt werden, z.B. für n=3 und den 3 Eingangsvariablen a,b,c, die jeweils eine Achse eines orthogonalen Koordinatensystems bezeichnen. Graphische Darstellung eines Booleschen Vektors (a,b,c):

figboolcube1

  • Ein Vektor (a,b,c) entspricht dann genau einem Punkt im 3-dimensionalen booleschen Zustandsraum.

Boolesche Algebra

Wahrheits-/Funktionstabellen

  • Boolesche Algebra ist Hilfsmittel beim Entwurf von digitalen Schaltungen.

  • Eine Aufgabenstellung definiert Schaltbedingungen, die in einer Funktions-/Wahrheitstabelle dargestellt werden.

  • Dabei können in einer Tabelle beliebige m-dimensionale Boolesche Funktionen als Verhaltensbeschreibung dargestellt werden, d.h., wie Eingangs- auf Ausgangswerte abgebildet werden.

switch1 switch2 motor1 light2
0 0 0 1
0 1 1 0
1 0 1 0
1 1 0 0

Boolesche Algebra

Normalformen

  • Diese Schaltbedingungen können auch durch boolesche Funktionen dargestellt werden, die aus der Funktionstabelle abgeleitet werden.

  • Die so gewonnenen Funktionen werden mittels Gesetzen der Booleschen Algebra umgeformt und vereinfacht, so dass eine technische Realisierung mit minimalen Aufwand erfolgen kann.

  • Aus Funktionstabellen werden im ersten Entwurfsschritt sog. Normalformen von logischen Funktionen abgeleitet. Man unterscheidet:

Disjunktive Normalform

Eine Summe aus Produkttermen (SOP)

Konjunktive Normalform

Ein Produkt aus Summentermen (POS)

Boolesche Algebra

Disjunktive Normalform (SOP)

  • Jeder Teilterm besteht aus einer Und-Verknüpfung der Eingangsvariablen, die entweder negiert oder nicht negiert im Term auftreten. Alle Teilterme werden Oder-verknüpft und ergeben die boolesche Funktion:
\[\begin{gathered} f({a_1},{a_2},{a_3},..,{a_n}) = (x_1^1 \bullet x_2^1 \bullet x_3^1 \bullet .. \bullet x_n^1) + (x_1^2 \bullet x_2^2 \bullet x_3^2 \bullet .. \bullet x_n^2) + .. \hfill \\ x_i^j = \{ {a_i},\neg {a_i}\} \hfill \\ \end{gathered} \]
  • Ableitung der SOP Normalform aus Funktionstabelle:
ai aj q
x x 1 → Teilterm
x x 0

Boolesche Algebra

  1. Nur Zeilen in der Funktionstabelle bei denen die Ausgangsvariable logisch 1 ist, führen zu einem Teilterm in der SOP-Normalform.
  2. Alle Eingangsvariablen werden Und-verknüpft und negiert, wenn die Eingangsvariable den Wert 0 besitzt.

Beispiel einer SOP Normalform

A B Q
0 1 1 → (¬ A • B)
1 0 1 → (A • ¬ B)
0 0 0
1 1 0

→ Q = (¬A•B) + (A•¬B)

Boolesche Algebra

Abbildung auf Digitallogik

  • Jede Boolesche Operation (+ *) wird auf Logikgatter abgebildet.

  • Negation werden auf Inverter abgebildet und ggfs. direkt in einer Verknüpfung integriert

Die boolesche Funktion Q führt zu folgender Digitallogikschaltung:

figbooldigsop1

Boolesche Algebra

Konjunktive Normalform

  • Jeder Teilterm besteht aus einer Oder-Verknüpfung der Eingangsvariablen, die entweder negiert oder nicht negiert im Term auftreten.

  • Alle Teilterme werden und-verknüpft und ergeben die boolesche Funktion:

\[\begin{gathered} f({a_1},{a_2},{a_3},..,{a_n}) = (x_1^1 + x_2^1 + x_3^1 + .. + x_n^1) \bullet (x_1^2 + x_2^2 + x_3^2 + .. + x_n^2) \bullet .. \hfill \\ x_i^j = \{ {a_i},\neg {a_i}\} \hfill \\ \end{gathered} \]
  • Ableitung der SOP Normalform aus Funktionstabelle:
ai aj q
x x 0 → Teilterm
x x 1

Boolesche Algebra

  1. Nur Zeilen in der Funktionstabelle bei denen die Ausgangsvariable logisch 0 ist, führen zu einem Teilterm in der POS-Normalform.
  2. Alle Eingangsvariablen werden Oder-verknüpft und negiert, wenn die Eingangsvariable den Wert 1 besitzt.

Beispiel einer POS Normalform

A B Q
1 1 0 → (¬ A + ¬ B)
0 0 0 → (A + B)
0 1 1
1 0 1

→ Q = (¬ A + ¬ B) • (A + B)

Boolesche Algebra

Beide Normalformen sind i.A. noch redundant, d.h. sie können vereinfacht werden.

  • Beide Normalformen können ineinander transformiert werden.
  • Die disjunktive Normalform SOP liefert kurze Gleichungen, wenn die Ausgangsvariable nur in wenigen Fällen logisch 1 ist, und die konjunktive beim Wert 0.

Boolesche Algebra

Technisches Beispiel

  • Eine Schaltmatrix mit drei Eingängen X=(A,B,C) und einem Ausgang Y soll bestimmt werden.

    • An den Ausgang Y ist eine Lampe angeschlossen.
    • Die Eingänge werden über Schalter gesteuert:
\[\begin{mdmathpre}%mdk \mathid{Taste}~1~\mathid{wird}~\mathid{gedrueckt}~\rightarrow \mathid{A}=1\\ \mathid{Taste}~2~\mathid{wird}~\mathid{gedrueckt}~\rightarrow \mathid{B}=1\\ \mathid{Taste}~3~\mathid{wird}~\mathid{gedrueckt}~\rightarrow \mathid{C}=1 \end{mdmathpre}%mdk \]

  • Immer wenn zwei Tasten gleichzeitig gedrückt werden (Xi=1,Xj=1), soll die Lampe leuchten (Y=1).

  • Aufgabe: Bestimmung der Funktionstabelle aus obigen Anforderungen und Vereinbarungen

Boolesche Algebra

figbooldiglog1

Abb. 11. Strukturelle und Verhaltensbeschreibung einer technischen Schaltung mit einer Funktionstabelle

Boolesche Algebra

Aufgabe

  1. Leite die Disjunktive Normalform aus der Wahrheitstabelle des technischen Beispiels ab.

  2. Leite die Konjunktive Normalform aus der Wahrheitstabelle des technischen Beispiels ab.

figbooldnf1

figboolknf1

Boolesche Algebra

Bestimmung der disjunktiven Normalform aus Funktionstabelle.

  1. Zeilen der Funktionstabelle, die als Ergebniswert y=1 besitzen, generieren einen Teilterm.
  2. Jeder Teilterm setzt sich aus dem Produkt aller Eingangsvariablen ai derart zusammen dass gilt:
\[x_{i - te{\text{ }}Variable}^{Term = Zeile} = \left\{ {\begin{array}{*{20}{c}} {{a_i}{\text{ wenn Eingangswert = 1}}} \\ {\neg {a_i}{\text{ wenn Eingangswert = 0}}} \end{array}} \right. \]
  1. Alle Teilterme werden summiert

Term 1: $\neg A \bullet B \bullet C$

Term 2: $A \bullet \neg B \bullet C$

Term 3: $A \bullet B \bullet \neg C$

DNF: $Y(A,B,C)=\neg A \bullet B \bullet C + A \bullet \neg B \bullet C + A \bullet B \bullet \neg C$

Boolesche Algebra

Bestimmung der konjunktiven Normalform aus Funktionstabelle.

  1. Zeilen der Funktionstabelle, die als Ergebniswert y=0 besitzen, generieren einen Teilterm.
  2. Jeder Teilterm setzt sich aus der Summe aller Eingangsvariablen ai derart zusammen dass gilt:
\[x_{i - te{\text{ }}Variable}^{Term = Zeile} = \left\{ {\begin{array}{*{20}{c}} {{a_i}{\text{ wenn Eingangswert = 0}}} \\ {\neg {a_i}{\text{ wenn Eingangswert = 1}}} \end{array}} \right. \]
  1. Alle Teilterme werden summiert

Term 1: $A + B + C$, Term 2: $A + B + \neg C$

Term 3: $A + \neg B + C$, Term 4: $\neg A + B + C$

Term 5: $\neg A + \neg B + C$

DNF: $Y(A,B,C)=A + B + C \bullet A + B + \neg C \bullet A + \neg B + C \bullet \neg A + B + C \bullet \neg A + \neg B + C$

Boolesche Algebra

Termumformungen

  • Mittels der booleschen Termumformungen können boolesche Ausdrücke mit folgenden Zielen umgeformt werden:
  • Reduzierung der Verknüpfungen,
  • Verbesserung der Signalaufeigenschaften
  • Transformation auf eine bestimmte Technologie, z.B. nur Nicht-Und-Verknüpfungen.
Kommutativ-Gesetze mit 2 Variablen
Die Variablen sind vertauschbar, die Eingänge von Und- bzw. Oder-Gattern können vertauscht werden.
\[\begin{gathered} x \bullet y = y \bullet x \hfill \\ x + y = y + x \hfill \\ \end{gathered} \]

Boolesche Algebra

Assoziativgesetze mit 3 Variablen
Reihenfolge der Berechnung ist beliebig, die Zusammenfassung zweier Eingänge von Gattern ist beliebig.
\[\begin{gathered} (x{\text{ }} \bullet {\text{ }}y){\text{ }} \bullet {\text{ }}z{\text{ }} = {\text{ }}x{\text{ }} \bullet {\text{ }}(y{\text{ }} \bullet {\text{ }}z){\text{ }} = {\text{ }}x{\text{ }} \bullet {\text{ }}y{\text{ }} \bullet {\text{ }}z \hfill \\ (x{\text{ }} + {\text{ }}y){\text{ }} + {\text{ }}z{\text{ }} = {\text{ }}x{\text{ }} + {\text{ }}(y{\text{ }} + {\text{ }}z){\text{ }} = {\text{ }}x{\text{ }} + {\text{ }}y{\text{ }} + {\text{ }}z \hfill \\ \end{gathered} \]
Distributivgesetze mit 3 Variablen
Eine gemeinsame Variable in zwei verknüpften Termen kann ausgeklammert werden.
\[\begin{gathered} (x{\text{ }} \bullet {\text{ }}y){\text{ }} + {\text{ }}(x{\text{ }} \bullet {\text{ }}z){\text{ }} = {\text{ }}x{\text{ }} \bullet {\text{ }}(y{\text{ }} + {\text{ }}z) \hfill \\ (x{\text{ }} + {\text{ }}y){\text{ }} \bullet {\text{ }}(x{\text{ }} + {\text{ }}z){\text{ }} = {\text{ }}x{\text{ }} + {\text{ }}(y{\text{ }} \bullet {\text{ }}z) \hfill \\ \end{gathered} \]
  • Die zweite Gleichung kennt keine Analogie in der gewöhnlichen Algebra!

Boolesche Algebra

figboolassoz1

Abb. 12. Beispiel der Anwendung des Assoziativgesetzes mit 3 Variablen

figbooldist1

Abb. 13. Beispiel für eine 3 → 2 Logikgatterminimierung mit dem Distributivgesetz und 3 Variablen

Boolesche Algebra

Inversionsgesetze mit 2 Variablen
Transformation von Und- nach Oder-Verknüpfung und umgekehrt; Negierung wandert von Eingängen zum Ausgang. Wichtig für Technologieumsetzung!
\[\begin{gathered} (\neg x \bullet \neg y) = \neg (x + y) \hfill \\ (\neg x + \neg y) = \neg (x \bullet y) \hfill \\ \end{gathered} \]

figbooldemorg

Abb. 14. De-Morgansche Regeln und Technologietransformation

Boolesche Algebra

Gesetzte der booleschen Algebra für Termumformungen

\[\begin{array}{*{20}{c}} {a \bullet 0 = 0}&{a \bullet 1 = a} \\ {a + 0 = a}&{a + 1 = 1} \\ {a \bullet a = a}&{a + a = a} \end{array} \]

Bindungsregeln

  1. Negation von Variablen oder Werten wird zuerst evaluiert.
  2. Und-Verknüpfung bindet stärker als Oder-Verknüpfung.
  3. Alle anderen Verknüpfungen werden von links nach rechts evaluiert.

Technische Logikzustände

Die boolesche Algebra kennt nur die zweiwertige Menge {0,1} zur Zustandsbeschreibung eines digitalen Wertes. Bei der technologischen Umsetzung können mehrwertige Logikzustände auftreten:

0

Starker logischer Wert False. Ein Signal mit diesem Wert darf mit keinem anderen starken Signal überlagert bzw. zusammengeschlossen werden (elektrisch: Kurzschluss!).

1

Starker logischer Wert True. Ein Signal mit diesem Wert darf mit keinem anderen starken Signal überlagert bzw. zusammengeschlossen werden.

L

Schwacher logischer Wert False. Schwache Signale können überlagert und mittels einer Auflösungsfunktion einen summierten Wert bilden.

H

Schwacher logischer Wert True. Schwache Signale können überlagert und mittels einer Auflösungsfunktion einen summierten Wert bilden.

Technische Logikzustände

Z

Hochohmiger Zustand. Mehrere Signale können überlagert und einen gemeinsamen Bus bilden. Der Zustand Z entkoppelt den schreibenden (treibenden) Zugriff eines Kommunikationsteilnehmers von einer Signalleitung. Die Signalleitung kann bidirektional verwendet werden. Lesender Zugriff ist aber jederzeit möglich.

X

Logischer Zustand ”Don’t-Care”. Bei der Evaluierung von booleschen Funktionen können dieses Zustände ignoriert werden, mit der Möglichkeit der Logikoptimierung.

Technische Logikzustände

Logiktypen in VHDL

bit

Zweiwertige Logik {0,1}

std_logic

Mehrwertige Logik {0,1,L,H,Z,X,..}

Example 1. (Beispiele in VHDL)
 

signal x: std_logic_vector(3 downto 0);
...
process triStateDriver(we,addr)
begin
  if we = ′1′ and addr=”00” then
    x <= ”0000”;
  elsif we = ′1′ and addr=”01” then
    x <= ”0001”;
  else
    x <= ”ZZZZ”; −− Tristate BUS State Disconnected
  end if;
end process;

Optimierung von Digitallogik

Ziele

  1. Verständnis der Ziele von Optimierungsverfahren in der Digitallogik
  2. Verständnis und Anwendung verschiedener systematischer Reduktionsverfahren und ihrer Möglichkeiten und Grenzen
  3. Grundkenntnis über moderne graphenbasierte Verfahren

Systematische Reduktion logischer Funktionen

Ziel der Minimierung:

  • Möglichst kleine Anzahl von Logikgattern bei der elektronischen Implementierung bei gleichzeitig geringer Signallaufzeit,

    • Gerade bei zwei-stelligen Operationen relevant (und Symmetrie wegen Hazards); n-stellige Operationen werden nicht verbessert!

  • Man unterscheidet vier grundlegenden Verfahren:

  1. Minimierung mittels Gesetzen der Booleschen Algebra - nicht systematisch.
  2. Karnaugh-Veitch-(KV) Diagramme, beschränkt auf kleine Anzahl von Funktionsvariablen.

Optimierung von Digitallogik

  1. Quine-McCluskey-Verfahren, systematisch, für mittlere Anzahl von Funktionsvariablen geeignet.
  2. Binary-Decision-Diagrams (BDD), häufig in Synthese-Programmen verwendet.

Aufgabe

  1. Minimiere die folgenden Booleschen Funktion mit Hilfsmitteln der Booleschen Algebra
\[\begin{gathered} f(a,b) = (a \bullet b) + (\neg a \bullet b) = ? \hfill \\ f(a,b,c,d) = a \bullet b \bullet c \bullet \neg b \bullet d = ? \hfill \\ f(a,b,c) = \neg (\neg a \bullet (\neg b + \neg c)) = ? \hfill \\ \end{gathered} \]

KV Diagramme

  • Die KV-Diagramm-Methode ist anschaulich und intuitiv, und soll als Einstieg verstanden werden.

  • Es findet eine Darstellung der Funktionstabelle in Zeilen und Spalten eines Diagramms statt. Dabei sind die Diagrammfelder so angeordnet, dass sich bei einem Übergang von einem zu einem anderen Feld immer nur eine Variable ändert.

  • Es existieren unterschiedliche Diagramme für DNF (SOP) und KNF (POS) Darstellungen.

  • In jedem Feld wird der zu den Werten der Eingangsvariablen gehörende Ausgangszustand/wert Fi,j={0,1} eingetragen.

  • Das Diagramm ist zyklisch: der Übergang von rechten Rand zum linken, und von unteren zum oberen ist möglich → Torusoberfläche

  • Bei drei Eingangsvariablen reduziert sich das Diagramm um zwei Zeilen.

KV Diagramme

figkv1

Abb. 15. (Links) KV-Diagramm für 4 Variablen A,B,C,D und DNF (Rechts) KV-Diagramm für 4 Variablen A,B,C,D und KNF.

KV Diagramme

Reduzierte disjunktive Normalform

  • Folgende Schritte sind zur Ableitung einer minimalen d.h. reduzierten DNF (RDNF) notwendig:

  • Benachbarte Felder Fi,j=1 werden zu Flächen mit 2N Elementen zusammengefasst. Die größtmöglichen Flächen/Gruppen sollen gebildet werden.

  • Alle Felder müssen in mindestens einer Fläche/Gruppe erfasst werden.

  • Ableitung eines neuen Teilterms der RDNF aus einer Fläche/Gruppe: Produkt aus allen Variablen, die allen Feldern der Gruppe gemeinsam sind.

  • Die Teilterme werden summiert.

KV Diagramme

figkv2

Abb. 16. Beispiel: KV-DNF

KV Diagramme

Reduzierte disjunktive Normalform

  • Die reduzierte DNF folgt dann:
\[f(A,{\text{ }}B,{\text{ }}C,{\text{ }}D){\text{ }} = \neg A \bullet \neg C + A \bullet C \bullet D + \neg B \bullet C \bullet \neg D \]

Es ist eine Reduktion von ursprünglich 49 booleschen Operationen und 8 Teiltermen auf 11 Operationen und 3 Teiltermen erfolgt! Nimmt man im Mittel 4 CMOS-Transistoren je boolescher Operation an, ergibt sich eine Verringerung der Transistoren von 196 → 44, und eine Verringerung der Chipfläche um den Faktor 2.11

KV Diagramme

Reduzierte konjunktive Normalform

Folgende Schritte sind zur Ableitung einer minimalen d.h. reduzierten KNF (RKNF) notwendig:

  1. Benachbarte Felder Fi,j=0 werden zu Flächen mit 2N Elementen zusammengefasst. Die größtmöglichen Flächen/Gruppen sollen gebildet werden.
  2. Alle Felder müssen in mindestens einer Fläche/Gruppe erfasst werden.
  3. Ableitung eines neuen Teilterms der RKNF aus einer Fläche/Gruppe: Summe aus allen Variablen, die allen Feldern der Gruppe gemeinsam sind.
  4. Die Teilterme werden multipliziert.

QM Verfahren

Verfahren nach Quine und McCluskey

Die QM-Methode ist formaler als das vorherige Diagrammverfahren. Zum Verständnis einige Definitionen:

Minterm
Produkterme (der DNF) werden als Minterme bezeichnet, wenn jede Variable einmal auftritt. Bei der vollständigen DNF ist jeder Produktterm ein Minterm.

Beispiel: $Q = A \bullet \neg B \bullet C \bullet \neg D + A \bullet B \bullet D$.

  • Der erste Term ist ein Minterm.
Maxterm

Summenterme (der KNF) werden als Maxterme bezeichnet, wenn jede Variable einmal auftritt. Bei der vollständigen KNF ist jeder Summenterm ein Maxterm.

Implikant

Ein Produktterm P heißt Implikant der booleschen Funktion Q, wenn aus P=1 ⇒ Q=1 folgt. Jeder Produktterm der DNF ist ein Implikant.

QM Verfahren

Beispiel: sowohl $A \bullet \neg B \bullet C \bullet \neg D$ als auch $A \bullet B \bullet D$ sind Implikanten von Q.

Primimplikant (Primterm)
Term, der nach Weglassen einer Variablen kein Implikant mehr wäre (kürzester Implikant).

Beispiel: Q=A•¬B•C•¬D + A•B•C + ¬A•¬B•C•¬D

  • Erste Term ist kein PI.
  • Zweiter Term ist ein PI, da $A \bullet B$ oder $B \bullet C$ oder $A \bullet C=1$ nicht ausreichen, damit Q=1 wird.
  • Dritter Term kein PI, da $\neg B \bullet C \bullet \neg D$ ausreicht, damit Q=1 wird (A=X)

Terme, in denen eine Variable komplementär auftreten, lassen sich verkürzen:

\[\begin{gathered} A \bullet \neg B \bullet C \bullet \neg D + \neg A \bullet \neg B \bullet C \bullet \neg D = \hfill \\ (A + \neg A) \bullet \neg B \bullet C \bullet \neg D = \neg B \bullet C \bullet \neg D \hfill \\ \end{gathered} \]

QM Verfahren

Schritt I
Alle Produktterme werden in einer Tabelle eingetragen. Für jede Variable wird der Wert eingetragen, damit Q=1 wird (Selektierte Funktionstabelle!). Beispiel:
\[\begin{gathered} Q = A \bullet B \bullet \neg C \bullet D + A \bullet B \bullet C \bullet \neg D + \neg A \bullet B \bullet C \bullet \neg D + \hfill \\ A \bullet B \bullet \neg C \bullet \neg D + \neg A \bullet B \bullet \neg C \bullet \neg D + A \bullet \neg B \bullet \neg C \bullet \neg D \hfill \\ \end{gathered} \]

figqm1

QM Verfahren

Schritt II
Terme, die sich nur in einer Variable unterscheiden, heißen ähnlich. Bildung der verkürzten Terme (nm) bedeutet: Ableitung aus Term (n) und (m). Im Beispiel sind das: (1) ⇔ (4), (2) ⇔ (3), (2) ⇔ (4), (3) ⇔ (5), (4) ⇔ (5), (4) ⇔ (6)

figqm2

QM Verfahren

Schritt III
Für die neuen verkürzten Terme wird Schritt II wiederholt. Der Vorgang endet, wenn keine 1-komplementären Terme mehr auftreten.

(2435) ⇒ X1X0
(2345) ⇒ X1X0

Schritt IV
Alle Terme, die nicht verkürzt werden konnten, sind Primterme:

(14) → $A \bullet B \bullet \neg C$
(46) → $A \bullet \neg C \bullet \neg D$

Verkürzte (minimierte) boolesche Funktion:

\[Q' = A \bullet B \bullet \neg C + A \bullet \neg C \bullet \neg D + B \bullet \neg D \]

QM Verfahren

Einzelne Primterme sind möglicherweise noch redundant. Ihre Anzahl lässt sich durch Bestimmung der minimalen Überdeckung noch minimieren.

Schritt V
Alle Produktterme (nicht minimiert) werden in Zeilen, und alle Primterme in Spalten einer neuen Tabelle eingetragen:


Im Beispiel: Suche der Überdeckungen zwischen Produkt- und Primtermen:

figqm3

QM Verfahren

Schritt VI

Alle Überdeckungen werden markiert (X), d.h. wenn ein Primterm vollständig in einem Minterm enthalten ist.

Schritt VII

Alle Primterme können weggelassen werden, solange in jeder Zeile mindestens eine Überdeckung vorhanden ist. Im Beispiel ist keine weitere Reduzierung möglich!

BDD Verfahren

Binary-Decision-Diagram (BDD)

  • Ein Binary-Decision-Diagram (BDD) ist ein azyklischer und gerichteter Graph, der einen Algorithmus zur Berechnung einer booleschen Funktion (BF) beschreibt.
  • Jede boolesche Funktion kann als BDD dargestellt werden.
  • Berechnung der dargestellten Funktion für einen gegebenen Eingangsvektor { x1,.., xn} beginnt an der Quelle (Wurzelknoten).
  • Ein BDD besteht aus einem Startknoten (Quelle) und inneren Knoten mit dem Ausgangsgrad 2.
  • Die inneren Knoten sind Variablen der BF zugeordnet.
  • Die beiden ausgehenden Kanten der inneren Knoten entsprechen der booleschen Wertemenge {0,1}.
  • Am Ende eines Pfades im BDD befindet sich eine Senke mit dem Ausgangsgrad 0.
  • Ein Pfad (Quelle → Senke) beschreibt die Evaluierung eines Funktionswertes der BF.

BDD Verfahren

  • Die Größe eines BDD’s ist maximal O(2n/n) bei einer BF mit n Variablen.
  • Nachteilige Eigenschaft von BDDs (wenn n groß ist): Die Tatsächliche Größe und Struktur eines BDD’s hängt von der Variablenreihenfolge bei der Erzeugung ab! (Ausnahme: symmetrische BF).

Beispiel: f(x1,x2)=¬x1+¬x2

figbdd1

BDD Verfahren

Shanon-Zerlegung

Erzeugung eines BDD’s aus BF schrittweise durch Evaluierung der einzelnen Variablen {x1,..,x2} mit den Werten {0,1}:

\[f({x_1},{x_2},..,{x_n}) = \neg{x_1}{f_{|{x_1} = 0}} + {x_1}{f_{|{x_1} = 1}} \]

Jeder innere Knoten stellt eine neue (Sub-) BF dar:

\[\begin{gathered} {f_{v1}}({x_1},{x_2}) = \neg {x_1} + \neg {x_2} = \neg {x_1}{f_{v2|{x_1} = 0}} + {x_1}{f_{v3|{x_1} = 1}} \hfill \\ {f_{v2}}({x_2}) = 1 + \neg {x_2} = 1,{f_{v3}}({x_2}) = 0 + \neg {x_2} = \neg {x_2} \hfill \\ \end{gathered} \]

figbdd2

BDD Verfahren

  • Die Tatsächliche Größe und Struktur eines BDD’s hängt von der Variablenreihenfolge bei der Erzeugung ab! (Ausnahme: symmetrische BF).

  • Beispiel zweier BDDs erzeugt aus f(x1,x2,x3)=x1 • x2 + x3