1
\$\begingroup\$

I built an FFT module for an 128-point FFT in VHDL. When I use the same principle for 8-point fft or 16-point fft (ofcourse then the file must be altered for less stages and different twiddle factors), the FFT result is perfectly fine. But when applying my 128-point, the complex components are messed up and incorrect.

I honestly have no clue why this is the case, I tried so much, increasing the size of my fixed point for example, but nothing yielded in the desired result.

I had the same setup first with real numbers rather than the fixed point implementation, but that is ofcourse not synthesizable.

I'm honouring this butterfly diagram, but corrected for 128-point and with those twiddle factors: https://www.researchgate.net/publication/2982495/figure/fig2/AS:394654890643462@1471104466217/Signal-flow-graph-of-an-8-point-DIT-FFT.png

My Butterfly module:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

library work;
use work.fft_pkg.ALL;

entity butterfly is
   port(
      s1,s2 : in complex;      --inputs
      w :in complex;      -- phase factor
      g1,g2 :out complex      -- outputs
   );
end butterfly;

architecture Behavioral of butterfly is

begin

--butterfly equations.
g1 <= add(s1,mult(s2,w));
g2 <= sub(s1,mult(s2,w));

end Behavioral;

My fft package: (based on https://vhdlguru.blogspot.com/2011/06/non-synthesisable-vhdl-code-for-8-point.html)

library IEEE;
use IEEE.std_logic_1164.all;
use ieee.numeric_std.all;

library ieee_proposed;
use ieee_proposed.fixed_pkg.all;

package fft_pkg is

    type complex is
         record
              r : sfixed(16 downto -12);
              i : sfixed(16 downto -12);
         end record;

    type complex_array_256 is array (0 to 255) of complex;
    type complex_array_128 is array (0 to 127) of complex;
    type complex_array_64 is array (0 to 63) of complex;
    type complex_array_32 is array (0 to 31) of complex;
    type complex_array_16 is array (0 to 15) of complex;
    type complex_array_8 is array (0 to 7) of complex;
    type complex_array_4 is array (0 to 3) of complex;

    function add (n1,n2 : complex) return complex;
    function sub (n1,n2 : complex) return complex;
    function mult (n1,n2 : complex) return complex;    
end fft_pkg;

package body fft_pkg is

    --addition of complex numbers
    function add (n1,n2 : complex) return complex is
        variable sum : complex;

        begin
        sum.r:=resize(n1.r + n2.r, 16, -12);
        sum.i:=resize(n1.i + n2.i, 16, -12);
        return sum;
    end add;

    --subtraction of complex numbers.
    function sub (n1,n2 : complex) return complex is

        variable diff : complex;

        begin
        diff.r:=resize(n1.r - n2.r, 16, -12);
        diff.i:=resize(n1.i - n2.i, 16, -12);
        return diff;
    end sub;

    --multiplication of complex numbers.
    function mult (n1,n2 : complex) return complex is

        variable prod : complex;

        begin
        prod.r:= resize((n1.r * n2.r) - (n1.i * n2.i), 16, -12);
        prod.i:= resize((n1.r * n2.i) + (n1.i * n2.r), 16, -12);
        return prod;
    end mult;
end fft_pkg; 

My FFT module: (I had to remove some lines to fit the length, let me know if / how I can show the full code somewhere)

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

library ieee_proposed;
use ieee_proposed.fixed_pkg.all;

library work;
use work.fft_pkg.ALL;

entity FFT128 is
    Port (
        x : in complex_array_128;
        Y: out complex_array_128
    );
end FFT128;


architecture Behavioral of FFT128 is

    constant const_N : integer := 128;

    signal s_1 : complex_array_128 := (others => ((others => '0'), (others => '0')));
    signal s_2 : complex_array_128 := (others => ((others => '0'), (others => '0')));
    signal s_3 : complex_array_128 := (others => ((others => '0'), (others => '0')));
    signal s_4 : complex_array_128 := (others => ((others => '0'), (others => '0')));
    signal s_5 : complex_array_128 := (others => ((others => '0'), (others => '0')));
    signal s_6 : complex_array_128 := (others => ((others => '0'), (others => '0')));
    signal s_7 : complex_array_128 := (others => ((others => '0'), (others => '0')));


    --  W_N^k = cos(2*pi*k/N) - j * sin(2*pi*k/N)
    constant W : complex_array_64 := (
        (to_sfixed(1.0, 16, -12),to_sfixed(0.0, 16, -12)), 
        (to_sfixed(0.9988, 16, -12),to_sfixed(-0.0491, 16, -12)), 
        (to_sfixed(0.9952, 16, -12),to_sfixed(-0.098, 16, -12)), 
        (to_sfixed(0.9892, 16, -12),to_sfixed(-0.1467, 16, -12)), 
        (to_sfixed(0.9808, 16, -12),to_sfixed(-0.1951, 16, -12)), 
        (to_sfixed(0.97, 16, -12),to_sfixed(-0.243, 16, -12)), 
        (to_sfixed(0.9569, 16, -12),to_sfixed(-0.2903, 16, -12)), 
        (to_sfixed(0.9415, 16, -12),to_sfixed(-0.3369, 16, -12)), 
        (to_sfixed(0.9239, 16, -12),to_sfixed(-0.3827, 16, -12)), 
        (to_sfixed(0.904, 16, -12),to_sfixed(-0.4276, 16, -12)), 
        (to_sfixed(0.8819, 16, -12),to_sfixed(-0.4714, 16, -12)), 
        (to_sfixed(0.8577, 16, -12),to_sfixed(-0.5141, 16, -12)), 
        (to_sfixed(0.8315, 16, -12),to_sfixed(-0.5556, 16, -12)), 
        (to_sfixed(0.8032, 16, -12),to_sfixed(-0.5957, 16, -12)), 
        (to_sfixed(0.773, 16, -12),to_sfixed(-0.6344, 16, -12)), 
        (to_sfixed(0.741, 16, -12),to_sfixed(-0.6716, 16, -12)), 
        (to_sfixed(0.7071, 16, -12),to_sfixed(-0.7071, 16, -12)), 
        (to_sfixed(0.6716, 16, -12),to_sfixed(-0.741, 16, -12)), 
        (to_sfixed(0.6344, 16, -12),to_sfixed(-0.773, 16, -12)), 
        (to_sfixed(0.5957, 16, -12),to_sfixed(-0.8032, 16, -12)), 
        (to_sfixed(0.5556, 16, -12),to_sfixed(-0.8315, 16, -12)), 
        (to_sfixed(0.5141, 16, -12),to_sfixed(-0.8577, 16, -12)), 
        (to_sfixed(0.4714, 16, -12),to_sfixed(-0.8819, 16, -12)), 
        (to_sfixed(0.4276, 16, -12),to_sfixed(-0.904, 16, -12)), 
        (to_sfixed(0.3827, 16, -12),to_sfixed(-0.9239, 16, -12)), 
        (to_sfixed(0.3369, 16, -12),to_sfixed(-0.9415, 16, -12)), 
        (to_sfixed(0.2903, 16, -12),to_sfixed(-0.9569, 16, -12)), 
        (to_sfixed(0.243, 16, -12),to_sfixed(-0.97, 16, -12)), 
        (to_sfixed(0.1951, 16, -12),to_sfixed(-0.9808, 16, -12)), 
        (to_sfixed(0.1467, 16, -12),to_sfixed(-0.9892, 16, -12)), 
        (to_sfixed(0.098, 16, -12),to_sfixed(-0.9952, 16, -12)), 
        (to_sfixed(0.0491, 16, -12),to_sfixed(-0.9988, 16, -12)), 
        (to_sfixed(0.0, 16, -12),to_sfixed(-1.0, 16, -12)), 
        (to_sfixed(-0.0491, 16, -12),to_sfixed(-0.9988, 16, -12)), 
        (to_sfixed(-0.098, 16, -12),to_sfixed(-0.9952, 16, -12)), 
        (to_sfixed(-0.1467, 16, -12),to_sfixed(-0.9892, 16, -12)), 
        (to_sfixed(-0.1951, 16, -12),to_sfixed(-0.9808, 16, -12)), 
        (to_sfixed(-0.243, 16, -12),to_sfixed(-0.97, 16, -12)), 
        (to_sfixed(-0.2903, 16, -12),to_sfixed(-0.9569, 16, -12)), 
        (to_sfixed(-0.3369, 16, -12),to_sfixed(-0.9415, 16, -12)), 
        (to_sfixed(-0.3827, 16, -12),to_sfixed(-0.9239, 16, -12)), 
        (to_sfixed(-0.4276, 16, -12),to_sfixed(-0.904, 16, -12)), 
        (to_sfixed(-0.4714, 16, -12),to_sfixed(-0.8819, 16, -12)), 
        (to_sfixed(-0.5141, 16, -12),to_sfixed(-0.8577, 16, -12)), 
        (to_sfixed(-0.5556, 16, -12),to_sfixed(-0.8315, 16, -12)), 
        (to_sfixed(-0.5957, 16, -12),to_sfixed(-0.8032, 16, -12)), 
        (to_sfixed(-0.6344, 16, -12),to_sfixed(-0.773, 16, -12)), 
        (to_sfixed(-0.6716, 16, -12),to_sfixed(-0.741, 16, -12)), 
        (to_sfixed(-0.7071, 16, -12),to_sfixed(-0.7071, 16, -12)), 
        (to_sfixed(-0.741, 16, -12),to_sfixed(-0.6716, 16, -12)), 
        (to_sfixed(-0.773, 16, -12),to_sfixed(-0.6344, 16, -12)), 
        (to_sfixed(-0.8032, 16, -12),to_sfixed(-0.5957, 16, -12)), 
        (to_sfixed(-0.8315, 16, -12),to_sfixed(-0.5556, 16, -12)), 
        (to_sfixed(-0.8577, 16, -12),to_sfixed(-0.5141, 16, -12)), 
        (to_sfixed(-0.8819, 16, -12),to_sfixed(-0.4714, 16, -12)), 
        (to_sfixed(-0.904, 16, -12),to_sfixed(-0.4276, 16, -12)), 
        (to_sfixed(-0.9239, 16, -12),to_sfixed(-0.3827, 16, -12)), 
        (to_sfixed(-0.9415, 16, -12),to_sfixed(-0.3369, 16, -12)), 
        (to_sfixed(-0.9569, 16, -12),to_sfixed(-0.2903, 16, -12)), 
        (to_sfixed(-0.97, 16, -12),to_sfixed(-0.243, 16, -12)), 
        (to_sfixed(-0.9808, 16, -12),to_sfixed(-0.1951, 16, -12)), 
        (to_sfixed(-0.9892, 16, -12),to_sfixed(-0.1467, 16, -12)), 
        (to_sfixed(-0.9952, 16, -12),to_sfixed(-0.098, 16, -12)), 
        (to_sfixed(-0.9988, 16, -12),to_sfixed(-0.0491, 16, -12))
    );

    constant const_div : complex := (to_sfixed(0.00781, 16, -12), (others => '0'));


    component butterfly is
        port(
            s1,s2 : in complex;         --inputs
            w :in complex;              -- phase factor
            g1,g2 :out complex          -- outputs
        );
    end component;  
begin
    
    --Stage 1
    bf_1_0 : butterfly port map(x(0), x(64), W(0), s_2(0), s_2(1));
    bf_1_1 : butterfly port map(x(32), x(96), W(0), s_2(2), s_2(3));
    bf_1_2 : butterfly port map(x(16), x(80), W(0), s_2(4), s_2(5));
    bf_1_3 : butterfly port map(x(48), x(112), W(0), s_2(6), s_2(7));
    bf_1_4 : butterfly port map(x(8), x(72), W(0), s_2(8), s_2(9));
    bf_1_5 : butterfly port map(x(40), x(104), W(0), s_2(10), s_2(11));
    bf_1_6 : butterfly port map(x(24), x(88), W(0), s_2(12), s_2(13));
    bf_1_7 : butterfly port map(x(56), x(120), W(0), s_2(14), s_2(15));
    bf_1_8 : butterfly port map(x(4), x(68), W(0), s_2(16), s_2(17));
    [redacted for length reasons]
    bf_1_58 : butterfly port map(x(23), x(87), W(0), s_2(116), s_2(117));
    bf_1_59 : butterfly port map(x(55), x(119), W(0), s_2(118), s_2(119));
    bf_1_60 : butterfly port map(x(15), x(79), W(0), s_2(120), s_2(121));
    bf_1_61 : butterfly port map(x(47), x(111), W(0), s_2(122), s_2(123));
    bf_1_62 : butterfly port map(x(31), x(95), W(0), s_2(124), s_2(125));
    bf_1_63 : butterfly port map(x(63), x(127), W(0), s_2(126), s_2(127));
    --Stage 2
    bf_2_0 : butterfly port map(s_2(0), s_2(2), W(0), s_3(0), s_3(2));
    bf_2_1 : butterfly port map(s_2(1), s_2(3), W(32), s_3(1), s_3(3));
    bf_2_2 : butterfly port map(s_2(4), s_2(6), W(0), s_3(4), s_3(6));
    bf_2_3 : butterfly port map(s_2(5), s_2(7), W(32), s_3(5), s_3(7));
    bf_2_4 : butterfly port map(s_2(8), s_2(10), W(0), s_3(8), s_3(10));
    bf_2_5 : butterfly port map(s_2(9), s_2(11), W(32), s_3(9), s_3(11));
    bf_2_6 : butterfly port map(s_2(12), s_2(14), W(0), s_3(12), s_3(14));
    bf_2_7 : butterfly port map(s_2(13), s_2(15), W(32), s_3(13), s_3(15));
    bf_2_8 : butterfly port map(s_2(16), s_2(18), W(0), s_3(16), s_3(18));
    bf_2_9 : butterfly port map(s_2(17), s_2(19), W(32), s_3(17), s_3(19));
    bf_2_10 : butterfly port map(s_2(20), s_2(22), W(0), s_3(20), s_3(22));
    [redacted for length reasons]
    bf_2_59 : butterfly port map(s_2(117), s_2(119), W(32), s_3(117), s_3(119));
    bf_2_60 : butterfly port map(s_2(120), s_2(122), W(0), s_3(120), s_3(122));
    bf_2_61 : butterfly port map(s_2(121), s_2(123), W(32), s_3(121), s_3(123));
    bf_2_62 : butterfly port map(s_2(124), s_2(126), W(0), s_3(124), s_3(126));
    bf_2_63 : butterfly port map(s_2(125), s_2(127), W(32), s_3(125), s_3(127));
    --Stage 3
    bf_3_0 : butterfly port map(s_3(0), s_3(4), W(0), s_4(0), s_4(4));
    bf_3_1 : butterfly port map(s_3(1), s_3(5), W(16), s_4(1), s_4(5));
    bf_3_2 : butterfly port map(s_3(2), s_3(6), W(32), s_4(2), s_4(6));
    bf_3_3 : butterfly port map(s_3(3), s_3(7), W(48), s_4(3), s_4(7));
    bf_3_4 : butterfly port map(s_3(8), s_3(12), W(0), s_4(8), s_4(12));
   [redacted for length reasons]
    bf_3_59 : butterfly port map(s_3(115), s_3(119), W(48), s_4(115), s_4(119));
    bf_3_60 : butterfly port map(s_3(120), s_3(124), W(0), s_4(120), s_4(124));
    bf_3_61 : butterfly port map(s_3(121), s_3(125), W(16), s_4(121), s_4(125));
    bf_3_62 : butterfly port map(s_3(122), s_3(126), W(32), s_4(122), s_4(126));
    bf_3_63 : butterfly port map(s_3(123), s_3(127), W(48), s_4(123), s_4(127));
    --Stage 4
    bf_4_0 : butterfly port map(s_4(0), s_4(8), W(0), s_5(0), s_5(8));
    bf_4_1 : butterfly port map(s_4(1), s_4(9), W(8), s_5(1), s_5(9));
    bf_4_2 : butterfly port map(s_4(2), s_4(10), W(16), s_5(2), s_5(10));
    bf_4_3 : butterfly port map(s_4(3), s_4(11), W(24), s_5(3), s_5(11));
    bf_4_4 : butterfly port map(s_4(4), s_4(12), W(32), s_5(4), s_5(12));
    bf_4_5 : butterfly port map(s_4(5), s_4(13), W(40), s_5(5), s_5(13));
    [redacted for length reasons]
    bf_4_59 : butterfly port map(s_4(115), s_4(123), W(24), s_5(115), s_5(123));
    bf_4_60 : butterfly port map(s_4(116), s_4(124), W(32), s_5(116), s_5(124));
    bf_4_61 : butterfly port map(s_4(117), s_4(125), W(40), s_5(117), s_5(125));
    bf_4_62 : butterfly port map(s_4(118), s_4(126), W(48), s_5(118), s_5(126));
    bf_4_63 : butterfly port map(s_4(119), s_4(127), W(56), s_5(119), s_5(127));
    --Stage 5
    bf_5_0 : butterfly port map(s_5(0), s_5(16), W(0), s_6(0), s_6(16));
    bf_5_1 : butterfly port map(s_5(1), s_5(17), W(4), s_6(1), s_6(17));
    bf_5_2 : butterfly port map(s_5(2), s_5(18), W(8), s_6(2), s_6(18));
   [redacted for length reasons]
    bf_5_59 : butterfly port map(s_5(107), s_5(123), W(44), s_6(107), s_6(123));
    bf_5_60 : butterfly port map(s_5(108), s_5(124), W(48), s_6(108), s_6(124));
    bf_5_61 : butterfly port map(s_5(109), s_5(125), W(52), s_6(109), s_6(125));
    bf_5_62 : butterfly port map(s_5(110), s_5(126), W(56), s_6(110), s_6(126));
    bf_5_63 : butterfly port map(s_5(111), s_5(127), W(60), s_6(111), s_6(127));
    --Stage 6
    bf_6_0 : butterfly port map(s_6(0), s_6(32), W(0), s_7(0), s_7(32));
    bf_6_1 : butterfly port map(s_6(1), s_6(33), W(2), s_7(1), s_7(33));
    bf_6_2 : butterfly port map(s_6(2), s_6(34), W(4), s_7(2), s_7(34));
    bf_6_3 : butterfly port map(s_6(3), s_6(35), W(6), s_7(3), s_7(35));
    [redacted for length reasons]
    bf_6_58 : butterfly port map(s_6(90), s_6(122), W(52), s_7(90), s_7(122));
    bf_6_59 : butterfly port map(s_6(91), s_6(123), W(54), s_7(91), s_7(123));
    bf_6_60 : butterfly port map(s_6(92), s_6(124), W(56), s_7(92), s_7(124));
    bf_6_61 : butterfly port map(s_6(93), s_6(125), W(58), s_7(93), s_7(125));
    bf_6_62 : butterfly port map(s_6(94), s_6(126), W(60), s_7(94), s_7(126));
    bf_6_63 : butterfly port map(s_6(95), s_6(127), W(62), s_7(95), s_7(127));
    --Stage 7
    bf_7_0 : butterfly port map(s_7(0), s_7(64), W(0), Y(0), Y(64));
    bf_7_1 : butterfly port map(s_7(1), s_7(65), W(1), Y(1), Y(65));
    bf_7_2 : butterfly port map(s_7(2), s_7(66), W(2), Y(2), Y(66));
    bf_7_3 : butterfly port map(s_7(3), s_7(67), W(3), Y(3), Y(67));
    bf_7_4 : butterfly port map(s_7(4), s_7(68), W(4), Y(4), Y(68));
    [redacted for length reasons]
    bf_7_58 : butterfly port map(s_7(58), s_7(122), W(58), Y(58), Y(122));
    bf_7_59 : butterfly port map(s_7(59), s_7(123), W(59), Y(59), Y(123));
    bf_7_60 : butterfly port map(s_7(60), s_7(124), W(60), Y(60), Y(124));
    bf_7_61 : butterfly port map(s_7(61), s_7(125), W(61), Y(61), Y(125));
    bf_7_62 : butterfly port map(s_7(62), s_7(126), W(62), Y(62), Y(126));
    bf_7_63 : butterfly port map(s_7(63), s_7(127), W(63), Y(63), Y(127));




end Behavioral;

As you can see, I have quite a large size for the fixed point values but that was just to test, and even with such large sizes my imaginary part is incorrect all the time. Often the sign is incorrect as well, so not just off by a few numbers. Any suggestions to what it might be?

I'm not even sure this is the best way to approach my issue at all so any suggestions are welcome!

I'm trying to learn here, the first time I'm applying FPGA and right away the assignment is quite hard.

\$\endgroup\$
3
  • \$\begingroup\$ 1 - have you tried your code work in Matlab/Python/C? Does it work? 2 - You don't even have a clock, you can implement asynchronous logic in an FPGA, but typically we use synchronous logic. 3 - what do you mean your imaginary values are incorrect? You mean for the twiddle factors or for the outputs? You know how 2's complement works? \$\endgroup\$
    – Ben
    Aug 3, 2023 at 17:47
  • \$\begingroup\$ I have tried my "code" in modelsim, booted from the Xilinx ISE. I have tried my full implementation using the "real" type rather than sfixed before and all of that worked fine. When changing to sfixed, things went south. What I mean with incorrect imaginary values is that once I apply an FFT, I end up with complex numbers of which, using calculations from Python, the imaginary part seems to be totally the wrong numbers in modelsim. So that indicates to me that something is wrong with this implementation yielding incorrect calculations \$\endgroup\$
    – Mart
    Aug 4, 2023 at 6:47
  • 1
    \$\begingroup\$ The resize function calls encapsulating the "+" and "-" operands in the functions add and sub in package fft_pkg will limit precision that can affect the results based on the number of successive operations. For fixed point arithmetic you either need to plan for changes in precision or increase the size to handle the precision needed. There's also the use of float_pkg where you can define a custom float. \$\endgroup\$ Aug 7, 2023 at 10:45

1 Answer 1

0
\$\begingroup\$

In VHDL, it is import to see the difference between hardware description and coding. One of it, is it doesn't always scale the way we think it will. When doing the synthesis, it will try to fit your design inside the FPGA. For instance, if on the 16 bit design, it fits inside the complex number module, it might work perfectly, but it is impossible to make it fit if you have 128 bits. (sorry, it's been a while, I don't remember the exact terminology).

Also, remember that the complexity of the FFT is exponential. The greater that circuit, the longer are the delays inside your FPGA. Maybe, you need to place more buffers in your intermediate steps.

When doing FPGA, the most important thing to remember is that VHDL is not programming. You need to understand how the software converts your code in hardware. What modules or block are used, where the connections are routed and how it will impact performance, which memory sector is used, and so on.

The tools that you want to use to debug VHDL in hardware is a logic analyzer. The more bits the better. You can get a single bit as a flag, or combine a few to give you some register value. Otherwise, it is very hard to debug. 8 channels LA are often not sufficient. I think 16 is the minimum since you'll want a few flag, maybe a few bit from your state machine and a 8 bit for a value. Using two cheap 8 bit LA can work, but you might have timing issue between them. Old logic analyzers are perfect for learning and can be found quite cheap on ebay (if you want to do more dev).

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your help so far! the thing is, this is just in simulation and even there I cannot get it to work unfortunately \$\endgroup\$
    – Mart
    Aug 3, 2023 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.