Überlauferkennung in einem CSA (Carry-save Adder)

In einem Carry-Save-Addierer gibt es drei Eingänge und zwei Ausgänge. Viele verschiedene Ausgangspaare repräsentieren dieselbe Zahl. Carry-Save-Addierer haben keinen Carry-Propagation-Overhead, daher eignen sie sich gut zum Addieren vieler Operanden mit geringer Latenz, aber der Preis für diese Geschwindigkeit besteht darin, dass Sie nicht wirklich etwas über das Ergebnis wissen (selbst ob es positiv oder negativ ist). ) bis Sie die letzten beiden Ausgänge mit einem "normalen" Addierer (z. B. Ripple-Carry, Carry-Select, Carry-Skip oder Carry-Lookahead) addieren.

Ich kenne keine Möglichkeit, einen Überlauf zu bestimmen, indem ich einfach auf die höchstwertigen Bits schaue (wie Sie es in einem Addierer können, der trägt). Hier ist zum Beispiel ein Beispiel, das im 3-Bit-2er-Komplement überläuft (3 + 3-2 = 4).

  0 1 1     (3)
  0 1 1     (3)
  1 1 0     (-2)
  -----
  1 1 0     (-2)
0 1 1       (6)

Und ein weiteres mit denselben höchstwertigen Bits, das nicht überläuft:

  0 1 1     (3)
  0 1 1     (3)
  1 0 1     (-3)
  -----
  1 0 1     (-3)
0 1 1 0     (6)

Ich musste in mein 68HC11-Handbuch zurückgreifen, um herauszufinden, wo ich in meiner Antwort falsch lag. So! Die Antwort ist, sich die Vorzeichenbits sowohl der Eingaben als auch der Ergebnisse anzusehen.

• Wenn Sie zwei positive Zahlen addieren und das Ergebnis negativ ist, hatten Sie einen Überlauf.
• Wenn Sie zwei negative Zahlen addieren und das Ergebnis positiv ist, hatten Sie einen Überlauf
• Die Addition einer negativen und einer positiven Zahl kann nicht überlaufen

Sie können einen Überlauf nach dem CSA erkennen, indem Sie die beiden höchstwertigen Übertragsbits bezeichnen$C_o$(das Bit, das verworfen wird) und$C$, und das höchstwertige Vorzeichenbit,$S$. Die Addition wird überlaufen, wenn$C_o = S = 0$Und$C=1$, dh alle positiven Zahlen in, aber die Summe kann nicht in der entsprechenden Zweierkomplementdarstellung dargestellt werden (obwohl man durch doppelte Überläufe am Ende eigentlich eine positive Zahl erhält) oder$C_0 = S = 1$Und$S=0$, dh alle negativen Eingaben, aber eine zu hohe Größe (aber es kann wegen doppelter Überläufe immer noch zu einer negativen Zahl führen).

Der Überlauf in der abschließenden Addition (Übertragssicherung in nichtredundante Form) wird wie üblich erkannt (vergleicht man die beiden letzten Übertragsbits, wenn sie unterschiedlich sind, gibt es einen Überlauf, wie wir sehen werden, eine Überprüfung der Vorzeichen ist nicht möglich).

Beispiel 1:

  011
  011
 +011
-----
 011  carry
  011 sum

Überlauf als$C_o = 0, S = 0, C = 1$

  110
 +011
 ----
  001

Hier kommt es am Ende zu einem weiteren Überlauf (obwohl dies nicht erkannt wird, da aus einer Zweierkomplement-Perspektive$-2 + 3$läuft nicht über), so dass trotz des Überlaufs eine positive Zahl erhalten wird.

Beispiel 2:

  010
  010
 +110
-----
 010  carry
  110 sum

Kein Überlauf wie$C_o = 0, S = 1, C = 1$

  100
 +110
 ----
  010

Korrekte Antwort! Es scheint jedoch, dass ein Überlauf aufgetreten ist, wenn man die Zweierkomplementaddition betrachtet. Dies kann gelöst werden, indem die Vorzeichenbits durch ersetzt werden$S' = C_o$Und$C'= C \oplus S \oplus C_o$(dadurch wird auch die Carry-Save-Darstellung verschiebbar) was zu führt

  000
 +010
 ----
  010

und kein Überlauf festgestellt (was richtig ist).

Beispiel 3:

  011
  011
 +111
-----
 011  carry
  111 sum

Kein Überlauf wie$C_o = 0, S = 1, C = 1$

  110
 +111
 ----
  101

Auch hier kein Überlauf erkannt, obwohl einer vorhanden ist. Ersetzen Sie die Vorzeichenbits wie oben beschrieben:

  010
 +011
 ----
  101

Da sich nun der ankommende Übertrag zur Endstufe (1) von dem abgehenden (0) unterscheidet, wird ein Überlauf erkannt, was natürlich korrekt ist$3+3-1$ist aus dem$[-4,3]$Reichweite möglich

All dies wird in „Carry-save architectures for high-speed digital signal processing“ von Tobias Noll vorgeschlagen und diskutiert.