Algorisme de Booth

L'algorisme de multiplicació de Booth és un algorisme de multiplicació que multiplica dos nombres binaris amb signe en la notació complement a dos. L'algorisme va ser inventat per Andrew Donald Booth el 1950 mentre feia recerca sobre cristal·lografia a la Universitat de Bloomsbury, a Birkbeck, Londres. Booth usava calculadores d'escriptori que eren més ràpides al desplaçament que sumant, i va crear l'algoritme per augmentar la seva velocitat. L'algorisme de Booth és d'interès en l'estudi de l'arquitectura de computadors.

L'algorisme

L'algorisme de Booth examina parells adjacents de bits del multiplicador I deN-bits en la representació de complement a dos amb signe, incloent un bit implícit sota del bit menys significatiu, y _-1 = 0. Per a cada bit y _i, per i corrent des de 0 fins a N-1, els bits y _i i y_i-1 són considerats. Quan aquests dos bits són iguals, l'acumulador del producte P és deixat sense canvis. Quan y _i = 0 iy _i-1 = 1, el multiplicant multiplicat per 2 ⁱ és agregat a P, i quan y _i = 1 i y _i-1 = 0, el multiplicant multiplicat per 2 ⁱ és restat de P. El valor final de P és el producte amb signe.

La representació del multiplicant i del producte no són especificades, típicament, aquests també estan tots dos a la representació de complement a dos, com el multiplicador, però qualsevol sistema de numeració que suporti l'addició i la sostracció treballarà igual de bé. Segons el que indica aquí, l'ordre dels passos no està determinat. Típicament, procedeix 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, i els bits baixos poden ser desplaçats cap a fora, i les addicions i substracciones subsegüents llavors poden ser fetes just en els N bits més alts de P. Hi ha moltes variacions i optimitzacions sobre aquests detalls.

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

Procediment

Suposem dos nombres, multiplicant i multiplicador, amb longituds a bits, x per al primer, i y per al segon:

• Construïm una matriu de tres files i x+ y+1 columnes. Identificarem les files com, A la primera, S la segona i P la tercera.

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

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

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

Un cop iniciada aquesta matriu, es realitza l'algorisme.

• Es realitzen i iteracions del següent bucle.
• # Comparar els dos bits menys significatius de P, per realitzar 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.
• # Desplaçament aritmètic de P a la dreta (es conserva el bit de signe).

• Finalment, després i iteracions, s'elimina l'últim bit de la dreta (menys significatiu), obtenint el resultat.

Exemple algorisme Multiplicador de Booth de 4 bits en VHDL

LIBRARY ieee;
USE ieee.std_logic_1164.all;
USE ieee.numeric_std.all;
ENTITY BoothMult4 IS PORT (
 A: IN STD_LOGIC_VECTOR(3 DOWNTO 0); 
 B: IN STD_LOGIC_VECTOR(3 DOWNTO 0);
 O: OUT STD_LOGIC_VECTOR(7 DOWNTO 0)
);
END BoothMult4;
ARCHITECTURE boothMult4Arch OF BoothMult4 IS
BEGIN 
Algorisme:PROCESS(A, B) -- Cada cop que canviï o bé A o be B
 variable num: STD_LOGIC_VECTOR(8 DOWNTO 0);
 variable Y, Z: UNSIGNED(3 DOWNTO 0);
 variable i: INTEGER;
 BEGIN
 num := "000000000";
 Y := UNSIGNED(B);
 num(4 DOWNTO 1) := A; 
 FOR i IN 0 TO 3 LOOP -- Per a cadaun dels bits
 IF(num(1) = '1' AND num(0) = '0') THEN
 Z := UNSIGNED(num(8 DOWNTO 5));
 num(8 DOWNTO 5) := STD_LOGIC_VECTOR(Z - Y); --Resta 
 ELSIF(num(1) = '0' AND num(0) = '1') THEN
 Z := UNSIGNED(num(8 DOWNTO 5));
 num(8 DOWNTO 5) := STD_LOGIC_VECTOR(Z + Y); --Suma
 END IF;
 num(7 DOWNTO 0) := num(8 DOWNTO 1); -- Desplaçament
 END LOOP;
 O(7 DOWNTO 0) <= num(8 DOWNTO 1);
END PROCESS; 
END boothMult4Arch;

Vegeu també

• Algorisme de multiplicació

Enllaços externs

• Radix-4 Booth Encoding (anglès)
• Radix-8 Booth Encoding Arxivat 2007-09-27 a Wayback Machine. a A Formal Theory of RTL and Computer Arithmetic Arxivat 2007-09-27 a Wayback Machine. (anglès)
• Algorisme de Booth Arxivat 2012-04-29 a Wayback Machine. (anglès)
• Algorisme de Booth implementat en JavaScript (anglès)
• Implementació en Python (anglès)