第6章数字信号分析-FFT

1、广西大学机械工程学院广西大学机械工程学院机械工程机械工程测试测试信息信息信号分信号分析析主讲：曾盛绰主讲：曾盛绰 教授教授 20102010年年1 1月月 广西大学机械工程学院广西大学机械工程学院机械工程测试机械工程测试信息信息信号分信号分析析Industry-Specific PDAsMedical Devices广西大学机械工程学院广西大学机械工程学院机械工程测试机械工程测试信息信息信号分析信号分析广西大学机械工程学院广西大学机械工程学院1、了解快速傅里叶变换的有关概念、了解快速傅里叶变换的有关概念2、掌握数字信号分析的快速傅里叶变换方法、掌握数字信号分析的快速傅里叶变换方法广西大学机械工

2、程学院广西大学机械工程学院 快速傅立叶变换快速傅立叶变换(FFT)(FFT)是离散傅立叶变换的一是离散傅立叶变换的一种有效的算法，通过选择和重新排列中间结果，减种有效的算法，通过选择和重新排列中间结果，减小运算量。小运算量。快速傅立叶变换快速傅立叶变换 当采样点数为当采样点数为10241024点点,DFT,DFT要求一百万次以要求一百万次以上计算量，而上计算量，而FFTFFT则只要求一万次。则只要求一万次。 DFTDFT有大量重复的有大量重复的coscos、sinsin计算，计算，FFTFFT的作用的作用就是用技巧减少就是用技巧减少coscos、sinsin项重复计算。项重复计算。 广西大学机

3、械工程学院广西大学机械工程学院 虽然频谱分析和DFT运算很重要，但在很长一段时间里，由于DFT运算复杂，并没有得到真正的运用，而频谱分析仍大多采用模拟信号滤波的方法解决，直到1965年首次提出DFT运算的一种快速算法以后，情况才发生了根本变化，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法快速付里变换（FFT）算法。FFT的出现，使DFT的运算大大简化，运算时间缩短一二个数量级，使DFT的运算在实际中得到广泛应用。广西大学机械工程学院广西大学机械工程学院 首先分析有限长序列首先分析有限长序列 x（n）进行一次）进行一次DFT运算所运算所需的运算量。需的运算

