【正文】 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點(diǎn) DFT g(0) g(1) g(2) g(3) N/2點(diǎn) 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。 h(n)=x(2r+1)={x(1),x(3),x(5),x(7)} 4點(diǎn) 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點(diǎn) 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點(diǎn) 2點(diǎn) 2點(diǎn) 2點(diǎn) 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。LLEngineering college, Linyi Normal University According to the inherent properties of DFT in k and n with period N/2,. , Obviously, we see that a Npoint DFT can be obtained by puting 2 N/2point DFT. Because N/2 is also even, then we can divide it into 2 N/4point. Similarly, we can divide a Npoint sequence into N/2 2point sequence. ( ) ( / 2) ( ) ( / 2)( ) ( ) ( )( / 2) ( ) ( )kNkNG k G k N H k H k NX k G k W H ksoX k N G k W H k= + = +236。239。239。239。238。= 229。 =239。=239。= + 239。= 239。= ?= * = 229。? Note: