信号与系统分析基础 非信息类专业 潘文诚 等 第6章 快速傅里叶变换新.pptVIP

第6章 快速傅里叶变换 第6章 快速傅里叶变换 6.1直接计算DFT的问题及改进的途径 根据上一章的内容，我们知道DFT为利用数字计算机对傅里叶变换进行分析和计算提供了重要途径。但在实际应用中，随着序列长度N的增加，DFT巨大的计算量使其在对信号分析的实时性要求较高的情况下，遇到了瓶颈。在这一小节，我们首先对DFT的所需要的计算量进行分析，然后给出减少计算量的基本思路。 比较式（6.1.1）和（6.1.2），可以看出DFT的反变换公式与正变换的差别仅在于旋转因子WN的指数符号取负 将上式进一步展开，可以得到 2.减少计算量的思路 大多数改善DFT计算效率的方法均利用了旋转因子WN的周期性、对称性和可约性。利用周期性和对称性我们可以得到 6.2按时间抽取（DIT）的基2FFT算法 根据上一小节的分析，我们知道在计算序列的DFT时，若能将整个序列逐次分解成较短的序列进行DFT计算，将在很大的程度上提高计算效率。按时间抽取的FFT正是基于这种思路，将原序列分解成若干个短小序列，计算这些短小序列的DFT，再将它们的结果组合得到原序列的DFT。在这一小节中，我们介绍这种算法的原理并讨论它的工作效率。 通常假设序列x(n)的长度为2的整数幂，即N =2L，若序列长度不满足此条件，可以通过补零使之满足这一条件。 而从图6-2 可以看出，将一个长度为N的序列分解成两个 由于原序列x(n)的长度为2L，因此分解之后两个序列的长 同样方法将序列分成两个 通过前面的分析，我们知道，经过这次分解之后，DFT的运算量又减少了大约一半。当然，我们还可以继续分解下去，直至子序列的长度为2。因此，对于任意长度序列x(n) ，我们都可以将其分解成若干个两点序列，然后对这些两点序列的DFT进行计算，最后再将它们的结果通过蝶形算符层层组合起来，得到序列的DFT，因此这种方法称为“基-2FFT”。图6-3给出了一个8点序列的基-2FFT的运算流图。 注意上图中的两点DFT运算，例如： 其他两点DFT X12(k)，X21(k)和X22(k)。因此两点DFT也可以利用一个蝶形运算符来表示。将图6-3中的两点DFT运算框替换成蝶形符，如图6-4所示。 从图6-4可以看出，当 ：当N=2L时，共有L级蝶形运算， 根据上式，可以看出，随着N的增大FFT对运算量的改善越发突出。表6-1给出了当N取不同值时，FFT算法与DFT算法的计算量及它们之间的比值。当N=2时，DFT的运算量是FFT运算量的4倍，而当N=1024时，DFT的运算量是FFT运算量的204倍，FFT对DFT运算效率的提高非常显著。 【例6-1】若使用某DSP处理芯片来计算2048点DFT，已知一次复数乘法运算需要400ns，一次复数加法运算需要100ns，则直接计算DFT需要多少时间？采用基-2 DIT FFT需要多少时间？ 【解】 直接计算DFT所需的复数乘法运算时间为 TD1=400ns×N2=400ns×20482=1.6777s 直接计算DFT所需的复数加法运算时间为 TD2=100ns×N(N－1)=100ns×2048(2048－1)=0.4192s 因此，直接计算DFT所需的时间为 TD=TD1＋TD2=1.6777s ＋ 0.4192s=2.0969s FFT运算所需的复数加法运算时间为 TF2=100ns×Nlog2N=100ns×2048log22048=0.0023s 因此，FFT运算所需的时间为 TF=TF1 ＋TF2=0.0045s ＋0.0023s=0.0068s 6.3 按频率抽取（DIF）的基2FFT算法 在上一小节中，我们讨论了对有限长序列 x(n)在时域上根据n的奇偶性将它分成若干个长度为2的短序列，实现了对DFT运算量的大幅度改善。考虑到，N点有限长序列的DFT X(k)在频域上也是一个长度为N的有限序列。因此，类似于时域的抽取方法，我们可以对序列X(k)在频域上按序号k的奇偶性，将其分解成若干个长度为2的短序列。经过这样的分解后，所需的运算量与DIT方式相同，这种方法我们称为按频率抽取（DIF）的基2FFT算法。 假设序列的长度N = 2L， L为正整数。在把输出N=2L ， L为正整数。在把输出 X(K)按序号k的奇偶性分组之前，先 由于 式(6.3. 2)为前一半输入和后一半输入之和的N/2点DFT，式(6.3. 3)为前一半输入和后一半输入之差与WNn乘积的N/2点DFT。令 式（6.3. 4）可以用蝶形运算表示，如图6-5所示。 这样，我们把一个N点的DFT按频域