4、量。 一般，一般，x（n）和）和wnkN都是复数，因此，每计算一个都是复数，因此，每计算一个X（k）值，要进行）值，要进行N次复数相乘，和次复数相乘，和N-1次复数相加次复数相加，X（k）一共有）一共有N个点，故完成全部个点，故完成全部DFT运算，需要运算，需要N2次复数相乘和次复数相乘和N（N-1）次复数相加，在这些运算中）次复数相加，在这些运算中，乘法比加法复杂，需要的运算时间多，尤其是复数，乘法比加法复杂，需要的运算时间多，尤其是复数相乘，每个复数相乘包括相乘，每个复数相乘包括4个实数相乘和个实数相乘和2个实数相加个实数相加，例，例 101, 1 , 0)()()(NnnkNNkwnxn

5、xDFTkX广西大学机械工程学院广西大学机械工程学院)()()()()(10nkNemnkNmeNnnkNmmnkNeewRnxIwInxRjwInxIwRnxRkX 又每个复数相加包括又每个复数相加包括2个实数相加，所个实数相加，所以，每计算一个以，每计算一个 X（k）要进行）要进行4N次实数次实数相乘和相乘和2N+2（N-1）=2（2N-1）次实数相加，）次实数相加，因此，整个因此，整个DFT运算需要运算需要4N2实数相乘和实数相乘和2N（2N-1）次实数相加。）次实数相加。广西大学机械工程学院广西大学机械工程学院 从上面的分析看到，在DFT计算中，不论是乘法和加法，运算量均与N2成正比。

6、因此，N较大时，运算量十分可观。例，计算N=10点的DFT，需要100次复数相乘，而N=1024点时，需要1048576（一百多万）次复数乘法，如果要求实时处理，则要求有很高的计算速度才能完成上述计算量。 反变换IDFT与DFT的运算结构相同，只是多乘一个常数1/N，所以二者的计算量相同。广西大学机械工程学院广西大学机械工程学院FFT算法的基本思想：算法的基本思想： 考察考察DFT与与IDFT的运算发现，利用以下两个特性可减少的运算发现，利用以下两个特性可减少运算量：运算量：1）系数 是一个周期函数，它的周期性和对称性可用来改进运算，提高计算效率。 例 又如 因此 利用这些周期性和对称性，使D

7、FT运算中有些项可合并；nkNjnkNew2nkNnNkNkNnNwww)()(, 12/NNwkNNkNww)2/(广西大学机械工程学院广西大学机械工程学院 2）利用）利用 的周期性和对称性，把长度的周期性和对称性，把长度为为N点的大点数的点的大点数的DFT运算依次分解为若干个小运算依次分解为若干个小点数的点数的DFT。因为。因为DFT的计算量正比于的计算量正比于N2，N小，小，计算量也就小。计算量也就小。 FFT算法正是基于这样的基本思想发展起来的。它算法正是基于这样的基本思想发展起来的。它有多种形式，但基本上可分为两类：时间抽取法和频率有多种形式，但基本上可分为两类：时间抽取法和频率抽取

8、法。抽取法。nkNw广西大学机械工程学院广西大学机械工程学院l 长度为N的有限长序列x(n)的DFT为l 考虑x(n)为复数序列的一般情况，对某一个k值，直接按(6.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。 10( )( ),0,1,1NknNnX kx n WkN(6.2.1) 一、直接计算一、直接计算DFT的特点及减少运算量的基本途径的特点及减少运算量的基本途径广西大学机械工程学院广西大学机械工程学院 如前所述，如前所述，N点点DFT的复乘次数等于的复乘次数等于N2。显然，把。显然，把N点点DFT分解为几个较短的分解为几个较短的DFT，可使乘法次数大大减少。另外，旋

9、，可使乘法次数大大减少。另外，旋转因子转因子WmN具有明显的周期性和对称性。具有明显的周期性和对称性。其其周期性周期性表现为表现为22()jm lNjmm lNmNNNNWeeW其其对称性对称性表现为表现为2mN mN mmNNNNNmmNNWWWWWW 或者 广西大学机械工程学院广西大学机械工程学院l FFT算法基本上分为两大类：时域抽取法FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取法FFT(Decimation In Frequency FFT,简称DIFFFT)。下面先介绍DIFFFT算法。l 设序列x(n)的长度为N，且满足2 ,MNM为自然数

10、按n的奇偶把x(n)分解为两个N/2点的子序列12( )(2 ),0,1,12( )(21),0,1,12Nx rxrrNx rxrr二、时域抽取法基二、时域抽取法基2FFT基本原理基本原理广西大学机械工程学院广西大学机械工程学院l 则x(n)的DFT为/2 1/2 12(21)00/2 1/2 121200( )( )( )(2 )(21)( )( )knknNNnnNNkrkrNNrrNNkkrNNrrX kx n Wx n Wxr WxrWx rWx r W由于222222/2jkrNjkrkrkrNNNWeeW所以 /2 1/2 11/22/21200( )( )( )( )( )NN

11、krkkrkNNNNrrX kx r WWx r WX kW Xk广西大学机械工程学院广西大学机械工程学院 其中其中X1(k)和和X2(k)分别为分别为x1(r)和和x2(r)的的N/2点点DFT，即即 /2 111/210/2 122/220( )( )( )( )( )( )NkrNrNkrNrX kx r WDFT x rXkx r WDFT x r(6.2.5) (6.2.6) 由于X1(k)和X2(k)均以N/2为周期，且 ，所以X(k)又可表示为2NkkNNWW 1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kX kW XkkNNX kX kW

12、Xkk(6.2.7) (6.2.8) 广西大学机械工程学院广西大学机械工程学院图6.2.1 蝶形运算符号 CABA BCA BC广西大学机械工程学院广西大学机械工程学院图6.2.2 N点DFT的一次时域抽取分解图(N=8) N/2点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)广西大学机械工程学院广西大学机械工程学院l 与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)

