文档介绍：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 x[n]. Alternatively, we can consider dividing output sequence X[k] into smaller and smaller subsequences in the same manner. FFT based on this procedure are called decimation-in-frequency algorithms.
1
精品ppt
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:
into even-numbered frequency samples (k=2r)
and the odd-number frequency samples (k=2r+1)
Separate
2
精品ppt
First half and last half
3
精品ppt
DIT-FFT Basic structure
Difference?
Decompose in 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
4
精品ppt
DFT N/2
x2(n)
DFT N/2
x1(n)
8-point DIF-FFT
Proceed separating N/2 points DFT, until get the whole flow graph of DIF-FFT
5
精品ppt
m=0
m=1
m=2
8-point DIF-FFT
6
精品ppt
2. Butterfly computation
“butterfly” element
-
Add first
Multiply second
Difference with DIT-FFT
Basic computation:
m is the level’s index, the most left level’s m=0;
p,q is the sequence number of upper nodes and lower nodes.
Determination of S in : S=2mp
Distance between two node pair:
7
精品ppt
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.
8
精品ppt
9
精品ppt
Inverse FFT
1. Comparison 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?
10
精品ppt