旋转因子的周期性，对称性和可约性。利用这两个途径实现DFT的快速傅里叶变换(FFT)，FFT算法基本上可分为按时间抽取的FFT算法(DIT-FFT)和按频率抽取的FFT算法(DIF-FFT)。
旋转因子的性质：
kn(k N)nk(n N)WN WN WN(1) 周期性 (2) 共轭对称性 (3) 可约性
kn( k)n*k( n)*WN [WN] [WN]mknWNkn WmN,
/m
WNkn WNkn/m
本次课设要求用基2的按时间抽取的FFT算法(DIT-FFT)实现FFT功能，设序列x(n)的长度为N，且N满足N=2M，M为正整数。若N不能满足上述关系，可以将序列x(n)补零实现。按时间抽取基2-FFT算法的基本思路是将N点序列按时间下标的奇偶分为两个N/2点序列，计算这两个N/2点序列的N/2点DFT，计算量可减小约一半；每一个N/2点序列按照同样的划分原则，可以划分为两个N/4点序列，最后，将原序列划分为多个2点序列，将计算量大大降低。
按时间下标的奇偶将N点x(n)分别抽取组成两个N/2点序列，分别记为x1(n)和x2(n)，将x(n)的DFT转化为x1(n)和x2(n)的DFT的计算。
2rk
WN e
2
j2rk
N
j
x(2r) x1(r)
,
x(2r 1) x2(r)
nk
X k x n WN
n 0N 2N 1
r 0,1, ,
N 12
n 0,2,4...N 12
x n W
nkN
n 1,3,5...N 12
x n W
N 1
nkN
r 0,1N 12
x 2r W x r W
1
2rkN
r 0,1N 12
x 2r 1 W
2
2r 1 kN
2rkN
r 0,1r 0,1
x r W
2r 1 kN
利用旋转因子的可约性，即：
2
rk2
e
rk
WN
rkk
X k x1 r WN WN x2 r WNrk
r 0
r 0
k X（ WNX（k）,0 k N 11k）2
N
12N 12
用蝶形运算可表示为如图3-2所示：