信号与系统课件--第四章快速傅立叶变换(FFT).ppt

4.1 引言 4.2 按时间抽取(DIT)的FFT算法 4.3 按频率抽取(DIF)的FFT算法 4.4 离散傅立叶反变换(IDFT)的快速计算方法 4.5 进一步减少运算量的措施 第四章 快速傅立叶变换(FFT) 4.1 引言 一，DFT直接计算工作量很大 计算一个X(k)工作量： N次 复数乘 ( N-1)次 复数加 或4N次 实数乘 2N+2(N-1)=4N-2次 实数加 全部计算N个X(k)N 次 复数乘 N( N-1)次 复数加 或4N次 实数乘 N(4N-2)次 实数加 例如： 10点 DFT 100次 复数乘 1024点 DFT 1,048,576次 复数乘，即100万次 复数乘运算！ 结论：直接计算DFT的计算量和N的平方成正比 对称性 周期性 本章以基2 的FFT算法为重点 二，DFT的高效计算 1965年 Cooley & Tukey 奠定FFT，把长序列短分解 如何利用WN 因子的周期性和对称性，导出一个高效的快速算法？ 使得乘法计算量由 次降为 次 以1024点为例，计算量降为5120次，仅为原来的 4.2 按时间抽取(DIT)的FFT算法(库利-图基算法) 一，算法原理（时域奇偶分，频域前后分） 设x(n)长度N， N=2N=2M M， M为自然数 x2(r) = x(2r+1) x1(r) = x(2r) 1、第一次抽取：将x(n)按奇、偶分成两组，可得各长N/2N/2的两个新序列 x(n)的DFT为 由于它们均以N/2为周期，且 ，因此 其中 和 分别为 x(2r)和x(2r1) 的N/2点DFT： 这样，将一个N点DFT分解成两个N/2点DFT 2、蝶形运算 用下面的蝶形图也可清楚地说明这种运算。 AA+BC C BA-BC 蝶形运算符号 一次复数乘、两次复数加几次乘？几次加？ 运算量减少近一半 一次时域抽取计算量： 复数乘 复数加 DFT (N=8) 直接计算需要88次复数乘、87次复数加 以N8为例 DFT (N=4) DFT (N=4) 36次复数乘 32次复数加 3、第二次抽取 将 按奇偶分解成两个N/4N/4长的子序列 和 于是 同样将 按奇偶分解成两个N/4长的子序列 和 经过第二次分解，将每个N/2点的DFT分解成两个N/4点的 DFT和N/4个蝶形运算 依次类推，经过M1次分解，最后将N点DFT分解成N/2个2点DFT DFT (N=2) DFT (N=2) DFT (N=2) DFT (N=2) 8点FFT运算流图 8点FFT运算流图 2. DFT与DIT-FFT算法运算量比较 全部“蝶形”数 复数乘法次数 复数加法次数 运算量 都 N2 ，在N值很大时，十分高效 每级蝶形有多少次复数乘和复数加？ N/2次复数乘，N次复数加 二，算法的讨论 1. 级的概念 上述DIT-FFT算法过程，将N点DFT先分成两个N/2点DFT，再直 至N/2个两点DFT。每分一次，称为一“级级”运算。N点DFT可以分成 M级，从左到右依次是1，2，M级,每级有N/2个蝶形 此算法以2为基，写作 （不足位，补零延伸） 1）原位计算 设 N个存贮单元 存入数据 可见：每次运算结 果存入原输入数据 占用的存贮单元 3. 原位计算和码位倒置 这种利用同一存贮 单元存贮蝶形计算 输入输出数据的方 法称为原位（址） 计算。 原位计算可节省大量内存，使设备成本降低。 N2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成 2） 码位倒置 先按自然顺序输入， 倒位序 变址运算 顺位序 二进顺序码 二进倒置码 倒位序 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 （按相似原理：若按自然序x(0),x(1),x(2),输入后不进行变址运 算，则输出将倒位序：X(0),X(4),X(2),X(6).) 由DITFFT流图可以看出，变换后的输出 依照正序排列，输入序 列 不再是原来的自然顺序，这是由于对 作奇偶抽取所产生的。 对N8，其自然序号是 0，1，2，3，4，5，6，7 第一次按奇偶分开，x(n)的序号是 0，2，4，6 | 1，3，5，7 每一组再作奇偶分开后序号是 0，4 | 2，6 | 1，5 | 3，7 将顺序码的二 进制位倒置 n2n1n0 n0n1n2 0 1 0 1 0 1 0 1 1 1 0 1 0 0 000 100 010 110 001 101 011 111 4. 旋转因子的分布规律 在N点DITFFT运算流图中，每级有N/2N/2个蝶形，每个蝶形要乘以因 子Wr 第一次将N点DFT分成两个N/2点DFT，这时出现的Wr因子是： 再往下分时，依次是 ，故每一级Wr因子的分布规律 是： Wr因子的一般分布规律： 4.3 按频率抽取(DIF)的FFT算法(桑德-图基算法) 一，算法原理（时域前后分，频域奇偶分） 设x(n)长度N=2N=2M M ，并将x(n)分成前后两段： 令后者的n=m+N/2，得： k为奇数 k为偶数 1 -1 X形运算单元蝶形运算单元 其中 将X(k)分解成偶数组和奇数组： DFT (N/2) DFT (N/2) DIF-FFT一次分解运算流图(N=8) 二，运算量 次复数乘法 次复数加法 DIF和DIT具有一样的运算量： DIF-FFT三级运算流图 输入为顺序，输出为倒序 三，简单小结 1. 基2 DITFFT算法 （1）算法思想：时域M级奇偶抽取，并利用 ，将N点 DFT变成M级蝶形运算 （2）运算量 复数乘法次数 复数加法次数 （3）特点：运算流图结构规则，可原位计算，程序简短，应用广泛。 2. 基2 DIFFFT算法 （1）算法思想：频域对X(k)进行M级奇偶抽取，并利用 ， 将N点DFT变成M级DIFFFT蝶形运算 （2）运算量及特点与基2DIFFFT相同 4、 DIT与DIF的联系 5、 通常多使用基2的FFT，因为它简单、效率高。 当N为任意数时，可将x(n)延伸补0；若不允许延伸情况下，可考 虑基r的FFT（如r=3,4,.），或混合基FFT 3、DIT与DIF的本质区别在于基本蝶形的不同 （1）只要保持各节点所连的支路和传输系数不变，变换节点位置 的排列，可以得到其它等效形式的流图 （2）DIT与DIF的流图满足转置定理转置定理：将所有支路方向都反向， 并且交换输入和输出，但节点变量值不交换。 N/2 点 碟 形 组 合 N/4 蝶 形 组合 N/4 蝶 形 组合 N/8 碟形 组合 N/8 碟形 组合 N/8 碟形 组合 N/8 碟形 组合 . . . . . . . . . 2点DFT 2点DFT 2点DFT . . . 4点 碟形 组合 2点DFT 4点 碟形 组合 . . . X(k) N N/2 N/4 N/8248 时间抽取基2-FFT算法的原理示意图 x（n ） N/2 碟 形 分 解 N/4 碟形 分解 N/4 碟形 分解 N/8 碟形 分解 N/8 碟形 分解 N/8 碟形 分解 N/8 碟形 分解 . . . . . . . . . 2点DFT 2点DFT 2点DFT . . . 4点 碟形 分解 2点DFT 4点 碟形 分解 . . . N N/2N/4N/8 24 X（k ） 频率抽取基2-FFT算法的原理示意图 4.4 离散傅立叶反变换(IDFT)的快速计算方法 由定义： 两者作比较，得到启发 方法一： 修改DFT运算中的各个系数-将 改为 ,最后乘以1/N 同时将常数 分解为 ，分散到各级中，即每一级都乘以因子 方法二：不修改FFT的程序和参数，利用共轭变换的方法 取共轭 直接访问 FFT程序 取共轭 乘系数 即 4.5 进一步减少运算量的措施 1. 多类蝶形单元运算 对第一级蝶形，W因子的指数为零， ,不需要乘法 第二级蝶形， 称其值为 的旋转因子为无关紧要的旋转因子无关紧要的旋转因子, 2. 旋转因子的生成 在FFT中，乘法主要来自旋转因子， 在编程时，正、余弦函数的产生一般有两个办法：一是在