【正文】 DFT G(0) G(1) G(2) G(3) X(0) X(1) X(2) X(3) x(0) x(2) x(4) x(6) 4點 DFT H(0) H(1) H(2) H(3) X(4) X(5) X(6) X(7) x(1) x(3) x(5) x(7) WN1 WN2 WN3 1 1 1 1 a) FFT implementation of an 8point DFT using two 4point DFTs Engineering college, Linyi Normal University 2點 2點 2點 2點 b) FFT implementation of an 8point DFT as two 4point DFTs and four 2point DFTs Engineering college, Linyi Normal University c) Full decimationintime FFT implementation of an 8point DFT Engineering college, Linyi Normal University ? The putation times for FFT ? Stages : v=log2N ? Butterflies of each stage: N/2 ? Each butterfly: 1 plex multiplications and 2 plex additions ? Npoint FFT: (N/2log2N) plex multiplications and (Nlog2N) plex additions ? Computing DFT directly: N2 plex multiplications and N(N1) plex additions Engineering college, Linyi Normal University For example: N=210=1024 DFT: plexmul. N2=220=1048576 plexadd. N(N1)=1024 1023=1047552 FFT: plexmul. N/2log 2N =5120 plexadd. Nlog 2N =10240 Assume: 1 plexmul. 100us 1 plexadd. 20us Then DFT needs , and DFT needs only. Engineering college, Linyi Normal University ? Inplace putation ? We needn’t to open another memory to store the output of each stage, because the former data we will not use again in later putation. ? Example x(0) x(4) G1(0) G1(1) 00( 0) ( 4)( 0) , [ ( 0) ]( 0) ( 4)( 1 ) , [ ( 4) ]NNx W xA re plac e t he ori ginal data xx W xA re plac e t he ori ginal data x??????Engineering college, Linyi Normal University ? Order of input sequence x(n) Engineering college, Linyi Normal University Summarization ? Let N=2v。 LEngineering college, Linyi Normal University /2/20/2/20( ) ( ) ( / 2) 。 LFor example: N=8, the flow graph is shown below x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) 1 1 1 1 N/2點 DFT g(0) g(1) g(2) g(3) N/2點 DFT h(0) h(1) h(2) h(3) WN1 WN2 WN3 X(0) X(2) X(4) X(6) X(1) X(3) X(5) X(7) Engineering college, Linyi Normal University Repeat this operation again, we may obtain the following graphs four 2point DFTs Engineering college, Linyi Normal University DIFFFT flow graph for input in normal order and output in bitreversed order Engineering college, Linyi Normal University ? Computation times Complex multiplication: N/2log2N plex additions: Nlog2N ? Compare the DITFFT and DIFFFT’s flow graphs, we may obtain the following conclusion: Two flow graphs are just transposed each other. ? Inpalace putations NOTE: In this algorithm, the input data is in normal sequence, but the output data is in bitreverse sequence. Engineering college, Linyi Normal University ? Comparison of DITFFT and DIFFFT ? They have same number of plex multiplications and plex additions ? They are all inpalace putation ? DITFFT and DIFFFT are transposed each other ? They all need order sorting ? They have different iterative formulas Engineering college, Linyi Normal University Application of FFT algorithms ? Computing IDFT using FFT Compare the expression of DFT and IDFT ? Twiddle factor : ? Constant coefficient: 1/N So we have 1010( ) [ ( ) ] ( )1( ) [ ( ) ] ( )NnkNnNnkNkX k D FT x n x n Wx n I D FT X k X k WN==== 229。 y(n) Let: x(n)real part。[g(n)g*(n)]。[G(k)G *(Nk )] Engineering college, Linyi Normal University Example: x(n)=[1,2,0,1]。 ? Convolutiontime parison of using FFT versus DFT。 。 。,d。 Examples Engineering college, Linyi Normal University 參考書閱讀和作業(yè) ? Textbook: ~172 ? Chinese reference book: ~37, ~82 ,~109 ? Exercises: ? 1: ,d。 G*(Nk)=[4j6, j2, 2,2] Therefore: X(k)=[4,1j, 2,1+j] Y(k)=[6,1j, 0,1+j] Engineering college, Linyi Normal University