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

Logische Zustände

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!

[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:

• Negation: Funktionstabelle

• Negation: Schaltsymbole, (1) → ISO, (2) → Amerika, (3) → alt

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

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

Logikgatter

Logikgatter

Logikgatter

Logikgatter

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.

• Konjunktion: Funktionstabelle

• Konjunktion: Schaltsymbole (1) → ISO, (2) → Amerika, (3) → alt

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

Logikgatter

Oder Gatter

Logische Funktion: Oder-Verknüpfung → Disjunktion

• Logische Verknüpfung zweier Eingangsvariablen.

• Disjunktion: Funktionstabelle

• Disjunktion: Schaltsymbole (1) → ISO, (2) → Amerika, (3) → alt

Logikgatter

Logikgatter

EXOR Gatter

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

• Logische Verknüpfung zweier Eingangsvariablen.

• EXOR Funktionstabelle

Logik Simulation

• Eine Logikschaltung besitzt Ein- und Ausgänge, d.h., beschrieben durch Vektoren X=(x₁,x₂,..,x_n) und Y=(y₁,y₂,..,y_m)

• 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

Logik Simulation

Logiktest

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,

Konjunktion

Und-Verknüpfung von n Eingangswerten zu einem Ausgangswert,

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:

• 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)

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):

• 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.

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:

• Ableitung der SOP Normalform aus Funktionstabelle:

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

→ 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:

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:

• Ableitung der SOP Normalform aus Funktionstabelle:

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

→ 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:

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

• Aufgabe: Bestimmung der Funktionstabelle aus obigen Anforderungen und Vereinbarungen

Boolesche Algebra

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.

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 a_i derart zusammen dass gilt:

3. Alle Teilterme werden summiert

Term 1:

Term 2:

Term 3:

DNF:

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 a_i derart zusammen dass gilt:

3. Alle Teilterme werden summiert

Term 1: , Term 2:

Term 3: , Term 4:

Term 5:

DNF:

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.

Boolesche Algebra

Assoziativgesetze mit 3 Variablen

Reihenfolge der Berechnung ist beliebig, die Zusammenfassung zweier Eingänge von Gattern ist beliebig.

Distributivgesetze mit 3 Variablen

Eine gemeinsame Variable in zwei verknüpften Termen kann ausgeklammert werden.

• Die zweite Gleichung kennt keine Analogie in der gewöhnlichen Algebra!

Boolesche Algebra

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!

Boolesche Algebra

Gesetzte der booleschen Algebra für Termumformungen

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,..}

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

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

Aufgabe

1. Minimiere die folgenden Booleschen Funktion mit Hilfsmitteln der Booleschen Algebra

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 F_i,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

KV Diagramme

Reduzierte disjunktive Normalform

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

• Benachbarte Felder F_i,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

KV Diagramme

Reduzierte disjunktive Normalform

• Die reduzierte DNF folgt dann:

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 F_i,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: .

• 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 als auch 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 oder oder nicht ausreichen, damit Q=1 wird.
• Dritter Term kein PI, da ausreicht, damit Q=1 wird (A=X)

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

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:

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)

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) →
(46) →

