资源描述
Cliquez pour modifier le style du titre du masque,Cliquez pour modifier les styles du texte du masque,Deuxime niveau,Troisime niveau,Quatrime niveau,Cinquime niveau,ESIEE,Slide,*,DSP C5000,Chapter 19,Fast Fourier Transform,Discrete Fourier Transform,Allows us to compute an approximation of the Fourier Transform on a discrete set of frequencies from a discrete set of time samples.,Where,k,are the index of the discrete frequencies and,n,the index of the time samples,Inverse Discrete Fourier Transform,The inverse formula,is:,Where,again,k,are the index of the discrete frequencies and,n,the index of the time samples.,We have the following properties:,Discrete time periodic spectra,Periodic time discrete spectra,DFT Computation,We can write the DFT:,We need:,N(N-1),complex,+,N,2,complex,Fast Fourier Transform 2 of 3,Using the following property:,The DFT can be rewritten:,For,k,=0,1,N-1,Fast Fourier Transform 3 of 3,Using the property that:,The entire DFT can be computed with only,k,=0,1,N/,2-1.,and,Butterfly,This leads to basic building block of the FFT,the,butterfly,.,TFD N/2,TFD N/2,x(0),x(2),x(N-2),x(1),x(3),x(N-1),X(0),X(1),X(N/2-1),X(N/2),X(N/2+1),X(N-1),W,0,W,1,W,N/2-1,-,-,-,We need:,N/2(N/2-1),complex,+for each,N/2,DFT.,(,N/2,),2,complex,for each DFT.,N/2,complex,at the input of the butterflies.,N,complex,+for the butter-flies.,Grand total:,N,2,/2,complex,+,N/2(N/2+1),complex,Number of Operations,If,N,=,2,r,we have,r=,log,2,(,N,)stages.For each one we have:,N/2,complex,(some of them are by 1).,N,complex+.,Thus the grand total of operations is:,N/2,log,2,(,N,),complex,.,N,log,2,(,N,),complex,+.,These counts can be compared with the ones for the DFT,Shuffling the Data,Bit Reverse Ordering,At each step of the algorithm,data are split between even and odd values.This results in scrambling the order.,Recursion of the algorithm,Algorithm Parameters 1 of 2,The FFT can be computed according to the following pseudo-code:,For each,stage,For each,group of butterfly,For each,butterfly,compute butterfly,end,end,end,Scaling,The DFT computation for each,k,is:,To prevent overflow we need to have:,This is guaranteed provided a scale factor,1/N,Quantization Noise,Quantization step is:,If words have,b+1,bits and,x(n),belongs to -1,1,If we assume that each real multiplication gives rise to a noise source of power,The total amount of noise power for each,X(k),is given by,Signal to Quantization Noise Ratio(SQNR)FFT case 1 of 3,The computation of one,X,(,k,)requires,N-1,butterflies:,x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7),X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),W,8,0,W,8,1,W,8,2,W,8,3,-,-,-,-,-,-,-,-,-,W,8,0,W,8,0,W,8,1,W,8,1,W,8,0,W,8,0,W,8,0,W,8,0,N/2 butterflies of the 1,st,stage,N/4 butterflies of the 2,nd,stage,1 butterfly of the last stage,Signal to Quantization Noise Ratio(SQNR)FFT case 2 of 3,Butterfly computation,To prevent overflow,we only need to scale the inputs of each butterfly by,1/2,X,n,(l),-,W,X,n,(k),X,n+1,(l),X,n+1,(k),X,n,(l),-,W,X,n,(k),X,n+1,(l),X,n+1,(k),1/2,1/2,Because we have,r,stages,the global scaling factor for one output is:,Signal to Quantization Noise Ratio(SQNR)FFT case 3 of 3,Quantization noise source at one stage is attenuated by scale factors of all the following stages.,This gives an equivalent noise source of:,for each output.,SQNR for FFT with scaling is given by:,16 bits per word,FFT Algorithm with Block Floating Point Scaling,Input data in bit reverse order,Set-up for next stage,Set-up for next group,Set-up for next butterfly,Scale inputs of butterfly(1/2),More butterflies?,More groups?,More stages?,End of algorithm,Compute butterfly,Case Study C54x,Use of audioFFT,*,(,*,)this program is the same as tiexamplesdsk5416biosaudio except for some slight modifications that will be emphazised when necessary,Block,processing,PCM3002 ADC,PCM3002 DAC,pipRx,pipTx,inBuffer,outBuffer,DSPLIB functions,The DSP Library(DSPLIB)is a collection of high-level optimized DSP function modules for the C54x and C55x DSP platform.,C54x DSPLIB functions for FFT computation,Block Processing 1 of 3,Echo,(),Include and declarations,Block Processing 2 of 3,Dsplib functions calls,Block Processing 3 of 3,Linker.cmd file,C54x DSPLIB FFT,To Change the Size of the Processing Buffer,Change buffer length declaration in,echo,function(audio.c),Change the call to,cfft,and,cifft,according to the size of the FFT(must be hard coded),Change buffer alignment in linker.cmd file,Follow on Activities for TMS320C5416 DSK,Application 8 for the the TMS320C5416 DSK uses the FFT as a spectrum analyzer to display the power in an audio signal at various frequencies.,Rather than using the optimized library DSPLIB for the FFT,it uses a C code version that is slower,but can be stepped through line by line using Code Composer Studio.,
展开阅读全文