第四章 模拟调制系统.ppt

文档介绍：第四章快速傅里叶变换
引言
直接计算DFT的问题及改进的途径
按时间抽选(DIT)的基-2 FFT算法
按频率抽选(DIF)的基-2 FFT算法
离散傅里叶反变换(IDFT) 的快速计算方法
线性卷积与线性相关的FFT算法
数字信号处理的实现
第四章快速傅里叶变换
引言
0
n
XN(k)
0
k
xN(n)
N-1
~
N-1
~
0
n
XN(k)
0
k
xN(n)
N-1
N-1
DFT
DFS
0
n
X(ej)*D(ej)
0

x(n)d(n)
DTFT
0
n
|X(ej)|
0

x(n)
DTFT
0
t
|Xa(j)|
0

xa(t)
FT
T
0
2
2
第四章快速傅里叶变换
直接计算DFT的问题及改进的途径
运算量:对某一k值,复乘N次,复加N-1次;
对DFT,复乘N2次,复加N(N-1)次(近似为N2);
例:N=1024,则N2=106,难以实现实时处理;
DFT:
改进途径:将较长的DFT分解为几个较短的DFT,并利用旋转因子WN的周期性、对称性和可约性(伸缩性)等特性减少运算次数。
1. 周期性:
2. 对称性:
3. 可约性:
设序列x(n)的长度为N,且满足
令
令
令
即N点DFT分解为两个N/2点DFT后按上述两公式合成,这种分解可用蝶形符号表示。
1. 周期性:
2. 对称性:
3. 可约性:
N
/2
点
DFT
W
N
0
N
/2
点
DFT
W
N
1
W
N
2
W
N
3
x
(0)
X
1
(0)
x
(2)
x
(4)
x
(6)
x
(1)
x
(3)
x
(5)
x
(7)
X
1
(1)
X
1
(2)
X
1
(3)
X
2
(0)
X
2
(1)
X
2
(2)
X
2
(3)
X
(0)
X
(1)
X
(2)
X
(3)
X
(4)
X
(5)
X
(6)
X
(7)
一次抽选分解后运算量:
复乘:2(N/2)2+N/2=N(N+1)/2N2/2
复加:2(N/2)(N/2-1)+2(N/2) =N2/2
分解前,复乘N2次,复加N(N-1)次(近似为N2);
C
A
B
A
+
BC
A
-
BC
蝶形运算
复乘1次,复加2次
N
/2
点
DFT
W
N
0
N
/2
点
DFT
W
N
1
W
N
2
W
N
3
x
(0)
X
1
(0)
x
(2)
x
(4)
x
(6)
x
(1)
x
(3)
x
(5)
x
(7)
X
1
(1)
X
1
(2)
X
1
(3)
X
2
(0)
X
2
(1)
X
2
(2)
X
2
(3)
X
(0)
X
(1)
X
(2)
X
(3)
X
(4)
X
(5)
X
(6)
X
(7)
C
A
B
A
+
BC
A
-
BC
C
A
B
A
+
BC
A
-
BC
对任意N=2L,按同样方法,都可分解为N/2个2点DFT
对任意N=2L,按同样方法,都可分解为N/2个2点DFT
对2点DFT:
对2点DFT: