Binäraddierer sind Schaltnetze zur Realisierung der Addition von Binärzahlen in Festkommadarstellung. Eingänge sind die beiden k-Bit-Operanden a und b sowie der Übertrag für die 0-te Stelle. Ausgegeben werden das k-Bit-Resultat und der Übertrag von der höchsten Stelle. Das Verhalten auf der R-T-Ebene ist damit festgeschrieben. Der Addierer für k = 1 Bit heisst Volladdierer. Das Schaltnetz ist ziemlich einfach:
binexp2bintab3({'a+b+c';'(a&b)|(a&c)|(b&c)'},{'a';'b';'c'},2)
Die Simulation des Volladdierers ist entsprechend überschaubar:
function [s,c] = fulladd(a,b,ci,q)
% [s,c] = fulladd(a,b,ci,q)
% Volladdierer für Stellensysteme zur Basis q
if nargin<4 q = 2; end;
z = a + b + ci;
s = rem(z,q);
c = floor(z/q);
Wir wollen im folgenden beispielhaft mögliche Realisierungen auf der Gatterebene angeben sowie den Aufbau schneller Addierer für große k .
Serieller-Addierer
Der serielle Addierer arbeitet nach dem in der Grundschule gelernten Prinzip der stellenweisen Addition beginnend bei der niederwertigsten Stelle. Die Hardware ist ein einfaches Schaltwerk bestehend aus einem Volladdierer und einem Zustandsflipflop, dem pro Takt je ein Bit der beiden Operanden beginnend mit dem niederwertigsten am Eingang angeboten wird:
q = 2; % Basis des Stellensystems
a = reverse([0 1 1 0 1]); % Stellenvektor des Summanden a
b = reverse([0 0 1 1 1]); % Stellenvektor des Summanden b
c = 0; % Übertrag 0
clear s
for k=1:length(a)
[s(k),c] = fulladd(a(k),b(k),c,q);
end
reverse(s),c % Ausgabe ins Kommandofenster
Dieser Code soll nur das zeitliche Nacheinander aufzeigen. Die Addition selbst wird durch die Funtion demofixpointadd dargestellt.
Ripple-Carry-Addierer
Der Ripple-Carry-Addierer arbeitet nach dem selben Schema wie der serielle Addierer. Jedoch werden für n-stellige Operanden n Volladdierer in Hardware realisiert. Der k-te Volladdierer empfängt den Übertrag des (k-1)-ten Volladdierers und gibt den selbst berechneten Übertrag an den nächsten Volladdierer. Obwohl alle Volladdierer im Schaltnetz parallel arbeiten, kann die höchstwertige Stelle erst endgültig berechnet werden, wenn bei diesem Volladdierer der Übertrag eintrifft. Im Gegensatz zum seriellen Addierer ist der Ripple-Carry-Addierer ein Schaltnetz.
Eine rekursive Simulation des Ripple-Carry-Addierers zeigt folgende Matlab-Funktion:
function [s,c] = ripplecarryadd(a,b,c0,q)
% [s,c] = ripplecarryadd(a,b,ci,q)
% Ripple-Carry-Addierer
% a, b : Vektoren der Ziffern der Summanden,
% Die Länge der Vektoren müssen gleich sein.
% c0 : Übertrag in die niederwertigste Stelle
% q : Basis des Systems, Default: 2
% s : Vektor der Ziffern der Summe.
% s hat die selbe Anzahl von Stellen wie a und b.
% c : Übertrag von der höchstwertigen Stelle.
% c kann als höchstwertige Stelle dem Vektor s
% nachgestellt werden.
if length(a)==1
[s,c] = fulladd(a,b,c0,q);
else
[sx,cx] = ripplecarryadd(a(1:end-1),b(1:end-1),c0,q);
[sy,c] = fulladd(a(end),b(end),cx,q);
s = [sx,sy];
end
Carry-Lookahed-Addierer
Anstatt die Überträge stellenweise zu berechnen kann man sämtliche Überträge direkt aus den Operanden ermitteln. Das Schaltnetz dafür ist ziemlich aufwändig - besonders für grosse Stellenzahlen. Diese Addierer heissen Carry-Lookahead-Addierer.
Carry-Select-Addierer
Für grosse Stellenzahlen ist der Carry-Lookahead-Addierer nicht mehr praktikabel. Mit drei n-Bit-Addierern (z.B. Carry-Lookahead- oder auch Carry-select-) kann man einen 2n-Bit-Addierer wie folgt realisieren:
Ein n-Bit-Addierer berechnet die niederwertigen n Bit der Summe und den Übertrag der n-ten Stelle. Zugleich berechnen zwei völlig gleiche n-Bit-Addierer die höherwertigen n Bit der Summe für die beiden möglichen Überträge der n-ten Stelle. Die Summen werden alle zeitgleich fertig. Mit einem n-fachen 2-zu-1-Multiplexer wird dann das Ergebnis aufgrund des tatsächlichen Übertrags der n-ten Stelle ausgewählt, das andere wird verworfen.
Eine Simulation zeigt folgende Matlab-Funktion:
function [s,c] = carryselectadd(a,b,ci,q)
% [s,c] = carryselectadd(a,b,ci,q)
% Carry-Select-Addierer
% a, b : Vektoren der Ziffern der Summanden,
% c0 : Übertrag in die niederwertigste Stelle
% q : Basis des Systems, Default: 2
% s : Vektor der Ziffern der Summe.
% s hat die selbe Anzahl von Stellen wie a und b.
% c : Übertrag von der höchstwertigen Stelle.
% c kann als höchstwertige Stelle dem Vektor s nachgestellt werden.
n = max(1,floor(length(a)/2));
% Simulation der parallelen Berechnung mit drei Addierern
% =======================================================
[sn,cn] = add(a(1:n),b(1:n),ci,q); % niedere n Bit
[s0,c0] = add(a(n+1:end),b(n+1:end),0,q); % höhere Bit für Carryin = 0
[s1,c1] = add(a(n+1:end),b(n+1:end),1,q); % höhere Bit für Carryin = 1
% Selektion des richtigen Ergebnisses
% ===================================
if cn==0
s = [sn s0];
c = c0;
else
s = [sn s1];
c = c1;
end