《快速傅立叶变换的算法》由会员分享，可在线阅读，更多相关《快速傅立叶变换的算法（90页珍藏版）》请在金锄头文库上搜索。
1、第3章 快速傅立叶变换(FFT),一.DFT运算特点,长度为N的有限长序列x(n)的为：对于每一个k的运算需要次乘法和次加法对于个k，需要次复数乘法和（）次加法;一次复数乘需要4次实数乘和2次实数加方能完成当N很大时,运算量将是惊人的,如N=1024,则要完成1048576 次(一百多万次)运算.这样,难以做到实时处理.,旋转因子的对称性、周期性和可约性： 1） 的对称性：,2） 的周期性：3） 的可约性：,二.改进的途径,利用这些特性，DFT中有些项可以合并； 可以将长序列的DFT分解为短序列的DFT，提高运算速度。,对于N点DFT,仅需(N/2)log2N 次复数乘法运算. 例如N=102
2、4=210 时，需要(1024/2)log2 210 =512*10=5120次。5120/1048576=4.88% ,速度提高20倍,三.基 2 时域抽取FFT 算法,（the Decimation-in-time Redix-2 FFT Algorithm）FFT分为两大类：时域抽取FFT（Decimation-In-Time FFT，简称DIT-FFT）频域抽取FFT（Decimation-In-Frequency FFT, 简称DIF-FFT）,(一).算法原理(基2FFT),设序列x（n）的 长度为N，且M 为自然数,序列长度为的幂：基,1.N/2点DFT(1).先将 按n的奇偶分
3、为两组作DFT,设N=2L ,不足时,可补些零。这样有:n为偶数时:n为奇数时:,因此，,由于: 所以,上式可表示为:,(n为偶数) (n为奇数),其中,(2).两点结论:(1) X (k),X (k)均为N/2点的DFT。(2) X(k)=X (k)+W X (k)只能确定出X(k)的k= 个； 即前一半的结果。,1 2,1 2,k,N,同理, 这就是说,X1(k),X2(k)的后一半, 分别等于其前一半的值。,(3).X(k)的后一半的确定,由于 （周期性）,所以:,又由于 ,所以,可见,X(k)的后一半，也完全由X1(k), X2 (k)的前一半所确定。*N点的DFT可由两个N/2点的D
4、FT来计算。,实现上式运算的流图称作蝶形运算,前一半,(4).蝶形运算,后一半,（N/2个蝶形),(前一半),(后一半),1 1,1,1,-1,由X1(k)、X 2(k)表示X(k)的运算是一种特殊的运算-碟形运算,表示上述算法可用蝶形结（ butterfly）,(1)N/2点的DFT运算量:复乘次数:复加次数: (2)两个N/2点的DFT运算量:复乘次数:复加次数: (3)N/2个蝶形运算的运算量:复乘次数:复加次数:,(5).计算工作量分析,复乘:,复加:,总共运算量:,按奇、偶分组后的计算量：,*但是,N点DFT的复乘为N2 ;复加N(N-1);与分解后相比可知,计算工作点差不多减少 一
5、半。,例如 N=8 时的DFT,可以分解为两个 N/2=4点的DFT.具体方法如下:(1)n为偶数时,即分别记作:,(2) n为奇数时,分别记作:,x1(0)=x(0) x1(1)=x(2) N/2点 x1(2)=x(4) DFT x1(3)=x(6) x2(0)=x(1) x2(1)=x(3) N/2点 x2(2)=x(5) DFT x2(3)=x(7),1 2,X1(0),X1(1),X1(2),X1(3),X2(0),X2(1),X2(2),X2(3),W,N,2,W,N,1,W,N,0,W,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(
6、6),X(7),(3)对X (k)和X (k)进行蝶形运算,前半部为X(0)-X(3),后半部分为X(4)-X(7) 整个过程如下图所示:,由于N=2 L ,所以 N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分 分解为两个N/4的子序列。例如，n为偶数时的 N/2点分解为:,2. N/4点DFT,进行N/4点的DFT,得到,(偶中偶),(偶中奇),从而可得到前N/4的X1(k),后N/4的X1(k)为,(奇中偶),(奇中奇),同样对n为奇数时，N/2点分为两个N/4点的序列进行DFT，则有:,例如,N=8时的DFT可分解为四个N/4的DFT,具体步骤如下:,(1) 将原序列x(n
7、)的“偶中偶”部分:,构成N/4点DFT， 从而得到X3(0), X3(1)。,(2) 将原序列x(n)的“偶中奇”部分:,构成N/4点DFT， 从而得到X4(0), X4(1)。,(3) 将原序列x(n)的“奇中偶”部分:,构成N/4点DFT， 从而得到X5(0), X5(1)。,(4) 将原序列x(n)的“奇中奇”部分:,构成N/4点DFT， 从而得到X6(0), X6(1)。,(0)= (0)= (0) N/4(1)= (2)= (4) DFT(0)= (1)= (2) N/4(1)= (3)= (6) DFT(0)= (0)= (1) N/4 (1)= (2)= (5) DFT (0)
8、= (1)= (3) N/4(1)= (3)= (7) DFT,3 1,3 1,4 1,4 1,5 2,5 2,6 2,6 2,0,2,N,N,0,2,N,N,-1,-1,-1,-2,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),（7）由X1(0), X1(1), X1(2), X1(3)，X2(0), X2(1),X2(2), X2(3)进行碟形运算, 得到X(0), X(1), X(2), X(3) X(4), X(5), X(6), X(7) 。,（5）由 X3(0), X3(1), X4(0), X4(1)进行碟形运算, 得到X1(0),
9、X1(1), X1(2), X1(3)。,（6）由 X5(0), X5(1), X6(0), X6(1)进行碟形运算, 得到X2(0), X2(1), X2(2), X2(3)。,这样,又一次分解,得到四个N/4点DFT,两级蝶形运算,其运算量有大约减少一半 即为N点DFT的1/4。对于N=8时DFT,N/4点即为两点DFT,因此,亦即,8点DIT-FFT运算流图,这种FFT算法,是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分解的,所以称作按时间抽取的算法 。,(二).运算量由上述分析可知,N=8需三级蝶形运算 N=2 =8,由此可知,N=2L 共需L级蝶形运算,而且每级都由N/2个
10、蝶形运算 组成,每个蝶 形运算有一次复乘,两次复加。,3,因此,N点的FFT的运算量为 复乘: mF =（N/2）L=（N/2） log2 N 复加: aF =N L=N log2 N由于计算机的乘法运算比加法运算所 需的时间多得多，故以乘法作为比较基准.,Example : 如N=4,x(n)=x0, x1, x2, x3even: x0, x2 even: x0odd: x2odd: x1, x3 even: x1odd: x3,分成四个1点的序列,1点序列的DFT就是序列本身，即不用计算,X1(k),X2(k),k=0,N/2-1,这里,蝶形运算,(三).DIT-FFT的运算规律及编程思
11、想,1、原位运算：每个蝶形的输入和输出均为相同位数。利用同一单元存储蝶形计算的 输入、输出数据,。即实现所谓原位运算。每一组(列)有N/2个蝶形运算,所以只需N个存储单元,可节省大量内存，因而硬件成本低。 2、旋转因子的变化规律：N点DFT，共有M级蝶形运算，每级有N/2个蝶形。,称为旋转因子，p称为旋转因子的指数。设L=1，2，M，表示从左到右的运算级数，第L级有 个不同的旋转因子，,对于 ， 各级的旋转因子表示为L=1时，L=2时，L=3时，,对于 的一般情况，第L级的旋转因子为,由于,所以,通过上式，可以计算第L级运算的旋转因子。实际的计算中L,J均为循环变量，从而可以求出旋转因子。,则
12、,3.蝶形运算规律,设序列x（n）经过时域抽选（位倒序）存入数组X,如果蝶形运算的两个输 入数据相距B个点，,XL(J),XL(J+B),XL-1(J),XL-1(J+B),编程的运算方法：从输入端（第1级）开始，逐级进行，共进行M级运算。 在进行第L级运算时，依次求出 个不同的旋转因子，然后 计算其对应的 个蝶形。可用三重循环程序实现DIT-FFT运算。,4. 倒位序规律由图可知,输出X(k)按正常顺序排列在存储单元,而 输入是按顺序:这种顺序称作倒位序,即二进制数倒位。,这是由奇偶分组造成的,以N=8为例说明如下:,倒位序实现输入序列先按自然顺序 存入存储单元,然后经变址运 算来实现倒位序
13、排列.设输入序列的序号为n,二 进制为(n2 n1 n0 )2 ,倒位序 顺序用 表示,其倒位序二 进制为(n0 n1 n2 )2 , 例如 ， N=8时如下表：,自然顺序n 二进制n n n 倒位序二进制n n n 倒位顺序n,0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7,用硬件电路和汇编语言程序产生倒序很容易， 用高级语言倒序的规律为：倒序数是在M位二进制数最高位加1，逢2向右进位。,000,100,010,110,111,变址处理方法,存储单元,自然顺序,变址,倒位序,5.蝶形运算两节点的距离:2m-1其中,m表示第m列,且m =1, ,L例如N=8=23 ,第一级(列)距离为21-1=1,第二级(列)距离为22-1=2，第三级(列)距离为23-1=4。,四.DIF的FFT算法(桑德图基算法),(一).算法原理1.N点DFT的另一种表达形式,
