Aritmetica binaria

Note

È possibile rappresentare un numero in codifica binaria.

Formalmente per convertire da decimale a binario si usa il metodo delle divisioni successive, ed il metodo delle potenze per la conversione da binario a decimale.

Si ha che per $n$ bit si possono rappresentare fino $2^n$ simboli.

Esistono altri metodi per rappresentare i numeri binari oltre alla conversione binaria.

Base $2$ complemento a $2$

La notazione base 2 complemento a due permette la rappresentazione di numeri negativi, dove se il numero è positivo rimane uguale alla sua codifica binaria diretta, per ottenere però il negativo si effettua il complemento ad $1$ (invertire i bit) e il complemento a $2$ (sommare $1$).

Notiamo che il primo bit indicherà il segno, inoltre si usa il complemento a due poiché le operazioni in complemento a $2$ sono più facili da fare.

Con $n\text{ bit}$ l’intervallo di rappresentazione è $[-2^{n-1},2^{n-1}-1]$.

Dati gli operandi $A$ e $B$, il risultato $S$ ed il resto $C$, è possibile costruire una tabella di verità e quindi un circuito. Si ha che:

$$S=A\oplus BC=A\cdot B$$

Possiamo costruire quindi un circuito chiamato half-adder: Da questo ne possiamo costruirne un altro detto full-adder, che somma $3$ numeri $A,B,C_{\text{In}}$: Considerando un ritardo fisso di $1$ per porta logica il ritardo per l’half-adder è:

$$\begin{array}{r}T(S)=1\\ T(C)=1\end{array}$$

Mentre per il full-adder è:

$$\begin{array}{rl}& T(S)=2\\ & T(C_{\text{out}})=3\end{array}$$

Ponendo full-adder (dove il primo è un half-adder) in parallelo è possibile creare un sommatore a $n$ bit. Tuttavia questo approccio è abbastanza lento, si usa quindi un sommatore CLA.

Sommatore CLA

Nel sommatore Carry Look Ahead (CLA), si aggiunge un componente CLA che precalcola i valori dei riporti.

Si ha che:

$$C_{i+1}=\underset{G_i\text{ funzione generatrice}}{\underbrace{A_i\cdot B_i}}+\underset{P_i\text{ funzione propagazione}}{\underbrace{(A_i\oplus B_i)}}{C}_i$$

$G_i$ indica la necessità di un riporto, mentre $P_i$ indica quando va propagato. Se espandiamo questa formula notiamo che il riporto non dipende dai riporti precedenti, in quanto $C_0=0$. È quindi possibile costruire il CLA con una rete a 2 livelli.

Siccome calcolare le nostre $C_i$ richiede delle porte logiche di dimensioni enormi, fisicamente non prodotte, si introduce l’architettura del CLA a blocchi da $m$ block size, consideriamo $m=2$:

Questo ha tempo logaritmico.

Moltiplicatori

Note

L’operazione di moltiplicazione è molto più complessa della somma.

Esistono diversi moltiplicatori, diversi dalla moltiplicazione in colonna, questo perché essa non è efficiente. Per esempio, esiste il caso specifico $Y=A\cdot BB<0$, che dev’essere calcolato come:

$$Y=(-A)\cdot (-B)$$

Inoltre è necessario estendere il segno dei prodotti parziali.

Moltiplicatore parallelo

Consideriamo la cella moltiplicatrice: Disposte in questo modo possiamo creare un moltiplicatore: Dove ogni riga può essere vista come un sommatore. Questo approccio a ha ritardo lineare.

Moltiplicatore di Wallace

Secondo questo approccio, in primis si moltiplicano tutte le coppie di bit degli operandi, e poi le disponiamo nella matrice. L’idea è di sommare usando un half adder (verde nell’immagine) per le somme di $2\text{ bit}$, e full adder (giallo nell’immagine) per le somme di $3\text{ bit}$ Questo processo ci da una matrice computazionale con un livello in meno. Ripetendo questo processo ridurremo le somme al risultato.

Operandi negativi in complemento a due

Consideriamo due numeri $A$ e $B$ in complemento a due. Se consideriamo

$$\begin{array}{rl}A& =(-a_3)2^3+a_2{2}^2+a_1{2}^1+a_0\\ B& =(-b_3)2^3+b_2{2}^2+b_1{2}^1+b_0\end{array}$$

Notiamo che: Separiamo quindi la matrice computazionale in due matrici $P^{+}$ e $P^{-}$ per segno: $P^{+}$ e $P^{-}$ si sommano separatamente con i metodi visti precedentemente, e infine si calcola con un sommatore $P=P^{+}-P^{-}$, che sarà il nostro risultato corretto.

Esistono degli algoritmi per ottimizzare la moltiplicazione.

Algoritmo di Booth Radix2

Per l’algoritmo di Booth si aggiunge uno $0$ nella posizione meno significativa al moltiplicatore, e poi lo scomponiamo in coppie da due sovrapposte partendo da destra. Per esempio il numero $11011$ diventerà $11,10,01,11,10$

Sostituiamo poi queste coppie con la codifica:

Coppia moltiplicatore	Codifica
$00$	$0$
$01$	$1$
$10$	$-1$
$11$	$0$

Eseguiamo poi la moltiplicazione con la nuova codifica, stando attenti che la moltiplicazione per $-1$ si esegue il complemento a $2$ del numero.

Algoritmo di Booth Radix4

Funziona esattamente con la stessa logica, però si prendono gruppi sovrapposti da $3\text{ bit}$. Per esempio $00100110$ diventa $001,100,011,100$.

Si usa poi la codifica:

Tripletta modificatore	Codifica
$000$	$0$
$001$	$1$
$010$	$1$
$011$	$2$
$100$	$-2$
$101$	$-1$
$110$	$-1$
$111$	$0$

A questo punto si procede esattamente come prima. Si nota che la moltiplicazione per $2$ comporta uno shift a sinistra. Inoltre, bisogna lasciare due spazi nella matrice computazionale al posto di uno.