Moltiplicazione e algoritmo di Booth

** 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}$. -->

La moltiplicazione è hardware in tutti i DSP e, oggi, in molti µC (quelli per il controllo real-time di processi veloci, come gli azionamenti elettrici). Se non servono prestazioni elevate la moltiplicazione può essere sintetizzata con un sottoprogramma di somme e scorrimenti. In ogni caso il principio è il calcolo manuale (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 →).

Moltiplicazione senza segno

A mano: $1101\cdot101$: si scrive il moltiplicandoil numero che viene sommato (spostato) nel calcolo del prodotto $1101$ per il bit 0 (che vale 1), si scrive $0$ per il bit 1 spostato di 1 posto, di nuovo $1101$ spostato di 2 posti e si sommano: $1000001=65$. Il circuito segue tre miglioramenti successivi:

1. si sommano i prodotti parziali man mano (senza memorizzarli): si somma il moltiplicando al risultato corrente solo se il bit corrente del moltiplicatoreil numero i cui bit decidono quali somme eseguire è 1;
2. invece di spostare a sinistra il moltiplicando (servirebbe un sommatorecircuito che somma due parole binarie a $2n$ bit), si sposta a destra il risultato corrente e si somma solo sulla metà alta: bastano $n$ bit di sommatore;
3. il moltiplicatore $Mt$ si ospita nella metà bassa del registro $P$ del prodotto: il controllo guarda il bit meno significativo di $P$ e ogni shift a destra di $P$ sposta anche $Mt$.

Esempio con $Md=1101$ (13) e $Mt=0101$ (5), $n=4$. Si parte da $P=0000\,0101$:

• bit 1 (LSBbit meno significativo=1): $P_{alto}=0000+1101=1101$; shift: $0110\,1010$;
• bit 0: nulla; shift: $0011\,0101$;
• bit 1: $P_{alto}=0011+1101=10000\to0000$ (con il riportobit che passa alla colonna successiva quando la somma supera la cifra massima $1$ che finisce nel bit più alto: si ottiene $1\,0000$ e dopo lo shift $1000\,0010$);
• bit 0: nulla; shift: $0100\,0001=65$ ✓. Il riporto della somma sulla metà alta si conserva nel bit più alto dopo lo shift (qui la parte alta è un naturale senza segnonumero naturale, tutti i bit sono di valore).

Perché non basta per i numeri con segno

L'organizzazione precedente non si estende ai numeri in complemento a 2codifica dei numeri con segno: il bit di segno del moltiplicatore ha peso negativo ($-2^{n-1}$) e quello del moltiplicando va esteso nel prodotto parzialesomma delle righe del prodotto calcolate fino a quel passo. Serve un algoritmo apposito: quello di Booth.

L'algoritmo di Booth

Idea. Il moltiplicatore si fattorizzascompone in una somma o differenza di potenze di 2 in somme e differenze di potenze di 2, così che il prodotto sia una serie di shift con una sottrazione finale: $-5\cdot12=5\cdot(4-16)=5\cdot4-5\cdot16$ (shift a sinistra di 2 e di 4 posti, e una sottrazione). Booth ha osservato che la fattorizzazione si automatizza leggendo i bit del moltiplicatore: una sequenza di unigruppo di bit consecutivi uguali a 1 nel moltiplicatore $0\,\underbrace{1\dots1}_k\,0$ vale $2^{j+k}-2^{j}$, quindi basta sottrarre all'inizio della sequenza e sommare alla fine. Il vantaggio (meno somme) si perde con moltiplicatori alternati (tipo $10101010$).

Registri. $A$ ($n$ bit, parte alta del prodotto, inizialmente 0), $Q$ ($n$ bit, contiene il moltiplicatore), un bit extra $q_{-1}$ (inizialmente 0) e il moltiplicando $M$ ($n$ bit). Per ognuno degli $n$ passi:

e poi shift aritmetico a destra della terna $(A,Q,q_{-1})$ di un posto (il bit di segno di $A$ si estende). Avvertenze:

• lo shift va fatto a ogni passo, anche quando non si somma;
• deve essere aritmetico (estensione del segnocopia del bit di segno nelle posizioni lasciate libere dallo shift);
• nella somma o sottrazione su $A$ si trascurano i riporti oltre il bit più significativo;
• il bit "precedente" il bit meno significativo del moltiplicatore è considerato 0 all'inizio. Dopo gli $n$ passi, la concatenazione $A\,Q$ (di $2n$ bit) è il prodotto in complemento a 2, qualunque sia il segno degli operandi. L'hardware è poco più complesso di quello del moltiplicatore senza segno: cambia solo la logica di controllo.

Esempio 1: $5\cdot(-3)$ su 4 bit

$M=0101$ (5), $Q=1101$ ($-3$), $A=0000$, $q_{-1}=0$.

Risultato $11110001_2=-15$ ✓.

Esempio 2 (tema d'esame): $(\texttt{0x1A})\cdot(\texttt{0x1B})$ su 5 bit

$\texttt{0x1A}=11010=-6$ (moltiplicando $M$), $\texttt{0x1B}=11011=-5$ (moltiplicatore $Q$). Prodotto atteso $30$, che sta nei $2n=10$ bit.

Risultato $0000011110_2=30$ ✓ (si ritrova, nella metà bassa, la sequenza dei bit del moltiplicatore che man mano escono). Scambiando i ruoli ($M=11011$, $Q=11010$) le righe cambiano ma il prodotto è lo stesso: nel compito si indica sempre quale operando si usa come moltiplicatore (di solito quello che dà meno somme).

Esempio 3: operandi di segno diverso, $(\texttt{0x1A})\cdot(\texttt{0x05})$ su 5 bit

$M=11010$ ($-6$), $Q=00101$ ($+5$). Le righe dopo ogni shift sono $00011\,00010$, $11110\,10001$, $00010\,01000$, $11110\,00100$, $11111\,00010$. Il risultato finale $1111100010_2=-30$ ✓ (in complemento a 2 su 10 bit: $1024-30$).

Errori comuni

• Non shiftare quando l'azione è "nessuna".
• Shift logico invece che aritmetico (quando $A$ è negativo si perde il segno).
• Sbagliare il verso della coppia: $10$ è sottrazione, $01$ è somma.
• Non portare il bit precedenteil bit meno significativo scartato nello shift precedente, che per il primo passo vale 0 $q_{-1}=0$ all'inizio.
• Leggere il risultato su $n$ bit invece che su $2n$ bit.
• Dimenticare di scrivere il prodotto parziale dopo lo shift quando il testo lo chiede.