数字信号处理快速傅立叶变换.pptx

《数字信号处理快速傅立叶变换.pptx》由会员分享，可在线阅读，更多相关《数字信号处理快速傅立叶变换.pptx（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.1 4.1 引引 言言DFTDFT是数字信号分析与处理中的一种重要变换。但直接计算DFTDFT的计算量与变换区间长度N N的平方成正比，当N N较大时，计算量太大，所以在快速傅里叶变换FFT(Fast Fourier Transform)FFT(Fast Fourier Transform)出现以前，直接用DFTDFT算法进行谱分析和信号的实时处理是不切实际的。直到19651965年提出DFTDFT的一种快速算法以后，情况才发生了根本的变化。第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第1页/共79页4.2 4.2 基基2FFT2FFT算法算法 4.2.1 4.2.1 直

2、接计算DFTDFT的特点及减少运算量的基本途径两者的差别仅在指数的符号和因子两者的差别仅在指数的符号和因子1/N.1/N.1.1.直接计算直接计算DFTDFT的运算量的运算量第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第2页/共79页 计算一个计算一个X(k)X(k)的值：的值：N N次复数乘法运算次复数乘法运算 N-1 N-1 次复数加法运算次复数加法运算.一个一个X(k)X(k)的值的工作量的值的工作量,如如X(1)X(1)N N点点DFTDFT运算量：运算量：复数乘法：复数乘法：N N2 2 复数加法：复数加法：N(N-1)N(N-1)第第4 4章章 快速傅立叶变换（快

3、速傅立叶变换（FFTFFT）第3页/共79页2 2 改进的途径改进的途径的对称性、周期性、可约性的对称性、周期性、可约性对称性:可约性:周期性:第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第4页/共79页4.2.2 4.2.2 时域抽取法基2FFT2FFT基本原理 算法原理算法原理(一一)N/2)N/2)N/2)N/2点点DFTDFTDFTDFT1.1.1.1.先将先将先将先将x(n)x(n)x(n)x(n)按按按按n n n n的奇偶分为两组作的奇偶分为两组作的奇偶分为两组作的奇偶分为两组作DFT,DFT,DFT,DFT,设设设设N=2N=2N=2N=2M M M M,这样

4、有这样有这样有这样有:n n n n为偶数时为偶数时为偶数时为偶数时:n n n n为奇数时为奇数时为奇数时为奇数时:第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第5页/共79页(n为偶数)(n为奇数)第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第6页/共79页 (1)X(1)X1 1(k),X(k),X2 2(k)(k)均为N/2N/2点的DFTDFT。(2)X(k)=X(2)X(k)=X1 1(k)+W(k)+WN Nk k X X2 2(k)(k)只能确定出X(k)X(k)的k=0.1k=0.1.N/2-1.N/2-1 个，即前一半的结果。2.2.2.

5、2.两点结论两点结论两点结论两点结论第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第7页/共79页3.X(k)3.X(k)的后一半的确的后一半的确定定由于X1(k)和X2(k)均以N/2为周期，得 可可可可见见,X(k)X(k)X(k)X(k)的后一半，也完全由的后一半，也完全由X X X X1 1 1 1(k)(k)(k)(k),X X X X2 2 2 2(k)(k)(k)(k)的前的前一半所确定。一半所确定。*N N点的点的DFTDFT可由两个可由两个N/2N/2点的点的DFTDFT来计算。来计算。第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第8页/共7

6、9页实现上式运算的流图称作蝶形运算（N/2个蝶形)4.4.蝶形运算蝶形运算(前一半)(后一半)1 1 11-1-11次 复乘2次复加第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第9页/共79页图4.2.1 蝶形运算符号 第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第10页/共79页例如例如例如例如 N=8 N=8 N=8 N=8 时的时的时的时的DFT,DFT,DFT,DFT,可以分解为两个可以分解为两个可以分解为两个可以分解为两个N/2=4N/2=4N/2=4N/2=4点的点的点的点的DFT.DFT.DFT.DFT.具体方法如下具体方法如下具体方法如下具体

