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 − = = −
9.1.1 Direct Evalutation of the Defination of DFT ◆Conjugate symmetry: WN-”=W=(W农）* RefX[k)->[RefnB Rew)-Imfxn}ImW] n=0 group terms in the summation for n and/(N-n): Refxn}RefWA"y Refxn']ReW n-0 n=2 n'=N-n,n=N-n' except n=0,N/2): N_ RefxN-n}ReWN-"l n= >[RefXnB ReW)+RefxN-nB Re(WSIN-n] →1 ->[(RefxrB+RefxN-nB)RefW] eWs 乘法次数减少近以一半 generally N=2
7 9.1.1 Direct Evalutation of the Defination of DFT ◆Conjugate symmetry: group terms in the summation for n and (N-n): 1 0 [ ] [ ] N n kn kn Re Re Re I X k x n W x n W N N m Im − = = − 1 1 2 [ ] [ ] [ ] N N n N kn N n k Re Re Re x x W n N n W Re − = − + − ( ) 1 1 2 [ ] [ ] N n N kn R e e e R x x W n R N n − = = + − N kn Re W 1 1 0 2 2 [ ] [ ] N + n N N n N N k k n n Re Re Re Re x W x n n W − − = = 1 2 [ ] [ ] N n N N n k N n Re e x W R = − − 乘法次数减少近似一半 except n=0,N/2): 1 2 [ ] N N n N kn Re e x n R W − = n N n n N n = = − − ， generally N=2r ( ) ( )* k k k N N N n N W W W − − n n = =
9.1.1 Direct Evalutation of the Defination of DFT ◆Conjugate symmetry: WN-m=Wm=(W农)* Re(X[I-∑Ren)ReW Im{n)ImW】 group terms in the summation for n and (N-n): (except n=0,N/2): IRefxiuil Re+Re(x{N-nBRetm] ->[(Re(xrb+Re(N-nb)ReW ReWN" similarly, >[Imfxn)ImW+Im{N-n)ImWN 乘法次数减少近以一半 L-ImW" >[(Im{xn)-Im{xN-nB)ImW
8 9.1.1 Direct Evalutation of the Defination of DFT ◆Conjugate symmetry: group terms in the summation for n and (N-n): 1 0 [ ] [ ] N kn kn N N n Re Re Re I X k x n W x n W m Im − = = − 1 1 2 [ ] [ ] [ ] N N n N kn N n k Re Re Re x x W n N n W Re − = − + − ( ) 1 1 2 [ ] [ ] N n N kn R e e e R x x W n R N n − = = + − N kn Re W 1 1 2 [ ] [ ] [ ] N N + n N kn N n k Im Im x W n N n Im Im x W − = − − − ( ) 1 1 2 [ ] [ ] N n N kn Im Im x n N n x W Im − = =− − − N kn −Im W similarly, 乘法次数减少近似一半 (except n=0,N/2): ( ) ( )* k k k N N N n N W W W − − n n = =
9.1.2 The Goertzel Algorithm ◆Sinc W e-eJ2rlkN=elπ/NkW=e2ak-l Multiply DFT equation with this factor X图-e2xv∑ire2aN-∑rkex/Hv- hin-r] ◆Define小-=之re2zun-r]=m*M列l 0≤≤W-1 n=N,0sr≤W-1 using x[n]=0 for nN-1, velnli=X[闪 yun]can be viewed as output of a filter to input x[n] Filter impulse response Hnj-erNun] Goertzel Filter X[k]is the output of the filter at time n=N. DFT of x[n]:X[k]=yalnll-N=xn]*hnll-N
9 ◆yk [n] can be viewed as output of a filter to input x[n] ◆Filter impulse response : ◆X[k] is the output of the filter at time n=N. 9.1.2 The Goertzel Algorithm ◆Since ◆Multiply DFT equation with this factor (2 / 2 / ) ( ) 2 1 kN N W j j N kN N kN j k e e e − − − = = = = ( ) ( ) 1 0 2 / 2 / [ ] r k N j k N N j N r X k x e er − = − = k n N y n X k = = ( ) 2 / [ ] j N kn h u n n e = ( ) ( ) 2 / [ ] k r j k N n r y n x r u e n r =− − ◆Define = − ◆using x[n]=0 for nN-1, ( ) ( ) 1 0 2 / [ ] N r j k N N r x r e − = − = h[ ] n r − =x n h n [ ]* [ ] 0 -1 r N n N= ，0 -1 r N Goertzel Filter DFT of x[n]: the filter is a [ ]* [ ] X k = = yk n n N= x n h n n N= ( ) 0 1 2 / [ ] , N n j N kn X k x n e = − − =
9.1.2 The Goertzel Algorithm ◆Goertzel Filter: n-eNn]="4刊 x(n] yk[n] =H(2)=i 7 21 k=0,1,.,W-1 for causal LTI system x[n]=0,n<0→yk[n]=0,n<0 [n]=[n-l]W*+n,n=01,,N,-1]=-0 x[n]is a complex X[]=[nlw,k=0,1,,N-l→ X-∑[nWg n=0 Computational complexity for one X[k]:for all X[k]: 4N real multiplications;4N real additions;x N Slightly less efficient than the direct method(4N,4N-2);x N But it avoids computation and storage of W (N2) W吸N个)
10 9.1.2 The Goertzel Algorithm ◆Goertzel Filter: (2 / ) [ ] [ ] j N kn h n u n e = ( ) 1 1 1 k k N H z W z = − − − [ ] [ 1] [ ], k y n y n W x n k k N − = − + , k n N X k y n = = kn ◆ WN But it avoids computation and storage of [ ] kn W u n N − = n N = 0,1,..., , k N = 0,1,..., -1 x n[ ] is a complex for causal LTI system x[n]=0, n<0 → yk [n]=0, n<0 k N = 0,1,..., -1 (N2 个) k WN (N 个) , 1 z yk [ 1] 0 − = ( )( ) ( ) [ ] [ 1] [ 1] [ ] [ ] k k y n y n y n W W k k k N N Re Im Re x n x Im Re j j jIm n − − = − + − + + + 1 0 [ ] [ ] N kn kn N N n X k x n W Re Re Im x n W Im − = = − 1 0 [ ] N kn N n X k x nW − = = ×N ◆Computational complexity for one X[k]: ◆4N real multiplications; 4N real additions; ◆Slightly less efficient than the direct method(4N, 4N-2); for all X[k]: ×N ( ) ( ) [ ] [ 1] [ 1] [ 1] [ 1] [ ] [ ] k k k k N k N k k k N k N Re Re Im Im Re Im Im Re y n y n W y n W y n W y n W Re x n jIm x j n − − − − = − − − − + − + + +
Second Order Goertzel Filter 为便于分析 ◆Goertzel Filter x[n] -1 y(n] cos N H,)-W欢*云1-袋*z -W x[n]=0,n<0 Multiply both numerator and denominator with for causalLTI system (1-e*2-1) 1-W啖z1 (a) a0。可 1-2cos2z+z2X阿 -1]=[-2]=0。 m-2+2c0s24-+xm,n=01N y[0]=x[0] n]=n]-Wn-] 实现零点因式 实现极点因式 每个K需计算N次 y[N]MN]WNMN-1]-XIk],k=0,1,...,N-1 y],y2]…yLW] 每个K只需计算1次
Second Order Goertzel Filter ◆Goertzel Filter ( ) ( )( ) 2 1 1 2 1 2 (1 ) 1 1 j k j k N k j N N k e e z H z z e z − − − − − − − = − [ ] [ ] [ 1] k y W k N N = − y y N N − =Xk, k=0,1,..., -1 N 1 1 2 1 2 1 2cos k N z k W z z N − − − − = − + ( ) 1 1 1 k k N H z W z = − − − 1 2 1 1 j k e N z − = − y y [ 0 −1] [ ] = = −2 y n[ ] Multiply both numerator and denominator with [ ] [ ] [ 1] k y W k n n = − y y n N − n N = 0,1,..., [ ] k y n 实现极点因式 实现零点因式 x[n]=0, n<0 y n[ ] 为便于分析 每个K只需计算1次 每个K需计算N次: for causal LTI system y y y N [1], [2] [ ] 11 2 [ ] y n y n x n [ 2] 2cos [ 1] [ ], N y n k =− − + − + ( ) ( ) k z Y z X = y[0]=x[0]