1

I'm trying to compute FFT of size (N/2) for sequence of real values of length N. I'm using this recipe. Here is my code in matlab:

clear;
clc;
x = [1, 2, 3, 4, 5, 6, 7, 8];
n = length(x);
z = [1 + 2j, 3 + 4j, 5 + 6j, 7 + 8j];
Z = fft(z);
Fe = (Z + (conj(Z)))/2;
Fo = (-1j*(Z - (conj(Z))))/2;
for k = 1 : n/2-1
     F(k) = Fe(k) + exp(-1j * 2 * pi * ((k-1)/n)) * Fo(k);
end;
F(n/2) = 0.5*(Z(1) + conj(Z(1)) + 1i*(Z(1) - conj(Z(1))))
fft(x)

Obviously, I get wrong result (at least I think it's wrong). As far as I understand, first four terms of F and fft(x) should be equal.

The part that confuses me is when I compute Fe and Fo I'm using fliplr(conj()) to get Z(N/2) - k)*, I'm not sure, if it's the proper way to do this.

lennon310
  • 3,590
  • 19
  • 24
  • 27
B_T
  • 13
  • 1
  • 3

1 Answers1

4

You can do it like this. I think the code speaks for itself:

x = [1, 2, 3, 4, 5, 6, 7, 8];   % some real-valued signal
n = length(x);                  % must be even!
n2 = n/2;                       % assume n is even
z = x(1:2:n)+j*x(2:2:n);        % complex signal of length n/2
Z = fft(z);
Ze = .5*( Z + conj([Z(1),Z(n2:-1:2)]) );        % even part
Zo = -.5*j*( Z - conj([Z(1),Z(n2:-1:2)]) );     % odd part
X = [Ze,Ze(1)] + exp(-j*2*pi/n*(0:n2)).*[Zo,Zo(1)];  % combine
X2 = fft(x);
max(abs(X-X2(1:n2+1)))  % 2.4492e-15
Matt L.
  • 89,963
  • 9
  • 79
  • 179