13、和x4(l)，即3241( )(2 ),0,1,1( )(21)4x lxlNlx lxl那么，X1(k)又可表示为 /4 1/4 12(21)11/21/200/4 1/4 13/4/24/4003/24( )(2 )(21)( )( )( )( ),0,1,/21NNklklNNiiNNklkklNNNiikNX kxl WxlWx l WWx l Wx kWXk kN(6.2.9) 广西大学机械工程学院广西大学机械工程学院式中 /4 133/430/4 144/440( )( )( )( )( )( )NklNiNklNix kx l WDFT x lx kx l WDFT x l 同理

14、，由X3(k)和X4(k)的周期性和Wm N/2的对称性 Wk+N/4 N/2=-Wk N/2 最后得到： 13/2413/24( )( )( ),0,1,/41(/4)( )( )kNkNX kXkWXkkNX kNXkWXk(6.2.10) 广西大学机械工程学院广西大学机械工程学院l 用同样的方法可计算出25/2625/26( )( )( ),0,1,/41(/4)( )kNkNXkXkWXkkNXkNX kWXk(6.2.11)其中 /4 155/450/4 166/4605262( )( )( )( )( )( )( )(2 ),0,1,/41( )(21)NklNiNklNiXkx

15、l WDFT x lXkx l WDFT x lx lxllNx lxl广西大学机械工程学院广西大学机械工程学院图6.2.3 N点DFT的第二次时域抽取分解图(N=8) N/4点DFTWN12WN12WN0WN1WN2WN3X1(0)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)x(0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4点DFTN/4点DFTN/4点DFTWN02WN02广西大学机械工程学院广西大学机械工程学院 图6.2.4 N点DITFF

16、T运算流图(N=8) WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 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)广西大学机械工程学院广西大学机械工程学院l 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为22(2)log

17、22(2)logMANNCMNCN MNN复数加次数为 例如，N=210=1024时221048576204.8(/2)log5120NNN三、三、DITFFT算法与直接计算算法与直接计算DFT运算量的比较运算量的比较广西大学机械工程学院广西大学机械工程学院图6.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线 广西大学机械工程学院广西大学机械工程学院 1.原位计算 由图6.2.4可以看出，DITFFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。 2.旋转因子的变化规律 如上所述，N点DITFFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因

18、子WpN，称其为旋转因子，p称为旋转因子的指数。 四、四、DITFFT的运算规律及编程思想的运算规律及编程思想广西大学机械工程学院广西大学机械工程学院l 观察图6.2.4不难发现，第L级共有2 L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：l L=1时，WpN=WJ N/4=WJ2L， J=0l L=2时， WpN =WJ N/2=WJ2L， J=0，1l L=3时， WpN =WJN=WJ2L， J=0，1，2，3广西大学机械工程学院广西大学机械工程学院12212,0,1,2,212222,0,1,2,212MLL MpJLNLML ML MPJJLNNNMLWW L JNW

19、WWJpJ对对N=2M的一般情况，第的一般情况，第L级的旋转因子为级的旋转因子为(6.2.12) (6.2.13) 广西大学机械工程学院广西大学机械工程学院l 3. 蝶形运算规律l 设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：l X (J) XL-1(J)+X L-1(J+B)WpNl XL(J+B) XL-1(J)-X L-1(J+B)WpNl 式中 p=J2 M-L；J=0,1,，2 L-1-1；L=1,2,，M广西大学机械工程学院广西大学机械工程学院l 下标L表示第L级运算，XL(J)则表示第L级运算后

20、数组元素X(J)的值。如果要用实数运算完成上述蝶形运算，可按下面的算法进行。l 设l T=X L-1(J+B)WpN=TR+jTIl X L-1(J)=XR(J)+jXI(J) l 式中下标R表示取实部，I表示取虚部，22()cos() sin22()cos() sinRRRIIIRITXJBpXJBpNNTXJBpXJBpNN广西大学机械工程学院广西大学机械工程学院( )( )( )( )( )( )( )()( )()( )LRRRRIIIRRRIIIXJXJj JXJXJTXJXJTXJBXJTXJBXJT则则 广西大学机械工程学院广西大学机械工程学院l 4. 编程思想及程序框图图6.2

