第三章离散傅立叶变换及其快速算法数字信号处理 第 3章? 2004
3.1周期序列的离散傅立叶级数
3.1.1周期序列的傅立叶级数（ DFS）
对于周期为 N的周期序列 可用 基序列 { } 来展开 。
的基频为基波为第 k次谐波为
)(~ nx
nkNje?2
)(~ nx N
2
0?
nNjnj eene 2
1 0)(
nkNjnkj
k eene
2
0)(
数字信号处理 第 3章? 2004
由
)()(
2)(2
neeene k
nk
N
jrNkn
N
j
rNk
说明 是以 N为周期的周期序列，所以基序列 { }（ k=0,…,N -1) 只有 n个是独立的，可以用这 n个基序列将 展开
nkNje?2
nkNje?2
)(~ nx
数字信号处理 第 3章? 2004
通常记具有以下性质：
1.周期性
2.共轭对称性
3.可约性
4.正交性
Nj
N eW
2?
NW
)( rNnNnN WW
*)( nNnN WW
nNrnrN WW?
0
11)(1 1
0
)(
1
0
*
N
n
nkm
N
N
n
mn
N
kn
N WNWWN km
km
数字信号处理 第 3章? 2004
离散傅立叶级数的表示：
正变换：
反变换：
1
0
1
0
2
)(~)(~
)(~)(
~
N
n
nk
N
N
n
nk
N
j
Wnxenx
nxD F SkX
1
0
1
0
2
)(
~1
)(
~1
)(
~
)(
~
N
k
nk
N
N
k
nk
N
j
WkX
N
ekX
N
kXI D F Snx
数字信号处理 第 3章? 2004
3.1.2离散傅立叶级数（ DFS）的性质
1.线性性如果则对任何实数或复数,有
)(~)(~
)(~)(~
22
11
nxD FSkX
nxD FSkX
1a 2a
)(
~
)(
~
)(~)(~
2211
2211
kXakXa
nxanxaD FS
数字信号处理 第 3章? 2004
2.序列周期的移位性质如果则
)(~)(~ kXnxD F S?
)(
~
)(
~
)(
~
2
kXe
kXWmnxD F S
mk
N
j
mk
N
数字信号处理 第 3章? 2004
证明：
1
0
)(~)](~[
N
n
nk
NWmnxmnxD F S
mk
N
mN
mi
ik
N WWix
1
)(~
)(~)(~
1
0
kxWWixW mkN
N
i
ik
N
mk
N
数字信号处理 第 3章? 2004
3.频域移位（调制）特性如果则
)(~)(~ kXnxD F S?
)(~)(~ lkXnxWD F S nlN
数字信号处理 第 3章? 2004
4.周期卷积定理设 和 具有相同的周期 N
则周期卷积
)(~1 nx )(~2 nx
记为
1
0
21 )(
~)(~)(~ N
m
mnxmxny
)(~)(~ 21 nxnx)(~ ny
数字信号处理 第 3章? 2004图 3-1-1两个序列的周期卷积数字信号处理 第 3章? 2004
说明：
上图是周期为 N=6的两个序列卷积的计算过程。类似于线性卷积，首先进行变量代换为,再将其中一个序列进行反褶，移位，相乘，然后加。
运算仅在 m=0到 m=N-1内进行，计算出一个周期的结果，再进行周期延拓得到整个序列
)(~)(~ 21 nxnx 和
)(~)(~ 21 mxmx 和
)(~ ny
数字信号处理 第 3章? 2004
周期卷积有下述定理，若证明：
代入
)(~ kY )](~[ nyD FS )(~)(~ 21 kXkX?
1
0
1
)](
~
[)(~
N
kN
kYI D F Sny
)(~)(~ 21 kXkX nk
NW
1
0
1 )(
~ N
m
kX )(~
1 mx
mk
NW
数字信号处理 第 3章? 2004
得
1
0
1
0
1)(~ N
k
N
mN
ny )(~1 mx mkNW )(~ 2 kX nkNW?
1
0
N
m
1
0
1 N
kN
kmnNW )()(~ 2 kX)(~1 mx
由移位定理得
1
0
21 )(
~)(~)(~ N
m
mnxmxny
数字信号处理 第 3章? 2004
同理可证明 频域周期卷积定理若则
)(~)(~)(~ 21 nxnxny?
1
0
21 )(
~
)(
~1
)(~)(
~
N
l
lkXlX
N
nyD F SkY
数字信号处理 第 3章? 2004
3.1.3周期序列的傅立叶变换周期为 N的周期序列 的傅立叶变换可表示为脉冲串的形式证明：
)(~ nx
)(~?jeX
k N
2
)(~ kX )2( Nk
[1?F?)(~?jeX
2
1 )(~?jeX
de j
)(~)(
~1
)
2
()(
~1
1
0
2
1
0
2
0
nxekX
N
de
N
k
kX
N
N
n
N
nk
j
N
n
nj
数字信号处理 第 3章? 2004
3.2离散傅立叶变换
3.2.1有限长序列的离散傅立叶变换一,DFT的定义长度为 N的序列 x(n)其频谱为在 上从 0开始等间隔的取 N个点，相应的 （ k=0,…,N -1),则上式变为
1
0
)()(
N
n
njj enxeX
)2,0[?
N
k
k
2?
数字信号处理 第 3章? 2004
1
0
2
)()(
N
n
kn
N
jj
enxeX k
（ k=0,…,N -1)
)()( kjeXkX令 并采用记号 N
j
N e
2?
可得有限长序列 {x(n)}(n=0,1,2,…,N -1)的离散正反傅立叶变换数字信号处理 第 3章? 2004
离散傅立叶变换,简称 DFT
傅立叶反变换,简称 IDFT
1
0
)()()(
N
n
nk
NWnxnxD F TkX （ k=0,…,N -1)
1
0
)(1)()(
N
k
nk
NWkXNkXI D F Tnx （ k=0,…,N -1)
数字信号处理 第 3章? 2004
二,周期性以及与 DFS的关系
1.余数运算表达式如果,
m为整数；则有：
mNnn 1 10 1 Nn
1nn N?
数字信号处理 第 3章? 2004
此运算符表示 n被 N除，商为 m，余数为 。
是 的解,或称作取余数,或说作 n对
N取模值,或简称为取模值,n模 N。
1n
)( 1nNn
例如：
N=8
N=16
)1())9(( 8 xx? )5())5(( 8 xx?
)9())9(( 16 xx? )12())4(( 16 xx
数字信号处理 第 3章? 2004
2.有限长序列 x(n)和周期序列 的关系有限长序列 x(n)是周期序列 的主值序列
)(~ nx
~ ( ) (( )) ( )x n x n x n rN
N
r
x n x n R nN N( ) (( )) ( )?
)(~ nx
数字信号处理 第 3章? 2004
3.周期序列 与有限长序列 的关系同样，周期序列 是有限长序列的周期延拓而有限长序列 是周期序列的主值序列。
)(~ kX )(kX
~ ( ) (( )) ( )X k X k X k rN
N
r
X k X k R kN N( ) (( )) ( )?
)(~ kX
)(~ kX
)(kX
)(kX
数字信号处理 第 3章? 2004
三,DFT与 Z变换的关系长度为 N的序列 x(n)其 Z变换,
与傅立叶变换相比较有,
X z x n z n
n
N
( ) ( )
0
1
10)()()( 22 NkzXeXkX kNjezk
N
j
数字信号处理 第 3章? 2004
可见序列的 N点 DFT是 x(n)的 Z变换在单位圆上 N点的等间隔采样。显然，对于同一序列当频率采样点数不同时，其 DFT的值也不同。
数字信号处理 第 3章? 2004
3.2.2 DFT的一些性质一,线性性若 x(n)与 y(n)是同样长的序列，则对任何实数或复数有a a1 2,
)]([)]([
)]()([
21
21
nyD F TanxD F Ta
nyanxaD F T
数字信号处理 第 3章? 2004
二,循环移位性质如果那么
)]([)( nxD F TkX?
Y k D F T y n W X kN mk( ) [ ( )] ( )
)())(()( nRmnxny NN
数字信号处理 第 3章? 2004图 3-2-1循环移位示意图数字信号处理 第 3章? 2004
证明：
令 n+m=nl,则有
Y k x n m R n WN N Nkn
n
N
( ) (( )) ( )
0
1
x n m WN Nkn
n
N
(( ))
0
1
mN
mn
mnk
NN WnxkY
1
1
)1())1(()(
mN
mn
kn
NN
km
N WnxW
1
1
1))1((
1
01
1))1((
N
n
kn
NN
mk
N WnxWW X kN mK ( )
数字信号处理 第 3章? 2004
同理可证明 频域移位定理：
若则
=
X k D F T x n( ) [ ( )]?
)())(()( kRlkXkY NN
y n I D F T Y k( ) [ ( )]? W x n
N
nl ( )
数字信号处理 第 3章? 2004
三,共轭复序列的 DFT
设 为 的共轭复序列，则证明：
)(nx? )(nx
D F T x n X N k R kN N[ ( )] (( )) ( )
)()(
)()()]([
1
0
1
0
kRWnx
kRWnxnxD F T
N
nk
N
N
n
N
nk
N
N
n
)()()()( )(1
0
kRkNXkRWnx NNnkNN
N
n
数字信号处理 第 3章? 2004
四,共轭对称性
)()()( njxnxnx ir
)]()([
2
1
)( * nxnxnx r
)]()([21)( * nxnxnjx i
用 和 分别表示实部与虚部序列的 DFT:
)(kXo
)(kXe )(kXo
)]}()([
2
1{)]([)( * nxnxD F TnxD F TkX
re
)]()([21 * kNXkX
数字信号处理 第 3章? 2004
共轭对称性：
共轭反对称性：
)]}()([21{)]([)( * nxnxD F TnjxD F TkX io
)]()([21 * kNXkX
)()( kNXkX ee
)()( kNXkX oo
数字信号处理 第 3章? 2004
由于 x(n)和 均是有限长序列,其定义区间为 （ 0～ N-1）,注意,
与在第二章中的对称性不同,这里所谓的对称性是指关于 N/2点的对称性,而不是关于原点的对称,见右图 。
图 3-2-2 关于 N/2点的共轭对称性
)(kX
数字信号处理 第 3章? 2004
若 x(n)为实序列，则其 DFT满足共轭对称特性若 x(n)为纯虚序列，则其 DFT满足共轭反对称性例：已知 f(n)=x(n)+jy(n),x(n)和 y(n)为实序列,F(k)=1+jN,求 x(n),y(n)
)()( * kNXkX
)()( * kNXkX
数字信号处理 第 3章? 2004
解：
)()]([)(
)(
1
)(
1
)]([)(
)()(]))(()([
2
1
)]([
)()(]))(()([
2
1
)]([
1
0
1
0
*
*
nNkYI D F Tny
nW
N
WkX
N
kXI D F Tnx
kj N RkRkNFkFnjyD F T
kRkRkNFkFnxD F T
N
k
kn
N
N
k
kN
N
NNN
NNN
数字信号处理 第 3章? 2004
五,循环卷积定理设 和 是两个具有相同长度 N的有限长序列，定义循环卷积：
n=0,…,N -1
记为同时满足交换率
)(1 nx )(2 nx
y n x m x n m R nN N
m
N
( ) ( ) (( )) ( )
1 2
0
1
y n x n x n( ) ( ) ( )1 2
)()()( 12 nxnxny
1
0
12 )())(()(
N
m
NN nRmnxmx
数字信号处理 第 3章? 2004
循环卷积的直接计算与前面讨论的周期卷积类似,步骤为反褶 循环移位 乘积 累加例 3-2-2：已知做 N=8的循环卷积 y(n)
解：先进行变量代换,将 变成
,接着将 周期延拓为 反褶后得到,从 n=0开始,对每一个 n=0,…,N-1,对进行循环移位并取主值形成再分别将 与 对应的 m点从
m=0到 m=N-1逐点相乘,并将乘积累加就得到了各个点的 y(n).计算过程图 3-2-3如下：
)2()(),()( 4241 nRnxnRnx
)(),( 21 nxnx )(),( 21 mxmx
)(2 mx Nmx ))((2
Nmx ))((2?
Nmx ))((2?
)())((2 mRmnx NN?
)(1 mx )())((2 mRmnx NN?
数字信号处理 第 3章? 2004
数字信号处理 第 3章? 2004
循环卷积定理；
若,
则
)]([)( 11 nxD F TkX? )]([)( 22 nxD F TkX?
nk
NN
N
n
N
m
nk
NNN
N
n
N
m
Wmnxmx
WnRmnxmx
nyD F TkY
))(()(
)]())(()([
)]([)(
2
1
0
1
1
0
21
1
0
1
0
)()()()( 2121
1
0
kXkXKXWmx mkN
N
m
Y k D F T y n X k X k( ) [ ( )] ( ) ( ) 1 2
数字信号处理 第 3章? 2004
同理可以证明 频域卷积定理：
若则
y n x n x n( ) ( ) ( )? 1 2
)()(1)]([)( 21 kXkX
N
nyD F TkY
1
0
21 )())(()(
1 N
l
NN kRlkXlXN
数字信号处理 第 3章? 2004
六,循环相关定理
n=0,…N -1
称为序列
)()( nynx 和设两个有限长实序列 具有相同的长度 N
1
0
)())(()()(~
N
m
NNxy nRmnymxnr
的 循环互相关)()( nynx 和数字信号处理 第 3章? 2004
循环相关定理：
若,
则有
)]([)( nxD F TkX? )]([)( nyD FTky?
)()(*)]([)( kYkXnrD FTkR xyxy
数字信号处理 第 3章? 2004
当 x(n)=y(n)时,称 为序列的 循环自相关)(~ nrxx
)(kRxx 2|)(|)()(* kXkXkX
2|)(| kX 是有限长序列的离散功率谱，注意
2|)(| kX 中没有相位的信息。
数字信号处理 第 3章? 2004
七,帕思瓦定理 (Parseval)
帕思瓦定理的离散傅立叶变换形式
1
0
)(*)(
N
n
nynx )(*)(1 1
0
kYkXN
N
k
数字信号处理 第 3章? 2004
证明：
=
=
=
=
1
0
)(*)(
N
n
nynx )(*)(1
1
0
1
0
nyWkXN nkN
N
k
N
n
)(*)(1
1
0
1
0
nyWkXN nkN
N
n
N
k
*)()(1 1
0
1
0
nyWkXN nkN
N
n
N
k
)(*)(1
1
0
kYkXN
N
k
数字信号处理 第 3章? 2004
当 x(n)=y(n)时，则有：
说明时域中的能量与频域中的能量相等
1
0
2|)(|
N
n
nx 2
1
0
|)(|1 kXN
N
k
数字信号处理 第 3章? 2004
3,2,3 离散频率与数字频率和模拟频率之间的关系
模拟频率,f 和 W,单位为赫兹 （ Hz） 和 弧度 /秒
（ rad/s） 。 关系为,W?2?f,
离散信号数字频率,?,单位为弧度 （ rad） 。 并通过采样信号的频谱,建立了模拟频率与数字频率之间的关系：
取值范围 对应于模拟频率的
离散的数字频率,用 k表示 。,因此可得出离散频率 k与数字频率和模拟频率之间的对应关系为：
sf
fT 2?W?
10 Nk
kNffkNk s 2
20 或
2/sf
数字信号处理 第 3章? 2004
3.3频域采样定理频域采样是指对有限长序列的傅氏变换在频域离散化得到 x(k)的过程。
本节讨论两个基本问题：
a：频域采样（ DFT）不失真的条件，即由
X (k)不失真地恢复 x(n)的条件
b：用 X (k)表示 X (z)和 的插值公式
(内插公式 )
X e j( )?
X e j( )?
数字信号处理 第 3章? 2004
1.频域采样 X（ k）不失真恢复 x(n)的条件：采样点数 N必须大于序列的长度 L
假定 x(n)的长度为 L（没有限制）
频率采样
=,0≤k≤N -1
令 =IDFT[X(k)]（ 0≤n≤N -1）,由于
=DFS[ ] =
= =IDFS[ ] =
n
nznxzX )()(
kNWzzXkX )()(
n
nk
NWnx )(
)(nxN
NkXkX ))(()(~? )(~ nx )(kX )(
~ kX )(kR
N
~( )x n NN nx ))(( )(~ kX )(nxN )(~ nx )(nR
N
数字信号处理 第 3章? 2004
因而有取主值区
= =====
=
= =
故有
=
由上式可知,是原序列 的周期延拓周期为 N，然后取主值，如图 3-3-1所示。
)(~ nx 1
0
1
N X k W N
nk
k
N ~
( )?
1
0
)(1
N
k
nk
NWkXN
1
0
)(1
N
k
nk
N
m
mk
N WWmxN
m
N
k
knm
NWmxN
1
0
)()(1 x n rN
r
( )?
)(nxN?
r
N nRrNnx )()(
)(nxN )(nx
数字信号处理 第 3章? 2004图 3-3-1 时域恢复示意图结论：若序列长度为 L，频域采样点数（或 DFT
的长度）为 N，且 L<N，则频域采样后可不失真地恢复原序列 ；但若 L>N，则频域采样后不能不失真地恢复原序列 。
)(nx
)(nx
数字信号处理 第 3章? 2004
2.用 表示 和 的内插公式
（ 1）用 表示设序列长度为 N，由傅里叶变换对得
= =
)(kX )(zX X e j( )?
)(kX )(zX
)(kX?
1
0
)(
N
n
nk
NWnx )(nx?
1
0
)(1
N
k
nk
NWkXN
数字信号处理 第 3章? 2004
= =
=
=
= =
)(zX
1
0
)(
N
n
nznx n
N
k
nk
N
N
n
zWkXN?
1
0
1
0
)(1
n
N
k
nk
N
N
n
zWkXN?
1
0
1
0
)(1
1
0
11
1)(1 N
k
k
N
NNk
N
zW
zWkX
N
1
0
11
)(1 N
k
k
N
N
zW
kX
N
z
1
0
)()(
N
k
k zkX?
其中
11
11)(
zW
z
Nz kN
N
k?
数字信号处理 第 3章? 2004
（ 2）用 表示 的内插公式将 分别代入式（ 3-3-6）和（ 3-3-7），
即可得到用 表示 的内插公式如下
= =
)(kX X e j( )?
jez?
)(kX X e j( )?
)(?jeX?jezzX?)(?
1
0
)()(
N
k
j
k ekX
)
2
(
1
11
)(
N
kj
Nj
j
k
e
e
N
e
]
22
[
]2/)
2
s i n [ (
)
2
s i n (1
N
kN
j
e
N
k
N
N
)2( Nk
数字信号处理 第 3章? 2004
其中与下面的时域采样中的内插函数相似图形 3-3-2如下：
2
2
s i n)s i n (
)(
t
t
T
t
T
t
tg
s
s
W
W
2
)1(
]2/)s in [ (
)
2
s in (1?
Nj
e
N
N
( )
数字信号处理 第 3章? 2004
图 3-2-2内插函数 零极点与 的幅频特性图)(z
k? )(
数字信号处理 第 3章? 2004
例：已知 =,0< <1,对 的 z变换 在单位圆上等间隔采样 N点,k=0,…,N-1，求
IDFT[ ]。
解：
na
)(nuan)(nx )(nx
|)()( zXkX? KNwz
)(kX
)(
1
)(
)()()(
)()()]([)(
0
0
nR
a
a
nRaa
nRanRrNnua
nRrNnxkXI D F Tnx
NN
n
r
N
rNn
r
N
rNn
r
N
rNn
r
NN
a )(zX
)0,1)(,0,10( rrNnurNnNn
数字信号处理 第 3章? 2004
3.4 DFT的快速算法 —— FFT
DFT的运算量：
减少运算量的方法：
1）将长度 N变短，例如若长度为 N/2，则运算量变成了：
2）利用 的性质：周期性共轭对称性 可约性
22
1
0
1
)1~1()()()(
NNNN
NkWnxnxD F TkX
N
n
nk
N
）（复加：，复乘：
4/4/ 22 NN?复加：，复乘：
nkNW )( rNnNnN WW
*)( nNnN WW nNrnrN WW?
数字信号处理 第 3章? 2004
FFT算法分类
基 -2 FFT算法：
所谓基 -2是指要求长度 N满足 （ M为整数），若不满足可将序列补零延长，使其满足。
混合基算法等
时域抽取与频域抽取：
MN 2?
），简称（
算法按频域抽取
），简称（
算法按时域抽取
FFT-D I FFr e q e n c y-In-D e c i m a t i on
FFT-D I FT i m e -In - D e c i m a t i on
FFT
F F T
数字信号处理 第 3章? 2004
3.4.1 时域抽取基 -2FFT算法（ DIT-FFT）
1.算法的推导按 n的奇偶把时间序列 x(n)分解为两个长为 N/2
点的序列，即因此
)2()(1 rxrx?
)12()(2 rxrx
12,...,1,0 Nr
12,...,1,0 Nr
kn
N
N
n
WnxkX )()(
1
0
k
N
kr
N
N
r
kr
N
N
r
rk
N
N
r
kr
N
N
r
WWrxWrx
WrxWrx
2
2
12/
0
2
1
12/
0
)12(
12/
0
2
12/
0
)()(
)12()2(
数字信号处理 第 3章? 2004
由于所以即其中 分别为 的 N/2点
DFT
这是 前 N/2点 DFT
X k x r W W x r W
X k W X k k N
r
N
N
kr
N
k
r
N
N
kr
N
k
( ) ( ) ( )
( ) ( ),,.,,,/
/
/
/
/
0
2 1
1 2
0
2 1
2 2
1 2 0 1 2 1
X k X k1 2( ) ( )和 x n x n1 2( ) ( )和
W e e WN kr j N Kr j N kr Nkr2 2 2 2 2 2/ /
kn
N
N
n
WnxkX 2/112/
0
1 )()(?
1
2,.,.,1,0
Nk
kn
N
N
n
WnxkX 2/212/
02
)()(
12,.,.,1,0 Nk
)12,...1,0)(( NkkX
数字信号处理 第 3章? 2004
图 3-4-1 蝶式运算图对于 后 N/2的 DFT,
由于 （周期性）
因此可用蝶式运算图来表示上述前 N/2和后 N/2两式,如图 3-4-1 所示
)(kX
kNNkN WW 2/
X k N X k W X kNk( ) ( ) ( )2 1 212,.,.,1,0 Nk
数字信号处理 第 3章? 2004
例如,N=8时的 DFT,可以分解为两个 N/2=4点 DFT
如图 3-4-2所示,
数字信号处理 第 3章? 2004
由于,因而 N/2仍是偶数,可以进一步把每个
N/2点的序列再按其奇偶部分分解为两个 N/4的子序列从而 可表示为
MN 2?
)12()(
)2()(
14
13
lxlx
lxlx )1
4(,.......,1,0
Nl
)(1 kX
)12(
2/1
14/
0
2
2/1
14/
0
1 )12()2()(
lkN
N
l
kl
N
N
l
WlxWlxkX
kl
N
N
l
k
N
kl
N
N
l
WlxWWlx 4/4
14/
0
2/4/3
14/
0
)()(
)()( 42/3 kXWkX kN 14,........1,0 N
数字信号处理 第 3章? 2004
因而有其中对 也可进行同样的分解：
k=0,1,...,N/4-1
)()()
4
( 42/31 kXWkX
N
kX kN
X k D F T x l x l W
X k D F T x l x l W
l
N
N
kl
l
N
N
kl
3 3
0
4 1
3 4
4 4
0
4 1
4 4
( ) ( ) ( )
( ) ( ) ( )
/
/
/
/
X k2( )
)()()( 62/52 kXWkXkX kN
)()()4( 62/52 kXWkXNkX kN
数字信号处理 第 3章? 2004
其中这样又一次的分解得到 4个 N/4点 DFT
klNN
l
WlxlxD F TkX 4/5
14/
0
55 )()()(?
klNN
l
WlxlxD F TkX 4/6
14/
0
66 )()()(?
)2()( 25 lxlx?
)14(,...,1,0)12()( 26 Nllxlx
数字信号处理 第 3章? 2004
如下图 3-4-3所示：
那么依次类推，经过 M-1次分解后，将 N点
DFT分解成 N/2个两点 DFT
数字信号处理 第 3章? 2004
下图为 N=8时的一个完整基 -2 DIT-FFT运算流图 3-4-4
2M
数字信号处理 第 3章? 2004
2.运算量当 N= 时，总共有 M级分解，每级有 N/2个蝶式运算。
每个蝶式运算需一次复乘两次复加，这样 M级总共需要的运算量为复乘次数复加次数
2M
N M N N
2 2 2 log
N M N N l o g 2
数字信号处理 第 3章? 2004
3.FFT算法的特点
（ 1）倒码码位倒置是指将原二进制数的码位倒过来按从低位到高位排列如：序号 4用 3位二进制表示正常码为 100
倒码为 001，变成了 1
顺序与倒序对照表如下：
数字信号处理 第 3章? 2004
顺序 二进制数 倒码 倒码顺序
0
1
2
3
4
5
6
7
000
001
010
011
100
101
110
111
000
100
010
110
001
101
011
000
0
4
2
6
1
5
3
7
数字信号处理 第 3章? 2004
（ 2）原位运算利用同一存储单元存放蝶式运算输入和输出数据的方法。
4.DIF-FFT算法其他形式的流图输入的数据为正序，输出是倒码排列。
如下图 3-4-7所示数字信号处理 第 3章? 2004
图 3-4-7 N=8 时输入是正常顺序的、输出是倒码排列的 DIT-FFT运算流图数字信号处理 第 3章? 2004
3.4.2 频域抽取基 -2 FFT算法 (DIF-FFT)
1.算法：
X k D F T x n x n W
x n W x n W
x n W x n N W
x n W x n N W
n
N
N
nk
n
N
N
nk
n N
N
N
nk
n
N
N
nk
n
N
N
n N k
n
N
N
Nk
N
nk
( ) ( ) ( )
( ) ( )
( ) ( / )
( ) ( / )
/
/
/ /
( / )
/
/
0
1
0
2 1
2
1
0
2 1
0
2 1
2
0
2 1
2
2
2
数字信号处理 第 3章? 2004
由于
N点 DFT按 k的奇偶分组可分为两个 N/2的 DFT
k取偶数时 （ k=2r,r=0,1,...,N/2-1）
W k
kN
kN k/ ( )2 1 1
1
为偶数为奇数
X r x n x n N W
x n x n N W
n
N
N
rn
n
N
N
rn
( ) [ ( ) ( / )]
( ) ( / )
/
/
/
2 2
2
0
2 1
2
0
2 1
2
数字信号处理 第 3章? 2004
k取奇数时（ k=2r+1,r=0,1,...,N/2-1)
2.蝶形运算和 进行如下蝶形运算
rnNnN
N
n
nr
N
N
n
WWNnxnx
WNnxnxrX
2/
12/
0
)12(
12/
0
)2/()(
)]2/()([)12(
)(nx )2/( Nnx?
数字信号处理 第 3章? 2004
如下图 3-4-8 DIF-FFT的蝶式运算流图：
x(n) x(n)+ x(n+N/2)
x(n+N/2) [x(n)- x(n+N/2)]
3.N=8 时,按 k 的奇偶分解过程先蝶形运算,后 DFT
nNW1?
nNW
数字信号处理 第 3章? 2004
如图 3-4-9 DIF-FFT的一次分解运算流图（ N=8）：
数字信号处理 第 3章? 2004
4.DIF-FFT的二次分解由于 N/2仍然为 2的整数幂，继续将 N/2点 DFT分成偶数组和奇数组，这样每个 N/2点 DFT又可分解成两个 N/4
点 DFT，其输入序列分别是按上下对半分图开后通过蝶式运算构成的 4个子序列,如图 3-4-10
数字信号处理 第 3章? 2004
按照以上方法继续分解下去，经过 M-1次分解，
最后分解为 N/2个两点 DFT，这 N/2个 2点 DFT的输出就是 N点 DFT的结果 X(k),如图 3-4-11
数字信号处理 第 3章? 2004
上图给出了 N=8时完整的 DIF-FFT的运算流图。由于这种方法是 按Ｘ（Ｋ）在频域进行奇偶分解，
因此称之为频域抽取ＦＦＴ运算．
比较ＤＩＦ－ＦＦＴ与ＤＩＴ－ＦＦＴ：
相同点：运算次数与存储量相同不同点：１,ＤＩＦ－ＦＦＴ输入序列为自然序列而输出为码位倒置序列
２,蝶式运算过程不同,
ＤＩＴ－ＦＦＴ是序列先乘旋转因子后相加减
ＤＩＦ－ＦＦＴ是序列先相加减后乘旋转因子数字信号处理 第 3章? 2004
3.4.3逆 DFT的快速算法（ IFFT）
1.比较 DFT与 IDFT的计算公式比较两式可知只要将 FFT中的旋转因子为,再乘以 1/N即可得到 IDFT的快速算法
IFFT 。
X k x n W k NN nk
n
N
( ) ( ),,.,,,,
0 1
0
1
x n N X k W n NN nk
k
N
( ) ( ),,.,,,,
1 0 1
0
1
WNnk
WN nk?
数字信号处理 第 3章? 2004
另外，可将常数 1/N分配到每级运算中，
因为,也就是每级蝶形运算均乘以 1/2
2.直接利用 FFT程序因为所以
1 1
2N
M? ( )
x n N X k W n NN nk
k
N( ) ( ),,.,,,,
1 0 1
0
1
x n N X k W Nnk
k
N
( ) ( )1
0
1
数字信号处理 第 3章? 2004
两边取共轭有：
此方法只需要一个 FFT程序即可进行正逆变换的快速计算。
x n N X k W n NN nk
k
N
( ) ( ),.,,,,
1 0 1
0
1
1N D F T X k{ [ ( )]}
数字信号处理 第 3章? 2004
FFT（ IFFT）算法的实现：
1.纯软件实现
2.硬件实现
3.DSP（软硬件结合）
数字信号处理 第 3章? 2004
3.4.4 N为合数的 FFT算法（混合基）
1.算法的实现长度 N是复合数,
共 V个因子 。
令 其中将 x(n)每隔 点抽取一点
vppppN?321
11 qpN vpppq?321
1p
组共
11
11
1
1
),1(,,1,0
)1(
)1(
)(
pqr
prpx
rpx
rpx
数字信号处理 第 3章? 2004
或记为例如：,即 =3,=6,按以上的方法将 x(n)分为 3组，每组长度为 6,如下所示：
第 0组,
第 1组,
第 2组,
)1(,,1,0),1(,,1,0)()( 111 plqrlrpxrx l
1863N 1p 1q
)(0 rx )15()12()9()6()3()0( xxxxxx
)(1 rx
)(2 rx
)16()13()10()7()4()1( xxxxxx
)17()14()11()8()5()2( xxxxxx
数字信号处理 第 3章? 2004
序列 x(n)的 N点 DFT为将 代入，则
1
0
)()(
N
n
nk
NWnxkX 1,,1,0 Nk?
lrpn 1
1
0
)1(
11
1
0
1
1
0
1
1
0
1
11
1
1
1
1 )1()1()(
)()(
q
r
rkp
N
kp
N
q
r
rkp
N
k
N
q
r
rkp
N
N
n
nk
N
WWprpxWWrpxWrpx
WnxkX
1
0
1
1
0
1
1
1
)(
q
r
rkp
N
p
l
lk
N WlrpxW
数字信号处理 第 3章? 2004
令则由于继续令如此进行下去直到最后变为 点的 DFT
1,,1,0)()( 1
1
0
1
1
1
qkkGWlrpx l
q
r
rkp
N?
1,,1,0)()( 1
1
0
1
1
qkWrxkG
q
r
rk
qll?
vpppq?321
221 qpq
vppq?32?
vp
数字信号处理 第 3章? 2004
由于此算法中采用了不同长度来进行抽取，所以有时也称为混合基 FFT算法。
下面为 时混合基一次分解为 3个 6点 DFT的流程图 3-4-13
1836N
数字信号处理 第 3章? 2004
数字信号处理 第 3章? 2004
经一次分解后的 3个 6点 DFT，每个又可以分解为 3个 2点的 DFT,如图 3-4-13所示数字信号处理 第 3章? 2004
2,算法的运算量第一次抽取后：
代替 N,代替第二次抽取后,
最后总运算量：
2111 )1( qppN
1q 2p 1p
22221 )1( qppq
32121 )1()1( ppppNpN
)( 21 vpppN v
数字信号处理 第 3章? 2004
3.5 DFT与 FFT的应用
DFT和 FFT在信号和信息处理的各个领域都具有广泛的应用。
本节主要介绍它们在频域分析、卷积与相关计算中的应用，并讨论 chirp-z变换及其快速算法数字信号处理 第 3章? 2004
3.5.1利用 FFT计算序列的频谱一,利用 FFT进行频谱分析的基本方法极坐标表示：
幅度谱：
相位谱：
)()()( kjXkXkX IR
X k X k e j k( ) ( ) ( )
X k X k X kR I( ) ( ) ( )2 2
( ) ( )( )k a r ct g X kX kI
R
数字信号处理 第 3章? 2004
FFT对模拟信号进行频谱分析的框图 3-5-1如下：
数字信号处理 第 3章? 2004
1.频率分辨率：
2.模拟频率分辨率：
3.用于 FFT的点数：
4.频率刻度值：
5.模拟信号长度：
6.分辨率：
F f fNs s2
2N
F
fN s
f fN k k Nk s 0 1 2,,,/?
NTfNt sp /
pt
F 1
数字信号处理 第 3章? 2004
例 3-5-1
用 FFT来计算信号的频谱,已知信号的最高频率为,
要求频率分辨率为,试确定：
1.采样间隔 T；
2.采用基 -2FFT的最小样点数 N,以及与此相对应的最小记录长度；
3.按你确定的参数所获得的实际分辨率 。
k H zf h 25.1? Hzf 5
数字信号处理 第 3章? 2004
解,
(1)按采样定理，采样间隔 T：
(2)基 -2FFT的最小样点数 N：
msfT
h
4.0105.2 12 1 3
5005/1m i n TFfN s
数字信号处理 第 3章? 2004
当采用基 -2FFT算法时，要求：
与此相对应的最小记录长度为：
（ 3）按确定的参数所获得的实际分辨率：
5 1 22 1]5 0 0[ l o g 2N
smsT p 0 4 8.24.05 1 2
Hz
N
fF s 88.4
数字信号处理 第 3章? 2004
二,用 FFT进行频谱分析存在的问题
1.频谱泄漏解决办法,采用其它形式的窗函数在实际应用中，通常将所观测的信号限制在一定的时间间隔内,也 就是说在时域对信号进行截断操作,或 称作加时间窗,亦即用时间窗函数乘以信号,由卷积定理可知，时域相乘,频域为卷积,
这就造成拖尾现象,称之为频谱泄漏,
数字信号处理 第 3章? 2004
2.栅栏效应用 DFT计算频谱时，只是知道频率为的整数倍处的频谱。在两个谱线之间的情况就不知道,这相当通过一个栅栏观察景象一样，故称作 栅栏效应 。
解决办法：序列后面 补零点加大 FFT
点数,可使谱线间隔变小来提高辨力，
以减少栅栏效应。
注意：若需要加窗，则应先加窗再补零。
2N
数字信号处理 第 3章? 2004
3.5.2 用 FFT计算线性卷积
1,线性卷积设 y（ n）是 x(n)（ n=0~M-1）和 h(n)（ n=0~N-1）
的线性卷积：
总运算量为：
)()()(*)()(
1
0
mnxmhnhnxny
N
m
Ｍ＋Ｎ－１１：的长度为?Nny )(
)1(1
)1(
NMN
NMN
）加法：（
乘法：
数字信号处理 第 3章? 2004
1.利用循环卷积计算线性卷积的条件设 是 x(n)和 h(n)长为 L的循环卷积：
其中 L>Max[N,M],
所以
)(nyc
)())(()()()()(
1
0
nRmnxmhnhnxny LL
L
m
c
)())(( rLnxnx
r
L
)()()()(
1
0
nRmrLnxmhny L
r
L
m
c
)()()(
1
0
nRmrLnxmh L
L
mr
数字信号处理 第 3章? 2004
）（
：范围内取非零值，故有仅在由于
yLny
mrLnxmhmrLnxmh
nh
N
m
L
m
Nn
)()()()(
)(
1
0
1
0
10
)()(
)()()(
1
0
nRrLny
nRmrLnxmhny
L
r
L
L
mr
c
）（
因此：
数字信号处理 第 3章? 2004
利用循环卷积计算线性卷积如下图 3-5-3：
数字信号处理 第 3章? 2004
利用 FFT进行线性卷积的步骤如下：
1.将序列 x(n)和 h(n)补零延长，使其长度若采用基 -2FFT，还应使 L大于或等于 的 2的最小整数次幂。
2.做 x(n)和 h(n)的长为 L点的 FFT得到 X(k)和 Y(k)，求它们的积 Y(k)=X(k)H(k)
3.求 Y（ k）的 IFFT并取前 N1点获得线性卷积的结果为
L≥ N1=N+M-1
N1
=IFFT[ ],0≤ n≤ N )(ny )(kY
数字信号处理 第 3章? 2004
二,长序列 FFT卷积的计算方法
1.重叠相加法
h(n)长度为 N,x(n）长度为无限长，取 M与 N尽量接近
x(n)与 y(n)的卷积为
)()( nxnx k
k
)()()( kMnRnxnx Mk
)(*)()(*)()( nxnhnhnxny k
k
)()](*)([ nynhnx k
k
k
k
数字信号处理 第 3章? 2004
重叠相加法的卷积示意图 3-5-4：
数字信号处理 第 3章? 2004
重叠相加法的步骤如下：
3.计算,并求长为 L的反变换，
即
4.将 的重叠部分相加，最后得到结果为
1.将 补零延长到 L =M+ N -1，并计算长为 L的 FFT，
得到
)(nh
)(kH
2.分别将 补零延长到 L =M+ N -1，并计算长为 L的
FFT，得到
)(nxk
)(kXk
)()()( kHkXkY kk?
)]([)( kYIF F Tny kk?
)(nyk
)()( nyny k
k
数字信号处理 第 3章? 2004
2.重叠保留法序列分段的方法：
0
0,0,1,,2()
( 1 ),1,1
nNxn
x n N n N L
( 1 ),0 1()
0,k
x n k L N n Lxn
n
为 其 他 值数字信号处理 第 3章? 2004
重叠保留法分段方法示意图数字信号处理 第 3章? 2004
输入的每段序列重叠 N-1点，而每段的循环卷积的输出去掉前面 N-1点只保留后面 M点，
)()(
0
kNnyny k
k
1,,1,)1('
2,,0,0)(
LNnMny
Nnny
k
k?
数字信号处理 第 3章? 2004
数字信号处理 第 3章? 2004
3.5.3 用 FFT计算线性相关
1.循环相关与线性相关的关系线性相关：
由于 仅在 n+k>0,n+k<M-1,k=0,…,L-1
范围内,有非零值,故知当 n的取值范围为：
取非零值的长度为
1
0
)()()()()(
L
kk
xy kyknxkyknxnr
)(nrxy
1)1(1 LMLMN
11L n M
()x n k?
数字信号处理 第 3章? 2004
循环相关：设若 则那么
1
0
1
0
~~ )()(~)(~)(~)(~
N
k
N
k
yx kyknxkyknxnr
LNn0 0 1,( 0,1 )n k N k L
1
0
~~ )()(~~
L
k
yx kyknxr
)()()(
1
0
nrkyknx xy
L
k
LNn0
(,)M a x M L N?
数字信号处理 第 3章? 2004
上述结果说明，在 0<n<N-L范围内，循环相关与线性相关相等若相关输出长度为 N1,相关序列长度为 L,为了利用循环相关得到正确的线性相关性结果,那么 循环相关的长度 N
至少应取
N=N1+L-1
数字信号处理 第 3章? 2004
2.利用 FFT计算相关函数的方法步骤：
1.FFT的长度 N满足 且
2.补零延长，构造周期为 N的序列
3.分别做 的 N点 FFT
计算 后求其反变换
11 NLN mN 2?
)(~),(~ nynx
)()(~),()(~ nRnynRnx NN
)(kRxy )(nrxy
数字信号处理 第 3章? 2004
3.用 FFT计算长序列相关函数的分段求和法当信号序列很长时,FFT长度很长这不利于信号的实时处理，因此为了提高速度采用分段求和法进行设输出的相关长度为,记录信号
y(n)的长度为 L=JP
1N
)()( jpnxnx j
1,,0
,0
0),()( Jj
Nnp
pnjpnyny
j?
数字信号处理 第 3章? 2004
则有：
那么
)()()()()(
1
0
1
0
jplyjplnxlylnxnr
p
l
j
p
l
jYX jj
)()(
)1(
kyknxjplk
lpj
jpk
令 10 Nn
)()()()()(
))()(()(
1
0
1
0
1
0
)1(1
0
nrkyknxkyknx
kyknxnr
xy
Jp
k
L
k
J
l
lpj
jpk
J
j
YX jj
10 Nn
数字信号处理 第 3章? 2004
总结分段法求和的步骤如下：
1.分段补零，做
2.分别计算 长度为 的
3.
4.作和 需做 J-1次
N/2点复加
5.求 需一个 N点 FFT
1,,0),(),( Jjnynx jj?
)(),( nynx jj 12 kN?
FFT，共作 J=L/p个 FFT
共轭乘计算共需作 J次 N/2点复乘 。
1,,0),()()( * NkkYkXkR jjYX jj?
10,)()(
1
0
NkkRkR
J
j
YXxy jj
)]([)( kRIFFTnr xyxy?
数字信号处理 第 3章? 2004
3.5.4
1.基本定义
x(n)有限长序列沿 Z平面上的一段螺线做 M点抽样其中 A和 W为复数,极坐标形式表示为线性调频 Z变换 (Chirp Z 变换 )算法
10 Nn
X z x n z
n
N
n( ) ( )?
0
1
z AW k Mk k 0 1
A A e j? 0 0?
W W e j0 0?
z A e W ek j k j0 00 0
数字信号处理 第 3章? 2004
式中 和 为实数，当 K=0时有
A决定谱分析起始点 的位置的值决定分析路径的盘旋趋势表示两个相邻分析点之间的夹角如果 的抽样点位于半径为 r 的圆上如果 的抽样点位于单位圆上
（常规的 DFT变换）
A0 W0
z A e j0 0 0
z0
W0
0
100 wrA zk
10 rA zk
数字信号处理 第 3章? 2004
如果,则随着 k增大，分析点 以为步长向外盘旋,时向内旋。
Chirp-Z变换的频率抽样点如图 3-5-8所示：
10?W zk
0 10?W
数字信号处理 第 3章? 2004
将 代入 Z变换公式得利用得
zk
X z x n AW x n A W k Mk
n
N
k n
n
N
n kn( ) ( )[ ] ( )
0
1
0
1
0 1
nk n k k n12 2 2 2[ ( ) ]
X z x n A Wk
n
N
n n k k n( ) ( ) [ ( ) ] /?
0
1
22 2 2
10)( 2/)(2/
1
0
2/ 222
MkWWAnxW nknnN
n
k
数字信号处理 第 3章? 2004
令则
Chirp-Z变换如图 3-5-9所示
y n x n A Wn n( ) ( ) / 2 2
h n W n( ) / 2 2
X z W y n h k n k Mk k
n
N
( ) ( ) ( )/
2
2
0
1
0 1
数字信号处理 第 3章? 2004
输出为当 时可以设想为频率随时间线性增长的复指数序列,即线性调频 (Chirp)信号。
)()()(*)()(
1
0
mnhmynhnynV
N
m
10?W
h n e j n( ) ( / ) 2 02?
数字信号处理 第 3章? 2004
2.Chirp-Z变换的实现步骤首先要确定现性卷积的区间，由于序列 x(n)的长度为 N,所以 y(n)的长度也是 N,如图 3-5-10c所示数字信号处理 第 3章? 2004
而 是无限长的，需截取。
但因只需要计算 V(n)在 [0,M-1]上 M个值
（ 1）
（ 2）
)0()()0(
1
0
mhmyV
N
m
)1()()1(
1
0
mMhmyMV
N
m
当 m由 0变到 N-1时,由 （ 1） 式知,m取最负的值
-(N-1),由 （ 2） 式知,m取最正的值 (M-1)。 可见,
为了计算出 V(n) 在区间 [0,M-1]上的 M个值,只要截取 h(n)在区间 [-(N-1),(M-1)]上的 (N+M-1)个值 。 如图
(b)所示 。 这时经线性卷积所得 V(n) 的非零值区间为
[-(N-1),(N+M-2)]。 长度为 2N+M-2。
h n e j n( ) ( / ) 2 02?
数字信号处理 第 3章? 2004
其次要确定循环卷积计算线性卷积时的
FFT长度 L,由
y n h n V n qL R n
q
L( ) ( ) ( ) ( )
为了用循环卷积代替线性卷积计算出 V(n)
在 [0,(M-1)]区间上的 M个序列值,要保证在上式中的周期延拓中,在 [0,M-1]区间上不能有混叠,循环卷积区间长度 L应大于或等于 N+M-1。 故在用基 -2 FFT算法进行快速卷积计算时,应选择 L≥ (N+M-1)
且满足 (m为自然数 )的最小值L m? 2
数字信号处理 第 3章? 2004
若选择 L=N+M-1,那么 y(n)尾部应补
M-1个零 。 并将 h(n)从 -(N-1)到 (M-1)所截取的一段 序列以 L为周期进行周期延拓,取主值序列形成,这时可以用快速卷积法计算如上构造的两个序列 y(n)和 的循环卷积 。h nL( )
)(ny
h nL( )
数字信号处理 第 3章? 2004
注意,
当选择 >N+M-1时,y(n)应补 L-N个零点,而 h(n)从区间 [(-N+1),(M-1)]截取后在 -N+1点前面补 L-(N+M-1)个零点后,以 L
为周期进行周期延拓 。 或直接截取 [-（ L-
M）,（ M-1） ]上的值后,再以 L为周期进行周期延拓取主值 。
L m? 2
数字信号处理 第 3章? 2004
具体步骤如下：
1.形成 序列
2.计算 FFT
h nL( )
h n W n M
W M n LL
n
n L
( )
/
( ) /
2
2
2
2
0 1
1
H k FFT h n k LL( ) [ ( )]0 1
数字信号处理 第 3章? 2004
3.做序列
4.计算 FFT
5.计算 IFFT
6.最后求得乘积
y n x n A W n N
N n L
n n
( ) ( )
/
2 2 0 1
0 1
Y k FFT y n k L( ) [ ( )]0 1
V n I F F T Y k H k n L( ) [ ( ) ( )]0 1
X z W V k k Mk k( ) ( )/2 2 0 1
3.1周期序列的离散傅立叶级数
3.1.1周期序列的傅立叶级数（ DFS）
对于周期为 N的周期序列 可用 基序列 { } 来展开 。
的基频为基波为第 k次谐波为
)(~ nx
nkNje?2
)(~ nx N
2
0?
nNjnj eene 2
1 0)(
nkNjnkj
k eene
2
0)(
数字信号处理 第 3章? 2004
由
)()(
2)(2
neeene k
nk
N
jrNkn
N
j
rNk
说明 是以 N为周期的周期序列，所以基序列 { }（ k=0,…,N -1) 只有 n个是独立的，可以用这 n个基序列将 展开
nkNje?2
nkNje?2
)(~ nx
数字信号处理 第 3章? 2004
通常记具有以下性质：
1.周期性
2.共轭对称性
3.可约性
4.正交性
Nj
N eW
2?
NW
)( rNnNnN WW
*)( nNnN WW
nNrnrN WW?
0
11)(1 1
0
)(
1
0
*
N
n
nkm
N
N
n
mn
N
kn
N WNWWN km
km
数字信号处理 第 3章? 2004
离散傅立叶级数的表示：
正变换：
反变换：
1
0
1
0
2
)(~)(~
)(~)(
~
N
n
nk
N
N
n
nk
N
j
Wnxenx
nxD F SkX
1
0
1
0
2
)(
~1
)(
~1
)(
~
)(
~
N
k
nk
N
N
k
nk
N
j
WkX
N
ekX
N
kXI D F Snx
数字信号处理 第 3章? 2004
3.1.2离散傅立叶级数（ DFS）的性质
1.线性性如果则对任何实数或复数,有
)(~)(~
)(~)(~
22
11
nxD FSkX
nxD FSkX
1a 2a
)(
~
)(
~
)(~)(~
2211
2211
kXakXa
nxanxaD FS
数字信号处理 第 3章? 2004
2.序列周期的移位性质如果则
)(~)(~ kXnxD F S?
)(
~
)(
~
)(
~
2
kXe
kXWmnxD F S
mk
N
j
mk
N
数字信号处理 第 3章? 2004
证明：
1
0
)(~)](~[
N
n
nk
NWmnxmnxD F S
mk
N
mN
mi
ik
N WWix
1
)(~
)(~)(~
1
0
kxWWixW mkN
N
i
ik
N
mk
N
数字信号处理 第 3章? 2004
3.频域移位（调制）特性如果则
)(~)(~ kXnxD F S?
)(~)(~ lkXnxWD F S nlN
数字信号处理 第 3章? 2004
4.周期卷积定理设 和 具有相同的周期 N
则周期卷积
)(~1 nx )(~2 nx
记为
1
0
21 )(
~)(~)(~ N
m
mnxmxny
)(~)(~ 21 nxnx)(~ ny
数字信号处理 第 3章? 2004图 3-1-1两个序列的周期卷积数字信号处理 第 3章? 2004
说明：
上图是周期为 N=6的两个序列卷积的计算过程。类似于线性卷积，首先进行变量代换为,再将其中一个序列进行反褶，移位，相乘，然后加。
运算仅在 m=0到 m=N-1内进行，计算出一个周期的结果，再进行周期延拓得到整个序列
)(~)(~ 21 nxnx 和
)(~)(~ 21 mxmx 和
)(~ ny
数字信号处理 第 3章? 2004
周期卷积有下述定理，若证明：
代入
)(~ kY )](~[ nyD FS )(~)(~ 21 kXkX?
1
0
1
)](
~
[)(~
N
kN
kYI D F Sny
)(~)(~ 21 kXkX nk
NW
1
0
1 )(
~ N
m
kX )(~
1 mx
mk
NW
数字信号处理 第 3章? 2004
得
1
0
1
0
1)(~ N
k
N
mN
ny )(~1 mx mkNW )(~ 2 kX nkNW?
1
0
N
m
1
0
1 N
kN
kmnNW )()(~ 2 kX)(~1 mx
由移位定理得
1
0
21 )(
~)(~)(~ N
m
mnxmxny
数字信号处理 第 3章? 2004
同理可证明 频域周期卷积定理若则
)(~)(~)(~ 21 nxnxny?
1
0
21 )(
~
)(
~1
)(~)(
~
N
l
lkXlX
N
nyD F SkY
数字信号处理 第 3章? 2004
3.1.3周期序列的傅立叶变换周期为 N的周期序列 的傅立叶变换可表示为脉冲串的形式证明：
)(~ nx
)(~?jeX
k N
2
)(~ kX )2( Nk
[1?F?)(~?jeX
2
1 )(~?jeX
de j
)(~)(
~1
)
2
()(
~1
1
0
2
1
0
2
0
nxekX
N
de
N
k
kX
N
N
n
N
nk
j
N
n
nj
数字信号处理 第 3章? 2004
3.2离散傅立叶变换
3.2.1有限长序列的离散傅立叶变换一,DFT的定义长度为 N的序列 x(n)其频谱为在 上从 0开始等间隔的取 N个点，相应的 （ k=0,…,N -1),则上式变为
1
0
)()(
N
n
njj enxeX
)2,0[?
N
k
k
2?
数字信号处理 第 3章? 2004
1
0
2
)()(
N
n
kn
N
jj
enxeX k
（ k=0,…,N -1)
)()( kjeXkX令 并采用记号 N
j
N e
2?
可得有限长序列 {x(n)}(n=0,1,2,…,N -1)的离散正反傅立叶变换数字信号处理 第 3章? 2004
离散傅立叶变换,简称 DFT
傅立叶反变换,简称 IDFT
1
0
)()()(
N
n
nk
NWnxnxD F TkX （ k=0,…,N -1)
1
0
)(1)()(
N
k
nk
NWkXNkXI D F Tnx （ k=0,…,N -1)
数字信号处理 第 3章? 2004
二,周期性以及与 DFS的关系
1.余数运算表达式如果,
m为整数；则有：
mNnn 1 10 1 Nn
1nn N?
数字信号处理 第 3章? 2004
此运算符表示 n被 N除，商为 m，余数为 。
是 的解,或称作取余数,或说作 n对
N取模值,或简称为取模值,n模 N。
1n
)( 1nNn
例如：
N=8
N=16
)1())9(( 8 xx? )5())5(( 8 xx?
)9())9(( 16 xx? )12())4(( 16 xx
数字信号处理 第 3章? 2004
2.有限长序列 x(n)和周期序列 的关系有限长序列 x(n)是周期序列 的主值序列
)(~ nx
~ ( ) (( )) ( )x n x n x n rN
N
r
x n x n R nN N( ) (( )) ( )?
)(~ nx
数字信号处理 第 3章? 2004
3.周期序列 与有限长序列 的关系同样，周期序列 是有限长序列的周期延拓而有限长序列 是周期序列的主值序列。
)(~ kX )(kX
~ ( ) (( )) ( )X k X k X k rN
N
r
X k X k R kN N( ) (( )) ( )?
)(~ kX
)(~ kX
)(kX
)(kX
数字信号处理 第 3章? 2004
三,DFT与 Z变换的关系长度为 N的序列 x(n)其 Z变换,
与傅立叶变换相比较有,
X z x n z n
n
N
( ) ( )
0
1
10)()()( 22 NkzXeXkX kNjezk
N
j
数字信号处理 第 3章? 2004
可见序列的 N点 DFT是 x(n)的 Z变换在单位圆上 N点的等间隔采样。显然，对于同一序列当频率采样点数不同时，其 DFT的值也不同。
数字信号处理 第 3章? 2004
3.2.2 DFT的一些性质一,线性性若 x(n)与 y(n)是同样长的序列，则对任何实数或复数有a a1 2,
)]([)]([
)]()([
21
21
nyD F TanxD F Ta
nyanxaD F T
数字信号处理 第 3章? 2004
二,循环移位性质如果那么
)]([)( nxD F TkX?
Y k D F T y n W X kN mk( ) [ ( )] ( )
)())(()( nRmnxny NN
数字信号处理 第 3章? 2004图 3-2-1循环移位示意图数字信号处理 第 3章? 2004
证明：
令 n+m=nl,则有
Y k x n m R n WN N Nkn
n
N
( ) (( )) ( )
0
1
x n m WN Nkn
n
N
(( ))
0
1
mN
mn
mnk
NN WnxkY
1
1
)1())1(()(
mN
mn
kn
NN
km
N WnxW
1
1
1))1((
1
01
1))1((
N
n
kn
NN
mk
N WnxWW X kN mK ( )
数字信号处理 第 3章? 2004
同理可证明 频域移位定理：
若则
=
X k D F T x n( ) [ ( )]?
)())(()( kRlkXkY NN
y n I D F T Y k( ) [ ( )]? W x n
N
nl ( )
数字信号处理 第 3章? 2004
三,共轭复序列的 DFT
设 为 的共轭复序列，则证明：
)(nx? )(nx
D F T x n X N k R kN N[ ( )] (( )) ( )
)()(
)()()]([
1
0
1
0
kRWnx
kRWnxnxD F T
N
nk
N
N
n
N
nk
N
N
n
)()()()( )(1
0
kRkNXkRWnx NNnkNN
N
n
数字信号处理 第 3章? 2004
四,共轭对称性
)()()( njxnxnx ir
)]()([
2
1
)( * nxnxnx r
)]()([21)( * nxnxnjx i
用 和 分别表示实部与虚部序列的 DFT:
)(kXo
)(kXe )(kXo
)]}()([
2
1{)]([)( * nxnxD F TnxD F TkX
re
)]()([21 * kNXkX
数字信号处理 第 3章? 2004
共轭对称性：
共轭反对称性：
)]}()([21{)]([)( * nxnxD F TnjxD F TkX io
)]()([21 * kNXkX
)()( kNXkX ee
)()( kNXkX oo
数字信号处理 第 3章? 2004
由于 x(n)和 均是有限长序列,其定义区间为 （ 0～ N-1）,注意,
与在第二章中的对称性不同,这里所谓的对称性是指关于 N/2点的对称性,而不是关于原点的对称,见右图 。
图 3-2-2 关于 N/2点的共轭对称性
)(kX
数字信号处理 第 3章? 2004
若 x(n)为实序列，则其 DFT满足共轭对称特性若 x(n)为纯虚序列，则其 DFT满足共轭反对称性例：已知 f(n)=x(n)+jy(n),x(n)和 y(n)为实序列,F(k)=1+jN,求 x(n),y(n)
)()( * kNXkX
)()( * kNXkX
数字信号处理 第 3章? 2004
解：
)()]([)(
)(
1
)(
1
)]([)(
)()(]))(()([
2
1
)]([
)()(]))(()([
2
1
)]([
1
0
1
0
*
*
nNkYI D F Tny
nW
N
WkX
N
kXI D F Tnx
kj N RkRkNFkFnjyD F T
kRkRkNFkFnxD F T
N
k
kn
N
N
k
kN
N
NNN
NNN
数字信号处理 第 3章? 2004
五,循环卷积定理设 和 是两个具有相同长度 N的有限长序列，定义循环卷积：
n=0,…,N -1
记为同时满足交换率
)(1 nx )(2 nx
y n x m x n m R nN N
m
N
( ) ( ) (( )) ( )
1 2
0
1
y n x n x n( ) ( ) ( )1 2
)()()( 12 nxnxny
1
0
12 )())(()(
N
m
NN nRmnxmx
数字信号处理 第 3章? 2004
循环卷积的直接计算与前面讨论的周期卷积类似,步骤为反褶 循环移位 乘积 累加例 3-2-2：已知做 N=8的循环卷积 y(n)
解：先进行变量代换,将 变成
,接着将 周期延拓为 反褶后得到,从 n=0开始,对每一个 n=0,…,N-1,对进行循环移位并取主值形成再分别将 与 对应的 m点从
m=0到 m=N-1逐点相乘,并将乘积累加就得到了各个点的 y(n).计算过程图 3-2-3如下：
)2()(),()( 4241 nRnxnRnx
)(),( 21 nxnx )(),( 21 mxmx
)(2 mx Nmx ))((2
Nmx ))((2?
Nmx ))((2?
)())((2 mRmnx NN?
)(1 mx )())((2 mRmnx NN?
数字信号处理 第 3章? 2004
数字信号处理 第 3章? 2004
循环卷积定理；
若,
则
)]([)( 11 nxD F TkX? )]([)( 22 nxD F TkX?
nk
NN
N
n
N
m
nk
NNN
N
n
N
m
Wmnxmx
WnRmnxmx
nyD F TkY
))(()(
)]())(()([
)]([)(
2
1
0
1
1
0
21
1
0
1
0
)()()()( 2121
1
0
kXkXKXWmx mkN
N
m
Y k D F T y n X k X k( ) [ ( )] ( ) ( ) 1 2
数字信号处理 第 3章? 2004
同理可以证明 频域卷积定理：
若则
y n x n x n( ) ( ) ( )? 1 2
)()(1)]([)( 21 kXkX
N
nyD F TkY
1
0
21 )())(()(
1 N
l
NN kRlkXlXN
数字信号处理 第 3章? 2004
六,循环相关定理
n=0,…N -1
称为序列
)()( nynx 和设两个有限长实序列 具有相同的长度 N
1
0
)())(()()(~
N
m
NNxy nRmnymxnr
的 循环互相关)()( nynx 和数字信号处理 第 3章? 2004
循环相关定理：
若,
则有
)]([)( nxD F TkX? )]([)( nyD FTky?
)()(*)]([)( kYkXnrD FTkR xyxy
数字信号处理 第 3章? 2004
当 x(n)=y(n)时,称 为序列的 循环自相关)(~ nrxx
)(kRxx 2|)(|)()(* kXkXkX
2|)(| kX 是有限长序列的离散功率谱，注意
2|)(| kX 中没有相位的信息。
数字信号处理 第 3章? 2004
七,帕思瓦定理 (Parseval)
帕思瓦定理的离散傅立叶变换形式
1
0
)(*)(
N
n
nynx )(*)(1 1
0
kYkXN
N
k
数字信号处理 第 3章? 2004
证明：
=
=
=
=
1
0
)(*)(
N
n
nynx )(*)(1
1
0
1
0
nyWkXN nkN
N
k
N
n
)(*)(1
1
0
1
0
nyWkXN nkN
N
n
N
k
*)()(1 1
0
1
0
nyWkXN nkN
N
n
N
k
)(*)(1
1
0
kYkXN
N
k
数字信号处理 第 3章? 2004
当 x(n)=y(n)时，则有：
说明时域中的能量与频域中的能量相等
1
0
2|)(|
N
n
nx 2
1
0
|)(|1 kXN
N
k
数字信号处理 第 3章? 2004
3,2,3 离散频率与数字频率和模拟频率之间的关系
模拟频率,f 和 W,单位为赫兹 （ Hz） 和 弧度 /秒
（ rad/s） 。 关系为,W?2?f,
离散信号数字频率,?,单位为弧度 （ rad） 。 并通过采样信号的频谱,建立了模拟频率与数字频率之间的关系：
取值范围 对应于模拟频率的
离散的数字频率,用 k表示 。,因此可得出离散频率 k与数字频率和模拟频率之间的对应关系为：
sf
fT 2?W?
10 Nk
kNffkNk s 2
20 或
2/sf
数字信号处理 第 3章? 2004
3.3频域采样定理频域采样是指对有限长序列的傅氏变换在频域离散化得到 x(k)的过程。
本节讨论两个基本问题：
a：频域采样（ DFT）不失真的条件，即由
X (k)不失真地恢复 x(n)的条件
b：用 X (k)表示 X (z)和 的插值公式
(内插公式 )
X e j( )?
X e j( )?
数字信号处理 第 3章? 2004
1.频域采样 X（ k）不失真恢复 x(n)的条件：采样点数 N必须大于序列的长度 L
假定 x(n)的长度为 L（没有限制）
频率采样
=,0≤k≤N -1
令 =IDFT[X(k)]（ 0≤n≤N -1）,由于
=DFS[ ] =
= =IDFS[ ] =
n
nznxzX )()(
kNWzzXkX )()(
n
nk
NWnx )(
)(nxN
NkXkX ))(()(~? )(~ nx )(kX )(
~ kX )(kR
N
~( )x n NN nx ))(( )(~ kX )(nxN )(~ nx )(nR
N
数字信号处理 第 3章? 2004
因而有取主值区
= =====
=
= =
故有
=
由上式可知,是原序列 的周期延拓周期为 N，然后取主值，如图 3-3-1所示。
)(~ nx 1
0
1
N X k W N
nk
k
N ~
( )?
1
0
)(1
N
k
nk
NWkXN
1
0
)(1
N
k
nk
N
m
mk
N WWmxN
m
N
k
knm
NWmxN
1
0
)()(1 x n rN
r
( )?
)(nxN?
r
N nRrNnx )()(
)(nxN )(nx
数字信号处理 第 3章? 2004图 3-3-1 时域恢复示意图结论：若序列长度为 L，频域采样点数（或 DFT
的长度）为 N，且 L<N，则频域采样后可不失真地恢复原序列 ；但若 L>N，则频域采样后不能不失真地恢复原序列 。
)(nx
)(nx
数字信号处理 第 3章? 2004
2.用 表示 和 的内插公式
（ 1）用 表示设序列长度为 N，由傅里叶变换对得
= =
)(kX )(zX X e j( )?
)(kX )(zX
)(kX?
1
0
)(
N
n
nk
NWnx )(nx?
1
0
)(1
N
k
nk
NWkXN
数字信号处理 第 3章? 2004
= =
=
=
= =
)(zX
1
0
)(
N
n
nznx n
N
k
nk
N
N
n
zWkXN?
1
0
1
0
)(1
n
N
k
nk
N
N
n
zWkXN?
1
0
1
0
)(1
1
0
11
1)(1 N
k
k
N
NNk
N
zW
zWkX
N
1
0
11
)(1 N
k
k
N
N
zW
kX
N
z
1
0
)()(
N
k
k zkX?
其中
11
11)(
zW
z
Nz kN
N
k?
数字信号处理 第 3章? 2004
（ 2）用 表示 的内插公式将 分别代入式（ 3-3-6）和（ 3-3-7），
即可得到用 表示 的内插公式如下
= =
)(kX X e j( )?
jez?
)(kX X e j( )?
)(?jeX?jezzX?)(?
1
0
)()(
N
k
j
k ekX
)
2
(
1
11
)(
N
kj
Nj
j
k
e
e
N
e
]
22
[
]2/)
2
s i n [ (
)
2
s i n (1
N
kN
j
e
N
k
N
N
)2( Nk
数字信号处理 第 3章? 2004
其中与下面的时域采样中的内插函数相似图形 3-3-2如下：
2
2
s i n)s i n (
)(
t
t
T
t
T
t
tg
s
s
W
W
2
)1(
]2/)s in [ (
)
2
s in (1?
Nj
e
N
N
( )
数字信号处理 第 3章? 2004
图 3-2-2内插函数 零极点与 的幅频特性图)(z
k? )(
数字信号处理 第 3章? 2004
例：已知 =,0< <1,对 的 z变换 在单位圆上等间隔采样 N点,k=0,…,N-1，求
IDFT[ ]。
解：
na
)(nuan)(nx )(nx
|)()( zXkX? KNwz
)(kX
)(
1
)(
)()()(
)()()]([)(
0
0
nR
a
a
nRaa
nRanRrNnua
nRrNnxkXI D F Tnx
NN
n
r
N
rNn
r
N
rNn
r
N
rNn
r
NN
a )(zX
)0,1)(,0,10( rrNnurNnNn
数字信号处理 第 3章? 2004
3.4 DFT的快速算法 —— FFT
DFT的运算量：
减少运算量的方法：
1）将长度 N变短，例如若长度为 N/2，则运算量变成了：
2）利用 的性质：周期性共轭对称性 可约性
22
1
0
1
)1~1()()()(
NNNN
NkWnxnxD F TkX
N
n
nk
N
）（复加：，复乘：
4/4/ 22 NN?复加：，复乘：
nkNW )( rNnNnN WW
*)( nNnN WW nNrnrN WW?
数字信号处理 第 3章? 2004
FFT算法分类
基 -2 FFT算法：
所谓基 -2是指要求长度 N满足 （ M为整数），若不满足可将序列补零延长，使其满足。
混合基算法等
时域抽取与频域抽取：
MN 2?
），简称（
算法按频域抽取
），简称（
算法按时域抽取
FFT-D I FFr e q e n c y-In-D e c i m a t i on
FFT-D I FT i m e -In - D e c i m a t i on
FFT
F F T
数字信号处理 第 3章? 2004
3.4.1 时域抽取基 -2FFT算法（ DIT-FFT）
1.算法的推导按 n的奇偶把时间序列 x(n)分解为两个长为 N/2
点的序列，即因此
)2()(1 rxrx?
)12()(2 rxrx
12,...,1,0 Nr
12,...,1,0 Nr
kn
N
N
n
WnxkX )()(
1
0
k
N
kr
N
N
r
kr
N
N
r
rk
N
N
r
kr
N
N
r
WWrxWrx
WrxWrx
2
2
12/
0
2
1
12/
0
)12(
12/
0
2
12/
0
)()(
)12()2(
数字信号处理 第 3章? 2004
由于所以即其中 分别为 的 N/2点
DFT
这是 前 N/2点 DFT
X k x r W W x r W
X k W X k k N
r
N
N
kr
N
k
r
N
N
kr
N
k
( ) ( ) ( )
( ) ( ),,.,,,/
/
/
/
/
0
2 1
1 2
0
2 1
2 2
1 2 0 1 2 1
X k X k1 2( ) ( )和 x n x n1 2( ) ( )和
W e e WN kr j N Kr j N kr Nkr2 2 2 2 2 2/ /
kn
N
N
n
WnxkX 2/112/
0
1 )()(?
1
2,.,.,1,0
Nk
kn
N
N
n
WnxkX 2/212/
02
)()(
12,.,.,1,0 Nk
)12,...1,0)(( NkkX
数字信号处理 第 3章? 2004
图 3-4-1 蝶式运算图对于 后 N/2的 DFT,
由于 （周期性）
因此可用蝶式运算图来表示上述前 N/2和后 N/2两式,如图 3-4-1 所示
)(kX
kNNkN WW 2/
X k N X k W X kNk( ) ( ) ( )2 1 212,.,.,1,0 Nk
数字信号处理 第 3章? 2004
例如,N=8时的 DFT,可以分解为两个 N/2=4点 DFT
如图 3-4-2所示,
数字信号处理 第 3章? 2004
由于,因而 N/2仍是偶数,可以进一步把每个
N/2点的序列再按其奇偶部分分解为两个 N/4的子序列从而 可表示为
MN 2?
)12()(
)2()(
14
13
lxlx
lxlx )1
4(,.......,1,0
Nl
)(1 kX
)12(
2/1
14/
0
2
2/1
14/
0
1 )12()2()(
lkN
N
l
kl
N
N
l
WlxWlxkX
kl
N
N
l
k
N
kl
N
N
l
WlxWWlx 4/4
14/
0
2/4/3
14/
0
)()(
)()( 42/3 kXWkX kN 14,........1,0 N
数字信号处理 第 3章? 2004
因而有其中对 也可进行同样的分解：
k=0,1,...,N/4-1
)()()
4
( 42/31 kXWkX
N
kX kN
X k D F T x l x l W
X k D F T x l x l W
l
N
N
kl
l
N
N
kl
3 3
0
4 1
3 4
4 4
0
4 1
4 4
( ) ( ) ( )
( ) ( ) ( )
/
/
/
/
X k2( )
)()()( 62/52 kXWkXkX kN
)()()4( 62/52 kXWkXNkX kN
数字信号处理 第 3章? 2004
其中这样又一次的分解得到 4个 N/4点 DFT
klNN
l
WlxlxD F TkX 4/5
14/
0
55 )()()(?
klNN
l
WlxlxD F TkX 4/6
14/
0
66 )()()(?
)2()( 25 lxlx?
)14(,...,1,0)12()( 26 Nllxlx
数字信号处理 第 3章? 2004
如下图 3-4-3所示：
那么依次类推，经过 M-1次分解后，将 N点
DFT分解成 N/2个两点 DFT
数字信号处理 第 3章? 2004
下图为 N=8时的一个完整基 -2 DIT-FFT运算流图 3-4-4
2M
数字信号处理 第 3章? 2004
2.运算量当 N= 时，总共有 M级分解，每级有 N/2个蝶式运算。
每个蝶式运算需一次复乘两次复加，这样 M级总共需要的运算量为复乘次数复加次数
2M
N M N N
2 2 2 log
N M N N l o g 2
数字信号处理 第 3章? 2004
3.FFT算法的特点
（ 1）倒码码位倒置是指将原二进制数的码位倒过来按从低位到高位排列如：序号 4用 3位二进制表示正常码为 100
倒码为 001，变成了 1
顺序与倒序对照表如下：
数字信号处理 第 3章? 2004
顺序 二进制数 倒码 倒码顺序
0
1
2
3
4
5
6
7
000
001
010
011
100
101
110
111
000
100
010
110
001
101
011
000
0
4
2
6
1
5
3
7
数字信号处理 第 3章? 2004
（ 2）原位运算利用同一存储单元存放蝶式运算输入和输出数据的方法。
4.DIF-FFT算法其他形式的流图输入的数据为正序，输出是倒码排列。
如下图 3-4-7所示数字信号处理 第 3章? 2004
图 3-4-7 N=8 时输入是正常顺序的、输出是倒码排列的 DIT-FFT运算流图数字信号处理 第 3章? 2004
3.4.2 频域抽取基 -2 FFT算法 (DIF-FFT)
1.算法：
X k D F T x n x n W
x n W x n W
x n W x n N W
x n W x n N W
n
N
N
nk
n
N
N
nk
n N
N
N
nk
n
N
N
nk
n
N
N
n N k
n
N
N
Nk
N
nk
( ) ( ) ( )
( ) ( )
( ) ( / )
( ) ( / )
/
/
/ /
( / )
/
/
0
1
0
2 1
2
1
0
2 1
0
2 1
2
0
2 1
2
2
2
数字信号处理 第 3章? 2004
由于
N点 DFT按 k的奇偶分组可分为两个 N/2的 DFT
k取偶数时 （ k=2r,r=0,1,...,N/2-1）
W k
kN
kN k/ ( )2 1 1
1
为偶数为奇数
X r x n x n N W
x n x n N W
n
N
N
rn
n
N
N
rn
( ) [ ( ) ( / )]
( ) ( / )
/
/
/
2 2
2
0
2 1
2
0
2 1
2
数字信号处理 第 3章? 2004
k取奇数时（ k=2r+1,r=0,1,...,N/2-1)
2.蝶形运算和 进行如下蝶形运算
rnNnN
N
n
nr
N
N
n
WWNnxnx
WNnxnxrX
2/
12/
0
)12(
12/
0
)2/()(
)]2/()([)12(
)(nx )2/( Nnx?
数字信号处理 第 3章? 2004
如下图 3-4-8 DIF-FFT的蝶式运算流图：
x(n) x(n)+ x(n+N/2)
x(n+N/2) [x(n)- x(n+N/2)]
3.N=8 时,按 k 的奇偶分解过程先蝶形运算,后 DFT
nNW1?
nNW
数字信号处理 第 3章? 2004
如图 3-4-9 DIF-FFT的一次分解运算流图（ N=8）：
数字信号处理 第 3章? 2004
4.DIF-FFT的二次分解由于 N/2仍然为 2的整数幂，继续将 N/2点 DFT分成偶数组和奇数组，这样每个 N/2点 DFT又可分解成两个 N/4
点 DFT，其输入序列分别是按上下对半分图开后通过蝶式运算构成的 4个子序列,如图 3-4-10
数字信号处理 第 3章? 2004
按照以上方法继续分解下去，经过 M-1次分解，
最后分解为 N/2个两点 DFT，这 N/2个 2点 DFT的输出就是 N点 DFT的结果 X(k),如图 3-4-11
数字信号处理 第 3章? 2004
上图给出了 N=8时完整的 DIF-FFT的运算流图。由于这种方法是 按Ｘ（Ｋ）在频域进行奇偶分解，
因此称之为频域抽取ＦＦＴ运算．
比较ＤＩＦ－ＦＦＴ与ＤＩＴ－ＦＦＴ：
相同点：运算次数与存储量相同不同点：１,ＤＩＦ－ＦＦＴ输入序列为自然序列而输出为码位倒置序列
２,蝶式运算过程不同,
ＤＩＴ－ＦＦＴ是序列先乘旋转因子后相加减
ＤＩＦ－ＦＦＴ是序列先相加减后乘旋转因子数字信号处理 第 3章? 2004
3.4.3逆 DFT的快速算法（ IFFT）
1.比较 DFT与 IDFT的计算公式比较两式可知只要将 FFT中的旋转因子为,再乘以 1/N即可得到 IDFT的快速算法
IFFT 。
X k x n W k NN nk
n
N
( ) ( ),,.,,,,
0 1
0
1
x n N X k W n NN nk
k
N
( ) ( ),,.,,,,
1 0 1
0
1
WNnk
WN nk?
数字信号处理 第 3章? 2004
另外，可将常数 1/N分配到每级运算中，
因为,也就是每级蝶形运算均乘以 1/2
2.直接利用 FFT程序因为所以
1 1
2N
M? ( )
x n N X k W n NN nk
k
N( ) ( ),,.,,,,
1 0 1
0
1
x n N X k W Nnk
k
N
( ) ( )1
0
1
数字信号处理 第 3章? 2004
两边取共轭有：
此方法只需要一个 FFT程序即可进行正逆变换的快速计算。
x n N X k W n NN nk
k
N
( ) ( ),.,,,,
1 0 1
0
1
1N D F T X k{ [ ( )]}
数字信号处理 第 3章? 2004
FFT（ IFFT）算法的实现：
1.纯软件实现
2.硬件实现
3.DSP（软硬件结合）
数字信号处理 第 3章? 2004
3.4.4 N为合数的 FFT算法（混合基）
1.算法的实现长度 N是复合数,
共 V个因子 。
令 其中将 x(n)每隔 点抽取一点
vppppN?321
11 qpN vpppq?321
1p
组共
11
11
1
1
),1(,,1,0
)1(
)1(
)(
pqr
prpx
rpx
rpx
数字信号处理 第 3章? 2004
或记为例如：,即 =3,=6,按以上的方法将 x(n)分为 3组，每组长度为 6,如下所示：
第 0组,
第 1组,
第 2组,
)1(,,1,0),1(,,1,0)()( 111 plqrlrpxrx l
1863N 1p 1q
)(0 rx )15()12()9()6()3()0( xxxxxx
)(1 rx
)(2 rx
)16()13()10()7()4()1( xxxxxx
)17()14()11()8()5()2( xxxxxx
数字信号处理 第 3章? 2004
序列 x(n)的 N点 DFT为将 代入，则
1
0
)()(
N
n
nk
NWnxkX 1,,1,0 Nk?
lrpn 1
1
0
)1(
11
1
0
1
1
0
1
1
0
1
11
1
1
1
1 )1()1()(
)()(
q
r
rkp
N
kp
N
q
r
rkp
N
k
N
q
r
rkp
N
N
n
nk
N
WWprpxWWrpxWrpx
WnxkX
1
0
1
1
0
1
1
1
)(
q
r
rkp
N
p
l
lk
N WlrpxW
数字信号处理 第 3章? 2004
令则由于继续令如此进行下去直到最后变为 点的 DFT
1,,1,0)()( 1
1
0
1
1
1
qkkGWlrpx l
q
r
rkp
N?
1,,1,0)()( 1
1
0
1
1
qkWrxkG
q
r
rk
qll?
vpppq?321
221 qpq
vppq?32?
vp
数字信号处理 第 3章? 2004
由于此算法中采用了不同长度来进行抽取，所以有时也称为混合基 FFT算法。
下面为 时混合基一次分解为 3个 6点 DFT的流程图 3-4-13
1836N
数字信号处理 第 3章? 2004
数字信号处理 第 3章? 2004
经一次分解后的 3个 6点 DFT，每个又可以分解为 3个 2点的 DFT,如图 3-4-13所示数字信号处理 第 3章? 2004
2,算法的运算量第一次抽取后：
代替 N,代替第二次抽取后,
最后总运算量：
2111 )1( qppN
1q 2p 1p
22221 )1( qppq
32121 )1()1( ppppNpN
)( 21 vpppN v
数字信号处理 第 3章? 2004
3.5 DFT与 FFT的应用
DFT和 FFT在信号和信息处理的各个领域都具有广泛的应用。
本节主要介绍它们在频域分析、卷积与相关计算中的应用，并讨论 chirp-z变换及其快速算法数字信号处理 第 3章? 2004
3.5.1利用 FFT计算序列的频谱一,利用 FFT进行频谱分析的基本方法极坐标表示：
幅度谱：
相位谱：
)()()( kjXkXkX IR
X k X k e j k( ) ( ) ( )
X k X k X kR I( ) ( ) ( )2 2
( ) ( )( )k a r ct g X kX kI
R
数字信号处理 第 3章? 2004
FFT对模拟信号进行频谱分析的框图 3-5-1如下：
数字信号处理 第 3章? 2004
1.频率分辨率：
2.模拟频率分辨率：
3.用于 FFT的点数：
4.频率刻度值：
5.模拟信号长度：
6.分辨率：
F f fNs s2
2N
F
fN s
f fN k k Nk s 0 1 2,,,/?
NTfNt sp /
pt
F 1
数字信号处理 第 3章? 2004
例 3-5-1
用 FFT来计算信号的频谱,已知信号的最高频率为,
要求频率分辨率为,试确定：
1.采样间隔 T；
2.采用基 -2FFT的最小样点数 N,以及与此相对应的最小记录长度；
3.按你确定的参数所获得的实际分辨率 。
k H zf h 25.1? Hzf 5
数字信号处理 第 3章? 2004
解,
(1)按采样定理，采样间隔 T：
(2)基 -2FFT的最小样点数 N：
msfT
h
4.0105.2 12 1 3
5005/1m i n TFfN s
数字信号处理 第 3章? 2004
当采用基 -2FFT算法时，要求：
与此相对应的最小记录长度为：
（ 3）按确定的参数所获得的实际分辨率：
5 1 22 1]5 0 0[ l o g 2N
smsT p 0 4 8.24.05 1 2
Hz
N
fF s 88.4
数字信号处理 第 3章? 2004
二,用 FFT进行频谱分析存在的问题
1.频谱泄漏解决办法,采用其它形式的窗函数在实际应用中，通常将所观测的信号限制在一定的时间间隔内,也 就是说在时域对信号进行截断操作,或 称作加时间窗,亦即用时间窗函数乘以信号,由卷积定理可知，时域相乘,频域为卷积,
这就造成拖尾现象,称之为频谱泄漏,
数字信号处理 第 3章? 2004
2.栅栏效应用 DFT计算频谱时，只是知道频率为的整数倍处的频谱。在两个谱线之间的情况就不知道,这相当通过一个栅栏观察景象一样，故称作 栅栏效应 。
解决办法：序列后面 补零点加大 FFT
点数,可使谱线间隔变小来提高辨力，
以减少栅栏效应。
注意：若需要加窗，则应先加窗再补零。
2N
数字信号处理 第 3章? 2004
3.5.2 用 FFT计算线性卷积
1,线性卷积设 y（ n）是 x(n)（ n=0~M-1）和 h(n)（ n=0~N-1）
的线性卷积：
总运算量为：
)()()(*)()(
1
0
mnxmhnhnxny
N
m
Ｍ＋Ｎ－１１：的长度为?Nny )(
)1(1
)1(
NMN
NMN
）加法：（
乘法：
数字信号处理 第 3章? 2004
1.利用循环卷积计算线性卷积的条件设 是 x(n)和 h(n)长为 L的循环卷积：
其中 L>Max[N,M],
所以
)(nyc
)())(()()()()(
1
0
nRmnxmhnhnxny LL
L
m
c
)())(( rLnxnx
r
L
)()()()(
1
0
nRmrLnxmhny L
r
L
m
c
)()()(
1
0
nRmrLnxmh L
L
mr
数字信号处理 第 3章? 2004
）（
：范围内取非零值，故有仅在由于
yLny
mrLnxmhmrLnxmh
nh
N
m
L
m
Nn
)()()()(
)(
1
0
1
0
10
)()(
)()()(
1
0
nRrLny
nRmrLnxmhny
L
r
L
L
mr
c
）（
因此：
数字信号处理 第 3章? 2004
利用循环卷积计算线性卷积如下图 3-5-3：
数字信号处理 第 3章? 2004
利用 FFT进行线性卷积的步骤如下：
1.将序列 x(n)和 h(n)补零延长，使其长度若采用基 -2FFT，还应使 L大于或等于 的 2的最小整数次幂。
2.做 x(n)和 h(n)的长为 L点的 FFT得到 X(k)和 Y(k)，求它们的积 Y(k)=X(k)H(k)
3.求 Y（ k）的 IFFT并取前 N1点获得线性卷积的结果为
L≥ N1=N+M-1
N1
=IFFT[ ],0≤ n≤ N )(ny )(kY
数字信号处理 第 3章? 2004
二,长序列 FFT卷积的计算方法
1.重叠相加法
h(n)长度为 N,x(n）长度为无限长，取 M与 N尽量接近
x(n)与 y(n)的卷积为
)()( nxnx k
k
)()()( kMnRnxnx Mk
)(*)()(*)()( nxnhnhnxny k
k
)()](*)([ nynhnx k
k
k
k
数字信号处理 第 3章? 2004
重叠相加法的卷积示意图 3-5-4：
数字信号处理 第 3章? 2004
重叠相加法的步骤如下：
3.计算,并求长为 L的反变换，
即
4.将 的重叠部分相加，最后得到结果为
1.将 补零延长到 L =M+ N -1，并计算长为 L的 FFT，
得到
)(nh
)(kH
2.分别将 补零延长到 L =M+ N -1，并计算长为 L的
FFT，得到
)(nxk
)(kXk
)()()( kHkXkY kk?
)]([)( kYIF F Tny kk?
)(nyk
)()( nyny k
k
数字信号处理 第 3章? 2004
2.重叠保留法序列分段的方法：
0
0,0,1,,2()
( 1 ),1,1
nNxn
x n N n N L
( 1 ),0 1()
0,k
x n k L N n Lxn
n
为 其 他 值数字信号处理 第 3章? 2004
重叠保留法分段方法示意图数字信号处理 第 3章? 2004
输入的每段序列重叠 N-1点，而每段的循环卷积的输出去掉前面 N-1点只保留后面 M点，
)()(
0
kNnyny k
k
1,,1,)1('
2,,0,0)(
LNnMny
Nnny
k
k?
数字信号处理 第 3章? 2004
数字信号处理 第 3章? 2004
3.5.3 用 FFT计算线性相关
1.循环相关与线性相关的关系线性相关：
由于 仅在 n+k>0,n+k<M-1,k=0,…,L-1
范围内,有非零值,故知当 n的取值范围为：
取非零值的长度为
1
0
)()()()()(
L
kk
xy kyknxkyknxnr
)(nrxy
1)1(1 LMLMN
11L n M
()x n k?
数字信号处理 第 3章? 2004
循环相关：设若 则那么
1
0
1
0
~~ )()(~)(~)(~)(~
N
k
N
k
yx kyknxkyknxnr
LNn0 0 1,( 0,1 )n k N k L
1
0
~~ )()(~~
L
k
yx kyknxr
)()()(
1
0
nrkyknx xy
L
k
LNn0
(,)M a x M L N?
数字信号处理 第 3章? 2004
上述结果说明，在 0<n<N-L范围内，循环相关与线性相关相等若相关输出长度为 N1,相关序列长度为 L,为了利用循环相关得到正确的线性相关性结果,那么 循环相关的长度 N
至少应取
N=N1+L-1
数字信号处理 第 3章? 2004
2.利用 FFT计算相关函数的方法步骤：
1.FFT的长度 N满足 且
2.补零延长，构造周期为 N的序列
3.分别做 的 N点 FFT
计算 后求其反变换
11 NLN mN 2?
)(~),(~ nynx
)()(~),()(~ nRnynRnx NN
)(kRxy )(nrxy
数字信号处理 第 3章? 2004
3.用 FFT计算长序列相关函数的分段求和法当信号序列很长时,FFT长度很长这不利于信号的实时处理，因此为了提高速度采用分段求和法进行设输出的相关长度为,记录信号
y(n)的长度为 L=JP
1N
)()( jpnxnx j
1,,0
,0
0),()( Jj
Nnp
pnjpnyny
j?
数字信号处理 第 3章? 2004
则有：
那么
)()()()()(
1
0
1
0
jplyjplnxlylnxnr
p
l
j
p
l
jYX jj
)()(
)1(
kyknxjplk
lpj
jpk
令 10 Nn
)()()()()(
))()(()(
1
0
1
0
1
0
)1(1
0
nrkyknxkyknx
kyknxnr
xy
Jp
k
L
k
J
l
lpj
jpk
J
j
YX jj
10 Nn
数字信号处理 第 3章? 2004
总结分段法求和的步骤如下：
1.分段补零，做
2.分别计算 长度为 的
3.
4.作和 需做 J-1次
N/2点复加
5.求 需一个 N点 FFT
1,,0),(),( Jjnynx jj?
)(),( nynx jj 12 kN?
FFT，共作 J=L/p个 FFT
共轭乘计算共需作 J次 N/2点复乘 。
1,,0),()()( * NkkYkXkR jjYX jj?
10,)()(
1
0
NkkRkR
J
j
YXxy jj
)]([)( kRIFFTnr xyxy?
数字信号处理 第 3章? 2004
3.5.4
1.基本定义
x(n)有限长序列沿 Z平面上的一段螺线做 M点抽样其中 A和 W为复数,极坐标形式表示为线性调频 Z变换 (Chirp Z 变换 )算法
10 Nn
X z x n z
n
N
n( ) ( )?
0
1
z AW k Mk k 0 1
A A e j? 0 0?
W W e j0 0?
z A e W ek j k j0 00 0
数字信号处理 第 3章? 2004
式中 和 为实数，当 K=0时有
A决定谱分析起始点 的位置的值决定分析路径的盘旋趋势表示两个相邻分析点之间的夹角如果 的抽样点位于半径为 r 的圆上如果 的抽样点位于单位圆上
（常规的 DFT变换）
A0 W0
z A e j0 0 0
z0
W0
0
100 wrA zk
10 rA zk
数字信号处理 第 3章? 2004
如果,则随着 k增大，分析点 以为步长向外盘旋,时向内旋。
Chirp-Z变换的频率抽样点如图 3-5-8所示：
10?W zk
0 10?W
数字信号处理 第 3章? 2004
将 代入 Z变换公式得利用得
zk
X z x n AW x n A W k Mk
n
N
k n
n
N
n kn( ) ( )[ ] ( )
0
1
0
1
0 1
nk n k k n12 2 2 2[ ( ) ]
X z x n A Wk
n
N
n n k k n( ) ( ) [ ( ) ] /?
0
1
22 2 2
10)( 2/)(2/
1
0
2/ 222
MkWWAnxW nknnN
n
k
数字信号处理 第 3章? 2004
令则
Chirp-Z变换如图 3-5-9所示
y n x n A Wn n( ) ( ) / 2 2
h n W n( ) / 2 2
X z W y n h k n k Mk k
n
N
( ) ( ) ( )/
2
2
0
1
0 1
数字信号处理 第 3章? 2004
输出为当 时可以设想为频率随时间线性增长的复指数序列,即线性调频 (Chirp)信号。
)()()(*)()(
1
0
mnhmynhnynV
N
m
10?W
h n e j n( ) ( / ) 2 02?
数字信号处理 第 3章? 2004
2.Chirp-Z变换的实现步骤首先要确定现性卷积的区间，由于序列 x(n)的长度为 N,所以 y(n)的长度也是 N,如图 3-5-10c所示数字信号处理 第 3章? 2004
而 是无限长的，需截取。
但因只需要计算 V(n)在 [0,M-1]上 M个值
（ 1）
（ 2）
)0()()0(
1
0
mhmyV
N
m
)1()()1(
1
0
mMhmyMV
N
m
当 m由 0变到 N-1时,由 （ 1） 式知,m取最负的值
-(N-1),由 （ 2） 式知,m取最正的值 (M-1)。 可见,
为了计算出 V(n) 在区间 [0,M-1]上的 M个值,只要截取 h(n)在区间 [-(N-1),(M-1)]上的 (N+M-1)个值 。 如图
(b)所示 。 这时经线性卷积所得 V(n) 的非零值区间为
[-(N-1),(N+M-2)]。 长度为 2N+M-2。
h n e j n( ) ( / ) 2 02?
数字信号处理 第 3章? 2004
其次要确定循环卷积计算线性卷积时的
FFT长度 L,由
y n h n V n qL R n
q
L( ) ( ) ( ) ( )
为了用循环卷积代替线性卷积计算出 V(n)
在 [0,(M-1)]区间上的 M个序列值,要保证在上式中的周期延拓中,在 [0,M-1]区间上不能有混叠,循环卷积区间长度 L应大于或等于 N+M-1。 故在用基 -2 FFT算法进行快速卷积计算时,应选择 L≥ (N+M-1)
且满足 (m为自然数 )的最小值L m? 2
数字信号处理 第 3章? 2004
若选择 L=N+M-1,那么 y(n)尾部应补
M-1个零 。 并将 h(n)从 -(N-1)到 (M-1)所截取的一段 序列以 L为周期进行周期延拓,取主值序列形成,这时可以用快速卷积法计算如上构造的两个序列 y(n)和 的循环卷积 。h nL( )
)(ny
h nL( )
数字信号处理 第 3章? 2004
注意,
当选择 >N+M-1时,y(n)应补 L-N个零点,而 h(n)从区间 [(-N+1),(M-1)]截取后在 -N+1点前面补 L-(N+M-1)个零点后,以 L
为周期进行周期延拓 。 或直接截取 [-（ L-
M）,（ M-1） ]上的值后,再以 L为周期进行周期延拓取主值 。
L m? 2
数字信号处理 第 3章? 2004
具体步骤如下：
1.形成 序列
2.计算 FFT
h nL( )
h n W n M
W M n LL
n
n L
( )
/
( ) /
2
2
2
2
0 1
1
H k FFT h n k LL( ) [ ( )]0 1
数字信号处理 第 3章? 2004
3.做序列
4.计算 FFT
5.计算 IFFT
6.最后求得乘积
y n x n A W n N
N n L
n n
( ) ( )
/
2 2 0 1
0 1
Y k FFT y n k L( ) [ ( )]0 1
V n I F F T Y k H k n L( ) [ ( ) ( )]0 1
X z W V k k Mk k( ) ( )/2 2 0 1
