Moltiplicatori veloci e divisione

Le realizzazioni a somme e shift (Moltiplicazione e algoritmo di BoothLa moltiplicazione hardware imita il calcolo a mano: somme e shift ripetuti. Per numeri senza segno si somma il moltiplicando se il bit del moltiplicatore è 1 e si fa shift a destra del prodotto parziale; il moltiplicatore sta nella metà bassa del registro del prodotto. Per i numeri con segno serve l'algoritmo di Booth: si guardano i bit del moltiplicatore a coppie (bit corrente, bit precedente, all'inizio 0): 10 → si sottrae il moltiplicando, 01 → si somma, 00/11 → niente; poi shift aritmeticoscorrimento che conserva il segno: a destra ripete il bit di segno a destra. Dopo $n$ passi si hanno $2n$ bit in complemento a 2. Va eseguito sui compiti d'esame a mano con lo schema di registri $A,|,Q,|,q_{-1}$.Moltiplicazione e algoritmo di Booth →) richiedono molte iterazioni: troppo lente per il controllo real-time di processi dinamici o per il signal processing. Nei µC e DSP si trovano quindi moltiplicatori veloci, capaci di calcolare il prodotto in un solo ciclo di clock.

Moltiplicatori a look-up table

Una memoria look-up tablememoria in cui sono scritti, già calcolati, i valori di una funzione: si legge la risposta invece di calcolarla contiene i prodotti di tutte le coppie di numeri a $n$ bit (senza segno). L'indirizzo della cella si forma accostando i due operandi, quindi un moltiplicatore $n\times n$ richiede $2^{2n}$ righe di $2n$ bit. Per esempio $1101\cdot0110=01001110$ si legge alla riga di indirizzo $1101\,0110$.

La crescita è esponenziale: già con 8 bit servono 1 Mbit di memoria, inaccettabile per l'area sul chip. Si realizzano quindi solo moltiplicatori a pochi bit (4) e se ne combinano più copie per operandi più larghi, fattorizzandoscomponendo il prodotto in prodotti parziali più piccoli il prodotto. Con $A=A_H\cdot16+A_L$ e $B=B_H\cdot16+B_L$ (due nibble a 4 bit): $$A\cdot B=A_HB_H\cdot256+(A_HB_L+A_LB_H)\cdot16+A_LB_L .$$ Servono quattro moltiplicatori $4\times4$ e un addizionatore che allineaporta le uscite dei moltiplicatori parziali alla posizione corretta con shift le uscite.

Moltiplicatori a matrice

Il prodotto di due numeri a 1 bit è un AND. Generalizzando, il prodotto $A\cdot B$ a $n$ bit è la somma dei prodotti parziali $A\,b_j\,2^j$: una matrice di porte AND e una matrice di sommatoricircuiti che sommano due parole binarie, con struttura regolare e quindi facile da realizzare. Il prodotto è pronto dopo circa $2n$ ritardi elementariil ritardo di una porta logica, usato come unità di misura del tempo di propagazione (quelli dei sommatori; le AND si trascurano); con sommatori veloci (CLA, ALU - sommatore, overflow, carry look-ahead e shiftL'ALU è un insieme di celle a 1 bit (full adder + selettori) collegate in parallelo: somma, sottrae ($A-B=A+\overline B+1$: si inverte $B$ e si porta il riporto iniziale a 1), fa AND/OR. Il ritardo è dominato dal riporto: nel ripple-carry cresce linearmente con i bit; col carry look-aheadtecnica che calcola in anticipo i riporti da generazione e propagazione, riducendo il ritardo i riporti si calcolano da generazione $g_i=A_iB_i$ e propagazione $p_i=A_i+B_i$ in pochi livelli di logica. L'overflow è $V=C_{in,n-1}\oplus C_{out,n-1}$. Gli shift logici inseriscono 0, gli aritmetici estendono il segno; il barrel shiftercircuito che sposta una parola di un numero qualsiasi di posizioni in un solo ciclo sposta di $m$ posti in un ciclo.ALU - sommatore, overflow, carry look-ahead e shift →) il ritardo si riduce molto.

Altre organizzazioni:

• somma per colonne: una colonna della matrice dei prodotti parziali (le AND) entra in un encodercircuito che conta gli uni presenti nei suoi ingressi e li scrive in binario che genera il bit di prodotto e i riporti per le colonne a sinistra. Struttura irregolare, ritardo $\sim2n$.
• riduzione per passi della matrice dei prodotti parziali fino a due sole righe, poi un sommatore finale veloce: evita la propagazione dei riporti nella matrice.
• Wallacemoltiplicatore che riduce a passi la matrice dei prodotti parziali usando solo half adder e full adder: stessa idea, con soli sommatori parziali da 2 o 3 bit (half addersemisommatore: somma due bit senza riporto entrante e full adder): struttura più regolare, riduzione un po' più lenta, ritardo comunque dominato dal sommatore finale.

Divisione

La divisione è richiesta raramente nei µC e nei DSP; alcuni processori hanno l'istruzione, ma richiede molti cicli. L'algoritmo più comune opera su operandi positivi per sottrazioni successive e sistema il segno alla fine.

Algoritmo "con ripristino" (restoring). Il restoquello che rimane dopo aver sottratto il quoziente per il divisore $R$ parte uguale al dividendo; il divisore $D$ è allineato al bit più alto del dividendo. A ogni passo si calcola $R-D$: se il risultato è positivo o nullo il bit di quozienteil risultato intero di una divisione è 1 e $R$ resta ridotto; se negativo il bit è 0 e si ripristina $R$ (si risomma $D$). Poi $D$ si sposta di un posto a destra e si ripete. Esempio: $65:13$. $65=1000001_2$, $13=1101$ (allineato: $1101000$): $65-104<0$ → bit 0; con $D$ spostato ($110100$): $65-52=13\ge0$ → bit 1, $R=13$; $D=11010$ ($26$): $13-26<0$ → 0; $D=1101$ ($13$): $13-13=0$ → bit 1, $R=0$. Quoziente $0101=5$, resto $0$ ✓.

Versione con meno hardware. Si sposta a sinistra il dividendo (invece di spostare a destra il divisore) usando una ALU a $n$ bit invece di $2n$, e si ospita il quoziente nella metà bassa del registro del resto. Il primo passo è sempre uno shift a sinistra senza sottrazione (se la prima sottrazione desse $R\ge0$ il quoziente sarebbe troppo grande: è così che si riconosce una divisione non permessa, che genera errore). Ogni sottrazione che dà $R<0$ si ripristina; a fine algoritmo la parte alta di $R$ va spostata a destra di un posto (altrimenti il resto è shiftato una volta di troppo). Esempio $37:6=6$ resto $1$: ripercorrendo i passi (shift, sottrazione $R-D$ sulla parte alta, ripristinooperazione che risomma il divisore al resto quando la sottrazione ha dato un valore negativo se negativa) si arriva al quoziente $0110$ e al resto $0001$.

Vincoli con $n$ bit

Con aritmetica intera a $n$ bit con segno il quoziente e il resto stanno in $[0,2^{n-1}-1]$. Con 5 bit sono compresi tra 0 e 15 e il massimo dividendo è $15\cdot15+14=239$: l'unico divisore valido è 15 (quoziente 15, resto 14); un divisore minore darebbe quoziente non rappresentabile. Il dividendo $65$ ammette i divisori da $5$ ($65:5=13$) a $15$ ($65:15=4$ resto 5); con $4$ il quoziente sarebbe $16$, non rappresentabile. Per riportare un dividendo all'interno del campo ammesso si premoltiplica per una potenza di 2 (si parla di fattore di scala del dividendo, ricordando poi di riportare il quoziente alla scala originale).

Il segno

Il segno si gestisce alla fine imponendo $$\text{dividendo}=Q\cdot D+R .$$ Per esempio $-13:4=-3$ con resto $-1$ (e non $-4$ con resto $+3$, che soddisfa la relazione ma non la convenzione): deve essere $-(x/y)=(-x)/y$, a meno del resto, cioè il quoziente si arrotonda verso zero e il resto ha il segno del dividendo.

Divisione con il moltiplicatore

Se non c'è un divisore hardware si usa il moltiplicatore. Per $Q=N/D$ con $0{,}5<D<1$ (dopo avere scalato $D$ con una potenza di 2) si pone $Z=1-D$, quindi $D=1-Z$ e $0<Z<0{,}5$. Dalla identità $\frac1{1-Z}=\frac{(1+Z)(1+Z^2)(1+Z^4)\cdots(1+Z^{2^{n-1}})}{1-Z^{2^n}}$ segue $$Q=\frac{N(1+Z)(1+Z^2)\cdots(1+Z^{2^{n-1}})}{1-Z^{2^n}}\;\approx\;N(1+Z)(1+Z^2)\cdots(1+Z^{2^{n-1}}).$$ L'errore relativo dell'approssimazione è $Z^{2^n}$: decresce più che esponenzialmente con $n$. Con una aritmetica a 8 bit basta $n=3$ per avere un errore minore dell'LSB; con $n=5$ si ha la precisione di un'aritmetica a 32 bit. (Il caso generale è $Q=\frac{1}{D/N}$ con $D/N$ scalato in $(0{,}5,1)$: $Z=1-D/N$.)

Esempio numerico: $N=3$, $D=2{,}1$: $D/N=0{,}7$ e $Z=0{,}3$. Il valore vero è $Q=3/2{,}1=1{,}428571$. Con la serie: $n=1$: $1+Z=1{,}3$; $n=2$: $1{,}3\cdot1{,}09=1{,}417$; $n=3$: $1{,}417\cdot1{,}0081=1{,}42848$ (errore relativo $Z^8=6{,}6\cdot10^{-5}$); $n=4$: $1{,}428571$ (errore $Z^{16}=4{,}3\cdot10^{-9}$). Quindi per superare l'accuratezzavicinanza del risultato al valore vero di una rappresentazione a 16 bit ($\sim3\cdot10^{-5}$) servono 4 fattori.

Errori comuni

• Credere che la tabella look-upmemoria con le risposte già calcolate scali bene: cresce come $4^n$.
• Dimenticare il ripristino quando il resto parziale diventa negativo.
• Arrotondare il quoziente negativo "per difetto" invece che verso zero.
• Applicare la serie a un $D$ fuori dall'intervallo $(0{,}5,1)$ (la serie converge solo se $|Z|<1$ e rapidamente se $Z<0{,}5$).