7、方法如下:(1)n为偶数时为偶数时,记作记作:第11页/共79页(2)n(2)n为奇数时为奇数时为奇数时为奇数时,分别记作分别记作分别记作分别记作:第12页/共79页点DFT点DFT-1-1-1-1一个一个N N点点DFTDFT分解为两个分解为两个N N/2/2点点DFTDFT的信号流图的信号流图 第13页/共79页图4.2.2 N点DFT的一次时域抽取分解图(N=8)第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第14页/共79页经过一次分解后，计算1个N点DFT共需要计算两个N/2点DFT和N/2个蝶形运算。而计算一个N/2点DFT需要(N/2)2次复数乘法和N/2(N/2

8、1)次复数加法。所以，计算N点DFT时，总共需要的复数乘法次数为 5.5.一次抽取运算量一次抽取运算量第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第15页/共79页 由于由于N=2N=2M M,所以所以 N/2N/2仍为偶数仍为偶数,可以进一步把每个可以进一步把每个N/2N/2点的序点的序列再按其奇偶部分分解为两个列再按其奇偶部分分解为两个N/4N/4的子序列。的子序列。(二)N/4)N/4点DFTDFT 与与第第一一次次分分解解相相同同，将将x x1 1(r)(r)按按奇奇偶偶分分解解成成两两个个N/4N/4长长的的子子序列序列x x3 3(l)(l)和和x x4 4(l)

9、(l)，即，即那么，X1(k)又可表示为 第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第16页/共79页式中 同理，由X3(k)和X4(k)的周期性和Wm N/2的对称性 Wk+N/4 N/2=-Wk N/2 最后得到：(4.2.10)第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第17页/共79页用同样的方法可计算出(4.2.11)其中 第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第18页/共79页点DFT点DFT-1-1-1-1第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第19页/共79页点DFT第第4 4章章 快速傅立

10、叶变换（快速傅立叶变换（FFTFFT）第20页/共79页偶中偶偶中奇DFT-1-1N/2N/2点点DFTDFT分解为两个分解为两个N/4N/4点点DFTDFT的信号流图的信号流图 DFT第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第21页/共79页奇中偶奇中奇-1-1DFTDFT第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第22页/共79页点DFT点DFT-1-1-1-1-1-1 点点DFT 点点DFT 点点DFT-1 点点DFT第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第23页/共79页-1-1-1-1-1-1-1 点点DFT-1 点点

11、DFT 点点DFT 点点DFT一个一个N N=8=8点点DFTDFT分解为四个分解为四个N N/4/4点点DFTDFT的信号流图的信号流图 第24页/共79页图4.2.3 N点DFT的第二次时域抽取分解图(N=8)第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第25页/共79页(三)N/4)N/4点DFTDFT第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第26页/共79页第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第27页/共79页-1-1-1-1-1-1-1-1-1 点点DFT 点点DFT 点点DFT 点点DFT-1-1-1第第4 4章章

12、快速傅立叶变换（快速傅立叶变换（FFTFFT）第28页/共79页 图4.2.4 N点DITFFT运算流图(N=8)第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第29页/共79页4.2.3 DITFFT4.2.3 DITFFT算法与直接计算DFTDFT运算量的比较l 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为复数加次数为 例如，N=210=1024时第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第30页/共79页图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线 第第4 4章章 快速傅

13、立叶变换（快速傅立叶变换（FFTFFT）第31页/共79页 1.1.原位计算原位计算 由图4.2.4可以看出，DITFFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。在N点DIT-FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子，称其为旋转因子，p为旋转因子的指数。但各级的旋转因子和循环方式都有所不同。为了编写计算程序，应先找出旋转因子与运算级数的关系。用L表示从左到右的运算级数(L=1，2，M)。观察图4.2.4不难发现，第L级共有2L1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：4.2.4 DITFFT的运算规律及编程思想 2

14、2旋转因子的变化规律旋转因子的变化规律第32页/共79页对N=2M的一般情况，第L级的旋转因子为第33页/共79页3.3.蝶形运算规律蝶形运算规律 设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：AL(J)AL-1(J)+A L-1(J+B)WpN AL(J+B)AL-1(J)-A L-1(J+B)WpN式中 p=J2 M-L；J=0,1,，2 L-1-1；L=1,2,，M 下标L表示第L级运算，AL(J)则表示第L级运算后数组元素A(J)的值。而AL1(J)表示第L级运算前A(J)的值（即第L级蝶形的输入数据）

15、第34页/共79页 4.4.编程思想及程序框图编程思想及程序框图图4.2.6 DITFFT运算和程序框图 第35页/共79页 DITFFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2n1n0)表示。图4.2.7 形成倒序的树状图(N=23)5.5.序列的倒序序列的倒序第36页/共79页表4.2.1 顺序和倒序二进制数对照表 第37页/共79页 图4.2.8 倒序规律 第38页/共79页 图4.2.9 倒序程序框图 第39页/共79页4.2.5 4.2.5 4.2.5 4.2.5 频域抽取法频域抽取法FFT