21、.6 DITFFT运算和程序框图 开 始送入x(n)， MN2 M倒 序L1 , M0 , B 1P2 M LJk J , N1 , 2LpNpNWBkXkXBkXWBkXkXkX)()()()()()(输 出结 束B 2 L1广西大学机械工程学院广西大学机械工程学院l 5. 序列的倒序l DITFFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2n1n0)表示。 图6.2.7 形成倒序的树状图(N=23) 01010101010101(n2n1n0)2000042615371000101100011010

22、11111广西大学机械工程学院广西大学机械工程学院表6.2.1 顺序和倒序二进制数对照表 广西大学机械工程学院广西大学机械工程学院 图6.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)广西大学机械工程学院广西大学机械工程学院 图6.2.9 倒序程序框图 221NNLHJNLHI1 , N1I JTJAJXIAIXT)()()()(J KLHK KJJ2KKKJJNNY广

23、西大学机械工程学院广西大学机械工程学院 在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIFFFT。 设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：10/2 110/2/2 1/2 1(/2)00/2 1/20( ) ( )( )( )( )( )()2 ( )()2NkNnNNknknNNnn NNNknk n NNNnnNkNknNNnX kDFT x nx n Wx n Wx n WNx n Wx nWNx nWx nW五、频域抽取法五、频域抽取法FFT(DIFFFT)广西大学机械工程学院广西大学机械工程学院/21,(

24、 1)1kNkNkWk 偶数 奇数 将X(k)分解成偶数组与奇数组，当k取偶数(k=2r,r=0,1,N/2-1)时 /2 120/2 12/20(2 ) ( )()2 ( )()2NrnNnNrnNnNXrx nx nWNx nx nW(6.2.14)广西大学机械工程学院广西大学机械工程学院当k取奇数(k=2r+1,r=0,1,N/2-1)时/2 1(21)0/2 1/20(21) ( )()2 ( )()2NnrNnNnnrNNnNXrx nx nWNx nx nWW(6.2.15) 将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得/2 11/20/2 12/20

25、(2 )( )(21)( )NrnNnNrnNnXrx n WXrx n W (6.2.16) 广西大学机械工程学院广西大学机械工程学院图6.2.10 DIFFFT蝶形运算流图符号 广西大学机械工程学院广西大学机械工程学院图6.2.11 DIFFFT一次分解运算流图(N=8) N/2点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)广西大学机械工程学院广西大学机械工程学院图6.2.12 DIF

26、FFT二次分解运算流图(N=8) N/4点DFTWN0WN1WN2WN3x(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)WN0WN2WN0WN2N/4点DFTN/4点DFTN/4点DFT广西大学机械工程学院广西大学机械工程学院图6.2.13 DIFFFT运算流图(N=8) WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0X(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)广西大学机械工程学院广西大学机械工程学院图6.

27、2.14 DITFFT的一种变形运算流图WN0WN0WN2WN0X(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)WN0WN2WN1WN3WN2WN0WN0WN0广西大学机械工程学院广西大学机械工程学院图6.2.15 DITFFT的一种变形运算流图WN0WN0WN2WN0X(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)WN0WN2WN1WN3WN2WN0WN0WN0广西大学机械工程学院广西大学机械工程学院l 上述FFT算法流图也可以用于离

28、散傅里叶逆变换(Inverse Discrete Fourier Transform，简称IDFT)。比较DFT和IDFT的运算公式： 1010( ) ( )( )1( ) ( )( )NkNnNknNkX kDFT x nx n Wx nIDFT x nX k WN六、六、IDFT的高效算法的高效算法广西大学机械工程学院广西大学机械工程学院图4.2.16 DITIFFT运算流图 WN0WN1WN2WN3WN0WN0N1x(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)WN2WN2N1N1N1N1N1N1N1广西大学

