L'algorisme de la cabina és un algorisme de multiplicació que ens permet multiplicar els dos nombres enters binaris amb signe en el complement a 2, respectivament. També s'utilitza per accelerar el rendiment del procés de multiplicació. També és molt eficient. Funciona amb els bits de cadena 0 del multiplicador que no requereix cap bit addicional només desplaçar els bits de cadena més a la dreta i una cadena d'1 en un pes de bit multiplicador 2^kal pes 2^mque es pot considerar com 2^{k+ 1}- 2^m .

A continuació es mostra la representació pictòrica de l'algoritme de la cabina:

En el diagrama de flux anterior, inicialment, AC i Q_{n + 1} els bits s'estableixen a 0 i el SC és un comptador de seqüències que representa el conjunt de bits totals n, que és igual al nombre de bits del multiplicador. N'hi ha BR que representen el multiplicar bits, i QR representa el bits multiplicadors . Després d'això, vam trobar dos bits del multiplicador com a Q_ni Q_{n + 1}, on Qn representa l'últim bit de QR, i Q_{n + 1}representa el bit incrementat de Qn en 1. Suposem que dos bits del multiplicador són iguals a 10; vol dir que hem de restar el multiplicador del producte parcial de l'acumulador AC i després realitzar l'operació de desplaçament aritmètic (ahr). Si els dos multiplicadors són iguals a 01, vol dir que hem de fer la suma del multiplicant al producte parcial de l'acumulador AC i després realitzar l'operació de desplaçament aritmètic ( Ashr ), inclòs Q_{n + 1} . L'operació de desplaçament aritmètic s'utilitza a l'algorisme de Booth per desplaçar els bits AC i QR cap a la dreta en un i es manté el bit de signe en AC sense canvis. I el comptador de seqüències es decrementa contínuament fins que es repeteix el bucle computacional, igual al nombre de bits (n).

Treballant l'algoritme de la cabina

1. Estableix els bits binaris Multiplicand i Multiplicador com a M i Q, respectivament.
2. Inicialment, establim AC i Q_{n + 1}registra el valor a 0.
3. SC representa el nombre de bits del multiplicador (Q) i és un comptador de seqüències que es decrementa contínuament fins a igualar el nombre de bits (n) o arribar a 0.
4. Un Qn representa l'últim bit de la Q i la Q_n+1mostra el bit incrementat de Qn en 1.
5. En cada cicle de l'algorisme de la cabina, Q_ni Q_{n + 1}els bits es comprovaran en els paràmetres següents de la següent manera:
   1. Quan dos bits Q_ni Q_{n + 1}són 00 o 11, simplement realitzem l'operació de desplaçament aritmètic a la dreta (ashr) al producte parcial AC. I els bits de Qn i Q_{n + 1}s'incrementa en 1 bit.
   2. Si els bits de Q_ni Q_{n + 1}Si es mostra a 01, els bits multiplicadors (M) s'afegiran a l'AC (registre de l'acumulador). Després d'això, realitzem l'operació de desplaçament correcta als bits AC i QR en 1.
   3. Si els bits de Q_ni Q_{n + 1}Si es mostra a 10, els bits multiplicadors (M) es restaran de l'AC (registre acumulador). Després d'això, realitzem l'operació de desplaçament correcta als bits AC i QR en 1.
6. L'operació funciona contínuament fins que arribem a n - 1 bit a l'algorisme de la cabina.
7. Els resultats dels bits binaris de multiplicació s'emmagatzemaran als registres AC i QR.

Hi ha dos mètodes utilitzats en l'algoritme de Booth:

negreta en css

1. RSC (Circular de desplaçament a la dreta)

Desplaça el bit més a la dreta del nombre binari i després s'afegeix al començament dels bits binaris.

2. RSA (Aritmètica de desplaçament a la dreta)

Afegeix els dos bits binaris i després desplaça el resultat cap a la dreta en una posició d'1 bit.

una matriu en java

Exemple : 0100 + 0110 => 1010, després d'afegir el nombre binari, desplaceu cada bit 1 cap a la dreta i poseu el primer bit de la resultant al començament del nou bit.

Exemple: Multipliqueu els dos nombres 7 i 3 utilitzant l'algorisme de multiplicació de Booth.

Anys . Aquí tenim dos nombres, 7 i 3. En primer lloc, hem de convertir 7 i 3 en nombres binaris com 7 = (0111) i 3 = (0011). Ara poseu 7 (en binari 0111) com a multiplicant (M) i 3 (en binari 0011) com a multiplicador (Q). I SC (Recompte de seqüències) representa el nombre de bits, i aquí tenim 4 bits, així que establiu el SC = 4. A més, mostra el nombre de cicles d'iteració dels algorismes de la cabina i després els cicles executats SC = SC - 1 vegada.

L'exemple numèric de l'algoritme de multiplicació de Booth és 7 x 3 = 21 i la representació binària de 21 és 10101. Aquí, obtenim la resultant en binari 00010101. Ara la convertim en decimal, com (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

ubuntu build essencial

Exemple: Multipliqueu els dos nombres 23 i -9 utilitzant l'algorisme de multiplicació de Booth.

Aquí, M = 23 = (010111) i Q = -9 = (110111)

Q_{n + 1} = 1, vol dir que la sortida és negativa.

Per tant, 23 * -9 = complement de 2 de 111100110001 => (00001100111)