Wednesday 23 December 2015

Real valued FFT in Matlab


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

readings - Appending 内 to a company name is read ない or うち?

For example, if I say マイクロソフト内のパートナーシップは強いです, is the 内 here read as うち or ない? Answer 「内」 in the form: 「Proper Noun + 内」 is always read 「ない...