16点的FFT算法VERILOG程序实现
问题的提出 解决问题的思路与方法
基2时间抽取FFT算法基2时间抽取FFT算法的计算复杂度
基2时间抽取FFT算法流图规律基2频率抽取FFT算法
FFT算法的实际应用
问题的提出4点序列{2,3,3,2} DFT的计算复杂度
X [m] k 0
N 1
km x[k ]WN ,
m 0,1, N 1
0 0 0 0 X [0] 2WN 3WN 3WN 2WN 10 0 1 2 3 X [1] 2WN 3WN 3WN 2WN 1 j 0 2 4 6 X [2] 2WN 3WN 3WN 2WN 0 0 3 6 9 X [3] 2WN 3WN 3WN 2WN 1 j
如 何 提 高 DFT 的 运 算 效 率
复数加法 N(N-1)
复数乘法 N 2
?
解决问题的思路1. 将长序列DFT分解为短序列的DFTkm 2. 利用旋转因子 WN 的周期性、对称性、可约性。
旋转因子1)周期性
的性质
km WN
(k N )m k ( m N ) km WN WN WN
2) 对称性WNmk N 2
mk W N
km WN
mk WN
3)可约性mk WN
mk nmk WN WnN
mk / n WN / n ,
N / n为整数
解决问题的方法
将时域序列逐次分解为一组子序列,利用旋转因子 的特性,由子序列的DFT来实现整个序列的DFT。
基2时间抽取(Decimation in time)FFT算法 x[2r ] N x[k ] r 0,1, 1 2 x[2r 1]
基2频率抽取(Decimation in frequency)FFT算法 X [2m] X [m] X [2m 1]
基2时间抽取FFT算法流图
N=2
x[k]={x[0], x[1]}
X [0] x[0] W20 x[1]1 X [1] x[0] W2 x[1] x[0] W20 x[1]
x[0] x[1] W20 -1
X [0] X [1]
X [m] X1[m] W4m X 2 [m], m 0,1m 4点基 2 算法流图 X [时间抽取 m 2] XFFT [ m ] W 1 4 X 2 [m], m 0,1
x[0] x[2] x[1] x[3]0 W2
X1[0]
X [0]
W20
2点DFT 1
X1[1]X2[0]
X [1]
W40 1
X [2] X [3]
2点DFT 1
X2[1]
W41 1
4点基2时间抽取FFT算法流图
x[0] x[2] x[1] x[3]W40 W40
X1[0] X1[1] X2[0] X2[1]W40 W41
X[0] X[1] X[2]
1
1 1
1
X[3]
X [m] X1[m] W8m X 2 [m], m 0,1,2,3 8点基2时间抽取FFT算法流图 X [m 4] X1[m] W8m X 2 [m], m 0,1,2,3x[0]X1[0] X1[1]
X [0] X [1] X [2] X [3] 1 1 1 1
x[2]x[4] x[6] x[1] x[3] x[5] x[7]
4点DFT
X1[2] X1[3]
X2[0] W801 W X2[1] 8
X [4] X [5]
4点DFT
X2[2] W82
X [6]X [7]
X2[3] W83
8点基2时间抽取FFT算法流图x x[0] [0][0] XX [0] 1111
X1[0] X1[1]2 1 1
x[2] [4]x[4] [2] x
W80 W80 W80 W80
2点DFT
X [0] X [1] X [2] X [3] 1 1 1 1
12点DFT
[1] XX [1] 11110 0 4 点 DFT W W [0] 8 4 XX [0] 1212
X1[2] X1[3]
x[6] [6]x[1] [1] xx x[3] [5] x x[5] [3]
12点DFT
W W [1] XX [1] 8 4 1212[0] XX [0] 21 21 [1] XX [1] 21 21
1
X2[0] W801 W X2[1] 8
X [4] X [5]
1
4点DFT
0 0 W [0] W XX [0] 8 4 22 22
x[7] [7] x
2点DFT XX [1] W W 22[1] 8 4 22 1 1
2 1 1
X2[2] W82
X [6]X [7]
X2[3] W83
基2时间抽取FFT算法第一级x[0] x[4] x[2]
x[6] x[1] x[5] x[3] x[7]W80 W80 W80 W80
第二级
第三级X[0]
1
X[1]W80 W82
1 1W80 W81
X[2] X[3] 1 1 1 1 X[0] X[1] X[2] X[3]
1
1
W80 W82
1 1
W82 W83
1
算法的计算复杂度
复乘次数复乘次数
N log 2 N 2
N2
N log2 N 2
N
基2时间抽取FFT算法流图第一级x[0] x[4] x[2] x[6] x[1] x[5] x[3] x[7]W80 W80 W80 W80
第二级
第三级X[0]
1
X[1]W80 W82
1 1W80 W81
X[2] X[3] 1 1 1 1 X[0] X[1] X[2] X[3]
1
1
W80 W82
1 1
W82 W83
1
FFT算法流图旋转因子
P W 规律 N
0 W 第一级的蝶形系数均为 N ,蝶形节点的距离为1。
0 N/4 第二级的蝶形系数为 WN ,蝶形节点的距离为2。 , WN
0 N /8 2N / 8 3N / 8 第三级的蝶形系数为 WN ,蝶形 , WN , WN , WN 节点的距离为4。
( N / 2 1) 0 1 , WN , , WN 第M级 的蝶形系数为 WN ,蝶形 节点的距离为N /2。
k0
k10
k20 1 x[000] x[100] x[010]
倒序
0
x[k2 k10]1
0 1
x[110]x[001]
x[k2 k1k0] 0
0 1 1 x[k2 k11] 1 1 0
x[101]x[011]
x[111]
基2频率抽取FFT算法X [m ] N / 2 1
k 0
x[k ]W
mk N
N 1 k N / 2 N / 2 1
x[k ]W
mk N
N / 2 1 k 0 N / 2 1
mk x[k ]WN
k 0
m( k N / 2) x[k N / 2]WN
x[k ] ( 1)k 0 N / 2 1 k 0 N / 2 1 k 0
m
mk x[k N / 2] WN
X [2r ]
rk x [ k ] x [ k N / 2 ] W N /2 k rk x [ k ] x [ k N / 2 ] W W N N /2
X [2r 1]
X [2r ]
N / 2 1 k 0
rk x [ k ] x [ k N / 2 ] W N /2 N / 2 1 k 0
r 0,1 N / 2 1
X [2r 1] x[0]
k rk x [ k ] x [ k N / 2 ] W W N N /2
X[0]
x[1] x[2]x[3] x[4]0 WN
4点 DFT
X[2]
X[4]X[6]
-1 -1 -1 -1
X[1]
x[5] x[6]x[7]
W
1 N
2 WN
4点 DFT
X[3] X[5] X[7]
W
3 N
x[0] x[1] x[2] x[3] x[4]-10 WN0 WN
2点DFT-1
X[0]
X[4]X[2] X[6] X[1] X[5] X[3]
W-1
2 N
2点 DFT 2点 DFT
x[5]x[6] x[7]
-1-1
W W
1 N 2 N 3 N0 WN
-1
W
-1 -1
W
2 N
2点 DFT
X[7]
x[0] x[1] x[2]-1 -1 -1 -1 -1 -10 WN0 WN 2 WN
X[0]
W-1
0 N
X[4] X[2]
x[3]x[4] x[5] x[6] x[7]
-1
0 WN
X[6]X[1]
W W
1 N0 WN
2 WN3 N
-1
0 WN
X[5] X[3]
-1-1
W
2 N
-1
0 WN
X[7]
FFT算法应用
利用N点复序列的FFT计算两个N点实序列FFT 利用N点复序列的FFT,计算2N点序列的FFT 利用FFT计算IFFT
利用N点复序列的FFT算法计算
两个N点实序列FFTx1[k], x2[k]是实序列, 将其构成复序列y[k]=x1[k]+j x2[k] DFT{x1[k]+j x2[k]}=YR [m]+jYI [m]DFT x1[k ] jx2 [k ] YR [( m) N ] jYI [( m) N ]1 DFT x1[k ] YR [m] YR [( m) N ] j (YI [m] YI [( m) N ]) 2
DFT x1[k ] ? DFT x2 [k ] ?
1 YR [m] YR [( m) N ] j (YI [m] YI [( m) N ]) DFT x2 [k ] 2j