第 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 lN j m
m lN 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
k r k k r 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 DFT x l
X k x l W DFT 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 ) l o g
22
( 2 ) l o 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
(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 ( ) si n
22
( ) c o s ( ) si n
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 nr
NN
n
N
X r x n x n W
N
x n x n W W
(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 I D 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 FT 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
de f
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 j x n x n j x n W
N N N
X k x n x n x n x n W
NN
X k x n j x n x n j x 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 jx n x n jx n W
N N N
x n x n jx n x n jx 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
l o 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( ) [ ( ) ] ( ) c o s ( ),0,1,,1N
H
n
X k D H T x n x n k n k NN?
式中,cas(α)=cosα+sinα。 其逆变换 (IDHT)为
1
0
12( ) [ ( ) ] ( ) c o s( ),0,1,,1N
HH
k
x n I DHT X k X k k n 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
第 4章 快速傅里叶变换 (FFT)
4.5.2 DHT与 DFT之间的关系为了便于比较,重写 DFT如下：
211
00
211
00
22
( ) [ ( ) ] ( ) ( ) [ c o s( ) si n( ) ]
1 1 2 2
( ) ( ) ( ) [ c o s( ) si n( ) ]
NN
j k n
N
nn
NN
j k n
N
kk
X k DF T 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 ( ) s i n ( )k n k n k n
N N N
2 22co s ( ) ( )j kn
Ne kn j knNN
第 4章 快速傅里叶变换 (FFT)
将 XH(k)分解为奇对称分量 XHo(k)与偶对称分量
XHe(k)之和
( ) ( ) ( )
1
( ) [ ( ) ( ) ]
2
1
( ) [ ( ) ( ) ]
2
H H e H o
H e H H
H o 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
( ) ( ) si 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( ) ( ) [ c o s ( ) s i n ( ) ],0,1,,1N
H
n
X N k x n k n k n 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
( ) ( ) co s ( ( ) )
22
( )[c o s ( ) s i n ( )] [ ( )]
N
H
n
N
n
X N k x n N k n
N
x n kn kn D F T x N n
NN
第 4章 快速傅里叶变换 (FFT)
3,循环移位性质
0 0 0
0 0 0
22
( ( ) ) ( ) ( ) c o s ( ) ( ) s i n ( )
22
( ( ) ) ( ) ( ) c o s ( ) ( ) s i 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
DHT 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
(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?
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 j X k
X k X k j X 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 D F T x n x n
X k X k
X k X k X N k X k
所以式 (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
(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 rk 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( ) sin
2 2 2
( ) ( ) c o s( ) c o s( ) ( ) c o s( )
/ 2 / 2
22
sin ( ) ( ) 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 ( ) ( ) s i 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
( ) ( )
( ) ( )
FHT
H
FHT
H
x n X k
x n X k
12( ) ( ) ( ) ( )
IF H T
HY k y n x n x n
计算式
(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 lN j m
m lN 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
k r k k r 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 DFT x l
X k x l W DFT 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 ) l o g
22
( 2 ) l o 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
(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 ( ) si n
22
( ) c o s ( ) si n
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 nr
NN
n
N
X r x n x n W
N
x n x n W W
(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 I D 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 FT 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
de f
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 j x n x n j x n W
N N N
X k x n x n x n x n W
NN
X k x n j x n x n j x 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 jx n x n jx n W
N N N
x n x n jx n x n jx 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
l o 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( ) [ ( ) ] ( ) c o s ( ),0,1,,1N
H
n
X k D H T x n x n k n k NN?
式中,cas(α)=cosα+sinα。 其逆变换 (IDHT)为
1
0
12( ) [ ( ) ] ( ) c o s( ),0,1,,1N
HH
k
x n I DHT X k X k k n 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
第 4章 快速傅里叶变换 (FFT)
4.5.2 DHT与 DFT之间的关系为了便于比较,重写 DFT如下：
211
00
211
00
22
( ) [ ( ) ] ( ) ( ) [ c o s( ) si n( ) ]
1 1 2 2
( ) ( ) ( ) [ c o s( ) si n( ) ]
NN
j k n
N
nn
NN
j k n
N
kk
X k DF T 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 ( ) s i n ( )k n k n k n
N N N
2 22co s ( ) ( )j kn
Ne kn j knNN
第 4章 快速傅里叶变换 (FFT)
将 XH(k)分解为奇对称分量 XHo(k)与偶对称分量
XHe(k)之和
( ) ( ) ( )
1
( ) [ ( ) ( ) ]
2
1
( ) [ ( ) ( ) ]
2
H H e H o
H e H H
H o 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
( ) ( ) si 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( ) ( ) [ c o s ( ) s i n ( ) ],0,1,,1N
H
n
X N k x n k n k n 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
( ) ( ) co s ( ( ) )
22
( )[c o s ( ) s i n ( )] [ ( )]
N
H
n
N
n
X N k x n N k n
N
x n kn kn D F T x N n
NN
第 4章 快速傅里叶变换 (FFT)
3,循环移位性质
0 0 0
0 0 0
22
( ( ) ) ( ) ( ) c o s ( ) ( ) s i n ( )
22
( ( ) ) ( ) ( ) c o s ( ) ( ) s i 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
DHT 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
(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?
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 j X k
X k X k j X 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 D F T x n x n
X k X k
X k X k X N k X k
所以式 (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
(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 rk 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( ) sin
2 2 2
( ) ( ) c o s( ) c o s( ) ( ) c o s( )
/ 2 / 2
22
sin ( ) ( ) 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 ( ) ( ) s i 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
( ) ( )
( ) ( )
FHT
H
FHT
H
x n X k
x n X k
12( ) ( ) ( ) ( )
IF H T
HY k y n x n x n
计算式
(4.5.18)
