数字信号处理(丁玉美版)教案第4章

1 第四章快速傅立叶变换 FFT FastFourierTransform 数字信号处理 2 4 1引言 DFT是数字信号处理的基础 是一种重要变换 快速算法的引出 使数字信号处理技术得到广泛应用 各种快速算法不断被采用 3 数字计算机 N足够大 1 1DFT提供了计算机处理的可能性 模拟信号的频谱分析 4 1 2DFT的运算量 k 0 1 2 N 1 计算机运算时 N项 N个 计算一个N点DFT 共需 次复乘 以做 一次复乘1 s计 若N 4096 所需时间为 由于计算量大 且要求相当大的内存 难以实现实时处理 限制了DFT的应用 5 长期以来 人们一直在寻求一种能提高DFT运算速度的方法 FFT便是Cooley Tukey在1965年提出的的快速算法 它可以使运算速度提高几百倍 从而使数字信号处理学科成为一个新兴的应用学科 4 1 3FFT算法的设计思想 1 利用 的特点 具有 1 周期性 2 共轭性 3 对称性 4 恒等性 5 可约性 2 把N点DFT化为几组点数较少的DFT运算 N点DFT运算的复乘次数为 次 若将N点DFT 化为2组 则复乘次数约为 次 7 4 2基2抽取FFT算法 theDecimation In TimeRadix 2FFTAlgorithm FFT分为两大类 时域抽取FFT Decimation In TimeFFT 简称DIT FFT 频域抽取FFT Decimation In FrequencyFFT 简称DIF FFT 8 4 2 1直接计算DFT的问题及改进的途径 k 0 1 N 1 n 0 1 N 1 DFT及IDFT的定义 9 可见 DFT与IDFT的计算成本基本相同 直接计算N点DFT时 对应一个k需要N次复数乘和 N 1 次复数加 对所有N个k值 则需要N 复数乘和N N 1 次复数加 其中 一次复数乘需要4次实数乘和2次实数加方能完成 当N较大时 运算量很大 10 例如 当N 8时 DFT需要64次复数乘 当N 1024时 DFT所需复数乘为1048576次 即一百多万次复数乘 为了减少运算次数 改进计算的方法 1 利用旋转因子的对称性 周期性和可约性 旋转因子 twiddlefactor 2 使长序列变短 11 4 2 2基2时域抽取法原理 库利 图基算法 设序列x n 的长度为N 且M为自然数N pointDFT Niseven 12 将其一分为二 分成偶数和奇数序列项 theeven indexedandodd indexedterms 则N 2点的序列为 even x1 r x 2r r 0 1 N 2 1odd x2 r x 2r 1 r 0 1 N 2 1 13 偶数序列therange 0 2n N 2 Niseven 0 n N 2 1奇数序列therange 1 2n 1 N 1 Niseven 0 2n N 20 n N 2 1 14 则x n 的DFT 15 由于所以 k 0 1 N 1 16 上式说明 按n的奇偶性将分解为两个N 2长的序列和 则N点DFT可分解为两个N 2点的DFT来计算 17 其中N 2 pointDFT k 0 1 N 2 1 k 0 1 N 2 1 18 因此 可写出两个N 2点的方程 19 而 20 同理而 21 所以 22 表示上述算法可用蝶形结 butterfly 23 Example 如N 4 x n x0 x1 x2 x3even x0 x2even x0odd x2odd x1 x3even x1odd x3 24 bitreversal shufflingprocess 混序或反序 码位倒置 分成四个1点的序列 25 thebutterfly 蝶形运算 1点序列的DFT就是序列本身 即不用计算 1 1 1 1 26 如N 4 则 将x1 r 再按r的奇偶进一步分解成两个N 4点长的子序列 27 28 其中 29 由X3 k 和X4 k 的周期性和的对称性 得 30 同理 得 31 其中 32 8点DIT FFT运算流图 33 4 2 3IDFT的高效算法 这样IFFT可与FFT用同一子程序实现 34 IDFT的运算规律 35 求IFFT 也可用DIT FFT的流程来实现 36 Example Determinethex n byIDFT X 5 1 1 1 Solution n 0 1 2 3 37 38 所以x n 1 1 2 1 39 theprograminMATLAB X input PleaseinputX N length X x fft conj X N x conj x N 40 Example 用FFT算法计算下面信号的8点DFT x n 4 320 1 231 然后 再用IFFT恢复原信号 41 solution 2 2 2 2 2 2 42 IFFT X 1 N FFT X 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 乘以1 N 1 8得原序列 43 4 2 4FFT的计算成本 最简单的FFT是Cooley Tukey法因为 N点DFT有M级蝶形运算 每一级都有N 2个蝶形运算结构 每个蝶形运算结构都有1次复数乘和2次复数加 45 所以 M级蝶形运算有复数乘M级蝶形运算有复数加 46 直接DFT的复数乘和复数加均近似为 当N 1时 所以DIT FFT大大减少了运算次数 47 Example forN 8 Solution M 3stages 三级 forFFT thetotalcostis FFT的总计算成本是 MN 2 3 8 2 12complexmultiplications 复数乘 48 fordirectlyDFT thetotalcostis 直接计算DFT的成本是 N 8 64 complexmultiplications Theratiois 比值是 实际上 当N 2048时 直接运算与FFT算法的计算量之比为372 4 49 4 2 5DIT FFT的运算规律及编程思想 1 原位运算 利用同一单元存储蝶形计算的输入 输出数据 每个蝶形的输入和输出均为相同位数 原位运算可节省大量内存 因而硬件成本低 2 旋转因子的变化规律 N点DFT 共有M级蝶形运算 每级有N 2个蝶形 50 称为旋转因子 p称为旋转因子的指数 为了编写程序 应找出旋转因子与运算级数的关系 设L 1 2 M 表示从左到右的运算级数 第L级有个不同的旋转因子 51 对于 各级的旋转因子表示为L 1时 L 2时 L 3时 52 对于的一般情况 第L级的旋转因子为 由于 53 所以通过上式 可以计算第L级运算的旋转因子 54 3 蝶形运算规律 设序列x n 经过时域倒序存入数组X如蝶形运算的两个输入数据相距B个点 应用原位运算 可得 55 4 编程思想及程序框图 其它运算规律 第L级中 每个蝶形的两个输入数据相距个点 同一旋转因子对应着间隔为点的个蝶形 对应第几组蝶形 56 8点DIT FFT运算流图 57 编程的运算方法 从输入端 第1级 开始 逐级进行 共进行M级运算 在进行第L级运算时 依次求出个不同的旋转因子 然后计算其对应相同的旋转因子的个蝶形 可用三重循环程序实现DIT FFT运算 58 3 59 5 序列的倒置 bitreversal 倒序是有规律的 由于 所以顺序数可用M位二进制数 表示 60 用硬件电路和汇编语言程序产生倒序很容易 用高级语言倒序的规律为 倒序数是在M位二进制数最高位加1 逢2向右进位 61 4 2 6频率抽取法FFT DIF FFT 设序列x n 长度为 将其前后对半分开 得 62 式中 63 再将X k 分解成偶数组和奇数组k为偶数时 64 k为奇数时 65 令 66 得 67 DIF FFT蝶形运算流图 68 N 8时 DIF FFT蝶形运算流图 69 注意 DIT FFT和DIF FFT的算法流图不是唯一的 其变形运算流图见P108 70 4 3进一步减少运算量的措施 以程序的复杂度换取计算量的进一步提高 4 3 1多类蝶形单元运算第一级旋转因子可简化 第二级旋转因子可简化 称为无关紧要的旋转因子 71 其复数乘法次数可减少为 CM 2 M 2 N 2当L 3时 第三级蝶形有两个无关紧要旋转因子 同一因子对应2 M L N 2 L级蝴蝶结 所以第三级共有 书110页 72 依次类推 从L 3到L M共可减少复数乘法次数为 DIT FFT的复数乘法次数为 73 另外 也可用实数乘法减少计算量 包含所有旋转因子称为一类蝶形单元运算 去掉为二类 去掉为三类 依次类推 称为多类蝶形单元运算 N 4096时 三类与一类比 仅75 74 4 3 2旋转因子的生成直接查表 提高速度 多占内存