Sommatori - full adder e ripple-carry

I blocchi aritmetici fondamentali di una ALU (Blocchi logici di un microprocessore - ALU, bus e logica tri-stateUn microprocessore semplice è formato da un'unità di controllo (decodifica le istruzioni e abilita gli altri blocchi), una ALU (operazioni aritmetiche e logiche), la memoria e i registri, collegati da bus (linee condivise unidirezionali o bidirezionali). La ALU combina un sommatore con un'unità logica e un multiplexer di selezione dell'operazione: la sottrazione è A + B̄ + 1 (XOR su B e riporto in ingresso a 1), le flag (zero, riporto, segno, overflow) descrivono il risultato. Un bus è una linea pilotata da più sorgenti: per evitare conflitti ogni uscita collegata è tri-state (il segnale enable la mette in alta impedenza) oppure open-drain (solo PDN: ciascuna può imporre 0, serve un pull-up per l'1).Blocchi logici di un microprocessore - ALU, bus e logica tri-state →) sono i sommatori, i traslatori, i comparatori e i moltiplicatori. Tutti gli altri si costruiscono sul sommatore (la sottrazione è $A+\overline B+1$: Rappresentazione dei numeri e dell'informazioneUn'informazione digitale è una stringa di bit. Numeri senza segno: N bit rappresentano 0…2^N − 1; in esadecimale ogni cifra raggruppa 4 bit. Numeri con segno: complemento a due (range −2^(N−1)…2^(N−1) − 1; si nega invertendo i bit e sommando 1; il bit più significativo è il segno e l'estensione di segno lo replica). Il BCD codifica ogni cifra decimale con 4 bit (0…9) e si ottiene dal binario con l'algoritmo double dabble (shift a sinistra, e +3 a ogni gruppo maggiore di 4 prima dello shift). Il codice Gray cambia un solo bit tra valori consecutivi. I numeri frazionari si trattano in virgola fissa (4 bit di parte frazionaria = multipli di 1/16), i caratteri in ASCII, gli errori con un bit di parità.Rappresentazione dei numeri e dell'informazione →).

Addizione di bit e di numeri

La somma di due bit $X+Y$ dà un bit di somma $S$ e un bit di riporto (carry) $C$: $0+0=00$, $0+1=01$, $1+0=01$, $1+1=10$ (riporto $1$, somma $0$). Un half adder ha $S=A\oplus B$, $C=AB$. Per sommare numeri a più bit, ogni posizione deve sommare anche il riporto della posizione precedente: tre bit $A$, $B$, $C_{in}$ danno somma $S$ e riporto $C_{out}$.

Full adder

Formula (full adder). Il full adder (sommatore completo a un bit) ha per tabella di verità $$S=A\oplus B\oplus C_{in}=\overline A\,\overline B\,C_{in}+\overline AB\,\overline{C_{in}}+A\overline B\,\overline{C_{in}}+ABC_{in},\qquad C_{out}=AB+BC_{in}+AC_{in}.$$

Esempio. Con $A = 1$, $B = 1$ e $C_{in} = 1$: $S = 1 \oplus 1 \oplus 1 = 1$ e $C_{out} = 1$ (almeno due ingressi valgono $1$).

Definizione (generate, propagate, delete e riporto). Il riporto d'uscita è la funzione maggioranza: vale $1$ se almeno due ingressi valgono $1$. Si ottimizza il circuito con tre segnali:

• generate $G=AB$: lo stadio genera un riporto $1$ indipendentemente da $C_{in}$;
• propagate $P=A\oplus B$ (o $A+B$): lo stadio propaga il riporto d'ingresso;
• delete (kill) $D=\overline A\,\overline B$: lo stadio cancella il riporto (uscita $0$ qualunque $C_{in}$). Allora $$C_{out}=G+P\cdot C_{in},\qquad S=P\oplus C_{in}.$$

Esempio. Con $A = 1$ e $B = 0$: $P = 1$ e $G = 0$, quindi $C_{out} = C_{in}$; con $A = B = 1$: $G = 1$ e $C_{out} = 1$ qualunque sia $C_{in}$.

Una scomposizione utile è in due fasi: set-up (calcolo di $G$ e $P$ da $A$ e $B$, indipendenti da $C_{in}$) e carry/sum (calcolo di $C_{out}$ ed $S$, che dipendono da $C_{in}$). Una realizzazione a gate di trasmissione (Logica a pass-transistor e gate di trasmissioneNella logica a pass-transistor gli ingressi pilotano sia i gate sia i terminali di source/drain di una rete di interruttori (N transistor per N ingressi, nessun consumo statico, alcune funzioni, come AND, MUX e XOR, richiedono pochi transistor). Gli n-MOS trasmettono bene gli 0 ma male gli 1 (V_DD − V_Tn, con effetto body: circa 1,8 V da 2,5 V), i p-MOS al contrario (V_Tp in modulo per lo 0): il livello degradato non è rigenerato e può far condurre un inverter successivo (consumo statico). Il gate di trasmissione (n-MOS e p-MOS in parallelo, con G e nG complementari) trasmette bene entrambi i livelli, con resistenza R_n‖R_p quasi costante, ma costa due transistor e raddoppia le capacità. Una catena di n pass-transistor ha ritardo ∝ n² (Elmore, 0,69 R C n(n+1)/2): si inseriscono buffer ogni m = 1,7√(t_buf/(R_eq C)) stadi.Logica a pass-transistor e gate di trasmissione →) usa $P$ per scegliere: $C_{out}=C_{in}$ se $P=1$, altrimenti $C_{out}=A$ (se $A=B$ il riporto è $A$); e una XOR a gate di trasmissione per $S$.

Sommatore ripple-carry

Formula (ritardo del sommatore ripple-carry, caso peggiore). Un sommatore a $N$ bit si ottiene collegando $N$ full adder in cascata: $C_{out,i}=C_{in,i+1}$. Il riporto "si propaga a onda" (ripple) dal bit meno significativo al più significativo. Indicati $t_s$ il ritardo del sum (da $C_{in}$ a $S$) e $t_c$ il ritardo di carry (da $C_{in}$ a $C_{out}$) di un full adder, e con $C_{in,0}=0$:

• il bit $i$ dà la somma al tempo $t_s+\big(\text{ritardi di riporto accumulati fino allo stadio }i\big)$;
• nel caso peggiore (riporto che attraversa tutti gli stadi: tutti $P=1$) l'ultimo bit attende $N-1$ ritardi di carry: $$\boxed{t_{add}=(N-1)\,t_c+t_s}\qquad(\text{lineare in }N).$$

Si include il set-up quando vale: $t_{add}=t_{setup}+(N-1)t_c+t_s$.

Esempio numerico. $t_c=100\ \mathrm{ps}$, $t_s=150\ \mathrm{ps}$: $N=4$: $450\ \mathrm{ps}$; $N=16$: $1650\ \mathrm{ps}$; $N=32$: $3250\ \mathrm{ps}$: raddoppiando il numero di bit il ritardo raddoppia circa. È il sommatore più semplice e compatto, ma lento: per le larghezze maggiori si usano architetture più veloci (Sommatori veloci - carry-bypass, carry-select e square-rootIl ripple-carry ha ritardo lineare in N. Il carry-bypass divide i bit in blocchi da M: se tutti i propagate del blocco valgono 1 (BP = P0P1…P_{M−1} = 1) un multiplexer fa saltare il riporto dall'ingresso all'uscita del blocco. Ritardo: t = t_setup + M t_carry + (N/M − 1) t_mux + (M−1) t_carry + t_sum, ottimo per M = √(N t_mux/(2 t_carry)); è determinato principalmente dal tempo di riporto. Il carry-select calcola in ogni blocco le somme per riporto 0 e per riporto 1 e un mux sceglie quella giusta: t = t_setup + M t_carry + (N/M) t_mux + t_sum, M ottimo √(N t_mux/t_carry); lo square-root carry-select usa blocchi di dimensione crescente (M, M+1, M+2…) perché il riporto arriva ogni volta un mux dopo: N ≈ K²/2 e t = t_setup + M t_carry + √(2N) t_mux + t_sum, cioè ritardo ∝ √N.Sommatori veloci - carry-bypass, carry-select e square-root →).

Ritardo dipendente dagli operandi

Il ritardo reale dipende dai dati. Si assumono $A$, $B$ applicati insieme e $C_{in,0}$ noto. Il riporto in uscita dallo stadio $i$ è disponibile dopo un tempo $\tau_{i}=t_c$ se lo stadio è generate o delete (la sua uscita non dipende da $C_{in}$) e $\tau_i=t_c+\tau_{i-1}$ se è propagate. Il tempo totale è $t_s$ più il massimo ritardo del riporto entrante in uno stadio, cioè $t_c$ per il numero di stadi consecutivi della catena più lunga (un generate o delete e i propagate che lo seguono).

Esempio dalle slide (stadi $0\ldots3$ con $(A_i,B_i)=(1,0),(0,1),(1,1),(0,0)$): lo stadio $0$ è propagate ($C_{in,0}=0$ è comunque contato: $C_{out,0}$ è disponibile a $t_c$), lo stadio $1$ propagate ($2t_c$), lo stadio $2$ generate (resetta la catena), lo stadio $3$ delete. Le somme sono pronte a $t_s$, $t_s+t_c$, $t_s+2t_c$ e $t_s+t_c$ (lo stadio $3$ riceve il riporto dello stadio $2$, che dipende solo da $G_2$): $t_{add}=2t_c+t_s$.

Operandi uguali bit a bit ($A_i=B_i$ in ogni posizione): ogni stadio è generate o delete, nessun riporto si propaga e $t_{add}=t_c+t_s$ (i due operandi devono coincidere in ogni posizione, cioè essere lo stesso numero: se differissero anche solo in alcuni bit comparirebbero stadi propagate). Per esempio la somma di due numeri a $16$ bit identici si completa in $t_c+t_s$ e non in $15\,t_c+t_s$.

Esempio con operandi a 16 bit ($A=1010101010101000$, $B=1100100010101100$, LSB a destra): le posizioni $0,\dots,15$ sono, nell'ordine, D, D, P, G, D, G, D, G, D, P, D, G, D, P, P, G. Il ritardo del riporto entrante nel bit $15$ è il massimo: nasce dallo stadio D in posizione $12$ ($t_c$), poi due stadi P (posizioni $13$ e $14$): $3\,t_c$. Quindi $t_{add}=3\,t_c+t_s$, molto minore del caso peggiore ($15\,t_c+t_s$). (Esercizio 17 · quesiti rapidi sui sommatori con dati numerici (temi d'esame 2025-2026) discute questo caso.)

Lunghezza dei numeri e overflow

La somma di due numeri a $N$ bit richiede $N+1$ bit (il riporto d'uscita $C_{out,N-1}$ è il bit in più). In complemento a due l'overflow si rivela con il confronto dei segni oppure come $C_{N-1}\oplus C_N$ (riporto entrante e uscente nell'ultimo stadio).

Errori comuni

• Usare $N\,t_c$ o $N(t_c+t_s)$ invece di $(N-1)t_c+t_s$ (la somma si calcola una sola volta, in fondo).
• Ritenere il ritardo $(N-1)t_c+t_s$ valido per ogni coppia di numeri: è il caso peggiore.
• Dimenticare che un bit generate o delete interrompe la catena del riporto.
• Confondere propagate ($A\oplus B$) e generate ($AB$).