Hello, I'm totally new to VHDL and i'm trying to do a polynonamial evaluation. In particular I have a signed 16 bit value (x) and I want to obtain y=d*x^3+c*x^2+b*x+a. I have created a signed multiplier: LIBRARY ieee; USE ieee.std_logic_1164.all; USE ieee.numeric_std.all; ENTITY my_signed_multiplier IS PORT( in1, in2 : IN signed (15 DOWNTO 0); clk,clr : IN std_logic; result : OUT signed(15 DOWNTO 0)); END ENTITY my_signed_multiplier; ARCHITECTURE logic OF my_signed_multiplier IS SIGNAL in1_reg, in2_reg : signed (15 DOWNTO 0); SIGNAL out_reg : signed (31 DOWNTO 0); BEGIN PROCESS(clk,clr) BEGIN IF clr ='1' THEN in1_reg<=(OTHERS => '0'); in2_reg<=(OTHERS => '0'); out_reg<=(OTHERS => '0'); ELSIF rising_edge(clk) THEN in1_reg<=in1; in2_reg<=in2; out_reg<=in1_reg*in2_reg; END IF; END PROCESS; result<=out_reg(31 DOWNTO 16); END ARCHITECTURE logic; Now I was supposed to create another entity which has a generic variable (eg: pow : integer ) that specifies how many instance of my_signed multiplier use to obtain the correct signal power elevation. By the way now I'm stuck is I don't know exactly how to do it. Any suggestions is appreciated . Thank you !

Take a step back. Before you start, think about how the circuit would look when created. Then go back and write the code. The multiplier entity you have created will causes a massive bias by just removing the 16 LSBs. Did you intend to do this? and did you intend to floor your results (rather than round to nearest?)

--- Quote Start --- Take a step back. Before you start, think about how the circuit would look when created. Then go back and write the code. The multiplier entity you have created will causes a massive bias by just removing the 16 LSBs. Did you intend to do this? and did you intend to floor your results (rather than round to nearest?) --- Quote End --- Dear Tricky, I have a 16 bit DAC so I'm forced to remove the 16 LSBs. Now I have created 7 multiplier with seven DFF with a generic delay. So that with the multipliers I can evaluate x^7, x^6, x^5...x^0 and, before the final sum (forgetting for now about the coefficients), I compensate the delays introduced by the multipliers with the DFFs. In particular I think that x should be delayed 6 cycles in respect to x^7=((((x*x)*x)*x)*x)*x)*x, x^2 5 cycles and so on. I have noticed that if I sum 8 signal of 16 bit at a time, I need a 24 bit output signal. By the way in VHDL seems that also the summing signals must be 24 bit. Now that I have 8 - 16 bit signals, there is a simple way on promoting them to 24 bit or I must create 8 new 24 bit signal and assignin them the 16 bit ones ? Thank you for your time.

actually, summing 8 16 bit signals, you should only need a 19 bit result. How are you doing the summing? signed/unsigned type do not do any bit extension for you, you have to handle it yourself. It is difficult to understand what you mean without seeing any code. But I worry that with your current method of removing of just removing the 16 LSBs, you wont be summing the results correctly. x^3 is going to be 48 bits wide, with x^2 32 bits. It would be wrong just to sum the 16 MSBs.

