Chap4快速傅立叶变换FFT.pptVIP

Chap4快速傅立叶变换（FFT） 本章主要内容 按时间抽取（DIT）的FFT算法 按频率抽取（DIF）的FFT算法 线性调频z变换 实序列FFT算法 FFT应用 §4.1 引言 一、DFT的计算工作量 §4.1 引言（续） 分析计算一个X(k)的值的工作量:如X(1) 考虑一般情况： 都是复数 一个X(k)：N次复数乘法，（N-1）次复数加法 所有X(k)：N2次复数乘法，N（N-1）次复数加法 运算量与N2（序列长度）成正比！ 当N很大时，如N=1024,则要完成1048576次 （一百多万次）运算，这样，难以做到实时处理。 §4.1 引言（续） 二、算法改进 1. 的对称性和周期性 对称性： 周期性： §4.1 引言（续） 利用上述特性，可以将有些项合并，并将DFT分解为短序列，从而降低运算次数，提高运算速度。1965年，库利（cooley）和图基（Tukey）首先提出FFT算法，对于N点DFT，仅需 次复数乘法运算。例如 ： §4.1 引言（续） 例如： §4.2按时间抽取的FFT算法 ——库利－图基算法 一、算法原理（基-2FFT） 1.先将x(n)按n的奇偶分为两组做DFT，设 不足时可在序列末尾补零，这样有： n为偶数时： n为奇数时： 因此： §4.2按时间抽取的FFT算法（续） §4.2按时间抽取的FFT算法（续） 均为N/2点DFT 只能确定出 的前N/2，即： 的后N/2点的确定 §4.2按时间抽取的FFT算法（续） 的后一半也完全由 的前一半所确定。 结论： 一个N点序列的DFT可由两个N/2点的DFT来确定。 §4.2按时间抽取的FFT算法（续） 2.蝶形运算 由 表示 的运算是一种特殊的运算 §4.2按时间抽取的FFT算法（续） 3.计算量分析：按奇偶分组后的计算量 一个N/2点的DFT运算量 ： 复乘次数： 复加次数： 两个N/2点的DFT运算量： 复乘次数： 复加次数： 一个蝶形运算量： 复乘次数：1 复加次数：2 N/2个蝶形运算量： 复乘次数： N/2 复加次数：N 总运算量： 复乘： 复加： §4.2按时间抽取的FFT算法（续） 例：N=8 可以分解为两个N/2＝4点的DFT §4.2按时间抽取的FFT算法（续） 得： §4.2按时间抽取的FFT算法（续） 同理： 仍为偶数，可进一步把每个N/2点的序 列再按其奇偶部分分解为两个N/4得子序列。 §4.2按时间抽取的FFT算法（续） 这样， §4.2按时间抽取的FFT算法（续） 由 进行蝶形运算，得： §4.2按时间抽取的FFT算法（续） 继续分解，直至两个一点为止。 N＝8完整流图如下： §4.2按时间抽取的FFT算法（续） 二、DIT DFT算法小结： 计算一个 的FFT时，需经过 级分解，最终得到N/2个两点DFT。 由两点DFT逐级合成4点，8点，… ，N点。 每级中都有N/2个蝶形。 每次分解都是根据序列序号的奇偶进行的，故称为按时间抽取的算法。 DIT DFT 属于原位运算。 流图中输入“乱序”，输出“顺序”。 §4.2按时间抽取的FFT算法（续） “乱序”原因 §4.2按时间抽取的FFT算法（续） “整序”规律 将输入序号按自然顺序排序后，用相应位数的二 进制码表示，再进行反序，即可实现输入端的整 序。 §4.2按时间抽取的FFT算法（续） 蝶形图的规律 第 级：蝶形运算有N/2个传输系数，为 §4.2按时间抽取的FFT算法（续） DIT DFT算法与直接计算的DFT运算量的比较 §4.2按时间抽取的FFT算法（续） 直接计算与FFT方法，乘法运算比较曲线 §4.3按频率抽取（DIF）的FFT算法 ——桑德－图基算法 一、算法原理 设 不足时，可在末尾补零。 将x(n)按n的自然顺序分为前后两组，即 §4.3按频率抽取（DIF）的FFT算法（续） §4.3按频率抽取（DIF）的FFT算法（续） 考虑两种情况： 当取偶数时：k＝2r r=0,1,…,N/2-1 当取奇数时：k＝2r＋1 r=0,1,…,N/2-1