快速傅里叶变换(FFT)幻灯片

1、第4章 快速傅里叶变换(FFT),4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 分裂基FFT算法 4.5 离散哈特莱变换(DHT),1,4.1 引言,DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年Cooley和Tukey发现了DFT的一种快速算法以后，情况才发生了根本的变化。,2,4.2 基2FFT算法,4.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列

2、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),3,注意：,通常将算术乘法和算术加法的次数作为计算复杂性的度量，因为这种方法使用起来很简单。如果在计算机上用软件实现这些算法，则乘法和加法的次数就直接与计算速度有关。 但是，在常用的VLSI实现时，芯片的面积和功率要求往往是最重要的考虑因素，而它们有可能与算法的运算次数没有直接的关系。

3、,4,显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性、对称性和可约性。其周期性表现为,(4.2.2),其对称性表现为,或者,5,可约性表现在：,6,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点的子序列,7,则x(n)的DFT

4、为,由于,所以,8,其中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),9,图4.2.1 蝶形运算符号,X1(k),X2(k),WNK,X1(k)+ WNK X2(k),X1(k)- WNK X2(k),10,经过一次分解后，计算复数乘和复数加的次数： 复数乘： 复数加： 一次分解后，运算量减少近一半，故可以对N/2点DFT再作进一步分解。,11,图4.2.2 N点DFT的一次时域抽取分解图(N=8),12,与第一次分解相同，将x1(

5、r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即,那么，X1(k)又可表示为,(4.2.9),13,式中,同理，由X3(k)和X4(k)的周期性和 的对称 性 ，最后得到：,(4.2.10),14,用同样的方法可计算出,(4.2.11),其中,15,图4.2.3 N点DFT的第二次时域抽取分解图(N=8),16,图4.2.4 N点DITFFT运算流图(N=8),17,4.2.3 DIT-FFT算法与直接计算DFT运算量的比较 运算流图有M级蝶型，每一级都有N/2个蝶型运算。每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为

6、,复数加次数为,例如，N=210=1024时,18,图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线,19,MATLAB提供了一个fft的函数用于计算一个向量x的DFT。调用X=fft(x,N)就计算出N点的DFT。如果向量x的长度小于N，那么就将x补0。如果略去N，则DFT的长度就是x的长度。如果x是一个矩阵，那么fft(x,N)计算x中每一列的N点的DFT。 fft由机器语言写成的，执行速度快。当N为2的幂次方，则使用基2 FFT算法，如果不是，那么将N分解为若干素因子并用一个较慢的混合基FFT算法。如果N为某个素数，则fft算法就蜕化为原始的DFT算法。,20,4.2.4

7、DIT-FFT的运算规律及编程思想 1.原位计算 1)由图4.2.4可以看出，DITFFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。 2)同一级，每个蝶形的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据节点又同在一水平线上，即计算完一个蝶形后，所得的数据可立即存入原输入数据所占用的存储单元。,21,3)经过M级运算后，原来存放输入序列数据的N个存储单元中依次存放X(k)的N个值。 这种利用同一存储单元存储蝶形计算输入、输出数据的方法称为原位计算，可以大大节省内存。 2.旋转因子的变化规律 如上所述，N点DIT-FFT运算流图中，每级都有N/

8、2个蝶形。每个蝶形都要乘以因子WpN，称其为旋转因子，p称为旋转因子的指数.,22,观察图4.2.4不难发现，第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下： L=1时， L=2时， L=3时， 对N=2M的一般情况，第L级的旋转因子为,(4.2.12),(4.2.13),23,3. 序列的倒序 DIT-FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2n1n0)表示。,图4.2.7 形成倒序的树状图(N=23),24,表4.2.1 顺序和倒序二进制数对照表,25,4.2.5 频

9、域抽取法FFT(DIF-FFT) 在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIF-FFT。 设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：,26,将X(k)分解成偶数组与奇数组，当k取偶数(k=2r,r=0,1,N/2-1)时,(4.2.14),x1(n),27,当k取奇数(k=2r+1,r=0,1,N/2-1)时,(4.2.15),将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得,(4.2.16),x2(n),28,图4.2.10 DIF-FFT蝶形运算流图符号,29,4.2.6 IDFT的

10、高效算法 上述FFT算法流图也可以用于离散傅里叶逆变换(Inverse Discrete Fourier Transform，简称IDFT)。比较DFT和IDFT的运算公式： 只要将DFT运算式中的系数 改变为 ，最后乘以 ，就是IDFT的运算公式。故只要将上述的DIT-FFT与DIF-FFT算法中的旋转因子 改为 ,最后的输出再乘以 就可以用来计算IDFT.,30,如果希望直接调用FFT子程序计算IFFT，则可用下面的方法： 由于,对上式两边同时取共轭，得,31,4.3.2 实序列的FFT算法 1.设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即,对y(n)进行N/2点FFT，输出Y(k)，则,根据DIT-