%This demo illustrates the Divide and Conquer approach
%to computing an N pt DFT when N=ML, where M and L are
%integers. The N pt DFT is decomposed into L M-pt DFT's,
%followed by N multiplications (done in the same for loop),
%followed by M L-pt DFT's as per Sect. 6.1 in the Text
clear all
N=16; M=2; L=8;
%Here's where me make up the signal
x=randn(1,N);
%
for l=1:L,
X(l,:)=exp(-j*(l-1)*2*pi*(0:M-1)/N).*fft(x(1,l:L:N),M);
end
for p=1:M,
XT(:,p)=fft(X(:,p),L);
end
%
XT=XT.'; XN=XT(:).';
%Here's the N pt DFT computed directly (but note
%Matlab generally does this as efficiently as possible)
Xfft=fft(x,N);
%Look at difference to make sure they are the same
norm_diff1=norm(XN-Xfft)
%Let's now do Direct Computation of N-pt DFT to
%compare the number of floating point operations (FLOPS)
%temp=flops;
for k=0:N-1,
XD(1,k+1)=exp(-j*k*2*pi*(0:N-1)/N)*x.';
end
norm_diff2=norm(XN-XD)