离散傅里叶变换的矩阵表示及其运算量ppt课件.ppt

第4章FFT4 1引言4 1 1离散傅里叶变换的矩阵表示及其运算量DFT在数字信号处理中起着非常重要的作用 这是与DFT存在着高效算法 即快速傅里叶变换 FFT 分不开的 快速运算的关键是减少运算量 离散傅里叶变换对为 4 1 4 2 式中 下面要用矩阵来表示DFT关系 一般情况下 信号序列x n 及其频谱序列X k 都是用复数来表示的 WN当然也是复数 因此 计算DFT的一个值X k 需要进行N次复数乘法 与1相乘也包括在内 和N 1次复数加法 所以 直接计算N点的DFT需要进行N2次复数乘法和N N 1 复数加法 显然 直接计算N点的IDFT所需的复乘和复加的次数也是这么多 当N足够大时 N2 N N 1 因此 DFT与IDFT的运算次数与N2成正比 随着N的增加 运算量将急剧增加 而在实际问题中 N往往是较大的 因此有必要对DFT与IDFT的计算方法予以改进 4 1 2因子的特性DFT和IDFT的快速算法的导出主要是根据因子的特性 1 周期性 对离散变量n有同样的周期性 2 对称性 或3 其它 4 2基2时间抽选的FFT算法4 2 1算法推导已经知道 令DFT的长度N 2M M为正整数 令 于是有 其中 是由x n 的偶数抽样点形成的DFT 而 是由x n 的奇数抽样点形成的DFT 但是这两个式子并不完全是N 2点的DFT 因为k的范围仍然是由0到N 1 因此 还应该进一步考虑k由N 2到N 1范围的情况 现在令 故对于后半段有 同理 又知 图4 1N点DFT分解为两个N 2点的DFT N 8 图4 2N 2点的DFT分解为两个N 4点的DFT N 8 综上所述 可以得到 其中G k P k 分别是x n 的偶数点和奇数点的N 2点DFT 这样 我们就将一个N点的DFT分解成了两个N 2点的DFT 由于DFT的运算量与其点数的平方成正比 因此使运算量减少了 但是 还应该将每一个N 2点的DFT再分解为两个N 4点的DFT 如此下去 直到分解为2点的DFT为止 总共需要进行log2N 1 log2 N 2 次分解 图4 32点DFT信号流图 蝶形图 对于2点DFT 有 所以2点DFT的运算只需一次加法和一次减法 这样的运算叫做蝶形运算 这样的信号流图叫做蝶形图 该算法每次分解都是将时域序列按奇偶分为两组 因此要求N等于2的正整数幂 故将这种FFT算法叫做基2时间抽选法 4 2 2算法特点1 倒序重排这种FFT算法的每次分解都是将输入序列按照奇偶分为两组 故要不断地将每组输入数据按奇偶重排 直到最后分解为2点的DFT 输入数据才不再改变顺序 这样做的结果 使得作FFT运算时 输入序列的次序要按其序号的倒序进行重新排列 现在将图4 4中输入序号以及重排后的序号按二进制写出如下 注 下标 2 表示二进制数 可以看出 将输入序号的二进制表示 n2n1n0 位置颠倒 得到 n0n1n2 就是相应的倒序的二进制序号 因此 输入序列按倒序重排 实际上就是将序号为 n2n1n0 的元素与序号为 n0n1n2 的元素的位置相互交换 2 同址计算从图4 4可以看出 整个算法流图可以分为四段 0 段为倒序重排 后面3段为3 log28 3 次迭代运算 首先计算2点DFT 然后将2点DFT的结果组合成4点DFT 最后将4点DFT组合为8点DFT 因此 对于N点FFT 只需要一列存储N个复数的存储器 3 运算量观察图4 4可知 图4 3所示的蝶形图实际上代表了FFT的基本运算 它实际上只包含了两次复数加法运算 一个N N 2M 点的FFT 需要进行M log2N次迭代运算 每次迭代运算包含了N 2个蝶型 因此共有N次复数加法 此外 除了第一次的2点DFT之外 每次迭代还包括了N 2次复数乘法 即乘WN的幂 因此 一个N点的FFT共有复数乘法的次数为 复数加法的次数为 因此 FFT算法比直接计算DFT大大减少了运算量 尤其是当N较大时 计算量的减少更为显著 比如 当N 1024时 采用FFT算法时复数乘法的次数 不超过直接计算DFT时复乘次数的千分之五 4 3基2频率抽选的FFT算法时间抽选法是在时域内将输入序列x n 逐次分解为偶数点子序列和奇数点子序列 通过求子序列的DFT而实现整个序列的DFT 而频率抽选法则是在频域内将X k 逐次分解成偶数点子序列和奇数点子序列 然后对这些分解得越来越短的子序列进行DFT运算 从而求得整个的DFT 当然 同样要求N为2的正整数幂 设 则可以分别表示出k为偶数和奇数时的X k 其中 其中 显然 X 2r 为g n 的N 2点DFT X 2r 1 为p n WNn的N 2点DFT 这样 一个N点的DFT分解为两个N 2点的DFT 将分解继续下去 直到分解为2点的DFT为止 当N 8时 基2频率抽选的FFT算法的整个信号流图如图4 6所示 将图4 6与图4 4比较 可知频率抽选法的计算量与时间抽选法相同 而且都能够同址计算 时间抽选法是输入序列按奇偶分组 故x n 的顺序要按倒序重排 而输出序列按前后分半 故X k 的顺序不需要重排 频率抽选法则是输出序列按奇偶分组 故X k 的顺序要按倒序重排 而输入序列按前后分半 故x n 不需要重排 4 5快速傅里叶反变换 IFFT IFFT是IDFT的快速算法 由于DFT的正变换和反变换的表达式相似 因此IDFT也有相似的快速算法 可以用三种不同的方法来导出IFFT算法 方法1设 则有 n 0 1 N 1 根据基2FFT的时间抽选法的第一次分解的结果 可以得到 图4 8由X k X k N 2 得到G k P k 再由N 2点的DFT求得N 4点的DFT 依次类推下去 就可推到求出x n 的各点 如图4 9所示 将此流图与图4 4比较 相当于整个流向反过来 此外 因子WNk成为WN k 还增加了因子1 2 但是 图4 9的IFFT算法不能直接利用按照图4 4编写的FFT算法程序 却可以利用图4 6的频率抽选FFT算法的程序 只需要将X k 作为输入序列 因子WNk变为WN k 并且将最后所得的输出序列的每个元素都除以N 方法2将DFT的正变换式 与其反变换式 比较 很容易知道 可以利用FFT算法的程序来计算IFFT 只需要将X k 作为输入序列 x n 则是输出序列 另外将因子WNk变为WN k 当然 最后还必须将输出序列的每个元素除以N 方法3对DFT的反变换式取共轭 有 与DFT的正变换式比较 可知完全可以利用FFT的计算程序 只需要将X k 作为输入序列 并将最后结果取共轭 再除以N就得到x n 4 7 1两个长度相同的实序列可以将两个长度相同的实序列组合成一个复序列来进行FFT运算 从而一次完成这两个实序列的FFT 减少了总的计算量 设p n 和g n 是两个长度均为N的实序列 并设 又设 则由DFT的线性有 4 36 P k 和G k 这两个复序列的实部都是周期性的偶序列 而其虚部都是周期性的奇序列 对复序列Y k 又有 4 37 这里下标r i分别表示实部和虚部 Y k 与其实部 虚部的长度都为N 现将 4 37 式中各序列作周期延拓 有 4 38 由周期性有 4 39 4 40 现在将序列与作如下分解 4 41 4 42 由 4 39 式和 4 40 式 容易证明在 4 41 和 4 42 这两个式子中 前一项都是偶序列 而后一项都是奇序列 将 4 41 式和 4 42 式代入 4 38 式 并将各项进行重新组合 得到 令0 k N 1 则上式为 这里的P k 和G k 的实部都是周期性偶序列 而它们的虚部都是周期性奇序列 此情况与 4 36 式中的复序列P k 和G k 的情况相同 因此有 上两式中0 k N 1 4 7 2一个2N点的实序列将一个2N点的实序列