数字信号处理第三版第四章.ppt

第4章 快速傅里叶变换(FFT) 4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.2 基2FFT算法 一般情况下，x(n)为复数序列，对某一个k值，直接按(4.2.1)式计算一个系数X(k)值需要： 复数乘法：N次 复数加法：(N-1)次 计算全部X(k)值需要： N2次 N(N-1)次 当N1时，N(N-1)?N2 ； ? 随着N增大复乘、复加次数非线性增大。 二、减少运算量的基本途径 在DFT定义式中只有两种运算：x(n)与WmN的乘和加， WmN的特性对运算量必有影响。 （1）根据旋转因子WmN的周期性、对称性和特殊值减少乘法运算次数。 4.2.2 时域抽取法（DIT）基2-FFT基本原理 根据减少运算量的途径，巧妙地在时域或频域进行不同的抽取分解与组合，可得到不同的快速算法。 FFT算法基本上分为两大类： 时域抽取法FFT (Decimation In Time-FFT，DIT-FFT) 频域抽取法FFT (Decimation In Frequency-FFT，DIF-FFT) 我们介绍基2DIT-FFT算法。 所谓基2是序列x(n)的长度N满足： 设序列x(n)的长度为N，且满足： 由于X1(k)和X2(k)均以N/2为周期，则由复指数序列的周期性可得: 由于N=2M，与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即： 用同样的方法，将x2(r)按奇偶分解，可得： 4.2.3 DIT―FFT算法与直接计算DFT运算量的比较 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。 所以，M级运算共需运算量为： 复数乘法： m(M)=（N/2）? M=（N/2）? log2 N 复数加法： a(M)= N? M= N? log2 N 4.2.4 DIT-FFT的实现 1.原位计算 DIT-FFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。 4.2.5频域抽取基－2FFT算法 算法的推导 DIF-FFT的蝶式运算流图 DIF-FFT的一次分解运算流图 DIF-FFT的二次分解运算流图 有关说明 4.2.6 IDFT的高效算法 上述FFT算法流图也可以用于IDFT (Inverse Discrete Fourier Transform)。 比较DFT和IDFT的运算公式： * 第4章 快速傅里叶变换(FFT) (4.2.1) 4.2.1 直接计算DFT的特点及减少运算量的基本途径 一、直接计算DFT的运算量 长度为N的有限长序列x(n)的DFT为： WmN的可约性为： WmN的对称性表现为： WmN的周期性表现为： (4.2.2) 或者 (4.2.3) WmN的特殊值为： （2）把N点DFT分解为几个较短DFT的组合，可使乘法次数大大减少。 FFT算法就是不断地把长序列的DFT分解成几个短序列的DFT，并利用旋转因子的周期性和对称性来减少DFT的运算次数。 因为，DFT的运算次数 ? N2 若序列长度N?，则运算次数? 。 最常用的算法是基2-FFT(N＝2M)。 为自然数 （1）算法思想：进行时域 M 级奇偶抽取，并利用： 将N点DFT变成 M 级蝶形运算。 （2）特点：运算流程图结构规则，可原位计算，程序简单。 为自然数 按n的奇偶把x(n)分解为两个N/2点的子序列： 则x(n)的DFT为： 所以 由于 其中X1(k)和X2(k)分别为x1(r)和x2(r)的 N/2 点DFT k=0,1,…,N-1 虽然k=0,1,…,N-1，但从此式只能方便地得到N/2个DFT系数，那么，还有N/2个DFT系数如何方便地得到呢？ 所以: 另外由旋转因子WmN的对称性： (4.2.7) (4.2.8) ? 这样将N点DFT分解为两个N/2点的DFT运算，用如图所示的流图符号（蝶形）表示。 要完成一个蝶形运算， 需一次复数乘和两次复数加法运算。 仅经过一次分解，就使 运算量减少近一半： N2?(N2 /4)+ (N