Ein Carry-Save-Addierer (CSA) besteht einfach aus n unabhängigen Volladdierern. Ein Multiplizierer mit solch einem Addierer heißt Carry-Save-Multiplizierer.
Um a mit b zu multiplizieren (a und b sind n-Bit-Zahlen), lade a und
b beide in die Register A und B.
Jede Addition erzeugt ein Bitpaar, abgespeichert im Summen- und Übertragsteil
von P.
Man lädt zunächst die Summenbits und das Übertragsbit
von P (Puffer-Register) mit Null und führt die erste ALU-Operation
durch. Dann wird das niedrigstwertige Summenbit von P in A geschoben. Die
n-1 höchstwertigen Bit von P brauchen nicht verschoben werden, weil
im nächsten Zyklus die Summenbits dem nächstniederen Addierer
zugeführt werden.
Vorteile:
1. Da jede Addition unabhängig ist, werden nur zwei Logikebenen
benötigt - ein enormer Fortschritt gegenüber 28 Logikebenen (64-Bit-Zahlen).
2. Jeder Additionsschritt ist sehr schnell, da jeder Addierer unabhängig
arbeitet und sich kein Übertrag fortpflanzt.
Nachteile:
1. Zusätzliche Hardware wird benötigt, weil eine Kopie des
Registers P die Überträge der Addierer speichern muß.
2. Das höchstwertige Wort des Resultats muß nach dem letzten
Schritt einem einfachen Addierer zugeführt werden., um es mit dem
Summen- und Übertragsteil zu kombinieren.
SRT-Division Algorithmus
SRT-Division Algorithmus ist ein schneller Divisionsalgorithmus und heißt nach Sweeney, Robertson und Tocher, die ihn unabhängig vonenander vorschlugen.
Algorithmus:
Um a durch b zu dividieren (a und b sind n-Bit-Zahlen), lade a und b beide in die Register A und B.
1. Hat B k führende Nullen bei insgesamt n Bit, verschiebe alle Register k Bit nach links. Wenn b nach dieser Verschiebung n+1 Bit hat, ist anschließend das höchstwertige Bit 0 und das Bit danach 1.
2. Für i=0 bis n-1
Sind die führenden drei Bit
von P gleich, setze qi=0, und schiebe (P,A) ein Bit nach links.
Sind die führenden drei Bit
von P nicht gleich, und ist P negativ, setze qi=-1, schiebe
(P,A) ein Bit nach links, und addiere B.
Ansonsten setze qi=1,
schiebe (P,A) ein Bit nach links, und subtrahiere B.
Ende der Schleife.
3. Ist der Schlußrest negativ, korrigiere ihn durch Addition von B und den Quotienten durch Subraktion von 1 von q. Schließlich muß der Rest k Bit nach rechts verschoben werden, wobei k die Anfangsverschiebung ist.
Anmerkung:
Bei der SRT-Division benutzt man redundante Quotientendarstellung, d.h. die Quotientenzahl in Termen der Ziffer -1,0,1 dargestellt ist. Daher kann das Quotientenbit nicht in den niedrigstwertigen Bits des Register A gespeichert werden; vielmehr muß es in einem Addierer in das normale Zweierkomplement umgewandelt werden. Ein üblicher Weg ist es, die positiven und die negativen Quotientenbits jeweils in einem Register zu akkumulieren und am Ende die beiden Registerinhalte zu subtrahieren.
Die Unterschiede von SRT- und normaler Division können wie folgt zusammengefaßt werden:
1. ALU-Entscheidungsregel: bei der nichtrückspeichernden
Division festgelegt durch Vorzeichen von P; bei SRT durch die beiden MSB
von P.
2. Quotientenbestimmung: bei der nichtrückspeichernden
Division unmittelbar aus dem Vorzeichen von P; bei SRT-Berechnung in einem
n-Bit-Volladdierer.
3. Geschwindigkeit: SRT-Division ist schneller bei Operanden,
die Nullen als Quotientenbits erzeugen.