信号与系统课件快速傅立叶变换FFT.ppt

?§ 4.1 引言 ?§ 4.2 按时间抽取(DIT)的FFT算法 ?§ 4.3 按频率抽取(DIF)的FFT算法 ?§ 4.4 离散傅立叶反变换(IDFT)的快速计算方法 ?§ 4.5 进一步减少运算量的措施 § 4.1 引言 § 4.2 按时间抽取(DIT)的FFT算法(库利-图基算法) § 4.3 按频率抽取(DIF)的FFT算法(桑德-图基算法) § 4.4 离散傅立叶反变换(IDFT)的快速计算方法 §4.5 进一步减少运算量的措施 * 第四章 快速傅立叶变换(FFT) 一，DFT直接计算工作量很大 计算一个X(k)工作量： N次 复数乘 ( N-1)次 复数加 或4N次 实数乘 2N+2(N-1)=4N-2次 实数加 全部计算N个X(k) N2 次 复数乘 N( N-1)次 复数加 或4N2次 实数乘 N(4N-2)次 实数加 例如： 10点 DFT 100次 复数乘 1024点 DFT 1,048,576次 复数乘，即100万次 复数乘运算！ 结论：直接计算DFT的计算量和N的平方成正比 ? ? ? ? 对称性 周期性 本章以基2 的FFT算法为重点 二，DFT的高效计算 1965年 Cooley Tukey 奠定FFT，把长序列短分解 如何利用WN 因子的周期性和对称性，导出一个高效的快速算法？ 使得乘法计算量由 次降为 次 以1024点为例，计算量降为5120次，仅为原来的 一，算法原理（时域奇偶分，频域前后分） 设x(n)长度N， N=2M， M为自然数 x2(r) = x(2r+1) x1(r) = x(2r) 1、第一次抽取：将x(n)按奇、偶分成两组，可得各长N/2的两个新序列 x(n)的DFT为 由于它们均以N/2为周期，且 ，因此 其中 和 分别为 x(2r)和x(2r＋1) 的N/2点DFT： 这样，将一个N点DFT分解成两个N/2点DFT ? ? ? ? ☉ ☉ ☉ ☉ 2、蝶形运算 用下面的蝶形图也可清楚地说明这种运算。 A A+BC C B A-BC 蝶形运算符号 一次复数乘、两次复数加 几次乘？几次加？ 运算量减少近一半 一次时域抽取计算量： 复数乘 复数加 DFT (N=8) ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ 直接计算需要8×8次复数乘、8×7次复数加 以N＝8为例 DFT (N=4) ☉ ☉ ☉ ☉ DFT (N=4) ☉ ☉ ☉ ☉ ? ? ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ 36次复数乘 32次复数加 3、第二次抽取 将 按奇偶分解成两个N/4长的子序列 和 于是 同样 将 按奇偶分解成两个N/4长的子序列 和 经过第二次分解，将每个N/2点的DFT分解成两个N/4点的DFT和N/4个蝶形运算 依次类推，经过M－1次分解，最后将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. 原位计算和码位倒置 这种利用同一存贮单元存贮蝶形计算输入输出数据的方法称为原位（址）计算。 原位计算可节省大量内存，使设备成本降低。 N＝2M点的FFT共进行M级运算