El algoritmo
En la Wikipedia hay una explicación muy clara y detallada del algoritmo de Booth (https://es.wikipedia.org/wiki/Algoritmo_de_Booth). En este caso se ha asumido, por simplicidad, que ambos términos (multiplicando y multiplicador) tienen la misma cantidad de bits.
Partimos de dos números enteros X e Y, ambos de N bits:
1. Construimos una matriz de 3 filas y N+N+1 columnas. La primera fila la llamaremos A, la segunda S y la tercera P.
1.1. En los N bits más significativos de A metemos X, el resto de bits de A los ponemos a 0.
1.2. En los N bits más significativos de S metemos -X (complemento a 2 de X), el resto de bits de S los ponemos a 0.
1.3. En los N bits más significativos de P metemos 0s, a continuación metemos los N bits de Y y en el bit que queda (el menos significativo) metemos un 0.
2. Hacer N veces:
2.1. Si los dos bits menos significativos de P son 01, hacer P <- P + A, en caso de que sean 10, hacer P <- P + S, en caso de que sean 00 o 11, no hacer nada
2.2. Hacer un desplazamiento aritmético (incluyendo el signo) de P hacia la derecha.
3. El resultado de la multiplicación serán los bits N a 1 de P (ojo, el bit 0 de P no forma parte de la solución).
Se trata de un algoritmo muy sencillo y que debe ser implementado de forma secuencial.
El flujo de datos
A continuación puede verse de forma esquemática cómo sería el flujo de datos en el multiplicador.
El multiplexor MUXa permite seleccionar entre la operación “P + A” o “P + S”, mientras que el multiplexor MUXp permite seleccionar entre al desplazamiento aritmético hacia la derecha de P, la entrada (para cargar el valor inicial de P a partir del operando Y) y la salida del sumador.
La unidad de control del multiplicador
Para gobernar las señales de carga de los registros y las señales de selección de los multiplexores es necesario implementar una unidad de control. La unidad de control se implementará mediante una máquina de estados finita (FSM) formada por biestables D, lógica de estado siguiente y lógica de salida de tipo Moore.
En este caso la máquina de estados que implementaría el algoritmo de Booth sería la siguiente:
Supongamos que se quiere multiplicar -3 por 2 utilizando una mantisa de 5 bits. En este caso:
-3 dec = 11101 bin
2 dec = 00010 bin
- Estado 0.
- Estado 1: MUXp=Y, Resetear el contador.
- Estado 2: Cargar A, Cargar S, Cargar P (se carga Y), Avanzar el contador.
- Estado 3.
Estando en el estado 3 los dos bits menos significativos de P valen en este momento “00” (P1=P0)y el contador no ha terminado (Ct=0), por lo que se va a estado 8.
- Estado 8: MUXp = SRA(P) (desplazamiento aritmético a la derecha de P un bit).
- Estado 9: MUXp = SRA(P), Cargar P (P <- SRA(P)).
- Estado 10: Avanzar el contador.
- Estado 3.
Estando en el estado 3 los dos bits menos significativos de P valen en este momento “10” (P1=1 y P0=0) y el contador no ha terminado (Ct=0), por lo que se va de nuevo al estado 6.
- Estado 6: MUXp = Sumador, MUXa = A.
- Estado 7: MUXp = Sumador, MUXa = A, Cargar P (P <- P + A)
- ...
Y así sucesivamente. Como se puede ver en el grafo de la FSM la multiplicación termina cuando, estando en el estado 3, el contador llega al final:
- ...
- Estado 3: Si el contador ha terminado pasamos al estado 11.
- Estado 11: Cargar Out (Out <- P).
- Estado 0 (se vuelve a empezar).
- ...
El el siguiente diagrama puede verse cómo quedaría todo el conjunto (registros, multiplexores, sumador y unidad de control) con lo que serían las entradas y salidas finales del multiplicador.
Implementación en VHDL
Para implementar en VHDL el FSM de la unidad de control basta con traducir el FSM a un modelo RTL: se traducen los arcos del grafo a lógica de estado siguiente y las salidas indicadas en los nodos del grafo a lógica de salida.
library ieee; use ieee.std_logic_1164.all; entity MultiplierControlUnit is generic ( NBits : integer := 4 ); port ( Clock : in std_logic; Reset : in std_logic; P1 : in std_logic; P0 : in std_logic; LoadA : out std_logic; LoadS : out std_logic; LoadP : out std_logic; LoadOut : out std_logic; AdderMuxSel : out std_logic; PMuxSel : out std_logic_vector(1 downto 0) ); end MultiplierControlUnit; architecture Architecture1 of MultiplierControlUnit is component Counter generic ( NBits : integer := 4; Limit : integer := 3 ); port ( Reset : in std_logic; Clock : in std_logic; Terminated : out std_logic ); end component; signal DBus : std_logic_vector(3 downto 0); signal QBus : std_logic_vector(3 downto 0); signal CounterReset : std_logic; signal CounterClock : std_logic; signal CounterTerminated : std_logic; begin -- counter for shift loop C : Counter generic map ( NBits => 8, Limit => NBits ) port map ( Reset => CounterReset, Clock => CounterClock, Terminated => CounterTerminated ); -- D flip-flop with synchronous reset for FSM process (Clock, Reset) begin if (Clock'event and (Clock = '1')) then if (Reset = '1') then QBus <= (others => '0'); else QBus <= DBus; end if; end if; end process; -- next state logic DBus <= "0001" when (QBus = "0000") else "0010" when (QBus = "0001") else "0011" when ((QBus = "0010") or (QBus = "1010")) else "0100" when ((QBus = "0011") and (P1 = '1') and (P0 = '0') and (CounterTerminated = '0')) else "0101" when (QBus = "0100") else "0110" when ((QBus = "0011") and (P1 = '0') and (P0 = '1') and (CounterTerminated = '0')) else "0111" when (QBus = "0110") else "1000" when ((QBus = "0101") or (QBus = "0111") or ((QBus = "0011") and (P1 = P0) and (CounterTerminated = '0'))) else "1001" when (QBus = "1000") else "1010" when (QBus = "1001") else "1011" when ((QBus = "0011") and (CounterTerminated = '1')) else "0000"; -- output logic LoadA <= '1' when (QBus = "0010") else '0'; LoadS <= '1' when (QBus = "0010") else '0'; LoadP <= '1' when ((QBus = "0010") or (QBus = "0101") or (QBus = "0111") or (QBus = "1001")) else '0'; LoadOut <= '1' when (QBus = "1011") else '0'; PMuxSel <= "01" when ((QBus = "0001") or (QBus = "0010")) else -- Y "10" when ((QBus = "0100") or (QBus = "0101") or (QBus = "0110") or (QBus = "0111")) else -- + "00" when ((QBus = "1000") or (QBus = "1001")) else "11"; AdderMuxSel <= '0' when ((QBus = "0110") or (QBus = "0111")) else -- A '1' when ((QBus = "0100") or (QBus = "0101")) else -- S '0'; CounterReset <= '1' when ((QBus = "0001") or (QBus = "0010")) else '0'; CounterClock <= '1' when ((QBus = "0010") or (QBus = "1010")) else '0'; end Architecture1;
La unidad de control incluye un contador interno (el componente instanciado como C) encargado de controlar la cantidad de veces que itera el bucle del algoritmo. En el caso del algoritmo de Booth el bucle itera tantas veces como bits tiene la mantisa (al instanciar el contador C hacemos Limit => NBits).
Como puede apreciarse, se trata de un diseño totalmente basado en modelos RTL (https://en.wikipedia.org/wiki/Register-transfer_level) por lo que su implementación es relativamente sencilla y el código generado siempre es sintetizable.
Todo el código fuente se puede descargar de la sección soft.
[ añadir comentario ] ( 1681 visualizaciones ) | [ 0 trackbacks ] | enlace permanente |
( 3 / 2801 )
Calendario
