快速傅里叶变换

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第,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,的复乘次数等于,N,2,加法次数,N(N-1),.,当,N1,时，即,N,点,DFT,的乘法和加法运算次数均与,N,2,成正比，当,N,较大时，运算量相等可观。,(4.2.1),注意：,通常将算术乘法和算术加法的次数作为计算复杂性的度量，因为这种方法使用起来很简单。如果在计算机上用软件实现这些算法，则乘法和加法的次数就直接与计算速度有关。,但是，在常用的,VLSI,实现时，芯片的面积和功率要求往往是最重要的考虑因素，而它们有可能与算法的运算次数没有直接的关系。,显然，把,N,点,DFT,分解为几个较短的,DFT,，可使乘法次数大大减少。另外，旋转因子,W,m,N,具有明显的周期性、对称性和可约性。其,周期性,表现为,(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,为,由于,所以,其中,X,1,(,k,),和,X,2,(,k,),分别为,x,1,(,r,),和,x,2,(,r,),的,N/2,点,DFT,，即,(4.2.5),(4.2.6),由于,X,1,(,k,),和,X,2,(,k,),均以,N/2,为周期，且,，所以,X(,k,),又可表示为,(4.2.7),(4.2.8),图,4.2.1,蝶形运算符号,X,1,(,k,),X,2,(,k,),W,N,K,X,1,(,k,)+W,N,K,X,2,(,k,),X,1,(,k,)-W,N,K,X,2,(,k,),经过一次分解后，计算复数乘和复数加的次数：,复数乘：,复数加：,一次分解后，运算量减少近一半，故可以对,N/2,点,DFT,再作进一步分解。,图,4.2.2 N,点,DFT,的一次时域抽取分解图,(N=8),与第一次分解相同，将,x,1,(,r,),按奇偶分解成两个,N/4,长的子序列,x,3,(,l,),和,x,4,(,l,),，即,那么，,X,1,(,k,),又可表示为,(4.2.9),式中,同理，由,X,3,(,k,),和,X,4,(,k,),的周期性和 的对称,性 ，最后得到：,(4.2.10),用同样的方法可计算出,(4.2.11),其中,图,4.2.3 N,点,DFT,的第二次时域抽取分解图,(N=8),图,4.2.4 N,点,DITFFT,运算流图,(N=8),4.2.3 DIT-FFT,算法与直接计算,DFT,运算量的比较,运算流图有,M,级蝶型，每一级都有,N/2,个蝶型运算。每一级运算都需要,N/2,次复数乘和,N,次复数加,(,每个蝶形需要两次复数加法,),。所以，,M,级运算总共需要的复数乘次数为,复数加次数为,例如,，,N=2,10,=1024,时,图,4.2.5 FFT,算法与直接计算,DFT,所需乘法次数的比较曲线,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,算法。,4.2.4 DIT-FFT,的运算规律及编程思想,1.,原位计算,1),由图,4.2.4,可以看出，,DITFFT,的运算过程很有规律。,N=2,M,点的,FFT,共进行,M,级运算，每级由,N/2,个蝶形运算组成。,2),同一级，每个蝶形的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据节点又同在一水平线上，即计算完一个蝶形后，所得的数据可立即存入原输入数据所占用的存储单元。,3),经过,M,级运算后，原来存放输入序列数据的,N,个存储单元中依次存放,X(,k,),的,N,个值。,这种利用同一存储单元存储蝶形计算输入、输出数据的方法称为,原位计算,，可以大大节省内存。,2.,旋转因子的变化规律,如上所述，,N,点,DIT-FFT,运算流图中，每级都有,N/2,个蝶形。每个蝶形都要乘以因子,W,p,N,，称其为旋转因子，,p,称为旋转因子的指数,.,观察图,4.2.4,不难发现，第,L,级共有,2,L-1,个不同的旋转因子。,N=2,3,=8,时的各级旋转因子表示如下：,L=1,时，,L=2,时，,L=3,时，,对,N=2,M,的一般情况，第,L,级的旋转因子为,(4.2.12),(4.2.13),3.,序列的倒序,DIT-FFT,算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于,N=2,M,，所以顺序数可用,M,位二进制数,(,n,M-1,n,M-2,n,1,n,0,),表示。,图,4.2.7,形成倒序的树状图,(N=2,3,),表,4.2.1,顺序和倒序二进制数对照表,4.2.5,频域抽取法,FFT(DIF-FFT),在基,2,快速算法中，频域抽取法,FFT,也是一种常用的快速算法，简称,DIF-FFT,。,设序列,x,(,n,),长度为,N=2,M,，首先将,x,(,n,),前后对半分开，得到两个子序列，其,DFT,可表示为如下形式：,将,X(,k,),分解成偶数组与奇数组，当,k,取偶数,(,k,=2,r,r,=0,1,N/2-1),时,(4.2.14),x,1,(,n,),当,k,取奇数,(,k,=2,r,+1,r,=0,1,N/2-1),时,(4.2.15),将,x,1,(,n,),和,x,2,(,n,),分别代入,(4.2.14),和,(4.2.15),式，可得,(4.2.16),x,2,(,n,),图,4.2.10 DIF-FFT,蝶形运算流图符号,4.2.6 IDFT,的高效算法,上述,FFT,算法流图也可以用于离散傅里叶逆变换,(Inverse Discrete Fourier Transform,，简称,IDFT),。比较,DFT,和,IDFT,的运算公式：,只要将,DFT,运算式中的系数 改变为 ，最后乘以 ，就是,IDFT,的运算公式。故只要将上述的,DIT-FFT,与,DIF-FFT,算法中的旋转因子 改为,最后的输出再乘以 就可以用来计算,IDFT.,如果希望直接调用,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.,