Transcription of Discrete Fourier Transform
1 : signal ProcessingDiscrete Fourier Transform Discrete Fourier Transform (DFT) Relations to Discrete -Time Fourier Transform (DTFT) Relations to Discrete -Time Fourier Series (DTFS)October 19, 2021 Yet Another Fourier RepresentationWhy do we need another Fourier Representation? Fourier seriesrepresent signals as sums of sinusoids. They provide insightsthat are not obvious from time representations, but Fourier series onlydefined for periodic [k] = n= N x[n]e j2 kn/N(summed over a period) Fourier transformshave no periodicity constaint:X( ) = n= x[n]e j n(summed over all samplesn)but are functions of continuous domain ( ).
2 Not convenient for numerical computationsDiscrete Fourier Transform : Discrete frequencies for aperiodic Fourier TransformDefinition and comparison to other Fourier :X[k] =1NN 1 n=0x[n]e j2 kNnx[n] =N 1 k=0X[k]ej2 kNnDTFS:X[k] =1N n= N x[n]e j2 kNnx[n] = k= N X[k]ej2 kNnDTFT:X( ) = n= x[n]e j nx[n] =12 2 X( )ej nd DTFS:x[n]is presumed to be periodic inNDTFT:x[n]is arbitraryDFT:only a portion of an arbitraryx[n]is consideredRelation Between DFT and DTFSIf a signal is periodic in the DFT analysis periodN, then the DFT coeffi-cients are equal to the DTFS [n] = cos2 n64.
3 Then ifN=64, the DFT coefficients areX1[k] =1NN 1 n=0x[n]e j2 Nkn=12 [k 1] +12 [k 63]as plotted [k]064012 The coefficients are the same as the Fourier series Between DFT and DTFSIf a signal is not periodic in the DFT analysis periodN, then there are noFourier series coefficients to [n] = cos3 n64. Then ifN=64, the DFT coefficients areX2[k] =1NN 1 n=0x2[n]e j2 Nknare plotted |X2[k]|064012 Even thoughx2[n]contains a single frequency = 3 /64, there are largecoefficients at many different reason is thatx2[n]is not periodic innwith periodN= Between DFT and DTFSA lthoughx2[n] = cos3 n64is not periodic inN=64, we can define a signalx3[n]that is equal tox2[n]for0 n <64and that is periodic inN= [n]
4 064128 The DFT coefficients for this signal are the same as those forx2[n]:k|X3[k]|064012 Furthermore, the DFT coefficients ofx3[n]equal the DTFS coefficients ofx3[n]. The large number of non-zero coefficients are necessary to producethe step discontinuity atn= Ways to Think About the DFTC ompare to DTFS:1. The DFT of a signalx[n]is equal to theDTFSof a version ofx[n]that is periodically extended so that it is periodic inN. emphasizes the importance to DTFT:2.
5 The DFT is equal to samples of theDTFTof a windowed version ofthe original signal . emphasizes the importance ofspectral smearin DFT Between DFT and DTFTThe DFT can also be thought of assamplesof the DTFT of awindowedversion ofx[n] [n] =x[n] w[n]represent awindowedversion ofx[n]wherew[n] ={10 n < N0otherwiseThen the Fourier Transform ofxw[n]isXw( ) = n= xw[n]e j n= n= x[n]w[n]e j n=N 1 n=0x[n]e j nScaleboth sides of this equation by1N. Thensamplethe resulting functionof at =2 kNto obtain an expression for the DFT ofx[n].}
6 X[k] =1NN 1 n=0x[n]e j2 Nkn=1 NXw(2 kN)Relation Between DFT and DTFTG raphical depiction of relation between DFT and [n]Relation Between DFT and DTFTG raphical depiction of relation between DFT and [n]windownxw[n] =x[n]w[n]0N 1 Relation Between DFT and DTFTG raphical depiction of relation between DFT and [n]windownxw[n] =x[n]w[n]0N 1 DTFT Xw( ) 0 Relation Between DFT and DTFTG raphical depiction of relation between DFT and [n]windownxw[n] =x[n]w[n]0N 1 DTFT Xw( ) 0 k1 NXw(2 kN)-N20N2sample: 2 kNscale:1/NRelation Between DFT and DTFTG raphical depiction of relation between DFT and [n]windowDFTnxw[n] =x[n]w[n]0N 1 DTFT Xw( ) 0 k1 NXw(2 kN)-N20N2sample: 2 kNscale.
7 1/NRelation Between DFT and DTFTG raphical depiction of relation between DFT and [n]windowDFTnxw[n] =x[n]w[n]0N 1 DTFT Xw( ) 0 k1 NXw(2 kN)-N20N2sample: 2 kNscale:1/NWhile sampling and scaling are important, it is thewindowingthat mostaffects frequency of Windowing on Fourier RepresentationsExample: characterize the effect of windowing on complex exponentialsignals, which are the basis functions for Fourier 1: FindX( ), the DTFT of a complex exponential signal :x[n] =ej onStep 2: FindXw( ), the DTFT of a windowed version ofx[n]:xw[n] =x[n]w[n]Step 3: CompareXw( )toX( ).
8 Effect of Windowing on Fourier RepresentationsStep 1: Find the DTFT of a complex exponentialx[n] =ej DTFT of a complex exponential is a train of o X( )2 2 ej ondtft This is easy to verify using the DTFT synthesis [n] =12 2 X( )ej nd =12 2 ( o)ej nd = ( o)ej nd =ej onEffect of Windowing on Fourier RepresentationsStep 2: Find the DTFT ofxw[n], a windowed version ofx[n].Letxw[n]represent a windowed version ofx[n].xw[n] =x[n]w[n] =ej onw[n]ThenXw( )= n= ej onw[n]e j nDTFT analysis equation= n= w[n]e j( o)ncombine exponential terms=W( o)DTFT ofw[n], shifted in frequencyThe DTFT of a windowed version of a complex exponential signal is ashifted version of the DTFT of the window onw[n]dtft W( o) Need to knowW( ).
9 Effect of Windowing on Fourier RepresentationsSimplest window is rectangular, with width ofN(length of DFT analysis)w[n] ={10 n < N0otherwiseas shown below forN= [n]0151 The DTFT ofw[n]isW( ) = n= w[n]e j n=N 1 n=0e j n=1 e j N1 e j =sinN 2sin 2e j N 1215 |W( )|02 2 Effect of Windowing on Fourier RepresentationsThe DTFT of a windowed version of a complex exponential signal is ashifted version of the DTFT of the window [n] =ej onw[n]dtft Xw( ) =W( o)15 |W( )|02 2 15 |Xw( )|=|W( o)|02 2 Effect of Windowing on Fourier RepresentationsStep 3: CompareXw( )toX( ).}
10 2 o X( )2 2 x[n] =ej ondtft 15 |Xw( )|02 2 xw[n] =x[n]w[n]dtft The frequency content ofX( )is at Discrete frequencies = o+ 2 frequency content ofXw( )is most dense at these same frequencies,but is spread out over almost all other frequencies as Between DFT and DTFTThe DFT can be thought of assamplesof the DTFT of awindowedversion ofx[n] [n]windowDFTnxw[n] =x[n]w[n]0N 1 DTFT Xw( ) 0 k1 NXw(2 kN)-N20N2sample: 2 kNscale:1/NThe remaining steps are to sample and of Windowing on Fourier RepresentationsThe DFT can be thought of assamplesof the DTFT of awindowedversion ofx[n]scaled by1/N.
