《DSP--FFT_深入浅出详细讲解快速傅里叶变换》由会员分享，可在线阅读，更多相关《DSP--FFT_深入浅出详细讲解快速傅里叶变换（171页珍藏版）》请在金锄头文库上搜索。
1、第四章快速付里叶变换 FFT FastFourierTransforming 第一节引言 一 快速付里叶变换FFT 有限长序列通过离散傅里叶变换 DFT 将其频域离散化成有限长序列 但其计算量太大 与N的平方成正比 很难实时地处理问题 因此引出了快速傅里叶变换 FFT FFT并不是一种新的变换形式 它只是DFT的一种快速算法 并且根据对序列分解与选取方法的不同而产生了FFT的多种算法 FFT在离散傅里叶反变换 线性卷积和线性相关等方面也有重要应用 二 FFT产生故事 当时加文 Garwin 在自已的研究中极需要一个计算付里叶变换的快速方法 他注意到图基 J W Turkey 正在写有关付里叶变
2、换的文章 因此详细询问了图基关于计算付里叶变换的技术知识 图基概括地对加文介绍了一种方法 它实质上就是后来的著名的库利 CooleyJ W 图基算法 在加文的迫切要求下 库利很快设计出一个计算机程序 1965年库利 图基在 MathematicofComputation杂志上发表了著名的 机器计算付里级数的一种算法 文章 提出一种快速计算DFT的方法和计算机程序 揭开了FFT发展史上的第一页 促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成 电子数字计算机的条件 使DFT的运算大简化了 三 本章主要内容 1 直接计算DFT算法存在的问题及改进途径 2 多种DFT算法 时间
3、抽取算法DIT算法 频率抽取算法DIF算法 线性调频Z变换即CZT法 3 FFT的应用 第二节直接计算DFT算法存在的问题及改进途径 一 直接计算DFT计算量 问题提出 设有限长序列x n 非零值长度为N 计算对x n 进行一次DFT运算 共需多大的运算工作量 1 比较DFT与IDFT之间的运算量 其中x n 为复数 也为复数所以DFT与IDFT二者计算量相同 2 以DFT为例 计算DFT复数运算量 计算一个X k 一个频率成分 值 运算量为例k 1则要进行N次复数乘法 N 1 次复数加法所以 要完成整个DFT运算 其计算量为 N N次复数相乘和N N 1 次复数加法 3 一次复数乘法换算成实
4、数运算量 复数运算要比加法运算复杂 需要的运算时间长 一个复数乘法包括4个实数乘法和2个实数相法 a jb c jd ac bd j bc ad 4次实数乘法 2次实数加法 4 计算DFT需要的实数运算量 每运算一个X k 的值 需要进行4N次实数相乘和2N 2 N 1 2 2N 1 次实数相加 整个DFT运算量为 4N2次实数相乘和2N 2N 1 次实数相加 由此看出 直接计算DFT时 乘法次数与加法次数都是和N2成比例的 当N很大时 所需工作量非常可观 例子 例1 当N 1024点时 直接计算DFT需要 N2 220 1048576次 即一百多万次的复乘运算这对实时性很强的信号处理 如雷达
5、信号处理 来讲 它对计算速度有十分苛刻的要求 迫切需要改进DFT的计算方法 以减少总的运算次数 例2 石油勘探 24道记录 每道波形记录长度5秒 若每秒抽样500点 秒 每道总抽样点数 500 5 2500点24道总抽样点数 24 2500 6万点DFT运算时间 N2 60000 2 36 108次 作业 二 改善DFT运算效率的基本途径 利用DFT运算的系数的固有对称性和周期性 改善DFT的运算效率 1 合并法 合并DFT运算中的某些项 3 分解法 将长序列DFT利用对称性和周期性 分解为短序列DFT 利用DFT运算的系数的固有对称性和周期性 改善DFT的运算效率 的对称性 的周期性 因为
6、由此可得出 例子 例 利用以上特性 得到改进DFT直接算法的方法 1 合并法 步骤1分解成虚实部 合并DFT运算中的有些项对虚实部而言所以带入DFT中 1 合并法 步骤2代入DFT中 展开 1 合并法 步骤3合并有些项 根据 有 1 合并法 步骤4结论 由此找出其它各项的类似归并方法 乘法次数可以减少一半 例 2 将长序列DFT利用对称性和周期性分解为短序列DFT 思路 因为DFT的运算量与N2成正比的如果一个大点数N的DFT能分解为若干小点数DFT的组合 则显然可以达到减少运算工作量的效果 2 将长序列DFT利用对称性和周期性分解为短序列DFT 方法 把N点数据分成二半 其运算量为 再分二半
7、 这样一直分下去 剩下两点的变换 2 将长序列DFT利用对称性和周期性分解为短序列DFT 结论 快速付里时变换 FFT 就是在此特性基础上发展起来的 并产生了多种FFT算法 其基本上可分成两大类 按抽取方法分 时间抽取法 DIT 频率抽取法 DIF 按 基数 分 基 2FFT算法 基 4FFT算法 混合基FFT算法 分裂基FFT算法其它方法 线性调频Z变换 CZT法 第三节基 2按时间抽取的FFT算法Decimation in Time DIT Coolkey Tukey 一 算法原理 设输入序列长度为N 2M M为正整数 将该序列按时间顺序的奇偶分解为越来越短的子序列 称为基2按时间抽取的F
8、FT算法 也称为Coolkey Tukey算法 其中基数2 N 2M M为整数 若不满足这个条件 可以人为地加上若干零值 加零补长 使其达到N 2M 例子 设一序列x n 的长度为L 9 应加零补长为N 24 16应补7个零值 0123456789101112131415n x n 二 算法步骤1 分组 变量置换 DFT变换 先将x n 按n的奇偶分为两组 作变量置换 当n 偶数时 令n 2r 当n 奇数时 令n 2r 1 得到 x 2r x1 r x 2r 1 x2 r r 0 N 2 1 则可得其DFT为两部分 前半部分 后半部分 2 代入DFT中 生成两个子序列 x 0 x 2 x 2r
9、 偶数点x 1 x 3 x 2r 1 奇数点 代入DFT变换式 3 求出子序列的DFT 上式得 4 结论1 一个N点的DFT被分解为两个N 2点DFT X1 k X2 k 这两个N 2点的DFT按照 再应用W系数的周期性 求出用X1 k X2 k 表达的后半部的X k N 2 的值 5 求出后半部的表示式 看出 后半部的k值所对应的X1 k X2 k 则完全重复了前半部分的k值所对应的X1 k X2 k 的值 6 结论2 频域中的N个点频率成分为 结论 只要求出 0 N 2 1 区间内的各个整数k值所对应的X1 k X2 k 值 即可以求出 0 N 1 整个区间内全部X k 值 这就是FFT能
10、大量节省计算的关键 7 结论3 由于N 2M 因此N 2仍为偶数 可以依照上面方法进一步把每个N 2点子序列 再按输入n的奇偶分解为两个N 4点的子序列 按这种方法不断划分下去 直到最后剩下的是2点DFT 两点DFT实际上只是加减运算 三 蝶形结 即蝶式计算结构也即为蝶式信号流图上面频域中前 后半部分表示式可以用蝶形信号流图表示 X1 k X2 k 作图要素 1 左边两路为输入 2 右边两路为输出 3 中间以一个小圆表示加 减运算 右上路为相加输出 右下路为相减输出 4 如果在某一支路上信号需要进行相乘运算 则在该支路上标以箭头 将相乘的系数标在箭头旁 5 当支路上没有箭头及系数时 则该支路的
11、传输比为1 例子 求N 23 8点FFT变换 1 先按N 8 N 2 4 做4点的DFT 先将N 8DFT分解成2个4点DFT 可知 时域上 x 0 x 2 x 4 x 6 为偶子序列x 1 x 3 x 5 x 7 为奇子序列频域上 X 0 X 3 由X k 给出X 4 X 7 由X k N 2 给出 a 比较N 8点直接DFT与分解2个4点DFT的FFT运算量 N 8点的直接DFT的计算量为 N2次 64次 复数相乘 N N 1 次 8 8 1 56次 复数相加 共计120次 b 求一个蝶形结需要的运算量 要运算一个蝶形结 需要一次乘法 两次加法 c 分解为两个N 2 4点的DFT的运算量
12、分解2个N 2点 4点 的DFT 偶数其复数相乘为复数相加为 奇数其复数相乘为复数相加为 d 用2个4点来求N 8点的FFT所需的运算量 再将N 2点 4点 合成N点 8点 DFT时 需要进行N 2个蝶形运算 还需N 2次 4次 乘法及次 8次 加法运算 e 将N 8点分解成2个4点的DFT的信号流图 4点DFT x 0 x 2 x 4 x 6 4点DFT x 1 x 3 x 5 x 7 X 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7 X1 0 X1 1 X1 2 X1 3 X2 0 X2 1 X2 2 X2 3 偶数序列 奇数序列 X 4 X 7 同学们自已写 x1 r x2
13、 r 2 N 2 4点 N 4 2点 FFT a 先将4点分解成2点的DFT 因为4点DFT还是比较麻烦 所以再继续分解 若将N 2 4点 子序列按奇 偶分解成两个N 4点 2点 子序列 即对将x1 r 和x2 r 分解成奇 偶两个N 4点 2点 点的子序列 b 求2点的DFT c 一个2点的DFT蝶形流图 2点DFT 2点DFT x 0 x 4 x 2 x 6 X3 0 X3 1 X4 0 X4 1 X1 0 X1 1 X1 2 X1 3 d 另一个2点的DFT蝶形流图 2点DFT 2点DFT x 1 x 5 x 3 x 7 X5 0 X5 1 X6 0 X6 1 X2 0 X2 1 X2
14、2 X2 3 同理 3 将N 4 2点 DFT再分解成2个1点的DFT a 求2个一点的DFT 最后剩下两点DFT 它可分解成两个一点DFT 但一点DFT就等于输入信号本身 所以两点DFT可用一个蝶形结表示 取x 0 x 4 为例 b 2个1点的DFT蝶形流图 1点DFT x 0 1点DFT x 4 X3 0 X3 1 进一步简化为蝶形流图 X3 0 X3 1 x 0 x 4 4 一个完整N 8的按时间抽取FFT的运算流图 x 0 x 4 x 2 x 6 x 1 x 5 x 3 x 7 X 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7 m 0 m 1 m 2 四 FFT算法中一些
15、概念 1 级 概念 将N点DFT先分成两个N 2点DFT 再是四个N 4点DFT 直至N 2个两点DFT 每分一次称为 一 级运算 因为N 2M所以N点DFT可分成M级如上图所示依次m 0 m 1 M 1共M级 2 组 概念 每一级都有N 2个蝶形单元 例如 N 8 则每级都有4个蝶形单元 每一级的N 2个蝶形单元可以分成若干组 每一组具有相同的结构 相同的因子分布 第m级的组数为 例 N 8 23 分3级 m 0级 分成四组 每组系数为m 1级 分成二组 每组系数为m 2级 分成一组 每组系数为 3 因子的分布 结论 每由后向前 m由M 1 0级 推进一级 则此系数为后级系数中偶数序号的那一
16、半 4 按时间抽取法 2点DFT 2点DFT 2点DFT 2点DFT 2点DFT 2点DFT 2点DFT 2点DFT 两个2点DFT 两个2点DFT 两个2点DFT 两个2点DFT 两个4点DFT 两个4点DFT 两个N 2点DFT X1 k X2 k X k 由于每一步分解都是基于在每级按输入时间序列的次序是属于偶数还是奇数来分解为两个更短的序列 所以称为 按时间抽取法 x n 五 按时间抽取的FFT算法与直接计算DFT运算量的比较 由前面介绍的按时间抽取的FFT运算流图可见 每级都由N 2个蝶形单元构成 因此每一级运算都需要N 2次复乘和N次复加 每个结加减各一次 这样 N 2M M级运算共需要 复乘次数 复加次数 可以得出如下结论 按时间抽取法所需的复乘数和复加数都是与成正比 而直接计算DFT时所需的复乘数与复加数则都是与N2成正比 复乘数md N2 复加数ad N N 1 N2 例子 看N 8点和N 1024点时直接计算DFT与用基2 按时间抽取法FFT的运算量 看出 当N较大时 按时间抽取法将比直接法快一 二个数量级之多 作业 六 按时间抽取FFT算法的特点 根据DIT基2
