imported>Aka: /* Laufzeiten */ Halbgeviertstrich

2018-11-21T13:45:45Z

Laufzeiten: Halbgeviertstrich

Neue Seite

{{Belege fehlen}}
Der '''Carry-Select-Addierer''' (von {{enS|carry}} Übertrag, {{lang|en|''select''}} (aus-)wählen) oder kurz CSCA ist ein beschleunigtes [[Addierwerk|Addiernetz]], welches zur Addition mehrstelliger [[Binärzahl]]en verwendet wird.

== Funktionsweise ==
[[Datei:Carry-Select-Addierer.png|mini|Beispiel eines 9-Bit Carry-Select-Addierers]]

Der CSCA unterteilt die gesamte ''[[Datenwort|Wortbreite]] n'' in ''M Blöcke''.

Im gegebenen Bildbeispiel sind die Blockbreiten 2, 3 und 4 [[Bit]].<br />
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-Addierer]]n (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 (Informatik)|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).

* Gesamtwortbreite = n
* Anzahl der Blöcke = K
* Variable Blockwortbreite = <math>m_k</math> mit k = 0,1,...,K-1
* Anfangsblockwortbreite = <math>m_0</math>
* Wortbreitenzuwachs = <math>\sigma_m</math> [in Bit/Block]

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

<math>0 = K^2 + K\cdot(2m_0-1)-2n</math>

<math>K = -\frac{2m_0-1}{2} \pm \sqrt{\left(\frac{2m_0-1}{2}\right)^2 +2n}</math>

Auf unser spezielles Beispiel (<math>n=9, m_0=2, \sigma_m=1</math>) angewandt:

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

Additionszeit:

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

<math>\tau_{CSCA}(n) = O(\sqrt{n})</math><br />

mit

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

{{SORTIERUNG:CarrySelectAddierer}}
[[Kategorie:Digitaltechnik]]
[[Kategorie:Computerarithmetik]]

Carry-Select-Addierer - Versionsgeschichte

imported>Aka: /* Laufzeiten */ Halbgeviertstrich