数字信号处理第4章 快速傅里叶变换.ppt

第四章 快速傅里叶变换 Fast Fourier Transform ——FFT 一、说明 二、本章主要内容 1.直接计算DFT算法存在的问题及改进途径。 2.多种DFT算法(时间抽取算法DIT算法，频率抽取算法DIF算法，线性调频Z变换即CZT法) 3.FFT的应用 §4.1 快速傅里叶变换 一、DFT的运算特点（计算量） 2、以DFT为例，计算DFT的复数运算量 3、一次复数乘法换算成实数运算量 4、计算DFT需要的实数运算量 可见计算DFT时，乘法次数和加法次数与N2成正比，当N很大时，运算量很大，所以要改进DFT的算法，减少运算次数。 二、出发点（基本途径） 例: （1）利用对称性进行合并 结论： （2）利用对称性和周期性将长序列DFT分解为短序列DFT--思路 因为DFT的运算量与N2成正比 如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算量的效果。 --方法 --结论 §4.2 按时间抽取的FFT算法Decimation-In-Time(DIT) 一、算法原理 例: 二、算法步骤 2、代入DFT中 得： 结论1 一个N点的DFT被分解为两个N/2点DFT。 3、求出后半部的表示式 结论2 结论3 三、蝶形运算流图 蝶形运算流图的另一种表示方法 例：求 N=23=8点FFT (a)比较N=8点直接DFT与分解2个4点DFT的FFT运算量 (b)求 一个蝶形结需要的运算量 (c)分解为两个N/2=4点的DFT的运算量 (d)用2个4点来求N=8点的FFT所需的运算量 (e)将N=8点分解成2个4点的DFT的信号流图 (2)N/2(4点)?N/4(2点)FFT 即分别将x1(r)和x2(r)按r的奇/偶分解成两个N/4点（2点）的子序列。 (b)求2点的DFT (c)将一个4点分解成2个2点的DFT的蝶形流图 (d)另一个蝶形流图 (3)将N/4点（2点）DFT再分解成2个1点的DFT (b)一个2点的DFT蝶形流图 (4)一个N=8完整的按时间抽取FFT的运算流图 四、FFT算法中一些概念 将N 点DFT先分成两个N/2点DFT，再分成四个N/4点DFT…直至N/2个两点DFT。每分一次称为一 “级”运算。 因为N=2M所以N点DFT可分成M级 如上图所示依次m=0,m=1….M-1共M级 （2）“组” （3） 因子的分布 （4）按时间抽取法 五、按时间抽取的FFT算法与直接计算DFT运算量的比较 由前面介绍的按时间抽取的FFT运算流图可见： 每级都由N/2个蝶形单元构成，因此每一级运算都需要N/2次复乘和N次复加（每个结加减各一次）。 这样（N=2M)M级运算共需要： 复乘次数： 复加次数： 例子 N=8点和N=1024点时直接计算DFT与用基2-按时间抽取法FFT的运算量。 六、按时间抽取FFT算法的特点 1、原位运算（in-place) 2、码位倒置 1、原位运算（in-place) 原位运算的结构，可以节省存储单元，降低设备成本。 定义：当数据输入到存储器以后，每一组运算的结果，仍然存放在这同一组存储器中直到最后输出。 例：N=8 FFT运算,输入: 2、码位倒置 从输入序列的序号及整序规律得到码位倒读规则。由N=8蝶形图看出：原位计算时，FFT输出的X(k)的次序正好是顺序排列的，即X(0)…X(7)，但输入x(n)都不能按自然顺序存入到存储单元中，而是按x(0),x(4),x(2), x(6)….的顺序存入存储单元即为乱序输入，顺序输出。这种顺序看起来相当杂乱，然而它是有规律的。即码位倒读规则。 以N=8为例： §4.4 离散傅里叶反变换的快速算法 以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速傅里叶反变换。从IDFT的定义出发，可以导出下列两种利用FFT来计算IFFT的方法。 一、利用FFT计算IFFT的思路 将下列两式进行比较 二、注意 利用FFT计算IFFT时命名应为： (1)把FFT的时间抽取法，用于IDFT运算时，由于输入变量由时间序列x(n)改成频率序列X(k)，原来按x(n)的奇、偶次序分组的时间抽取法FFT，现在就变成了按X(k)的奇偶次序抽取了，即为频率抽取的IFFT。 (2) 频率抽取的FFT运算用于IDFT运算时，则应变为时间抽取的IFFT。 IFFT的基本蝶形运算 三、直接利用FFT流图的方法 前面IFFT算法，编程方便，但要改动FFT的程序和参数才能实现。 步骤： §4.5 实序列的快速傅里叶变换 用一个N点的FFT计算一个2N点的实序列的DFT 1、将长度为2N的实序列x(n)按n的奇偶分为两个子序列 x(n)的变换X(k)可以表示为： 2、将x1(n)和x2(n)分别作为