Forum Discussion

Altera_Forum's avatar
Altera_Forum
Icon for Honored Contributor rankHonored Contributor
14 years ago

Need help for VHDL recursive function

Hi!

I'm new to advance VHDL programming. Here below is my code for generating hermite plolynomial (hp). It can be defind recursively like below.

hp(k, t) = 1 when k = 0,

hp(k, t) = 2*t when k = 1, and

hp(k, t) = 2*t*h(k-1, t) - 2*(k-1)*h(k-2,t) when K>1.

Here, k is a positive integer, and t is continues time.

Based on the expressions I wrote a VHDL I code as below.

Library IEEE;

use IEEE.std_logic_1164.all;

use IEEE.numeric_std.all;

-- --------------------------------------

entity hermitePolynomial_2 is

-- --------------------------------------

port ( clk_1 : in std_logic; -- System Clock (50MHz)

ce_1 : in std_logic;

Din : in std_logic_vector(3 downto 0);

Tin : in std_logic_vector(15 downto 0); --

Result : out std_logic_vector(40 downto 0));

end hermitePolynomial_2;

-- --------------------------------------

Architecture RTL of hermitePolynomial_2 is

-- ---------------------------------------

signal Tinr : std_logic_vector (Tin'range);

function Her (d : natural; t : natural) return natural is

variable res : natural;

begin

if d = 0 then -- note that, by convention, 0! = 1

res := (0=>'1',others=>'0'); -- 1

elsif d = 1 then

res := 2 * t;

else

res := (2 * t * Her(d-1, t) - 2 * (d-1) * Her(d-2, t)); -- function call notation trick

end if;

return res;

end function Her;

Begin

process(clk_1)

begin

if (rising_edge(clk_1)) then

Dinr <= Din; -- input FFs

Tinr <= Tin; -- input FFs

Result <= std_logic_vector(Her(to_natural(Dinr), to_natural(Tinr)));

end if;

end process;

End architecture RTL;

I'm not able to synthezise it. Could anyone please hlep me to rectify my code? Please.. please..:confused:

9 Replies

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    --- Quote Start ---

    I'm not able to synthezise it.

    --- Quote End ---

    At first sight, the code can't synthesize due to various errors related to the incorrect handling of numeric types.

    Next problem is, that integer or natural are restricted to 32 bits in most VHDL implementations, e.g. Quartus or ModelSim, So you won't never get a correct result of 41 bit length.

    But the serious problem is, that recursion depth isn't restricted in a way, that could be recognized by the design compiler. If you let Quartus try to compile the code (after editing the syntax errors and ignoring the result length issue), you get this:

    Error (10493): VHDL Function Call or Procedure Call Statement error at hermitePolynomial_2.vhd(20): calls to function or procedure "Her" caused stack overflow

    That's pretty reasonable when trying to synthesize an effictively infinite number of subprogram instances!

    I see, that you have restricted d to 15 in the input. But because you change it to natural, the compiler can't "see" this restriction. Furthermore even d=15 would be too much for synthesis considering the quadratic growth of recursion, but it's somewhat more finite.

    The basic point is, that recursion in HDL means generating parallel logic instances. So although it's generally allowed for subprograms, it's only meaningful for special cases.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    Looking at your code, it is quite clear you are trying to treat VHDL as if it were software. It is not. Think about the logic you need before trying to describe it in code.

    A couple of points show this : your attempted use of recursion, and trying to complete everything in a single clock cycle.

    In Digital logic you need to pipeline functions like this. As a general rule, you can only complete a single arithmetic function (like add, multiply) per clock cycle, but you can run many functions of these in parrallel. You are trying to complete many multiplies and adds in series within a single clock cycle.

    Id step back and reasses your logic design. Try and draw it on paper or in visio before writing the VHDL.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    --- Quote Start ---

    your attempted use of recursion, and trying to complete everything in a single clock cycle.

    --- Quote End ---

    A good point about the limited use of recursive subprograms. "Calling" a subprogram recursively can never infer registers respectively pipelined operation.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    Thank you very much, Tricky. This is the first time I get real technical solutions. I understand your explanations.

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    Tricky, now only I understood the real problem of digital system. If I want to implement it in multiple clock cycles, how can I do it? could you please give me any examples which does the task similar to what I was trying to do? so that I can understand more.

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    --- Quote Start ---

    At first sight, the code can't synthesize due to various errors related to the incorrect handling of numeric types.

    Next problem is, that integer or natural are restricted to 32 bits in most VHDL implementations, e.g. Quartus or ModelSim, So you won't never get a correct result of 41 bit length.

    But the serious problem is, that recursion depth isn't restricted in a way, that could be recognized by the design compiler. If you let Quartus try to compile the code (after editing the syntax errors and ignoring the result length issue), you get this:

    Error (10493): VHDL Function Call or Procedure Call Statement error at hermitePolynomial_2.vhd(20): calls to function or procedure "Her" caused stack overflow

    That's pretty reasonable when trying to synthesize an effictively infinite number of subprogram instances!

    I see, that you have restricted d to 15 in the input. But because you change it to natural, the compiler can't "see" this restriction. Furthermore even d=15 would be too much for synthesis considering the quadratic growth of recursion, but it's somewhat more finite.

    The basic point is, that recursion in HDL means generating parallel logic instances. So although it's generally allowed for subprograms, it's only meaningful for special cases.

    --- Quote End ---

    @FvM: Thank you very much. Now, I realize I got to go for a long way to reach real VHDL programming.

    Could you please give me the edited code? so that I can refer it.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    heres a quick example: f = (a * b) + (c * d). It has a latency of 2 clock cycles (ie. result F appears 2 clocks after A,B,C and D inputs. You can put in 1 input every clock cycle, and result is produced every clock cycle) 

    
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity func is
  port (
    clk        : in  std_logic;
    
    a,b,c,d    : in  unsigned(7 downto 0);
    
    f          : out unsigned(16 downto 0)
  );
  
end entity func;
  
architecture rtl of func is 
  signal AxB, CxD : unsigned(15 downto 0);       
begin
  
  process(clk)
  begin
    if rising_edge(clk) then
      
      AxB  <= a*b;
      CxD  <= c*d;
      
      f    <= ('0' & AxB) + ('0' & CxD);      
    end if;
  end process;
  
  
end architecture rtl;
    And heres the circuit diagram:
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    --- Quote Start ---

    heres a quick example: f = (a * b) + (c * d). It has a latency of 2 clock cycles (ie. result F appears 2 clocks after A,B,C and D inputs. You can put in 1 input every clock cycle, and result is produced every clock cycle) 

    
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity func is
  port (
    clk        : in  std_logic;
    
    a,b,c,d    : in  unsigned(7 downto 0);
    
    f          : out unsigned(16 downto 0)
  );
  
end entity func;
  
architecture rtl of func is 
  signal AxB, CxD : unsigned(15 downto 0);       
begin
  
  process(clk)
  begin
    if rising_edge(clk) then
      
      AxB  <= a*b;
      CxD  <= c*d;
      
      f    <= ('0' & AxB) + ('0' & CxD);      
    end if;
  end process;
  
  
end architecture rtl;
    And heres the circuit diagram:

    --- Quote End ---

    Tricky,

    I simply got the point. So nicely explained. I really thank you.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    --- Quote Start ---

    Please notice, that only the obvious syntax errors are corrected.

    I should add a comment on the recursion problem. When executing a sequential computer program, the number of recursions is determined at run time, depending on the actual data. In hardware design, the maximum number of recursions must be known at compile time to generate the logic for it.

    I added a constant parameter to the function to clarify the maximum number of recursions. hermitePolynomial_3.vhd is the respective text. Then Quartus doesn't run immediately into a stack error. But Quartus may be still unable to compile the design because the involved parallel logic is too complex. With d_max = 7, about 15k LEs are consumed, I didn't want to try for larger numbers.

    Besides huge logic cell consumption, the problem of missing pipeline registers can't be solved by the recurcsive description, I fear. With d_max = 7, a delay of about 70 ns with Cyclone III is calculated by the timing analyzer.

    --- Quote End ---

    FvM,

    Thanks a lot for your attention to my question and for your explanation + code. I'll refer it and try to modify my work.