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.

fft_rec(x)
function y = fft_rec(x)
% This custom function is a recursive implementation of the
% Decimation-In-Time (DIT), radix-2 FFT.
% It comes from the paper by Stefan Worner 
% "Fast Fourier Transform. Numerical Analysis Seminar", ETH Zurich.

N = length(x);

if N == 1
    y = x;
else
    m = N/2;
    y_top       = fft_rec(x(1:2:(N-1)));
    y_bottom = fft_rec(x(2:2:N));
    d = exp(-2*pi*1i/N) .^ (0:m-1);
    z = d.*y_bottom;
    y = [ y_top + z , y_top - z ];
end

Contact us