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 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 yi-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 i és agregat a P, i quan y i = 1 i y i-1 = 0, el multiplicant multiplicat per 2 i é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 i é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.[1] 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.
Suposem dos nombres, multiplicant i multiplicador, amb longituds a bits, x per al primer, i y per al segon:
Un cop iniciada aquesta matriu, es realitza l'algorisme.
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;