Verkürzte (minimierte) boolesche Funktion:

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:

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 { x₁,.., x_n} 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(2ⁿ/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(x₁,x₂)=¬x₁+¬x₂

BDD Verfahren

Shanon-Zerlegung

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

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

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(x₁,x₂,x₃)=x₁ • x₂ + x₃

BDD Verfahren

Abstrakter Syntaxbaum

• Alternativ kann die logische Formel (in syntaktischer Notation) zunächst im ersten Schritt durch einen Parser auf einen abstrakten Syntaxbaum (AST) abgebildet werden

  • Der AST besteht aus binären Operationen (Knoten haben zwei Eingangskanten)
  • Die Terme werden bereits evaluiert und vereinfacht

• Im zweiten Schritt wird aus dem AST ein BDD ähnlich der Shanonzerlegung gebildet (aber es wird immer nur ein binärer Term evaluiert)

BDD Verfahren

BDDVIEW

BDD Verfahren

Ordered BDD

Ein OBDD ist ein BDD, in dem auf jeden Pfad alle Variablen höchstens einmal und gemäß einer vorgegebenen Ordnung getestet bzw. evaluiert werden müssen.

Reduktion von BDDs

Die Reduktion eines (O)BDD’s hat das Ziel, die Anzahl der Pfade und Variablen zu minimieren, was in einer reduzierten und minimierten BF resultiert.

Löschregel

Die beiden Kanten eines Knotens v(x_i) verzweigen beide auf den gleichen Nachfolgeknoten w(x_j). Der Knoten v kann entfernt werden, und alle eingehenden Kanten werden auf w umgeleitet.

Zusammenfassungsregel

Zwei Knoten v(x_i) und w(x_i) der gleichen Variable besitzen gleiche 0- und 1-Nachfolger. Die Knoten v und w können zu einem neuen Knoten s und f zusammengefasst werden.

BDD Verfahren

• Für eine möglichst schnelle Suche, optimal Θ(log 2N), sollte der Baum balanziert sein, d.h. jeder Knoten hat zwei Nachfolger (außer Endknoten).

• Die Höhe eines Baumes ist dann minimal H=log 2N:

BDD Verfahren

• Für die Balanzierung eines Baumes benötigt man zwei Rotationsoperationen:

  1. Rechte Rotation im Uhrzeigersinn von zwei benachbarten Knoten,
  2. und linke Rotation gegen den Uhrzeigersinn.

• Rechte Rotation zweier Knoten q und p. Die weiterführenden Verzweigungen werden entsprechend der Ordnungsrelation umgeordnet (linkes Bild).

• Linke Rotation zweier Knoten q und p. Die weiterführenden Verzweigungen werden entsprechend der Ordnungsrelation umgeordnet (rechtes Bild).

BDD Verfahren

• Kombination aus Links- und Rechtsrotation führt zur Balanzierung eines linkslastigen asymmetrischen Baumes (linkes Bild).

• Kombination aus Rechts- und Linksrotation führt zur Balanzierung eines rechtslastigen asymmetrischen Baumes (rechtes Bild).

BDD Verfahren

Aufgabe

1. Erstelle von folgender BF einen BDD

2. Optimiere den BDD mit den eingeführten BDD Regelen

3. Leite die optimierte BF aus dem BDD ab.

BDD Verfahren

Lösung

BDD Verfahren

• Die Ableitung einer BF aus einem BDD wendet die inverse Shanon Zerlegung an

• Bei der Ableitung einer BF aus einem BDD beginnt man bei den 0/1 Blättern und aufwärts gehend baut man für jeden Knoten eine BF bis der Wurzelknoten erreicht wurde

• Beispiel: Knoten v₃(x₃) ist f₃=¬ x₃ • 0 + x₃ • 1 = x₃

Hazards

Wenn eine Hazard (Gefahr) in einer digitalen Schaltung auftritt, führt dies zu einer vorübergehenden Änderung der Ausgabe der Schaltung [2].

• D.h., ein Hazard in einer digitalen Schaltung ist eine vorübergehende Störung im idealen Betrieb der Schaltung, die nach einer unbestimmten Zeit von selbst aufgehoben wird.

• Diese Störungen oder Fluktuationen treten auf, wenn unterschiedliche Wege vom Eingang zum Ausgang unterschiedliche Verzögerungen haben, und aufgrund dieser Tatsache Änderungen der Eingangsvariablen den Ausgang nicht sofort ändern, sondern am Ausgang nach einer kleinen Verzögerung erscheinen, die durch die Logikgatter verursacht wird.

• In digitalen Schaltungen gibt es drei verschiedene Arten von Gefahren

  1. Statischer Hazard
  2. Dynamische Hazard
  3. Funktionaler Hazard

Hazards

Statische Hazards

Formal tritt ein statischer Hazard auf, wenn eine Änderung an einem Eingang dazu führt, dass sich der Ausgang kurzzeitig ändert, bevor er sich auf seinen korrekten Wert stabilisiert. Basierend auf dem korrekten Wert gibt es zwei Arten statischer Gefahren, wie in der folgenden Abbildung dargestellt:

Static-1-Hazard

Befindet sich der Ausgang aktuell im logischen Zustand 1 und nachdem der Eingang seinen Zustand geändert hat, ändert sich der Ausgang vor dem Setzen auf 1 vorübergehend auf 0, dann handelt es sich um eine Static-1-Gefahr.

Static-0-Hazard

Befindet sich der Ausgang aktuell im logischen Zustand 0 und nachdem der Eingang seinen Zustand geändert hat, ändert sich der Ausgang vor dem Setzen auf 0 vorübergehend auf 1, dann handelt es sich um eine Static-0-Gefahr.

Hazards

Erkennung statischen Hazards mit K-map

Betrachten wir zuerst die Gefahr von Statik-1. Um eine statische 1-Gefahr für eine digitale Schaltung zu erkennen, werden folgende Schritte ausgeführt:

Hazards

Schritt 1

Erstelle die BF für den Ausgang der digitalen Schaltung auf, Y(A,B,C,..).

Schritt 2

Erstelle einer K-Map für diese Funktion Y, und notiere alle angrenzenden 1-Werte.

Schritt 3

Wenn es ein Zellenpaar mit 1-Werten gibt, das nicht in derselben Gruppe zu liegen scheint (d.h. ein Prim-Implikant), zeigt dies das Vorhandensein einer statischen 1-Gefahr an. Jedes dieser Paare ist eine statische Gefahr.

---

Abb. 19. Beispiel Logikschaltung mit Hazards

Hazards

Das grün umrandete Paar von 1-Werten ist nicht Teil der gleichen Gruppierung / Paarung. Dies führt zu einer statischen Gefahr in diesem Schaltkreis.

Hazards

Beseitigung von statischen Hazards

• Sobald eine statische 1-Gefahr erkannt wurde, kann sie leicht beseitigt werden, indem der Funktion (Schaltung) weitere Terme (Logikgatter) hinzugefügt werden.

• Der gebräuchlichste Ansatz ist, die fehlende Gruppe in die vorhandene boolesche Funktion einzufügen, da das Hinzufügen dieses Terms die Funktion nicht beeinflusst, die Instabilität jedoch beseitigt.

• Da im obigen Beispiel das grün umrandete Paar von 1-Werten die statische-1-Gefahr verursacht, fügen wir dies wie folgt als Hauptimplikant für die vorhandene Funktion hinzu:

Hazards

• In ähnlicher Weise müssen für statische-0-Gefahren 0-Werte anstelle von 1-Nummern berücksichtigt werden.

• Wenn benachbarte 0-Werte in der K-map nicht in derselben Gruppe zusammengefasst sind, so können diese eine statische-0-Gefahr verursachen.

Hazards

• Die Methode zum Erkennen und Beseitigen der statischen 0-Gefahr ist völlig analog wie die für die statische 1-Gefahr, außer dass anstelle von SOP POS verwendet wird, da es sich in diesem Fall um 0-Werte handelt.

Aufgabe

1. Implementiere die Schaltungen aus Abb. 19 in Retro und weise die Logikhazards durch Testen nach

2. Wo verläuft der längste kombinatorische Pfad in der Schaltung?

3. Implementiere die modifizierte Schaltung aus Abb. 21 in Retro und weise Hazardfreiheit durch Testen exemplarisch nach.