L'algoritmo di Booth è un algoritmo di moltiplicazione che permette di moltiplicare rispettivamente due interi binari con segno in complemento a 2. Viene utilizzato anche per accelerare l'esecuzione del processo di moltiplicazione. È anche molto efficiente. Funziona sui bit di stringa 0 nel moltiplicatore che non richiede bit aggiuntivi, sposta solo i bit di stringa più a destra e una stringa di 1 in un bit di peso moltiplicatore 2^Kpesare 2^Mche può essere considerato come 2^k+1- 2^M .

Di seguito è riportata la rappresentazione pittorica dell'algoritmo di Booth:

Nel diagramma di flusso sopra, inizialmente, AC E Q_n+1 i bit sono impostati su 0 e il SC è un contatore di sequenza che rappresenta il totale dei bit impostati N, che è uguale al numero di bit nel moltiplicatore. Ci sono BR che rappresentano il bit moltiplicando, e QR rappresenta il bit moltiplicatori . Successivamente, abbiamo riscontrato due bit del moltiplicatore come Q_Ne Q_n+1, dove Qn rappresenta l'ultimo bit di QR, e Q_n+1rappresenta il bit incrementato di Qn di 1. Supponiamo che due bit del moltiplicatore siano pari a 10; significa che dobbiamo sottrarre il moltiplicatore dal prodotto parziale nell'accumulatore AC e quindi eseguire l'operazione di spostamento aritmetico (ashr). Se i due moltiplicatori sono uguali a 01, significa che dobbiamo eseguire l'addizione del moltiplicando al prodotto parziale nell'accumulatore AC e quindi eseguire l'operazione di spostamento aritmetico ( Ashr ), Compreso Q_n+1 . L'operazione di spostamento aritmetico viene utilizzata nell'algoritmo di Booth per spostare i bit AC e QR verso destra di uno e mantiene invariato il bit di segno in AC. E il contatore di sequenza viene continuamente decrementato finché il ciclo di calcolo non viene ripetuto, pari al numero di bit (n).

Lavorando sull'algoritmo Booth

1. Impostare i bit binari del Moltiplicando e del Moltiplicatore rispettivamente come M e Q.
2. Inizialmente impostiamo AC e Q_n+1registra il valore su 0.
3. SC rappresenta il numero di bit del moltiplicatore (Q), ed è un contatore di sequenza che viene continuamente decrementato fino a raggiungere il numero di bit (n) o raggiungere 0.
4. Una Qn rappresenta l'ultimo bit della Q e della Q_n+1mostra il bit di Qn incrementato di 1.
5. Ad ogni ciclo dell'algoritmo della cabina, Q_Ne Q_n+1i bit verranno controllati sui seguenti parametri come segue:
   1. Quando due bit Q_Ne Q_n+1sono 00 o 11, eseguiamo semplicemente l'operazione di spostamento aritmetico a destra (ashr) fino al prodotto parziale AC. E i pezzi di Qn e Q_n+1viene incrementato di 1 bit.
   2. Se i pezzi di Q_Ne Q_n+1viene visualizzato su 01, i bit del moltiplicando (M) verranno aggiunti all'AC (registro dell'accumulatore). Successivamente, eseguiamo l'operazione di spostamento a destra sui bit AC e QR di 1.
   3. Se i pezzi di Q_Ne Q_n+1Se viene riportato a 10, i bit del moltiplicando (M) verranno sottratti dall'AC (registro dell'accumulatore). Successivamente, eseguiamo l'operazione di spostamento a destra sui bit AC e QR di 1.
6. L'operazione funziona continuamente finché non raggiungiamo n - 1 bit nell'algoritmo della cabina.
7. I risultati dei bit binari della moltiplicazione verranno memorizzati nei registri AC e QR.

Esistono due metodi utilizzati nell'algoritmo di Booth:

sistema operativo Linux

1. RSC (circolare spostamento a destra)

Sposta il bit più a destra del numero binario e quindi viene aggiunto all'inizio dei bit binari.

2. RSA (aritmetica dello spostamento a destra)

Aggiunge i due bit binari e quindi sposta il risultato a destra della posizione di 1 bit.

barrato il ribasso

Esempio : 0100 + 0110 => 1010, dopo aver aggiunto il numero binario sposta ogni bit di 1 a destra e metti il ​​primo bit della risultante all'inizio del nuovo bit.

Esempio: moltiplica i due numeri 7 e 3 utilizzando l'algoritmo di moltiplicazione di Booth.

Anni . Qui abbiamo due numeri, 7 e 3. Prima di tutto dobbiamo convertire 7 e 3 in numeri binari come 7 = (0111) e 3 = (0011). Ora imposta 7 (in binario 0111) come moltiplicando (M) e 3 (in binario 0011) come moltiplicatore (Q). E SC (Sequence Count) rappresenta il numero di bit, e qui abbiamo 4 bit, quindi imposta SC = 4. Inoltre, mostra il numero di cicli di iterazione degli algoritmi di Booth e quindi i cicli vengono eseguiti SC = SC - 1 volta.

L'esempio numerico dell'algoritmo di moltiplicazione di Booth è 7 x 3 = 21 e la rappresentazione binaria di 21 è 10101. Qui otteniamo il risultante in binario 00010101. Ora lo convertiamo in decimale, come (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

tipi di riferimento Java

Esempio: moltiplica i due numeri 23 e -9 utilizzando l'algoritmo di moltiplicazione di Booth.

Qui, M = 23 = (010111) e Q = -9 = (110111)

Q_n+1 = 1, significa che l'uscita è negativa.

Quindi, 23 * -9 = complemento a 2 di 111100110001 => (00001100111)