Was sind Carry-Lookahead-Addierer und Ripple-Carry-Addierer?

Ein System von Ripple-Carry-Addierern ist eine Folge von Standard-Volladdierern, die es ermöglichen, Zahlen zu addieren, die mehr Bits enthalten als die eines einzelnen Volladdierers. Jeder Volladdierer hat ein Übertragsbit (Cin) und ein Übertragsbit (Cout), und die Addierer sind verbunden, indem Cout in Schritt k mit Cin in Schritt k+1 verbunden wird (Cin in Schritt 0 ist C0 im Bild, Cout in Schritt 3 ist C4 auf dem Bild)

Die Herausforderung bei Ripple-Carry-Addierern ist die Ausbreitungsverzögerung der Carry-Bits. Nehmen Sie an, dass sich in einem Augenblick die Werte von A und B ändern, so dass

A1 = 0
B1 = 1
A0 = 1
B0 = 1

Da A0 und B0 hoch sind, erzeugt der erste Volladdierer einen Übertrag, dh C1 = 1. Es dauert jedoch einige Zeit, bis sich die Logik beruhigt hat, sodass sich C1 nicht ändert, bis sich A1 und B1 geändert haben. Bevor C1 auftaucht, erzeugt der zweite Volladdierer also keinen Übertrag, aber wenn C1 auftaucht, berechnet der zweite Addierer neu und erzeugt einen Übertrag, dh C2 = 1. Im schlimmsten Fall wird C4 bis 4 nicht korrekt berechnet *Fortpflanzungsverzögerung, und Cn wird nicht bis n*Fortpflanzungsverzögerung berechnet.

Ein Carry-Lookahead-Addierersystem löst dieses Problem, indem es berechnet, ob ein Übertrag erzeugt wird, bevor es die Summe tatsächlich berechnet. Es gibt mehrere Schemata, um dies zu tun, also gibt es nicht "eine" Schaltung, die einen Look-Ahead-Addierer darstellt. Die Idee ist ungefähr so:

Die Berechnung von C4 ist nicht schneller als im Ripple-Carry oben, ebenso wenig wie PG und GG - die Magie geschieht nur, wenn Sie mehrere dieser Blöcke zusammenfügen, um noch größere Zahlen zu addieren.

Der wichtige Teil des Bildes ist, dass der violette Block drei Werte erzeugt: C4, PG (Propagate) und GG (Generate). PG geht hoch, wenn dieser Block Cin zu Cout weiterleitet, und GG geht hoch, wenn der Block unabhängig von Cin einen Überlauf erzeugt. (Außerdem darf der Block weder einen Übertrag ausbreiten noch erzeugen, in diesem Fall sind sowohl PG als auch GG niedrig und Cout ist 0.) PG und GG können im violetten Block unabhängig vom Wert von C0 berechnet werden - also wenn C0 schließlich ankommt, kann der violette Block einfach sein zuvor berechnetes Ergebnis konsultieren, und wenn das Ergebnis ein "Propagieren" ist, dann wird C0 direkt an C4 weitergegeben; dies ist viermal schneller als die Ausbreitung durch alle vier Volladdierer.

Der Grund, warum der Block die Ausgänge PG und GG hat, ist, damit wir auf hierarchische Weise noch größere Ausbreitungsbeschleunigungen erzielen können.

Siehe auch: http://faculty.kfupm.edu.sa/COE/abouh/Lesson3_3.pdf