16、FFTFFTFFT（DIT_FFT)DIT_FFT)DIT_FFT)DIT_FFT)算法原理算法原理(一一)N/2)N/2点点DFTDFT第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第40页/共79页第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第41页/共79页k k为偶数时：k k为奇数时：第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第42页/共79页 可见,上面两式均为N/2的DFT。第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第43页/共79页-1-1(二二)蝶形运算蝶形运算第第4 4章章 快速傅立叶变换（快速傅立叶

17、变换（FFTFFT）第44页/共79页图4.2.10 DIFFFT蝶形运算流图符号 第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第45页/共79页 N=8 N=8时时,按按k k的奇偶分解过程先蝶形运算的奇偶分解过程先蝶形运算,后作后作DFT:DFT:-1 1-1 1-1-1-1 1第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第46页/共79页X(0)X(6)X(4)X(2)X(1)X(5)X(3)X(7)0NW1NW2NW3NW-1 1-1 1-1 1-1 1x(0)x(3)x(1)x(2)x(4)x(5)x(6)x(7)0NW2NW2点DFT-1 1-1

18、 12NW0NW-1 1-1 12点DFT2点DFT2点DFT 仿照按时间抽取的方法，再将仿照按时间抽取的方法，再将N/2N/2点点DFTDFT按按k k的的奇偶分解为两个奇偶分解为两个N/4N/4点的点的DFTDFT第47页/共79页如此进行下去如此进行下去,直至分解为直至分解为2 2点点DFTDFT-1 1-1 1-1 1-1 1-1 1-1 1-1 1-1 1-1 1-1 1-1 1-1 1第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第48页/共79页图4.2.11 DIFFFT一次分解运算流图(N=8)第49页/共79页图4.2.12 DIFFFT二次分解运算流图(N

19、=8)第50页/共79页图4.2.13 DIFFFT运算流图(N=8)第51页/共79页 FFTFFT算法的特点算法的特点l分级运算分级运算l同址运算同址运算l倒序输入，顺序输出倒序输入，顺序输出(DIT),(DIT),正序输入，正序输入，倒序输出倒序输出(DIF)(DIF)lDIT-FFTDIT-FFT蝶形先乘后加蝶形先乘后加(减减)，而，而DIF-DIF-FFTFFT蝶形先加蝶形先加(减减)后相乘。后相乘。第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第52页/共79页v 利用利用FFT计算计算IFFT的思路的思路1 14.2.6 IDFT4.2.6 IDFT4.2.6 I

20、DFT4.2.6 IDFT的高效算法的高效算法第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第53页/共79页把把FFT的时间抽取法，用于的时间抽取法，用于IDFT运算时，由于运算时，由于输入变量由时间序列输入变量由时间序列x(n)改成频率序列改成频率序列X(k)，原原来按来按x(n)的奇、偶次序分组的时间抽取法的奇、偶次序分组的时间抽取法FFT，现在就变成了按现在就变成了按X(k)的奇偶次序抽取了。的奇偶次序抽取了。频率抽取的频率抽取的FFT运算用于运算用于IDFT运算时，也应改运算时，也应改变为时间抽取的变为时间抽取的IFFT。第第4 4章章 快速傅立叶变换（快速傅立叶变换

21、（FFTFFT）第54页/共79页图4.2.16 DITIFFT运算流图 第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第55页/共79页图4.2.17 DITIFFT运算流图(防止溢出)第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第56页/共79页此DFT可用FFT程序v 利用利用FFT计算计算IFFT的思路的思路2直接调用FFT子程序计算IFFT的方法：共轭FFT共轭乘1/N第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第57页/共79页-1-1-1-1例：有限长序x(n)=1,2,-1,3按FFT运算流图求X(k)，在由X(k)按IFFT

22、反求x(n)DFT过程：第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第58页/共79页IDFT过程：-1-1-1-11/41/41/41/4第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第59页/共79页由DIT-FFT运算流图已得出结论，N=2M点FFT共需要MN/2次复数乘法。由(4.2.12)式，当L=1时，只有一种旋转因子 ，所以，第一级不需要乘法运算。当L=2 时，共有两个旋转因子：和 ，因此，第二级也不需要乘法运算。在DFT中，又称其值为1和j的旋转因子为无关紧要的旋转因子，如 ，等。4.3 4.3 进一步减少运算量的措施进一步减少运算量的措施4.

