Gatterlogik

Boolsche Terme und Gleichungen

BILD

Logiktabellen

BILD

Logikpläne

BILD

• Technische Einrichtung zur Verknüpfungen von n Eingangssignalen xi

• Ausgangssignal sei y

• n=0;1;2;.... 2n

• Theoretisch sind 2 verschiedene Operatoren möglich

• Für n = 0 gibt es die beiden trivialen Möglichkeiten y = 0 und y = 1 (Konstanten)

• n = 1 heißt: Es gibt genau eine Eingangsvariable (hier: x1) Für n = 1 existieren vier verschiedene Funktionen: Neben den Konstanten und gibt es diese Möglichkeiten:

  BILD

• n = 2 heißt, es gibt genau zwei Eingangsvariablen (hier: x1 und x2) Für n = 2 existieren 16 verschiedene Funktionen.

• Es existieren 16 mögliche Schaltfunktionen

BILD

• Bei drei Eingängen sind 256 unterschiedliche Logikfunktionen möglich, bei vier Eingängen sind es bereits 65.536.

• Davon wird nur ein winziger Anteil auf typische Gatter abgebildet. Das sind:

  BILD

• Gatter mit drei oder mehr Eingängen können prinzipiell auch aus Zwei-Eingangs-Gattern nachgebildet werden. Dabei sind technischer Aufwand und Signalverzögerung größer.

BILD

• Boolesche Gleichungen, Funktionstabellen und Logikpläne

• dazwischen gibt es eindeutige Korrespondenzen

• Negationspunkte am Eingang sind nicht dasselbe wie Negationspunkte am Ausgang !!!

BILD

• Jede Boolesche Gleichung lässt sich eindeutig im Logikplan abbilden - und umgekehrt.

• Jede Verknüpfung entspricht einem Logikgatter.

• Jede Variable entspricht einem Leitungsnetz.

• Tabellen können Logik unvollständig abbilden.

Beispiel:

BILD

FOLIE

Der Wert einer logischen Funktion bleibt unverändert, wenn

• alle Eingangsvariablen negiert werden und

• die Ausgangsvariable negiert wird und

• die entgegen gesetzte logische Operation verwendet wird.

Beispiele:

BILD

• Jede denkbare Logikfunktion abbildbar sein

• Technischen Aufwand möglichst gering halten

• Beispiele:

  • AND, OR, Negation

  • NOR

  • NAND

Beispiel:

BILD

• Nur Operatoren AND, OR und Negation

• Disjunktive Normalform: Eingangsvariablen werden konjunktiv (AND) verknüpft, Konjunktionsterme werden disjunktiv (OR) verknüpft.

• Konjunktive Normalform: Eingangsvariablen werden disjunktiv (OR) verknüpft, Disjunktionsterme werden konjunktiv (AND) verknüpft.

• In den kanonischen Normalformen gehen in jeden Term alle Eingangsvariablen ein.

Beispiele:

BILD

Verschiedene Minimierungskriterien:

1. Gesamtmenge an Logikgatter - Fläche Chip oder Leiterplatte

2. Anzahl unterschiedlicher Gattertypen - Fertigungstechnik

3. Länge logischer Verkettungen - Rechenzeit

• Verfahren nach Karnaugh/Veith

• minimiert (1) und (3)

• benötigt AND- und OR-Gatter mit n Eingängen sowie NOT.

• Logiktabelle aufstellen.

  • KDN oder KKN hätten maximalen Aufwand!

• Alle Ausgangswerte ins KV-Diagramm übertragen

• Zusammenfassung von 2^n- Blöcken benachbarter Einsen/Nullen, dabei

• nicht vorgegebene Ausgangswerte '-' nur dort mit '1'/'0' belegen, wo es für möglicht große 2n-Blöcke hilfreich ist

• Alle Einsen/Nullen müssen mindestens ein mal abgedeckt sein

• Außerhalb aller 2^n-Block wird für '-' der Wert '0'/'1' angenommen

• Für jeden 2^n-Block wird der Konjunktions/Disjunktionsterm notiert

• Alle Konjunktionsterme werden disjunktiv (OR) verknüpft, bzw.

• Alle Disjunktionsterme werden konjunktiv (AND) verknüpft

• Bei n Eingangsvariablen müssen 2^n Felder vorgesehen werden

• Jedes Feld hat n Nachbarfelder, die sich jeweils in genau einer Eingangsvariablen unterscheiden

BILD

• Bis zu n = 5 ist grafisches Arbeiten noch praktikabel

• Methodisches Vorgehen gut auf Computerprogramme übertragbar

  BILD

Ergebnisse

• + liefert zweistufige Logik, dadurch kurze Laufzeiten

• - Benötigt ggf. Gatter mit sehr vielen Eingängen

• -Einbinden von XOR-Gattern verkompliziert die Arbeit

FOLIE

• Boolesche Gleichungen und Terme beschreiben logische Funktionen in mathematischer Form.

• Logiktabellen veranschaulichen die Funktion, können aber sehr umfangreich werden. Sie erlauben eine "Don't Care"-Belegung.

• Logikpläne bilden die technische Realisierung ab.

• Gebräuchliche Logikgatter sind NOT, AND, NAND, OR, NOR, XOR.

• Gatter der Typen AND, NAND, OR und NOR lassen sich mit einer größeren Anzahl von Eingängen realisieren (typ. bis >16).

• Die Rechenregeln der Booleschen Algebra erlauben die math. Umstellung logischer Verknüpfungen (z.B. de Morgan'sche Regel).

• Konjunktive und disjunktive Normalformen von logischen Verknüpfungen korrespondieren direkt mit der Logiktabelle.

• Das Minimierungsverfahren nach KV führt zu einer zweistufigen AND-OR-Logik mit minimalem technischen Aufwand.

• Logikgatter arbeiten grundsätzlich mit Verzögerung.

Eingangskapazitäten und elektr. Leitungen vergrößern diesen Effekt.