Algoritmul de cabină este un algoritm de multiplicare care ne permite să înmulțim cele două numere întregi binare cu semn în complementul 2, respectiv. De asemenea, este folosit pentru a accelera performanța procesului de înmulțire. Este si foarte eficient. Funcționează pe șirurile de biți 0 din multiplicator care nu necesită nici un bit suplimentar, doar deplasarea biților din dreapta și un șir de 1 într-o greutate de biți de multiplicare 2^kla greutatea 2^mcare poate fi considerat ca 2^{k+ 1}- 2^m .

Mai jos este reprezentarea picturală a algoritmului Booth:

În schema de mai sus, inițial, AC și Q_{n + 1} biții sunt setați la 0 și SC este un numărător de secvențe care reprezintă totalul de biți setați n, care este egal cu numărul de biți din multiplicator. Sunt BR care reprezintă biți multiplicand, iar QR reprezintă biți multiplicatori . După aceea, am întâlnit doi biți ai multiplicatorului ca Q_nși Q_{n + 1}, unde Qn reprezintă ultimul bit al QR și Q_{n + 1}reprezintă bitul incrementat al lui Qn cu 1. Să presupunem că doi biți ai multiplicatorului sunt egali cu 10; înseamnă că trebuie să scădem multiplicatorul din produsul parțial din acumulatorul AC și apoi să efectuăm operația de schimbare aritmetică (ashr). Dacă cei doi multiplicatori sunt egali cu 01, înseamnă că trebuie să efectuăm adăugarea multiplicandului la produsul parțial din acumulatorul AC și apoi să efectuăm operația de schimbare aritmetică ( Ashr ), inclusiv Q_{n + 1} . Operația de schimbare aritmetică este utilizată în algoritmul lui Booth pentru a deplasa biții AC și QR la dreapta cu unul și rămâne neschimbat bitul de semn în AC. Și contorul de secvență este decrementat continuu până când bucla de calcul se repetă, egală cu numărul de biți (n).

Lucrul la algoritmul Booth

1. Setați biții binari Multiplicand și Multiplicator ca M și, respectiv, Q.
2. Inițial, am setat AC și Q_{n + 1}înregistrează valoarea la 0.
3. SC reprezintă numărul de biți de multiplicare (Q) și este un numărător de secvențe care este decrementat continuu până la egal cu numărul de biți (n) sau atins la 0.
4. Un Qn reprezintă ultimul bit al Q, iar Q_n+1arată bitul incrementat al lui Qn cu 1.
5. Pe fiecare ciclu al algoritmului de cabină, Q_nși Q_{n + 1}biții vor fi verificați pe următorii parametri, după cum urmează:
   1. Când doi biți Q_nși Q_{n + 1}sunt 00 sau 11, pur și simplu efectuăm operația de deplasare aritmetică la dreapta (ashr) la produsul parțial AC. Și biții Qn și Q_{n + 1}este incrementat cu 1 bit.
   2. Dacă biții din Q_nși Q_{n + 1}este afișat la 01, biții de multiplicare (M) vor fi adăugați la AC (registrul acumulatorului). După aceea, efectuăm operația de schimbare corectă la biții AC și QR cu 1.
   3. Dacă biții din Q_nși Q_{n + 1}se arată la 10, biții de multiplicare (M) vor fi scăzuți din AC (registrul acumulatorului). După aceea, efectuăm operația de schimbare corectă la biții AC și QR cu 1.
6. Operația funcționează continuu până când ajungem la n - 1 bit în algoritmul de cabină.
7. Rezultatele biților binari de multiplicare vor fi stocați în registrele AC și QR.

Există două metode utilizate în algoritmul lui Booth:

filigran în cuvânt

1. RSC (Circulară de schimbare la dreapta)

Deplasează bitul din dreapta al numărului binar și apoi este adăugat la începutul biților binari.

2. RSA (Right Shift Arithmetic)

Acesta adaugă cei doi biți binari și apoi deplasează rezultatul la dreapta cu poziția de 1 bit.

blocați reclamele youtube Android

Exemplu : 0100 + 0110 => 1010, după adăugarea numărului binar, deplasați fiecare bit cu 1 la dreapta și puneți primul bit de rezultantă la începutul noului bit.

Exemplu: Înmulțiți cele două numere 7 și 3 utilizând algoritmul de înmulțire al lui Booth.

Ani . Aici avem două numere, 7 și 3. În primul rând, trebuie să convertim 7 și 3 în numere binare precum 7 = (0111) și 3 = (0011). Acum setați 7 (în binar 0111) ca multiplicand (M) și 3 (în binar 0011) ca multiplicator (Q). Și SC (Sequence Count) reprezintă numărul de biți, iar aici avem 4 biți, deci setați SC = 4. De asemenea, arată numărul de cicluri de iterație ale algoritmilor cabinei și apoi ciclurile rulate SC = SC - 1 dată.

Exemplul numeric al algoritmului de înmulțire al lui Booth este 7 x 3 = 21 și reprezentarea binară a lui 21 este 10101. Aici, obținem rezultatul în binar 00010101. Acum o convertim în zecimal, ca (000010101)₁₀= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

10 din 50.00

Exemplu: Înmulțiți cele două numere 23 și -9 utilizând algoritmul de înmulțire al lui Booth.

Aici, M = 23 = (010111) și Q = -9 = (110111)

Q_{n + 1} = 1, înseamnă că ieșirea este negativă.

Prin urmare, 23 * -9 = complementul 2 al lui 111100110001 => (00001100111)