Dear Tricky, Yes, you are right, I need a 19 bit result. My fault. This is the code I'm implementing: LIBRARY ieee; USE ieee.std_logic_1164.all; USE ieee.numeric_std.all; ENTITY my_poly_test IS PORT( in1 : IN SIGNED (15 DOWNTO 0); clk,clr : IN std_logic; result : OUT SIGNED (15 DOWNTO 0)); END ENTITY my_poly_test; ARCHITECTURE logic OF my_poly_test IS SIGNAL x2 : SIGNED (15 DOWNTO 0); SIGNAL x3 : SIGNED (15 DOWNTO 0); SIGNAL x4 : SIGNED (15 DOWNTO 0); SIGNAL x5 : SIGNED (15 DOWNTO 0); SIGNAL x6 : SIGNED (15 DOWNTO 0); SIGNAL x7 : SIGNED (15 DOWNTO 0); SIGNAL x_d : STD_LOGIC_VECTOR(15 DOWNTO 0); SIGNAL x2_d : STD_LOGIC_VECTOR(15 DOWNTO 0); SIGNAL x3_d : STD_LOGIC_VECTOR (15 DOWNTO 0); SIGNAL x4_d : STD_LOGIC_VECTOR (15 DOWNTO 0); SIGNAL x5_d : STD_LOGIC_VECTOR (15 DOWNTO 0); SIGNAL x6_d : STD_LOGIC_VECTOR (15 DOWNTO 0); SIGNAL x7_d : STD_LOGIC_VECTOR(15 DOWNTO 0); SIGNAL sum : STD_LOGIC_VECTOR(18 DOWNTO 0); COMPONENT my_signed_multiplier IS PORT( in1, in2 : IN signed (15 DOWNTO 0); clk,clr : IN std_logic; result : OUT signed(15 DOWNTO 0)); END COMPONENT; COMPONENT my_generic_dff_aclr IS GENERIC (delay : INTEGER :=4); PORT( d : IN STD_LOGIC_VECTOR(15 DOWNTO 0); clk , clr : IN STD_LOGIC; q: OUT STD_LOGIC_VECTOR(15 DOWNTO 0)); END COMPONENT; COMPONENT my_signed_adder IS PORT( in1,in2 : IN SIGNED (15 DOWNTO 0); clk,clr : IN std_logic; result : OUT SIGNED (15 DOWNTO 0)); END COMPONENT; BEGIN M1 : my_signed_multiplier PORT MAP (in1,in1,clk,clr,x2); M2 : my_signed_multiplier PORT MAP (in1,x2,clk,clr,x3); M3 : my_signed_multiplier PORT MAP (in1,x3,clk,clr,x4); M4 : my_signed_multiplier PORT MAP (in1,x4,clk,clr,x5); M5 : my_signed_multiplier PORT MAP (in1,x5,clk,clr,x6); M6 : my_signed_multiplier PORT MAP (in1,x6,clk,clr,x7); DFF1: my_generic_dff_aclr GENERIC MAP(1) PORT MAP (std_logic_vector(x6),clk,clr,x6_d); DFF2: my_generic_dff_aclr GENERIC MAP(2) PORT MAP (std_logic_vector(x5),clk,clr,x5_d); DFF3: my_generic_dff_aclr GENERIC MAP(3) PORT MAP (std_logic_vector(x4),clk,clr,x4_d); DFF4: my_generic_dff_aclr GENERIC MAP(4) PORT MAP (std_logic_vector(x3),clk,clr,x3_d); DFF5: my_generic_dff_aclr GENERIC MAP(5) PORT MAP (std_logic_vector(x2),clk,clr,x2_d); DFF6: my_generic_dff_aclr GENERIC MAP(6) PORT MAP (std_logic_vector(x),clk,clr,x_d); PROCESS(clk,clr) BEGIN IF clr ='1' THEN x2<=(OTHERS => '0'); x3<=(OTHERS => '0'); x4<=(OTHERS => '0'); x5<=(OTHERS => '0'); x6<=(OTHERS => '0'); x7<=(OTHERS => '0'); x2_d<=(OTHERS => '0'); x3_d<=(OTHERS => '0'); x4_d<=(OTHERS => '0'); x5_d<=(OTHERS => '0'); x6_d<=(OTHERS => '0'); x7_d<=(OTHERS => '0'); ELSIF rising_edge(clk) THEN sum<=1+signed(x2_d)+signed(x3_d)+signed(x4_d)+signed(x5_d)+signed(x6_d)+signed(x7_d); result<=sum(19 DOWNTO 3); END IF; END PROCESS; END ARCHITECTURE logic; Every time I take a mutiplication I take only the 16 MSbs. So at the final sum each signal is exactly 16 bits wide. Thank you for help.