29、机械工程学院广西大学机械工程学院图4.2.17 DITIFFT运算流图(防止溢出) WN02121x(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)212121WN121WN221WN3212121WN021WN2212121WN021WN22121WN02121WN0212121WN021WN021广西大学机械工程学院广西大学机械工程学院l 如果希望直接调用FFT子程序计算IFFT，则可用下面的方法：l 由于 10101( )( )1( )( )NknNkNknNkx nX k WNx nXk WN对上式两边同时取

30、共轭，得1011( )( )( )NknNkx nXk WDFT XkNN广西大学机械工程学院广西大学机械工程学院6.3 进一步减少运算量的措施进一步减少运算量的措施l 6.3.1 多类蝶形单元运算l 由DITFFT运算流图已得出结论，N=2M点FFT共需要MN/2次复数乘法。l 由(4.2.12)式，当L=1时，只有一种旋转因子W0N=1，所以，第一级不需要乘法运算。 广西大学机械工程学院广西大学机械工程学院l 综上所述，先除去第一、二两级后，所需复数乘法次数应是l 从L=3至L=M共减少复数乘法次数为(2)(2)2MNCM(4.3.1) 13312( )2222MMLLLLNNN(4.3.

31、2) 因此，DITFFT的复乘次数降至 (2)(2)(2)(3)2222MNNNCMM(4.3.3) 广西大学机械工程学院广西大学机械工程学院22(1)()()222()()22()222()()22defjxjyxjyjxyxyj xyRjIRxyIxyyx 广西大学机械工程学院广西大学机械工程学院l 从实数运算考虑，计算N=2M点DITFFT所需实数乘法次数为(2)4(3)2(2)2213(2)102MNNRMNM(4.3.4)广西大学机械工程学院广西大学机械工程学院l 6.3.2 旋转因子的生成l 在FFT运算中，旋转因子WmN=cos(2m/N)-jsin(2m/N)，求正弦和余弦函数

32、值的计算量是很大的。 广西大学机械工程学院广西大学机械工程学院l 6.3.3 实序列的FFT算法 l 设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即1212( )(2 ),( )(21),0,1,12( )( )( ),0,1,12Nx nxnx nxnnNy nx njx n n对y(n)进行N/2点FFT，输出Y(k)，则1122( )( )( ),0,1,1( )( )( )2epopX kDFT x nYkNkXkDFT x njYk 根据DITFFT的思想及式(4.2.7)和(4.2.8)，可得到 12( )( )( ),0,1,2kNN

33、X kX kW Xk k广西大学机械工程学院广西大学机械工程学院l 由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为 ()( ),1,2,12NX NkXk k广西大学机械工程学院广西大学机械工程学院6.4 分裂基分裂基FFT算法算法 l6.4.1 分裂基FFT算法原理 l 当n=pq，且p=N/4，q=4时，n可表示为101010,03,0144NNnpnnnnnn并有 10110/4 13()41000( )( )()4NknNnNNknnNnnX kx n WNxnn W 广西大学机械工程学院广西大学机械工程学院010100/4 13104/4 102404

34、0403304()4 ( )()()423()4NknknNnnNkknknkkNNNWxnn WNNx n Wx nWx nWNx nW WW再将上式中的k表示为10104,01,034Nkkkkk广西大学机械工程学院广西大学机械工程学院可得 1001010100000010010/4 1(4)0040823(4)(4)0404/4 120040403(4)04( )(4) ()()43()()24 ()()()423()4NkknkkkkknNNkknkkknNX kXkkNx nx nWNNx nWx nWWNNx nx nWx nWNx nWW 对k0=0，1,2,3,并用k表示k1，

