You have no items in your shopping cart.

Subtotal: 0.00

Abstract

A new architecture, namely, Multiplier-and accumulator (MAC) based Radix-4 Booth Multiplication Algorithm for high-speed arithmetic logics have been proposed and implemented on Spartan6 FPGA project Board . By combining multiplication with accumulation and devising a hybrid type adder the performance was improved. The modified booth encoder will reduce the number of partial products generated by a factor of 2. Fast multipliers are essential parts of digital signal processing systems. The speed of multiply operation is of great importance in digital signal processing as well as in the general purpose processors. The number to be added is the multiplicand, the number of times that it is added is the multiplier, and the result is the product. Each step of addition generates a partial product.

Demonstration video

 

Tool required

Software:

  • Xilinx ISE 14.7i

Language:

  • VHDL

Hardware:





Sp_6_FPGA_project_Board

Block Diagram for Implementation of Booth Multiplier

 



Block_Dgm_Booth_Multiplier

Introduction:

Booth Algorithm

Booth algorithm requires examination of the multiplier bits, and shifting of the partial product. Prior to the shifting, the multiplicand may be added to partial product, subtracted from the partial product, or left unchanged according to the following rules:

Look at the first least significant bits of the multiplier “X”, and the previous least Significant bits of the multiplier “X - 1”.

⇛0 0 Shift only

⇛1 1 Shift only.

⇛0 1 Add Y to U, and shift

⇛1 0 Subtract Y from U, and shift or add (-Y) to U and shift

⇛Take U & V together and shift arithmetic right shift which preserves the sign bit of 2’s complement number. Thus a positive number remains positive, and a negative number remains negative.

⇛Shift X circular right shift because this will prevent us from using two registers for the X value.



Booth_Multiplier_alg_1



Booth_Multiplier_alg_2

Booth Multiplier Output Image

Booth Multiplier Output Image

 

Booth Multiplier Output Image

 

Booth Multiplier Output Image

 

Booth Multiplier Output Image

Booth Multiplier Output Image

 

Source Code

VHDL Code for Booth Multiplier using Spartan6 FPGA project Board

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_SIGNED.ALL;

entity booth_mult is
Generic(
W : integer  := 6	-- specify mulitiplier width; must be even value
);
port(
clk	: in std_logic;
start		: in std_logic;
n_reset	: in std_logic;
mcand		: in std_logic_vector(W-1 downto 0);
mplier		: in std_logic_vector(W-1 downto 0);
done 		: out std_logic;
product	: out std_logic_vector(2*W-1 downto 0)
);
end booth_mult;

architecture arch of booth_mult is
type state_type is(IDLE, BUSY);
attribute ENUM_ENCODING	: string;	-- used for explicit state machine encoding
attribute ENUM_ENCODING of state_type	: type is "01 10";
signal state_reg, state_next	: state_type;
signal q_reg, q_next 	: unsigned(6 downto 0);
signal mcand_reg	: std_logic_vector(W-1 downto 0);		--registers for the multiplicand
signal prod_reg, prod_next	: std_logic_vector(2*W downto 0);
signal result_reg, result_next	: std_logic_vector(2*W downto 0);  	-- this holds the result before shift
signal q_add, q_reset	: std_logic;

begin
sync_update :
process(clk, n_reset)	-- process to incriments sequential logic on rising clock edges
begin
if rising_edge(clk) then
if n_reset = '0' then
state_reg <= IDLE;
q_reg <= (others => '0');
prod_reg <= (others => '0');
else
q_reg <= q_next;
state_reg <= state_next;
prod_reg <= prod_next(2*W) & prod_next(2*W downto 1);  -- shift prod register each time
result_reg <= prod_next;
end if;	
end if;
end process;

control_logic :	
process(state_reg, q_reg, result_reg, start, prod_reg, mplier, mcand )					
begin
-- init signals and no reg update
q_add <= '0';
q_reset <= '0';
done <= '0';
state_next <= state_reg  ;
prod_next <= prod_reg ;
result_next <= result_reg;	
case state_reg is
when IDLE => 
if (start = '1') then   -- load numbers to multiply
mcand_reg <= mcand;
prod_next(2*W downto W+1) <= (others => '0');  -- fill prod_next reg with [0000...0000(mplier)0]
prod_next(W downto 1) <= mplier;
prod_next(0) <= '0';
state_next <= BUSY;
end if;

when BUSY =>
q_add <= '1';
if (q_reg = '0' & conv_unsigned(W, 7)(6 downto 1)  and start /= '1') then  -- after W/2 clock cycles multiplication is done
product <= prod_next(2*W) & prod_next(2*W  downto 2);
done <= '1' ;
q_add <= '0';
q_reset <= '1';
state_next <= IDLE;
end if;
-- Booth Decoding and operation
case result_reg(2 downto 0) is     
when "001" | "010" => 	-- Add Mcand
prod_next <= ((prod_reg(2*W) & prod_reg(2*W downto W+1)) + (mcand_reg(W - 1) & mcand_reg)) & prod_reg(W downto 1);
when "011" => 					-- Add 2*Mcand
prod_next <= ((prod_reg(2*W) & prod_reg(2*W downto W+1)) + (mcand_reg & '0' )) & prod_reg(W downto 1);
when "100" => 					-- Subtract 2*Mcand
prod_next <= ((prod_reg(2*W) & prod_reg(2*W downto W+1)) - (mcand_reg & '0' )) & prod_reg(W downto 1);
when "101" | "110" => 	-- Subtract Mcand
prod_next <= ((prod_reg(2*W) & prod_reg(2*W downto W+1)) - (mcand_reg(W - 1) & mcand_reg)) & prod_reg(W downto 1); -- 2xMcand 
when others => 				-- Just shift
prod_next <= prod_reg(2*W) & prod_reg(2*W downto 1);
end case;
end case;
end process;
	
-- timer/counter for timed logic
q_next <= (others => '0') when q_reset = '1' else       	-- reset q_next to bottom if q_reset is 1
q_reg + 1 when q_add = '1' else         	-- increment q_reg by 1 if q_add is 1
q_reg;   
end arch;

Pin Assignment for Booth Multiplier Implementation

NET "mcand[5]" LOC = P30;
NET "mcand[4]" LOC = P29;
NET "mcand[3]" LOC = P27;
NET "mcand[2]" LOC = P26;
NET "mcand[1]" LOC = P24;
NET "mcand[0]" LOC = P23;
NET "mplier[5]" LOC = P50;
NET "mplier[4]" LOC = P48;
NET "mplier[3]" LOC = P47;
NET "mplier[2]" LOC = P46;
NET "mplier[1]" LOC = P33;
NET "mplier[0]" LOC = P32;
NET "product[11]" LOC = P62;
NET "product[10]" LOC = P61;
NET "product[9]" LOC = P59;
NET "product[8]" LOC = P58;
NET "product[7]" LOC = P45;
NET "product[6]" LOC = P44;
NET "product[5]" LOC = P43;
NET "product[4]" LOC = P41;
NET "product[3]" LOC = P40;
NET "product[2]" LOC = P38;
NET "product[1]" LOC = P35;
NET "product[0]" LOC = P34;
NET "clk" LOC = P85;
NET "done" LOC = P74;
NET "n_reset" LOC = P57;
NET "start" LOC = P56;

Conclusion

Radix 4 modified booth algorithm was successfully implemented in Spartan-6 FPGA and output verified with switches and LED’s of Spartan6 FPGA project Board .