《数字信号处理》第四章快速付立叶变换(FFT)课件.ppt
4-14-1引言一.DFT.DFT的计算工作量 两者的差别仅在指数的符号和因子1/N.DFT与与IDFT运算特点运算特点同理：同理：IDFT运算量与运算量与DFT相同。相同。通常x(n)和都是复数,所以计算一个 X(k)的值需要N次复数乘法运算,和 次 复数加法运算.那么,所有的X(k)就要N2次复 数乘法运算,N(N-1)次复数加法运算.当N很 大时,运算量将是惊人的,如N=1024,则要完 成1048576 次(一百多万次)运算.这样,难以做到实时处理.一个X(k)的值的工作量,如X(1)二.改进的途径 1.的对称性和周期性得:对称性:周期性:利用上述特性,可以将有些项合并,并将DFTDFT分解为短序列,从而降低运算次数,提高运算速度.1965.1965年,库利(cooley)(cooley)和图基(Tukey)(Tukey)首先提出FFTFFT算法.对于N N点DFT,DFT,仅需(N/2)log(N/2)log2 2N N 次复数乘法运算.例如N=1024=2N=1024=21010 时，需要(1024/2)log(1024/2)log2 2 2 21010=512*10=5120=512*10=5120次。5120/1048576=5120/1048576=4.88%4.88%,速度提高2020倍FFT算法分类算法分类:q时间抽选法时间抽选法DIT:Decimation-In-Timeq频率抽选法频率抽选法DIF:Decimation-In-Frequency4-2 4-2 按时间抽取按时间抽取(DIT)(DIT)的的FFTFFT算法算法 库利库利-图基算法图基算法一.算法原理(基2FFT)2FFT)(一)N/2)N/2点DFTDFT1.1.先将 按n的奇偶分为两组作DFT,DFT,设N=2N=2L L,不足时,可补些零。这样有:n为偶数时:n为奇数时:因此，由于由于:所以所以,上式可表示为上式可表示为:(n为偶数)(n为奇数)其中,2.2.两点结论:(1)X(1)X(k),X(k),X(k)(k)均为N/2N/2点的DFTDFT。(2)X(k)=X(2)X(k)=X(k)+W(k)+W X X(k)(k)只能确定出 X(k)X(k)的k=k=个；即前一半的结果。1 21 2kN 同理,这就是说,X1(k),X2(k)的后一半,分别 等于其前一半的值。3.X(k)3.X(k)的后一半的确定的后一半的确定由于 （周期性）（周期性）,所以:可可见,X(k)X(k)的后一半，也完全由X X1 1(k)(k),X X2 2(k)(k)的前一半所确定。*N点的DFT可由两个N/2点的DFT来计算。又由于 ,所以实现上式运算的流图称作蝶形运算 前一半4.4.蝶形运算蝶形运算 后一半（N/2个蝶形)(前一半)(后一半)1 1 11-1-1由X1(k)、X 2(k)表示X(k)的运算是一种特殊的运算-碟形运算5.分解后的运算量：分解后的运算量：运算量减少了近一半运算量减少了近一半 例如 N=8N=8 时的DFT,DFT,可以分解为两个 N/2=4N/2=4点的DFTDFT.具体方法如下:(1)n(1)n为偶数时,即 分别记作:(2)n(2)n为奇数时,分别记作:x1 1(0)=(0)=x(0)(0)x1(1)=(1)=x(2)(2)N/2N/2点点 x1(2)=(2)=x(4)DFT (4)DFT x1(3)=(3)=x(6)(6)x2(0)=(0)=x(1)(1)x2(1)=(1)=x(3)(3)N/2N/2点点 x2(2)=(2)=x(5)(5)DFT DFT x2(3)=(3)=x(7)(7)1 2 X X1(0)(0)X X1(1)(1)X X1(2)(2)X X1(3)(3)X X2(0)(0)X X2(1)(1)X X2(2)(2)X X2(3)(3)WN2WN1WN0WN3-1-1-1-1X(0)X(0)X(1)X(1)X(2)X(2)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)(3)(3)对X X(k)(k)和X X(k)(k)进行蝶形运算,前半部为 X(0)X(3),X(0)X(3),后半部分为X(4)X(7)X(4)X(7)整个过程如下图所示:由于N=2N=2 L,所以 N/2N/2仍为偶数,可以进 一步把每个N/2N/2点的序列再按其奇偶部分 分解为两个N/4N/4的子序列。例如，n为偶数时的 N/2N/2点分解为:(二二)N/4)N/4点点DFTDFT进行N/4N/4点的DFTDFT,得到(偶中偶)(偶中奇)从而可得到前N/4的X1(k)后N/4的X1(k)为注意到(奇中偶奇中偶)(奇中奇奇中奇)同样对n n为奇数时，N/2N/2点分为两个N/4N/4点 的序列进行DFT，则有:例如,N=8N=8时的DFTDFT可分解为四个N/4N/4的DFT,DFT,具体步骤如下:(1)将原序列x(n)的“偶中偶”部分:构成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)。（5）由 X3(0),X3(1),X4(0),X4(1)进行碟形运算,得到X1(0),X1(1),X1(2),X1(3)。（6）由 X5(0),X5(1),X6(0),X6(1)进行碟形运算,得到X2(0),X2(1),X2(2),X2(3)。(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)=(1)=(3)N/4 (1)=(3)=(7)DFT3 13 14 14 15 25 26 26 2 02NN02NNWWWW0123NNNN-1-1-1-2-1-1WWWWX(0)X(1)X(0)X(1)X(0)X(1)X(0)X(1)33445566X(0)X(1)X(2)X(3)X(0)X(1)X(2)X(3)11122221X(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)。这样,又一次分解,得到四个N/4N/4点DFT,DFT,两级蝶形运算,其运算量有大约减少一半 即为N N点DFTDFT的1/41/4。对于N=8N=8时DFT,N/4DFT,N/4点即为两点DFT,DFT,因此 亦即,(0)(4)(2)(6)(1)(5)(3)(7)WN0WN0WN0W0N-1-1-1-1X(0)X(1)X(0)X(1)X(0)X(1)X(0)X(1)33445566WN0WN2WN0WN2-1-1-1-1X(0)X(1)X(2)X(3)X(0)X(1)X(2)X(3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)因此,8点DFT的FFT的运算流图如下 这种FFTFFT算法,是在时间上对输入序列 的次序是属于偶数还是属于奇数来进行分 解的,所以称作按时间抽取的算法 。(DITDIT)（三）FFT运算量与运算特点 1 N=2L时，共有L=log2N级运算；每一级有N/2个蝶形结。2每一级有N个数据中间数据），且每级只用到本级的转入中间数据，适合于迭代运算。3计算量：每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N 次复乘法；复加法L*N=Nlog2N 次。与直接DFT定义式运算量相比(倍数)N2/(Nlog2N)。当 N大时，此倍数很大。比较比较DFT 参考参考P150 表表4-1 图图4-6可以直观看出，当点数可以直观看出，当点数N越大时，越大时，FFT的优点更突出。的优点更突出。(0)=(0)=X X0 0(0)(0)X X1 1(0)(0)X X2 2(0)X(0)X3 3(0)(0)=X(0)=X(0)(4)=(4)=X X0 0(1)(1)X X1 1(1)X(1)X2 2(1)X(1)X3 3(1)(1)=X(1)=X(1)(2)=(2)=X X0 0(2)(2)X X3 3(2)(2)=X(2)=X(2)(6)=(6)=X X0 0(3)(3)X X3 3(3)(3)=X(3)=X(3)(1)=(1)=X X0 0(4)(4)X X1 1(4)X(4)X2 2(4)X(4)X3 3(4)(4)=X(4)=X(4)(5)=(5)=X X0 0(5)(5)X X3 3(5)(5)=X(5)=X(5)(3)=(3)=X X0 0(6)(6)X X3 3(6)(6)=X(6)=X(6)(7)=(7)=X X0 0(7)(7)X X1 1(7)X(7)X2 2(7)X(7)X3 3(7)(7)=X(7)=X(7)WWWWN0N0N0N0-1-1-1-1WWWWN0N2N0N2-1-1-1-1WWWWNNNN0123.三三.DIT.DIT的的FFTFFT算法的特点算法的特点 1.1.原位运算输入数据、中间运算结果和最后输出均用同一存储器。设用m(m=1,2,L)表示第m列;用用k,jk,j表示蝶形输入数据所在的（上/下）行数(0,1,2,N-1);(0,1,2,N-1);这时任何一个蝶形运算可用下面通用式表示，即 由运算流图可知,一共有N N个输入个输入/出出行,一共有loglog2 2 N=LN=L列（级）蝶形运算(基本迭代运算).).1 1 11-1-1 所以,当m=1时,则有（前两个蝶形）当m=2时,则有（前两个蝶形）当m=3时,则有（前两个蝶形）可见,在某列进行蝶形运算的任意两个节点(行)k)k和j j的节点变量 就完全可以确定蝶形运算的结果 ,与其它行(节点)无关。这样,蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中,即实现所谓原位运算。每一组(列)有N/2N/2个蝶形运算,所以只需N N个存储单元，可以节 省存储单元。2 2 倒位序规律 由图可知,输出X X(k)(k)按正常顺序排列在存储单元,而输入是按顺序:这种顺序称作倒位序,即二进制数倒位。n=00n=10n=01n=11n=01n=1101010101 (n2)x(000)0 x(100)4 x(010)2 x(110)6 x(001)1x(101)5 x(011)3 x(111)7（偶）（奇）这是由奇偶分组造成的,以N=8N=8为例 说明如下:3.3.倒位序实现 输入序列先按自然顺序存入存储单 元,然后经变址运算来实现倒位序排列 设输入序列的序号为n n,二进制为 (n2 n1 n0)2,倒位序顺序用 表示,其倒位序二进制为(n0 n1 n2)2,例如，N=8N=8时如下表：0 00 0 0 0 0 00 0 0 0 0 0 0 0 1 01 0 0 0 1 11 1 0 0 0 4 0 4 2 02 0 1 1 0 00 0 1 1 0 2 0 2 3 03 0 1 1 1 11 1 1 1 0 6 0 6 4 14 1 0 0 0 00 0 0 0 1 1 1 1 5 15 1 0 0 1 11 1 0 0 1 5 1 5 6 16 1 1 1 0 00 0 1 1 1 3 1 3 7 17 1 1 1 1 11 1 1 1 1 7 1 7 自然顺序n n 二进制n n n n n n 倒位序二进制n n n n n n 倒位顺序n n2 1 0 0 1 2A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)变址处理方法变址处理方法存储单元自然顺序变址倒位序4.4.蝶形运算两节点的距离蝶形运算两节点的距离:2m-1 其中,m表示第m列,且且m=1,L=1,L 例如N=8=2N=8=23 3,第一级(列)距离为2 21-11-1=1,=1,第二级(列)距离为2 22-12-1=2=2，第三级(列)距离为2 23-13-1=4=4。(0)(4)(2)(6)(1)(5)(3)(7)WN0WN0WN0W0N-1-1-1-1X(0)X(1)X(0)X(1)X(0)X(1)X(0)X(1)33445566WN0WN2WN0WN2-1-1-1-1X(0)X(1)X(2)X(3)X(0)X(1)X(2)X(3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)结点距离为1节（结）点距离为25.WNr 的确定(仅给出方法)考虑蝶形运算两节点的距离为2m-1 ,蝶 形运算可表为 Xm(k)=Xm-1(k)+Xm-1(k+2m-1)WNr Xm(k+2m-1)=Xm-1(k)-Xm-1(k+2m-1)WNr 由于N N为已知,所以将r r的值确定即可。r r的求解方法：的求解方法：（1 1）将将上上式式的的第第一一个个节节点点标标号号值值k k表表示示为为L L位二进制数，注意：位二进制数，注意：（2 2）把把此此二二进进制制数数乘乘上上 ，即即左左移移L-L-m m位位，右右边边空空出出位位添添0 0，此此数数即即为为所所求求r r的的二二进制数。进制数。（严格证明参考有关书籍）（严格证明参考有关书籍）例如 N=8=2N=8=23 3 (1)(1)k=2,m=3 的r r值,k=2=(010)2 左移L-m=3-3=0,r=(010)2=2;(2)k=3,m=3 的r r值;k=3=(011)2,左移0位,r=3r=3；(3)(3)k=5,m=2的值;k=5=(101)2 左移L-m=1=1位 r=(010)2=2。为此，令k=(n2n1n0)2,再再将k=(n2n1n0)2 左移(L-m)位,右边位置补零,就可得到(r)2 的值，即(r)2=(k)22L-m 。6 6.存储单元 存输入序列(n),n=0,1,N-1,(n),n=0,1,N-1,计N N 个单元;存放系数 ,r=0,1,N/2-1,r=0,1,N/2-1,需N/2N/2个存储单元；共计(N+N/2)个存储单元。4-3 DIF4-3 DIF的的FFTFFT算法算法(桑德桑德图基算法图基算法)一.算法原理 1.N1.N点DFTDFT的另一种表达形式 由于 故 因此 X(k)可表为 2.N点DFT按k的奇偶分组可分为两个N/2的DFT 当k k为偶数,即 k=2r k=2r时,(-1)k=1；当k k为奇数,即 k=2r+1 k=2r+1 时(-1)k=-1 。这时 X(k)X(k)可分为两部分：k k为偶数时：可见,上面两式均为N/2N/2的DFTDFT。k k为奇数时：-1-13.3.蝶形运算-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 34.N=84.N=8时时,按按k k的奇偶分解过程的奇偶分解过程 先蝶形运算，后先蝶形运算，后DFT:DFT:5.5.仿照DITDIT的方法 再将N/2N/2点DFTDFT按k k的奇偶分解为两个N/4N/4点的DFTDFT,如此进行下去,直至分解为2 2点DFTDFT。(0)X(0)(0)X(0)(1)X(4)(1)X(4)(2)X(2)(2)X(2)(3)X(6)(3)X(6)(4)X(1)(4)X(1)(5)X(5)(5)X(5)(6)X(3)(6)X(3)(7)X(7)(7)X(7)-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 3-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 02 20 02 2-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 00 00 00 0例如 N=8 N=8时DIFDIF的FFTFFT流图如下：二.原位运算 每级(列)都是由N/2N/2个蝶形运算构 成,即 -1-1W WN Nr r三三.蝶形运算两节点的距离蝶形运算两节点的距离 一般公式为2L-m=N/2m 例如 N=2N=23 3=8=8：(1)(1)m=1 时的距离为 8/2=48/2=4；(2)(2)m=2 时的距离为 8/4=2;8/4=2;(3)(3)m=3 时的距离为 8/8=18/8=1。r r的求法：k=(n2 n1 n0),左移m-1位,右边空出补零,得(r)r)2 2,亦即(r)r)2 2=(k)=(k)2 2 2m-1.例如,N=8:N=8:(1)m=1,k=2,k=(010)(1)m=1,k=2,k=(010)2 2 左移0位,(,(r)r)2 2=(010)=(010)2 2=2;=2;(2)m=2,k=1,k=(001)(2)m=2,k=1,k=(001)2 2 左移1 1位,(,(r)r)2 2=(010)=(010)2 2=2;=2;(3)m=2,k=5,k=(101)(3)m=2,k=5,k=(101)2 2 左移1 1位,(,(r)r)2 2=(010)=(010)2 2=2.=2.四四.的计算的计算 由于DIFDIF蝶形运算的两节点的距离为 N/2m,所以蝶形运算可表为：1.1.相同点 (1)(1)进行原位运算；(2)(2)运算量相同,均为（N/2)Log2N次复乘,N Log2N次复加。2.2.不同点 (1)DIT(1)DIT输入为倒位序,输出为自然顺序；DIFDIF正好与此相反。但DITDIT也有输入为自然顺序,输出为倒位序的情况。五五.DIFDIF法与法与DITDIT法的异同法的异同(2)(2)蝶形运算不同a.a.(DIT)(DIT)用矩阵表示=11b.b.(DFT)(DFT)用矩阵表示=11(3)(3)两种蝶形运算的关系 互为转置（矩阵）；将流图的所有支路方向都反向,交换输入和输出，即可得到另一种蝶形。a.a.(DIT)(DIT)b.b.(DFT)(DFT)1111 4-4 IFFT4-4 IFFT算法一.稍微变动FFT程序和参数可实现IFFT 比较两式可知,只要DFTDFT的每个系数 换成 ,最后再乘以常数1/N1/N就可以得到IDFTIDFT的快速算法-IFFT。另外,可以将常数1/N1/N分配到每级运算中,也就是每级蝶形运算均乘以1/1/2 2。二.不改(FFT)(FFT)的程序直接实现IFFTIFFT 这就是说,先将X(k)X(k)取共轭,即将X(k)X(k)的虚部乘-1-1，直接利用FFTFFT程序计算DFT；然后再取一次共轭；最后再乘1/N,1/N,即得 。所以FFT,IFFTFFT,IFFT可用一个子程序。共轭共轭FFT共轭共轭乘乘1/N 4-54-5 线性卷积的FFTFFT算法一.线性卷积的长度 设一离散线性移不变系统的冲激响 应为 ,其输入信号为 .其输出 为 .并且 的长度为L点,的 长度为M点,则：以实例说明：0 1 0 1 2 2 3 31 12 23 3.。1。0 1 0 1 1 12 23 32 3。0 0 1 1 2 2 3 3。0 1 0 1 1 12 23 32 3。0 0 1 1 2 2 3 3 4 40 0 1 1 2 2 3 3 4 4 5 50 1 0 1 1 12 23 32 3。0 0 1 1 2 2 3 3 4 4 5 51 13 33 35 56 66 6。二.用FFTFFT算 的步骤：FFTFFTIFFTxx(n)h(n)y(n)X(k)H(k)Y(k)流程图三.几点说明 1.1.当 M=L 时,用圆周卷积计算线性 卷积的速度快,点数越多,速度越快,N N6464时,速度增加明显.2.2.LM 时,速度增加不太明显,为了 增加速度,采用(1)(1)重叠相加法(2)(2)重叠保留法.