35、用n表示n0，可以写出广西大学机械工程学院广西大学机械工程学院/4 140/4 140/4 14203(4 ) ( )()()()4243(41) ( )()()()4243(42) ( )()()()424(43) ( )()()(42NknNnNkn nNnNknnNnNNNXkx nx nx nx nWNNNXkx njx nx njx nWNNNXkx nx nx nx nWNNXkx njx nx njx n/4 14303)4014NknnNnNWNk (4.4.1) 广西大学机械工程学院广西大学机械工程学院/2 120/4 140/4 1340(2 ) ( )(),01223(4

36、1) ( )()()()4240143(43) ( )()()()424014NknNnNnknNNnNnknNNnNNXkx nx nWkNNNXkx njx nx njx nWWNkNNNXkx njx nx njx nWWNk(4.4.2) 广西大学机械工程学院广西大学机械工程学院214234( )( )(),01223( ) ( )()()()4243( ) ( )()()()424014nNnNNNx nx nx nnNNNx nx njx nx njx nWNNNxnx njx nx njx nWNn(4.4.3) 令 广西大学机械工程学院广西大学机械工程学院l 则(6.4.2)式

37、可写成如下更简明的形式：/2 12220/4 1141440/4 1242440(2 )( )( ),012(41)( )( ),014(43)( )( ),014NknNnNknNnNknNnNXkx n WDFT x nkNXkxn WDFT x nkNXkxn WDFT xnk(6.4.4) 广西大学机械工程学院广西大学机械工程学院图6.4.1 分裂基第一次分解L形流图 点DFT 点DFT 点DFTx2(1)x2(1 N/4)2N4N4N) 1 (14x) 1 (24x1NW3NWx(1)41Nx21Nx431Nx 1 1 1 j广西大学机械工程学院广西大学机械工程学院l例如，N=16，

38、第一次抽选分解时，由式(6.4.3)得l x2(n)=x(n)+x(n+8), 0n7lx14(n)=x(n)-x(n+8)-jx(n+4)-x(n+12)Wn16, l 0n3lx2 4( n ) = x ( n ) - x ( n + 8 ) + j x ( n + 4 ) -x(n+12)W3n16, l 0n3l 把上式代入式(6.4.4)，可得l X(2k)=DFTx2(n), 0k7 l X(4k+1)=DFTx14(n), 0k3 l X(4k+3)=DFTx24(n), 0k3广西大学机械工程学院广西大学机械工程学院图6.4.2 分裂基FFT算法L形排列示意图与结构示意图(a)

39、分裂基FFT算法L形排列示意图；(b)分裂基FFT算法运算流图结构示意图 ( a )( b )广西大学机械工程学院广西大学机械工程学院图6.4.3 16点分裂基第一次分解L形流图(图中省去箭头) (8)点DFTx2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)点DFT点DFT)0(14x) 1 (14x)2(14x)3(14x)0(24x) 1 (24x)2(24x)3(24x44N44N2Nx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(8)x(9)x(10)x(11)x(12)x(13)x(14)x(15)0NW1NW3NW2NW0NW3N

40、W6NW j j jX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X(8)X(9)X(10)X(11)X(12)X(13)X(14)X(15)X(2k)X(4k1)X(4k3)1111111111广西大学机械工程学院广西大学机械工程学院l 第二次分解：l 先对图4.4.3中N/2点DFT进行分解。l 令X1(l)=X(2l)，则有l X1( 2 l ) = D F T y 2 ( n ) , 0l3 l X1( 4 l + 1 ) = D F T y14( n ) , 0l1 l X1(4l+3)=DFTy24(n), 0l1 广西大学机械工程学院广西大学机械工程学院l 其中

41、ly2(n)=x2(n)+x2(n+4), 0n3ly14( n ) = x2( n ) - x2( n + 4 ) -x2(n+2)x(n+6)Wn8,n=0,1ly24( n ) = x2( n ) - x2( n + 4 ) + jx2(n+2)x2(n+6)W3n8,n=0,1广西大学机械工程学院广西大学机械工程学院图6.4.4 图4.4.4中N/2点DFT的分解L形流图 (4)点DFTx2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)y2(0)y2(1)y2(2)y2(3)X1(0) X(0)X1(2) X(4)X1(4) X(8)X1(6) X(12)

