第4章快速傅里叶变换

1、第第4章章 快速傅里叶变换快速傅里叶变换 (fast fourier transformfft)4.1 引言引言4.2 基基2fft算法算法4.1 引言引言) 1() 1 ()0()()0()1(01000100nxwxwxwwnxxnnnnnnnn) 1() 1 ()0()() 1 ()1(11101101nxwxwxwwnxxnnnnnnnn) 1() 1 ()0()()()1(1010nxwxwxwwnxkxnknknknnnnknnkwnxenxnxkxnnknnnnknnjn0 )()()(dft)(10102) 1() 1 ()0() 1() 1 ()0()1()1(2)1(1)1

2、(0)1()1(1211101)1(0201000nxxxwwwwwwwwwwwwnxxxnnnnnnnnnnnnnnnnnnnnnwkxekxnkxnxnknknnknknj0 )()(1)(idft)(10102)1() 1 ()0(1)(1)0()1(01000100nxwxwxwnwkxnxnnnnnkkn)1() 1 ()0(1)(1) 1 ()1(11101101nxwxwxwnwkxnxnnnnnkkn)1() 1 ()0(1)(1)()1(1010nxwxwxwnwkxnnxnnnnnnnnkknn) 1() 1 ()0(1) 1() 1 ()0()1()1(2)1(1)1(0

3、)1()1(1211101)1(0201000nxxxwwwwwwwwwwwwnnxxxnnnnnnnnnnnnnnnnnnn) 1() 1 ()0() 1() 1 ()0()1()1(2)1(1)1(0)1()1(1211101)1(0201000nxxxwwwwwwwwwwwwnxxxnnnnnnnnnnnnnnnnnnn) 1() 1 ()0(1) 1() 1 ()0()1()1(2)1(1)1(0)1()1(1211101)1(0201000nxxxwwwwwwwwwwwwnnxxxnnnnnnnnnnnnnnnnnnn计算计算x(k)的一个值需要的一个值需要n次复数乘法和次复数乘法和

4、(n-1)次复数加法，计算次复数加法，计算x(k)的所有的所有n个值需要个值需要nn次复数乘法和次复数乘法和n(n-1)次复数加法。次复数加法。nnwnxekxnkxnxnkwnxenxnxkxnknknnkknnjnnnknnnnknnjn0)()(1)()(0)()()()(1010210102 idft dft一、一、时域抽取法基时域抽取法基2fft原理原理 4.2 基基2fft算法算法将长度为将长度为n的序列的序列x(n) 按奇偶分解为两个按奇偶分解为两个n/2点的子序列点的子序列 则则x(n)的的dft为为12 1 0 ) 12()(12 1 0 )2()(21nrrxrxnrrxr

5、x，1 1 0 , )()()()()()() 12()2()()()()(dft)(12/0212/212/02/112/02212/02112/0)12(12/0210nkkxwkxwrxwwrxwrxwwrxwrxwrxwnxwnxwnxnxkxnrknkrnknnrkrnnrkrnknnrkrnnrrknnrkrnnknnnknnnnknnn，奇数偶数2/212/02/222/112/02/112110)(dft)()()(dft)()(1, 1 , 0 )()()()(nnrkrnnnrkrnknnnknnrxwrxkxrxwrxkxnkkxwkxwnxkx，1 1 0 , )()(

6、)()()()() 12()2()()()()(dft)(12/0212/212/02/112/02212/02112/0)12(12/0210nkkxwkxwrxwwrxwrxwwrxwrxwrxwnxwnxwnxnxkxnrknkrnknnrkrnnrkrnknnrkrnnrrknnrkrnnknnnknnnnknnn，奇数偶数x(k)按前按前n/2点和后点和后n/2点分开表示点分开表示12 1 0)()()2()()()(2121nkkxwkxnkxkxwkxkxknkn，abca cba cb图图4.2.2 n点点dft一次时域抽取分解运算流图（一次时域抽取分解运算流图（n=8）n/2

7、点dftwn0n/2点dftwn1wn2wn3x(0)x1(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)12 1 0)()()2()()()(2121nkkxwkxnkxkxwkxkxknkn，abca cba cb)2()(1rxrx) 12()(2rxrx12 1 0nr，图图4.2.2 n点点dft一次时域抽取分解运算流图（一次时域抽取分解运算流图（n=8）n/2点dftwn0n/2点dftwn1wn2wn3x(0)x1(0)x(2)x(4

8、)x(6)x(1)x(3)x(5)x(7)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)图图4.2.2包括两个包括两个n/2点点dft和和n/2个蝶形，每个个蝶形，每个n/2点点dft需要需要(n/2)(n/2)次复数乘法和次复数乘法和(n/2-1)(n/2)次复数加法运算，每个次复数加法运算，每个蝶形只有一次复数乘法运算和两次复数加法运算。所以，总的复蝶形只有一次复数乘法运算和两次复数加法运算。所以，总的复数乘法次数为：数乘法次数为：2/2/ ) 1(2/2)2/(22nnnnn总的复数加法次数为：总的复

9、数加法次数为：2/2)2/(2)2/() 12/(2nnnn图图4.2.3 n点点dft二次时域抽取分解运算流图（二次时域抽取分解运算流图（n=8） )(3rx )(4rx )(5rx )(6rx图图4.2.4 n点点fft运算流图（运算流图（n=8）分组分组方法方法原始数据原始数据序列序列n/2n/2分组分组n/4n/4分组分组( (最终分组结果最终分组结果) )计算计算结果结果按按奇奇偶偶分分组组x(0)x(0)x x1 1(0)(0)x(0)x(0)x x3 3(0)(0)x(0)x(0)x(0)x(0)x(1)x(1)x x1 1(1)(1)x(2)x(2)x x3 3(1)(1)x(

10、4)x(4)x(1)x(1)x(2)x(2)x x1 1(2)(2)x(4)x(4)x x4 4(0)(0)x(2)x(2)x(2)x(2)x(3)x(3)x x1 1(3)(3)x(6)x(6)x x4 4(1)(1)x(6)x(6)x(3)x(3)x(4)x(4)x x2 2(0)(0)x(1)x(1)x x5 5(0)(0)x(1)x(1)x(4)x(4)x(5)x(5)x x2 2(1)(1)x(3)x(3)x x5 5(1)(1)x(5)x(5)x(5)x(5)x(6)x(6)x x2 2(2)(2)x(5)x(5)x x6 6(0)(0)x(3)x(3)x(6)x(6)x(7)x(7)x x2 2(3)(3)x(7)x(7)x x6 6(1)(1)x(7)x(7)x(7)x(7)离散数据点按奇偶分组过程离散数据点按奇偶分组过程 【例例】假设时域连续信号假设时域连续信号x(t)=x1(t)+x2(t)+x3(t)，其中，其中x1(t)=3sin(30t)， x2(t)=2sin(40t)， x3(t)=sin(60t)。(1)如果用如果用fft对对x(t)进行频谱分析，问采样频率进行频谱分析，问采样频率fs和采样点数和采样点数n应如何选应如何选择，才能精确求出择，才能精确求出x1(t)、x2(t)、x3