T12-Arithmetische-Schaltungen-und-ALU

Arithmetische Schaltungen & ALU

Zusammenfassung

Arithmetische Schaltungen realisieren Addition und Subtraktion von Binär- und Zweierkomplementzahlen. Der Halbaddierer (HA) addiert zwei Bits ohne Übertrag, der Volladdierer (FA) addiert drei Bits (mit Eingangsübertrag). Der Carry-Ripple-Addierer (CR_n) verkettet Volladdierer (Kosten , Tiefe ). Der Conditional-Sum-Addierer (CSA) erreicht logarithmische Tiefe durch parallele Berechnung mit Multiplexern. Die ReTI ALU kombiniert Addierer/Subtrahierer und logische Operationen, gesteuert durch einen 3-Bit-Select-Eingang.

Exam-Relevanz

MEDIUM. Nicht direkt als Klausuraufgabe gefragt, aber unterstützt das Verständnis von A2 (ReTI ALU, Maschinencode). Die Kosten-/Tiefeformeln für HA, FA, CR_n und MUX sind wichtig für Schaltkreisanalyse.

Halbaddierer (HA)

Addiert zwei 1-Bit-Zahlen ohne Eingangsübertrag.

mit .

(carry) (sum)
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

Formeln:

Kosten und Tiefe:

Volladdierer (FA)

Addiert zwei 1-Bit-Zahlen mit Eingangsübertrag .

mit .
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1

Formeln:

Alternative Darstellung als Verkettung von zwei HAs:

Kosten und Tiefe:

Carry-Ripple-Addierer (CR_n)

Verkettet Volladdierer nach der Schulmethode: Der Übertrag jeder Stelle ripppelt zur nächsten.

Induktive Definition:

  • :
  • : besteht aus für die höherwertigen Stellen und einem FA für die niederwertigste Stelle

Komplexität

In der Vorlesung wird vereinfacht angegeben, wenn man nur den Carry-Pfad betrachtet. Die exakte Formel mit ergibt .

Sowohl Kosten als auch Tiefe sind linear in .

Inkrementer (INC_n)

Ein Inkrementer ist ein Addierer mit für alle — es wird nur addiert. Ersetze in die FAs durch HAs:

Subtrahierer

Wegen der Zweierkomplement-Regel kann Subtraktion auf Addition zurückgeführt werden:

Kombinierter Addierer/Subtrahierer

Ein Steuersignal sub wählt zwischen Addition und Subtraktion:

  • (Addition: sub = 0)
  • (Subtraktion: sub = 1)

Das sub-Signal wird gleichzeitig als Eingangsübertrag gesetzt.

Zweierkomplement-Überlauf

Ein Überlauf tritt auf, wenn das Ergebnis nicht im Darstellungsbereich liegt:

Äquivalent:

Beispiel: , 

  0 0 1 1   (= 3)
+ 0 1 0 1   (= 5)
----------
  1 0 0 1   (Überlauf! 8 ∉ R_3)

MUX (Multiplexer)

Ein -Bit-Multiplexer wählt zwischen zwei -Bit-Eingängen aus:

Pro Bit gilt:

Kosten und Tiefe:

CSA (Carry-Save-Addierer / Conditional-Sum-Addierer)

Idee

Nutze Parallelverarbeitung, um die Tiefe von linear auf logarithmisch zu reduzieren. Teile die -Bit-Addition in obere und untere Hälfte, berechne beide Hälften rekursiv und wähle das richtige Ergebnis der oberen Hälfte per MUX basierend auf dem Übertrag der unteren Hälfte.

Rekursive Definition (für )

  • : Zwei für obere und untere Hälfte, ein wählt das Ergebnis der oberen Hälfte

Tiefe

Beweis (Induktion über ):

  • : ✓
  • :

Kosten

Genauer: .

Vergleich mit Carry-Lookahead-Addierer (CLA)

Der CLA erreicht lineare Kosten und logarithmische Tiefe:

Untere Schranken

Für die Addition gelten:

Begründung:

  • Ein binärer Baum mit Blättern hat innere Knoten → mindestens Gatter
  • Ein binärer Baum mit Blättern hat mindestens Tiefe

Der CR_n ist optimal in den Kosten ( vs. untere Schranke ), aber nicht in der Tiefe. Der CSA erreicht die Tiefe-Schranke bis auf einen konstanten Faktor.

ReTI ALU

Die ALU (Arithmetic Logic Unit) berechnet arithmetische und logische Operationen für ReTI.

Spezifikation

  • Zwei 32-Bit-Operanden , , Eingangscarry
  • 3-Bit-Select-Eingang (8 Funktionen)
  • 32-Bit-Ausgang
  • Insgesamt 68 Eingänge, 32 Ausgänge

Select-Tabelle

ALU-Funktion
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Compute-Befehle von ReTI

MI Befehl Wirkung
0 0 1 0 SUBI i
0 0 1 1 ADDI i
0 1 0 0 OPLUSI i
0 1 0 1 ORI i
0 1 1 0 ANDI i
1 0 1 0 SUB i
1 0 1 1 ADD i
1 1 0 0 OPLUS i
1 1 0 1 OR i
1 1 1 0 AND i

Realisierungsoptionen

Option 1: Separate Schaltkreise für jede Funktion, Auswahl durch verallgemeinerten Multiplexer. Einfach, aber teurer.

Option 2: Gemeinsame Behandlung ähnlicher Funktionen. AND und EXOR berechnen logische Operationen gemeinsam, ein MUX (gesteuert durch ) wählt das logische Ergebnis. Der Addierer/Subtrahierer wird über aktiviert. Komplexer, aber effizienter (geringere Kosten und Tiefe).

Sign Extension

Für Additionen verschieden langer Zahlen (z.B. mit ):

ü

Es gilt — das Vorzeichenbit wird auf 32 Bit erweitert.

Übungsblätter

Blatt Aufgabe Thema Punkte
Blatt08 5a : ON-Menge, Quine-McCluskey, Minimalpolynom 2
Blatt08 5b Minimalpolynom für allgemeines 1
Blatt08 5c–e XOR-Schaltkreis mit geringer Tiefe (Baumstruktur) 5
Blatt08 6 6-Bit Zweierkomplement-Addition, Überlauferkennung 3
Blatt09 2a Addierer/Subtrahierer mit sub-Signal 2
Blatt09 2b Überlaufsignal overflow 2
Blatt09 3a CSA-INC: schneller Inkrementer auf CSA-Basis 3
Blatt09 3b Tiefe und Kosten von CSA-INC 3 (Bonus)

Quellen

Priorität

MEDIUM. Unterstützt A2 (ReTI Maschinencode). Beherrsche:

  1. HA und FA: Wahrheitstabelle, Formeln, Kosten, Tiefe
  2. ,
  3. Subtraktion via XOR + carry-in = 1
  4. Überlauferkennung:
  5. CSA: , rekursiver Aufbau mit MUX
  6. ALU-Select-Tabelle und Compute-Befehle