Logikgatter

Grundidee und Funktion

Ein Logikgatter, auch Gatter genannt, ist eine Anordnung zur Realisierung einer booleschen Funktion. Es verarbeitet binäre Eingangssignale und bildet daraus ein binäres Ausgangssignal. Heutzutage handelt es sich praktisch immer um eine elektronische Schaltung.

Die Eingänge werden durch logische Operatoren verknüpft: Die Konjunktion entspricht dem Und-Gatter (AND), die Disjunktion dem Oder-Gatter (OR), die Kontravalenz dem Exklusiv-Oder-Gatter (XOR) und die Negation dem Nicht-Gatter (NOT). Gatter mit negiertem Ausgang sind NAND (Nicht-Und), NOR (Nicht-Oder) und XNOR (Nicht-Exklusiv-Oder). Deutsche Bezeichnungen für NAND, NOR und XNOR sind unüblich.

Grundsätzlich lassen sich alle logischen Verknüpfungen als Gatter verwirklichen. Mehrere Gatter können zu einem Flipflop, Latch oder Multiplexer zusammengeschaltet werden. Aus Flipflops entstehen unter anderem Datenspeicher und Zähler; aus solchen Schaltungen können Mikroprozessoren entwickelt werden. Die Schaltalgebra dient dazu, komplexe logische Funktionen zu implementieren und zu vereinfachen. Die Anzahl der Gatteräquivalente ist ein Maß für die logische Komplexität einer Schaltung.

Technische Umsetzung und universelle Gatter

Moderne Logikgatter bestehen mit wenigen Ausnahmen aus Transistoren. Ein Signal wird durch zwei Spannungsbereiche dargestellt, die als 0 und 1 oder als low und high beziehungsweise L und H bezeichnet werden. Die Spannungsgrenzen sind so festgelegt, dass Transistoren trotz Produktionstoleranzen sicher leitend oder sicher sperrend schalten. Das Ausgangssignal eines Gatters kann direkt mit Eingängen weiterer Gatter verbunden werden; dadurch entstehen komplexe digitale Schaltungen.

Elektronische Gatter werden unter anderem als TTL-, CMOS- und BiCMOS-Bausteine in integrierten Schaltkreisen angeboten. TTL basiert auf Bipolartransistoren, CMOS auf Feldeffekttransistoren, genauer MOSFETs, und BiCMOS verbindet beide Transistorfamilien. Logikgatter bilden den Kern von Mikroprozessoren und können in FPGA- oder PLD-ICs in großer Zahl per Software programmiert werden. Gatter lassen sich außerdem aus diskreten Bauelementen, Schaltern oder Relais aufbauen. Historisch gab es auch mechanische Aufbauten; sogar fluidische Bauelemente sind möglich.

NAND- und NOR-Gatter sind besonders wichtig. Nach Quine/McCluskey lassen sich alle binären Funktionen auf AND, OR und NOT zurückführen. OR und NOT können mit NAND-Gattern dargestellt werden; AND und NOT können mit NOR-Gattern dargestellt werden. Deshalb kann jede logische Schaltung allein mit NAND- oder allein mit NOR-Bausteinen verwirklicht werden, sofern Gatter-Durchlaufzeiten und Signalflankenzeiten berücksichtigt werden.

Ein Beispiel ist der Chip SN7400N. Er enthält vier NAND-Gatter mit jeweils zwei Eingängen. Das Präfix SN weist auf Texas Instruments als Hersteller hin. Das Suffix N bezeichnet ein Kunststoff-DIP-Gehäuse. Der Datumscode 7645 bedeutet, dass der Chip in der 45. Kalenderwoche des Jahres 1976 gefertigt wurde.

Wahrheitstabellen als Beschreibungsmittel

Eine Wahrheitstabelle stellt die möglichen Ausgangszustände eines Gatters in Abhängigkeit von den Eingangszuständen dar. Sie enthält alle möglichen Kombinationen der Eingangssignale und das jeweils zugehörige Ausgangssignal. Aus einer Wahrheitstabelle lassen sich logische Formeln vergleichsweise einfach ablesen.

Für die disjunktive Normalform werden die Zeilen mit dem Ausgangswert 1 betrachtet: Die einzelnen Zeilen werden logisch oder verknüpft, die Eingänge innerhalb jeder Zeile logisch und. Bei der konjunktiven Normalform mit dem Ergebnis 0 ist es umgekehrt. Zur weiteren Verkürzung einer solchen Formel kann ein KV-Diagramm verwendet werden.

Vereinfachung mit dem KV-Diagramm

Das Karnaugh-Veitch-Diagramm, kurz KV-Diagramm, ist ein Verfahren, um aus der disjunktiven oder konjunktiven Normalform eine möglichst kompakte logische Formel zu bilden.

