Sprint Race for Fast Butterflies
30 Jan 2013
31 Jan 2013)
Benchmarking of Various FFT Algorithm Implementations Based on Execution Time.
function X = dif_fft(x)
% Radix-2, Decimation in Frequency (DIF) FFT Computation.
% Attention: 1) Length of input signal x should be a power of 2.
% 2) Only the first iteration of this algorithm is implemented here!
N = length(x);
g = zeros(1,N/2);
h = zeros(1,N/2);
% Create sequences g[n] and h[n]:
g(i) = x(i) + x(i + N/2);
h(i) = (x(i) - x(i + N/2))*exp(-1i*2*pi*(i-1)/N);
% Compute their N/2-point DFT:
G = fft(g);
H = fft(h);
X = zeros(1,N);
X(2*k) = H(k); % odd part
X(2*k-1) = G(k); % even part