 |
DigitaltechnikProf. Jürgen Plate |
|
DigitaltechnikProf. Jürgen Plate |
Die Grundverknüpfungen NICHT, UND, ODER sind die logischen Grundoperationen (Grundfunktionen). Sie sind als Axiome definiert und werden postuliert (nicht beweisbar).
x1 ¦ x2 ¦ y
----+----+---
0 ¦ 0 ¦ 0
0 ¦ 1 ¦ 1
1 ¦ 0 ¦ 1
1 ¦ 1 ¦ 0
| Grundfunktion | Zeichen | Beispiel |
|---|---|---|
| Negation (NICHT) | ~ ! | y = ~x1 |
| Konjunktion (UND) | * & | y = x1 * x2 |
| Disjunktion (ODER | + | y = x1 + x2 |
Da in Gleichungen i. a. mehrere Grundfunktionen vorkommen, gibt es auch in der Boole'schen Algebra Vorrangregeln für die Reihenfolge der Durchführung der einzelnen Operationen. Die Negation besitzt die höchste Präferenz, danach folgt die Konjunktion und schließlich die Disjunktion. Zum Beispiel:
y = a + ~b * c mit a=1, b=0, c=0
y = 1 + ~0 * 0
= 1 + 1 * 0
= 1 + 0
= 1
Durch Klammerung kann die Präferenzreihenfolge verändert werden;
Klammerausdrücke werden zuerst ausgewertet. Zum Beispiel:
y = (a + ~b) * c mit a=1, b=0, c=0
y = (1 + ~0) * 0
= (1 + 1) * 0
= 1 * 0
= 0
Aus den logischen Grundfunktionen lassen sich beliebige Schaltfunktionen
zusammensetzen. Bauen wir doch gleich einmal eine einfache Schaltung,
einen digitalen Umschalter. Seine Funktion ist einfach: Wenn der Eingang
"G" (Gate) der Schaltung 0 ist, soll der Eingang "A" auf den Ausgang "Q"
durchgeschaltet werden, wenn G den Wert 1 besitzt, der Eingang "B".
Die Wahrheitstabelle lautet demnach:
| G | A | B | Q |
| 0 | 0 | X | 0 |
| 0 | 1 | X | 1 |
| 1 | X | 0 | 0 |
| 1 | X | 1 | 1 |
Die Schaltfunktion dazu:
Q = (~G * A) + (G * B)Und die Blockschaltung:
Ein zweites Beispiel ist schon etwas komplexer. Es soll eine zweistellige Dualzahl decodiert werden; es ist ein 1-aus-4-Decoder zu bauen. Für jeden Wert der Zahl (00, 01, 10, 11) soll genau ein Ausgang einen 1-Pegel führen, alle anderen Ausgänge sind 0. Die Wahrheitstabelle:
| A | B | Q1 | Q2 | Q3 | Q4 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
Dazu gibt es vier Schaltfunktionen:
Q1 = ~A * ~B Q2 = ~A * B Q3 = A * ~B Q4 = A * BDie Blockschaltung ist natürlich auch aufwendiger als die erste:
| 1 | x + 0 = x | x * 1 = x |
| 2 | x + 1 = 1 | x * 0 = 0 |
| 3 Idempotenz-Gesetz | x + x = x | x * x = x |
| 4 | x + ~x = 1 | x * ~x = 0 |
| 5 doppelte Negation | ~ ~x = x | |
| 6 Kommutativ-Gesetz | x1 + x2 = x2 + x1 | x1 * x2 = x2 * x1 |
| 7 Assioziativ-Gesetz | x1 + (x2 + x3) = (x1 + x2) + x3 | x1 * (x2 * x3) = (x1 * x2) * x3 |
| 8 Distributiv-Gesetz | x1 * (x2 + x3) = (x1 * x2) + (x1 * x3) | x1 + (x2 * x3) = (x1 + x2) * (x1 + x3) |
| 9 Absorptionsgesetz | x1 + (x1 * x2) = x1 | x1 * (x1 + x2) = x1 |
| 10 | x1 + (~x1 * x2) = x1 + x2 | x1 * (~x1 + x2) = x1 * x2 |
| 11 Expansiosgesetz | x1 = (x1 * x2) + (x1 * ~x2) | x1 = (x1 + x2) * (x1 + ~x2) |
| 12 Theoreme von de Morgan | ~(x1 + x2 + x3 + ... + xn) = ~x1 * ~x2 * ~x3 * ... * ~xn | ~(x1 * x2 * x3 * ... * xn) = ~x1 + ~x2 + ~x3 + ... + ~xn |
| 13 Shannonsches Inversionstheorem | ~F(x1,x2,x3,...,xn, +, *) = F(~x1,~x2,~x3,...,~xn, *, +) | |
Die Distributivgesetze werden vor allem in der umgekehrten Reihenfolge zum Ausklammern von Variablen oder Ausdrücken verwendet, um Schaltfunktionen zu vereinfachen.
Die de Morgan-Theoreme sind in der Praxis sehr bedeutsam, denn sie drücken die Dualität zwischen Konjunktion und Disjunktion aus. Die Disjunktion kann dementsprechend mitttels Konjunktion und Negation realisiert werden und umgekehrt. Damit reichen, wie oben schon erwähnt, zwei Grundoperationen aus, um alle Schaltfunktionen darzustellen. Andere Schreibweise (für 2 Variable):
x1 + x2 = ~(~x1 * ~x2) x1 * x2 = ~(~x1 + ~x2)
Das Shannonsches Inversionstheorem erlaubt das Invertieren einer Schaltfunktion. Dazu ein Beispiel. Gesucht wird die Inversion der Schaltfunktion
y = (x1 * (~x2 + (x3 * x4))) + (x2 * ~x4)Es ergibt sich auf konventiounellem Weg der Umformung:
~y = ~(x1 * (~x2 + (x3 * x4))) * ~(x2 * ~x4) = = (~x1 + ~(~x2 + (x3 * x4))) * (~x2 + x4) = = (~x1 + (x2 * ~(x3 * x4))) * (~x2 + x4) = = (~x1 + (x2 * (~x3 + ~x4))) * (~x2 + x4)Vergleicht man die Ausdrücke für y und ~y, zeigt sich, daß alle Variablen invertiert sind und alle Disjunktionen durch Konjunktionen ersetzt wurden und umgekehrt. Dies ist eine allgemeingültige Regel für das Invertieren einer Schaltfunktion, eben das Shannonsches Inversionstheorem.
y = x1 + (x2 * ~x3) + (~x2 + x3) ~y = ~x1 * (~x2 + x3) * ( x2 * ~x3)Bisher sind als Grundfunktionen mit zwei Variablen die Verknüpfungen UND und ODER bekannt. Zusammen mit der Funktion NICHT für eine Binärvariable sind alle Schaltfunktionen darstellbar. Die Auswahl dieser Grundfunktionen ist zwar willkürlich, aber wohlüberlegt. Andere Verknüpfungen sind teilweise sogar weniger aufwendig. Auch die zuvor behandelten Theoreme lassen sich für andere Grundfunktionen aufstellen. Es stellt sich also die Frage, welche weiteren Schaltfunktionen in der Praxis sinvoll sind. Es bleibt in der Regel bei folgenden Erweiterungen:
| NAND | Negierte UND-Verknüpfung |
| NOR | Negierte ODER-Verknüpfung |
| ÄQUIVALENZ | Funktion hat der Wert 1, wenn beide Eingänge gleich sind (auf beliebige Anzahl Eingänge erweiterbar) |
| ANTIVALENZ Exklusiv-Oder, (E)XOR | Die Funktion hat den Wert 1, wenn beide Eingänge ungleich sind (auf beliebige Anzahl Eingänge erweiterbar - nur ein Eingang darf 1 sein). Negation der Äquivalenz-Funktion. |
| INHIBITION | Die Funktion hat den Wert 1, wenn ein Eingang 0 UND der andere Eingang 1 ist. Daher gibt es zwei Inhibitionsfunktionen. |
Die Grundfunktionen NICHT, UND, ODER lassen sich durch die neuen Funktionen NAND und NOR, aber auch INHIBITION und IMPLIKATION darstellen. Die letzen beiden spielen in der Praxis jedoch keine so große Rolle. Die Realisierung mit NAND und NOR ist jedoch häufig anzutreffen. Hier werden auch von den Herstellern digitaler Schaltungen zahlreiche Gattertypen angeboten. Im Folgenden wird die Realisierung der drei Grundfunktionen durch NAND und NOR gezeigt.
| Funktion | Realisierung mit NAND | Realisierung mit NOR |
| NICHT | y = ~x = ~(x * x) = ~(x * 1) | y = ~x = ~(x * x) = ~(x + 0) |
| UND | y = x1 * x2 = ~ ~(x1 * x2)
|
y = x1 * x2 = ~(~x1 + ~x2)
|
| ODER | y = x1 + x2 = ~(~x1 * ~x2)
|
y = x1 + x2 = ~ ~(x1 + x2)
|
x1 x2 x3 y Minterme
0 0 0 0
0 0 1 1 → (~x1 * ~x2 * x3)
0 1 0 1 → (~x1 * x2 * ~x3)
0 1 1 0
1 0 0 1 → (x1 * ~x2 * ~x3)
1 0 1 1 → (x1 * ~x2 * x3)
1 1 0 1 → (x1 * x2 * ~x3)
1 1 1 0
y = (~x1 * ~x2 * x3) + (~x1 * x2 * ~x3) + (x1 * ~x2 * ~x3) +
+ (x1 * ~x2 * x3) + (x1 * x2 * ~x3)
Um zur konjunktiven Normalform zu gelangen werden alle Zeilenkombinationen
der Wahrheitstabelle herausgegriffen, bei der die Ausgangsvariable den Wert 0 annimmt
(Maxterme bzw. Volldisjunktionen). Beispiel:
x1 x2 x3 y Maxterme 0 0 0 0 → (x1 + x2 + x3) 0 0 1 1 0 1 0 1 0 1 1 0 → (x1 + ~x2 + ~x3) 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 → (~x1 + ~x2 + ~x3) y = (x1 + x2 + x3) * (x1 + ~x2 + ~x3) * (~x1 + ~x2 + ~x3)Alternativ stellt man zuerst die disjunktive Normalform für ~y auf. Beispiel:
x1 x2 x3 y Minterme 0 0 0 0 → (~x1 * ~x2 * ~x3) 0 0 1 1 0 1 0 1 0 1 1 0 → (~x1 * x2 * x3) 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 → (x1 * x2 * x3) ~y = (~x1 * ~x2 * ~x3) + (~x1 * x2 * x3) + (x1 * x2 * x3)Nach Negation beider Seiten erhält man mit dem Theorem von de Morgan:
y = (x1 + x2 + x3) * (x1 + ~x2 + ~x3) * (~x1 + ~x2 + ~x3)Disjunktive und konjunktive Normalform sind vollständig gleichwertig. Die DNF ist aus der Wahrheitstabelle leichter ablesbar und i. A. Basis für die anschließende Vereinfachung. Man kann aber auch den Ansatz wählen, daß man abhängig vom Wert der Ausgangsvariablen DNF oder KNF wählt:
Jede Schaltfunktion läßt sich immer durch eine zweistufige Schaltung realisieren.
Die Wahrheitstabelle ergibt sich dann zu:
| W | x3 | x2 | x1 | a | b | c | d | e | f | g |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 5 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 6 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
Die Gleichungen für die 7 Variablen lauten dann:
a = (~x3 * x2 * x1) + (x3 * ~x2 * ~x1) + (x3 * ~x2 * x1) b = ~(~x3 * ~x2 * ~x1) c = (x3 * ~x2 * x1) d = (~x3 * ~x2 * ~x1) + (~x3 * x2 * ~x1) + (x3 * ~x2 * ~x1) e = c f = b g = aNach Vereinfachung mit den Theoremen ergibt sich:
a = (x1 * x2) + x3 b = (x3 + x2 + x1) c = (x3 * ~x2 * x1) d = ~x1 e = c f = b g = aWas dann zur folgenden Schaltung führt:
Soll die Vorgeschichte, d.h. der Zustand der Ausgänge zu einem früheren Zeitpunkt eine Rolle spielen, ist eine Erweiterung um Speicherelemente notwendig. Schaltwerke sind Digitalschaltungen, bei denen der Zustand der Ausgänge zu jedem Zeitpunkt vom Zustand der Eingänge zu diesem Zeitpunkt und endlich vielen vorausgegangenen Zuständen abhängt. Der Zustand von endlich vielen vorhergegangenen Zeitpunkten führt zu inneren Zuständen, welche die Schaltung einnimmt.
Als Speicherelemente werden in der Regel Flipflops verwendet (siehe später).
An dieser Stelle soll als Beispiel für ein Schaltnetz ein Addierer für zwei Dualzahlen behandelt werden, der unter anderem den Kern des Rechenwerks bildet. Das Ergebnis der Addition ist nicht einstellig, denn wenn beide Summanden den Wert 1 haben, wird eine zweite Stelle benötigt. Es ergeben sich also zwei Ausgangsvariablen, ein Summenbit und ein Übertragsbit:
| x1 | x2 | Summe | Übertrag |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Aus dieser Wahrheitstabelle ist nun das Schaltnetz zu entwickeln. Es lassen sich für Summe (S) und Übertrag (Ü) zwei Schaltfunktionen aufstellen:
S = (~x1 * x2) + (x1 * ~x2) = (x1 + x2) * ~(x1 * x2) Ü = (x1 * x2)Die Funktionsgleichung für S kann durch Verwendung von Ü vereinfacht werden:
S = (x1 + x2) * ~ÜEs ergibt sich dann folgende einfache Schaltung:
Will man mehrstellige Dualzahlen addieren, muß das Addierschaltnetz bei jeder Stelle auch den Übertrag der vorhergehenden Stelle berücksichtigen, es kommt also eine Eingangsvariable hinzu. Der erste Gedanke wäre sicher, ein entsprechendes Schaltnetz zu entwerfen. Man kann aber auch zu S den Übertrag der vorhergehenden Stelle addieren, indem man einen zweiten Halbaddierer verwendet (die beiden Übertragsausgänge werden ODER-verknüpft):
Nun hat man einen Volladdierer für zwei Dualstellen. Zum Aufbau mehrstelliger Addierwerke wird lediglich der Übertrags-Ausgang einer Stelle mit dem Übertragseingang der nächsten verbunden.
 Zum vorhergehenden Abschnitt |
 Zum Inhaltsverzeichnis |
 Zum nächsten Abschnitt |