1、1,3.3 radix-2 Decimation-In-Frequency FFT,Decimation-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 and smaller subsequences in the same m

2、anner. FFT based on this procedure are called decimation-in-frequency algorithms.,2,1. Basic principle of radix-2 DIF-FFT,Firstly, separate input sequence x(n) into two groups-first half and last half, then compute its DFT:,3,First half and last half,4,DIT-FFT Basic structure,Difference?,Decompose i

3、n time-domain according to odd and even Decompose in first half and last half in frequency-domain Decompose in frequency-domain according to odd and even Decompose in first half and last half in time-domain,is decomposed into 2 points,5,DFT N/2 x2(n),DFT N/2 x1(n),8-point DIF-FFT,Proceed separating

4、N/2 points DFT, until get the whole flow graph of DIF-FFT,6,7,2. Butterfly computation,Add first Multiply second,Difference with DIT-FFT,Basic computation:,m is the levels index, the most left levels m=0; p,q is the sequence number of upper nodes and lower nodes. Determination of S in : S=2mp Distan

5、ce between two node pair:,8,3. 16 points DIF-FFT (Input in normal 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.,9,10,3.4 Inverse FFT,1. Comparison

6、of FFT Transformation Pair,Difference between FFT and IFFT： （1）Constant：1/N （2）Sign of W factor,FFT and IFFT: Same program? Same structure?,11,Let,2. Computation of IFFT by FFT Algorithm,Method 1: Idea：Change W factor into W factor in DFT (Sign),Process: (a) Compute X(k)s FFT, Acquire g(n) (b) Compu

7、te x(n)=g(N-n)/N,12,Method 2： Idea：Change W factor into W factor in DFT (Sign),令,Process: （a）Compute X(k), and acquire its conjugate form X*(k) （b）Compute X*(k)s FFT, acquire g(n) （c）Compute x(n)=g*(n)/N,13,Let and:,Because DFT is a linear transform:,3.5 FFT Algorithm for Real Sequence Real sequence

8、 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:,14,2. Compute a 2-N points real sequences FFT by an N-points FFT. Suppose x(n) is a 2N points

9、 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,？,Based on symmetric property:,15,Similar with DIT-FFT,2N points DFT first half:,2N points DFT last half:,16,3.6 Linear convolution by FFT,Too large to compute,1. Object

10、ive （1）Background Filter 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-sav

11、e method,17,2 Overlap-add method,（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).,18,2 Overlap-add metho

12、d,Because: yi(n)s length N， xi(n) 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 F

13、FT: yi(n)= xi(n) h(n),19,（2）Computing 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:：,20,2 Overlap-save method,Basic ide

14、a of overlap-save method is to compute N 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.,21,2 Overlap-save method,Zero padding,From the figure: yi(n)s last N2 points is accurate value of linear convolution.,Key 1:Decompose x(n) into a series of overlap parts.,Delete,Key 2: Save x(n)s last N2 points.,Overlap-save method,Delete,Delete,22,（2）Computation process,(a) Decompose x(n) :,(b) Compute yi(n)=xi(n) h(n) by FFT,(c) Delete the first N1-1 points value of yi(n),