《《快速傅里叶变换》PPT课件》由会员分享，可在线阅读，更多相关《《快速傅里叶变换》PPT课件（23页珍藏版）》请在金锄头文库上搜索。
1、3.3 radix-2 Decimation-In-Frequency FFT3.3 radix-2 Decimation-In-Frequency FFTDecimation-in-time FFT algorithm are based on structuring the DFT computation by forming smaller and smaller subsequences of the input sequence xn. Alternatively, we can consider dividing output sequence Xk into smaller an
2、d smaller subsequences in the same manner. FFT based on this procedure are called decimation-in-frequency algorithms.11. Basic principle of radix-2 DIF-FFTFirstly, separate input sequence x(n) into two groups-first half and last half, then compute its DFT:into even-numbered frequency samples (k=2r)a
3、nd the odd-number frequency samples (k=2r+1)Separate 2First half and last halfFirst half and last half3DIT-FFT Basic structureDIT-FFT Basic structureDifference?Decompose in time-domain according to odd and even Decompose in time-domain according to odd and even Decompose in first half and last half
4、in frequency-domain Decompose in first half and last half in frequency-domainDecompose in frequency-domain according to odd and even Decompose in frequency-domain according to odd and even Decompose in first half and last half in time-domain Decompose in first half and last half in time-domainis dec
5、omposed into 2 pointsis decomposed into 2 points4DFT DFT N/2N/2x x2 2(n)(n)DFT DFT N/2N/2x x1 1(n)(n)8-point DIF-FFT8-point DIF-FFTProceed separating N/2 points DFT, until Proceed separating N/2 points DFT, until get the whole flow graph of DIF-FFTget the whole flow graph of DIF-FFT5m=0m=0m=1m=1m=2m
6、=28-point DIF-FFT8-point DIF-FFT62. 2. Butterfly computationButterfly computation“ “butterfly” elementbutterfly” element- -Add firstAdd firstMultiply secondMultiply secondDifference with DIT-FFTBasic computation:Basic computation:m is the levels index, the most left levels m=0;m is the levels index,
7、 the most left levels m=0;p,q is the sequence number of upper nodes and lower nodes.p,q is the sequence number of upper nodes and lower nodes.Determination of S in : S=2Determination of S in : S=2mm p pDistance between two node pair: Distance between two node pair: 73. 16 points DIF-FFT (Input in no
8、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.893.4 Inverse FFT3.4 Inverse FFT1. Comparison of FFT Transformation PairDifference between FFT and I
9、FFT：（1）Constant：1/N（2）Sign of W factorFFT and IFFT:Same program?Same structure?10Let2. Computation of IFFT by FFT AlgorithmMethod 1:IdeaIdea：Change W factor into W factor in DFT (Sign)Change W factor into W factor in DFT (Sign)Process: Process: ( (a) Compute X(k)s FFT, Acquire g(n)a) Compute X(k)s F
10、FT, Acquire g(n) (b) Compute x(n)=g(N-n)/N (b) Compute x(n)=g(N-n)/N11Method 2：IdeaIdea：Change W factor into W factor in DFT (Sign)Change W factor into W factor in DFT (Sign)令令 Process:Process: （a a）Compute X(k), and acquire its conjugate form X*(k)Compute X(k), and acquire its conjugate form X*(k)
11、（b b）Compute X*(k)s FFT, acquireCompute X*(k)s FFT, acquire g(n)g(n) （c c）Compute x(n)=g*(n)/NCompute x(n)=g*(n)/N12Let and:Because DFT is a linear transform:3.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 s
12、imultaneously by one N-points FFT.Suppose x1(n) and x2(n) are two interdependent real sequence, their DFT are: 132. Compute 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
13、(2n)， x2(n)=x(2n+1)，n=0,1,2,.N-1Based on symmetric property:14Similar with DIT-FFTSimilar with DIT-FFT2N2N points DFT first half:points DFT first half:2N2N points DFT last half:points DFT last half:153.6 Linear convolution by FFTFilterh(n)x(n)y(n)Too large to compute1. Objective（1）Background Filter
14、h(n), length N1, long input sequence x(n), then:（2）Problems When computation linear convolution using circular convolution, too many zeros are padded, low efficiency.（3）Solution Decomposition computation on long sequence. Two different ways: Overlap-add method; Overlap-save method 162 Overlap-add me
15、thod（1）Basic concept Decompose long sequence x(n) into N2 short sequence xi(n):We 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).172 Overlap-add methodBecause: yi(n)s length N， xi(n)
16、 s length N2，Overlapping after zero padding.Overlap between two next 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) 18 （2）Computing
17、 process (A) Compute N1 points filter h(n)s H(k), H(k)=DFTh(n) (B) Compute 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:：192 Overlap-save methodBasic idea of overlap-save method is to compute N
18、 point sequence xi(n) and M point sequence h(n)s N points circular convolution. Then extract the part that circular convolution equals to linear convolution. n202 Overlap-save methodZero Zero paddingpaddingFrom the figure:yi(n)s last N2 points is accurate value of linear convolution.Key 1:Decompose
19、Key 1:Decompose x(n) into a x(n) into a series of series of overlapoverlap parts. parts. DeleteDeleteKey 2: Key 2: SaveSave x(n)s last x(n)s last N N2 2 points.points.Overlap-save methodDeleteDeleteDeleteDelete21（2）Computation process(a) Decompose x(n) :(b) Compute yi(n)=xi(n) h(n) by FFT (c) Delete
20、 the first N1-1 points value of yi(n)（3）Comparison of two methods: (a) Equal computation costs. (b) Overlap save method can omit the final part of overlap adding method: adding.22SummarySummary1.1.How to compute real sequences FFTHow to compute real sequences FFTHow to compute real sequences FFTHow to compute real sequences FFT ；2. Overlap save method and overlap add 2. Overlap save method and overlap add 2. Overlap save method and overlap add 2. Overlap save method and overlap add method.method.method.method.23
