Numeri con segno, complemento a 2, sottrazione e overflow

Il sommatore (Sommatori binari - half adder, full adder e ripple carryHalf adder (2 ingressi): $S=X\oplus Y$, $C=XY$. Full adder (3 ingressi, con riporto in ingresso $Z$): $S=X\oplus Y\oplus Z$, $C=XY+XZ+YZ=G+PZ$ con $P=X\oplus Y$, $G=XY$; si realizza con due half adder e una OR. Il ripple carry adder a $n$ bit concatena $n$ full adder: il riporto "ondeggia" dal LSB al MSB, quindi il ritardo cresce linearmente con $n$. È un circuito iterativo (gerarchico e regolare). Il moltiplicatore a 2 bit usa 4 AND e 2 half adder.Sommatori binari - half adder, full adder e ripple carry →) lavora su numeri senza segno. Come rappresentare i numeri negativi, in modo che lo stesso circuito faccia somme e sottrazioni? La risposta è il complemento a 2. (Un'altra trattazione è in Rappresentazione dei numeri interi con segnoInteri con segno su n bit: modulo e segno, complemento a 1, complemento a 2 ed eccesso K; intervalli rappresentabili, calcolo dell'opposto, estensione del segno.Rappresentazione dei numeri interi con segno → e Aritmetica binariaSomma e sottrazione in binario, overflow per senza segno (riporto) e per complemento a 2 (segni), flag del processore, moltiplicazione per somme e scorrimenti, algoritmo di Booth, divisione, shift logici e aritmetici.Aritmetica binaria →.)

Sottrazione di numeri senza segno

