FFT with down-sampling in time domain
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