Dazu werden Nullen oder Einsen sinnvoll zusammengefasst. Zusätzlich können redundante Felder, also „leere“ Felder ohne Einfluss auf die Funktion, günstig interpretiert werden. Das Ergebnis ist eine vereinfachte Kompaktform der logischen Funktion.

Gattertypen, Formeln und Ausgangswerte

Logikgatter werden in Schaltplänen durch Symbole dargestellt. Dafür existieren mehrere Standards, darunter IEC 60617-12 : 1997, ANSI/IEEE Std 91/91a-1991 und DIN 40700 (vor 1996). Die wichtigsten Gattertypen sind:

• AND (Und-Gatter): „a und b“. Die Funktion lautet Y = A ∧ B beziehungsweise Y = A · B. Für die Eingangsreihenfolge 00, 01, 10, 11 lauten die Ausgänge 0, 0, 0, 1.

• OR (Oder-Gatter): „a oder b“. Die Funktion lautet Y = A ∨ B beziehungsweise Y = A + B. Die Ausgänge lauten 0, 1, 1, 1.

• NOT (Nicht-Gatter): „nicht a“. Die Funktion lautet Y = ¬A, auch Y = Ā oder Y = Ã. Bei den Eingängen 0 und 1 lauten die Ausgänge 1 und 0.

• NAND (Nicht-Und): „a nand b“. Die Funktion lautet Y = ¬(A ∧ B) beziehungsweise Y = \overline{AB}. Die Ausgänge lauten 1, 1, 1, 0.

• NOR (Nicht-Oder): „a nor b“. Die Funktion lautet Y = ¬(A ∨ B) beziehungsweise Y = \overline{A+B}. Die Ausgänge lauten 1, 0, 0, 0.

• XOR (Exklusiv-ODER, Antivalenz): „a xor b“. Die Funktion lautet Y = A ⊕ B. Der Ausgang ist genau dann 1, wenn die beiden Eingänge verschieden sind; die Ausgänge lauten 0, 1, 1, 0.

• XNOR (Exklusiv-Nicht-ODER, Äquivalenz): „a Doppelpfeil b“. Die Funktion lautet Y = ¬(A ⊕ B) beziehungsweise Y = A ⊙ B. Der Ausgang ist 1, wenn die Eingänge gleich sind; die Ausgänge lauten 1, 0, 0, 1.

In einer Übersicht werden außerdem AOI- und OAI-Gatter genannt. Früher waren auf dem europäischen Kontinent die deutschen Symbole der DIN 40700 verbreitet. Im englischen Sprachraum waren und sind die amerikanischen Symbole üblich. Die IEC-Symbole fanden international nur begrenzte Akzeptanz und werden in der amerikanischen Literatur fast durchgängig ignoriert.

Historische Entwicklung

Der Geschichtsabschnitt ist laut Artikel nicht hinreichend mit Belegen ausgestattet; einzelne Angaben könnten daher entfernt werden.

Gottfried Wilhelm Leibniz beschrieb das Binärsystem mathematisch exakt in einer Veröffentlichung von 1705 und erläuterte, wie sich damit Arithmetik und Logik verbinden lassen. Die ersten Logikgatter waren mechanisch. Charles Babbage entwarf 1837 mit der Analytical Engine eine Rechenmaschine, deren logische Gatter auf mechanischen Reaktionen beruhten. Später wurden elektromagnetische Relais eingesetzt.

Almon Strowger meldete 1891 eine „Einheit, die einen Logikgatter-Schalterstromkreis enthält“ zum Patent an. Nikola Tesla begann 1898 mit der Archivierung und Verfeinerung solcher Einheiten. Lee De Forest veränderte 1907 eine Elektronenröhre so, dass sie als Und-Gatter verwendet werden konnte.

Ludwig Wittgenstein führte 1921 in Theorem 5.101 des Tractatus Logico-Philosophicus die erste Wahrheitstabelle ein, ohne sie so zu nennen. Walther Bothe entwickelte 1924 ein modernes elektronisches Und-Gatter. Konrad Zuse entwarf und baute von 1935 bis 1938 elektromechanische Gatter für den Computer Z1. Claude Elwood Shannon begründete 1937 die Anwendung der Booleschen Algebra auf Stromkreise. Helmut Schreyer baute 1942 versuchsweise eine elektronische Rechenanlage mit 100 Röhren und 1944 einen elektronischen Übersetzer von Dezimal- in Binärzahlen.

Das erste integrierte Logikgatter wird Jack Kilby und dem Jahr 1958 zugeschrieben; es umfasste etwa zehn Bauteile. Zehn Jahre später fertigte Texas Instruments TTL-Schaltkreise der Serie 74xx in Großserie, die schnell zur Grundlage der Industrieautomation wurden. Gegenwärtige Forschungsprojekte befassen sich mit molekularen Logikgattern.