butterfly in fft not working...............

[nehsr]

Hello,

My fast fourier transform's butterfly is not giving me the appropriate results when simulating, can anyone please help me with it?..... the codes are as follows:

---

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
library IEEE; -- library name and library use clause
use IEEE.std_logic_1164.all; -- specifies multi level logic system 
use IEEE.MATH_REAL.ALL;
 
package fft_pkg is
 
type complex is 
    record
        r : real;
        i : real;
    end record;
 
type comp_array is array (0 to 7) of complex;
type comp_array2 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:=n1.r + n2.r;
sum.i:=n1.i + n2.i;
return sum;
end add;
 
--subtraction of complex numbers.
function sub (n1,n2 : complex) return complex is
 
variable diff : complex;
 
begin 
diff.r:=n1.r - n2.r;
diff.i:=n1.i - n2.i;
return diff;
end sub;
 
--multiplication of complex numbers.
function mult (n1,n2 : complex) return complex is
 
variable prod : complex;
 
begin 
prod.r:=(n1.r * n2.r) - (n1.i * n2.i);
prod.i:=(n1.r * n2.i) + (n1.i * n2.r);
return prod;
end mult;
 
end fft_pkg;
 
 
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.MATH_REAL.ALL;
library work;
use work.fft_pkg.ALL;
 
 
 
entity fft8 is
port(   s : in comp_array; --input signals in time domain
        x3 : out comp_array  --output signals in frequency domain
        );
end fft8;
 
architecture Behavioral of fft8 is
 
component butterfly is 
   port(
      s1,s2: in complex;      --inputs
      w :in complex;      -- phase factor
      x1,x2 :out complex      -- outputs
   );
end component;  
signal x1,x2: comp_array := (others => (0.0,0.0));    
--phase factor, W_N = e^(-j*2*pi/N)  and N=8 here.
--W_N^i = cos(2*pi*i/N) - j*sin(2*pi*i/N);  and i has range from 0 to 7.
constant w : comp_array2 := ( (1.0,0.0), (0.7071,-0.7071), (0.0,-1.0), (-0.7071,-0.7071) );
begin
 
--first stage of butterfly's.
bf11 : butterfly port map(s(0),s(4),w(0),x1(0),x1(1));
bf12 : butterfly port map(s(2),s(6),w(0),x1(2),x1(3));
bf13 : butterfly port map(s(1),s(5),w(0),x1(4),x1(5));
bf14 : butterfly port map(s(3),s(7),w(0),x1(6),x1(7));
 
--second stage of butterfly's.
bf21 : butterfly port map(x1(0),x1(2),w(0),x2(0),x2(2));
bf22 : butterfly port map(x1(1),x1(3),w(2),x2(1),x2(3));
bf23 : butterfly port map(x1(4),x1(6),w(0),x2(4),x2(6));
bf24 : butterfly port map(x1(5),x1(7),w(2),x2(5),x2(7));
 
--third stage of butterfly's.
bf31 : butterfly port map(x2(0),x2(4),w(0),x3(0),x3(4));
bf32 : butterfly port map(x2(1),x2(5),w(1),x3(1),x3(5));
bf33 : butterfly port map(x2(2),x2(6),w(2),x3(2),x3(6));
bf34 : butterfly port map(x2(3),x2(7),w(3),x3(3),x3(7));
end Behavioral;
 
 
library IEEE;
use IEEE.STD_LOGIC_1164.all;
use IEEE.MATH_REAL.all;
library work;
use work.fft_pkg.all;
 
entity butterfly is
    port(
        s1        : in  complex;   --inputs
        w              : in  complex;   -- phase factor
        x1: out complex    -- outputs
        );
end butterfly;
 
architecture Behavioral of butterfly is
 
    signal xxx : integer := 0;
 
    type comp_array is array (0 to 7) of complex;
    type comp_array2 is array (0 to 3) of complex;
 
