Sommatori binari - half adder, full adder e ripple carry

I circuiti aritmetici binari sono circuiti combinatori che eseguono somme, sottrazioni e altre operazioni su numeri binari. Sono l'esempio tipico di circuito iterativo: la stessa sotto-funzione è ripetuta per ogni bit, e i blocchi uguali si passano dati intermedi (i riporti) che non compaiono in uscita. Si usa quindi l'approccio gerarchico (Progettazione di una rete combinatoria - approccio gerarchico e porte NAND-NORUna rete combinatoria ha uscite che dipendono solo dagli ingressi presenti (nessuna memoria, nessuna retroazione); una sequenziale dipende anche dalla storia (stato, memoria, feedback). Progetto: specifiche, tabella di verità, funzione a costo minimo, diagramma logico, verifica. Con molti ingressi si usa l'approccio gerarchico (blocchi e sottoblocchi riusabili; regolarità). Blocchi base: funzioni di una variabile, vettori, enabling. Mappatura tecnologica: in CMOS NAND e NOR sono più compatte, quindi SOP $\to$ NAND-NAND e POS $\to$ NOR-NOR.Progettazione di una rete combinatoria - approccio gerarchico e porte NAND-NOR →).

Half adder (semisommatore)

L'half adder somma due bit $X$ e $Y$ e dà due uscite: la somma $S$ (il bit meno significativo del risultato) e il riporto $C$ (carry).

Formula (half adder)

$$S=X\oplus Y,\qquad C=X\cdot Y .$$

Esempio. Con $X=Y=1$: $S=1\oplus1=0$ e $C=1\cdot1=1$, cioè $1+1=10_2$.

È una porta XOR più una AND. Non gestisce un riporto in ingresso.

Full adder (sommatore completo)

Il full adder somma tre bit: i due addendi $X,Y$ e il riporto in ingresso $Z$ proveniente dal bit meno significativo vicino.

Formula (full adder: somma e riporto). La somma $S$ vale 1 quando il numero di 1 in ingresso è dispari: è la funzione di disparità (Mappe di Karnaugh - POS, condizioni di don't care e paritàPer la POS minima si raggruppano gli 0 della mappa, si ottiene la SOP minima di $\overline F$ e si scrive $F$ come prodotto di somme (variabile diretta se vale 0 nel gruppo, negata se vale 1). Le condizioni di don't care (X) sono combinazioni di ingresso che non si presentano o la cui uscita è indifferente: si usano come 1 o come 0 a seconda di quel che allarga i gruppi (mai raggruppamenti fatti solo di X). Le funzioni XOR a più variabili (disparità) e XNOR (parità) hanno mappa a scacchiera: non si semplificano con i gruppi.Mappe di Karnaugh - POS, condizioni di don't care e parità →), $S=X\oplus Y\oplus Z=\sum m(1,2,4,7)$. Il riporto $C$ vale 1 quando almeno due ingressi valgono 1 (funzione maggioranza): $C=\sum m(3,5,6,7)=XY+XZ+YZ$ (SOP minima: 3 implicanti primi, tutti essenziali).

Esempio. Con $X=Y=Z=1$: $S=1$ e $C=1$ ($1+1+1=11_2$); con $X=1,Y=0,Z=1$: $S=0$ e $C=1$ ($1+0+1=10_2$).

Formula (full adder con propagate e generate). Si pone $P=X\oplus Y$ (propagate) e $G=XY$ (generate). Allora $$S=P\oplus Z,\qquad C=G+P\cdot Z .$$

Esempio. Con $X=1,Y=0,Z=1$: $P=1$, $G=0$, $S=P\oplus Z=0$ e $C=G+PZ=1$.

Il riporto in uscita c'è se i due bit generano un riporto da soli ($X=Y=1$) oppure se propagano il riporto in ingresso ($X\ne Y$ e $Z=1$). Quindi un full adder è: un primo half adder $(X,Y)\to(P,G)$, un secondo half adder $(P,Z)\to(S,\,PZ)$ e una OR che unisce $G$ e $PZ$. Equivalenza con la forma a maggioranza: $XY+Z(X\oplus Y)=XY+Z(\overline XY+X\overline Y)=XY+\overline XYZ+X\overline YZ=XY+XZ+YZ$ (si usano $XY+\overline XYZ=XY+YZ$ e $XY+X\overline YZ=XY+XZ$, cioè $X+\overline XW=X+W$ con il fattore comune raccolto).

Ripple carry adder

Definizione (sommatore ripple carry). Per sommare due numeri di $n$ bit $A=A_{n-1}\dots A_0$ e $B=B_{n-1}\dots B_0$ si collegano $n$ full adder: il riporto in uscita di ciascuno è il riporto in ingresso del successivo, dal LSB ($C_0$, di solito $0$) al MSB ($C_n$). Il riporto si propaga (ripple = ondeggiare) lungo la catena.

Esempio: $0110+0111$ ($6+7$). Si procede dal bit 0:

Somma $S_3S_2S_1S_0=1101=13$, riporto finale $C_4=0$ ✓.

Esempio con riporto in uscita: $1011+0101$ ($11+5$): le somme parziali sono tutte $0$ e i riporti $C_1=C_2=C_3=C_4=1$: risultato $0000$ con $C_4=1$, cioè $10000_2=16$. Per numeri senza segno $C_4=1$ indica overflow (il risultato non sta in 4 bit) (Numeri con segno, complemento a 2, sottrazione e overflowSottrazione senza segno: se $M\ge N$ nessun prestito in uscita, altrimenti il risultato $M-N+2^n$ è scorretto. Complemento a 1: $2^n-1-N$ (inversione bit a bit); complemento a 2: $2^n-N=$ complemento a 1 $+1$. Numeri con segno: segno e modulo (due zeri, intervallo simmetrico) oppure complemento a 2 (un solo zero, da $-2^{n-1}$ a $2^{n-1}-1$, MSB di peso $-2^{n-1}$). In complemento a 2 somma e sottrazione sono la stessa addizione: $A-B=A+\overline B+1$, riporto in uscita scartato. Overflow: senza segno $\Leftrightarrow C_{out}=1$ nella somma; con segno $\Leftrightarrow C_{in,MSB}\ne C_{out,MSB}$ (due operandi dello stesso segno con risultato di segno opposto).Numeri con segno, complemento a 2, sottrazione e overflow →).

Un sommatore a 4 bit con riporto in ingresso ha 9 ingressi: una tabella di verità da $2^9=512$ righe sarebbe ingestibile; da qui l'utilità della struttura iterativa.

Ritardo

Formula (ritardo del sommatore ripple carry). Ogni full adder può calcolare la propria somma solo quando riceve il riporto dal precedente: i riporti si determinano uno dopo l'altro. Se ogni porta ha ritardo $t_G$, il riporto attraversa ogni stadio in circa $2t_G$ (una AND e una OR). Il ritardo totale cresce linearmente con $n$: circa $2n\,t_G$ per l'ultima somma. Il ripple adder è il più semplice e il più lento; per numeri a molti bit si usano circuiti con riporto anticipato (carry look-ahead), non trattati nel corso.

Esempio. Con $n=8$ bit e $t_G=1\,\mathrm{ns}$ l'ultima somma arriva dopo circa $2\cdot8\cdot1=16\,\mathrm{ns}$.

VHDL

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;

entity fa is
  port ( x, y, cin : in  std_logic;
         s, cout   : out std_logic );
end fa;

architecture df of fa is
begin
  s    <= x xor y xor cin;
  cout <= (x and y) or (cin and (x xor y));
end df;

Sommatore a 4 bit gerarchico (structural, quattro istanze del full adder):

entity add4 is
  port ( a, b : in  std_logic_vector(3 downto 0);
         cin  : in  std_logic;
         s    : out std_logic_vector(3 downto 0);
         cout : out std_logic );
end add4;

architecture ripple of add4 is
  signal c : std_logic_vector(4 downto 0);     -- riporti interni
begin
  c(0) <= cin;
  FA0 : entity work.fa(df) port map (a(0), b(0), c(0), s(0), c(1));
  FA1 : entity work.fa(df) port map (a(1), b(1), c(1), s(1), c(2));
  FA2 : entity work.fa(df) port map (a(2), b(2), c(2), s(2), c(3));
  FA3 : entity work.fa(df) port map (a(3), b(3), c(3), s(3), c(4));
  cout <= c(4);
end ripple;

Versione behavioral: non descrive il circuito ma il comportamento, e lascia al sintetizzatore la scelta dell'hardware. Realizza il sommatore come somma di tre numeri senza segno da 5 bit: i due addendi preceduti da uno '0' e il riporto in ingresso preceduto da quattro '0'; il riporto in uscita è il bit più significativo del risultato.

architecture behav of add4 is
  signal cin5 : std_logic_vector(4 downto 0);
  signal sum  : std_logic_vector(4 downto 0);
begin
  cin5 <= "0000" & cin;
  sum  <= std_logic_vector( unsigned('0' & a) + unsigned('0' & b) + unsigned(cin5) );
  s    <= sum(3 downto 0);
  cout <= sum(4);
end behav;

Cenni sul moltiplicatore

Come in decimale, si moltiplica il moltiplicando per ciascun bit del moltiplicatore (un prodotto di due bit è una AND) ottenendo i prodotti parziali, che si traslano e si sommano. Il moltiplicatore a 2 bit ($A_1A_0\times B_1B_0$, prodotto $P_3P_2P_1P_0$) usa 4 AND e 2 half adder: $$P_0=A_0B_0,\quad P_1=A_1B_0\oplus A_0B_1,\quad P_2=A_1B_1\oplus(A_1B_0\cdot A_0B_1),\quad P_3=A_1B_1\cdot(A_1B_0\cdot A_0B_1).$$ Controllo con $A=B=3$: $P_0=1$; $P_1=1\oplus1=0$ con riporto $1$; $P_2=1\oplus1=0$; $P_3=1\cdot1=1$ → $P=1001=9$ ✓ (verificato su tutte le 16 combinazioni).

Errori comuni

• Dimenticare il riporto in ingresso nel full adder (un half adder non basta per i bit centrali).
• Leggere $C_4=1$ come "risultato errato" per numeri con segno: il criterio di overflow è diverso (Numeri con segno, complemento a 2, sottrazione e overflowSottrazione senza segno: se $M\ge N$ nessun prestito in uscita, altrimenti il risultato $M-N+2^n$ è scorretto. Complemento a 1: $2^n-1-N$ (inversione bit a bit); complemento a 2: $2^n-N=$ complemento a 1 $+1$. Numeri con segno: segno e modulo (due zeri, intervallo simmetrico) oppure complemento a 2 (un solo zero, da $-2^{n-1}$ a $2^{n-1}-1$, MSB di peso $-2^{n-1}$). In complemento a 2 somma e sottrazione sono la stessa addizione: $A-B=A+\overline B+1$, riporto in uscita scartato. Overflow: senza segno $\Leftrightarrow C_{out}=1$ nella somma; con segno $\Leftrightarrow C_{in,MSB}\ne C_{out,MSB}$ (due operandi dello stesso segno con risultato di segno opposto).Numeri con segno, complemento a 2, sottrazione e overflow →).
• Credere che il ripple adder sia veloce: il ritardo cresce con $n$.
• Confondere $S$ (bit di somma) con $C$ (riporto) nello scrivere le uscite dell'half adder.