Right, there are going to be many problems here: 1. your "My_signed_multiplier" delay is 2 clocks. So using in1 directly to each multiplier stage is going to mean x3 is going to be x2 multiplied by the value of in1 2 clocks after the value of in1 to create x2. So you need to create pipelined versions of the input to allign it properly. 2. You cannot clear x2-7 and xN_d in the other process - they are assigned from the components. This will cause multiple driver errors 3. You've got the magnitude problem I mentioned in my previous post when doing the sum. What you're doing is like this: lets imagin we have X^3 + X^2 + X + 7, and say X is 25. THe answer should be 16282. SO, according to your code: X^3 = 15625, lets lose the 2 LSBs (as we're doing 2 mults), we get 156. X^2 = 625, lets lose the LSB, we get 62 so 156 + 62 + 25 + 7 = 250. Nothing like the actual answer, even if we dropped the 2 LSBs from the correct answer. You need to pay attention to bit allignment when you do the multiplies and adds. Otherwise you end up adding values together that are orders of magnitude apart. 4. Other coding stype point: Please use named association in entity instantiation rather than positional (plus if you want to, ditch the component declarations all together and go with direct instantiation): eg: my_ent_inst : entity work.my_ent generic map ( some_generic => 1, --etc ) port map ( portA => input1, portB => input2, --etc ) It is less prone to the annoying errors you get with positional. (And for direct instantiation, the compiler checks the entity matches the instantiation, rather than the component declaration, so you get an instant error if there is a missmatch, rather than waiting for the error to pop out during elaboration which can be several minutes later).

Polynomial Evaluation | Altera Community

25 Replies

Altera_Forum
Honored Contributor
12 years ago
--- Quote Start ---
Thank you kaz !

Do you suggest to add the 16 leading zeros at each multiplication and then taking always the 16 MSbs ?

If don't I suppose that if I want to evaluate x^7 I would have to add much more than 16 bit or I am wrong ?
--- Quote End ---

you remove 16 lsbs from each mult result. thus
x*x means 16bits*16bits => 32 bits, discard 16 lsbs yielding 16 bits result as x^2 (but keep in head that it is x^2/2^16)
now x^2*x is 16bits * 16bits yielding 32 bits, discard 16 lsbs and so on.

The idea is that if you enter in matlab:
x = 25;

y1=x^2+x^3+x^4+x^5+x^6+x^7
= 6357828750
y2= (floor(x^2/2^16)+floor(x^3/2^16)+floor(x^4/2^16)+floor(x^5/2^16)+floor(x^6/2^16)+floor(x^7/2^16))*2^(16) = 6357712896

so at final result from adder insert 16 zeros (in effect we multiply back by the loss). in simple algebra:
x + y = x + y or = (x/2 + y/2)*2
Altera_Forum
Honored Contributor
12 years ago
TO_BE_DONE
Altera_Forum
Honored Contributor
12 years ago
Thank you Kaz,

you remove 16 lsbs from each mult result. thus
x*x means 16bits*16bits => 32 bits,
Got it !

discard 16 lsbs yielding 16 bits result as x^2 (but keep in head that it is x^2/2^16)
now x^2*x is 16bits * 16bits yielding 32 bits, discard 16 lsbs and so on.
So x^3 would be ((x^2/2^16)*x)/2^16, so when I sum, I have to add 32 zeros to x^3 ?
Am I right or I am missing something?

I can make it work !! i know !!
Altera_Forum
Honored Contributor
12 years ago
--- Quote Start ---
Thank you Kaz,

discard 16 lsbs yielding 16 bits result as x^2 (but keep in head that it is x^2/2^16)
now x^2*x is 16bits * 16bits yielding 32 bits, discard 16 lsbs and so on.

So x^3 would be ((x^2/2^16)*x)/2^16 or I'm totally confused as always ?

I can make it work !! i know !!
--- Quote End ---

we are pre-dividing each result by 2^16(by discarding 16 lsbs) so each mult result is correct by this ratio.
don't worry what each stage means in maths. just discard 16 LSBs from each and every mult then make final compensation by inserting 16 leading zeros in the adder result.
Thus anything that enters adder is not true value but scaled version by 2^16.
you can do same thing when multiplying by a,b,c etc. before final adder and apply same thing to any constant term.
Altera_Forum
Honored Contributor
12 years ago
--- Quote Start ---
Thank you Kaz,

discard 16 lsbs yielding 16 bits result as x^2 (but keep in head that it is x^2/2^16)
now x^2*x is 16bits * 16bits yielding 32 bits, discard 16 lsbs and so on.
So x^3 would be ((x^2/2^16)*x)/2^16, so when I sum, I have to add 32 zeros to x^3 ?
Am I right or I am missing something?

I can make it work !! i know !!
--- Quote End ---

wrong?? not 32 bits just one simple same rule. discard 16 lsbs from any mult result. add 16 leading zeros at final sum.
Altera_Forum
Honored Contributor
12 years ago
--- Quote Start ---
we are pre-dividing each result by 2^16(by discarding 16 lsbs) so each mult result is correct by this ratio.
don't worry what each stage means in maths. just discard 16 LSBs from each and every mult then make final compensation by inserting 16 leading zeros in the adder result.
Thus anything that enters adder is not true value but scaled version by 2^16.
you can do same thing when multiplying by a,b,c etc. before final adder and apply same thing to any constant term.
--- Quote End ---

Thank you kaz ! I will work on your suggestions. I really appreciate !

Have a nice day !
Altera_Forum
Honored Contributor
12 years ago
--- Quote Start ---
discard 16 lsbs yielding 16 bits result as x^2 (but keep in head that it is x^2/2^16)
now x^2*x is 16bits * 16bits yielding 32 bits, discard 16 lsbs and so on.
So x^3 would be ((x^2/2^16)*x)/2^16, so when I sum, I have to add 32 zeros to x^3 ?
Am I right or I am missing something?
--- Quote End ---

The question addresses an interesting point. Assumed you have signed 16 bit numbers with a number range of -2^15..2^15-1. And you are raising a 16 bit input number to the 7th power. What's the minimum input value that gives a non-zero result?

The result will be only slightly better for unsigned 16 bit numbers. For many DSP related problems, fixed point arithmetic helps to overcome range and scaling problems, but in this case, only a considerably larger bit width or a floating point representation can help.

As a minor point, to keep the result resolution of signed multiply, you'll strip off only 15 LSBs and apply saturation logic to handle the special case (-2^15)*(-2^15).

Altera_Forum

Honored Contributor

12 years ago

Hello guys,

I've modified my vhdl code as you suggested. Hope it works and that all is finally ok !

LIBRARY ieee;
USE ieee.std_logic_1164.all;
USE ieee.numeric_std.all;
ENTITY my_poly_test IS
    PORT( in1 : IN SIGNED (15 DOWNTO 0);
                clk,clr : IN std_logic;
             result : OUT SIGNED (15 DOWNTO 0));
END ENTITY my_poly_test;
ARCHITECTURE logic OF my_poly_test IS
    SIGNAL x2 : SIGNED (15 DOWNTO 0);
    SIGNAL x3 : SIGNED (15 DOWNTO 0);
    SIGNAL x4 : SIGNED (15 DOWNTO 0);
    SIGNAL x5 : SIGNED (15 DOWNTO 0);
    SIGNAL x6 : SIGNED (15 DOWNTO 0);
    SIGNAL x7 : SIGNED (15 DOWNTO 0);
    SIGNAL in1_1d : STD_LOGIC_VECTOR(15 DOWNTO 0);
    SIGNAL in1_2d : STD_LOGIC_VECTOR(15 DOWNTO 0);
    SIGNAL in1_3d  : STD_LOGIC_VECTOR (15 DOWNTO 0);
    SIGNAL in1_4d : STD_LOGIC_VECTOR (15 DOWNTO 0);
    SIGNAL in1_5d : STD_LOGIC_VECTOR (15 DOWNTO 0);
    SIGNAL x_6d : STD_LOGIC_VECTOR(15 DOWNTO 0);
    SIGNAL x2_5d : STD_LOGIC_VECTOR(15 DOWNTO 0);
    SIGNAL x3_4d : STD_LOGIC_VECTOR (15 DOWNTO 0);
    SIGNAL x4_3d : STD_LOGIC_VECTOR (15 DOWNTO 0);
    SIGNAL x5_2d : STD_LOGIC_VECTOR (15 DOWNTO 0);
    SIGNAL x6_1d : STD_LOGIC_VECTOR (15 DOWNTO 0);
    SIGNAL x7_d : STD_LOGIC_VECTOR(15 DOWNTO 0);
    SIGNAL sum : SIGNED(31 DOWNTO 0);
    
              
    BEGIN
        M1 :   work.my_signed_multiplier PORT MAP (in1=>in1,in2=>in1,clk=>clk,clr=>clr,result=>x2);
        
        DFF1:  work.my_generic_dff_aclr GENERIC MAP(delay =>1) PORT MAP (d => std_logic_vector(in1), clk => clk, clr=> clr, q => in1_1d);
       M2 :   work.my_signed_multiplier PORT MAP (in1=> signed(in1_1d),in2=> x2,clk=>clk,clr=>clr,result => x3);
        
        DFF2:  work.my_generic_dff_aclr GENERIC MAP(delay =>1) PORT MAP (d => in1_1d,clk => clk,clr=> clr,q =>in1_2d);
        M3 :   work.my_signed_multiplier PORT MAP (in1=> signed(in1_2d),in2=>x3,clk=>clk,clr=>clr,result => x4);
        
        DFF3:  work.my_generic_dff_aclr GENERIC MAP(delay =>1) PORT MAP (d =>in1_2d,clk => clk,clr=> clr,q =>in1_3d);
        M4 :   work.my_signed_multiplier PORT MAP (in1=> signed(in1_3d),in2=>x4,clk=>clk,clr=>clr,result => x5);
        
        DFF4:  work.my_generic_dff_aclr GENERIC MAP(delay =>1) PORT MAP (d => in1_3d,clk =>clk,clr=> clr,q =>in1_4d);
        M5 :   work.my_signed_multiplier PORT MAP (in1=> signed(in1_4d),in2=>x5,clk=>clk,clr=>clr,result => x6);
        
        DFF5:  work.my_generic_dff_aclr GENERIC MAP(delay =>1) PORT MAP (d => in1_4d,clk =>clk,clr=> clr,q =>in1_5d);
        M6 :   work.my_signed_multiplier PORT MAP (in1=> signed(in1_5d),in2=>x6,clk=>clk,clr=>clr,result => x7);
        
        DFF6:  work.my_generic_dff_aclr  GENERIC MAP(delay =>1) PORT MAP (d => std_logic_vector(x6), clk => clk, clr=> clr, q =>x6_1d);
        DFF7:  work.my_generic_dff_aclr  GENERIC MAP(delay =>2) PORT MAP (d => std_logic_vector(x5), clk => clk, clr=> clr, q =>x5_2d);
        DFF8:  work.my_generic_dff_aclr  GENERIC MAP(delay =>3) PORT MAP (d => std_logic_vector(x4), clk => clk, clr=> clr, q =>x4_3d);
        DFF9:  work.my_generic_dff_aclr  GENERIC MAP(delay =>4) PORT MAP (d => std_logic_vector(x3), clk => clk, clr=> clr, q =>x3_4d);
        DFF10: work.my_generic_dff_aclr GENERIC MAP(delay =>5) PORT MAP (d => std_logic_vector(x2), clk => clk, clr=> clr, q =>x2_5d);
        DFF11: work.my_generic_dff_aclr GENERIC MAP(delay =>6) PORT MAP (d => std_logic_vector(in1), clk => clk, clr=> clr,q =>x_6d);
    PROCESS(clk,clr)
    BEGIN
        IF clr ='1' THEN
        result<=(OTHERS => '0');
        
        ELSIF rising_edge(clk) THEN
            sum<=1+signed(("0000000000000000")&x_6d)+signed(x2_5d&("0000000000000000"))+signed(x3_4d&("0000000000000000"))+signed(x4_3d&("0000000000000000"))+signed(x5_2d&("0000000000000000"))+signed(x6_1d&("0000000000000000"))+signed(x7_d&("0000000000000000"));
            result<=sum(31 DOWNTO 16);
        END IF;    
    END PROCESS;
END ARCHITECTURE logic;

Thank you for your help !

Altera_Forum
Honored Contributor
12 years ago
--- Quote Start ---
The question addresses an interesting point. Assumed you have signed 16 bit numbers with a number range of -2^15..2^15-1. And you are raising a 16 bit input number to the 7th power. What's the minimum input value that gives a non-zero result?

The result will be only slightly better for unsigned 16 bit numbers. For many DSP related problems, fixed point arithmetic helps to overcome range and scaling problems, but in this case, only a considerably larger bit width or a floating point representation can help.

As a minor point, to keep the result resolution of signed multiply, you'll strip off only 15 LSBs and apply saturation logic to handle the special case (-2^15)*(-2^15).
--- Quote End ---

Thank you FvM I will look for it too.
Altera_Forum
Honored Contributor
12 years ago
Instead of asking us if it works - how about testing it yourself and learning the tools? Modelsim would be the first step. Compile your code in there and fix any syntax errors. Then write yourself a testbench to drive some stimulus to test this block. THen run the testbench and debug your design. Does it produce the results you expected? are the pipelines all correct?

These are all challenges you need to learn to do yourself.

Looking at the code its getting better. But you lack comments, and nice spacing (who likes to see so many adds on a single line)? How about using hex notation instead of the really long binary strings?

You also dont have enough 0s on most of your co-efficients. For it to work properly, the x_6d needs 80 leading 0s, x2_5d needs 64 leading and 16 trailing, x3_4d needs 48 leading and 32 trailing etc.

Thats a lot of 0s. Maybe you could work out a method to make it less clunky?

Forum Discussion

Polynomial Evaluation

25 Replies

Recent Discussions

USB-BlasterII mounts as "USB-Blaster variant"

Quartus Dark Theme on Linux - Solution

Error(23098) when using IPM_IOPLL on Agliex 7

Quartus 13.1 License

Highlight similar instances of a selected word fails when scrolling