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.
Answer
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
No comments:
Post a Comment