23、3.1 4.3.1 4.3.1 4.3.1 多类蝶形单元运算多类蝶形单元运算第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第60页/共79页先除去第一、二两级后，所需复数乘法次数应是当L=3时，有两个无关紧要的旋转因子和，因为同一旋转因子对应着2ML=N/2L个碟形运算，所以第三级共有2N/23=N/4 个碟形不需要复数乘法运算。依此类推，当L3时，第L级的2个无关紧要的旋转因子减少复数乘法的次数为2N/2L=N/2L1。这样，从L=3至L=M共减少复数乘法次数为(4.3.1)第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第61页/共79页(4.3.2)下面再讨

24、论FFT中特殊的复数运算，以便进一步减少复数乘法次数。一般实现一次复数乘法运算需要四次实数乘，两次实数加。但对这一特殊复数，任一复数(x+jy)与其相乘时，因此，DIT-FFT的复乘次数降至(4.3.3)第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第62页/共79页第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第63页/共79页只需要两次实数加和两次实数乘就可实现。这样，对应的每个蝶形节省两次实数乘。在DIT-FFT运算流图中，从L=3至L=M级，每级都包含旋转因子 ，第L级中，对应N/2L个蝶形运算。因此从第三级至最后一级，旋转因子 节省的实数乘次数与(4.

25、3.2)式相同。所以从实数乘运算考虑，计算N=2M点DIT-FFT所需实数乘法次数为(4.3.4)第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第64页/共79页若包含了所有旋转因子，则称该算法为一类碟形单元运算；若去掉的旋转因子，则称之为二类碟形单元运 算；若再判断处理，则称之为四类碟形运算。若再去掉的旋转因子，则称为三类碟形单元运算；后三种运算称为多类碟形单元运算。显然，碟形单元类型越多，编程就越复杂，但当N较大时，乘法运算的减少量是相当可观的。例如，N=4096时，三类碟形单元运算的乘法次数为一类碟形单元运算的75%。第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFT

26、FFT）第65页/共79页l在FFT运算中，旋转因子l，求正弦和余弦函数值的计算量是很大的。所以编程时，产生旋转因子的方法直接影响运算速度。4.3.2 4.3.2 4.3.2 4.3.2 旋转因子的生成旋转因子的生成l产生旋转因子的方法产生旋转因子的方法:l1.在每级运算中直接产生；l2.在FFT程序开始前预先计算出，m=0，1，N/21，存放在数组中，作为旋转因子表，在程序执行过程中直接查表得到所需旋转因子值，不再计算。这样使运算速度大大提高，其不足之处是占用内存较多。第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第66页/共79页在实际工作中，数据x(n)常常是实数序列。如

27、果直接按FFT运算流图计算，就是把x(n)看成一个虚部为零的复序列进行计算，这就增加了存储量和运算时间。4.3.34.3.34.3.34.3.3 实序列的实序列的FFTFFTFFTFFT算法算法l处理该问题的方法有三种处理该问题的方法有三种:l早期提出的方法是用一个N点FFT计算两个N点实序列的FFT，一个实序列作为x(n)的实部，另一个作为虚部，计算完FFT后，根据DFT的共轭对称性，由输出X(k)分别得到两个实序列的N点DFT。l第二种方法是用N/2点FFT计算一个N点实序列的DFT。l第三种方法是用离散哈特莱变换（DHT）1。第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）

28、第67页/共79页设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即对y(n)进行N/2点FFT，输出Y(k)，则用用N/2N/2点点FFTFFT计算一个计算一个N N点实序列的点实序列的DFTDFT的原理：的原理：第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第68页/共79页由于x(n)为实序列，因此X(k)具有共轭对称性，X(k)的另外N/2点的值为：根据DIT-FFT的思想及式(4.2.7)和(4.2.8)，可得到X(k)的前 个值：(4.3.5)其中：第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第69页/共7

29、9页 计算 点FFT的复乘次数为 ，计算式(4.3.5)的复乘次数为，所以用这种算法,计算X(k)所需复数乘法次数为。相对一般的N点FFT算法，上述算法的运算效率为，当N=2M=210时，=20/11，运算速度提高近1倍。第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第70页/共79页 本章仅介绍算法最简单、编程最容易的基2FFT算法原理及其编程思想，使读者建立快速傅里叶变换的基本概念，了解研究FFT算法的主要途径和编程思路。其他高效快速算法请读者参考文献1、3、12。例如，分裂基FFT算法、离散哈特莱变(换DHT)、基4FFT、基8FFT、基rFFT、混合基FFT，以及进一步

