Chapter 9 Computation of the Discrete Fourier Transform 9.0 Introduction 9.1 Direct Computation Of The Discrete Fourier Transform 9.2 decimation-in-time FFT Algorithms 9.3 decimation-in-frequency FFT Algorithms 9.4 practical considerations 9.5 2
2 9.0 Introduction 9.1 Direct Computation Of The Discrete Fourier Transform 9.2 decimation-in-time FFT Algorithms 9.3 decimation-in-frequency FFT Algorithms 9.4 practical considerations 9.5 ...... Chapter 9 Computation of the Discrete Fourier Transform
9,0 Introduction Implement a convolution of two sequences by the following procedure: 1.Compute the N-point DFTXk and X2k of two sequencen and x2[n; X[闪-∑W 2.Compute for0≤k≤W-1i ◆3.Compute x,m=x[mx,[刊as the inverse DFT ofX[W· 网N-大空[kw -C Why not convolve the two sequences directly? Since DFT has efficient FFT(Fast Fourier Transform algorithms that can be orders of magnitude(数量级 2n,10)more efficient than others. 3
3 9.0 Introduction ◆1. Compute the N-point DFT and of two sequence and ; X k 1 X k 2 x n1 x n2 ◆2. Compute for ; X k X k X k 3 1 2 = 0 k N −1 ◆3. Compute as the inverse DFT of . X k 3 x3 n=x n1 N x n2 ◆Implement a convolution of two sequences by the following procedure: ◆Why not convolve the two sequences directly? ◆Since DFT has efficient FFT ( Fast Fourier Transform ) algorithms that can be orders of magnitude(数量级 2 n ,10n ) more efficient than others. 1 2 1 3 0 1 N kn N k x n N X k N x n W − − = = (( )) 1 3 1 2 0 1 2 N N m x n x m x n N n x x n m − = = = − 1 0 N kn N n X k n x W − = =
9.1 Direct Computation of the Discrete Fourier Transform The DFT pair was given as X∑meRx,XT个eR 0≤k,n≤W-1 DFTcomputational complexity: Each DFT coefficientrequires N complex multiplications; N-1 complex additions All N DFT coefficients require N2 complex multiplications; N(N-1)complex additions D
4 9.1 Direct Computation of the Discrete Fourier Transform ◆The DFT pair was given as ( ) 1 0 1 2 / [ ] N k j N kn x n X k N e − = = ( ) 1 0 2 / [ ] , N n j N kn X k x n e − = − = ◆DFTcomputational complexity: ◆Each DFT coefficient requires ◆N complex multiplications; ◆N-1 complex additions ◆All N DFT coefficients require ◆N2 complex multiplications; ◆N(N-1) complex additions 0 1 − k n, N
9.1 Direct Computation of the Discrete Fourier Transform Most fast methods are based on Periodicity properties Periodicity of W in n and k; ej2z/N)kn_e-j(2z/N)k(n+N)-e j(2zlN)(k+N)n W农=WN+m=W+m, e2πN=W Complex conjugate symmetry W收N-w=W-()*, (WN-）*-(W）*=WW ej2π/Nk(N-m=ej2m/N)kNe-j(2π/Wk(m三e/2π/WMkm (e2x1M）
( ) n N Wk N− 5 9.1 Direct Computation of the Discrete Fourier Transform ◆Most fast methods are based on Periodicity properties ◆Periodicity of in n and k; j(2 /N k N n ) ( ) e − − j(2 / 2 / N)kn k j( N) (n N) e e − − + = ( ) ( ) , kn N N k k n n W W W N N N + + = = ( ) ( )* ( )* N N N N W W W k k k −n n − n = = ◆Complex conjugate symmetry j(2 /N)(k n N) e − + = j(2 /N) e WN − = j(2 /N k) n e = ( )*, kn = WN j(2 / 2 / N k )kN N n j( ) ( ) e e − − − = kn WN − = ( ) ( ) 2 / * = j N nk e − n N Wk
9.1.1 Direct Evalutation of DFT Defination X[-∑Wg=∑ne2x n= =∑(Re{n+jImi(ReW}+jmw》 =>IReiAn那Rewy-mi}inW +j(Refxn}ImW+Imixn]ReW) k=0,1,2,…,N-1 Computational complexity in terms of real operations 4N2 real multiplications N(4N-2)real additions:N*2*(N+(N-1)
6 9.1.1 Direct Evalutation of DFT Defination ◆Computational complexity in terms of real operations ◆4N2 real multiplications ◆N(4N-2) real additions : N*2*( N+(N-1) ) ( ) 1 0 2 / [ ] N n j N kn x n e − = − = 1 0 N kn n X k n x WN − = = 1 0 [ ] [ ] N kn kn N N n Re Re Im x n W x n W Im − = = − ( [ ] [ ] ) kn kn Re Im Im Re x n W x N N + j + n W k N = − 0,1,2, , 1 ( )( ) 1 0 = [ ] [ ] N kn kn N N n Re Im Re Im x n x W W j n j − = + + 1 0 [ ] [ ] N kn kn N N n Re Re Re I X k x n W x n W m Im − = = −