Digitale Logik und Logikgatter einfach erklärt
In der digitalen Logik und auch in der Informatik muss man hin und wieder Bits miteinander verknüpfen, um zum Beispiel zu prüfen, ob sie bestimmte Bedingungen erfüllen. Um diese Verknüpfungsarten soll es in diesem Artikel gehen.Da stellt sich gleich die Frage: Was ist ein Bit?
Ein Bit ist ein Zustand, der nur zwei Werte annehmen kann: in der Informatik ist das 1 für wahr oder 0 für falsch und in der digitalen Elektronik arbeitet man mit unterschiedlichen Spannungspegeln: High (enstsprechend 1, z. B. +5V, also Strom fließt) und Low (entsprechend 0, 0V, Verbindung mit Ground, es fließt kein Strom). Der Einfachheit halber will ich mich in diesem Artikel nur auf die Verwendung von Einsen und Nullen beschränken. Eine 1 meint dann aber auch immer einen High-Pegel an einem Pin z. B. an einem IC und eine 0 einen Low-Pegel.
Allermeistens verknüpfen wir jeweils zwei Bits (A und B) miteinander, also eine 0 oder 1 mit einer anderen 0 oder 1. Und bekommen dann ein Ergebnisbit (Q), wieder eine 0 oder eine 1. Mit dem Ergebnisbit können wir dann weiterrechnen oder es weiterverknüpfen. Es gibt zwar auch logische Gatter in ICs wie den 7410-Chip, der NAND-Gatter mit drei Eingängen und einem Ausgang bietet, aber auf die wollen wir nicht in aller Ausführlichkeit eingehen. Außerdem ist das Prinzip das selbe, nur eben mit mehreren Einsen oder Nullen am Eingang.
Die Rechnungen der Verknüpfungen - es gibt bei 2 Bits ja nur 4 Kombinationen - stellt man in sogenannten Wahrheitstabellen dar, damit ganz klar ist, wie die Logik bzw. das Gatter funktioniert.
Arten von logischen Verknüpfungen
Es gibt mehrere Arten, wie man Bits miteinander verknüpfen kann. Je nach Verknüpfungsart kommt dann ein anderes Ergebnis heraus. Die Wahrheitstabellen der Verknüpfungsarten sind alle unterschiedlich.NOT, "Nicht" oder "Nein, andersrum!"
Die Not-Verknüpfung ist die einfachste Verknüpfung und hat nur einen Eingang und macht aus einer 1 eine 0 und aus einer 0 eine 1. Sie dreht den Wert also einfach um, man sagt auch, sie negiert oder invertiert ihn.Wahrheitstabelle NOT | |
---|---|
Eingang | Ausgang |
0 | 1 |
1 | 0 |
Logik-Symbol: ¬
Gatter-Symbol:
IC: 7404 (beinhaltet sechs Inverter)
Verwendung in Programmiersprachen:
Basic: NOT
C, Java, Python, etc.: ~ (im Gegensatz zum logischen NOT (!)
AND, "Und" oder "Alle müssen!"
Die Und-Verknüpfung hat zwei Eingänge und einen Ausgang, wie die meisten Verknüpfungen. Nur wenn alle Eingänge 1 sind, ist auch der Ausgang 1, ansonsten bleibt der Ausgang 0.Leitsatz: Wahr, wenn A UND B wahr sind.
Wahrheitstabelle AND | ||
---|---|---|
Eingang A | Eingang B | Ausgang |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Logik-Symbol: ⋀
Gatter-Symbol:
IC: 7408 (beinhaltet vier AND-Gatter mit je zwei Eingängen)
Verwendung in Programmiersprachen:
Basic: AND
C, Java, Python, etc.: & (im Gegensatz zum logischen UND (&&))
OR, "Oder" oder "Einer reicht aus."
Die Oder-Verknüpfung hat zwei Eingänge und einen Ausgang, wie die meisten Verknüpfungen. Wenn einer der Eingänge 1 sind, ist der Ausgang 1. Nur wenn alle Eingänge 0 sind, ist auch der Ausgang 0.Leitsatz: Wahr, wenn A ODER B wahr sind.
Wahrheitstabelle AND | ||
---|---|---|
Eingang A | Eingang B | Ausgang |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Logik-Symbol: ⋁
Gatter-Symbol:
IC: 7432 (beinhaltet vier OR-Gatter mit je zwei Eingängen)
Verwendung in Programmiersprachen:
Basic: OR
C, Java, Python, etc.: | (im Gegensatz zum logischen ODER (||)
XOR, "Exklusiv Oder" oder "Nur nicht drängeln. Immer nur einer!"
Die Exklusiv-Oder-Verknüpfung hat zwei Eingänge und einen Ausgang, wie die meisten Verknüpfungen. Nur wenn ein einziger der Eingänge 1 ist, ist auch der Ausgang 1. Sind mehrere oder keiner 1, dann bleibt der Ausgang 0.Leitsatz: Wahr, wenn ENTWEDER A ODER B wahr sind.
Wahrheitstabelle XOR | ||
---|---|---|
Eingang A | Eingang B | Ausgang |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Logik-Symbol: ⊻
Gatter-Symbol:
IC: 7486 (beinhaltet vier XOR-Gatter mit je zwei Eingängen)
Verwendung in Programmiersprachen:
Basic: XOR
C, Java, Python, etc.: ^ (es gibt kein explizites XOR für logische Verknüpfungen)
NAND, wie AND, nur mit negiertem Ergebnis
Die Nicht-Und-Verknüpfung funktioniert erst einmal genauso wie ein AND, nur wird das Ergebnis dann am Schluss umgedreht, es ist sozusagen ein UND, dem ein NOT folgt. Die NAND-Verknüpfung gibt es vor Allem aus technischen Gründen: Mit diesen Gattern lässt sich jede mögliche Verknüpfung darstellen. Mit ein paar NANDs mehr oder weniger kann man also auf AND, OR, XOR und NOT-Gatter verzichten. Man muss also nur NAND-Gatter produzieren, um jede mögliche logische Schaltung bauen zu können. Und die Produktion von NAND-Gattern ist aufgrund technischer Gegebenheiten besonders günstig.Leitsatz: Falsch, wenn A UND B wahr sind.
Wahrheitstabelle NAND | ||
---|---|---|
Eingang A | Eingang B | Ausgang |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Logik-Symbol: ⊼
Gatter-Symbol:
(wie für AND, der Kringel vor dem Ausgang zeigt an, dass das Ergebnis negiert wird.)
IC: 7400 (beinhaltet vier NAND-Gatter mit je zwei Eingängen)
Verwendung in Programmiersprachen:
Basic: NOT (A AND B)
C, Java, Python, etc.: ~ (A & B)
NOR, wie OR, nur mit negiertem Ergebnis
Die Nicht-Oder-Verknüpfung funktioniert erst einmal genauso wie ein OR, nur wird das Ergebnis dann am Schluss umgedreht, es ist sozusagen ein OR, dem ein NOT folgt. Oder anders gesagt: Nur wenn alle Eingänge 0 sind, ist der Ausgang 1. Für NOR-Gatter gilt das gleiche wie für NAND-Gatter: auch mit einer Kombination dieser lässt sich jede mögliche Verknüpfung darstellen.Leitsatz: Falsch, wenn A ODER B wahr sind.
Wahrheitstabelle NAND | ||
---|---|---|
Eingang A | Eingang B | Ausgang |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
Logik-Symbol: ⊽
Gatter-Symbol:
(wie für OR, der Kringel vor dem Ausgang zeigt an, dass das Ergebnis negiert wird.)
IC: 7402 (beinhaltet vier NOR-Gatter mit je zwei Eingängen)
Verwendung in Programmiersprachen:
Basic: NOT (A OR B)
C, Java, Python, etc.: ~ (A | B)
Benutzung von logischen Gattern in digitalen Schaltungen
Wenn man in digitalen Schaltungen höhere Chips miteinander verbinden will, etwa eine CPU mit einem Interface-Chip, dann stellt man häufiger vor dem Problem, dass der Chip-Enable-Eingang (CE) des einen (peripheren) Chips auf spezielle Bitkombinationen aus anderen Chips (der CPU) reagieren soll, um etwa nur auf bestimmte Adressen zu reagieren.Beispiel: gegeben sei eine CPU mit 16 Adressleitungen (zur Ansprache von 65536 Einzeladressen), bei dem die unteren 32 KiB für RAM reserviert ist. Die obersten 8 KiB des Adressbereiches von 57.243 bis 65.535 sollen nur für ein Peripherie-Gerät benutzt werden. Die Chip-Enable-Leitung soll also immer dann auf High gesetzt werden (damit der Peripherie-Chip diese Daten weiterverarbeitet), wenn die Adressleitungen A15, A14 und A13 auf high (bzw. 1) sind. Ansonsten bleibt CE low und der Chip ignoriert die Daten.
Immer wenn die CPU eine Adresse über 57.242 adressiert (die obersten 8 KiB, binär 1110 0000 0000 0000 bis 1111 1111 1111 1111), dann sind die obersten drei Bits auf 1. Wollte man nur die obersten 4 KiB (binär 1111 0000 0000 0000 bis 1111 1111 1111 1111) ansprechen (also ab Adresse 61.439), dann würde man die obersten vier Bit prüfen müssen. Wir wollen aber jetzt bei 8 KiB bleiben.
Daraus ergibt sich die Aussage: Der Ausgang soll 1 (zur Einspeisung für CE=high) sein, wenn A13, A14 UND A15 high (bzw. 1) sind.
CE = A ⋀ B ⋀ C
Am einfachsten kann man das Problem natürlich mit einem AND-Gatter mit 3 Eingängen, wie dem 7411 (drei AND-Gatter mit je drei Eingängen) lösen, an die man A13, A14 und A15 an die Eingänge klemmt und den Ausgang an CE. Dann wir CE immer high, wenn von A13 bis A15 alles auf high ist. Braucht CE ein low, benutzen wir stattdessen einfach den 7410 (drei NAND-Gatter mit je drei Eingängen).A B C | CE |
Jetzt kann man sich natürlich ein Riesen-Sortiment an 74er-ICs mit allen möglichen logischen Gattern anschaffen und pflegen. Dann hätten man immer den direkten Weg. Oder man nimmt, was man hat und kombiniert so, dass das Ergebnis logisch das Gleiche ist.
Hat man z. B. nur AND-ICs 7408 mit jeweils 2 Eingängen und einem Ausgang. Dann könnte man die Logik mit 2 Unterabfragen (also Gattern) so implementieren:
CE = (A ⋀ B) ⋀ C
ist A oder B gleich 0, dann wird der Klammerausdruck 0 und damit der ganze Ausdruck.
ist C gleich 0, wird das Ergebnis ebenfalls 0.
Nur wenn A und B gleich 1 sind, wird der Klammerausdruck 1 und zusammen mit der 1 von C wird das Ergebnis 1.
Da ein 7408 vier AND-Gatter hat und wir nur zwei davon brauchen, brauchen wir mit dem 7408 (AND mit 4 mal 2 Eingängen) wie auch mit dem 7411 (AND mit 3 mal 3 Eingängen) je ein IC und haben in beiden Fällen noch 2 Gatter frei. Wenn man also keine hochkomplexen Logiken hat, spart man nicht unbedingt, wenn man viele spezielle Gatter vorrätig hält.
Abbildung von anderen Gattern mit NAND-Gattern
Ich hatte ja erwähnt, dass es möglich ist, mit NAND-Gattern (7400) jede mögliche Logik abzubilden. Versuchen wir uns mal an obigem Beispiel.CE = (A ⋀ B) ⋀ C
X = ((a ⊼ b) ⊼ c) ⊼ c
CE = ¬X
CE = X ⊼ X
Wahrheitstabelle X
a b c X
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
Alles nur eine Frage der Logik. In Gattern sieht das so aus:Damit sind die vier NAND-Gatter eines 7400 verbraucht. Insgesamt bleibt es aber bei einem einzigen Chip. Das heißt im Grunde, dass wir nur 7400er auf unsere Einkaufsliste setzen müssen und damit alles abbilden können, wenn wir ein wenig unsere Hirnwindungen bemühen.
Im Internet habe ich den sehr schön übersichtlichen Logikrechner von Jörn-Henning Daug gefunden, der einen bei der Rechnerei unterstützt, eine Wahrheitstabelle für eine Aussage ausgibt und mit dem man so überprüfen kann, ob die eigene Wandlungsformel in NAND-Gatter korrekt ist, wie ich es z. B. für die obige Gleichung gemacht habe.
Das auf der rechter Seite alles Einsen stehen, heißt, das die Terme und links und rechts des Doppelpfeils äquivalent, also gleichbedeutend sind. Das Ergebnis der Wahrheitstabelle stimmt in allen Fällen überein.
Sehr aussagekräftig ist auch der Ausdrucksbaum, den man mit dem Tool rauslassen kann. Hier zeigt uns die linke Hälfte im Prinzip an, wie wir unseren 7400 zu verkabeln haben, nämlich so:
Umsetzung von Standard-Gattern in NAND-Gatter
NOT-Gatter
Äquivalenzformel: ¬ A = A ⊼ AHardware-Einsatz: 1 NAND-Gatter
Wahrheitstabelle
a ¬a a⋀a
0 1 1
1 0 0
Gatter-Schema:AND-Gatter
Äquivalenzformel: A ⋀ B = ¬ (A ⊼ B) = (A ⊼ B) ⊼ (A ⊼ B)Hardware-Einsatz: 2 NAND-Gatter
Wahrheitstabelle
a b a⋀b ¬(a⊼b)
0 0 0 0
0 1 0 0
1 0 0 0
1 1 1 1
Gatter-Schema:OR-Gatter
Äquivalenzformel: A ⋁ B = (¬ A) ⊼ (¬ B) = (A ⊼ A) ⊼ (B ⊼ B)Hardware-Einsatz: 3 NAND-Gatter
Wahrheitstabelle
a b a⋁b (¬a)⊼(¬b)
0 0 0 0
0 1 1 1
1 0 1 1
1 1 1 1
Gatter-Schema:XOR-Gatter
Äquivalenzformel: A ⊻ B = ((a ⊼ b) ⊼ a) ⊼ ((a ⊼ b) ⊼ b)Hardware-Einsatz: 4 NAND-Gatter
Wahrheitstabelle
a b a⊻b ((a⊼b)⊼a)⊼((a⊼b)⊼b)
0 0 0 0
0 1 1 1
1 0 1 1
1 1 0 0
Gatter-Schema:Simulation von logischen Schaltungen
Wer sich nicht auf den Logik-Rechner und Wahrheitstabellen verlassen möchte, bevor er eine Schaltung in Hardware umsetzt, dem möchte ich die kostenlose Logiksimulator-Software LogiSim von Dr. Carl Burch empfehlen, mit der man logische Schaltungen zeichnen und testen kann.Ich habe z. B. einmal drei Arten von Umsetzungen eines XOR-Gatters damit entworfen:
A und B stellen die Eingänge dar, sie sind als binär definiert. Man kann auf sie drauf klicken und so den Zustand zwischen HIGH und LOW umschalten. Q ist der Ausgang und zeigt das Ergebnis an (entweder 1 oder 0).
Je nach Zustand von A und B ändert sich der Ausgang und die Farben der Linien. Hellgrün meint dabei: dieser Abschnitt ist HIGH und dunkelgrün meint: dieser Abschnitt ist LOW. So kann man sehr schön erkennen, was sich in der Schaltung tut, wenn man die Eingänge verändert.
Natürlich kann man auch wesentlich komplexere Schaltungen mit Logisim designen. Es gibt Bibliotheken für unzählige Gatter und Bausteine.
Die Dokumentation von Logisim ist sehr gut und auch in deutsch sehr gut verständlich. Nach kurzem Einlesen gelingt das Arbeiten mit Logsim recht intuitiv.
Logische Schaltungen helfen zum Beispiel bei der Auswahl der richtigen Adressleitungen bei einem Projekt wie meinem Breadboard-Computer.
Quellen, Literaturverweise und weiterführende Links
D. Steinbach: IC Daten Buch, Hofacker Verlag 1978Online-Logikrechner von Jörn-Henning Daug
Logiksimulator-Software LogiSim von Dr. Carl Burch