30、减少运算量的途径等内容，对研究新的快速算法都是很有用的。本节简要介绍其他几种快速算法的运算量及其主要特点，以便读者选择快速算法时参考。4.4 4.4 其他快速算法简介其他快速算法简介第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第71页/共79页l从理论上讲，不同基数的FFT算法的运算效率不同，实际中最常用的是基2FFT、基4 FFT、分裂基FFT和DHT 1。为此，下面简要介绍后三种FFT算法的特点和运算效率，以扩展读者的视野。其具体算法请参考文献1、12。l在基rFFT算法中，基4FFT算法运算效率与基8FFT很接近，但基4FFT算法实现程序简单，且判断开销少。可以证明，当

31、FFT的基大于4时，不会明显降低计算量。基4FFT要求N=4M，M为自然数。其复数乘法次数为12（4.4.1）CM(基4)其中未计入乘以j和1的计算。第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第72页/共79页比较基2FFT的复数乘法次数 ，基4FFT的复数乘法次数减少25%。1984年，法国的杜梅尔（P.Dohamel）和霍尔曼（H.Hollmann）将基2分解和基4分解糅合，提出了分裂基FFT算法，其复数乘法次数接近FFT理论最小值，但其运算流图却与基2FFT很相似，编程简单，运算程序也很短，是一种很实用的高效算法。分裂基FFT算法复数乘法次数为2CM(分裂基)=（4.

32、4.2）第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第73页/共79页l 只考虑（4.4.2）式的第一项，分裂基FFT算法的复数乘法次数就比基2FFT减少33%，比基4FFT减少11%。应当说明，在比较时，未考虑（4.4.2）式后2项减少的运算量，所以分裂基FFT算法的效率更高。由此可见，分裂基FFT算法的效率最高，所以得到广泛应用。l但是，对实序列x(n)，上述各种FFT算法仍将其看成虚部为零的复序列存储和计算。而一次复数乘法需要四次实数乘法和二次实数加法。所以，必然浪费存储资源和增加多余的运算量。我们知道，实序列的N点DFT具有共轭对称性，即l第第4 4章章 快速傅立叶变

33、换（快速傅立叶变换（FFTFFT）第74页/共79页所以，只要计算出X（k）的前面N/2个值，则其后面的N/2个值可以由对称性求得。因此，FFT算法得到的N个X（k）值有一半是多余的。离散哈特莱变换（DHT）就是针对实序列的一种高效变换算法，相对一般的FFT算法，DHT的快速算法FHT可以减少近一半的计算量1。N点基2时域抽取快速DHT（基2DIT-FHT）算法的实数乘法次数为1（4.4.3）第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第75页/共79页N点基2DIT-FHT算法的实数加法次数为1应当说明，DHT是与DFT不同的变换，所以要想得到实序列DFT，还要根据二者的关

34、系式进行转换。下面会看到该关系非常简单。（4.4.4）可见，基2DIT-FHT算法的实数乘法次数约为基2DIT-FFT算法的一半。与前面三种FFT算法比较，对实序列，基2DIT-FHT算法的实数乘法次数最少。第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第76页/共79页DHTDHT具有以下主要优点：具有以下主要优点：(1)DHT是实数变换，在对实信号进行处理时避免了复数运算，运算效率高，且实现硬件简单经济。(2)DHT的正、逆变换（除了因子1/N外）具有相同的形式，所以实现硬件或程序亦相同。（4.4.5）N点DHT定义如下：（4.4.6）第第4 4章章 快速傅立叶变换（快速傅

35、立叶变换（FFTFFT）第77页/共79页(4)DHT与DFT之间的关系非常简单，容易实现二者之间的转换，关系式如下：(3)DHT满足循环卷积定理，所以，可以直接用FHT实现实序列的快速卷积，大大提高处理速度，并使处理硬件简化。所以对实信号x(n)x(n)进行谱分析时，可以先对x(n)x(n)进行FHT,FHT,得到XH(k)=DHTx(n)XH(k)=DHTx(n)N N,然后再将H H(k)(k)转换成X(k)=DFTx(n)X(k)=DFTx(n)N N，这样可以提高分析速度，减少存储空间。（4.4.7）第第4 4章章 快速傅立叶变换（快速傅立叶变换（FFTFFT）第78页/共79页感谢您的观看！第79页/共79页