Algoritme de Booth

El algoritme de multiplicació de Booth és un algoritme de multiplicació que multiplica dos número binario en signe en la notació de complement a dos. L'algoritme va ser inventat per Andrew Donald Booth i la seua esposa Kathleen Booth en 1950 mentres feyen investigació sobre cristalografia en l'Universitat de Bloomsbury, en Birkbeck, Londres. Booth usava calculadores d'escritori que eren més ràpides en el desplaçament que sumant, i va crear l'algoritme per a aumentar la seua velocitat. L'algoritme de Booth és d'interés en l'estudi de l'arquitectura de computadores.

L'algoritme

L'algoritme de Booth examina parells adjacents de bits del multiplicador I de N-bits en la representació de complement a dos en signe, incloent un bit implícit baix del bit menys significatiu, i_-1 = 0. Per a cada bit i_i, per a i corrent des de 0 fins a N-1, els bits i_i i i_i-1 són considerats. Quan estos dos bits són iguals, l'acumulador del producte P es deixa sense canvis. Quan i_i = 0 i i_i-1 = 1, el multiplicant multiplicat per 2ⁱ és agregat a P; i quan i_i = 1 i i_i-1 = 0, el multiplicant multiplicat per 2ⁱ és restat de P. El valor final de P és el producte en signe.

La representació del multiplicant i del producte no són especificades; típicament, estos també estan abdós en la representació de complement dos, com el multiplicador, pero qualsevol sistema de numeració que soporte l'adició i la substracción treballarà igual de be. Segons lo indicat ací, l'orde dels passos no està determinat. Típicament, procedix des del bit menys significatiu (LSB) al bit més significatiu (MSB), començant en i = 0; la multiplicació per 2ⁱ és llavors típicament reemplaçat pel desplaçament (shifting) incremental de l'acumulador P a la dreta entre els passos; els bits baixos poden ser desplaçats cap a fòra, i les adició i substracciones subsecuentes llavors poden ser fetes just en els N bits més alts de P. Hi ha moltes variacions i optimisacions sobre estos detalls.

L'algoritme és a sovint descrit com convertir seqüències de 1s en el multiplicador en un +1 d'orde alt i un -1 d'orde inferior en els extrems de la seqüència. Quan una seqüència corre per el MSB, no hi ha +1 d'orde alt, i l'efecte net és l'interpretació com un negatiu de valor apropiat.

Procediment

Siguen dos números, multiplicant i multiplicador, en llongituts en bits, x per al primer, i I per al segon:

• Es construïx una matriu de tres files i x+i+1 columnes. S'identifica les files com, A la primera, S la segona i P la tercera.

• S'inicien els x primers bits de cada fila en:
  • A, el multiplicant.
  • S, el complement a dos del multiplicant.
  • P, zeros.

• Els següents i bits es completen en:
  • A, zeros.
  • S, zeros.
  • P, el multiplicador.

• Per a finalisar la matriu, s'inicien a 0 tots els valors de l'última columna.

Una volta iniciada esta matriu, es realisa l'algoritme.

• Es realisen i iteraciones del següent bucle.
  1. Es comparen els dos bits menys significatius de P, per a realisar la següent acció:
     • 00 o 11: no es fa res.
     • 01: P = P + A. S'ignora el desbordament (overflow).
     • 10: P = P + S. S'ignora el desbordament.
  2. Desplaçament aritmètic de P a la dreta (es conserva el bit de signe).

• Finalment, despuix de i iteraciones, s'elimina (per mig d'un desplaçament) l'últim bit de la dreta (menys significatiu), obtenint el resultat.

Vore també

• Algoritme de multiplicació