Esercizio 5algoritmo di Booth (temi d'esame gennaio 2021, gennaio 2022, gennaio 2023 e gennaio 2026)

---

Teoria usata: 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 →, Numeri binari e complemento a dueI processori lavorano con un numero fisso di bit $n$. I naturali vanno da $0$ a $2^n-1$; per i negativi si usa il complemento a due: $C_2(N)=2^n-N=\overline N+1$ (si invertono tutti i bit e si somma 1). Con $n$ bit rappresenta $-2^{n-1}\le N\le2^{n-1}-1$, ha un solo zero e unifica somma e sottrazione. Quando il risultato esce dall'intervallo c'è overflow; gli overflow intermedi si compensano se il risultato finale è rappresentabile. La lunghezza di parola non è l'accuratezza.Numeri binari e complemento a due →.

Schema di lavoro

Registri $A$ (5 bit, parte alta del prodotto, all'inizio 0), $Q$ (5 bit, moltiplicatore), bit $q_{-1}=0$ e moltiplicando $M$. A ogni passo si guarda la coppia $Q_0q_{-1}$: 10 → $A\leftarrow A-M$; 01 → $A\leftarrow A+M$; 00 o 11 → nulla; poi shift aritmetico a destra di $A\,Q\,q_{-1}$. Dopo 5 passi $A\,Q$ (10 bit) è il prodotto in complemento a 2. Per ogni prodotto si assume il primo fattore come moltiplicando e il secondo come moltiplicatore (la scelta inversa dà prodotti parziali diversi ma lo stesso risultato).

I valori: $\texttt{0x1C}=11100=-4$, $\texttt{0x12}=10010=-14$, $\texttt{0x1A}=11010=-6$, $\texttt{0x1B}=11011=-5$, $\texttt{0x05}=00101=5$, $10001=-15$, $10110=-10$.

(a) $(-4)\cdot(-14)$: $M=11100$, $Q=10010$

Risultato $0000111000_2=\mathbf{56}$ ✓ ($(-4)(-14)=56$).

(b) $(-6)\cdot(-5)$: $M=11010$, $Q=11011$

Risultato $0000011110_2=\mathbf{30}$ ✓.

(c) $5\cdot(-6)$, con $M=\texttt{0x1A}=11010$ e $Q=\texttt{0x05}=00101$

Risultato $1111100010_2=-30$ ✓ (in complemento a 2 su 10 bit: $1024-30=994=1111100010$). Qui il moltiplicatore $00101$ ha 4 transizioni, quindi sono necessarie 4 somme/sottrazioni: la sequenza alternata non è favorevole a Booth.

(d) $(-15)\cdot(-10)$: $M=10001$, $Q=10110$

Risultato $0010010110_2=\mathbf{150}$ ✓ ($=128+16+4+2$). Il prodotto $150$ non entrerebbe in 8 bit con segno ($>127$) ma entra nei $2n=10$ bit.

Errori comuni

• Non scorrere a destra quando l'azione è "nulla".
• Shift logico invece di aritmetico: a $A=11110$ lo shift logico darebbe $01111$ invece di $11111$.
• Sottrarre quando la coppia è 01: 10 sottrae, 01 somma.
• Dimenticare i bit scartati dalla somma oltre il bit più alto (il riporto uscente da $A$ non va conservato).
• Leggere il risultato su 5 bit invece che su 10.