Carry-Select-Addierer

Carry-Select-Addierer

Der Carry-Select-Addierer (von englisch carry Übertrag, select (aus-)wählen]) oder kurz CSCA ist ein beschleunigtes Addiernetz, welches zur Addition mehrstelliger Binärzahlen verwendet wird.

Funktionsweise

Beispiel eines 9-Bit Carry-Select-Addierers

Der CSCA unterteilt die gesamte Wortbreite n in M Blöcke.

Im gegebenen Bildbeispiel sind die Blockbreiten 2, 3 und 4 Bit.
Es handelt sich also um eine Addition von zwei 2 + 3 + 4 = 9 Bit breiten Binärzahlen.

Das Prinzip dieses Addiernetzes lässt sich mit dem Begriff „parallelisierte Vorabberechnung“ beschreiben, denn jeder der Blöcke besteht aus jeweils zwei Carry-Ripple-Addierern (kurz CRA), die gleichzeitig die Berechnung für ihren Bit-Anteil der Binärzahlen ausführen. Dabei liegt an einem der CRA ein Übertragsbit an (c=1), während der Carry-Eingang des anderen auf c=0 gesetzt ist. Somit werden pro Block beide möglichen Fälle parallel ausgerechnet und an einen Multiplexer angelegt. Dieser schaltet schließlich in Abhängigkeit vom höchstwertigen Übertragungsbit des vorherigen Blocks auf die richtige Lösungsvariante, welche im Idealfall schon fertig berechnet ist.

Laufzeiten

Um eine optimale Laufzeit zu erhalten, ist es sinnvoll, die beliebig variable Blockwortbreite wachsen zu lassen, da so die Berechnung im Block synchron mit dem Anlegen des endgültigen Übertragungsbits abschließt.

Im folgenden Rechenbeispiel wird davon ausgegangen, dass dies genau dann der Fall ist, wenn der Wortbreitenzuwachs 1 Bit pro Block entspricht (siehe Beispiel).

  • eins Gesamtwortbreite = n
  • zwei Anzahl der Blöcke = K
  • drei variable Blockwortbreite = mk mit k = 0,1,...,K-1
  • vier Anfangsblockwortbreite = m0
  • fünf Wortbreitenzuwachs = σm [in Bit/Block]

n = \sum_{k=0}^{K-1}\,m_k = m_0 + (m_0+1) + (m_0+2) + ... + (m_0+K-1)
n = K \cdot m_0 + (1+2+...+K-1) = K \cdot m_0 + K\cdot\frac{K-1}{2}

0 = K^2 + K\cdot(2m_0-1)-2n

K = -\frac{2m_0-1}{2} \pm \sqrt{\frac{2m_0-1}{2}+2n}


Auf unser spezielles Beispiel (n = 9,m0 = 2,σm = 1) angewandt:

K = - \frac{3}{2} + \sqrt{ \frac{9}{4} + \frac{72}{4} } = 2 (0,1,2 - entspricht drei Blöcken)

Additionszeit:

\tau_{CSCA}(n) = \tau_{CRA}(m_0) + (K-1) \cdot \tau_{Block}

\tau_{CSCA}(n) = O(\sqrt{n})

mit

\tau_{CRA}(n) = \tau_{Halbaddierer} + (n-1) \cdot \tau_{Carry-Ripple} + \tau_{Halbaddierer}


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Carry-Ripple-Addierer — Aufbau eines 4 Bit Carry Ripple Addierers Der Carry Ripple Addierer (von engl. carry Übertrag, ripple rieseln), auch Ripple Carry Addierer oder ripple through carry, ist ein Addiernetz, dient also der Addition mehrstelliger Binärzahlen. Ein n Bit …   Deutsch Wikipedia

  • Ripple-Carry-Addierer — Aufbau eines 4 Bit Carry Ripple Addierers Der Carry Ripple Addierer (von engl. carry Übertrag, ripple rieseln), auch Ripple Carry Addierer oder ripple through carry, ist ein Addiernetz, dient also der Addition mehrstelliger Binärzahlen. Ein n Bit …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”