第 4章 快速傅里叶变换 (FFT)
第 4章 快速傅里叶变换 (FFT)
4.1 引言
4.2 基 2FFT算法
4.3 进一步减少运算量的措施
4.4 分裂基 FFT算法
4.5 离散哈特莱变换 (DHT)
第 4章 快速傅里叶变换 (FFT)
4.1 引言
DFT是信号分析与处理中的一种重要变换 。 因直
接计算 DFT的计算量与变换区间长度 N的平方成正比,
当 N较大时, 计算量太大, 所以在快速傅里叶变换 (简
称 FFT)出现以前, 直接用 DFT算法进行谱分析和信号
的实时处理是不切实际的 。 直到 1965年发现了 DFT的
一种快速算法以后, 情况才发生了根本的变化 。
第 4章 快速傅里叶变换 (FFT)
4.2 基 2FFT算法
4.2.1 直接计算 DFT的特点及减少运算量的基本途径
长度为 N的有限长序列 x(n)的 DFT为
考虑 x(n)为复数序列的一般情况, 对某一个 k值,
直接按 (4.2.1)式计算 X(k)值需要 N次复数乘法, (N-1)次
复数加法 。
1
0
( ) ( ),0,1,,1
N
kn
N
n
X k x n W k N
?
?
? ? ? ? ? ??
(4.2.1)
第 4章 快速傅里叶变换 (FFT)
如前所述, N点 DFT的复乘次数等于 N2。 显然,
把 N点 DFT分解为几个较短的 DFT,可使乘法次数大大
减少 。 另外, 旋转因子 WmN具有明显的周期性和对称
性 。 其周期性表现为
22()j m l N j m
m l N mNN
NNW e e W
??? ? ?
? ? ? ?
(4.2.2)
其对称性表现为
2
[]m N m N m mN N N N
Nm
m
NN
W W W W
WW
? ? ? ?
?
??
??
或者
第 4章 快速傅里叶变换 (FFT)
4.2.2 时域抽取法基 2FFT基本原理
FFT 算法基本上分为两大类：时域抽取法
FFT(Decimation In Time FFT,简称 DIT-FFT)和频域抽取
法 FFT(Decimation In Frequency FFT,简称 DIF―FFT) 。
下面先介绍 DIF―FFT 算法 。
设序列 x(n)的长度为 N,且满足
2,MNM? 为自然数
按 n的奇偶把 x(n)分解为两个 N/2点的子序列
1
2
( ) ( 2 ),0,1,1
2
( ) ( 2 1 ),0,1,1
2
N
x r x r r
N
x r x r r
? ? ? ? ? ?
? ? ? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
则 x(n)的 DFT为
/ 2 1 / 2 1
2 ( 2 1 )
00
/ 2 1 / 2 1
2
12
00
( ) ( ) ( )
( 2 ) ( 2 1 )
( ) ( )
k n k n
NN
nn
NN
k r k r
NN
rr
NN
k k r
NN
rr
X k x n W x n W
x r W x r W
x r W x r W
??
??
?
??
??
??
??
? ? ?
??
??
??
??
由于
2
2 2
22 2
/2
j k rN
j k rk r k rN
NNW e e W
?
? ??
? ? ?
所以
/ 2 1 / 2 1
1 / 2 2 / 2 1 2
00
( ) ( ) ( ) ( ) ( )
NN
kr k kr k
N N N N
rr
X k x r W W x r W X k W X k
??
??
? ? ? ???
第 4章 快速傅里叶变换 (FFT)
其中 X1(k)和 X2(k)分别为 x1(r)和 x2(r)的 N/2点 DFT，
即
/ 2 1
1 1 / 2 1
0
/ 2 1
2 2 / 2 2
0
( ) ( ) [ ( ) ]
( ) ( ) [ ( ) ]
N
kr
N
r
N
kr
N
r
X k x r W D F T x r
X k x r W D F T x r
?
?
?
?
??
??
?
?
(4.2.5)
(4.2.6)
由于 X1(k)和 X2(k)均以 N/2为周期, 且
, 所以 X(k)又可表示为
2
Nk k
NNWW
? ??
12
12
( ) ( ) ( ) 0,1,1
2
( ) ( ) ( ) 0,1,1
22
k
N
k
N
N
X k X k W X k k
NN
X k X k W X k k
? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
(4.2.7)
(4.2.8)
第 4章 快速傅里叶变换 (FFT)
图 4.2.1 蝶形运算符号
C
A
B
A ＋ BC
A － BC
第 4章 快速傅里叶变换 (FFT)
图 4.2.2 N点 DFT的一次时域抽取分解图 (N=8)
N /2 点
D F T
W N
0
N /2 点
D F T
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 )
第 4章 快速傅里叶变换 (FFT)
与第一次分解相同, 将 x1(r)按奇偶分解成两个 N/4
长的子序列 x3(l)和 x4(l),即
32
41
( ) ( 2 ),0,1,,1
( ) ( 2 1 ) 4
x l x l Nl
x l x l
? ? ? ? ? ? ?
???
?
那么,X1(k)又可表示为 / 4 1 / 4 1
2 ( 2 1 )
1 1 / 2 1 / 2
00
/ 4 1 / 4 1
3 / 4 / 2 4 / 4
00
3 / 2 4
( ) ( 2 ) ( 2 1 )
( ) ( )
( ) ( ),0,1,/ 2 1
NN
k l k l
NN
ii
NN
k l k k l
N N N
ii
k
N
X k x l W x l W
x l W W x l W
x k W X k k N
??
?
??
??
??
? ? ?
??
? ? ? ? ? ? ?
??
??
(4.2.9)
第 4章 快速傅里叶变换 (FFT)
式中 / 4 1
3 3 / 4 3
0
/ 4 1
4 4 / 4 4
0
( ) ( ) [ ( ) ]
( ) ( ) [ ( ) ]
N
kl
N
i
N
kl
N
i
x k x l W D F T x l
x k x l W D F T x l
?
?
?
?
??
??
?
?
同理, 由 X3(k)和 X4(k)的周期性和 Wm N/2的对称
性 Wk+N/4 N/2=-Wk N/2 最后得到,
1 3 / 2 4
1 3 / 2 4
( ) ( ) ( ),0,1,,/ 4 1
( / 4) ( ) ( )
k
N
k
N
X k X k W X k kN
X k N X k W X k
??? ? ? ? ? ? ?
?? ? ? ?
?
(4.2.10)
第 4章 快速傅里叶变换 (FFT)
用同样的方法可计算出
2 5 / 2 6
2 5 / 2 6
( ) ( ) ( ),0,1,/ 4 1
( / 4 ) ( )
k
N
k
N
X k X k W X k kN
X k N X k W X k
??? ?
? ? ? ? ??
? ? ? ??
(4.2.11)
其中
/ 4 1
5 5 / 4 5
0
/ 4 1
6 6 / 4 6
0
52
62
( ) ( ) [ ( ) ]
( ) ( ) [ ( ) ]
( ) ( 2 )
,0,1,/ 4 1
( ) ( 2 1 )
N
kl
N
i
N
kl
N
i
X k x l W DF T x l
X k x l W DF T x l
x l x l
lN
x l x l
?
?
?
?
??
??
? ?
? ? ? ? ??
?? ?
?
?
第 4章 快速傅里叶变换 (FFT)
图 4.2.3 N点 DFT的第二次时域抽取分解图 (N=8)
N /4 点
D F T
W
N
1
2
W
N
1
2
W N
0
W N
1
W N
2
W N
3
X
1
( 0 )
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 )
x ( 0 )
X
3
( 0 )
X
3
( 1 )
X
4
( 0 )
X
4
( 1 )
x ( 4 )
x ( 2 )
x ( 6 )
x ( 1 )
x ( 5 )
x ( 3 )
x ( 7 )
N /4 点
D F T
N /4 点
D F T
N /4 点
D F T
W
N
0
2
W
N
0
2
第 4章 快速傅里叶变换 (FFT)
图 4.2.4 N点 DIT―FFT 运算流图 (N=8)
W N
0
W N
1
W N
2
W N
3
W N
0
W N
2
W N
0
W N
2
W N
0
W N
0
W N
0
W N
0
x ( 0 )
x ( 4 )
x ( 2 )
x ( 6 )
x ( 1 )
x ( 5 )
x ( 3 )
x ( 7 )
A ( 0 )
A ( 1 )
A ( 2 )
A ( 3 )
A ( 4 )
A ( 5 )
A ( 6 )
A ( 7 )
A ( 0 )
A ( 1 )
A ( 2 )
A ( 3 )
A ( 4 )
A ( 5 )
A ( 6 )
A ( 7 )
A ( 0 )
A ( 7 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
A ( 0 )
A ( 1 )
A ( 2 )
A ( 3 )
A ( 4 )
A ( 5 )
A ( 6 )
A ( 7 )
第 4章 快速傅里叶变换 (FFT)
4.2.3 DIT―FFT 算法与直接计算 DFT运算量的比较
每一级运算都需要 N/2次复数乘和 N次复数加 (每个
蝶形需要两次复数加法 )。 所以, M级运算总共需要的
复数乘次数为
2
2
( 2 ) lo g
22
( 2 ) lo g
M
A
NN
C M N
C N M N N
? ? ?
? ? ?
复数加次数为
例如, N=210=1024时
2
2
1048576 2 0 4, 8
( / 2) l o g 5 1 2 0
N
NN ??
第 4章 快速傅里叶变换 (FFT)
图 4.2.5 FFT算法与直接计算 DFT所需乘法次数的比较曲线
第 4章 快速傅里叶变换 (FFT)
4.2.4 DIT―FFT 的运算规律及编程思想
1.原位计算
由图 4.2.4可以看出, DIT―FFT 的运算过程很有规
律 。 N=2M点的 FFT共进行 M级运算, 每级由 N/2个蝶
形运算组成 。
2.旋转因子的变化规律
如上所述, N点 DIT―FFT 运算流图中, 每级都有
N/2个蝶形 。 每个蝶形都要乘以因子 WpN,称其为旋转
因子, p称为旋转因子的指数 。
第 4章 快速傅里叶变换 (FFT)
观察图 4.2.4不难发现, 第 L级共有 2 L-1个不同的旋
转因子 。 N=23=8时的各级旋转因子表示如下,
L=1时, WpN=WJ N/4=WJ2L,J=0
L=2时, WpN =WJ N/2=WJ2L,J=0,1
L=3时, WpN =WJN=WJ2L,J=0,1,2,3
对 N=2M的一般情况, 第 L级的旋转因子为
1
2
21
2
,0,1,2,,2 1
2 2 2 2
,0,1,2,,2 1
2
ML
LM
p J L
N
L M L M L M
P J J L
NN N
ML
W W L J
N
W W W J
pJ
?
?
?
??
?
?
? ? ? ? ? ?
? ? ? ?
? ? ? ? ? ? ?
?
g
g
g
(4.2.12)
(4.2.13)
第 4章 快速傅里叶变换 (FFT)
3,蝶形运算规律
设序列 x(n)经时域抽选 (倒序 )后, 存入数组 X中 。
如果蝶形运算的两个输入数据相距 B个点, 应用原位计
算, 则蝶形运算可表示成如下形式,
X (J) XL-1(J)+X L-1(J+B)WpN
XL(J+B) XL-1(J)-X L-1(J+B)WpN
式中 p=J·2 M-L； J=0,1,…,2 L-1-1； L=1,2,…,M
?
?
第 4章 快速傅里叶变换 (FFT)
下标 L表示第 L级运算, XL(J)则表示第 L级运算后
数组元素 X(J)的值 。 如果要用实数运算完成上述蝶形
运算, 可按下面的算法进行 。
设
T=X L-1(J+B)WpN=TR+jTI
X L-1(J)=X′R(J)+jX′I(J)
式中下标 R表示取实部, I表示取虚部,
22
( ) c o s ( ) s in
22
( ) c o s ( ) s in
R R R I
I I R I
T X J B p X J B p
NN
T X J B p X J B p
NN
??
??
??? ? ? ?
??? ? ? ?
第 4章 快速傅里叶变换 (FFT) ( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
LR
R R R
I I I
R R R
I I I
X J X J j J
X J X J T
X J X J T
X J B X J T
X J B X J T
??
???
???
?? ? ?
?? ? ?
则
第 4章 快速傅里叶变换 (FFT)
4,编程思想及程序框图
图 4.2.6 DIT―FFT 运算和程序框图
开 始
送入 x ( n ), M
N ＝ 2
M
倒 序
L ＝ 1,M
Ｊ ＝ 0,B － 1
P ＝ 2
M － L
J
k ＝ J,N － 1,2
L
p
N
p
N
WBkXkXBkX
WBkXkXkX
)()()(
)()()(
????
???
输 出
结 束
B 2
L － 1
第 4章 快速傅里叶变换 (FFT)
5,序列的倒序
DIT―FFT 算法的输入序列的排序看起来似乎很乱,
但仔细分析就会发现这种倒序是很有规律的 。 由于
N=2M,所以顺序数可用 M位二进制数 (nM-1nM-2…n1n0)
表示 。
图 4.2.7 形成倒序的树状图 (N=23)
0
1
0
1
0
1
0
1
0
1
0
1
0
1
( n
2
n
1
n
0
)
2
0 0 0 0
4
2
6
1
5
3
7
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
0 1 1
1 1 1
第 4章 快速傅里叶变换 (FFT)
表 4.2.1 顺序和倒序二进制数对照表
第 4章 快速傅里叶变换 (FFT)
图 4.2.8 倒序规律
x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 )
A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 )
A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 )
x ( 0 ) x ( 4 ) x ( 2 ) x ( 6 ) x ( 1 ) x ( 5 ) x ( 3 ) x ( 7 )
第 4章 快速傅里叶变换 (FFT)
图 4.2.9 倒序程序框图
2
2
1
??
?
?
NN
LHJ
NLH
I ＝ 1,N
1
I ≥ J
TJA
JXIA
IXT
?
?
?
)(
)()(
)(
J ＜ K
LHK ?
KJJ ??
2KK
KJJ
?
??
Ｙ
N
N
Y
第 4章 快速傅里叶变换 (FFT)
4.2.5 频域抽取法 FFT(DIF―FFT)
在基 2快速算法中, 频域抽取法 FFT也是一种常用
的快速算法, 简称 DIF―FFT 。
设序列 x(n)长度为 N=2M,首先将 x(n)前后对半分
开, 得到两个子序列, 其 DFT可表示为如下形式,
1
0
/ 2 1 1
0 / 2
/ 2 1 / 2 1
( / 2 )
00
/ 2 1
/2
0
( ) [ ( ) ] ( )
( ) ( )
( ) ( )
2
[ ( ) ( ) ]
2
N
k
N
n
NN
k n k n
NN
n n N
NN
k n k n N
NN
nn
N
k N k n
NN
n
X k DFT x n x n W
x n W x n W
N
x n W x n W
N
x n W x n W
?
?
??
??
??
?
??
?
?
??
??
? ? ?
? ? ?
?
??
??
?
第 4章 快速傅里叶变换 (FFT)
/2 1,( 1 )
1
k N k
N
k
W
k
???
? ? ? ?
????
偶数
奇数
将 X(k)分解成偶数组与奇数组，当 k取偶数
(k=2r,r=0,1,…,N/2 -1)时
/ 2 1
2
0
/ 2 1
2
/2
0
( 2 ) [ ( ) ( )]
2
[ ( ) ( )]
2
N
rn
N
n
N
rn
N
n
N
X r x n x n W
N
x n x n W
?
?
?
?
? ? ?
? ? ?
?
? (4.2.14)
第 4章 快速傅里叶变换 (FFT)
当 k取奇数 (k=2r+1,r=0,1,…,N/2-1)时
/ 2 1
( 2 1 )
0
/ 2 1
/2
0
( 2 1 ) [ ( ) ( ) ]
2
[ ( ) ( ) ]
2
N
nr
N
n
N
n n r
NN
n
N
X r x n x n W
N
x n x n W W
?
?
?
?
?
? ? ? ?
? ? ?
?
? g(4.2.15)
将 x1(n)和 x2(n)分别代入 (4.2.14)和 (4.2.15)式, 可得
/ 2 1
1 / 2
0
/ 2 1
2 / 2
0
( 2 ) ( )
( 2 1 ) ( )
N
rn
N
n
N
rn
N
n
X r x n W
X r x n W
?
?
?
?
?
??
?
?
? ??
??
?
?
(4.2.16)
第 4章 快速傅里叶变换 (FFT)
图 4.2.10 DIF―FFT 蝶形运算流图符号
第 4章 快速傅里叶变换 (FFT)
图 4.2.11 DIF―FFT 一次分解运算流图 (N=8)
N /2 点
D F T
W N
0
N /2 点
D F T
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 )
第 4章 快速傅里叶变换 (FFT)
图 4.2.12 DIF―FFT 二次分解运算流图 (N=8)
N /4 点
D F T
W N
0
W N
1
W N
2
W N
3
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
X ( 0 )
X ( 4 )
X ( 2 )
X ( 6 )
X ( 1 )
X ( 5 )
X ( 3 )
X ( 7 )
W N
0
W N
2
W N
0
W N
2
N /4 点
D F T
N /4 点
D F T
N /4 点
D F T
第 4章 快速傅里叶变换 (FFT)
图 4.2.13 DIF―FFT 运算流图 (N=8)
W N
0
W N
1
W N
2
W N
3
W N
0
W N
2
W N
0
W N
2
W N
0
W N
0
W N
0
W N
0
X ( 0 )
X ( 4 )
X ( 2 )
X ( 6 )
X ( 1 )
X ( 5 )
X ( 3 )
X ( 7 )
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
第 4章 快速傅里叶变换 (FFT)
图 4.2.14 DIT―FFT 的一种变形运算流图
W N
0
W N
0
W N
2
W N
0
X ( 0 )
X ( 4 )
X ( 2 )
X ( 6 )
X ( 1 )
X ( 5 )
X ( 3 )
X ( 7 )
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
W N
0
W N
2
W N
1
W N
3W N
2
W N
0
W N
0
W N
0
第 4章 快速傅里叶变换 (FFT)
图 4.2.15 DIT―FFT 的一种变形运算流图
W N
0
W N
0
W N
2
W N
0
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
W N
0
W N
2
W N
1
W N
3
W N
2
W N
0
W N
0
W N
0
第 4章 快速傅里叶变换 (FFT)
4.2.6 IDFT的高效算法
上述 FFT算法流图也可以用于离散傅里叶逆变换
(Inverse Discrete Fourier Transform,简称 IDFT)。 比较
DFT和 IDFT的运算公式,
1
0
1
0
( ) [ ( )] ( )
1
( ) [ ( )] ( )
N
k
N
n
N
kn
N
k
X k D F T x n x n W
x n ID F T x n X k W
N
?
?
?
?
?
??
??
?
?
第 4章 快速傅里叶变换 (FFT)
图 4.2.16 DIT―IFFT 运算流图
W N
0
W N
1?
W N
2?
W N
3?
W N
0
W N
0
N1
x ( 0 )
x ( 4 )
x ( 2 )
x ( 6 )
x ( 4 )
x ( 5 )
x ( 3 )
x ( 7 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
W N
2?
W N
2?
N1
N1
N1
N1
N1
N1
N1
第 4章 快速傅里叶变换 (FFT)
图 4.2.17 DIT―IFFT 运算流图 (防止溢出 )
W
N
0
2
1
21 x ( 0 )
x ( 4 )
x ( 2 )
x ( 6 )
x ( 1 )
x ( 5 )
x ( 3 )
x ( 7 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
21
21
21
W
N
1
2
1
?
W
N
2
2
1
?
W
N
3
2
1
?
21
21
W
N
0
2
1
W
N
2
2
1
?
21
21
W
N
0
2
1
W
N
2
2
1
?
21
W
N
0
2
1
21
W
N
0
2
1
21
21
W
N
0
2
1
W
N
0
2
1
第 4章 快速傅里叶变换 (FFT)
如果希望直接调用 FFT子程序计算 IFFT,则可用下
面的方法,
由于
1
0
1
0
1
( ) ( )
1
( ) ( )
N
kn
N
k
N
kn
N
k
x n X k W
N
x n X k W
N
?
?
?
?
??
?
?
?
?
?
对上式两边同时取共轭, 得
? ?1
0
11( ) [ ( ) ] [ ( )]N kn
N
k
x n X k W D F T X kNN
? ?
? ? ?
?
???
第 4章 快速傅里叶变换 (FFT)
4.3 进一步减少运算量的措施
4.3.1 多类蝶形单元运算
由 DIT―FFT 运算流图已得出结论, N=2M点 FFT共
需要 MN/2次复数乘法 。
由 (4.2.12) 式, 当 L=1 时, 只有一种旋转因子
W0N=1,所以, 第一级不需要乘法运算 。
第 4章 快速傅里叶变换 (FFT)
综上所述, 先除去第一, 二两级后, 所需复数乘法
次数应是
从 L=3至 L=M共减少复数乘法次数为
( 2 ) ( 2 )2M NCM??
(4.3.1)
1
33
12 ( ) 2
2 2 2
MM
L
L
LL
NNN
?
??
? ? ???
(4.3.2)
因此,DIT―FFT 的复乘次数降至
( 2 ) ( 2 ) ( 2 ) ( 3 ) 22 2 2M N N NC M M? ? ? ? ? ? ?
(4.3.3)
第 4章 快速傅里叶变换 (FFT)
22
( 1 ) ( ) ( )
22
2
[ ( ) ( ) ]
2
2
()
2
22
( ) ( )
22
def
j x jy x jy jx y
x y j x y
R jI
R x y
I x y y x
? ? ? ? ? ?
? ? ? ?
??
??
? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
从实数运算考虑, 计算 N=2M点 DIT―FFT 所需实数
乘法次数为
( 2 ) 4 [ ( 3 ) 2 ] ( 2 )
22
13
( 2 ) 1 0
2
M
NN
RM
NM
? ? ? ? ?
? ? ?(4.3.4)
第 4章 快速傅里叶变换 (FFT)
4.3.2 旋转因子的生成
在 FFT运算中，旋转因子 WmN=cos(2πm/N)-
jsin(2πm/N)，求正弦和余弦函数值的计算量是很大的。
第 4章 快速傅里叶变换 (FFT)
4.3.3 实序列的 FFT算法
设 x(n)为 N点实序列, 取 x(n)的偶数点和奇数点分
别作为新构造序列 y(n)的实部和虚部, 即
12
12
( ) ( 2 ),( ) ( 2 1 ),0,1,,1
2
( ) ( ) ( ),0,1,,1
2
N
x n x n x n x n n
N
y n x n j x n n
? ? ? ? ? ? ? ?
? ? ? ? ? ? ?
对 y(n)进行 N/2点 FFT,输出 Y(k),则
11
22
( ) [ ( )] ( )
,0,1,,1( ) [ ( )] ( ) 2ep
op
X k D F T x n Y k N
kX k D F T x n j Y k
?? ??
? ? ? ? ??? ? ?
??
根据 DIT―FFT 的思想及式 (4.2.7)和 (4.2.8)，可得到
12( ) ( ) ( ),0,1,2
k
N
NX k X k W X k k? ? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
由于 x(n)为实序列，所以 X(k)具有共轭对称性，
X(k)的另外 N/2点的值为
( ) ( ),1,2,,12NX N k X k k?? ? ? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
4.4 分裂基 FFT算法
4.4.1 分裂基 FFT算法原理
当 n=pq,且 p=N/4,q=4时, n可表示为
1 0 1 0 1 0,0 3,0 144
NNn p n n n n n n? ? ? ? ? ? ? ? ?
并有
10
1
1
0
/ 4 1 3
()
4
10
00
( ) ( )
()
4
N
kn
N
n
NN
k n n
N
nn
X k x n W
N
x n n W
?
?
?
?
??
?
??
?
??
第 4章 快速傅里叶变换 (FFT)
0 1
01
0
0
/ 4 1 3
1 0 4
/ 4 1
02
4 0 4 0 4
0
33
04
( ) ]
4
[ ( ) ( ) ( )
42
3
( ) ]
4
N
kn kn
N
nn
N
kk
n
knkk
NN
N
W x n n W
NN
x n W x n W x n W
N
x n W W W
?
?
?
??
? ? ? ? ?
??
??
?
再将上式中的 k表示为
1 0 1 04,0 1,0 34
Nk k k k k? ? ? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
可得
10
0
1 0 1 0 1 0 0
00
0
0 1 0 0
10
/ 4 1
( 4 )
0 0 4
0
8 2 3 ( 4 ) ( 4 )
0 4 0 4
/ 4 1
2
0 0 4 0 4
0
3 ( 4 )
04
( ) ( 4 )
[ ( ) ( )
4
3
( ) ( ) ]
24
[ ( ) ( ( ) ( )
42
3
( ) ]
4
N
kk
n
k k k k k n
N
N
kk
n
k k k n
N
X k X k k
N
x n x n W
NN
x n W x n W W
NN
x n x n W x n W
N
x n W W
?
?
?
? ? ?
?
?
?
??
? ? ?
? ? ? ?
? ? ? ? ?
??
?
?
对 k0=0,1,2,3,并用 k表示 k1,用 n表示 n0,可以
写出
第 4章 快速傅里叶变换 (FFT)
/ 4 1
4
0
/ 4 1
4
0
/ 4 1
42
0
3
( 4 ) [ ( ) ( ) ( ) ( ) ]
4 2 4
3
( 4 1 ) [ ( ) ( ) ( ) ( ) ]
4 2 4
3
( 4 2 ) [ ( ) ( ) ( ) ( ) ]
4 2 4
( 4 3 ) [ ( ) ( ) ( ) (
42
N
kn
N
n
N
k n n
N
n
N
k n n
N
n
N N N
X k x n x n x n x n W
N N N
X k x n jx n x n jx n W
N N N
X k x n x n x n x n W
NN
X k x n jx n x n jx n
?
?
?
?
?
?
?
?
? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
?
?
?
/ 4 1
43
0
3
)]
4
01
4
N
k n n
N
n
N
W
N
k
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
? ? ?
?
??
?
(4.4.1)
第 4章 快速傅里叶变换 (FFT)
/ 2 1
2
0
/ 4 1
4
0
/ 4 1
34
0
( 2 ) [ ( ) ( ) ],0 1
22
3
( 4 1 ) [ ( ) ( ) ( ) ( ) ]
4 2 4
01
4
3
( 4 3 ) [ ( ) ( ) ( ) ( ) ]
4 2 4
01
4
N
kn
N
n
N
n k n
NN
n
N
n k n
NN
n
NN
X k x n x n W k
N N N
X k x n jx n x n jx n W W
N
k
N N N
X k x n jx n x n jx n W W
N
k
?
?
?
?
?
?
?
? ? ? ? ? ?
?
?
? ? ?
? ? ? ? ? ? ? ???
?
??
?
??
? ? ??
?
? ? ?
? ? ? ? ? ? ? ???
??
? ? ?
?
?
?
??
?
?
?
? (4.4.2)
第 4章 快速傅里叶变换 (FFT)
2
1
4
23
4
( ) ( ) ( ),0 1
22
3
( ) [ ( ) ( ) ( ) ( )]
4 2 4
3
( ) [ ( ) ( ) ( ) ( )]
4 2 4
01
4
n
N
n
N
NN
x n x n x n n
N N N
x n x n j x n x n j x n W
N N N
x n x n j x n x n j x n W
N
n
?
? ? ? ? ? ?
?
?
?
? ? ? ? ? ? ?
?
?
? ? ? ? ? ? ? ?
?
?
? ? ??
?
(4.4.3)
令
第 4章 快速傅里叶变换 (FFT)
则 (4.4.2)式可写成如下更简明的形式,
/ 2 1
2
22
0
/ 4 1
1 4 1
44
0
/ 4 1
2 4 2
44
0
( 2 ) ( ) [ ( ) ],0 1
2
( 4 1 ) ( ) [ ( ) ],0 1
4
( 4 3 ) ( ) [ ( ) ],0 1
4
N
kn
N
n
N
kn
N
n
N
kn
N
n
N
X k x n W D F T x n k
N
X k x n W D F T x n k
N
X k x n W D F T x n k
?
?
?
?
?
?
?
? ? ? ? ?
?
?
?
? ? ? ? ? ??
?
?
? ? ? ? ? ??
?
?
?
?
(4.4.4)
第 4章 快速傅里叶变换 (FFT)
图 4.4.1 分裂基第一次分解 L形流图
点
D F T
…
…
…
…
点
D F T
点
D F T
…
…
…
…
…
…
…
…
…
…
x
2
( 1 )
x
2
(1 ＋ N / 4 )
2
N
4
N
4
N
)1(
1
4
x
)1(
2
4
x
1
N
W
3
N
W
x ( 1 )
?
?
?
?
?
?
?
4
1
N
x
?
?
?
?
?
?
?
2
1
N
x
?
?
?
?
?
?
?
4
3
1
N
x
－ 1
－ 1 － 1－ j
第 4章 快速傅里叶变换 (FFT)
例如, N=16,第一次抽选分解时, 由式 (4.4.3)得
x2(n)=x(n)+x(n+8),0≤n≤7
x14(n)={［ x(n)-x(n+8)］ -j［ x(n+4)-x(n+12)］ }Wn16,
0≤n≤3
x24(n)={［ x(n)-x(n+8)］ +j［ x(n+4)-x(n+12)］ }W3n16,
0≤n≤3
把上式代入式 (4.4.4),可得
X(2k)=DFT［ x2(n)］,0≤k≤7
X(4k+1)=DFT［ x14(n)］,0≤k≤3
X(4k+3)=DFT［ x24(n)］,0≤k≤3
第 4章 快速傅里叶变换 (FFT)
图 4.4.2 分裂基 FFT算法 L形排列示意图与结构示意图
(a)分裂基 FFT算法 L形排列示意图；
(b)分裂基 FFT算法运算流图结构示意图
( a ) ( b )
第 4章 快速傅里叶变换 (FFT)
图 4.4.3 16点分裂基第一次分解 L形流图 (图中省去箭头 )
( 8 )
点
D F T
x
2
( 0 )
x
2
( 1 )
x
2
( 2 )
x
2
( 3 )
x
2
( 4 )
x
2
( 5 )
x
2
( 6 )
x
2
( 7 )
点
D F T
点
D F T
)0(
1
4
x
)1(
1
4
x
)2(
1
4
x
)3(
1
4
x
)0(
2
4
x
)1(
2
4
x
)2(
2
4
x
)3(
2
4
x
4
4
?
N
4
4
?
N
2
N
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
x ( 8 )
x ( 9 )
x ( 1 0 )
x ( 1 1 )
x ( 1 2 )
x ( 1 3 )
x ( 1 4 )
x ( 1 5 )
0
N
W
1
N
W
3
N
W
2
N
W
0
N
W
3
N
W
6
N
W
－ j
－ j
－ j
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
X ( 8 )
X ( 9 )
X ( 1 0 )
X ( 1 1 )
X ( 1 2 )
X ( 1 3 )
X ( 1 4 )
X ( 1 5 )
X (2 k )
X (4 k ＋ 1)
X (4 k ＋ 3)
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
第 4章 快速傅里叶变换 (FFT)
第二次分解,
先对图 4.4.3中 N/2点 DFT进行分解 。
令 X1(l)=X(2l),则有
X1(2l)=DFT［ y2(n)］,0≤l≤3
X1(4l+1)=DFT［ y14(n)］,0≤l≤1
X1(4l+3)=DFT［ y24(n)］,0≤l≤1
第 4章 快速傅里叶变换 (FFT)
其中
y2(n)=x2(n)+x2(n+4),0≤n≤3
y14(n)={［ x2(n)-x2(n+4)］ -［ x2(n+2)x(n+6)］ }Wn8,n=0,1
y24(n)={［ x2(n)-x2(n+4)］ +j［ x2(n+2)x2(n+6)］ }W3n8,n=0,1
第 4章 快速傅里叶变换 (FFT)
图 4.4.4 图 4.4.4中 N/2点 DFT的分解 L形流图
( 4 )
点
D F T
x
2
( 0 )
x
2
( 1 )
x
2
( 2 )
x
2
( 3 )
x
2
( 4 )
x
2
( 5 )
x
2
( 6 )
x
2
( 7 )
y
2
( 0 )
y
2
( 1 )
y
2
( 2 )
y
2
( 3 )
X
1
( 0 ) ＝ X ( 0 )
X
1
( 2 ) ＝ X ( 4 )
X
1
( 4 ) ＝ X ( 8 )
X
1
( 6 ) ＝ X ( 1 2 )
X
1
( 1 ) ＝ X ( 2 )
X
1
( 5 ) ＝ X ( 1 0 )
X
1
( 3 ) ＝ X ( 6 )
X
1
( 7 ) ＝ X ( 1 4 )
X
1
(2 l )
X
1
(4 l ＋ 1 )
X
1
(4 l ＋ 3 )
4N
)0(
1
4
y
)1(
1
4
y
)1(
2
4
y
)0(
2
4
y
1
2N
W
3
2N
W
－ j
－ j
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
第 4章 快速傅里叶变换 (FFT)
图 4.4.5 4点分裂基 L形运算流图
v ( 0 )
v ( 1 )
v ( 2 )
v ( 3 )
V ( 0 )
V ( 2 )
V ( 1 )
V ( 3 )
－ j
－ 1
－ 1
－ 1
－ 1
第 4章 快速傅里叶变换 (FFT)
图 4.4.6 16点分裂基 FFT运算流图
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
x ( 8 )
x ( 9 )
x ( 1 0 )
x ( 1 1 )
x ( 1 2 )
x ( 1 3 )
x ( 1 4 )
x ( 1 5 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
X ( 8 )
X ( 9 )
X ( 1 0 )
X ( 1 1 )
X ( 1 2 )
X ( 1 3 )
X ( 1 4 )
X ( 1 5 )
－ j
－ 1
－ 1
－ 1
－ 1
－ j
－ j
－ 1
－ 1
－ 1
－ 1
－ j
－ j
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ j
－ j
－ j
－ j
W
1
W
2
W
3
W
3
W
6
W
9
W
2
W
6
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
N
N
N
N
N
N
N
N
第 4章 快速傅里叶变换 (FFT)
4.4.2 分裂基 FFT算法的运算量
设第 j级有 lj个 L形, j=1,2,…,M-1,M=log2N,则有
l1=N/4。 由图 4.4.2(b)可见, 第 j-1列中的 L形包含了第 j
列中的一部分结点的计算, 即空白部分, 所占结点数
刚好等于第 j-1列中所有 L形对应结点的一半, 所以第 j
列 L形个数就减少 l j-1/2个, 即
第 4章 快速傅里叶变换 (FFT)
1
1
1
2
2
3
1
0
42
4
1
( 1 )
4 2 4 2
11
( 1 )
4 2 4 2 4
1 1 1
( ) ( 1 ) ]
4 2 4 2 4
j
j
j
ij
j
i
lN
l
N
l
N l N
l
N l N
l
NN
l
?
?
?
??
?
? ? ? ?
? ? ? ? ?
? ? ? ? ??
第 4章 快速傅里叶变换 (FFT)
由于每个 L形有两次复 (数 )乘运算, 所以全部复
乘次数为
1
1
2
2 2 1
2 [ ( ) ]
3 3 3 2
1 2 2
lo g ( 1 )
3 9 9
M
M
Mj
j
M
N
C l M
N N N
?
?
? ? ? ? ?
? ? ? ?
?
(4.4.5)
第 4章 快速傅里叶变换 (FFT)
4.5 离散哈特莱变换 (DHT)
4.5.1 离散哈特莱变换定义
设 x(n),n=0,1,…,N-1,为一实序列, 其 DHT定义为
1
0
2( ) [ ( )] ( ) co s ( ),0,1,,1N
H
n
X k D H T x n x n kn k NN?
?
?
? ? ? ? ? ? ??
式中, cas(α)=cosα+sinα。 其逆变换 (IDHT)为
1
0
12( ) [ ( )] ( ) co s ( ),0,1,,1N
HH
k
x n ID H T X k X k kn n NNN ?
?
?
? ? ? ? ? ? ??
(4.5.3)
第 4章 快速傅里叶变换 (FFT)
逆变换证明如下,
1
0
1
0
1
0
1
0
22
c o s( ) c o s( )
2 2 2 2
[ c o s( ) si n( ) ] [ c o s( ) si n( ) ]
2 2 2 2
[ c o s( ) c o s( ) si n( ) si n( )
2 2 2 2
c o s( ) si n( ) si n( ) c o s( ) ]
22
[ c o s ( ) si n
N
k
N
k
N
k
N
k
k n k
NN
k n k n k k
N N N N
k n k k n k
N N N N
k n k k n k
N N N N
kn
N
??
?
? ? ? ?
??
? ? ? ?
??
? ? ? ?
??
?
?
?
?
?
?
?
?
?
?
? ? ?
??
??
? ? ?
?
?
?
? ( ) ]
,
0,
kn
N
Nn
n
?
?
?
?
?
??
?
?
?
?
?? (4.5.4)
第 4章 快速傅里叶变换 (FFT)
将式 (4.5.2)代入式 (4.5.3)得
11
00
11
00
1
0
1 2 2
( ) c o s( ) c o s( )
1 2 2
( ) c o s( ) c o s( )
,01
()
0,0
NN
k
NN
k
N
k
x k k n
N N N
x k n k
N N N
N
x
N
?
?
??
??
??
??
?
?
?
??
??
??
??
?
?
?
??
?
? ?
??
?
??
??
? g
第 4章 快速傅里叶变换 (FFT)
4.5.2 DHT与 DFT之间的关系
为了便于比较, 重写 DFT如下,
211
00
211
00
22
( ) [ ( ) ] ( ) ( ) [ c o s( ) sin( ) ]
1 1 2 2
( ) ( ) ( ) [ c o s( ) sin( ) ]
NN
j k n
N
nn
NN
j k n
N
kk
X k D FT x n x n e x n k n j k n
NN
x n X k e X k k n j k n
N N N N
?
?
??
??
??
?
??
??
??
? ? ? ?
? ? ?
??
??
(4.5.5)
(4.5.6)
容易看出,DHT的核函数
DFT的核函数
的实部与虚部之和。
2 2 2c o s( ) c o s( ) si n( )k n k n k n
N N N
? ? ???
2 22c o s ( ) ( )j kn
Ne k n j k nNN
? ????
第 4章 快速傅里叶变换 (FFT)
将 XH(k)分解为奇对称分量 XHo(k)与偶对称分量
XHe(k)之和
( ) ( ) ( )
1
( ) [ ( ) ( ) ]
2
1
( ) [ ( ) ( ) ]
2
H He Ho
He H H
Ho H H
X k X k X k
X k X k X N k
X k X k X N k
??
? ? ?
? ? ?
(4.5.7)
(4.5.8)
(4.5.9)
由 DHT定义有
1
0
1
0
2
( ) ( ) c o s ( )
2
( ) ( ) s i n ( )
N
He
n
N
Ho
n
X k x n k n
N
X k x n k n
N
?
?
?
?
?
?
?
?
?
?
(4.5.10a)
(4.5.10b)
第 4章 快速傅里叶变换 (FFT)
所以, x(n)的 DFT可表示为
同理, x(n)的 DHT可表示为
因此, 已知 x(n)的 DHT,则 DFT可用下式求得,
( ) ( ) ( )H e H oX k X k j X k?? (4.5.11)
( ) ( ) I m [ ( ) ]HeX k H k X k?? (4.5.12)
11( ) [ ( ) ( ) ] [ ( ) ( ) ]
22H H H HX k X k X N k j X k X N k? ? ? ? ? ?(4.5.13)
第 4章 快速傅里叶变换 (FFT)
4.5.3 DHT的主要优点
(1)DHT是实值变换, 在对实信号或实数据进行谱
分析时避免了复数运算, 从而提高了运算效率, 相应
的硬件也更简单, 更经济；
(2)DHT的正, 反变换 (除因子 1/N外 )具有相同的形
式, 因而, 实现 DHT的硬件或软件既能进行 DHT,也
能进行 IDHT；
(3)DHT与 DFT间的关系简单，容易实现两种谱之
间的相互转换。
第 4章 快速傅里叶变换 (FFT)
4.5.4 DHT的性质
1,线性性质
1 1 2 2
1 2 1 2
( ),( ) ( )
( ) ( ) ( ) ( )
HH
HH
x X k x n X k
a x n b x n a X k b X k
??
? ? ?(4.5.14)
2,x(N-n)的 DHT
( ) ( ),( ) ( )HHx n X k x N n X N n? ? ? ?
1
0
22( ) ( )[ co s ( ) s i n ( )],0,1,,1N
H
n
X N k x n kn kn k NNN??
?
?
? ? ? ? ? ? ? ??
(4.5.15)
其中, 当 k=0时, XH(N-k)=XH(N)=XH(0)。
第 4章 快速傅里叶变换 (FFT)
证明 由 DHT定义
1
0
1
0
1
0
2
[ ( ) ] ( ) c o s( )
2
( ) c o s( ( ) )
22
( ) [ c o s( ) si n( ) ]
N
n
N
n
N
n
DFT x N n x N n k n
N
x n k N n
N
x n k n k n
NN
?
?
??
?
?
?
?
?
?
? ? ?
??
??
?
?
?
而
1
0
1
0
2
( ) ( ) c o s ( ( ) )
22
( ) [ c o s ( ) s i n ( ) ] [ ( ) ]
N
H
n
N
n
X N k x n N k n
N
x n k n k n D F T x N n
NN
?
??
?
?
?
?
? ? ?
? ? ? ?
?
?
第 4章 快速傅里叶变换 (FFT)
3,循环移位性质
0 0 0
0 0 0
22
( ( ) ) ( ) ( ) c o s( ) ( ) si n( )
22
( ( ) ) ( ) ( ) c o s( ) ( ) si n( )
N N H
N N H
x n n R n X k k n H N k k n
NN
x n n R n X k k n H N k k n
NN
??
??
? ? ? ?
? ? ? ?
(4.5.16)
(4.5.17)
证明 由 DHT定义有
1
0
1
0
1
0
[ ( ) ( ) ]
2
( ( ) ) c o s( )
2
( ) c o s( ( ) )
2 2 2 2
( ) [ c o s( ) c o s( ) si n ( ) si n ( )
2 2 2 2
si n ( ) c o s( ) c o s( ) si n ( ) ]
o N N
N
oN
n
N
o
n
N
oo
n
oo
DH T x n n R n
x n n k n
N
x n k n n
N
x n k n k n k n k n
N N N N
k n k n k n k n
N N N N
?
?
? ? ? ?
? ? ? ?
?
?
?
?
?
?
?
??
??
??
??
?
?
?
第 4章 快速傅里叶变换 (FFT)
1
0
1
0
2 2 2
( ) [ c o s( ) si n( ) ] c o s( )
2 2 2
( ) [ c o s( ) si n( ) ] si n( )
22
( ) c o s( ) ( ) si n( )
N
o
n
N
o
n
H o H o
x n k n k n k n
N N N
x n k n k n k n
N N N
X k k n X N k k n
NN
? ? ?
? ? ?
??
?
?
?
?
??
??
? ? ?
?
?
第 4章 快速傅里叶变换 (FFT)
4,奇偶性
奇对称序列和偶对称序列的 DHT仍然是奇对称序
列或偶对称序列, 即 DHT不改变序列的奇偶性 。
5.循环卷积定理
1 1 2 2
1 2 2 1 2 1
1 2 1 2 1 2
( ) ( ),( ) ( )
( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( )
HH
H H e H H o
H H e H H o
x n X k x n X k
x n x n X k X k X N k X k
x n x n X k X k X N k X k
??
? ? ?
? ? ?
e
e
(4.5.18)
(4.5.19)
第 4章 快速傅里叶变换 (FFT)
证明 下面利用 DFT的循环卷积定理和 DHT与 DFT
之间的关系来证明
其中, X1(k)=DFT［ x1(n)］,X2(k)=DFT［ x2(n)］,
根据 DHT与 DFT之间的关系, 则有
1 2 1 2[ ( ) ( ) ] ( ) ( )D F T x n x n X k X k?eg
1 1 1
2 2 2
2 2 2
( ) ( ) ( )
( ) ( ) ( )
11
[ ( ) ( ) ] [ ( ) ]
22
H e H o
H e H o
H H H
X k X k jX k
X k X k jX k
X k X N k j X N k
??
??
? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
将上面两式代入式 (4.5.20)并整理后, 得
2 1 1 1 1
2 1 1 1 1
12
2 1 2 1
1
( ) ( ) [ ( ) ( ) ( ) ( ) ]
2
1
( ) [ ( ) ( ) ( ) ( ) ]
2
( ) [ ( ) ( ) ]
R e [ ( ) ] I m [ ( ) ]
( ) ( ) ( ) ( )
H He Ho He Ho
H He Ho He Ho
H
H He H Ho
X k X k X k X k j X k j X k
X N k X k X k j X k j X k
X k DF T x n x n
X k X k
X k X k X N k X k
? ? ? ?
? ? ? ? ?
?
??
? ? ?
e
所以式 (4.5.18)成立 。 同理可证明式 (4.5.19)亦成立 。
当 x1(n)或 x2(n)是偶对称序列时, 则由 DHT的奇偶性有
1 2 1 2( ) ( ) ( ) ( ) ( )H H Hx n x n X k X k X k??e
(4.5.21)
第 4章 快速傅里叶变换 (FFT)
4.5.5 DHT的快速算法 (FHT)
1.基 2DIT―FHT 算法及运算流图
仿照快速 DFT的分解方法，可通过时域抽取或频域
抽取的方式实现快速 DHT。
x(n)的 N=2M点 DHT如下式,
1
0
0
1
11
22
00
2
( ) ( ) c o s ( ),0 1
( ) ( 2 )
,0 1
( ) ( 2 1 ) 2
22
( ) ( 2 ) c o s ( 2 ) ( 2 1 ) c o s ( ( 2 1 ) )
N
H
n
NN
H
rr
X k x n k n k N
N
x r x r N
r
x r x r
X k x r r k x r r k
NN
?
??
?
?
??
??
? ? ? ?
? ?
? ? ??
??
?
? ? ? ?
?
??
对 x(n)进行奇偶抽取
(4.5.22)
(4.5.23)
第 4章 快速傅里叶变换 (FFT)
与 DFT的时域抽取分解比较,
不是 一个指数函数，所以处理要比 W(2r+1)kN麻烦一
些。 根据三角公式有
2c o s ( ( 2 1 ) )kr
N
? ?
11
22
01
00
1
2
1
0
c o s( ) c o s c o s c o s( ) si n
2 2 2
( ) ( ) c o s( ) c o s( ) ( ) c o s( )
/ 2 / 2
22
si n ( ) ( ) c o s( )
/2
H
rr
r
X k x r rk k x r rk
N N N
k x r rk
NN
??
?
? ? ? ? ? ?
? ? ?
??
??
??
?
?
? ? ? ? ?
??
??
??
?
(4.5.24)
(4.5.25)
第 4章 快速傅里叶变换 (FFT)
令 X0H(k)=DHT［ x0(n)］,X1H(k)=DHT［ x1(n)］, 并
考虑 DHT的周期性, (4.5.25)式可写成
0 1 1
22( ) ( ) c o s( ) ( ) si n( ) ( )
2H H H H
NX k X k k X k k X k
NN
??? ? ? ?
为了使以下推导中公式简明，记
C(k)=cos (2π/N)k, S(k)=sin (2π/N)/k 。将式 (4.5.26)
中的 k分别取 k,N/2+k,N/2-k和 N-k四个值，并考虑
X0H(k)和 X1H(k)以 N/2为周期，得到
第 4章 快速傅里叶变换 (FFT)
0 1 1
0 1 1
0 1 1
0 1 1
( ) ( ) [ ( ) ( ) ( ) ( )]
2
( ) ( ) [ ( ) ( ) ( ) ( )]
22
( ) ( ) [ ( ) ( ) ( ) ( )]
2 2 2
( ) ( ) [ ( ) ( ) ( ) ( )]
22
H H H H
H H H H
H H H H
H H H
N
X k X k C k X k S k X k
NN
X k X k C k X k S k X k
N N N
X k X k S k X k C k X k
NN
X N k X k S k X k C k X k
?
? ? ? ?
?
?
?
? ? ? ? ?
?
?
?? ? ? ? ? ?
?
?
? ? ? ? ? ? ?
?
0
4
8
Nk
N
??
?
(4.5.27)
第 4章 快速傅里叶变换 (FFT)
当 k=0时, 式 (4.5.27)中有重复, 可单独写成
01
01
( 0) ( 0) ( 0)
( ) ( 0) ( 0)
2
H H H
H H H
X X X
NX X X
???
?
? ??
??
(4.5.28)
同理, 在 k=N/4时有
01
01
( ) ( ) ( )
4 4 4
3
( ) ( ) ( )
4 4 4
H H H
H H H
N N N
X X X
N N N
X X X
?
???
?
?
? ??
??
(4.5.29)
第 4章 快速傅里叶变换 (FFT)
图 4.5.1 基 2DIT-FHT原理和哈特莱碟形
点
D F T
2N
…
x ( 0 )
x ( 2 )
x ( N － 2)
点
D F T
2N
…
x ( 1 )
x ( 3 )
x ( N － 1)
X
0 H
( k )
X
1 H
( k )
X
0 H
( N /2 － k )
X
1 H
( N /2 － k )
X
H
( k )
X
H
( N /2 － k )
X
H
( N /2 ＋ k )
X
H
( N － k )
c ( k )
s ( k )
s ( k )
－ c ( k ) － 1
－ 1
第 4章 快速傅里叶变换 (FFT)
图 4.5.2 4点 DFHT蝶形图
－ 1
－ 1
－ 1
－ 1
x
0
( 0 ) ＝ x ( 0 )
x
0
( 2 ) ＝ x ( 2 )
x
1
( 0 ) ＝ x ( 1 )
x
1
( 1 ) ＝ x ( 3 )
X
H
( 0 )
X
H
( 1 )
X
H
( 2 )
X
H
( 3 )
第 4章 快速傅里叶变换 (FFT)
图 4.5.3 16点基 2DIT―FHT 流图
x ( 0 )
x ( 8 )
x ( 4 )
x ( 1 2 )
x ( 2 )
x ( 1 0 )
x ( 6 )
x ( 1 4 )
x ( 1 )
x ( 9 )
x ( 5 )
x ( 1 3 )
x ( 3 )
x ( 1 1 )
x ( 7 )
x ( 1 5 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
X ( 8 )
X ( 9 )
X ( 1 0 )
X ( 1 1 )
X ( 1 2 )
X ( 1 3 )
X ( 1 4 )
X ( 1 5 )
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ c
2
－ c
1
－ c
3
c
3
c
2
c
1
c
2
－ c
2
s
2
s
2
s
2
s
1
s
3
s
3
s
2
1
s
c
2
－ c
2
s
2
s
2
－ 1
－ 1
第 4章 快速傅里叶变换 (FFT)
2,基 2DIT―FHT 的运算量
观察图 4.5.3可知, 运算流图中都是实数运算 。
N=2M点 FHT流图共分为 M级 。 用 L表示流图自右向左
的蝶形级数 。 第 L级乘法次数为 2L(N/2L-2),但最后二
级无乘法运算, 所以, 总的乘法次数 MH为
2
1
1
2 ( 2 ) 3 4
2
33
2
22
M
L
H L
L
H
M N M N
A N M N
?
?
? ? ? ? ?
? ? ?
? (4.5.30)
(4.5.31)
同理可求得总的加法次数 AH为
第 4章 快速傅里叶变换 (FFT)
4.5.6 实信号的快速循环卷积
用 DIT―FFT 计算两个实信号 x1(n)和 x2(n)的循环卷
积时, 最直接的方法是将信号的虚部都置为零, 再按
复序列用 FFT计算 。 显然这样做是很浪费的 。 现在我们
可用基 2DIT―FHT 直接进行实正交变换来处理实信号
的循环卷积问题 。
11
22
( ) ( )
( ) ( )
F H T
H
F H T
H
x n X k
x n X k
??
??
12( ) ( ) ( ) ( )
I F H T
HY k y n x n x n? ? ? e
计算式
(4.5.18)
第 4章 快速傅里叶变换 (FFT)
4.1 引言
4.2 基 2FFT算法
4.3 进一步减少运算量的措施
4.4 分裂基 FFT算法
4.5 离散哈特莱变换 (DHT)
第 4章 快速傅里叶变换 (FFT)
4.1 引言
DFT是信号分析与处理中的一种重要变换 。 因直
接计算 DFT的计算量与变换区间长度 N的平方成正比,
当 N较大时, 计算量太大, 所以在快速傅里叶变换 (简
称 FFT)出现以前, 直接用 DFT算法进行谱分析和信号
的实时处理是不切实际的 。 直到 1965年发现了 DFT的
一种快速算法以后, 情况才发生了根本的变化 。
第 4章 快速傅里叶变换 (FFT)
4.2 基 2FFT算法
4.2.1 直接计算 DFT的特点及减少运算量的基本途径
长度为 N的有限长序列 x(n)的 DFT为
考虑 x(n)为复数序列的一般情况, 对某一个 k值,
直接按 (4.2.1)式计算 X(k)值需要 N次复数乘法, (N-1)次
复数加法 。
1
0
( ) ( ),0,1,,1
N
kn
N
n
X k x n W k N
?
?
? ? ? ? ? ??
(4.2.1)
第 4章 快速傅里叶变换 (FFT)
如前所述, N点 DFT的复乘次数等于 N2。 显然,
把 N点 DFT分解为几个较短的 DFT,可使乘法次数大大
减少 。 另外, 旋转因子 WmN具有明显的周期性和对称
性 。 其周期性表现为
22()j m l N j m
m l N mNN
NNW e e W
??? ? ?
? ? ? ?
(4.2.2)
其对称性表现为
2
[]m N m N m mN N N N
Nm
m
NN
W W W W
WW
? ? ? ?
?
??
??
或者
第 4章 快速傅里叶变换 (FFT)
4.2.2 时域抽取法基 2FFT基本原理
FFT 算法基本上分为两大类：时域抽取法
FFT(Decimation In Time FFT,简称 DIT-FFT)和频域抽取
法 FFT(Decimation In Frequency FFT,简称 DIF―FFT) 。
下面先介绍 DIF―FFT 算法 。
设序列 x(n)的长度为 N,且满足
2,MNM? 为自然数
按 n的奇偶把 x(n)分解为两个 N/2点的子序列
1
2
( ) ( 2 ),0,1,1
2
( ) ( 2 1 ),0,1,1
2
N
x r x r r
N
x r x r r
? ? ? ? ? ?
? ? ? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
则 x(n)的 DFT为
/ 2 1 / 2 1
2 ( 2 1 )
00
/ 2 1 / 2 1
2
12
00
( ) ( ) ( )
( 2 ) ( 2 1 )
( ) ( )
k n k n
NN
nn
NN
k r k r
NN
rr
NN
k k r
NN
rr
X k x n W x n W
x r W x r W
x r W x r W
??
??
?
??
??
??
??
? ? ?
??
??
??
??
由于
2
2 2
22 2
/2
j k rN
j k rk r k rN
NNW e e W
?
? ??
? ? ?
所以
/ 2 1 / 2 1
1 / 2 2 / 2 1 2
00
( ) ( ) ( ) ( ) ( )
NN
kr k kr k
N N N N
rr
X k x r W W x r W X k W X k
??
??
? ? ? ???
第 4章 快速傅里叶变换 (FFT)
其中 X1(k)和 X2(k)分别为 x1(r)和 x2(r)的 N/2点 DFT，
即
/ 2 1
1 1 / 2 1
0
/ 2 1
2 2 / 2 2
0
( ) ( ) [ ( ) ]
( ) ( ) [ ( ) ]
N
kr
N
r
N
kr
N
r
X k x r W D F T x r
X k x r W D F T x r
?
?
?
?
??
??
?
?
(4.2.5)
(4.2.6)
由于 X1(k)和 X2(k)均以 N/2为周期, 且
, 所以 X(k)又可表示为
2
Nk k
NNWW
? ??
12
12
( ) ( ) ( ) 0,1,1
2
( ) ( ) ( ) 0,1,1
22
k
N
k
N
N
X k X k W X k k
NN
X k X k W X k k
? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
(4.2.7)
(4.2.8)
第 4章 快速傅里叶变换 (FFT)
图 4.2.1 蝶形运算符号
C
A
B
A ＋ BC
A － BC
第 4章 快速傅里叶变换 (FFT)
图 4.2.2 N点 DFT的一次时域抽取分解图 (N=8)
N /2 点
D F T
W N
0
N /2 点
D F T
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 )
第 4章 快速傅里叶变换 (FFT)
与第一次分解相同, 将 x1(r)按奇偶分解成两个 N/4
长的子序列 x3(l)和 x4(l),即
32
41
( ) ( 2 ),0,1,,1
( ) ( 2 1 ) 4
x l x l Nl
x l x l
? ? ? ? ? ? ?
???
?
那么,X1(k)又可表示为 / 4 1 / 4 1
2 ( 2 1 )
1 1 / 2 1 / 2
00
/ 4 1 / 4 1
3 / 4 / 2 4 / 4
00
3 / 2 4
( ) ( 2 ) ( 2 1 )
( ) ( )
( ) ( ),0,1,/ 2 1
NN
k l k l
NN
ii
NN
k l k k l
N N N
ii
k
N
X k x l W x l W
x l W W x l W
x k W X k k N
??
?
??
??
??
? ? ?
??
? ? ? ? ? ? ?
??
??
(4.2.9)
第 4章 快速傅里叶变换 (FFT)
式中 / 4 1
3 3 / 4 3
0
/ 4 1
4 4 / 4 4
0
( ) ( ) [ ( ) ]
( ) ( ) [ ( ) ]
N
kl
N
i
N
kl
N
i
x k x l W D F T x l
x k x l W D F T x l
?
?
?
?
??
??
?
?
同理, 由 X3(k)和 X4(k)的周期性和 Wm N/2的对称
性 Wk+N/4 N/2=-Wk N/2 最后得到,
1 3 / 2 4
1 3 / 2 4
( ) ( ) ( ),0,1,,/ 4 1
( / 4) ( ) ( )
k
N
k
N
X k X k W X k kN
X k N X k W X k
??? ? ? ? ? ? ?
?? ? ? ?
?
(4.2.10)
第 4章 快速傅里叶变换 (FFT)
用同样的方法可计算出
2 5 / 2 6
2 5 / 2 6
( ) ( ) ( ),0,1,/ 4 1
( / 4 ) ( )
k
N
k
N
X k X k W X k kN
X k N X k W X k
??? ?
? ? ? ? ??
? ? ? ??
(4.2.11)
其中
/ 4 1
5 5 / 4 5
0
/ 4 1
6 6 / 4 6
0
52
62
( ) ( ) [ ( ) ]
( ) ( ) [ ( ) ]
( ) ( 2 )
,0,1,/ 4 1
( ) ( 2 1 )
N
kl
N
i
N
kl
N
i
X k x l W DF T x l
X k x l W DF T x l
x l x l
lN
x l x l
?
?
?
?
??
??
? ?
? ? ? ? ??
?? ?
?
?
第 4章 快速傅里叶变换 (FFT)
图 4.2.3 N点 DFT的第二次时域抽取分解图 (N=8)
N /4 点
D F T
W
N
1
2
W
N
1
2
W N
0
W N
1
W N
2
W N
3
X
1
( 0 )
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 )
x ( 0 )
X
3
( 0 )
X
3
( 1 )
X
4
( 0 )
X
4
( 1 )
x ( 4 )
x ( 2 )
x ( 6 )
x ( 1 )
x ( 5 )
x ( 3 )
x ( 7 )
N /4 点
D F T
N /4 点
D F T
N /4 点
D F T
W
N
0
2
W
N
0
2
第 4章 快速傅里叶变换 (FFT)
图 4.2.4 N点 DIT―FFT 运算流图 (N=8)
W N
0
W N
1
W N
2
W N
3
W N
0
W N
2
W N
0
W N
2
W N
0
W N
0
W N
0
W N
0
x ( 0 )
x ( 4 )
x ( 2 )
x ( 6 )
x ( 1 )
x ( 5 )
x ( 3 )
x ( 7 )
A ( 0 )
A ( 1 )
A ( 2 )
A ( 3 )
A ( 4 )
A ( 5 )
A ( 6 )
A ( 7 )
A ( 0 )
A ( 1 )
A ( 2 )
A ( 3 )
A ( 4 )
A ( 5 )
A ( 6 )
A ( 7 )
A ( 0 )
A ( 7 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
A ( 0 )
A ( 1 )
A ( 2 )
A ( 3 )
A ( 4 )
A ( 5 )
A ( 6 )
A ( 7 )
第 4章 快速傅里叶变换 (FFT)
4.2.3 DIT―FFT 算法与直接计算 DFT运算量的比较
每一级运算都需要 N/2次复数乘和 N次复数加 (每个
蝶形需要两次复数加法 )。 所以, M级运算总共需要的
复数乘次数为
2
2
( 2 ) lo g
22
( 2 ) lo g
M
A
NN
C M N
C N M N N
? ? ?
? ? ?
复数加次数为
例如, N=210=1024时
2
2
1048576 2 0 4, 8
( / 2) l o g 5 1 2 0
N
NN ??
第 4章 快速傅里叶变换 (FFT)
图 4.2.5 FFT算法与直接计算 DFT所需乘法次数的比较曲线
第 4章 快速傅里叶变换 (FFT)
4.2.4 DIT―FFT 的运算规律及编程思想
1.原位计算
由图 4.2.4可以看出, DIT―FFT 的运算过程很有规
律 。 N=2M点的 FFT共进行 M级运算, 每级由 N/2个蝶
形运算组成 。
2.旋转因子的变化规律
如上所述, N点 DIT―FFT 运算流图中, 每级都有
N/2个蝶形 。 每个蝶形都要乘以因子 WpN,称其为旋转
因子, p称为旋转因子的指数 。
第 4章 快速傅里叶变换 (FFT)
观察图 4.2.4不难发现, 第 L级共有 2 L-1个不同的旋
转因子 。 N=23=8时的各级旋转因子表示如下,
L=1时, WpN=WJ N/4=WJ2L,J=0
L=2时, WpN =WJ N/2=WJ2L,J=0,1
L=3时, WpN =WJN=WJ2L,J=0,1,2,3
对 N=2M的一般情况, 第 L级的旋转因子为
1
2
21
2
,0,1,2,,2 1
2 2 2 2
,0,1,2,,2 1
2
ML
LM
p J L
N
L M L M L M
P J J L
NN N
ML
W W L J
N
W W W J
pJ
?
?
?
??
?
?
? ? ? ? ? ?
? ? ? ?
? ? ? ? ? ? ?
?
g
g
g
(4.2.12)
(4.2.13)
第 4章 快速傅里叶变换 (FFT)
3,蝶形运算规律
设序列 x(n)经时域抽选 (倒序 )后, 存入数组 X中 。
如果蝶形运算的两个输入数据相距 B个点, 应用原位计
算, 则蝶形运算可表示成如下形式,
X (J) XL-1(J)+X L-1(J+B)WpN
XL(J+B) XL-1(J)-X L-1(J+B)WpN
式中 p=J·2 M-L； J=0,1,…,2 L-1-1； L=1,2,…,M
?
?
第 4章 快速傅里叶变换 (FFT)
下标 L表示第 L级运算, XL(J)则表示第 L级运算后
数组元素 X(J)的值 。 如果要用实数运算完成上述蝶形
运算, 可按下面的算法进行 。
设
T=X L-1(J+B)WpN=TR+jTI
X L-1(J)=X′R(J)+jX′I(J)
式中下标 R表示取实部, I表示取虚部,
22
( ) c o s ( ) s in
22
( ) c o s ( ) s in
R R R I
I I R I
T X J B p X J B p
NN
T X J B p X J B p
NN
??
??
??? ? ? ?
??? ? ? ?
第 4章 快速傅里叶变换 (FFT) ( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
LR
R R R
I I I
R R R
I I I
X J X J j J
X J X J T
X J X J T
X J B X J T
X J B X J T
??
???
???
?? ? ?
?? ? ?
则
第 4章 快速傅里叶变换 (FFT)
4,编程思想及程序框图
图 4.2.6 DIT―FFT 运算和程序框图
开 始
送入 x ( n ), M
N ＝ 2
M
倒 序
L ＝ 1,M
Ｊ ＝ 0,B － 1
P ＝ 2
M － L
J
k ＝ J,N － 1,2
L
p
N
p
N
WBkXkXBkX
WBkXkXkX
)()()(
)()()(
????
???
输 出
结 束
B 2
L － 1
第 4章 快速傅里叶变换 (FFT)
5,序列的倒序
DIT―FFT 算法的输入序列的排序看起来似乎很乱,
但仔细分析就会发现这种倒序是很有规律的 。 由于
N=2M,所以顺序数可用 M位二进制数 (nM-1nM-2…n1n0)
表示 。
图 4.2.7 形成倒序的树状图 (N=23)
0
1
0
1
0
1
0
1
0
1
0
1
0
1
( n
2
n
1
n
0
)
2
0 0 0 0
4
2
6
1
5
3
7
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
0 1 1
1 1 1
第 4章 快速傅里叶变换 (FFT)
表 4.2.1 顺序和倒序二进制数对照表
第 4章 快速傅里叶变换 (FFT)
图 4.2.8 倒序规律
x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 )
A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 )
A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 )
x ( 0 ) x ( 4 ) x ( 2 ) x ( 6 ) x ( 1 ) x ( 5 ) x ( 3 ) x ( 7 )
第 4章 快速傅里叶变换 (FFT)
图 4.2.9 倒序程序框图
2
2
1
??
?
?
NN
LHJ
NLH
I ＝ 1,N
1
I ≥ J
TJA
JXIA
IXT
?
?
?
)(
)()(
)(
J ＜ K
LHK ?
KJJ ??
2KK
KJJ
?
??
Ｙ
N
N
Y
第 4章 快速傅里叶变换 (FFT)
4.2.5 频域抽取法 FFT(DIF―FFT)
在基 2快速算法中, 频域抽取法 FFT也是一种常用
的快速算法, 简称 DIF―FFT 。
设序列 x(n)长度为 N=2M,首先将 x(n)前后对半分
开, 得到两个子序列, 其 DFT可表示为如下形式,
1
0
/ 2 1 1
0 / 2
/ 2 1 / 2 1
( / 2 )
00
/ 2 1
/2
0
( ) [ ( ) ] ( )
( ) ( )
( ) ( )
2
[ ( ) ( ) ]
2
N
k
N
n
NN
k n k n
NN
n n N
NN
k n k n N
NN
nn
N
k N k n
NN
n
X k DFT x n x n W
x n W x n W
N
x n W x n W
N
x n W x n W
?
?
??
??
??
?
??
?
?
??
??
? ? ?
? ? ?
?
??
??
?
第 4章 快速傅里叶变换 (FFT)
/2 1,( 1 )
1
k N k
N
k
W
k
???
? ? ? ?
????
偶数
奇数
将 X(k)分解成偶数组与奇数组，当 k取偶数
(k=2r,r=0,1,…,N/2 -1)时
/ 2 1
2
0
/ 2 1
2
/2
0
( 2 ) [ ( ) ( )]
2
[ ( ) ( )]
2
N
rn
N
n
N
rn
N
n
N
X r x n x n W
N
x n x n W
?
?
?
?
? ? ?
? ? ?
?
? (4.2.14)
第 4章 快速傅里叶变换 (FFT)
当 k取奇数 (k=2r+1,r=0,1,…,N/2-1)时
/ 2 1
( 2 1 )
0
/ 2 1
/2
0
( 2 1 ) [ ( ) ( ) ]
2
[ ( ) ( ) ]
2
N
nr
N
n
N
n n r
NN
n
N
X r x n x n W
N
x n x n W W
?
?
?
?
?
? ? ? ?
? ? ?
?
? g(4.2.15)
将 x1(n)和 x2(n)分别代入 (4.2.14)和 (4.2.15)式, 可得
/ 2 1
1 / 2
0
/ 2 1
2 / 2
0
( 2 ) ( )
( 2 1 ) ( )
N
rn
N
n
N
rn
N
n
X r x n W
X r x n W
?
?
?
?
?
??
?
?
? ??
??
?
?
(4.2.16)
第 4章 快速傅里叶变换 (FFT)
图 4.2.10 DIF―FFT 蝶形运算流图符号
第 4章 快速傅里叶变换 (FFT)
图 4.2.11 DIF―FFT 一次分解运算流图 (N=8)
N /2 点
D F T
W N
0
N /2 点
D F T
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 )
第 4章 快速傅里叶变换 (FFT)
图 4.2.12 DIF―FFT 二次分解运算流图 (N=8)
N /4 点
D F T
W N
0
W N
1
W N
2
W N
3
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
X ( 0 )
X ( 4 )
X ( 2 )
X ( 6 )
X ( 1 )
X ( 5 )
X ( 3 )
X ( 7 )
W N
0
W N
2
W N
0
W N
2
N /4 点
D F T
N /4 点
D F T
N /4 点
D F T
第 4章 快速傅里叶变换 (FFT)
图 4.2.13 DIF―FFT 运算流图 (N=8)
W N
0
W N
1
W N
2
W N
3
W N
0
W N
2
W N
0
W N
2
W N
0
W N
0
W N
0
W N
0
X ( 0 )
X ( 4 )
X ( 2 )
X ( 6 )
X ( 1 )
X ( 5 )
X ( 3 )
X ( 7 )
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
第 4章 快速傅里叶变换 (FFT)
图 4.2.14 DIT―FFT 的一种变形运算流图
W N
0
W N
0
W N
2
W N
0
X ( 0 )
X ( 4 )
X ( 2 )
X ( 6 )
X ( 1 )
X ( 5 )
X ( 3 )
X ( 7 )
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
W N
0
W N
2
W N
1
W N
3W N
2
W N
0
W N
0
W N
0
第 4章 快速傅里叶变换 (FFT)
图 4.2.15 DIT―FFT 的一种变形运算流图
W N
0
W N
0
W N
2
W N
0
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
W N
0
W N
2
W N
1
W N
3
W N
2
W N
0
W N
0
W N
0
第 4章 快速傅里叶变换 (FFT)
4.2.6 IDFT的高效算法
上述 FFT算法流图也可以用于离散傅里叶逆变换
(Inverse Discrete Fourier Transform,简称 IDFT)。 比较
DFT和 IDFT的运算公式,
1
0
1
0
( ) [ ( )] ( )
1
( ) [ ( )] ( )
N
k
N
n
N
kn
N
k
X k D F T x n x n W
x n ID F T x n X k W
N
?
?
?
?
?
??
??
?
?
第 4章 快速傅里叶变换 (FFT)
图 4.2.16 DIT―IFFT 运算流图
W N
0
W N
1?
W N
2?
W N
3?
W N
0
W N
0
N1
x ( 0 )
x ( 4 )
x ( 2 )
x ( 6 )
x ( 4 )
x ( 5 )
x ( 3 )
x ( 7 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
W N
2?
W N
2?
N1
N1
N1
N1
N1
N1
N1
第 4章 快速傅里叶变换 (FFT)
图 4.2.17 DIT―IFFT 运算流图 (防止溢出 )
W
N
0
2
1
21 x ( 0 )
x ( 4 )
x ( 2 )
x ( 6 )
x ( 1 )
x ( 5 )
x ( 3 )
x ( 7 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
21
21
21
W
N
1
2
1
?
W
N
2
2
1
?
W
N
3
2
1
?
21
21
W
N
0
2
1
W
N
2
2
1
?
21
21
W
N
0
2
1
W
N
2
2
1
?
21
W
N
0
2
1
21
W
N
0
2
1
21
21
W
N
0
2
1
W
N
0
2
1
第 4章 快速傅里叶变换 (FFT)
如果希望直接调用 FFT子程序计算 IFFT,则可用下
面的方法,
由于
1
0
1
0
1
( ) ( )
1
( ) ( )
N
kn
N
k
N
kn
N
k
x n X k W
N
x n X k W
N
?
?
?
?
??
?
?
?
?
?
对上式两边同时取共轭, 得
? ?1
0
11( ) [ ( ) ] [ ( )]N kn
N
k
x n X k W D F T X kNN
? ?
? ? ?
?
???
第 4章 快速傅里叶变换 (FFT)
4.3 进一步减少运算量的措施
4.3.1 多类蝶形单元运算
由 DIT―FFT 运算流图已得出结论, N=2M点 FFT共
需要 MN/2次复数乘法 。
由 (4.2.12) 式, 当 L=1 时, 只有一种旋转因子
W0N=1,所以, 第一级不需要乘法运算 。
第 4章 快速傅里叶变换 (FFT)
综上所述, 先除去第一, 二两级后, 所需复数乘法
次数应是
从 L=3至 L=M共减少复数乘法次数为
( 2 ) ( 2 )2M NCM??
(4.3.1)
1
33
12 ( ) 2
2 2 2
MM
L
L
LL
NNN
?
??
? ? ???
(4.3.2)
因此,DIT―FFT 的复乘次数降至
( 2 ) ( 2 ) ( 2 ) ( 3 ) 22 2 2M N N NC M M? ? ? ? ? ? ?
(4.3.3)
第 4章 快速傅里叶变换 (FFT)
22
( 1 ) ( ) ( )
22
2
[ ( ) ( ) ]
2
2
()
2
22
( ) ( )
22
def
j x jy x jy jx y
x y j x y
R jI
R x y
I x y y x
? ? ? ? ? ?
? ? ? ?
??
??
? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
从实数运算考虑, 计算 N=2M点 DIT―FFT 所需实数
乘法次数为
( 2 ) 4 [ ( 3 ) 2 ] ( 2 )
22
13
( 2 ) 1 0
2
M
NN
RM
NM
? ? ? ? ?
? ? ?(4.3.4)
第 4章 快速傅里叶变换 (FFT)
4.3.2 旋转因子的生成
在 FFT运算中，旋转因子 WmN=cos(2πm/N)-
jsin(2πm/N)，求正弦和余弦函数值的计算量是很大的。
第 4章 快速傅里叶变换 (FFT)
4.3.3 实序列的 FFT算法
设 x(n)为 N点实序列, 取 x(n)的偶数点和奇数点分
别作为新构造序列 y(n)的实部和虚部, 即
12
12
( ) ( 2 ),( ) ( 2 1 ),0,1,,1
2
( ) ( ) ( ),0,1,,1
2
N
x n x n x n x n n
N
y n x n j x n n
? ? ? ? ? ? ? ?
? ? ? ? ? ? ?
对 y(n)进行 N/2点 FFT,输出 Y(k),则
11
22
( ) [ ( )] ( )
,0,1,,1( ) [ ( )] ( ) 2ep
op
X k D F T x n Y k N
kX k D F T x n j Y k
?? ??
? ? ? ? ??? ? ?
??
根据 DIT―FFT 的思想及式 (4.2.7)和 (4.2.8)，可得到
12( ) ( ) ( ),0,1,2
k
N
NX k X k W X k k? ? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
由于 x(n)为实序列，所以 X(k)具有共轭对称性，
X(k)的另外 N/2点的值为
( ) ( ),1,2,,12NX N k X k k?? ? ? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
4.4 分裂基 FFT算法
4.4.1 分裂基 FFT算法原理
当 n=pq,且 p=N/4,q=4时, n可表示为
1 0 1 0 1 0,0 3,0 144
NNn p n n n n n n? ? ? ? ? ? ? ? ?
并有
10
1
1
0
/ 4 1 3
()
4
10
00
( ) ( )
()
4
N
kn
N
n
NN
k n n
N
nn
X k x n W
N
x n n W
?
?
?
?
??
?
??
?
??
第 4章 快速傅里叶变换 (FFT)
0 1
01
0
0
/ 4 1 3
1 0 4
/ 4 1
02
4 0 4 0 4
0
33
04
( ) ]
4
[ ( ) ( ) ( )
42
3
( ) ]
4
N
kn kn
N
nn
N
kk
n
knkk
NN
N
W x n n W
NN
x n W x n W x n W
N
x n W W W
?
?
?
??
? ? ? ? ?
??
??
?
再将上式中的 k表示为
1 0 1 04,0 1,0 34
Nk k k k k? ? ? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
可得
10
0
1 0 1 0 1 0 0
00
0
0 1 0 0
10
/ 4 1
( 4 )
0 0 4
0
8 2 3 ( 4 ) ( 4 )
0 4 0 4
/ 4 1
2
0 0 4 0 4
0
3 ( 4 )
04
( ) ( 4 )
[ ( ) ( )
4
3
( ) ( ) ]
24
[ ( ) ( ( ) ( )
42
3
( ) ]
4
N
kk
n
k k k k k n
N
N
kk
n
k k k n
N
X k X k k
N
x n x n W
NN
x n W x n W W
NN
x n x n W x n W
N
x n W W
?
?
?
? ? ?
?
?
?
??
? ? ?
? ? ? ?
? ? ? ? ?
??
?
?
对 k0=0,1,2,3,并用 k表示 k1,用 n表示 n0,可以
写出
第 4章 快速傅里叶变换 (FFT)
/ 4 1
4
0
/ 4 1
4
0
/ 4 1
42
0
3
( 4 ) [ ( ) ( ) ( ) ( ) ]
4 2 4
3
( 4 1 ) [ ( ) ( ) ( ) ( ) ]
4 2 4
3
( 4 2 ) [ ( ) ( ) ( ) ( ) ]
4 2 4
( 4 3 ) [ ( ) ( ) ( ) (
42
N
kn
N
n
N
k n n
N
n
N
k n n
N
n
N N N
X k x n x n x n x n W
N N N
X k x n jx n x n jx n W
N N N
X k x n x n x n x n W
NN
X k x n jx n x n jx n
?
?
?
?
?
?
?
?
? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
?
?
?
/ 4 1
43
0
3
)]
4
01
4
N
k n n
N
n
N
W
N
k
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
? ? ?
?
??
?
(4.4.1)
第 4章 快速傅里叶变换 (FFT)
/ 2 1
2
0
/ 4 1
4
0
/ 4 1
34
0
( 2 ) [ ( ) ( ) ],0 1
22
3
( 4 1 ) [ ( ) ( ) ( ) ( ) ]
4 2 4
01
4
3
( 4 3 ) [ ( ) ( ) ( ) ( ) ]
4 2 4
01
4
N
kn
N
n
N
n k n
NN
n
N
n k n
NN
n
NN
X k x n x n W k
N N N
X k x n jx n x n jx n W W
N
k
N N N
X k x n jx n x n jx n W W
N
k
?
?
?
?
?
?
?
? ? ? ? ? ?
?
?
? ? ?
? ? ? ? ? ? ? ???
?
??
?
??
? ? ??
?
? ? ?
? ? ? ? ? ? ? ???
??
? ? ?
?
?
?
??
?
?
?
? (4.4.2)
第 4章 快速傅里叶变换 (FFT)
2
1
4
23
4
( ) ( ) ( ),0 1
22
3
( ) [ ( ) ( ) ( ) ( )]
4 2 4
3
( ) [ ( ) ( ) ( ) ( )]
4 2 4
01
4
n
N
n
N
NN
x n x n x n n
N N N
x n x n j x n x n j x n W
N N N
x n x n j x n x n j x n W
N
n
?
? ? ? ? ? ?
?
?
?
? ? ? ? ? ? ?
?
?
? ? ? ? ? ? ? ?
?
?
? ? ??
?
(4.4.3)
令
第 4章 快速傅里叶变换 (FFT)
则 (4.4.2)式可写成如下更简明的形式,
/ 2 1
2
22
0
/ 4 1
1 4 1
44
0
/ 4 1
2 4 2
44
0
( 2 ) ( ) [ ( ) ],0 1
2
( 4 1 ) ( ) [ ( ) ],0 1
4
( 4 3 ) ( ) [ ( ) ],0 1
4
N
kn
N
n
N
kn
N
n
N
kn
N
n
N
X k x n W D F T x n k
N
X k x n W D F T x n k
N
X k x n W D F T x n k
?
?
?
?
?
?
?
? ? ? ? ?
?
?
?
? ? ? ? ? ??
?
?
? ? ? ? ? ??
?
?
?
?
(4.4.4)
第 4章 快速傅里叶变换 (FFT)
图 4.4.1 分裂基第一次分解 L形流图
点
D F T
…
…
…
…
点
D F T
点
D F T
…
…
…
…
…
…
…
…
…
…
x
2
( 1 )
x
2
(1 ＋ N / 4 )
2
N
4
N
4
N
)1(
1
4
x
)1(
2
4
x
1
N
W
3
N
W
x ( 1 )
?
?
?
?
?
?
?
4
1
N
x
?
?
?
?
?
?
?
2
1
N
x
?
?
?
?
?
?
?
4
3
1
N
x
－ 1
－ 1 － 1－ j
第 4章 快速傅里叶变换 (FFT)
例如, N=16,第一次抽选分解时, 由式 (4.4.3)得
x2(n)=x(n)+x(n+8),0≤n≤7
x14(n)={［ x(n)-x(n+8)］ -j［ x(n+4)-x(n+12)］ }Wn16,
0≤n≤3
x24(n)={［ x(n)-x(n+8)］ +j［ x(n+4)-x(n+12)］ }W3n16,
0≤n≤3
把上式代入式 (4.4.4),可得
X(2k)=DFT［ x2(n)］,0≤k≤7
X(4k+1)=DFT［ x14(n)］,0≤k≤3
X(4k+3)=DFT［ x24(n)］,0≤k≤3
第 4章 快速傅里叶变换 (FFT)
图 4.4.2 分裂基 FFT算法 L形排列示意图与结构示意图
(a)分裂基 FFT算法 L形排列示意图；
(b)分裂基 FFT算法运算流图结构示意图
( a ) ( b )
第 4章 快速傅里叶变换 (FFT)
图 4.4.3 16点分裂基第一次分解 L形流图 (图中省去箭头 )
( 8 )
点
D F T
x
2
( 0 )
x
2
( 1 )
x
2
( 2 )
x
2
( 3 )
x
2
( 4 )
x
2
( 5 )
x
2
( 6 )
x
2
( 7 )
点
D F T
点
D F T
)0(
1
4
x
)1(
1
4
x
)2(
1
4
x
)3(
1
4
x
)0(
2
4
x
)1(
2
4
x
)2(
2
4
x
)3(
2
4
x
4
4
?
N
4
4
?
N
2
N
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
x ( 8 )
x ( 9 )
x ( 1 0 )
x ( 1 1 )
x ( 1 2 )
x ( 1 3 )
x ( 1 4 )
x ( 1 5 )
0
N
W
1
N
W
3
N
W
2
N
W
0
N
W
3
N
W
6
N
W
－ j
－ j
－ j
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
X ( 8 )
X ( 9 )
X ( 1 0 )
X ( 1 1 )
X ( 1 2 )
X ( 1 3 )
X ( 1 4 )
X ( 1 5 )
X (2 k )
X (4 k ＋ 1)
X (4 k ＋ 3)
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
第 4章 快速傅里叶变换 (FFT)
第二次分解,
先对图 4.4.3中 N/2点 DFT进行分解 。
令 X1(l)=X(2l),则有
X1(2l)=DFT［ y2(n)］,0≤l≤3
X1(4l+1)=DFT［ y14(n)］,0≤l≤1
X1(4l+3)=DFT［ y24(n)］,0≤l≤1
第 4章 快速傅里叶变换 (FFT)
其中
y2(n)=x2(n)+x2(n+4),0≤n≤3
y14(n)={［ x2(n)-x2(n+4)］ -［ x2(n+2)x(n+6)］ }Wn8,n=0,1
y24(n)={［ x2(n)-x2(n+4)］ +j［ x2(n+2)x2(n+6)］ }W3n8,n=0,1
第 4章 快速傅里叶变换 (FFT)
图 4.4.4 图 4.4.4中 N/2点 DFT的分解 L形流图
( 4 )
点
D F T
x
2
( 0 )
x
2
( 1 )
x
2
( 2 )
x
2
( 3 )
x
2
( 4 )
x
2
( 5 )
x
2
( 6 )
x
2
( 7 )
y
2
( 0 )
y
2
( 1 )
y
2
( 2 )
y
2
( 3 )
X
1
( 0 ) ＝ X ( 0 )
X
1
( 2 ) ＝ X ( 4 )
X
1
( 4 ) ＝ X ( 8 )
X
1
( 6 ) ＝ X ( 1 2 )
X
1
( 1 ) ＝ X ( 2 )
X
1
( 5 ) ＝ X ( 1 0 )
X
1
( 3 ) ＝ X ( 6 )
X
1
( 7 ) ＝ X ( 1 4 )
X
1
(2 l )
X
1
(4 l ＋ 1 )
X
1
(4 l ＋ 3 )
4N
)0(
1
4
y
)1(
1
4
y
)1(
2
4
y
)0(
2
4
y
1
2N
W
3
2N
W
－ j
－ j
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
第 4章 快速傅里叶变换 (FFT)
图 4.4.5 4点分裂基 L形运算流图
v ( 0 )
v ( 1 )
v ( 2 )
v ( 3 )
V ( 0 )
V ( 2 )
V ( 1 )
V ( 3 )
－ j
－ 1
－ 1
－ 1
－ 1
第 4章 快速傅里叶变换 (FFT)
图 4.4.6 16点分裂基 FFT运算流图
x ( 0 )
x ( 1 )
x ( 2 )
x ( 3 )
x ( 4 )
x ( 5 )
x ( 6 )
x ( 7 )
x ( 8 )
x ( 9 )
x ( 1 0 )
x ( 1 1 )
x ( 1 2 )
x ( 1 3 )
x ( 1 4 )
x ( 1 5 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
X ( 8 )
X ( 9 )
X ( 1 0 )
X ( 1 1 )
X ( 1 2 )
X ( 1 3 )
X ( 1 4 )
X ( 1 5 )
－ j
－ 1
－ 1
－ 1
－ 1
－ j
－ j
－ 1
－ 1
－ 1
－ 1
－ j
－ j
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ j
－ j
－ j
－ j
W
1
W
2
W
3
W
3
W
6
W
9
W
2
W
6
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
N
N
N
N
N
N
N
N
第 4章 快速傅里叶变换 (FFT)
4.4.2 分裂基 FFT算法的运算量
设第 j级有 lj个 L形, j=1,2,…,M-1,M=log2N,则有
l1=N/4。 由图 4.4.2(b)可见, 第 j-1列中的 L形包含了第 j
列中的一部分结点的计算, 即空白部分, 所占结点数
刚好等于第 j-1列中所有 L形对应结点的一半, 所以第 j
列 L形个数就减少 l j-1/2个, 即
第 4章 快速傅里叶变换 (FFT)
1
1
1
2
2
3
1
0
42
4
1
( 1 )
4 2 4 2
11
( 1 )
4 2 4 2 4
1 1 1
( ) ( 1 ) ]
4 2 4 2 4
j
j
j
ij
j
i
lN
l
N
l
N l N
l
N l N
l
NN
l
?
?
?
??
?
? ? ? ?
? ? ? ? ?
? ? ? ? ??
第 4章 快速傅里叶变换 (FFT)
由于每个 L形有两次复 (数 )乘运算, 所以全部复
乘次数为
1
1
2
2 2 1
2 [ ( ) ]
3 3 3 2
1 2 2
lo g ( 1 )
3 9 9
M
M
Mj
j
M
N
C l M
N N N
?
?
? ? ? ? ?
? ? ? ?
?
(4.4.5)
第 4章 快速傅里叶变换 (FFT)
4.5 离散哈特莱变换 (DHT)
4.5.1 离散哈特莱变换定义
设 x(n),n=0,1,…,N-1,为一实序列, 其 DHT定义为
1
0
2( ) [ ( )] ( ) co s ( ),0,1,,1N
H
n
X k D H T x n x n kn k NN?
?
?
? ? ? ? ? ? ??
式中, cas(α)=cosα+sinα。 其逆变换 (IDHT)为
1
0
12( ) [ ( )] ( ) co s ( ),0,1,,1N
HH
k
x n ID H T X k X k kn n NNN ?
?
?
? ? ? ? ? ? ??
(4.5.3)
第 4章 快速傅里叶变换 (FFT)
逆变换证明如下,
1
0
1
0
1
0
1
0
22
c o s( ) c o s( )
2 2 2 2
[ c o s( ) si n( ) ] [ c o s( ) si n( ) ]
2 2 2 2
[ c o s( ) c o s( ) si n( ) si n( )
2 2 2 2
c o s( ) si n( ) si n( ) c o s( ) ]
22
[ c o s ( ) si n
N
k
N
k
N
k
N
k
k n k
NN
k n k n k k
N N N N
k n k k n k
N N N N
k n k k n k
N N N N
kn
N
??
?
? ? ? ?
??
? ? ? ?
??
? ? ? ?
??
?
?
?
?
?
?
?
?
?
?
? ? ?
??
??
? ? ?
?
?
?
? ( ) ]
,
0,
kn
N
Nn
n
?
?
?
?
?
??
?
?
?
?
?? (4.5.4)
第 4章 快速傅里叶变换 (FFT)
将式 (4.5.2)代入式 (4.5.3)得
11
00
11
00
1
0
1 2 2
( ) c o s( ) c o s( )
1 2 2
( ) c o s( ) c o s( )
,01
()
0,0
NN
k
NN
k
N
k
x k k n
N N N
x k n k
N N N
N
x
N
?
?
??
??
??
??
?
?
?
??
??
??
??
?
?
?
??
?
? ?
??
?
??
??
? g
第 4章 快速傅里叶变换 (FFT)
4.5.2 DHT与 DFT之间的关系
为了便于比较, 重写 DFT如下,
211
00
211
00
22
( ) [ ( ) ] ( ) ( ) [ c o s( ) sin( ) ]
1 1 2 2
( ) ( ) ( ) [ c o s( ) sin( ) ]
NN
j k n
N
nn
NN
j k n
N
kk
X k D FT x n x n e x n k n j k n
NN
x n X k e X k k n j k n
N N N N
?
?
??
??
??
?
??
??
??
? ? ? ?
? ? ?
??
??
(4.5.5)
(4.5.6)
容易看出,DHT的核函数
DFT的核函数
的实部与虚部之和。
2 2 2c o s( ) c o s( ) si n( )k n k n k n
N N N
? ? ???
2 22c o s ( ) ( )j kn
Ne k n j k nNN
? ????
第 4章 快速傅里叶变换 (FFT)
将 XH(k)分解为奇对称分量 XHo(k)与偶对称分量
XHe(k)之和
( ) ( ) ( )
1
( ) [ ( ) ( ) ]
2
1
( ) [ ( ) ( ) ]
2
H He Ho
He H H
Ho H H
X k X k X k
X k X k X N k
X k X k X N k
??
? ? ?
? ? ?
(4.5.7)
(4.5.8)
(4.5.9)
由 DHT定义有
1
0
1
0
2
( ) ( ) c o s ( )
2
( ) ( ) s i n ( )
N
He
n
N
Ho
n
X k x n k n
N
X k x n k n
N
?
?
?
?
?
?
?
?
?
?
(4.5.10a)
(4.5.10b)
第 4章 快速傅里叶变换 (FFT)
所以, x(n)的 DFT可表示为
同理, x(n)的 DHT可表示为
因此, 已知 x(n)的 DHT,则 DFT可用下式求得,
( ) ( ) ( )H e H oX k X k j X k?? (4.5.11)
( ) ( ) I m [ ( ) ]HeX k H k X k?? (4.5.12)
11( ) [ ( ) ( ) ] [ ( ) ( ) ]
22H H H HX k X k X N k j X k X N k? ? ? ? ? ?(4.5.13)
第 4章 快速傅里叶变换 (FFT)
4.5.3 DHT的主要优点
(1)DHT是实值变换, 在对实信号或实数据进行谱
分析时避免了复数运算, 从而提高了运算效率, 相应
的硬件也更简单, 更经济；
(2)DHT的正, 反变换 (除因子 1/N外 )具有相同的形
式, 因而, 实现 DHT的硬件或软件既能进行 DHT,也
能进行 IDHT；
(3)DHT与 DFT间的关系简单，容易实现两种谱之
间的相互转换。
第 4章 快速傅里叶变换 (FFT)
4.5.4 DHT的性质
1,线性性质
1 1 2 2
1 2 1 2
( ),( ) ( )
( ) ( ) ( ) ( )
HH
HH
x X k x n X k
a x n b x n a X k b X k
??
? ? ?(4.5.14)
2,x(N-n)的 DHT
( ) ( ),( ) ( )HHx n X k x N n X N n? ? ? ?
1
0
22( ) ( )[ co s ( ) s i n ( )],0,1,,1N
H
n
X N k x n kn kn k NNN??
?
?
? ? ? ? ? ? ? ??
(4.5.15)
其中, 当 k=0时, XH(N-k)=XH(N)=XH(0)。
第 4章 快速傅里叶变换 (FFT)
证明 由 DHT定义
1
0
1
0
1
0
2
[ ( ) ] ( ) c o s( )
2
( ) c o s( ( ) )
22
( ) [ c o s( ) si n( ) ]
N
n
N
n
N
n
DFT x N n x N n k n
N
x n k N n
N
x n k n k n
NN
?
?
??
?
?
?
?
?
?
? ? ?
??
??
?
?
?
而
1
0
1
0
2
( ) ( ) c o s ( ( ) )
22
( ) [ c o s ( ) s i n ( ) ] [ ( ) ]
N
H
n
N
n
X N k x n N k n
N
x n k n k n D F T x N n
NN
?
??
?
?
?
?
? ? ?
? ? ? ?
?
?
第 4章 快速傅里叶变换 (FFT)
3,循环移位性质
0 0 0
0 0 0
22
( ( ) ) ( ) ( ) c o s( ) ( ) si n( )
22
( ( ) ) ( ) ( ) c o s( ) ( ) si n( )
N N H
N N H
x n n R n X k k n H N k k n
NN
x n n R n X k k n H N k k n
NN
??
??
? ? ? ?
? ? ? ?
(4.5.16)
(4.5.17)
证明 由 DHT定义有
1
0
1
0
1
0
[ ( ) ( ) ]
2
( ( ) ) c o s( )
2
( ) c o s( ( ) )
2 2 2 2
( ) [ c o s( ) c o s( ) si n ( ) si n ( )
2 2 2 2
si n ( ) c o s( ) c o s( ) si n ( ) ]
o N N
N
oN
n
N
o
n
N
oo
n
oo
DH T x n n R n
x n n k n
N
x n k n n
N
x n k n k n k n k n
N N N N
k n k n k n k n
N N N N
?
?
? ? ? ?
? ? ? ?
?
?
?
?
?
?
?
??
??
??
??
?
?
?
第 4章 快速傅里叶变换 (FFT)
1
0
1
0
2 2 2
( ) [ c o s( ) si n( ) ] c o s( )
2 2 2
( ) [ c o s( ) si n( ) ] si n( )
22
( ) c o s( ) ( ) si n( )
N
o
n
N
o
n
H o H o
x n k n k n k n
N N N
x n k n k n k n
N N N
X k k n X N k k n
NN
? ? ?
? ? ?
??
?
?
?
?
??
??
? ? ?
?
?
第 4章 快速傅里叶变换 (FFT)
4,奇偶性
奇对称序列和偶对称序列的 DHT仍然是奇对称序
列或偶对称序列, 即 DHT不改变序列的奇偶性 。
5.循环卷积定理
1 1 2 2
1 2 2 1 2 1
1 2 1 2 1 2
( ) ( ),( ) ( )
( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( )
HH
H H e H H o
H H e H H o
x n X k x n X k
x n x n X k X k X N k X k
x n x n X k X k X N k X k
??
? ? ?
? ? ?
e
e
(4.5.18)
(4.5.19)
第 4章 快速傅里叶变换 (FFT)
证明 下面利用 DFT的循环卷积定理和 DHT与 DFT
之间的关系来证明
其中, X1(k)=DFT［ x1(n)］,X2(k)=DFT［ x2(n)］,
根据 DHT与 DFT之间的关系, 则有
1 2 1 2[ ( ) ( ) ] ( ) ( )D F T x n x n X k X k?eg
1 1 1
2 2 2
2 2 2
( ) ( ) ( )
( ) ( ) ( )
11
[ ( ) ( ) ] [ ( ) ]
22
H e H o
H e H o
H H H
X k X k jX k
X k X k jX k
X k X N k j X N k
??
??
? ? ? ? ?
第 4章 快速傅里叶变换 (FFT)
将上面两式代入式 (4.5.20)并整理后, 得
2 1 1 1 1
2 1 1 1 1
12
2 1 2 1
1
( ) ( ) [ ( ) ( ) ( ) ( ) ]
2
1
( ) [ ( ) ( ) ( ) ( ) ]
2
( ) [ ( ) ( ) ]
R e [ ( ) ] I m [ ( ) ]
( ) ( ) ( ) ( )
H He Ho He Ho
H He Ho He Ho
H
H He H Ho
X k X k X k X k j X k j X k
X N k X k X k j X k j X k
X k DF T x n x n
X k X k
X k X k X N k X k
? ? ? ?
? ? ? ? ?
?
??
? ? ?
e
所以式 (4.5.18)成立 。 同理可证明式 (4.5.19)亦成立 。
当 x1(n)或 x2(n)是偶对称序列时, 则由 DHT的奇偶性有
1 2 1 2( ) ( ) ( ) ( ) ( )H H Hx n x n X k X k X k??e
(4.5.21)
第 4章 快速傅里叶变换 (FFT)
4.5.5 DHT的快速算法 (FHT)
1.基 2DIT―FHT 算法及运算流图
仿照快速 DFT的分解方法，可通过时域抽取或频域
抽取的方式实现快速 DHT。
x(n)的 N=2M点 DHT如下式,
1
0
0
1
11
22
00
2
( ) ( ) c o s ( ),0 1
( ) ( 2 )
,0 1
( ) ( 2 1 ) 2
22
( ) ( 2 ) c o s ( 2 ) ( 2 1 ) c o s ( ( 2 1 ) )
N
H
n
NN
H
rr
X k x n k n k N
N
x r x r N
r
x r x r
X k x r r k x r r k
NN
?
??
?
?
??
??
? ? ? ?
? ?
? ? ??
??
?
? ? ? ?
?
??
对 x(n)进行奇偶抽取
(4.5.22)
(4.5.23)
第 4章 快速傅里叶变换 (FFT)
与 DFT的时域抽取分解比较,
不是 一个指数函数，所以处理要比 W(2r+1)kN麻烦一
些。 根据三角公式有
2c o s ( ( 2 1 ) )kr
N
? ?
11
22
01
00
1
2
1
0
c o s( ) c o s c o s c o s( ) si n
2 2 2
( ) ( ) c o s( ) c o s( ) ( ) c o s( )
/ 2 / 2
22
si n ( ) ( ) c o s( )
/2
H
rr
r
X k x r rk k x r rk
N N N
k x r rk
NN
??
?
? ? ? ? ? ?
? ? ?
??
??
??
?
?
? ? ? ? ?
??
??
??
?
(4.5.24)
(4.5.25)
第 4章 快速傅里叶变换 (FFT)
令 X0H(k)=DHT［ x0(n)］,X1H(k)=DHT［ x1(n)］, 并
考虑 DHT的周期性, (4.5.25)式可写成
0 1 1
22( ) ( ) c o s( ) ( ) si n( ) ( )
2H H H H
NX k X k k X k k X k
NN
??? ? ? ?
为了使以下推导中公式简明，记
C(k)=cos (2π/N)k, S(k)=sin (2π/N)/k 。将式 (4.5.26)
中的 k分别取 k,N/2+k,N/2-k和 N-k四个值，并考虑
X0H(k)和 X1H(k)以 N/2为周期，得到
第 4章 快速傅里叶变换 (FFT)
0 1 1
0 1 1
0 1 1
0 1 1
( ) ( ) [ ( ) ( ) ( ) ( )]
2
( ) ( ) [ ( ) ( ) ( ) ( )]
22
( ) ( ) [ ( ) ( ) ( ) ( )]
2 2 2
( ) ( ) [ ( ) ( ) ( ) ( )]
22
H H H H
H H H H
H H H H
H H H
N
X k X k C k X k S k X k
NN
X k X k C k X k S k X k
N N N
X k X k S k X k C k X k
NN
X N k X k S k X k C k X k
?
? ? ? ?
?
?
?
? ? ? ? ?
?
?
?? ? ? ? ? ?
?
?
? ? ? ? ? ? ?
?
0
4
8
Nk
N
??
?
(4.5.27)
第 4章 快速傅里叶变换 (FFT)
当 k=0时, 式 (4.5.27)中有重复, 可单独写成
01
01
( 0) ( 0) ( 0)
( ) ( 0) ( 0)
2
H H H
H H H
X X X
NX X X
???
?
? ??
??
(4.5.28)
同理, 在 k=N/4时有
01
01
( ) ( ) ( )
4 4 4
3
( ) ( ) ( )
4 4 4
H H H
H H H
N N N
X X X
N N N
X X X
?
???
?
?
? ??
??
(4.5.29)
第 4章 快速傅里叶变换 (FFT)
图 4.5.1 基 2DIT-FHT原理和哈特莱碟形
点
D F T
2N
…
x ( 0 )
x ( 2 )
x ( N － 2)
点
D F T
2N
…
x ( 1 )
x ( 3 )
x ( N － 1)
X
0 H
( k )
X
1 H
( k )
X
0 H
( N /2 － k )
X
1 H
( N /2 － k )
X
H
( k )
X
H
( N /2 － k )
X
H
( N /2 ＋ k )
X
H
( N － k )
c ( k )
s ( k )
s ( k )
－ c ( k ) － 1
－ 1
第 4章 快速傅里叶变换 (FFT)
图 4.5.2 4点 DFHT蝶形图
－ 1
－ 1
－ 1
－ 1
x
0
( 0 ) ＝ x ( 0 )
x
0
( 2 ) ＝ x ( 2 )
x
1
( 0 ) ＝ x ( 1 )
x
1
( 1 ) ＝ x ( 3 )
X
H
( 0 )
X
H
( 1 )
X
H
( 2 )
X
H
( 3 )
第 4章 快速傅里叶变换 (FFT)
图 4.5.3 16点基 2DIT―FHT 流图
x ( 0 )
x ( 8 )
x ( 4 )
x ( 1 2 )
x ( 2 )
x ( 1 0 )
x ( 6 )
x ( 1 4 )
x ( 1 )
x ( 9 )
x ( 5 )
x ( 1 3 )
x ( 3 )
x ( 1 1 )
x ( 7 )
x ( 1 5 )
X ( 0 )
X ( 1 )
X ( 2 )
X ( 3 )
X ( 4 )
X ( 5 )
X ( 6 )
X ( 7 )
X ( 8 )
X ( 9 )
X ( 1 0 )
X ( 1 1 )
X ( 1 2 )
X ( 1 3 )
X ( 1 4 )
X ( 1 5 )
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ 1
－ c
2
－ c
1
－ c
3
c
3
c
2
c
1
c
2
－ c
2
s
2
s
2
s
2
s
1
s
3
s
3
s
2
1
s
c
2
－ c
2
s
2
s
2
－ 1
－ 1
第 4章 快速傅里叶变换 (FFT)
2,基 2DIT―FHT 的运算量
观察图 4.5.3可知, 运算流图中都是实数运算 。
N=2M点 FHT流图共分为 M级 。 用 L表示流图自右向左
的蝶形级数 。 第 L级乘法次数为 2L(N/2L-2),但最后二
级无乘法运算, 所以, 总的乘法次数 MH为
2
1
1
2 ( 2 ) 3 4
2
33
2
22
M
L
H L
L
H
M N M N
A N M N
?
?
? ? ? ? ?
? ? ?
? (4.5.30)
(4.5.31)
同理可求得总的加法次数 AH为
第 4章 快速傅里叶变换 (FFT)
4.5.6 实信号的快速循环卷积
用 DIT―FFT 计算两个实信号 x1(n)和 x2(n)的循环卷
积时, 最直接的方法是将信号的虚部都置为零, 再按
复序列用 FFT计算 。 显然这样做是很浪费的 。 现在我们
可用基 2DIT―FHT 直接进行实正交变换来处理实信号
的循环卷积问题 。
11
22
( ) ( )
( ) ( )
F H T
H
F H T
H
x n X k
x n X k
??
??
12( ) ( ) ( ) ( )
I F H T
HY k y n x n x n? ? ? e
计算式
(4.5.18)
