数字信号处理——第4章 FFT.pptVIP

4.1 引言 DFT在实际应用中很重要: 可以计算信号的频谱、功率谱和线性卷积等。 FFT并不是一种与DFT不同的变换，而是DFT的一种快速计算的算法。 直接按DFT变换进行计算，当序列长度N很大时，计算量非常大，所需时间会很长。 1965年图基（J.W.Tuky)和库利(T.W.Coody)在Math.Computation Vol.19,1965上发表《机器计算傅立叶级数的一种算法》，才使得用DFT进行谱分析得以实现。 4.2 基2 FFT算法 运算量 减少运算工作量的途径 FFT算法分类: 时间抽选法 DIT: Decimation-In-Time 频率抽选法（自学） DIF: Decimation-In-Frequency 时间抽选的基2 FFT算法 设序列点数 N = 2M，M 为整数。 若不满足，则补零 N为2的整数幂的FFT算法称基2 FFT算法。 则x(n)的DFT: 再利用周期性求X(k)的后半部分 将N点DFT分解为两个N/2点的DFT运算。 完成一个蝶形运算，需要一次复数乘法和两次复数加法运算。 经过一次分解，运算量减少近一半（见下页）。 分解后的运算量： 这样逐级分解，直到2点DFT 当N = 8时，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k = 0, 1 基2时间抽取FFT算法流图 2、运算量 当N = 2M时，共有M级蝶形，每级N / 2个蝶形，每个蝶形有1次复数乘法2次复数加法。 3、算法特点 1）原位计算 2）倒位序 3）蝶形运算 对N = 2M点FFT，输入倒位序，输出自然序， 第m级运算每个蝶形的两节点距离为 2m–1 第m级运算： 4、DIT算法的其他形式流图 输入倒位序输出自然序 输入自然序输出倒位序 输入输出均自然序 相同几何形状 输入倒位序输出自然序 输入自然序输出倒位序 * * 第4章 快速傅里叶变换 理解按时间抽选的基-2FFT算法的算法原理、运算流图、 所需计算量和算法特点 直接计算DFT的问题及改进的途径 N (N – 1) N 2 N个X(k) (N点DFT) N – 1 N 一个X(k) 复数加法 复数乘法 2N+2 (N – 1)=2 (2N – 1) 4N 一个X (k) 2N (2N – 1) 4N 2 N个X (k) (N点DFT) 2 一次复加 2 4 一次复乘 实数加法 实数乘法 DFT的运算量 N点DFT的复数乘法次数举例 1 048 576 1024 1028 32 262 144 512 256 16 65 536 256 64 8 16384 128 16 4 4049 64 4 2 N2 N N2 N 结论：当N很大时，其运算量很大，对实时性很强的信号处理来说，要求计算速度快，因此需要改进DFT的计算方法，以大大减少运算次数。 N点DFT的复数乘法次数等于N2。把N点的 DFT分解成几个较短的DFT，可使乘法的次 数大大减少。 旋转因子 具有周期性、对称性和可约性。 对称性 周期性 可约性 将序列x(n)按n的奇偶分成两组： 1、算法原理 N (N / 2 –1) N 2 / 2 两个N / 2点DFT N N / 2 N / 2个蝶形 总计 2 1 一个蝶形 N / 2 (N / 2 –1) (N / 2)2 一个N / 2点DFT 复数加法 复数乘法 运算量减少了近一半 N/2仍为偶数，进一步分解：N/2 N/4 同理： 其中： 第一级 第二级 第三级 复数乘法： 复数加法： 比较DFT 复乘次数 N N 2 FFT DFT m表示第m级迭代，k，j表示数据所在的行数 000 0 0 000 001 1 4 100 010 2 2 010 011 3 6 110 100 4 1 001 111 7 7 111 110 6 3 011 101 5 5 101 自然序 倒位序 * *