42、X1(1) X(2)X1(5) X(10)X1(3) X(6)X1(7) X(14)X1(2l)X1(4l1 )X1(4l3 )4N)0(14y) 1 (14y) 1 (24y)0(24y12NW32NW j j11111111广西大学机械工程学院广西大学机械工程学院 图6.4.5 4点分裂基L形运算流图 v(0)v(1)v(2)v(3)V(0)V(2)V(1)V(3) j1111广西大学机械工程学院广西大学机械工程学院 图6.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(10)x(11)x(12)x(13)x(14)x

43、(15)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X(8)X(9)X(10)X(11)X(12)X(13)X(14)X(15) j1111 j j1111 j j111111111111 j j j jW 1W 2W 3W 3W 6W 9W 2W 6111111111111NNNNNNNN广西大学机械工程学院广西大学机械工程学院l 6.4.2 分裂基FFT算法的运算量l 设第j级有lj个L形，j=1,2,M-1,M=log2N，则有l1=N/4。由图4.4.2(b)可见，第j-1列中的L形包含了第j列中的一部分结点的计算，即空白部分，所占结点数刚好等于第j-1列中所有L形

44、对应结点的一半，所以第j列L形个数就减少l j-1/2个，即l 广西大学机械工程学院广西大学机械工程学院111223104241(1)424211(1)42424111()(1) 42424jjjijjilNlNlNlNlNlNlNNl广西大学机械工程学院广西大学机械工程学院 由于每个L形有两次复(数)乘运算，所以全部复乘次数为1122212() 3332122log( 1)399MMMjjMNClMNNN (6.4.5) 广西大学机械工程学院广西大学机械工程学院6.5 离散哈特莱变换离散哈特莱变换(DHT) l6.5.1 离散哈特莱变换定义 l 设x(n),n=0,1,N-1，为一实序列，其

45、DHT定义为102( ) ( )( )cos(),0,1,1NHnXkDHT x nx nkn kNN式中，cas()=cos+sin。其逆变换(IDHT)为1012( )( )( )cos(),0,1,1NHHkx nIDHT XkXkkn nNNN (6.5.3) 广西大学机械工程学院广西大学机械工程学院l 逆变换证明如下：1010101022cos()cos()2222cos()sin()cos()sin()2222cos()cos()sin()sin()2222cos()sin()sin()cos()22cos()sinNkNkNkNkknkNNknknkkNNNNknkknkNNNN

46、knkknkNNNNk nN(),0,k nNNnn(6.5.4) 广西大学机械工程学院广西大学机械工程学院l 将式(6.5.2)代入式(6.5.3)得1100110010122( )cos()cos()122( )cos()cos(),01( )0,0NNkNNkNkxkknNNNxknkNNNNxN 广西大学机械工程学院广西大学机械工程学院l 4.5.2 DHT与DFT之间的关系 l 为了便于比较，重写DFT如下：211002110022( ) ( )( )( )cos()sin()1122( )( )( )cos()sin()NNjknNnnNNjknNkkX kDFT x nx n e

47、x nknjknNNx nX k eX kknjknNNNN(4.5.5) (4.5.6) 容易看出，DHT的核函数 DFT的核函数 的实部与虚部之和。 222cos()cos()sin()knknknNNN222cos()()jknNeknjknNN广西大学机械工程学院广西大学机械工程学院l 将XH(k)分解为奇对称分量XHo(k)与偶对称分量XHe(k)之和 ( )( )( )1( )( )()21( )( )()2HHeHoHeHHHoHHXkXkXkXkXkXNkXkXkXNk(6.5.7) (6.5.8)(6.5.9)由DHT定义有10102( )( )cos()2( )( )sin

48、()NHenNHonXkx nknNXkx nknN(6.5.10a)(6.5.10b) 广西大学机械工程学院广西大学机械工程学院l 所以，x(n)的DFT可表示为l同理，x(n)的DHT可表示为l因此，已知x(n)的DHT，则DFT可用下式求得： ( )( )( )HeHoX kXkjXk(6.5.11)( )( )Im( )HeXkHkX k(6.5.12)11( )( )()( )()22HHHHX kXkXNkj XkXNk(6.5.13) 广西大学机械工程学院广西大学机械工程学院l 6.5.3 DHT的主要优点 l (1)DHT是实值变换，在对实信号或实数据进行谱分析时避免了复数运算

49、，从而提高了运算效率，相应的硬件也更简单、更经济；l (2)DHT的正、反变换(除因子1/N外)具有相同的形式，因而，实现DHT的硬件或软件既能进行DHT，也能进行IDHT；l (3)DHT与DFT间的关系简单，容易实现两种谱之间的相互转换。 广西大学机械工程学院广西大学机械工程学院l 6.5.4 DHT的性质 l 1. 线性性质11221212( ),( )( )( )( )( )( )HHHHxXkx nXkax nbx naXkbXk(6.5.14) 2. x(N-n)的DHT( )( ), ()()HHx nXkx NnXNn1022()( )cos()sin(),0,1,1NHnXN

50、kx nknknkNNN (6.5.15)其中，当k=0时，XH(N-k)=XH(N)=XH(0)。广西大学机械工程学院广西大学机械工程学院l 证明 由DHT定义 1010102 ()()cos()2( )cos()22( )cos()sin()NnNnNnDFT x Nnx NnknNx nk NnNx nknknNN而 10102()( )cos() )22( )cos()sin() ()NHnNnXNkx nNk nNx nknknDFT x NnNN广西大学机械工程学院广西大学机械工程学院l 3. 循环移位性质00000022()( )( )cos()()sin()22()( )( )

