Signal processing - The discrete fourier transform

f Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 42 sites.google.com/site/ncpdhbkhn 43 Symmetry (1) 1 2 3 4 5 6 7 8 0 0.2 0.4 0.6 0.8 1 n x 1 [ n ] 1 2 3 4 5 6 7 8 0 0.5 1 1.5 2 2.5 3 k X 1 R [ k ] 1 2 3 4 5 6 7 8 -2 -1 0 1 2 k X 1 I [ k ] 1 2 3 4 5 6 7 0 0.2 0.4 0.6 0.8 1 n x 2 [ n ] 1 2 3 4 5 6 7 -1 0 1 2 3 k X 2 R [ k ] 1 2 3 4 5 6 7 -2 -1 0 1 2 k X 2 I [ k ] sites.google.com/site/ncpdhbkhn 44 Symmetry (2) 0 1 0 1 [ ] [ ] [ ], [ ] [ ] [ ], R I R I x n x n jx n n N X k X k jX k k N           2 21 1 0 0 1 [ ] [ ] , [ ] [ ] N Nj kn j kn N N n k X k x n e x n X k e N         1 0 1 0 1 0 2 2 0 2 2 0 2 2 0 [ ] [ ]cos [ ]sin , [ ] [ ]sin [ ]cos , [ ] [ ]cos [ ]sin , [ ] N R R I n N I R I n N R R I k I X k x n kn x n kn k N N N X k x n kn x n kn k N N N x n X k kn X k kn n N N N x k X                                                                 1 0 2 2 0[ ]sin [ ]cos , N R I k k kn X k kn k N N N                      sites.google.com/site/ncpdhbkhn 45 Symmetry (3) 1 0 1 0 2 2 0 2 2 0 [ ] [ ]cos [ ]sin , [ ] [ ]sin [ ]cos , N R R I n N I R I n X k x n kn x n kn k N N N X k x n kn x n kn k N N N                                                If is real, then 0[ ] [ ]Ix n x n  1 1 0 0 1 1 0 0 2 2 2 2 [ ] [ ]cos [ ]cos [ ] [ ]sin [ ]sin N N R R n n N N I R n n X k x n kn x n kn N N X k x n kn x n kn N N                                            0 0 1 1 0 0 1 1 0 0 1 1 * [ ], [ ] [ ] [ ], , [ ] [ ] [ ], [ ], [ ] [ ] [ ], R R R N R I I N I N X k X k X k X N k k N k X k X k X N k k N X k X k X k X N k k N                              sites.google.com/site/ncpdhbkhn 46 Symmetry (4) 0 1[ ] [ ] [ ],ce cox n x n x n n N     1 1 2 2 0 0 [ ] [ ][ ] [ ] , [ ] [ ] [ ], ce ceN N x n x N nx n x n n N x n x n x n            1 1 2 2 0 0 [ ] [ ][ ] [ ] , [ ] [ ] , co ceN N x n x N nx n x n n N x n x n n             The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform a) Linearity b) Periodic, Circular, and Modulo – N Operations c) Symmetry d) Circular Shift of a Sequence e) Circular Convolution f) Circular Correlation g) DFT of Stretched and Sampled Sequences 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 47 sites.google.com/site/ncpdhbkhn 48 Circular Shift of a Sequence 0 n [ ]x n 1N  0 n [ ]x n 1N    0 n 2[ ] [ ] [ ] [ ]N Nz n z n p n x n   1N  0 n 2[ ] [ ]z n x n  1N    [ ] [ ]DFT kmNNNx n m W X k  [ ] N x n 1 0 1N  [ ] N x n m 1 01N  The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform a) Linearity b) Periodic, Circular, and Modulo – N Operations c) Symmetry d) Circular Shift of a Sequence e) Circular Convolution f) Circular Correlation g) DFT of Stretched and Sampled Sequences 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 49 sites.google.com/site/ncpdhbkhn 50 Circular Convolution (1) [ ] [ ] [ ] ( ) ( ) ( )DTFT j j j m y n h m x n m Y e H e X e            0 1[ ] [ ] [ ],Y k H k X k k N    1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 N N N N kn km kl kn N N N N k k m l N N N k m l n N m l k H k X k W h m W x l W W N N h m x l W N N                                          ( ) [ ] [ ] [ ] [ ] [ ] [ ] 1 0 11 0 otherwise ( ) , , N k m l n N k m l n rN W N         modulo( ) N m l n rN l n m rN n m N n m           1 1 0 0 [ ] [ ] [ ] [ ] [ ] N N N m m y n h m x n m h m x n m          1 0 1 N kn N k y n Y k W N     [ ] [ ] sites.google.com/site/ncpdhbkhn 51 Circular Convolution (2) 1 1 0 0 [ ] [ ] [ ] [ ] [ ] N N N m m y n h m x n m h m x n m          [ ] [ ] [ ]y n h n x n N [ ] [ ] [ ] [ ] [ ] [ ]DFTNy n h n x n Y k H k X k  N 0n  x[2] x[3]x[4] x[5] [ ]x n 0n  x[0] x[1]x[2] x[3] 8 2[ ]x n  Circular mapping 0n  x[2] x[3]x[4] x[5] 8 2[ ]x n  Circular addressing sites.google.com/site/ncpdhbkhn 52 Circular Convolution (3) Ex. 3 1 2 3 4 0 1 2 3[ ] { }, [ ] { }.h n x n   [ ] [ ] [ ].y n h n x n NGiven Find 1 0 [ ] [ ] [ ] N N m y n h m x n m     0[ ]h 1[ ]h2[ ]h 3[ ]h x[0] x[3]x[2] x[1] 1 03 2 2 10 3 3 21 0 0 0 0 1 3 2 2 3 1 1 0 2 3 3 2 4 1 16 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]y h x h x h x h x             1 0 1 1 0 2 3 3 2 1 1 2 0 3 3 4 2 18 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]y h x h x h x h x             2 0 2 1 1 2 0 3 3 1 2 2 1 3 0 4 3 16 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]y h x h x h x h x             3 0 3 1 2 2 1 3 0 1 3 2 2 3 1 4 0 10 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]y h x h x h x h x             0n  123 Method 1 sites.google.com/site/ncpdhbkhn 53 Circular Convolution (4) Ex. 3 1 2 3 4 0 1 2 3[ ] { }, [ ] { }.h n x n   [ ] [ ] [ ].y n h n x n NGiven Find 0 0 0 1 3 2 2 3 1 1 0 2 3 3 2 4 1 16[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]y h x h x h x h x             1 0 1 1 0 2 3 3 2 1 1 2 0 3 3 4 2 18[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]y h x h x h x h x             2 0 2 1 1 2 0 3 3 1 2 2 1 3 0 4 3 16[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]y h x h x h x h x             3 0 3 1 2 2 1 3 0 1 3 2 2 3 1 4 0 10[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]y h x h x h x h x             0 0 3 2 1 0 1 1 0 3 2 1 2 2 1 0 3 2 3 3 2 1 0 3 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] y x x x x h y x x x x h y x x x x h y x x x x h                                 sites.google.com/site/ncpdhbkhn 54 Circular Convolution (5) Ex. 3 1 2 3 4 4 4 2 2 4 4 3 2 1 4 4 4 1 1 1 10 0 1 1 1 1 0 6 11 1 1 1 1 2 2 1 12 2 1 1 1 1 2 2 13 3 1 1 3 2 2 [ ] [ ] [ ] [ ] X W W WX j j j W WX W W WX j j j                                                                        1 2 3 4 0 1 2 3[ ] { }, [ ] { }.h n x n   [ ] [ ] [ ].y n h n x n NGiven Find Method 2[ ] [ ] [ ] [ ] [ ] [ ]DFTNy n h n x n Y k H k X k  N 1 2 3 4 4 4 2 2 4 4 3 2 1 4 4 4 1 1 1 10 0 1 1 1 1 1 10 11 1 1 1 2 2 2 1 12 2 1 1 1 1 3 2 13 3 1 1 4 2 2 [ ] [ ] [ ] [ ] H W W WH j j j W WH W W WH j j j                                                                        sites.google.com/site/ncpdhbkhn 55 Circular Convolution (6) Ex. 3 1 2 3 4 0 1 2 3[ ] { }, [ ] { }.h n x n   [ ] [ ] [ ].y n h n x n NGiven Find Method 2    6 2 2 2 2 2 10 2 2 2 2 2; ; ; ; ; ; ;j j j j           X H [ ] [ ] [ ] [ ] [ ] [ ]DFTNy n h n x n Y k H k X k  N 0 0 0 6 10 60 1 8 2 4 3 8[ ] [ ] [ ] ; [ ] ; [ ] ; [ ]Y H X Y j Y Y j         0 1 1 1 1 0 1 1 1 1 60 16 1 1 1 1 1 1 8 101 1 4 42 1 1 1 1 2 1 1 1 1 4 16 3 1 1 3 1 1 8 18 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] y Y y j j Y j j j y Y y j j Y j j j                                                                                The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform a) Linearity b) Periodic, Circular, and Modulo – N Operations c) Symmetry d) Circular Shift of a Sequence e) Circular Convolution f) Circular Correlation g) DFT of Stretched and Sampled Sequences 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 56 sites.google.com/site/ncpdhbkhn 57 Circular Correlation 1 0 0 1[ ] [ ] [ ], N xy N n r l x n y n l l N        *[ ] [ ] [ ] [ ] [ ] [ ]DFTxy xyNNr l x n y n R k X k Y k   N The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform a) Linearity b) Periodic, Circular, and Modulo – N Operations c) Symmetry d) Circular Shift of a Sequence e) Circular Convolution f) Circular Correlation g) DFT of Stretched and Sampled Sequences 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 58 sites.google.com/site/ncpdhbkhn 59 DFT of Stretched Sequences 0 n [ ]x n 1N  ( )[ ]Lx n 0 n 1L  0 2 1 0 otherwise ( ) [ / ], , , ,...,( )[ ] , L x n L n L L N Lx n    ( )[ ] [ ] [ ]DFTL NL Nx n X k X k  1 1( )[ ] [ ] [ ]DFTL NLx n x n X kL L   sites.google.com/site/ncpdhbkhn 60 DFT of Sampled Sequences 0 1( )[ ] [ ],M Nx n x nM n M     1 0 1 ( ) / [ ] M DFT M N M m Nx n X k m M M        1 0 1 ( )/ [ ] M DFT MN M m Nx n m X k M M        0 n [ ]x n 1N  0 n ( )[ ]Mx n sites.google.com/site/ncpdhbkhn 61 Properties of the DFT The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT a) Linear Convolution Using Circular Convolution b) Implementation of FIR Filters Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 62 sites.google.com/site/ncpdhbkhn 63 Linear Convolution Using Circular Convolution (1) 0 2[ ] [ ] [ ], k y n h k x n k n L M         ( ) ( ) ( )j j jY e H e X e   2 0 1/[ ] ( ),j k NY k Y e k N    2 2/ /[ ] ( ), [ ] ( )j k N j k NH k H e X k X e   [ ] [ ] [ ] [ ] [ ] [ ]DFTzero padded zp zp Ny n h n x n Y k H k X k   N Pad with (M – 1) zeros [ ]x n  [ ]y n [ ] [ ] [ ]Y k H k X k Pad with (L – 1) zeros [ ]h n N – point IDFT [ ]X k [ ]H k N – point DFT N – point DFT [ ]zpx n [ ]zph n Length L Length M Length N 1N L M   sites.google.com/site/ncpdhbkhn 64 Linear Convolution Using Circular Convolution (2) 0 2[ ] [ ] [ ], k y n h k x n k n L M         0 0 0 0 1 1 0 0 02 2 1 0 13 3 2 1 24 4 3 2 5 0 4 3 6 0 0 4 [ ] [ ] [ ] [ ] [ ] [ ][ ] [ ] [ ] [ ] [ ][ ] [ ] [ ] [ ] [ ][ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] y x y x x hy x x x hy x x x hy x x x y x x y x                                             0 0 0 4 3 2 1 0 1 0 0 0 4 3 2 1 2 1 0 0 0 4 3 2 3 2 1 0 0 0 4 0 4 3 2 1 0 0 0 0 0 4 3 2 1 0 0 0 0 0 4 3 2 1 0 0 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x x x x h x x x x x h x x x x x h x x x x x x x x x x x x x x x x x x x x                          The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT a) Linear Convolution Using Circular Convolution b) Implementation of FIR Filters Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 65 Implementation of FIR Filters Using the DFT (1) • The input may have indefinite length • The input’s length may be too large for storage & computation • The computation can not be started untill all input signal samples have been collected  delays sites.google.com/site/ncpdhbkhn 66 Pad with (M – 1) zeros [ ]x n  [ ]y n [ ] [ ] [ ]Y k H k X k Pad with (L – 1) zeros [ ]h n N – point IDFT [ ]X k [ ]H k N – point DFT N – point DFT [ ]zpx n [ ]zph n Length L Length M Length N 1N L M   sites.google.com/site/ncpdhbkhn 67 Implementation of FIR Filters Using the DFT (2) 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 3 0 2 1 0 0 0 0 0 4 0 0 2 1 0 0 0 0 5 0 0 0 2 1 0 0 0 6 0 0 0 0 2 1 0 0 7 0 0 0 0 0 2 1 0 8 9 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] y h y h h y h h h y h h h y h h h y h h h y h h h y h h h y y                   0 1 2 3 4 5 6 0 0 0 0 0 0 2 1 7 0 0 0 0 0 0 0 2 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x x x x x x h h x h                                          The overlap – add method sites.google.com/site/ncpdhbkhn 68 Implementation of FIR Filters Using the DFT (3) 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 3 0 2 1 0 0 0 0 0 4 0 0 2 1 0 0 0 0 5 0 0 0 2 1 0 0 0 6 0 0 0 0 2 1 0 0 7 0 0 0 0 0 2 1 0 8 9 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] y h y h h y h h h y h h h y h h h y h h h y h h h y h h h y y                   0 1 2 3 4 5 6 0 0 0 0 0 0 2 1 7 0 0 0 0 0 0 0 2 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x x x x x x h h x h                                          The overlap – add method   1 2 4 0 0 2 1 3 4 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x y h h h x x           3 4 5 1 0 0 2 5 6 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x y h h h x x         sites.google.com/site/ncpdhbkhn 69 Implementation of FIR Filters Using the DFT (4) 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 3 0 2 1 0 0 0 0 0 4 0 0 2 1 0 0 0 0 5 0 0 0 2 1 0 0 0 6 0 0 0 0 2 1 0 0 7 0 0 0 0 0 2 1 0 8 9 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] y h y h h y h h h y h h h y h h h y h h h y h h h y h h h y y                   0 1 2 3 4 5 6 0 0 0 0 0 0 2 1 7 0 0 0 0 0 0 0 2 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x x x x x x h h x h                                          The overlap – save method The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT a) Effects of Time – Windowing on Sinusoidal Signals b) Effects of Time – Windowing on Signals with Continuous Spectra c) “Good” Window and the Uncertainty Principle d) The Spectrogram 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 70 sites.google.com/site/ncpdhbkhn 71 Effects of Time – Windowing on Sinusoidal Signals (1) -6 -4 -2 0 2 4 6 -1 0 1 t x c ( t ) -6 -4 -2 0 2 4 6 0 0.5 1 t w c ( t ) -6 -4 -2 0 2 4 6 -1 0 1 t w c ( t ) x c ( t ) 01 0 2 0 otherwise , / ( ) ,c t T w t    ˆ ( ) ( ) ( )c c cx t w t x t 1 0 1 0 otherwise , [ ] , t L w n     ˆ ˆ[ ] ( ) ( ) ( ) [ ] [ ]c c cx n x nT w nT x nT w n x n    sites.google.com/site/ncpdhbkhn 72 Effects of Time – Windowing on Sinusoidal Signals (2) Ideal A/D ( )cx t  [ ]w n N – point DFT ˆ [ ]X k[ ]x n 1 s T F  ˆ[ ]x n Ideal A/D ( )cx t  ( )cw t N – point DFT ˆ [ ]X kˆ ( )cx t 1 s T F  ˆ[ ]x n sites.google.com/site/ncpdhbkhn 73 Effects of Time – Windowing on Sinusoidal Signals (3) 1 1 1( ) cos( ),cx t A t t       1 1 1 1 1 1 1 1 2 2 j j t j j tA e e Ae e      1 1 1 1 1 1 1 1 2 2 ˆ ( ) ( ) ( ) ( ) ( )j j t j j tc c c c cx t w t x t Ae w t e Ae w t e        1 1 1 1 1 1 1 1 2 2 ˆ ( ) [ ( )] [ ( )]j jc c cX j Ae W j Ae W j          01 0 0 otherwise , ( ) ( ) ,c R t T w t w t     0 20 2 2 /sin( / )( ) ( ) / j T c R TW j W j e      sites.google.com/site/ncpdhbkhn 74 Effects of Time – Windowing on Sinusoidal Signals (4) -6 -4 -2 0 2 4 6 -1 -0.5 0 0.5 1 -6 -4 -2 0 2 4 6 0 0.5 1 -6 -4 -2 0 2 4 6 0 0.5 1 -6 -4 -2 0 2 4 6 -1 0 1 2 3 -6 -4 -2 0 2 4 6 -1 0 1 2 3 -6 -4 -2 0 2 4 6 -1 -0.5 0 0.5 1 -6 -4 -2 0 2 4 6 -1 0 1 2 3 t t t     ( )cx t ( )cw t ˆ ( ) ( ) ( )c c cx t w t x t 1 1 ( )cX j ( )cW j 0T ˆ ( )cX j sites.google.com/site/ncpdhbkhn 75 Effects of Time – Windowing on Sinusoidal Signals (5) 0 2 4 6 8 10 12 -0.5 0 0.5 1 1.5 2 2.5 3  Wc(j( - 2)) Wc(j( - 1)) 0 2 4 6 8 10 12 0 0.5 1 1.5 2 2.5 3 3.5  Wc(j( - 2)) + Wc(j( - 1)) 2 1 0 0 0 2 1 2 1T T F F           The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT a) Effects of Time – Windowing on Sinusoidal Signals b) Effects of Time – Windowing on Signals with Continuous Spectra c) “Good” Window and the Uncertainty Principle d) The Spectrogram 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 76 sites.google.com/site/ncpdhbkhn 77 Effects of Time – Windowing on Signals with Continuous Spectra -8 -6 -4 -2 0 2 4 6 8 -0.5 0 0.5 1 F (Hz) M a g n i t u d e Spectrum of rectangular window -8 -6 -4 -2 0 2 4 6 8 0 0.5 1 F (Hz) M a g n i t u d e Spectrum of infinite duration signal 200 400 600 800 1000 1200 1400 1600 0 0.5 1 F (Hz) M a g n i t u d e Shifted copies of window spectrum -8 -6 -4 -2 0 2 4 6 8 0 2 4 F (Hz) M a g n i t u d e Spectrum of windowed signal 1 1 2 2 ( ) ( ) ( ( )) ( ) ( ( ))c c c c k c k k X j X j W j d X j W j                  The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT a) Effects of Time – Windowing on Sinusoidal Signals b) Effects of Time – Windowing on Signals with Continuous Spectra c) “Good” Window and the Uncertainty Principle d) The Spectrogram 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 78 sites.google.com/site/ncpdhbkhn 79 “Good” Windows and the Uncertainty Principle (1) -6 -4 -2 0 2 4 6 -0.2 0 0.2 0.4 0.6 0.8 Smearing & leakage sites.google.com/site/ncpdhbkhn 80 “Good” Windows and the Uncertainty Principle (2) 1 ( ) CTFTc c jx at X a a      0 0( ) cos[ ( )] cos[( ) ]cx at at a t    Time and frequency scaling property Uncertainty principle 22 2 ( )t ct x t dt   22 21 2 ( )cX j d        1 2t    sites.google.com/site/ncpdhbkhn 81 “Good” Windows and the Uncertainty Principle (3) -1.5 -1 -0.5 0 0.5 1 1.5 -0.2 0 0.2 0.4 0.6 0.8  WR(j) -1.5 -1 -0.5 0 0.5 1 1.5 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9  WB(j) = [WR(j)]2 -1.5 -1 -0.5 0 0.5 1 1.5 2 4 6 8 10 12 t wRectangular(t) -1.5 -1 -0.5 0 0.5 1 1.5 2 4 6 8 10 12 t wBartlett(t) 2 0 2 0 4 4 2 sin ( / ) ( ) /Bartlett TW j T    sites.google.com/site/ncpdhbkhn 82 “Good” Windows and the Uncertainty Principle (4) -3 -2 -1 0 1 2 3 0 5 10  WRectangular(j) 100 200 300 400 500 600 0 2 4 6  .25WR(j( + 2/T0) .25WR(j( - 2/T0) 0.5WR(j) 100 200 300 400 500 600 0 2 4 6  WHann(j) -0.1 -0.08 -0.06 -0.04 -0.02 0 0.02 0.04 0.06 0.08 0.1 0 100 200 300 400 500 600 t wHann(t) 0 0 0 5 0 25 2 0 25 2 ( ) . ( ) . ( ( / )) . ( ( / )) Hann Rectangular Rectangular Rectangular W j W j W j T W j T            0 20 50 0 50( ) . . cos ( )Hann Rect tw t w t T         sites.google.com/site/ncpdhbkhn 83 “Good” Windows and the Uncertainty Principle (5) -3 -2 -1 0 1 2 3 0 5 10  WRectangular(j) 100 200 300 400 500 600 0 2 4 6 8  .23WR(j( + 2/T0) .23WR(j( - 2/T0) 0.54WR(j) 100 200 300 400 500 600 0 2 4 6 8  WHann(j) -0.1 -0.08 -0.06 -0.04 -0.02 0 0.02 0.04 0.06 0.08 0.1 0 100 200 300 400 500 600 t wHann(t) 0 0 0 54 0 23 2 0 23 2 ( ) . ( ) . ( ( / )) . ( ( / )) Hamming Rectangular Rectangular Rectangular W j W j W j T W j T            0 20 54 0 46( ) . . cos ( )Hamm Rect tw t w t T         sites.google.com/site/ncpdhbkhn 84 “Good” Windows and the Uncertainty Principle (6) sites.google.com/site/ncpdhbkhn 85 “Good” Windows and the Uncertainty Principle (7) 100 200 300 400 500 600 700 800 900 1000 0.2 0.4 0.6 0.8 1 1.2 F (Hz) A m p l i t u d e Rectangular 100 200 300 400 500 600 700 800 900 1000 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 F (Hz) A m p l i t u d e Bartlett 100 200 300 400 500 600 700 800 900 1000 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 F (Hz) A m p l i t u d e Hann 100 200 300 400 500 600 700 800 900 1000 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 F (Hz) A m p l i t u d e Hamming 2 2 3 2 4( ) cos( ) cos( ) cos( )x t Ft Ft Ft    Ex. The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT a) Effects of Time – Windowing on Sinusoidal Signals b) Effects of Time – Windowing on Signals with Continuous Spectra c) “Good” Window and the Uncertainty Principle d) The Spectrogram 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 86 sites.google.com/site/ncpdhbkhn 87 The Spectrogram 1 2 0 ( / )[ , ] [ ] [ ] L j k N m m X k n w m x n m e       0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 0 50 100 150 200 250 300 350 400 450 500 Time (Seconds) F r e q u e n c y ( H z ) The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 88 sites.google.com/site/ncpdhbkhn 89 Direct Computation of the Discrete – Fourier Transform 1 0 0 1 1[ ] [ ] , , ,..., N kn N n X k x n W k N      1 0 1 0 1 1[ ] [ ] , , ,..., N kn N k x n X k W n N N       1 0 1 0 2 2 2 2 [ ] [ ]cos [ ]sin [ ] [ ]sin [ ]cos N R R I k N I R I k X k x n kn x n kn N N X k x n kn x n kn N N                                       The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The Fast Fourier Transform Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 90 sites.google.com/site/ncpdhbkhn 91 The Fast Fourier Transform Idea Using a Matrix Approach (1) 2 3 4 5 6 7 8 8 8 8 8 8 8 2 4 6 2 4 6 8 8 8 8 8 8 3 6 4 7 2 5 8 8 8 8 8 8 8 4 4 4 4 8 8 8 8 5 2 7 4 6 3 8 8 8 8 8 8 8 6 4 2 6 4 2 8 8 8 8 8 8 7 6 5 4 3 8 8 8 8 8 1 1 1 1 1 1 1 10 11 1 12 13 1 1 1 14 15 1 16 17 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] X W W W W W W WX W W W W W WX W W W W W W WX W W W WX W W W W W W WX W W W W W WX W W W W WX               28 8 0 1 2 3 4 5 6 7 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x x x x x x W W x                                       2 4 6 3 5 7 8 8 8 8 8 8 8 4 4 2 6 2 6 8 8 8 8 8 8 6 4 2 3 7 5 8 8 8 8 8 8 8 4 4 4 4 8 8 8 8 2 4 6 5 7 3 8 8 8 8 8 8 8 4 4 6 2 6 2 8 8 8 8 8 8 6 4 2 7 5 3 8 8 8 8 8 8 8 1 1 1 1 1 1 1 1 0 1 2 1 1 4 1 6 1 1 1 1 1 1 3 1 1 1 [ ] [ ] [ ] [ ] [ ] [ ] x W W W W W W W x W W W W W W x W W W W W W W x W W W W x W W W W W W W x W W W W W W x W W W W W W W                5 7 [ ] [ ]x              sites.google.com/site/ncpdhbkhn 92 The Fast Fourier Transform Idea Using a Matrix Approach (2) 2 4 6 3 5 7 8 8 8 8 8 8 8 4 4 2 6 2 6 8 8 8 8 8 8 6 4 2 3 7 5 8 8 8 8 8 8 8 4 4 4 4 8 8 8 8 2 4 6 5 7 3 8 8 8 8 8 8 8 4 4 6 2 6 2 8 8 8 8 8 8 6 4 2 7 5 8 8 8 8 8 1 1 1 1 1 1 1 10 11 1 12 13 1 1 1 14 15 1 16 17 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] X W W W W W W WX W W W W W WX W W W W W W WX W W W WX W W W W W W WX W W W W W WX W W W W WX               38 8 0 2 4 6 1 3 5 7 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x x x x x x W W x                                       4 8 5 8 8 6 2 8 8 7 3 8 8 1W W W W W W W         -1 -0.5 0 0.5 1 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 8 Real Part I m a g i n a r y P a r t 0 8W 1 8W 2 8W 3 8W 4 8W 5 8W 6 8W 7 8W 2 4 6 3 5 7 8 8 8 8 8 8 8 4 4 2 6 2 6 8 8 8 8 8 8 6 4 2 3 7 5 8 8 8 8 8 8 8 2 4 6 3 5 7 8 8 8 8 8 8 8 4 4 2 6 2 6 8 8 8 8 8 8 6 4 2 3 7 5 8 8 8 8 8 8 8 1 1 1 1 1 1 1 1 0 1 2 1 1 4 1 6 1 1 1 1 1 1 1 1 1 1 1 1 [ ] [ ] [ ] [ ] x W W W W W W W x W W W W W W x W W W W W W W x x W W W W W W W W W W W W W W W W W W W W                            1 3 5 7 [ ] [ ] [ ] [ ] x x x              sites.google.com/site/ncpdhbkhn 93 The Fast Fourier Transform Idea Using a Matrix Approach (3) 2 4 6 3 5 7 8 8 8 8 8 8 8 4 4 2 6 2 6 8 8 8 8 8 8 6 4 2 3 7 5 8 8 8 8 8 8 8 2 4 6 3 5 7 8 8 8 8 8 8 8 4 4 2 6 2 6 8 8 8 8 8 8 6 4 2 8 8 8 1 1 1 1 1 1 1 10 11 1 12 13 1 1 1 1 1 1 1 14 15 1 16 17 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] X W W W W W W WX W W W W W WX W W W W W W WX X W W W W W W WX W W W W W WX W W W WX                            3 7 58 8 8 8 0 2 4 6 1 3 5 7 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x x x x x x W W W x                                             2 3 84 4 4 4 8 22 2 84 4 33 2 84 4 4 1 0 0 01 1 1 1 0 1 0 0 01 2 3 0 0 01 1 4 5 0 0 01 6 7 0 1 2 3 4 5 6 7 [ ] [ ] [ ] [ ] ; ; ; [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] ; [ ] [ ] [ ] [ ] Even Odd T T Top Bottom x x WW W W x x WW W x x WW W W x x X X X X X X X X                                           W D X X X X 4 8 4 4 8 4 Top Even OddBottom                 X W D W x W D W xX sites.google.com/site/ncpdhbkhn 94 The Fast Fourier Transform Idea Using a Matrix Approach (4) 4 8 4 4 8 4 Top Even OddBottom                X W D W x W D W xX 2 22 / / point DFT : &E N E O N O N W  X W x X x T E N O B E N O      X X D X X X D X N – point Input Sequence N/2 – point Sequence N/2 – point Sequence N/2 – point DFT N/2 – point DFT Merge N/2 – point DFT N – point DFT Coefficients n Even n Odd [ ]Ox n[ ]Ex n [ ]EX k [ ]OX k [ ]X k N – point FFT sites.google.com/site/ncpdhbkhn 95 The Fast Fourier Transform Idea Using a Matrix Approach (5) 2 4 6 3 5 7 8 8 8 8 8 8 8 4 4 2 6 2 6 8 8 8 8 8 8 6 4 2 3 7 5 8 8 8 8 8 8 8 2 4 6 3 5 7 8 8 8 8 8 8 8 4 4 2 6 2 6 8 8 8 8 8 8 6 4 2 8 8 8 1 1 1 1 1 1 1 10 11 1 12 13 1 1 1 1 1 1 1 14 15 1 16 17 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] X W W W W W W WX W W W W W WX W W W W W W WX X W W W W W W WX W W W W W WX W W W WX                            3 7 58 8 8 8 0 2 4 6 1 3 5 7 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x x x x x x W W W x                                         2 4 6 2 4 6 8 8 8 8 8 8 4 4 4 4 8 8 8 8 6 4 2 6 4 2 8 8 8 8 8 8 2 3 2 3 8 8 8 8 8 8 3 6 3 6 8 8 8 8 8 8 5 2 7 5 2 7 8 8 8 8 8 8 7 6 5 8 8 8 1 1 1 1 1 1 1 10 1 12 1 1 1 14 1 16 1 11 1 13 1 15 17 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] X W W W W W WX W W W WX W W W W W WX W W W W W WX W W W W W WX W W W W W WX W W WX                            7 6 58 8 8 0 1 2 3 4 5 6 1 7 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x x x x x x W W W x                                         4 4 4 8 4 8 E T O B                  X W W x X W D W D x The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFTransform Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms a) Algebraic Derivation b) Practical Programming Considerations c) Alternative Forms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 96 sites.google.com/site/ncpdhbkhn 97 Algebraic Derivation (1) 1 0 0 1 1[ ] [ ] , , ,..., N kn N n X k x n W k N      1 1 2 2 2 2 1 0 0 2 2 1( ) ( )[ ] [ ] N N k m k m N N m m x m W x m W          1 1 2 2 2 2 0 0 2 2 1( ) ( )[ ] [ ] N N k m k k m N N N m m x m W W x m W         2 0 1 2 2 1 2 1 0 1 2 2 1 [ ] [ ], , , ,..., / [ ] [ ], , , ,..., / a n x n n N b n x n n N        2 1 2 0 2 1 2 0 0 1 1 0 1 2 1 0 1 2 1 / / / / [ ] [ ] [ ], , ,..., [ ] [ ] , , ,..., / [ ] [ ] , , ,..., / k N N km N m N km N m X k A k W B k k N A k a m W k N B k b m W k N                  2 2/N NW W sites.google.com/site/ncpdhbkhn 98 Algebraic Derivation (2) 0 1 2 1[ ] [ ] [ ], , ,..., /kNX k A k W B k k N    2 2 2 2 Nk N N N NX k A k W B k                      2 [ ] [ ]kN NX k A k W B k       2 Nk k N NW W       0 1 1 2 0 1 1 2 2 k N k N NX k A k W B k k N NX k A k W B k k             [ ] [ ] [ ], , ,..., [ ] [ ], , ,..., sites.google.com/site/ncpdhbkhn 99 Algebraic Derivation (3) 8DFT 0 1 2 3 4 5 6 7 0 7[ ] { [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]},X k x x x x x x x x k   Ex. [ ]X k  4DFT 1 3 5 7 0 3[ ] { [ ], [ ], [ ], [ ]},B k x x x x k   4DFT 0 2 4 6 0 3[ ] { [ ], [ ], [ ], [ ]},A k x x x x k   2DFT 0 4 0 1[ ] { [ ], [ ]}, ,C k x x k  2DFT 2 6 0 1[ ] { [ ], [ ]}, ,D k x x k  2DFT 1 5 0 1[ ] { [ ], [ ]}, ,E k x x k  2DFT 3 7 0 1[ ] { [ ], [ ]}, ,F k x x k  2 8 2 8 0 1 2 0 1 [ ] [ ] [ ], , [ ] [ ] [ ], , k k A k C k W D k k A k C k W D k k        2 8 2 8 0 1 2 0 1 [ ] [ ] [ ], , [ ] [ ] [ ], , k k B k E k W F k k B k E k W F k k        8 8 0 1 2 3 2 0 1 2 3 [ ] [ ] [ ], , , , [ ] [ ] [ ], , , , k k X k A k W B k k X k A k W B k k          sites.google.com/site/ncpdhbkhn 100 Algebraic Derivation (4) 8DFT 0 1 2 3 4 5 6 7 0 7[ ] { [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]},X k x x x x x x x x k   Ex. 2 8 2 8 0 1 2 0 1 [ ] [ ] [ ], , [ ] [ ] [ ], , k k A k C k W D k k A k C k W D k k        1 1 1 1 r m m N m r m m N m X p X p W X q X q X p W X q           [ ] [ ] [ ] [ ] [ ] [ ] 1[ ]mX p 1[ ]mX q [ ]mX p [ ]mX q r NW 1 sites.google.com/site/ncpdhbkhn 101 Algebraic Derivation (5) 8DFT 0 1 2 3 4 5 6 7 0 7[ ] { [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]},X k x x x x x x x x k   Ex. 0 1 2 3 4 5 6 7 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] x x x x x x x x 0[ ]x 4[ ]x 2[ ]x 6[ ]x 1[ ]x 5[ ]x 3[ ]x 7[ ]x Merge two 1 – point DFTs Merge two 1 – point DFTs Merge two 1 – point DFTs Merge two 1 – point DFTs Merge two 2 – point DFTs Merge two 4 – point DFTs Merge two 4 – point DFTs 0 4 [ ] [ ] x x 2 6 [ ] [ ] x x 1 5 [ ] [ ] x x 3 7 [ ] [ ] x x 0 2 4 6 [ ] [ ] [ ] [ ] x x x x 1 3 5 7 [ ] [ ] [ ] [ ] x x x x 0 1 2 3 4 5 6 7 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] X X X X X X X X Algebraic Merging The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFTransform Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms a) Algebraic Derivation b) Practical Programming Considerations c) Alternative Forms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 102 sites.google.com/site/ncpdhbkhn 103 Practical Programming Considerations 0[ ]x 0[ ]X 4[ ]x 1[ ]X 2[ ]x 2[ ]X 6[ ]x 3[ ]X 1[ ]x 4[ ]X 5[ ]x 5[ ]X 3[ ]x 6[ ]X 7[ ]x 7[ ]X 0 8W 0 8W 0 8W 0 8W 1 1 1 1 0[ ]C 1[ ]C 0[ ]D 1[ ]D 0[ ]E 1[ ]E 0[ ]F 1[ ]F 0[ ]A 1[ ]A 2[ ]A 3[ ]A 0[ ]B 1[ ]B 2[ ]B 3[ ]B 0 8W 2 8W 2 8W 0 8W 1 8W 0 8W 3 8W 2 8W 1 1 1 1 1 1 1 1 Stage 1 Stage 1 Stage 1 The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFTransform Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms a) Algebraic Derivation b) Practical Programming Considerations c) Alternative Forms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 104 sites.google.com/site/ncpdhbkhn 105 Alternative Form (1) sites.google.com/site/ncpdhbkhn 106 Alternative Form (2) The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFTransform Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 107 sites.google.com/site/ncpdhbkhn 108 Decimation – in – Frequency FFT Algorithms (1) 1 0 0 1 1[ ] [ ] , , ,..., N kn N n X k x n W k N      1 1 2 2 0 0 2 0 1 1 2 ( ) /[ ] [ ] [ ] , , ,..., N N k n kn N N n n NX k x n W x n W k          1 1 2 2 2 2 2 0 0 2 / /[ ] N N Nk k kn N N n n Nx n W x n W                1 1 2 2 2 2 0 0 2 / /[ ] N N kn kn N N n n Nx n W x n W            1 2 2 0 0 1 1 2 2/ [ ] , , ,..., N kn N n N Nx n x n W k              1 2 2 0 2 1 0 1 1 2 2/ [ ] [ ] , , ,..., N n kn N N n N NX k x n x n W W k                  sites.google.com/site/ncpdhbkhn 109 Decimation – in – Frequency FFT Algorithms (2) 1 2 2 0 1 2 2 0 0 1 1 2 2 2 1 0 1 1 2 2 / / [ ] [ ] , , ,..., [ ] [ ] , , ,..., N kn N n N n kn N N n N NX k x n x n W k N NX k x n x n W W k                                   2 0 1 2 1 2 0 1 2 1 [ ] [ ] [ / ], , ,..., / [ ] [ ] [ / ] , , ,..., /nN a n x n x n N n N b n x n x n N W n N           1 2 2 0 1 2 2 0 0 1 1 2 0 1 1 2 / / [ ] [ ] , , ,..., [ ] [ ] , , ,..., N kn N n N kn N n NA k a n W k NB k b n W k             2 0 1 1 2 2 1 0 1 1 2 [ ] [ ], , ,..., [ ] [ ], , ,..., NX k A k k NX k B k k          sites.google.com/site/ncpdhbkhn 110 Decimation – in – Frequency FFT Algorithms (3) 8DFT 0 1 2 3 4 5 6 7 0 7[ ] { [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]},X k x x x x x x x x k   Ex. 8 4 4 [ ] [ ] [ ] [ ] ( [ ] [ ]) n a n x n x n b n x n x n W       0 0 0 1 1 2 1 3 2 4 2 5 3 6 3 7 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] A X B X A X B X A X B X A X B X         2 8 2 8 2 2 2 2 [ ] [ ] [ ] [ ] ( [ ] [ ]) [ ] [ ] [ ] [ ] ( [ ] [ ]) n n c n a n a n d n a n a n W e n b n b n f n b n b n W             sites.google.com/site/ncpdhbkhn 111 Decimation – in – Frequency FFT Algorithms (4) 8DFT 0 1 2 3 4 5 6 7 0 7[ ] { [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]},X k x x x x x x x x k   Ex. 1 2 2 0 1 2 2 0 0 1 1 2 0 1 1 2 2 0 1 1 2 2 1 0 1 1 2 / / [ ] [ ] , , ,..., [ ] [ ] , , ,..., [ ] [ ], , ,..., [ ] [ ], , ,..., N kn N n N kn N n NA k a n W k NB k b n W k NX k A k k NX k B k k                    0 0 1 0 0 1 0 1 2 4 0 0 1 1 2 1 0 1 3 6 0 0 1 0 1 1 0 1 2 5 0 0 1 1 3 1 0 1 3 7 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] C c c A X C c c A X D d d A X D d d A X E e e B X E e e B X F f f B X F f f B X                                   1 1 1 1 [ ] [ ] [ ] [ ] ( [ ] [ ]) m m m r m m m N X p X p X q X q X p X q W         1[ ]mX p 1[ ]mX q [ ]mX p [ ]mX q r NW 1 sites.google.com/site/ncpdhbkhn 112 Decimation – in – Frequency FFT Algorithms (5) 8DFT 0 1 2 3 4 5 6 7 0 7[ ] { [ ], [ ], [ ], [ ], [ ], [ ], [ ], [ ]},X k x x x x x x x x k   Ex. 0[ ]x 0[ ]X 1[ ]x 4[ ]X 2[ ]x 2[ ]X 3[ ]x 6[ ]X 4[ ]x 1[ ]X 5[ ]x 5[ ]X 6[ ]x 3[ ]X 7[ ]x 7[ ]X 0 8W 2 8W 2 8W 0 8W 1 8W 0 8W 3 8W 2 8W 1 1 1 1 1 1 1 1 0 8W 0 8W 0 8W 0 8W 1 1 1 1 The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications sites.google.com/site/ncpdhbkhn 113 sites.google.com/site/ncpdhbkhn 114 Generalizations and Additional FFT Algorithms (1) 2 1 2 1 1 2 2 1 1 2 1 1 2 2 0 1 1 0 1 1 0 1 1 0 1 1 , , ,..., , , ,..., , , ,..., , , ,..., n N n n n N n N k k N k n N n N             2 1 2 1 1 2 1 2 1 2 2 2 1 1 2 1( )( )nk N n n k N k Nn k N n k N n k n k        1 2 2 1 1, ,N NNN N N N NW W W W W   1 0 0 1 1[ ] [ ] , , ,..., N kn N n X k x n W k N      2 1 2 1 2 1 1 2 2 1 1 1 1 1 2 2 1 2 0 0 ( )( )[ ] [ ] N N N n n k N k N n n X k N k x N n n W            2 1 1 1 1 2 2 2 1 2 2 1 1 1 2 1 2 0 0 [ ] N N k n k n k n N N N n n x N n n W W W               sites.google.com/site/ncpdhbkhn 115 Generalizations and Additional FFT Algorithms (2) 2 1 1 1 1 2 2 2 1 2 2 1 1 1 1 1 2 2 1 2 0 0 [ ] [ ] N N k n k n k n N N N n n X k N k x N n n W W W                2 1 2 1 2 [ ] [ ]nx n x N n n  1 1 2 2 1 1 1 1 1 0 [ ] [ ] N k n n n N n X k x n W      2 1 2 2 2 2 2 2 1 1 1 2 1 0 [ ] [ ] N k n k n N n N n X k N k W X k W       1 2 1 22 1 [ ] [ ]k nk N nx n W X k 2 2 2 1 2 2 1 1 1 2 2 0 [ ] [ ] N k n k N n X k N k x n W       Generalizations and Additional FFT Algorithms (3) 1. Form the N2 decimated sequences compute the N1 – point DFT of each sequences. 2. Multiply each N1 – point DFT by the twiddle factor: 3. Compute the N2 – point DFTs of the N1 sequences determined from step 2. sites.google.com/site/ncpdhbkhn 116 2 1 2 1 2 [ ] [ ],nx n x N n n  1 2 1 22 1 [ ] [ ].k nk N nx n W X k The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications a) Goertzel’s Algorithm b) Chirp Transform Algorithm c) Sliding DFT sites.google.com/site/ncpdhbkhn 117 sites.google.com/site/ncpdhbkhn 118 Goertzel’s Algorithm (1) 1 0 0 1 1[ ] [ ] , , ,..., N kn N n X k x n W k N      1kNNW   1 1 0 0 ( )[ ] [ ] [ ] N N kN kn k N n N N N n n X k W x n W x n W           3 4 4 0 4 ( )[ ] [ ] k n n N X k x n W       2 3 4 4 4 4 43 2 1 0[ ] [ ] [ ] [ ] k k k kx W x W x W x W          4 4 4 43 2 1 0[ ] [ ] [ ] [ ]k k k kW x W x W x W x       sites.google.com/site/ncpdhbkhn 119 Goertzel’s Algorithm (2)    4 4 4 43 2 1 0[ ] [ ] [ ] [ ] [ ]k k k kX k W x W x W x W x       4 4 4 4 4 4 1 0 0 0 1 1 1 0 2 2 1 3 3 2 4 4 3 3 [ ] , [ ] [ ] [ ], [ ] [ ] [ ], [ ] [ ] [ ] [ ] [ ] [ ], [ ] [ ] [ ] [ ] k k k k k k k k k k k k k k k k k k y y x W y y x W y y x W y y x W y y x W y W y                     1 0[ ] [ ] [ ], [ ] [ ] k k N k k y n W y n x n n N X k y N       The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications a) Goertzel’s Algorithm b) Chirp Transform Algorithm c) Sliding DFT sites.google.com/site/ncpdhbkhn 120 sites.google.com/site/ncpdhbkhn 121 Chirp Transform Algorithm 1 0 0 1 1[ ] [ ] , , ,..., N kn N n X k x n W k N      2 2 21 2 [ ( ) ]kn k n k n    2 2 21 2 2 2 0 ( ) [ ] [ ] k n k nN N N N n X k x n W W W       2 2 21 2 2 2 0 ( ) [ ] k n k nN N N N n x n W W W                2 2 22 2 2 0 1/ / /[ ] * ,n n nN N Nx n W W W n N      2 2/ ( / )[ ] n j n N nNh n W e   2 2/[ ] * [ ] [ ] [ ] n N x n W h nX k h n      The Discrete Fourier Transform 1. Computational Fourier Analysis 2. The Discrete Fourier Transform 3. Sampling the Discrete – Time Fourier Transform 4. Properties of the Discrete Fourier Transform 5. Linear Convolution Using the DFT 6. Fourier Analysis of Signals Using the DFT 7. Direct Computation of the DFT 8. The FFT Idea Using a Matrix Approach 9. Decimation – in – Time FFT Algorithms 10. Decimation – in – Frequency FFT Algorithms 11. Generalizations and Additional FFT Algorithms 12. Computation of DFT for Special Applications a) Goertzel’s Algorithm b) Chirp Transform Algorithm c) Sliding DFT sites.google.com/site/ncpdhbkhn 122 sites.google.com/site/ncpdhbkhn 123 Sliding DFT 1 0 1 1 0 otherwise [ ], [ ] , ,n x n N m m N x m n N         1 1 0 0 1 1 0 1[ ] [ ] [ ] , , N N mk mk n n N N m m X k x m W x n N m W n N k N                1 1 1 0 1 0 1 0 1 { [ ] [ ] [ ]} , , [ ] [ ] , k n N N mk N N m X k x n x n N W n N k N X k x n W k N                   0 1N  n N 1n  n 1n N  n 1[ ]nx m [ ]nx m1[ ]Nx m