CODEWITHSUNDEEP
matlabfft
Flama
Flama

Reputation: 868

Implementing my own FFT in MATLAB giving wrong results

I'm trying to implement my own fft in MATLAB the following way:

function z=FastFourierTransform(x)
  N=length(x);
  if N <= 1
    z = x;
  else
    range = (0:N/2-1);
    e = exp(-2i*pi/N).^range;
    odd = FastFourierTransform(x(1:2:N-1));
    even = e.*FastFourierTransform(x(2:2:N));
    z = [even + odd, even - odd];
  end
return

Turns out, there seems to be somthing wrong with it since it does not give the same result as the built in function provided by MATLAB.

I'm calling the function the following way:

N = 128;
x = 32*pi*(1:N)'/N;
u = cos(x/16).*(1+sin(x/16));
actualSolution = fft(u);
actualSolution
mySolution = FastFourierTransform(u)';
mySolution

actualSolution

mySolution

The numbers are always the same but they sometimes differ in their sign.

Upvotes: 1

Views: 142

Answers (1)

Aziz
Aziz

Reputation: 20765

You have swapped odd and even.

Using this line to compute z will produce the correct FFT:

z = [odd + even, odd - even];

My guess is that the source of confusion is that Matlab uses 1-based indices, and the pseudocode you used to implement the function uses 0-based indices.

Upvotes: 2

Related Questions