Example: barber

Chapter 4 The FFT and Power Spectrum Estimation Contents

Chapter 4 The FFT and Power SpectrumEstimationContentsSlide 1 The Discrete-Time Fourier TransformSlide 2 Data Window FunctionsSlide 3 Rectangular Window Function (cont. 1)Slide 4 Rectangular Window Function (cont. 2)Slide 5 Normalization for Spectrum EstimationSlide 6 The Hamming Window FunctionSlide 7 Other Window FunctionsSlide 8 The DFT and IDFTS lide 9 DFT ExamplesSlide 10 The Inverse DFT (IDFT)Slide 11 The Fast Fourier Transform (FFT)Slide 11 Decimation in Time FFT AlgorithmSlide 12 Decimation in Time FFT (cont. 1)Slide 13 Decimation in Time FFT (cont. 2)Slide 14 Decimation in Time FFT (cont. 3)Slide 15 Decimation in Time FFT (cont. 4)Slide 16 Decimation in Time FFT (cont. 5)Slide 17 Decimation in Time FFT (cont. 6)Slide 17 Bit Reversed Input OrderingSlide 18C Decimation in Time FFT ProgramSlide 19C FFT Program (cont.)

Slide 26 Estimating Power Spectra by FFT’s Slide 26 The Periodogram and Sample Autocorrelation Function Slide 27 Justification for Using the Periodogram Slide 28 Averaging Periodograms Slide 29 Efficient Method for Computing the Sum of the Periodograms of Two Real Sequences Slide 30 Experiment 4.1 The FFT Slide 31 FFT Experiments (cont. 1)

Tags:

  Spectrum, Power, Estimating, Power spectrum, Estimating power

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Chapter 4 The FFT and Power Spectrum Estimation Contents

1 Chapter 4 The FFT and Power SpectrumEstimationContentsSlide 1 The Discrete-Time Fourier TransformSlide 2 Data Window FunctionsSlide 3 Rectangular Window Function (cont. 1)Slide 4 Rectangular Window Function (cont. 2)Slide 5 Normalization for Spectrum EstimationSlide 6 The Hamming Window FunctionSlide 7 Other Window FunctionsSlide 8 The DFT and IDFTS lide 9 DFT ExamplesSlide 10 The Inverse DFT (IDFT)Slide 11 The Fast Fourier Transform (FFT)Slide 11 Decimation in Time FFT AlgorithmSlide 12 Decimation in Time FFT (cont. 1)Slide 13 Decimation in Time FFT (cont. 2)Slide 14 Decimation in Time FFT (cont. 3)Slide 15 Decimation in Time FFT (cont. 4)Slide 16 Decimation in Time FFT (cont. 5)Slide 17 Decimation in Time FFT (cont. 6)Slide 17 Bit Reversed Input OrderingSlide 18C Decimation in Time FFT ProgramSlide 19C FFT Program (cont.)

2 1)Slide 20C FFT Program (cont. 2)Slide 21C FFT Program (cont. 3)Slide 22C FFT Program (cont. 4)Slide 23C FFT Program (cont. 5)Slide 24C FFT Program (cont. 6)Slide 25C FFT Program (cont. 7)Slide 26 estimating Power Spectra by FFT sSlide 26 The Periodogram and SampleAutocorrelation FunctionSlide 27 Justification for Using the PeriodogramSlide 28 Averaging PeriodogramsSlide 29 Efficient Method for Computing the Sumof the Periodograms of Two RealSequencesSlide 30 Experiment The FFTS lide 31 FFT Experiments (cont. 1)Slide 32 FFT Experiments (cont. 2)Slide 33 FFT Experiments (cont. 3)Slide 34 Experiment Power SpectrumEstimationSlide 35 Making a Spectrum AnalyzerSlide 35 Ping-Pong Buffers4-iiSlide 36 Ping-Pong Buffers (cont.)Slide 37 Spectrum Estimation (cont. 1)Slide 38 Spectrum Estimation (cont. 2)Slide 39 Spectrum Estimation (cont.

3 3)Slide 40 Another Method of Averaging PeriodogramsSlide 41 Testing Your Spectrum AnalyzerSlide 42 Initial Testing (cont.)Slide 43 Displaying the Spectrum Using CCSS lide 44 Displaying the Spectrum (cont.)Slide 45 Testing with External InputsSlide 46 Testing with External Inputs (cont. 1)Slide 47 Testing with External Inputs (cont.)Slide 48 Testing with an Exponential Averager4-iii Chapter 4 The FFT and Power SpectrumEstimationThe Discrete-Time Fourier TransformThe discrete-time signalx[n] =x(nT) is obtainedby sampling the continuous-timex(t) with periodTor sampling frequency s= 2 Fourier transformofx[n] isX( ) = Xn= x[n]e j nT=X(z)|z=ej T(1)Notice thatX( ) has period discrete-time signal can be determined fromits discrete-time Fourier transform by the inversionintegralx[n] =1 sZ s/2 s/2X( )ej nTd (2)= a sum of sinusoids,ej nT, scaled byX( ).

