vhdl 4 bit booth algorithm, VHDL 고속 곱셈기
8-bit booth algorithm VHDL
library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
entity booth is
port (
reset : in std_logic;
clk : in std_logic;
load : in std_logic;
mlpcnd : in std_logic_vector (3 downto 0);
mlplr : in std_logic_vector (3 downto 0);
product : out std_logic_vector (7 downto 0)
);
end entity booth;
architecture rtl of booth is
signal q1 : std_logic;
signal ac : std_logic_vector (3 downto 0);
signal br : std_logic_vector (3 downto 0);
signal qr : std_logic_vector (3 downto 0);
signal sc : integer;
begin
process (reset, clk)
variable tmp_ac : std_logic_vector (3 downto 0);
begin
if (reset='0') then
br <= (others => '0');
qr <= (others => '0');
ac <= (others => '0');
q1 <= '0';
sc <= 4;
product <= (others => '0');
elsif(clk='1' and clk'event) then
if (load='1') then
br <= mlpcnd;
qr <= mlplr;
ac <= (others => '0');
q1 <= '0';
sc <= 4;
product <= (others => '0');
else
if (sc=0) then
product <= ac & qr;
else
if (qr(0)='0' and q1='1') then
tmp_ac := ac + br;
elsif (qr(0)='1' and q1='0') then
tmp_ac := ac + not br + '1';
else
tmp_ac := ac;
end if;
end if;
q1 <= qr(0);
qr <= tmp_ac(0) & qr(3 downto 1);
ac <= tmp_ac(3) & tmp_ac(3 downto 1);
sc <= sc - 1;
end if;
end if;
end process;
end architecture rtl;
Multiplicand : 0011
Multiplier : 0111
result : 00010101
Simulation result
Booth Algorithm은 partial products의 수를 줄이는 것을 그 목표로 하며 2‘s complement 표현에서 연속된 ’1‘의 string을 가산/감산함으로써 partial product의 수를 줄이게 된다. 이렇게 함으로써 그 연산의 과정이 줄어들게 되고 연산 속도는 빨라지게 된다. modified Booth Algorithm의 경우 3-bit씩 encoding하되 1-bit씩 overlapping 되도록 encoding을 한다. 각각의 encoding된 구간에 대해서 partial product를 찾고 shift한다. 이렇게 함으로써 partial product의 수를 n/2 로 감소시킬 수 있게 된다. 또한 modified Booth Algorithm의 경우 양수, 음수에 관계없이 항상 연산의 결과가 성립한다.
Reference
[1] Brown, Vranesic, Fundamentals of Digital Logic,2ed, p 291,683
[2] http://www.russinoff.com/libman/top.html
[3] http://en.wikipedia.org/wiki/Booth's_multiplication_algorithm