--  function add (x1, x2, x3  : comp_array) return comp_array;
--  function sub (x1, x2, x3  : comp_array) return comp_array;
--  function mult (x1, x2, x3 : comp_array) return comp_array;
 
    --butterfly equations.
 
    function sub (s, w : comp_array) return comp_array is
        variable diff : comp_array;
        variable x1   : comp_array;
        variable x2   : comp_array;
        variable x3   : comp_array;
 
    begin
        x1(1) := sub(s(0), mult(s(4), w(0)));
        x1(3) := sub(s(2), mult(s(6), w(0)));
        x1(5) := sub(s(1), mult(s(5), w(0)));
 
        --2nd stage equations:
        x2(2) := sub(x1(0), mult(x1(2), w(0)));
        x2(1) := sub(x1(1), mult(x1(3), w(2)));
        x2(4) := sub(x1(4), mult(x1(6), w(0)));
        x2(5) := sub(x1(5), mult(x1(7), w(2)));
 
        --3rd stage equations:
        x3(4) := sub(x2(0), mult(x2(4), w(0)));
        X3(5) := sub(x2(1), mult(x2(5), w(1)));
        x3(6) := sub(x2(2), mult(x2(6), w(2)));
        x3(7) := sub(x2(3), mult(x2(7), w(3)));
        return diff;
    end sub;
 
 
    --1st stage equations:
    function add (s, w : comp_array) return comp_array is
        variable sum : comp_array;
        variable x1  : comp_array;
        variable x2  : comp_array;
        variable x3  : comp_array;
 
    begin
        x1(0) := add(s(0), mult(s(4), w(0)));
        x1(2) := add(s(2), mult(s(6), w(0)));
        x1(4) := add(s(1), mult(s(5), w(0)));
        x1(6) := add(s(3), mult(s(7), w(0)));
        --2nd stage equations (sum):
        x2(0) := add(x1(0), mult(x1(2), w(0)));
        x2(3) := add(x1(1), mult(x1(3), w(2)));
        x2(6) := add(x1(4), mult(x1(6), w(0)));
        x2(7) := add(x1(5), mult(x1(7), w(2)));
        --3rd stage equations(sum):
        x3(0) := add(x2(0), mult(x2(4), w(0)));
        X3(1) := add(x2(1), mult(x2(5), w(1)));
        x3(2) := add(x2(2), mult(x2(6), w(2)));
        x3(3) := add(x2(3), mult(x2(7), w(3)));
        return sum;
    end add;
 
begin
 
--end process;
 
end Behavioral;

---

 

[TrickyDicky]

give us some more specific problems and we can help. you question sounds like - "I cant be bothered to work out the problem - can you do it for me?"

 

[nehsr]

if you take the code and simulate it, which in my case am using modelsim, the waveforms obtained are not the expected results which are expected....... its been two days i've been trying to figure out why : am not obtaining the appropriate results....... these results can be worked out from a calculator as such : (input a)+ w(input b), where a and b are the inputs in form of re and imaginary, and w is the twiddle factor........ however, my coding doesn't seem to let that happen......... i just want a fresh eye from somebody else onto that problem from my coding, and see if by any chance we can spot the flaw?........

 

[TrickyDicky]

Ok. My fresh eye:

THis is clearly a simulation model, because it is completly unsynthesisable and cannot be put onto an FPGA. You cannot use real type inside an FPGA. And even if you wanted to, wheres the clock?
Second - as its a simulation model - why not make it simple? All those buttfly mappings seem arbitrary and I have no idea what you're doing.
Finally: The butterfly entity does nothing. It has no processes, therefore nothing will happen.

 

[nehsr]

Many thanks tricky........ Is there anything i mean, any amendments i can implement to the butterfly entity so that i can get any kind of process?..... for example, i have an 's' as input in the entity, can i replace that with a clock and if so, what would be the amendments i'll need to make?.....

 

[TrickyDicky]

you need to read up on logic design and a vhdl tutorial.
a function needs to be called from a process.

 

[Oveis.Gharan]

Hi,
You should test your algorithm in MATLAB first and see whether the algorithm work properly.
Then modify the MATLAB algorithm from double(floating point) calculation to bit true (Fixed point) with proper data bus and coefficients wordlength. Then resimulate with MATLAB the algorithm. If all the calculations are correct and quantization noise which in every multiplier output truncation be injected are in acceptable range, then you could describe your hardware with HDL.
Have you followed the above flow yet?