4 4-1 Data Window FunctionsThe observed data sequence must be limitedto a finite duration to compute the transformsummation in Rectangular Window FunctionThe most obvious approach is to simply truncatethe summation to a finite range, for example,0 n N 1. Let theN-point rectangular datawindow function beh1[n] = 1 forn= 0,1, .. , N 10 elsewhere(3)Then the truncated sequence isy[n] =x[n]h1[n].LetH1( ),X( ), andY( ) be the discrete-timeFourier transforms ofh1[n],x[n], andy[n]. ThenY( ) =1 sZ s/2 s/2X( )H1( )d (4)Which is a frequency domain Rectangular Window Function (cont. 1)The discrete-time Fourier transform of the rectangularwindow isH1( ) =N 1Xn=0e j nT=e j (N 1)T/2H0( ) (5)whereH0( ) =sin( NT/2)sin( T/2)(6)This transform is called thespectral window. 1 Frequency / sFigure 1: Spectral Window for Rectangular Data Win-dow,|H1( )|, forN= 104-3 Rectangular Window Function (cont.)

5 2)|H1( )|has a peak magnitude ofNat integermultiples of sand is 0 at frequenciesk s/Nthat are not multiples of main lobe at the origin has width 2 transform of the truncated sum is asmoothed version of the true Spectrum ,X( ),obtained by convolvingX( ) withH1( ).The value at frequency is predominantly anaverage of values in the vicinity of weightedbyH1( ) over its main lobe which extendsfrom = ( s/N) to = + ( s/N).The maximum sidelobe magnitude ofH1( )is down only about 13 dB from the main lobepeak. SoX( ) estimated by the truncatedsummation can be significantly distorted bylarge values ofX( ) away from leakingthrough the spectral Normalization for SpectrumEstimationSpectral leakage can be reduced by using a datawindow with smaller sidelobes in its unbiased Power spectral density estimates, adata windowh[n] should be normalized so that1NN 1Xn=0h2[n] = 1(7)The Hanning WindowThe Hanning spectral window isH2( ) =c2e j (N 1) ( ) + sN + + sN i(8)with the corresponding data windowh2[n]= 1+cos n N 12 2 N forn= 0.

6 , N 10elsewhere(9)wherec2= (3/8) 1 The maximum sidelobe amplitude is downby dB from the main lobe peak for theHanning , the mainlobe has width 4 s/Nwhich is double the width of the main lobe forthe rectangular is a trade-off between the main lobewidth and peak side lobe Hamming Window FunctionThe Hamming spectral window isH3( ) =c3e j (N 1) ( ) + sN + + sN i(10)with the corresponding data windowh3[n]= c3 + cos n N 12 2 N forn= 0, .. , N 10elsewhere(11)wherec3= ( ) 1 is almost the same as the Hanning window. Itsspectral sidelobes are down by at least 40 Other Window FunctionsSee DSP books for the Blackman and Blackman spectral window is formed byadding in shifts ofH1( ) to the right and leftby 2 s/Nas well as the shifts of s/Nfor theHamming and Hanning windows. The width ofthe main lobe is 6 s/Nbut the peak sidelobesare down by 80 Kaiser window approximates the prolatespheroidal waveforms and has a parameter thatcan be varied to trade-off the main lobe widthand peak sidelobe level.

