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