数字信号处理（第2版）教学课件第4章 快速傅里叶变换

第第 4 4 章章 快速傅里叶变换（快速傅里叶变换（FFTFFT）学习重点了解直接计算 DFT 存在的问题和 FFT 算法的优势。熟练掌握按时间抽取的基-2FFT 算法原理。掌握按频率抽取的基-2FFT 算法原理。了解快速傅里叶反变换（IFFT）算法原理。了解 FFT 算法的在工程上的应用。4.1 引言 DFT 计算量过大，即使采用当时最先进的计算机来处理也无法实现信号的实时处理。在 DFT 算法提出后的很长一段时间内仅停留在理论研究阶段，并没有真正得到广泛的实际应用。1965 年J.W.Cooley（库利）与 J.W.Turkey（图基）在计算数学上发表了著名的论文机器计算傅里叶级数的一种算法，该论文提出了一种计算 DFT 的快速算法（即现在所说的库利-图基算法）,该算法使得 DFT 的计算量下降了 12 个数量级。后来又有桑德-图基等算法的出现，结合当时电子计算机技术的快速发展，很快就发展与完善了一套高效的 DFT 快速算法，也就是现在普遍称之为 FFT（Fast Fourier Transform）的算法，使 DFT 的运算在实际中得到广泛应用，也标志着数字信号处理这门新兴学科的正式诞生。多年来，人们继续寻求更快、更灵活的高效算法，各种 FFT 算法层出不穷，使 DFT 的运算效率进一步提高。本章主要讨论最基本的也是最重要的基-2FFT 算法。4.2 基-2FFT 算法4.2.1 直接计算 DFT 的特点及减少运算量的基本途径1直接计算的问题【例】如果一台通用计机算平均每次复乘需 100us，每次 复加需 20us，用来直接计算 N=1024 点的 DFT。问直接运算需多少时间？解：直接运算 N 点 DFT 共需复数乘法 N 2 次，复数加法 N(N 1)次，因此直接运算 DFT 所用的计算时间为直接运算 N 点 DFT 共需:复数乘法 N 2 次 复数加法 N(N 1)次2改进途径周期性：利用 的性质，把长度为 N 点的大点数的 DFT 运算依次分解为若干个小点数的 DFT。使计算量变小。对称性：可约性：特殊点：4.2.2 按时间抽取法的基-2 FFT（DIT-FFT）基本原理按n的奇偶把x(n)分解为两个N/2点的子序列 则x(n)的DFT为由于所以 其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即 由于X1(k)和X2(k)均以N/2为周期，且 ，所以X(k)又可表示为 蝶形运算符号用蝶形运算符号表示 DFT 的分解运算两个 N/2 点 DFT 组成一个 N 点 DFT 与直接计算 N 点的 DFT 计算量相比，几乎节省了一半的计算量。N 2M,因此 N 仍然是 2 的整数次幂，故可以对 N 点 DFT 再做进一步分解。与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即那么，X1(k)又可表示为 式中 同理，由X3(k)和X4(k)的周期性和Wm N/2的对称性 Wk+N/4 N/2=-Wk N/2 最后得到：将一个 N/2 点 DFT 分解为两个 N/4 点 DFT 用同样的方法可计算出(4.2.11)其中 将一个 N 点 DFT 分解成四个 N/4 点 DFT2 点 DFT 也就是一个蝶形运算，运算流图如下所示。N=8 点的按时间抽取基-2 FFT 运算流图4.2.3 DIT-FFT 算法特点与运算量1蝶形运算2原位计算3序数重排4蝶形运算两个输入数据的“距离”当 N 2M 时，则共有 M 级蝶形运算。第 L 级运算，每个蝶形的两个输入数据的“距离”为 2L-1。5旋转因子的变化规律 每级都有 N/2 个蝶形，每个蝶形都要乘以因子，称其为旋转因子WNp，其中 p 称为旋转因子的指数。第 L 级蝶形运算，共有 2 L-1个不同的旋转因子 6.DITFFT运算量 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为复数加次数为 例如，N=210=1024时令4.2.4 按频域抽取的基-2 FFT（DIF-FFT）基本原理设序列 x(n)的长度为 N 2M，将 x(n)前后对半分开，得到两个子序列 x(n)和则 x(n)的 N 点 DFT 可表示为如下形式其中（4-14）将 X(k)按自变量 k 分解成偶数组 X(2r)和奇数组 X(2r+1)，（4-16）显然 x1(n)和 x2(n)均为 N/2 点序列，将式（4-16）代入式（4-15），得（4-15）4.2.4 频域抽取法FFT(DIFFFT)在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIFFFT。设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：偶数 奇数 将X(k)分解成偶数组与奇数组，当k取偶数 (k=2r,r=0,1,N/2-1)时 当k取奇数(k=2r+1,r=0,1,N/2-1)时 将x1(n)和x2(n)分别代入以上两式，可得 DIFFFT蝶形运算流图符号 DIFFFT一次分解运算流图(N=8)DIFFFT二次分解运算流图(N=8)N=8 点 DIF-FFT 运算流图DIF-FFT 算法的运算量：与 DIT-FFT 算法的运算量完全相同4.2.5 IDFT 的高效算法由 FFT 算法得到 IFFT 算法，需要做以下改变。1将 FFT 算法中旋转因子 WN 变为 。2在 FFT 的每级蝶形运算中都分别乘以因子 1/2。3输入变量的改变，对整体算法的实现影响不大，但算法名称有相应变化直接运用 FFT 来实现 IFFT 由上面表达式可以看到，完全不需要改动 FFT 程序，而是直接利用它做 IFFT，分以下三个步骤：将 X(k)取共轭得到 X (k)；然后对 X(k)的共轭 X (k)直接做 FFT（采用 FFT 算法程序）最后再对 FFT 的运算结果取共轭并乘以 1/N，得到 x(n)。采用这种方法来计算反变换 IFFT 虽然用了两次取共轭运算，但可以与 FFT 共用同一子程序，因而用起来很方便。因此 设设序序列列h(n)长长度度为为N，x(n)为为无无限限长长序序列列。将将x(n)均均匀分段，匀分段，每段长度取每段长度取M，则：则：于是，于是，h(n)与与x(n)的线性卷积可表示为：的线性卷积可表示为：其中：其中：该式说明，计算该式说明，计算h(n)与与x(n)的线性卷积时，的线性卷积时，可先进行分段线性卷可先进行分段线性卷积积yk(n)，然后把分，然后把分段卷积结果叠加起来段卷积结果叠加起来即可。即可。重叠相加法卷积示意图重叠相加法卷积示意图 每一分段卷积每一分段卷积yk(n)的长度为的长度为N+M-1，因此，因此yk(n)与与yk+1(n)有有N-1个点重叠，必须把重叠的部分相个点重叠，必须把重叠的部分相加，才能得到完整的卷积序列加，才能得到完整的卷积序列y(n)。由图由图3.4.4可以看出，当第二个分段可以看出，当第二个分段卷积卷积y1(n)计算完后，叠加重叠点便计算完后，叠加重叠点便可得输出序列可得输出序列y(n)的前的前2M个值，同个值，同样，分段卷积样，分段卷积yi(n)计算完后，就可计算完后，就可得到得到y(n)第第 i 段的段的M个序列值。个序列值。v 显然可用快速卷积法计算分段显然可用快速卷积法计算分段卷积，快速卷积的计算区间为卷积，快速卷积的计算区间为L N+M-1。v这种方法不要求大的存贮容量，这种方法不要求大的存贮容量，而且运算量和延时也大大减少。而且运算量和延时也大大减少。