51、cos()()sin()NNHNNHx nnRnXkknH NkknNNx nnRnXkknH NkknNN(6.5.16) (6.5.17) 证明 由DHT定义有 101010 ()( )2() cos()2( )cos()2222( )cos()cos()sin()sin()2222sin()cos()cos()sin()oNNNoNnNonNoonooDHT x nnRnx nnknNx nk nnNx nknknknknNNNNknknknknNNNN广西大学机械工程学院广西大学机械工程学院1010222( )cos()sin()cos()222( )cos()sin()sin()22

52、( )cos()()sin()NonNonHoHox nknknknNNNx nknknknNNNXkknXNkknNN广西大学机械工程学院广西大学机械工程学院l 4. 奇偶性l 奇对称序列和偶对称序列的DHT仍然是奇对称序列或偶对称序列，即DHT不改变序列的奇偶性。l 5.循环卷积定理1122122121121212( )( ),( )( )( )( )( )( )()( )( )( )( )( )()( )HHHHeHHoHHeHHox nXkx nXkx nx nXk XkXNk Xkx nx nXk XkXNk Xk(6.5.18) (6.5.19) 广西大学机械工程学院广西大学机械工

53、程学院l 证明 下面利用DFT的循环卷积定理和DHT与DFT之间的关系来证明l 其 中 ， X1( k ) = D F Tx1(n),X2(k)=DFTx2(n),根据DHT与DFT之间的关系，则有1212( )( )( )( )DFT x nx nX kXk111222222( )( )( )( )( )( )11( )()()22HeHoHeHoHHHX kXkjXkXkXkjXkXkXNkj XNk广西大学机械工程学院广西大学机械工程学院l 将上面两式代入式(6.5.20)并整理后，得21111211111221211( )( )( )( )( )( )21()( )( )( )( )2

54、( )( )( )Re( )Im( )( )( )()( )HHeHoHeHoHHeHoHeHoHHHeHHoX kXkXkXkjXkjXkXNkXkXkjXkjXkXkDFT x nx nX kX kXk XkXNk Xk所以式(4.5.18)成立。同理可证明式(4.5.19)亦成立。 当x1(n)或x2(n)是偶对称序列时，则由DHT的奇偶性有1212( )( )( )( )( )HHHx nx nXkXk Xk(6.5.21)广西大学机械工程学院广西大学机械工程学院l 6.5.5 DHT的快速算法(FHT) l 1.基2DITFHT算法及运算流图l 仿照快速DFT的分解方法，可通过时域抽取或频域抽取的方式实现快速DHT。 l x(n)的N=2M点DHT如下式：10011122002( )( )cos(),01( )(2 ),01( )(21)222( )(2 )cos(2)(21)cos(21) )NHnNNHrrXkx nknkNN