DSPRelated.com
Code

FFT with down-sampling in time domain

Emmanuel November 9, 20102 comments Coded in Matlab

This code calculates the FFT by the down-sampling in time algorithm using Matlab. It is based on the butterfly equations.

clc, clear all, close all
N=128;
x=-1:2/128:1-2/128;
%number of stages
M=q_log2(N);
%to array elements in a proper way for the butterfly
for k=0:N-1;
    x1(k+1)=x(bi2de(fliplr(de2bi(k,M)))+1);
end
%to set up twiddle factors
for k=0:N/2-1;
    W(k+1)=exp(-1i*2*pi*k/N);
end
%entering to graph
%k holds the stage
for k=1:M;
    k2=2^k;
    k21=2^(k-1);
    Mk=2^(M-k);
    %l holds the butterfly
    for l=1:N/k2;
        %l=1:N/pow(2,k)
        %m holds the upper element of the butterfly
        for m=1:k21;
        op1 = x1((l-1)*(k2)+m);
        op2 = x1((l-1)*(k2)+m+k21);
        %butterfly equation
        x1((l-1)*(k2)+m) = op1+W(Mk*(m-1)+1)*op2;
        x1((l-1)*(k2)+m+k21) = op1-W(Mk*(m-1)+1)*op2;
        end
    end
end