Schaltnetze

Da Bits nur zwei Werte annehmen (Null oder Eins, Wahr oder Falsch, Strom an oder Strom aus), können Verknüpfungen von Bits mit Hilfe logischer Operationen realisiert werden. Auch Arithmetik ist durch Kombination logischer Operationen implementierbar, indem Zahlen im Binärsystem kodiert werden.

Logikgatter

Die Verknüfungstabellen der drei gängigsten logischen Operationen sind im Folgenden dargestellt:

Negation (not)

Logisches Und (and)

Logisches Oder (or)

Negation (not) berechnet das jeweils entgegengesetzte Bit zur Eingabe, Das Ergebnis der Konjunktion (and) ist genau dann gesetzt, wenn beide Eingaben gesetzt sind, und das Ergebnis der Disjunktion (or) ist genau dann nicht gesetzt, wenn keine der Eingaben gesetzt ist.

Jede logische Operation kann durch geeignete Kombination von not, and und or realisiert werden. Elektronische Bauteile, die solche Verknüpfungen implementieren, heißen Gatter oder Schaltnetze, wobei der Begriff Gatter vornehmlich für einfache Schaltnetze verwendet wird.

Die bisher gezeigten Operationen können alle mit Hilfe der sogenannten nand (für not and) Operation implementiert werden. Alle Schaltnetze eines Computers können also allein aus NAND-Gattern gebaut werden. Die Verknüpfungstabelle der nand-Operation ist wie folgt definiert.

Die Implementierung der anderen gezeigten Operation mit Hilfe eines NAND-Gatters beschreiben wir mit Hilfe einer beispielhaft eingeführten Hardware-Beschreibungssprache. Gatter haben Ein- und Ausgänge, die konzeptuell mit Leitungen verbunden werden können. Ein NAND-Gatter hat zwei Eingänge und einen Ausgang. Verbinden wir die Eingänge mit Leitungen a und b und den Ausgang mit einer Leitung out, schreiben wir dies als NAND(a, b; out). Hierbei sind in der Parameter-Liste Eingänge von Ausgängen durch ein Semikolon getrennt.

NOT(a; out):
  NAND(a, a; out)

Konjunktion können wir nun mit Hilfe eines NAND- und eines NOT-Gatters implementieren, denn a and b = not (a nand b):

AND(a, b; out):
  NAND(a, b; c)
  NOT(c; out)

Für die Disjunktion nutzen wir die Identität a or b = (not a) nand (not b):

OR(a, b; out):
  NOT(a; c)
  NOT(b; d)
  NAND(c, d; out)

Eine häufig verwendete Verknüpfung ist xor (für exclusive or), deren Ergebnis genau dann gesetzt ist, wenn die beiden Argumente unterschiedliche Werte haben:

Die xor-Verknüpfung kann wie folgt als Gatter realisiert werden:

XOR(a, b; out):
  NOT(a; c)
  NOT(b; d)
  AND(a, d; e)
  AND(c, b; f)
  OR(e, f; out)

Diese Implementierung verwendet (indirekt) neun NAND- Gatter. Eine alternative Implementierung mit nur vier NAND- Gattern sieht wie folgt aus:

XOR(a, b; out):
  NAND(a, b; c)
  NAND(a, c; d)
  NAND(c, b; e)
  NAND(d, e; out)

Aus logischer Sicht ist nur das Ein-Ausgabe-Verhalten eines Gatters interessant. Allerdings beeinflusst die Anzahl der verwendeten Bauteile die Effizienz, da höhere Signallaufzeiten langsamere Berechnungen zur Folge haben.

Multiplexer

Weitere, für die Architektur von Digitalrechnern wichtige, Schaltnetze sind sogenannte Multiplexer, die es über einen Steuerungskanal ermöglichen zwischen verschiedenen Eingängen auszuwählen. Ein 2-zu-1 Multiplexer, wählt zum Beispiel zwischen zwei Eingangs-Bits mit Hilfe eines Steuerungs-Bits aus (setzt also je nach Wert des Steuerungs-Bits den einen oder den anderen Eingang auf den Ausgang).

Die Wahrheitstabelle eines 2-zu-1-Multiplexer mit den Eingangsbits a und b und dem Steuerungsbit x sieht folgendermaßen aus:

