 # The Discrete Fourier Transform, Quote of the Day Mathematics may

0

#### Presentation Transcript

• 1.The Discrete Fourier Transform Quote of the Day Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true. Bertrand Russell Content and Figures are from Discrete-Time Signal Processing, 2e by Oppenheim, Shafer, and Buck, ©1999-2000 Prentice Hall Inc.
• 2.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 2 Sampling the Fourier Transform Consider an aperiodic sequence with a Fourier transform Assume that a sequence is obtained by sampling the DTFT Since the DTFT is periodic resulting sequence is also periodic We can also write it in terms of the z-transform The sampling points are shown in figure could be the DFS of a sequence Write the corresponding sequence
• 3.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 3 Sampling the Fourier Transform Cont’d The only assumption made on the sequence is that DTFT exist Combine equation to get Term in the parenthesis is So we get
• 4.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 4 Sampling the Fourier Transform Cont’d
• 5.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 5 Sampling the Fourier Transform Cont’d Samples of the DTFT of an aperiodic sequence can be thought of as DFS coefficients of a periodic sequence obtained through summing periodic replicas of original sequence If the original sequence is of finite length and we take sufficient number of samples of its DTFT the original sequence can be recovered by It is not necessary to know the DTFT at all frequencies To recover the discrete-time sequence in time domain Discrete Fourier Transform Representing a finite length sequence by samples of DTFT
• 6.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 6 The Discrete Fourier Transform Consider a finite length sequence x[n] of length N For given length-N sequence associate a periodic sequence The DFS coefficients of the periodic sequence are samples of the DTFT of x[n] Since x[n] is of length N there is no overlap between terms of x[n-rN] and we can write the periodic sequence as To maintain duality between time and frequency We choose one period of as the Fourier transform of x[n]
• 7.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 7 The Discrete Fourier Transform Cont’d The DFS pair The equations involve only on period so we can write The Discrete Fourier Transform The DFT pair can also be written as
• 8.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 8 Example The DFT of a rectangular pulse x[n] is of length 5 We can consider x[n] of any length greater than 5 Let’s pick N=5 Calculate the DFS of the periodic form of x[n]
• 9.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 9 Example Cont’d If we consider x[n] of length 10 We get a different set of DFT coefficients Still samples of the DTFT but in different places
• 10.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 10 Properties of DFT Linearity Duality Circular Shift of a Sequence
• 11.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 11 Example: Duality
• 12.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 12 Symmetry Properties
• 13.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 13 Circular Convolution Circular convolution of of two finite length sequences
• 14.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 14 Example Circular convolution of two rectangular pulses L=N=6 DFT of each sequence Multiplication of DFTs And the inverse DFT
• 15.Copyright (C) 2005 Güner Arslan 351M Digital Signal Processing 15 Example We can augment zeros to each sequence L=2N=12 The DFT of each sequence Multiplication of DFTs