Frage zum CSA

Hallo,

mir ist aufgefallen, dass man die Kosten des Conditional Sum Adders für 2 Bit Eingänge reduzieren kann, wenn man die Schaltung wie folgt vereinfacht:


Für den Teil, der a1+b1+0 berechnet kann man einen Halbaddierer (cost(HA) = 2) verwenden.

Der Teil, der a1+b1+1 berechnet, muss folgende Funktion realisieren:

a b |s2 s1
0 0 | 0 1
0 1 | 1 0
1 0 | 1 0
1 1 | 1 1

s2 kann durch ein OR-Gatter und s1 durch ein XOR-Gatter und einen Inverter umgesetzt werden. cost()=3
Somit würden die ursprünglichen Kosten um 3+2=5 reduziert werden.
Mein Tutor meinte, dass ginge "sicherlich nicht", aber ich konnte keinen Fehler finden.
Lässt sich das auch auf größere Eingänge anwenden oder wird der Unterschied mit zunehmender Eingangsgröße verschwindend gering?

/discuss

Gute Beobachtung!

Ich stimme mit dir überein, dass man den CSA1 nicht als FA realisieren muss, sondern je nach Eingangscarry optimierte Schaltungen benutzen kann.
Für Eingangscarry 0 nimmt man einen HA mit Kosten 2 und für Eingangscarry 1 ein XNOR und ein OR, Kosten 2.
Man kann also pro CSA1 3 Gatter einsparen (Original: FA mit Kosten 5, Optimiert: Kosten 2).

Insgesamt also:
C(CSA1) = 2
C(CSAn) = 7n^(log3) - 4n - 2

Der Original-CSAn hat Kosten 10n^(log3) - 4n - 2

Das ist natürlich eine gute Einsparung, die asymptotischen Kosten liegen aber trotzdem immer noch bei O(n^log3).

Grüße
Florian