Wenn das Steuerungsbit x auf 0 gesetzt worden ist, wird das Eingangsbit a zum Ausgang weitergeleitet, sonst das Bit b.

Multiplexer können zu größeren Multiplexern zusammengeschaltet werden. Zum Beispiel kann ein 4-zu-1-Multiplexer wie folgt aus drei 2-zu-1-Multiplexern zusammengebaut werden.

4MUX1(x, y, a, b, c, d; out):
  2MUX1(y, a, b; e)
  2MUX1(y, c, d; f)
  2MUX1(x, e, f; out)

Hierbei wird je nach Wert der Steuerungs-Bits x und y einer der Eingänge a bis d auf den Ausgang out geleitet. Die Implementierung des Gatters 2MUX1 ist eine Übungsaufgabe.

In Computern werden Bits in der Regel gebündelt verarbeitet. Bündelungen aus mehreren Bits heißen Bus und sind in der Regel 8, 16, 32, usw. Bits breit, um sie per Multiplexer effizient steuern zu können. Digitale Multiplexer können \(2^n\) Eingänge verarbeiten, wenn \(n\) die Anzahl der Steuerungsbits ist.

Arithmetikgatter

Schaltnetze können nicht nur logische sondern auch arithmetische Operationen ausführen, indem Zahlen als Bitfolgen, also im Binärsystem, dargestellt werden. Die folgende Tabelle zeigt die Zahlen von eins bis zehn im Unär-, Dezimal- und im Binärsystem mit drei Stellen:

Addition mit Binärzahlen folgt dem gleichen Verfahren wie Addition von Zahlen in anderen Zahlensystemen: Zahlen werden stellenweise addiert, wobei Überträge zur nächsthöheren Stelle übernommen werden. Das folgende Beispiel illustriert die Addition der Zahlen zwei und drei im Binärsystem mit drei Stellen.

  010
+ 011
ü 1
-----
  101

Das Ergebnis ist die Binärdarstellung der Zahl fünf.

Zur Implementierung binärer Addition durch ein Schaltnetz implementieren wir zunächst ein Gatter HADD (für half adder), das aus zwei Eingangs-Bits das Ergebnis-Bit und das Übertrags- Bit berechnet:

HADD(a, b; sum, carry):
  XOR(a, b; sum)
  AND(a, b; carry)

Ein ADD-Gatter benötigt ein zusätzliches Eingabe-Bit für den Übertrag der nächst-niedrigeren Stelle. Die Definition des ADD-Gatters ist eine Übungsaufgabe. Zur Addition von Binärzahlen mit \(n\) Stellen können dann \(n\) ADD-Gatter hintereinander geschaltet werden.

Arithmetisch-logische Einheit (ALU)

Die arithmetisch-logische Einheit (ALU für Arithmetic-Logic Unit) ist das komplexeste Schaltnetz im Hauptprozessor eines Computers. Sie kombiniert Implementierungen verschiedener logischer und arithmetischer Operationen, die über Steuerungs-Bits (ähnlich wie bei einem Multiplexer) ausgewählt werden können. Verschiedene Prozessoren unterscheiden sich in Art und Anzahl durch die ALU implementierter Operationen. Hierbei werden Prozessoren mit wenigen effizienten Instruktionen (RISC für Reduced Instruction Set Computer) von solchen mit vielen maßgeschneiderten Instruktionen (MISC für Multiple Instruction Set Computer) unterschieden. Der Vorteil der RISC-Architektur ist, dass die Signalverzögerung durch die ALU geringer ist, weil diese weniger Instruktionen zur Verfügung stellen muss. Der Vorteil der MISC-Architektur ist, dass sie Instruktionen, die durch mehrere RISC-Instruktionen modelliert werden müssten, direkt in Hardware und damit effizienter implementiert.

Die Ein- und Ausgabe der ALU ist mit Registern und dem Hauptspeicher verbunden, die Steuerungs-Bits werden mit Hilfe eines speziellen Registers namens Programmzähler bestimmt. Speicher und Programmzähler werden im nächsten Abschnitt behandelt. Sie sind der Schlüssel dazu, komplexe Instruktionen auf Basis der primitiven, von der ALU bereitgestellten, Instruktionen zu implementieren und deshalb ein wichtiges Abstraktionskonzept zur Realisierung von Computern.