快速傅里叶变换幻灯片.pptx

2 第7章 快速傅里叶变换 7.1 引言 7.2 直接计算DFT的问题及改进的途径 7.3.1 按时间抽取（DIT）的基-2FFT算法 7.3.2 按频率抽取（DIF）的基-2FFT算法 补充内容： IDFT的高效算法 补充内容：实序列的FFT算法 3 7.1 引言 有限长序列通过离散傅里叶变换（DFT）将其频域离 散化成有限长序列，但其计算量太大，很难实时处理，因此 引出了快速傅里叶变换（FFT）。 FFT并不是一种新的变换形式，它只是DFT的一种快 速算法，并且根据对序列分解与选取方法的不同产生了多种 算法。 FFT在离散傅里叶反变换、线性卷积和线性相关等方 面也有重要应用。 4 4 7.2 直接计算DFT的问题及改进的途径 7.2.1 直接计算DFT的运算量问题 若x(n)是N点序列，实现x(n)的DFT，即求出N个X(k)， 需要N2次复数乘法，N(N-1)次复数加法。 5 5 一个复数乘法包括4个实数乘法和2个实数加法。一次复数加法需二次实数加法。 例如： x(n) N=1024，N2=1048576 因而每运算一个X(k)需4N次实数乘法和2N+2(N-1)=2(2N-1)次实数加法。 所以，整个DFT运算总共需要4N2次实数乘法和2N(2N-1)次实数加法。 (a+jb)(c+jd)=(ac-bd)+j(bc+ad) 6 解决耗时的乘法问题是将数字信号处理理论用于实际的 关键问题。特别是40年前，计算机的速度相当慢。因此，很 多学者对解决DFT的快速计算问题产生了极大的兴趣。 Cooley J W, Tukey J W. An algorithm for the machine computation of complex Fourier series. Mathematics of Computation, 1965, pp297~301 7 7.2.2 改善途径 FFT的思路： 如何充分利用这些关系 对称性 周期性 8 以四点DFT为例 9 10 利用WNnk的对称性和周期性，将大点数的DFT分解成若 干个小点数的DFT，FFT正是基于这个基本思路发展起来的。 分类：按时间抽取（DIT）算法和按频率抽取（DIF） 算法。 问题是如何分最有效？ N点DFT N/2点DFT N/4点 DFT 2点 DFT 1个 2个 4个 N/2个 Decimation in Time Decimation in Frequency 11 12 7.3 .1按时间抽取（DIT）的基-2FFT算法 1.算法原理 设序列x(n)长度为N＝2M，M为整数，将x(n)（n=0,1… N-1）按n的奇偶分解成两组N/2点的子序列 x1(r)= x(2r) x2(r)= x(2r+1) r =0,1…N/2-1（长度为N/2） 则 13 X1(k)、X2(k)都是 N/2 点的 DFT，它们各自又可分成 N/4 点的DFT，如此继续分下去，直至两点DFT。两点DFT 不需要乘法运算： 2点DFT的运算流图 15 由于每一步分解都是按输入序列在时间上的奇偶次序， 分解成两个半长的子序列，所以称“按时间抽取算法”。 蝶形运算单元 16 2.运算量比较 对N=2M，共可分M次，即m =0,1…M-1，每一级有N/2 个如下的蝶形单元 一个蝶形单元只需一次复数乘法，两次复数加法。 总共复数乘法： 复数加法： 可以共享 17 直接计算DFT与FFT算法的计算量之比为 18 3.算法特点 1）原位运算 两点构成一个蝶形单元，并且这两点不再参与别的蝶形 单元的运算。 所谓原位运算，就是当数据输入到存储器后，每一级运 算的结果仍然贮存在这同一组存储器中，直到最后输出，中 间无需其它存储器。 19 2）旋转因子的变化规律 (4.2.13) 如上所述，N点DIT―FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子 ，称其为旋转因子，p称为旋转因子的指数。 不难发现，第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：