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 ] ( 1466 visualizaciones ) | [ 0 trackbacks ] | enlace permanente
Tweet | |
( 3 / 2559 )Las FPGAs y los CPLDs son circuitos integrados digitales programables a nivel hardware mediante algún tipo de lenguaje de descripción de hardware (VHDL, Verilog, SystemC, etc.). A lo largo de este post se desarrolla una primera toma de contacto con este tipo de integrados.
FPGA
La FPGA que se ha usado es una Xilinx Spartan 3E, que se puede encontrar en la placa Papilio One (http://papilio.cc). Esta placa es open hardware, con interface USB, memoria flash SPI para almacenar la configuración del hardware y con una buena relación calidad/precio (unos 38 dólares aproximadamente).
El entorno de desarrollo de Xilinx es un poco complejo (muchas opciones) pero se le coge el truco rápido. Es gratuito (aunque no es software libre) y muy fácil de instalar tanto en Windows como en Linux (no está para Mac). El entorno de desarrollo permite gestionar proyectos en VHDL o Verilog y generar al final los ficheros ".bit" que son los que se mandan a la FPGA.
De http://papilio.cc se descarga el Papilio Loader, un software open source que permite "tostar" los ficheros ".bit" en la placa FPGA y probar los diseños rápidamente. En la propia página del proyecto vienen varios tutoriales.
Prueba de concepto
Como prueba inicial se plantea un circuito conversor de binario (4 bits, del 0 al 9) a 7 segmentos mediante interfaz serie:
Se trata de un esquema muy sencillo: un registro de desplazamiento de 4 bits (que permite leer la entrada serie), un latch de 4 bits que carga el contenido del registro de desplazamiento y a la salida del latch una lógica combinatoria que convierte el número de 4 bits en una salida de 7 bits (para el display de 7 segmentos).
VHDL de la lógica combinatoria
VHDL es un lenguaje de descripción de hardware, no un lenguaje imperativo al uso. Cada línea de código describe un comportamiento y la única forma de realizar procesamiento secuencial es mediante la cláusula "process" ya que por defecto se ejecuta "todo a la vez".
Una lógica combinatoria está basada en puertas lógicas y las puertas lógicas se "ejecutan" siempre, no son como los biestables u otros elementos secuenciales. Para la lógica combinatoria de conversión binario a 7 segmentos se puede utilizar la sentencia WHEN...ELSE:
B(0) <= '1' when ((x = "0000") or (x = "0001") or (x = "0011") or (x = "0100") or (x = "0101") or (x = "0110") or (x = "0111") or (x = "1000") or (x = "1001")) else '0'; B(1) <= '1' when ((x = "0000") or (x = "0010") or (x = "0011") or (x = "0101") or (x = "0110") or (x = "1000") or (x = "1001")) else '0'; B(2) <= '1' when ((x = "0000") or (x = "0010") or (x = "0110") or (x = "1000")) else '0'; B(3) <= '1' when ((x = "0000") or (x = "0010") or (x = "0011") or (x = "0101") or (x = "0110") or (x = "0111") or (x = "1000") or (x = "1001")) else '0'; B(4) <= '1' when ((x = "0000") or (x = "0001") or (x = "0010") or (x = "0011") or (x = "0100") or (x = "0111") or (x = "1000") or (x = "1001")) else '0'; B(5) <= '1' when ((x = "0000") or (x = "0100") or (x = "0101") or (x = "0110") or (x = "1000") or (x = "1001")) else '0'; B(6) <= '1' when ((x = "0010") or (x = "0011") or (x = "0100") or (x = "0101") or (x = "0110") or (x = "1000") or (x = "1001")) else '0';
Como se puede apreciar en este caso, las 7 líneas de código debe "ejecutarse" de forma concurrente. Dicho de otra forma: se describen 7 circuitos combinacionales que deben implementarse en paralelo.
En este caso x es la salida del latch mientras que B es la salida de la FPGA que está conectada al display de 7 segmentos. En este caso se ha usado un display de cátodo común por lo que para encender un segmento del display hay que emitir un ‘1’ en la salida correspondiente.
VHDL de la lógica secuencial
La lógica secuencial se divide en la lógica del registro de desplazamiento que se ha implementado utilizando el clásico modelo RTL:
d_reg <= data_in & q_reg(3 downto 1); --d_reg es q_reg desplazado concatenado con el bit que hay en data_in process(clock_in) --el proceso se activa cuando clock_in cambia begin if (rising_edge(clock_in)) then --cuando hay un flanco de subida q_reg <= d_reg; --se carga d_reg en q_reg end if; end process;
Y la lógica del latch de 4 bits, que se encarga de cargar el registro de desplazamiento (q_reg) en la señal de entrada de la lógica combinatoria para la salida de 7 segmentos (x), y que también se ha implementado utilizando el modelo RTL:
process(latch_in) --el proceso se activa cuando latch_in cambia begin if (rising_edge(latch_in)) then --cuando hay un flanco de subida x <= q_reg; --se carga q_reg en x end if; end process;
En este caso las acciones a realizar no se hacen "siempre" sino que dependen de otras señales (clock_in y latch_in) y debe hacerse una evaluación secuencial (si ocurre esto entonces aquello), por eso se utilizan bloques "process". Nótese que ambos bloques "process" se "ejecutan" en paralelo.
VHDL completo
El código VHDL completo, incluyendo la arquitectura y el port queda como sigue:
library IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.STD_LOGIC_ARITH.ALL; use IEEE.STD_LOGIC_UNSIGNED.ALL; entity SimpleShiftRegister is port ( clock_in : in std_logic; data_in : in std_logic; latch_in : in std_logic; B : out std_logic_vector(6 downto 0) ); end SimpleShiftRegister; architecture behavioral of SimpleShiftRegister is signal d_reg : std_logic_vector(3 downto 0); signal q_reg : std_logic_vector(3 downto 0); signal x : std_logic_vector(3 downto 0); begin d_reg <= data_in & q_reg(3 downto 1); B(0) <= '1' when ((x = "0000") or (x = "0001") or (x = "0011") or (x = "0100") or (x = "0101") or (x = "0110") or (x = "0111") or (x = "1000") or (x = "1001")) else '0'; B(1) <= '1' when ((x = "0000") or (x = "0010") or (x = "0011") or (x = "0101") or (x = "0110") or (x = "1000") or (x = "1001")) else '0'; B(2) <= '1' when ((x = "0000") or (x = "0010") or (x = "0110") or (x = "1000")) else '0'; B(3) <= '1' when ((x = "0000") or (x = "0010") or (x = "0011") or (x = "0101") or (x = "0110") or (x = "0111") or (x = "1000") or (x = "1001")) else '0'; B(4) <= '1' when ((x = "0000") or (x = "0001") or (x = "0010") or (x = "0011") or (x = "0100") or (x = "0111") or (x = "1000") or (x = "1001")) else '0'; B(5) <= '1' when ((x = "0000") or (x = "0100") or (x = "0101") or (x = "0110") or (x = "1000") or (x = "1001")) else '0'; B(6) <= '1' when ((x = "0010") or (x = "0011") or (x = "0100") or (x = "0101") or (x = "0110") or (x = "1000") or (x = "1001")) else '0'; process(clock_in) begin if (rising_edge(clock_in)) then q_reg <= d_reg; end if; end process; process(latch_in) begin if (rising_edge(latch_in)) then x <= q_reg; end if; end process; end behavioral;
Tras compilar y sintetizar este código, la implementación eléctrica generada es la siguiente:
Como se puede ver, tanto el registro de desplazamiento como el latch se implementa mediante biestables D mientras que la lógica combinatoria de conversión de binario a 7 segmentos se implementa mediante LUTs (Look Up Tables), en lugar de mediante puertas lógicas. Esta forma de implementar lógica combinatoria es muy habitual en las FPGAs y los CPLDs.
Conexión con el Arduino
La FPGA funciona a 3.3 voltios mientras que el Arduino funciona a 5 voltios. Es necesario, por tanto adaptar los voltajes. En este caso concreto todas las señales salen del Arduino y entran en la FPGA por lo que se ha optado por hacer una adaptación de voltaje sencilla basada en transistores.
En el Arduino la función encargada de enviar un valor al display de 7 segmentos deberá colocar los datos de forma serie a través del pin data_in usando como reloj clock_in. Se activará latch_in cuando se desee mostrar en el display el valor cargado en el registro de desplazamiento. Obsérvese que al hacer la conversión de voltajes utilizando transistores NPN en configuración de emisor común, la lógica debe ser negada, es decir, para emitir un 1 de 3.3 voltios, emitimos un 0 de 5 voltios y para emitir un 0 de 3.3 voltios, emitimos un 1 de 5 voltios:
const int CLK_PIN = 0; const int DATA_PIN = 1; const int LATCH_PIN = 2; #define ONE LOW #define ZERO HIGH void byteOut(unsigned char v) { for (unsigned char i = 0; i < 4; i++) { if ((v & 1) != 0) digitalWrite(DATA_PIN, ONE); else digitalWrite(DATA_PIN, ZERO); delay(1); digitalWrite(CLK_PIN, ONE); delay(1); digitalWrite(CLK_PIN, ZERO); delay(1); v = v >> 1; } digitalWrite(LATCH_PIN, ONE); delay(1); digitalWrite(LATCH_PIN, ZERO); delay(1); }
A continuación puede verse un vídeo con el invento en funcionamiento:
Algunos enlaces para empezar con VHDL (en español)
Lista de reproducción de YouTube del profesor Carlos Fajardo sobre VHDL - Vídeos muy amenos y fáciles de seguir.
Libro online "Programación en VHDL" - Muy buen libro, aunque le echo en falta más ejemplos y ejercicios.
[ añadir comentario ] ( 1748 visualizaciones ) | [ 0 trackbacks ] | enlace permanente
Tweet | |
( 3 / 2948 )
Calendario
