快速傅里叶变换-02ppt课件

1、Decimation-in-time FFT algorithm are based on structuring the DFT computation b y f o r m i n g s m a l l e r a n d s m a l l e r subsequences of the input sequence xn. Alternatively, we can consider dividing output sequence Xk into smaller and smaller subsequences in the same manner. FFT based on t

2、his procedure are called decimation-in-frequency algorithms.1. Basic principle of radix-2 DIF-FFT /2 110/2( ) ( )NNknknNNnn NX kx n Wx n W/2 1/2 1()200( ) ()2NNNk nknNNnnNx n Wx nW/2 120( )() 2NNkknNNnNx nWx nW/2 1/2 1200( ) ()2NNNkknknNNNnnNx n Wx nWW/2 10( )1()2NkknNnNx nx nW 01kNFirstly, separate

3、 input sequence x(n) into two groups-first half and last half, then compute its DFT:kXinto even-numbered frequency samples (k=2r)and the odd-number frequency samples (k=2r+1)Separate 12/0 )2()1()()(NnknNkWNnxnxkX2/2 10(21)( )() 2NNnrnNnNXrx nx nWW22/2 1/2 11200(2 )( ) (21)( )NNNNrnrnnnXrx n WXrx n W

4、120)2()()()2()()(21 NnWNnxnxnxNnxnxnxnN， is even.k is odd.k2/2 10(2 )( )() 2NNrnnNXrx nx nW/2 11/20/2 12/20(2 )( ) (21)( )NrnNnNrnNnXrx n WXrx n W X k 122kNNX kXkW Xk1,.,1 , 02 Nk 12kNX kXkW XkDifference?0,1,.,21nN N/2 DFT:)0(x)1(x)2(x)3(x)4(x)5(x)6(x)7(x0NW1NW2NW3NW)0(X)2(X)4(X)6(X)1(X)3(X)5(X)7(X)

5、0(1x)1(1x)2(1x)3(1x)0(2x)1(2x)2(2x)3(2x1 1 1 1 0NW0NW0NW0NW0NW2NW0NW2NW0NW1NW2NW3NW)0(x)1(x)2(x)3(x)4(x)5(x)6(x)7(x)0(X)4(X)2(X)6(X)1(X)5(X)3(X)7(X1 1 1 1 1 1 1 1 1 1 1 1 SNmmmmmmWqXpXqXqXpXpX)()()()()()(11 )(1qXm )(1pXm )(pXm)(qXmsNWDifference with DIT-FFTsNW12 mNpq3. 16 points DIF-FFT (Input in no

6、rmal and output in bit-reversed order order)For each DIT-FFT, there exists a DIF-FFT that corresponds to interchanging the input and output and reversing direction of all the arrows in the flow graph.1. Comparison of FFT Transformation Pair1,.,0 10 NkWnxkXNnknN1,.0 W110kn-N NnkXNnxNkDifference betwe

7、en FFT and IFFT：（1Constant：1/N（2Sign of W factorFFT and IFFT:Same program?Same structure?1-knN01( ) WNkx nX kN Let2. Computation of IFFT by FFT AlgorithmMethod 1:Idea：Change W factor into W factor in DFT (Sign)1-knkNNN01 WWNkX kN 1(N-n)kN01 WNkX kN 1knN0 g(n) WNkX k )(1x(n)nNgN *11-kn*knNN0011( ) W

8、WNNkkx nX kXkNN Method 2：Idea：Change W factor into W factor in DFT (Sign)令令1*knN0 g(n) WNkXk (n)g N1x(n)* 11( )XkDFT x nLet and: 12( )( )y nx njx n ( )Y kDFT y n12( )( )-( )y nx njx n1211 ( )( )( )( )( )-( )22x ny ny nx ny ny nj，*11( )( )(-)2XkY kYNk 22( )XkDFT x n*21( )( )-(- )2XkY kYN kjBecause DF

9、T is a linear transform:( )DFT y nYNk3.5 FFT Algorithm for Real SequenceReal sequence x(n)s FFT computations memory and time cost is very large.1. Compute two real sequences FFT simultaneously by one N-points FFT.Suppose x1(n) and x2(n) are two interdependent real sequence, their DFT are: 2. Compute

10、 a 2-N points real sequences FFT by an N-points FFT.Suppose x(n) is a 2N points real sequence, separate x(n) into odd-numbered group x1(n) and even-numbered group x2(n): x1(n)=x(2n)， x2(n)=x(2n+1)，n=0,1,2,.N-1 1122( )( )XkDFT x nXkDFT x n12 ( )( )( )y nx njx n*1211( )( )(- )( )( )-(- )22X kY kYN kXk

11、Y kYN kj， -1-121200-1-122200 (2 )(2 )(2 ) (21)(21)(21)NNnknkNNnnNNnknkNNnnXkDFT xnxn Wxn WXkDFT xnxnWxnW X k ( )Y kDFT y n0,.1nN0,.1kNBased on symmetric property: 2-1-1-12(21)222000-1-12222200-1-112200122( )(2 )(21)(2 )(21)( )( )( )( )NNNnkrkrkNNNnrrNNrkkrkNNNrrNNrkkrkNNNrrkNX kx n Wxr WxrWxr WWxrWx

12、 r WWx r WX kWXk01kN122( )-( )kNX kNX kWXk 122( )( ),kNX kX kWXk01kN3.6 Linear convolution by FFTFilterh(n)x(n)y(n)Too large to compute1. Objective（1Background Filter h(n), length N1, long input sequence x(n), then:（2Problems When computation linear convolution using circular convolution, too many z

13、eros are padded, low efficiency.（3Solution Decomposition computation on long sequence. Two different ways: Overlap-add method; Overlap-save method 2 Overlap-add method（1Basic concept Decompose long sequence x(n) into N2 short sequence xi(n): notherN)i (niN)n(x01(n)x22i i(n)xx(n)i ii(n)yh(n)*(n)xh(n)

14、x(n)y(n)iiWe can see that computing convolution of each decomposed part of x(n) with h(n) respectively, then add outcome together, and finally acquiring the output sequence y(n).2 Overlap-add methodx(n)Because: yi(n)s length N， xi(n) s length N2，Overlapping after zero padding.Overlap between two nex

15、t parts length is: N-N2= N1 -1，Add overlap parts together, then acquire y(n)Compute every parts convolution using fast algorithm, zero padded xi(n) and h(n) to N=N1+N2-1, let:N=2m, compute using FFT: yi(n)= xi(n) h(n) （2Computing process (A) Compute N1 points filter h(n)s H(k), H(k)=DFTh(n) (B) Comp

16、ute N2 points sequence xi(n)s Xi(k), Xi(k) =DFTxi(n) (C) Compute Yi(k)= Xi(k)H(k) (D) Compute N points IFFT： yi(n) =IFFTYi(k) (E) Add the overlapping parts:： i(n)yy(n)i2 Overlap-save methodBasic idea of overlap-save method is to compute N point sequence xi(n) and M point sequence h(n)s N points circ

17、ular convolution. Then extract the part that circular convolution equals to linear convolution. ( ) ()clLqy ny nqL Rn 12And ( )s length is 1.ly nNN 21Suppose is a length sequence and is a length sequence, their linear convolution is:x nNh nN ( )() ()lmy nx nh nx m h nm 2( ) is two sequences point circular convolutioncy nN21NNn( )y n121NN2N2N2 Overlap-save method x nFrom the figure:yi(n)s last N2 points is accurate value of linear convolution.Overlap-save method（2Computation pro