快速傅里叶变换(FFT)整理版.ppt

如果希望直接调用FFT子程序计算IFFT，则可用下面的方法： 由于 对上式两边同时取共轭，得 4.3.2 实序列的FFT算法 1.设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即 对y(n)进行N/2点FFT，输出Y(k)，则 根据DIT-FFT的思想及式(4.2.7)和(4.2.8)，可得到 由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为 2.一个N点FFT计算两个N点实序列的FFT，一个序列作为实部，一个序列作为虚部，计算完FFT后，根据DFT的共轭对称性，由输出X(k)分别得到两个时序列的N点FFT. 第4章 快速傅里叶变换(FFT) 第4章 快速傅里叶变换(FFT) 4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 分裂基FFT算法 4.5 离散哈特莱变换(DHT) 4.1 引言 DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年Cooley和Tukey发现了DFT的一种快速算法以后，情况才发生了根本的变化。 4.2 基2FFT算法 4.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为 考虑x(n)为复数序列的一般情况，对某一个k值，直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。 因此，N点DFT的复乘次数等于N2,加法次数N(N-1). 当N1时， ，即N点DFT的乘法和加法运算次数均与N2成正比，当N较大时，运算量相等可观。 (4.2.1) 注意： 通常将算术乘法和算术加法的次数作为计算复杂性的度量，因为这种方法使用起来很简单。如果在计算机上用软件实现这些算法，则乘法和加法的次数就直接与计算速度有关。 但是，在常用的VLSI实现时，芯片的面积和功率要求往往是最重要的考虑因素，而它们有可能与算法的运算次数没有直接的关系。 显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性、对称性和可约性。其周期性表现为 (4.2.2) 其对称性表现为 或者 可约性表现在： 4.2.2 时域抽取法基2 FFT基本原理 FFT算法基本上分为两大类：时域抽取法FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取法FFT(Decimation In Frequency FFT,简称DIF-FFT)。下面介绍DIT-FFT算法。 设序列x(n)的长度为N，且满足 为自然数 按n的奇偶把x(n)分解为两个N/2点的子序列 则x(n)的DFT为 由于 所以 其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即 (4.2.5) (4.2.6) 由于X1(k)和X2(k)均以N/2为周期，且 ，所以X(k)又可表示为 (4.2.7) (4.2.8) ? 图4.2.1 蝶形运算符号 X1(k) X2(k) WNK X1(k)+ WNK X2(k) X1(k)- WNK X2(k) 经过一次分解后，计算复数乘和复数加的次数： 复数乘： 复数加： 一次分解后，运算量减少近一半，故可以对N/2点DFT再作进一步分解。 图4.2.2 N点DFT的一次时域抽取分解图(N=8) 与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即 那么，X1(k)又可表示为 (4.2.9) 式中 同理，由X3(k)和X4(k)的周期性和 的对称 性 ，最后得到： (4.2.10) 用同样的方法可计算出 (4.2.11) 其中 图4.2.3 N点DFT的第二次时域抽取分解图(N=8) 图4.2.4 N点DIT―FFT运算流图(N=8) 4.2.3 DIT-FFT算法与直接计算DFT运算量的比较 运算流图有M级蝶型，每一级都有N/2个蝶型运算。每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总