Calculate the sum of DFT by naive and recurrence methods
Calculate the sum of DFT by naive and recurrence methods
Create input data
Create input data
(Local) In[]:=
gN_samples=4096;(*totalsamplelength*)
gN=256;(*DFTblocklength*)
(Local) In[]:=
gNoises=RandomVariate[NormalDistribution[0,1],gN_samples];
(Local) In[]:=
gSamples=RecurrenceFilter[{{1,1.3435,0.9025},{1}},gNoises];
ListLinePlot[gSamples[[1;;256]],PlotLabel->"samples (head 256 samples)"]
(Local) Out[]=
Naive method
Naive method
(Local) In[]:=
dft_sum_naive=Sum[Fourier[Reverse[gSamples][[1+i;;i+gN]],FourierParameters->{0,-1}],{i,0,gN_samples-gN}]/(gN_samples-gN+1);
ListLogPlot[{Re[dft_sum_naive],Im[dft_sum_naive],Abs[dft_sum_naive]},PlotRange->Full,Joined->True,PlotLabel->"DFT sum (naive method)",PlotLegends->{"Re","Im","Abs"}]
(Local) Out[]=
Recurrence method
Recurrence method
(Local) In[]:=
RecurrenceDft[samples_,Lblk_]:=Block[{dft,i,N_samples=Length[samples],samples_rev=Reverse[samples],vec_w,dft_sum},dft=Fourier[samples_rev[[1+N_samples-Lblk;;N_samples]],FourierParameters->{0,-1}];(*initialFFTforoldestdata*)dft_sum=dft;(*recursion*)vec_w=Table[Exp[-I*k*2Pi/Lblk],{k,0,Lblk-1}];For[i=N_samples-Lblk-1,i>=0,--i,dft=vec_w*dft+(samples_rev[[1+i]]-samples_rev[[1+i+Lblk]])/Sqrt[Lblk];dft_sum+=dft;];dft_sum/(N_samples-Lblk+1)]
(Local) In[]:=
dft_sum_rec=RecurrenceDft[gSamples,gN];
ListLogPlot[{Re[dft_sum_rec],Im[dft_sum_rec],Abs[dft_sum_rec]},PlotRange->Full,Joined->True,PlotLabel->"DFT (recursive)",PlotLegends->{"Re","Im","Abs"}]
(Local) Out[]=
Comparison
Comparison
ListLogPlot[Abs[dft_sum_rec-dft_sum_naive],Joined->True,PlotRange->Full]
(Local) Out[]=