Si sottrae $N$ da $M$ (entrambi su $n$ bit) bit per bit con i prestiti (Basi di numerazione e conversioni - binario, ottale ed esadecimaleUn numero in base $r$ vale $\sum a_i r^i$ (cifre $a_i\in{0,\dots,r-1}$). Conversioni: base $r\to$ decimale con la somma pesata; decimale $\to$ base $r$ per divisioni successive (parte intera, resti letti dal basso) e moltiplicazioni successive (parte frazionaria, parti intere lette dall'alto); binario $\leftrightarrow$ ottale/esadecimale a gruppi di 3/4 bit. Somma, differenza e prodotto binari seguono le regole decimali con cifre 0 e 1; la differenza ha prestiti, il prodotto somma prodotti parziali traslati.Basi di numerazione e conversioni - binario, ottale ed esadecimale →).

• Se $M\ge N$: nessun prestito in uscita dal bit più significativo, e il risultato è corretto.
• Se $M<N$: c'è un prestito in uscita e il risultato è $M-N+2^n$, sbagliato. Il valore assoluto corretto è $2^n$ meno il risultato ottenuto (il suo complemento a 2), e il segno è negativo.

Esempio ($n=8$): $01100100-10010110$ ($100-150$). Il risultato a 8 bit è $11001110$ ($206=100-150+256$), con prestito in uscita $1$ ($M<N$). Valore assoluto: $256-206=50=00110010$. Risultato corretto: $-00110010_2=-50$.

Altro esempio con $M\ge N$: $10011011-01001110$ ($155-78$) $=01001101$ ($77$), nessun prestito.

Complementi

Definizione (complemento a 1 e a 2). Dato $N$ su $n$ bit:

• complemento a 1: $(2^n-1)-N$, cioè il complemento di ogni bit (si scambiano 0 e 1);
• complemento a 2: $2^n-N$, cioè complemento a 1 più 1.

Esempio. $N=1011001$ su $7$ bit: complemento a 1 $=0100110$ (bit invertiti), complemento a 2 $=0100110+1=0100111$.

Il complemento del complemento restituisce $N$. Per $0$ il complemento a 2 su $n$ bit è ancora $0$ (si scarta il riporto).

Sottrazione con il complemento a 2. Poiché $M-N=M+(2^n-N)-2^n$, si somma a $M$ il complemento a 2 di $N$ e si toglie $2^n$:

• se $M\ge N$ la somma produce un riporto in uscita (il termine $2^n$), che si scarta: resta $M-N$;
• se $M<N$ non c'è riporto in uscita e la somma vale $2^n-(N-M)$, il complemento a 2 della differenza: per ottenere il modulo si ripete il complemento a 2, e si mette il segno meno.

In questo modo la stessa addizione serve per sommare e sottrarre; con i numeri in complemento a 2 (sotto) l'ultimo passaggio sparisce.

Rappresentare numeri con segno

Si vedono due rappresentazioni a $n$ bit.

Segno e modulo. Si antepone un bit di segno: $0$ per positivi (e zero), $1$ per negativi. Un numero e il suo opposto differiscono solo per il bit di segno. Con 4 bit: da $-7$ a $+7$, ma lo zero ha due rappresentazioni ($0000$ e $1000$). Le operazioni trattano segno e modulo separatamente, quindi la sottrazione richiede una correzione di segno.

Definizione (numeri con segno in complemento a 2). I positivi sono come in senza segno ($0$ seguito dal modulo); un negativo $-N$ si rappresenta con il complemento a 2 di $N$, cioè $2^n-N$. L'MSB è $0$ per tutti i positivi e $1$ per tutti i negativi. Con 4 bit:

bit	senza segno	segno e modulo	complemento a 2
0000	0	$+0$	0
0111	7	7	7
1000	8	$-0$	$-8$
1001	9	$-1$	$-7$
1010	10	$-2$	$-6$
1011	11	$-3$	$-5$
1100	12	$-4$	$-4$
1101	13	$-5$	$-3$
1110	14	$-6$	$-2$
1111	15	$-7$	$-1$

Esempio. A $8$ bit $-13=2^8-13=243=11110011$.

Proprietà (intervallo e peso dell'MSB in complemento a 2). In complemento a 2 c'è un solo zero e l'intervallo è asimmetrico: da $-2^{n-1}$ a $2^{n-1}-1$ (con 8 bit da $-128$ a $127$; $-(-128)$ non è rappresentabile). Il valore si legge dando all'MSB il peso $-2^{n-1}$: $11110011=-128+64+32+16+2+1=-13$.

Esempio. A $4$ bit l'intervallo è da $-8$ a $+7$; $1011=-8+2+1=-5$.

Esempi a 8 bit: $+9=00001001$; $-9$: segno e modulo $10001001$, complemento a 2 $11110111$ ($=256-9$: si inverte $00001001\to11110110$ e si somma 1). $-13$: segno e modulo $10001101$, complemento a 2 $11110011$. Il numero $-3$ a 8 bit in complemento a 2 è $11111101$. Estensione del segno: per aumentare i bit di un numero in complemento a 2 si replica l'MSB ($1101\to11111101$ resta $-3$).

I calcolatori usano il complemento a 2 perché somma e sottrazione condividono lo stesso hardware.

Somma e sottrazione con segno in complemento a 2

Somma: si sommano i numeri inclusi i bit di segno e si scarta il riporto in uscita dal bit di segno. Il risultato è in complemento a 2. Esempi a 8 bit:

Formula (sottrazione in complemento a 2). $A-B=A+(-B)$, cioè si somma ad $A$ il complemento a 2 di $B$: $A-B=A+\overline B+1$ (complemento a 1 di $B$ più 1). Esempio: $+7-(-12)$: $-12=11110100$, il suo complemento a 2 è $00001100$ ($+12$), e $00000111+00001100=00010011=+19$ ✓.

Esempio. A $4$ bit, $5-3$: $0101+\overline{0011}+1=0101+1100+1=(1)\,0010=+2$, riporto scartato.

Circuito addizionatore-sottrattore

Con un solo circuito si fanno entrambe le operazioni: si introduce un segnale $S$ (0 = somma, 1 = sottrazione). Ogni bit $B_i$ passa per una porta XOR con $S$: se $S=0$ passa $B_i$, se $S=1$ passa $\overline{B_i}$ (complemento a 1). Lo stesso segnale $S$ è il riporto in ingresso del primo full adder, e fornisce il "+1". Il sommatore calcola quindi $A+B$ (con $S=0$) oppure $A+\overline B+1=A-B$ (con $S=1$). Per $n=4$: quattro XOR, quattro full adder in cascata.

Overflow

L'overflow (straripamento) si ha quando il risultato non sta nei bit disponibili: per esempio $1000+1000=10000$ con numeri a 4 bit. È un problema in ogni sistema con un numero di bit fissato; il sistema deve poterlo rilevare.

Numeri senza segno.

• Nella somma c'è overflow se il riporto in uscita dal bit più significativo vale 1.
• Nella sottrazione non può esserci overflow (il risultato non supera il minuendo); il riporto in uscita dell'addizionatore-sottrattore vale $C=1$ se $M\ge N$ (risultato corretto) e $C=0$ se $M<N$ (risultato da correggere con complemento e segno meno). Equivalente al "prestito" invertito.

Proprietà (overflow in complemento a 2). Somma e sottrazione di operandi di segno diverso non hanno mai overflow (il modulo non cresce). Si ha overflow solo se i due addendi (per la sottrazione: $A$ e $-B$) hanno lo stesso segno e il risultato ha segno opposto. In termini di riporti: c'è overflow se il riporto che entra nel bit di segno è diverso dal riporto che esce dal bit di segno: $$V=C_{in,\,MSB}\oplus C_{out,\,MSB}.$$

Esempio. A $4$ bit $5+4$: $0101+0100=1001$, riporto entrante nel segno $1$, uscente $0$, quindi $V=1$ (il risultato $1001$ sarebbe $-7$).

Perché: se i due positivi sommano oltre $2^{n-1}-1$, il riporto entra nel bit di segno (che diventa 1) ma non esce; se i due negativi scendono sotto $-2^{n-1}$, il riporto non entra ma esce. Con $V=1$ il risultato è errato.

Esempi a 8 bit (intervallo $-128\dots127$):

• $70+80$: $01000110+01010000=10010110$; riporto in ingresso al segno $1$, in uscita $0$ $\Rightarrow$ $V=1$: $150$ non sta, il risultato è letto come $-106$.
• $(-70)+(-80)$: $10111010+10110000=(1)\,01101010$; riporto in ingresso $0$, in uscita $1$ $\Rightarrow$ $V=1$: $-150$ non sta, letto come $+106$.
• $100+27=127$: $01100100+00011011=01111111$, riporti $0$ e $0$ $\Rightarrow V=0$ (al limite, ma corretto).
• $(-100)+(-28)=-128$: $10011100+11100100=(1)\,10000000$, riporti $1$ e $1$ $\Rightarrow V=0$ (corretto).

Esercizi di riferimento (numeri in complemento a 2, MSB = segno):

• (a) $110001+011101$ (6 bit: $-15+29$): somma $001110$, riporto in ingresso al segno $1$, in uscita $1$ $\Rightarrow$ nessun overflow; risultato $+14$ ✓.
• (b) $0110111+0101111$ (7 bit: $+55+47$): somma $1100110$; riporto in ingresso al segno $1$, in uscita $0$ $\Rightarrow$ overflow ($102>63$).
• (c) $00000111-11110100$ ($+7-(-12)$): $00000111+00001100=00010011$ $\Rightarrow$ nessun overflow, $+19$.
• (d) $0110111-0101111$ ($+55-47$, 7 bit): complemento a 2 del sottraendo $1010001$; $0110111+1010001=(1)\,0001000$; riporti $1$ e $1$ $\Rightarrow$ nessun overflow; $+8$ (il riporto in uscita si scarta).

VHDL

Con il package numeric_std il tipo signed rappresenta numeri in complemento a 2:

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

entity add_signed is
  port ( a, b : in  std_logic_vector(7 downto 0);
         s    : out std_logic_vector(7 downto 0);
         v    : out std_logic );                    -- overflow
end add_signed;

architecture beh of add_signed is
  signal sum : std_logic_vector(7 downto 0);
begin
  sum <= std_logic_vector(signed(a) + signed(b));
  s   <= sum;
  v   <= (a(7) xnor b(7)) and (a(7) xor sum(7));    -- stesso segno in ingresso, segno diverso in uscita
end beh;

Il package fa interpretare i vettori come numeri con segno; con un package come std_logic_unsigned gli stessi vettori sarebbero senza segno (Introduzione al VHDL - entity, architecture, tipi e livelli di descrizioneVHDL è un linguaggio di descrizione dell'hardware (HDL), non di programmazione: le dichiarazioni sono concorrenti e descrivono blocchi di circuito; serve per documentare, simulare e sintetizzare. Un blocco ha una entity (nome e porte in/out) e almeno una architecture (cosa c'è dentro: structural con component e port map, dataflow con equazioni booleane, behavioral con comportamento). Tipi: std_logic (da 1164: '0','1','X','Z','U','-',...), std_logic_vector, bit, boolean, integer. Signal per i collegamenti interni, constant per i valori fissi.Introduzione al VHDL - entity, architecture, tipi e livelli di descrizione →).

Errori comuni

• Dire che in complemento a 2 il riporto in uscita indica overflow: per i numeri con segno conta il confronto tra il riporto entrante e quello uscente dal bit di segno.
• Calcolare il complemento a 2 invertendo i bit senza sommare 1.
• Credere che $-(-2^{n-1})$ sia rappresentabile: l'intervallo è asimmetrico.
• Usare l'estensione con zeri (anziché replicare il segno) su un numero negativo.
• Scrivere $-13$ a 8 bit come $10001101$ (è segno e modulo): in complemento a 2 è $11110011$.
• Segno del risultato nella sottrazione senza segno: se c'è prestito va corretto con complemento e segno meno.