7 Excellent designs canbe seems to be a law of nature that the mainlobe width must be increased to reduce The Discrete Fourier Transform andits InverseLetx0, x1, .. , xN 1be anN-point sequence andletx[n] = xnforn= 0, .. , N 10elsewhereLetX( ) be the discrete-time Fourier transformofx[n]. Thediscrete Fourier transform(DFT) ofxnis defined to be theN-point sequenceXk=X(k s/N) =N 1Xn=0x[n]e jnT k s/N=N 1Xn=0xne j2 Nnk;k= 0, .. , N 1 (12)The DFT is simply the set ofNsamples ofX( ) taken at frequencies spaced by s/Nin theNyquist band. Notice that ifkis allowed to takevalues outside the set{0, .. , N 1}, the valuecomputed by (12) repeats with DFT ExamplesComplex Exponential Sinusoidxn=ej( sN)nT=ej2 Nn (13)Fork= 0, .. , N 1Xk=N 1Xn=0ej2 Nn e j2 Nnk=N 1Xn=0ej2 Nn( k)=1 ej2 ( k)1 ej2 N( k)=N [k ](14)Cosine Wavexn= cos2 Nn = Nn + j2 Nn = Nn + Nn(N )(15)Xk= [k ] + [k (N )] (16)4-9 The Inverse Discrete FourierTransform (IDFT)The originalN-point sequence can be determinedby using the inverse discrete Fourier transform(IDFT) formulaxn=1NN 1Xk=0 Xkej2 Nnkforn= 0,1.

8 , N 1(17)Computational RequirementsDirect computation of a DFT value for a singlekusing (12) requiresN 1 complex additionsandNcomplex multiplications ignoring the factthat for somekthe exponentials are 1 or , direct computation of allNpoints requiresN(N 1) complex additions next slide shows how the computation can bereduced to be proportional toNlog2 Nby cleverlybreaking the DFT sum down into The Fast Fourier TransformThe computational complexity can be reducedto the order ofNlog2 Nby algorithms known asfast Fourier transforms(FFT s) that compute theDFT indirectly. For example, withN= 1024 theFFT reduces the computational requirements by afactor ofN2 Nlog2N= improvement increases in Time FFT AlgorithmOne FFT algorithm is called thedecimation-in-timealgorithm. A brief derivation is presentedbelow for reference.

9 To simplify the notation, letWN=e j2 /Nso (12) becomesXk=N 1Xn=0xnWnkN(18)This algorithm assumes thatNis a Power of Decimation in Time FFT (cont. 1)Splitting the sum into a sum over evennand oneover oddngivesXk=N2 1Xn=0x2nW2nkN+N2 1Xn=0x2n+1W(2n+1)kNfork= 0,1, .. , N 1(19)Let the even numbered points be theN/2 pointsequencean=x2nforn= 0,1, .. ,N2 1(20)and the odd numbered points be theN/2 pointsequencebn=x2n+1forn= 0,1, .. ,N2 1(21)Also observe thatW2N=WN/2. Thus, (19) can bewritten asXk=N2 1Xn=0anWnkN/2+WkNN2 1Xn=0bnWnkN/2;k= 0, .. , N 1(22)4-12 Decimation in Time FFT (cont. 2)LetAkandBkbe theN/2-point DFT s ofanandbnso that these DFT s have periodN/2 andXk=Ak+WkNBkfork= 0,1, .. , N 1 (23)The next step results in the key equations forthe decimation-in-time FFT. First observe thatWN/2N= 1. Then, the previous equation can beseparated into the two equationsXk=Ak+WkNBkfork= 0,1.

10 ,N2 1 (24)Xk+N2=Ak WkNBkfork= 0,1, .. ,N2 1 (25)Equations (24) and (25) show how to compute anN-point DFT by combining a pair ofN/2-pointDFT s. A flowgraph for this pair of equations isshown in Figure 2. This computation is called anFFT butterfly. A complete flowgraph for this firststep withN= 8 is shown in Figure Decimation in Time FFT (cont. 3) AkBkXkXk+N2 1 WkNFigure 2: Flowgraph for an FFT ButterflyIf theN/2-point DFT s,AkandBk, are known,N/2 complex multiplications are required tocomputeBkWkN,N/2 complex additions tocomputeXk=Ak+WkNBk, andN/2 complexsubtractions to computeXk+N2=Ak WkNBkfork= 0,1, .. ,N2 1. Addition and subtraction canbe considered to be essentially the same. Thus, theentireN-point DFT can be computed withN/2complex multiplications andNcomplex additionsfrom the pair ofN/2-point DFT Decimation in Time FFT (cont.)


Related search queries