Code covered by the BSD License  

Highlights from
Sprint Race for Fast Butterflies

image thumbnail

Sprint Race for Fast Butterflies

by

 

30 Jan 2013 (Updated )

Benchmarking of Various FFT Algorithm Implementations Based on Execution Time.

dif_fft(x)
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]:
for i=1:N/2
     g(i) = x(i) + x(i + N/2);
     h(i) = (x(i) - x(i + N/2))*exp(-1i*2*pi*(i-1)/N);
end

% Compute their N/2-point DFT:
G = fft(g);
H = fft(h);

X = zeros(1,N); 
for k=1:N/2     
     X(2*k)     = H(k);  % odd part
     X(2*k-1) = G(k);  % even part
end

Contact us