A polynomial equation is an equation which is formed with variables, coefficients and exponents. They can be written in the following format:
y =anxn + an-1xn-1 + ... +a1x + a0 .
Here an, an-1 ... , a1 ,a0 are coefficients,
n, n-1, ... etc are exponents and x is the variable.
In this post, I want to share, VHDL code for computing the value of 'y' if you know the value of 'x' and coefficients forming the polynomial.
Directly calculating the polynomial with the above equation is very inefficient. So, first we reformat the equation as per Horner's rule:
y =(((anx + an-1)x + an-2)x + an-3)x + ... )x +a0 .
This modified equation can be represented by the following block diagram:
There are 3 sub-entities in the above block diagram.
1) Block number 1:
This block keep generating successive powers of input x.
In the first clock cycle it generates x^0 = 1.
In the 2ndclock cycle it generates x^1.
In the 3rd clock cycle it generates x^2.
In the nth clock cycle it generates x^(n-1).
Every clock cycle, the previous outputs are multiplied with 'x' to get the next power of x.
2)Block number 2:
The powers of x generated in the first block are multiplied with the corresponding coefficients of the polynomial in Block numbered 2. The coefficients are declared and initialized in the top level entity and can be changed easily.
3)Block number 4:
This block is basically an accumulative adder which accumulates all the products generated by the multiplier. Once it does 'n' additions, we have the final result available in output 'y'. An output 'done' is set as high to indicate that the output is ready.
Let me share the VHDL codes for these entities along with the testbench.
1) power_module.vhd
--This module generates successive powers of input x in each clock cycle.
--For example 1,x,x^2,x^3,x^4 etc.
--The output from the previous cycle is multiplied again by x to get the next power.
--The output from this entity is passed to the multiplier module, where it gets
--multiplied by the corresponding coefficient.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity power_module is
generic(N : integer := 32);
port (
Clock : in std_logic;
reset : in std_logic;
x : in signed(N-1 downto 0);
x_powered : out signed(N-1 downto 0)
);
end power_module;
architecture Behav of power_module is
signal x_pow : signed(N-1 downto 0) := to_signed(1,N);
begin
POWER_PROC : process(Clock,reset)
variable temp_prod : signed(2*N-1 downto 0);
begin
if (reset='1') then
x_pow <= to_signed(1,N);
elsif(rising_edge(Clock)) then
temp_prod := x*x_pow;
--The MSB half of the result is ignored. We assume that all intermediate powers of x
--can be represented by a max of N bits.
x_pow <= temp_prod(N-1 downto 0);
end if;
end process;
x_powered <= x_pow;
end architecture;
2) multiplier.vhd
--The successive powers of x are multiplied by the corresponding coeffcients here.
--The results are sent to the adder module which acts as an "accumulator".
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity multiplier is
generic(N : integer := 32);
port (
Clock : in std_logic;
x,y : in signed(N-1 downto 0);
prod : out signed(N-1 downto 0)
);
end multiplier;
architecture Behav of multiplier is
begin
MULT_PROC : process(Clock)
variable temp_prod : signed(2*N-1 downto 0) := (others => '0');
begin
if(rising_edge(Clock)) then
temp_prod := x*y;
--The MSB half of the result is ignored. We assume that all intermediate numbers
--be represented by a max of N bits.
prod <= temp_prod(N-1 downto 0);
end if;
end process;
end architecture;
3) adder.vhd
--The output from multiplier module is received by this module and accumulated to
--form the output. If the polynomial equation has a degree of 'n' then 'n' additions has to take place
--to get the final result.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity adder is
generic(N : integer := 32);
port (
Clock : in std_logic;
reset : in std_logic;
x : in signed(N-1 downto 0);
sum : out signed(N-1 downto 0)
);
end adder;
architecture Behav of adder is
signal temp_sum : signed(N-1 downto 0) := (others => '0');
begin
ADDER_PROC : process(Clock,reset)
begin
if (reset = '1') then
temp_sum <= (others => '0');
elsif(rising_edge(Clock)) then
temp_sum <= temp_sum + x;
end if;
end process;
sum <= temp_sum;
end architecture;
4) Top Level Entity : poly_eq_calc.vhd
--This is the top level entity for the polynomial equation calculator.
--The power_module, multiplier and adders entities are instantiated inside this top level block.
--When the output signal done is High, the output available at the 'y' output is the result we want.
--Ignore all other values of 'y' when done is Low.
--We have assumed that all the intermediate numbers calculated to reach the final result, can be represented
--by a maximum of N bits. This simplifies the design very much.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity poly_eq_calc is
generic(N : integer := 32);
port (
Clock : in std_logic;
reset : in std_logic;
x : in signed(N-1 downto 0);
y : out signed(N-1 downto 0);
done : out std_logic
);
end poly_eq_calc;
architecture Behav of poly_eq_calc is
component power_module is
generic(N : integer := 32);
port (
Clock : in std_logic;
reset : in std_logic;
x : in signed(N-1 downto 0);
x_powered : out signed(N-1 downto 0)
);
end component;
component multiplier is
generic(N : integer := 32);
port (
Clock : in std_logic;
x,y : in signed(N-1 downto 0);
prod : out signed(N-1 downto 0)
);
end component;
component adder is
generic(N : integer := 32);
port (
Clock : in std_logic;
reset : in std_logic;
x : in signed(N-1 downto 0);
sum : out signed(N-1 downto 0)
);
end component;
signal x_powered,coeff,product_from_mult : signed(N-1 downto 0) := (others => '0');
constant NUM_COEFFS : integer := 4; --Change here to change the degree of the polynomial.
type arr_type is array (0 to NUM_COEFFS-1) of signed(N-1 downto 0);
--Eq : 3*x^3 - 2*x^2 - 4*x + 5;
--The coefficients belonging to higher powers of x are stored in higher addresses in Coeffs array.
signal Coeffs : arr_type := (to_signed(5,N), --change coefficients here.
to_signed(-4,N),
to_signed(-2,N),
to_signed(3,N));
signal reset_adder : std_logic := '0';
begin
--Instantiate the 3 sub-entities.
calc_power_of_x : power_module generic map(N => N)
port map(Clock,reset,x,x_powered);
multiply : multiplier generic map(N => N)
port map(Clock,x_powered,coeff,product_from_mult);
add : adder generic map(N => N)
port map(Clock,reset_adder,product_from_mult,y);
--The process controlling the 3 sub-entities and also supplying them with coefficients.
MAIN_PROC : process(Clock,reset)
variable coeff_index : integer := 0;
begin
if(reset = '1') then
done <= '0';
coeff_index := 0;
coeff <= Coeffs(0);
reset_adder <= '1';
elsif(rising_edge(Clock)) then
reset_adder <= '0'; --the disabling of 'reset of adder' gets noticed by adder entity in the next clock cycle.
if(coeff_index < NUM_COEFFS-1) then
coeff_index := coeff_index+1;
coeff <= Coeffs(coeff_index); --send the coefficients one by one to the multiplier entity.
elsif(coeff_index = NUM_COEFFS-1) then
coeff_index := coeff_index+1;
else
done <= '1'; --The final result is available in 'y' now.
end if;
end if;
end process;
end architecture;
5) Testbench : tb_poly_eq_calc.vhd
--Testbench code.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
--The testbench entity is always empty.
entity tb_poly_eq_calc is
end tb_poly_eq_calc;
architecture sim of tb_poly_eq_calc is
constant clk_period : time := 10 ns; --set the clock period here.
signal Clk : std_logic := '1';
signal reset : std_logic := '1';
constant N : integer := 32; --change the width of input and output here.
signal x,y : signed(N-1 downto 0) := (others => '0');
signal done : std_logic := '0';
begin
Clk <= not Clk after clk_period / 2; --generate clock
--Instantiating Design Under Test.
DUT : entity work.poly_eq_calc generic map(N => N)
port map (Clk, reset, x, y, done);
--Apply inputs here. Only 'x' can be changed here.
--To change coefficients and degree of polynomial edit the top level entity directly.
SEQUENCER_PROC : process
begin
--first input.
reset <= '1';
wait for clk_period * 2.5;
reset <= '0';
x <= to_signed(4, N);
wait for clk_period;
wait until done='1'; --wait for result to be out.
wait for clk_period;
--second input.
reset <= '1';
wait for clk_period;
reset <= '0';
x <= to_signed(7, N);
wait for clk_period;
wait until done='1'; --wait for result to be out.
wait for clk_period;
--third input.
reset <= '1';
wait for clk_period;
reset <= '0';
x <= to_signed(15, N);
wait for clk_period;
wait until done='1'; --wait for result to be out.
wait for clk_period;
--fourth input.
reset <= '1';
wait for clk_period;
reset <= '0';
x <= to_signed(-9, N);
wait for clk_period;
wait until done='1'; --wait for result to be out.
wait for clk_period;
reset <= '1';
wait;
end process;
--Check if the results are correct and report the result.
CHECK_RESULTS_PROC : process(Clk)
variable actual_res : integer := 0;
variable input_num,x_int : integer := 0;
begin
if(rising_edge(Clk)) then
if(done = '1') then
x_int := to_integer(x);
--Change this equation if you change the polynomial eq inside the top level entity.
actual_res := 3*x_int*x_int*x_int - 2*x_int*x_int - 4*x_int + 5;
input_num := input_num+1;
if(actual_res = to_integer(y)) then
report "Input number " & integer'image(input_num) & " Worked Well";
else
report "Input number " & integer'image(input_num) & " Has Error";
end if;
end if;
end if;
end process;
end architecture;
The code was simulated successfully using Modelsim 10.4a version. The simulation waveform below shows the signals for the first two set of inputs:
The design was synthesized successfully using Vivado 2020.2 version.
No comments:
Post a Comment