第四章快速傅里叶变换.ppt

第四章快速傅里叶变第四章快速傅里叶变换换现在学习的是第1页，共35页1965年年库利库利-图基图基计算数学计算数学(Mathematic of Computation)“机器计算傅里叶级数的一种算法机器计算傅里叶级数的一种算法”揭开了揭开了FFT发展史上的第一页发展史上的第一页1967年至年至1968年间年间FFT的数字硬件制成的数字硬件制成电子数字计算机电子数字计算机FFT算法迅速发展算法迅速发展DFT走向实用走向实用现在学习的是第2页，共35页一、直接计算直接计算DFT算法算法存在的问题及改进途径存在的问题及改进途径问题提出：问题提出：设有限长序列设有限长序列x(n),非零值长度为非零值长度为N,计计算对算对x(n)进行一次进行一次DFT运算，共需多运算，共需多大的运算工作量大的运算工作量?(一)存在的问题存在的问题现在学习的是第3页，共35页1.比较比较DFT与与IDFT之间的运算量之间的运算量其中x(n)为复数，也为复数所以DFT与与IDFT二者计算量相同二者计算量相同。现在学习的是第4页，共35页2.DFT的复数运算量的复数运算量计算一个计算一个X(k)(一个频率成份一个频率成份)值，运算量为值，运算量为例例 k=1 则要进行则要进行完成整个完成整个DFT运算，其计算量为：运算，其计算量为：N次复数乘法次复数乘法+(N-1)次复数加法次复数加法N*N次复数相乘次复数相乘+N*(N-1)次复数加法次复数加法现在学习的是第5页，共35页3.一次一次复数运算量换算成实数运算量复数运算量换算成实数运算量4次复数乘法2次实数加法复数运算要比实数运算复杂，需要的运算时间长。复数运算要比实数运算复杂，需要的运算时间长。一个复数乘法包括一个复数乘法包括4次实数次实数乘法乘法和和2次实数次实数加法加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)一个复数加法包括一个复数加法包括2次实数次实数加法加法。(a+jb)+(c+jd)=(a+c)+j(b+d)2次实数加法现在学习的是第6页，共35页4.计算计算DFT需要的实数运算量需要的实数运算量由此看出：直接计算由此看出：直接计算DFT时，乘法次数与加法次数都是和时，乘法次数与加法次数都是和N2成比例的。当成比例的。当N很大时，所需工作量非常可观很大时，所需工作量非常可观。4N2次实数相乘和次实数相乘和2N(2N-1)次实数相加次实数相加.整个整个DFT实数运算量为：实数运算量为：N*N次复数乘次复数乘 +N*(N-1)次复数加次复数加整个整个DFT的复数运算量转换为实数运算量：的复数运算量转换为实数运算量：2*N*N次次实数加实数加4*N*N次次实数乘实数乘2*N*(N-1)次次实数加实数加2N(2N-1)次实数加次实数加现在学习的是第7页，共35页例子例子例例1:当当N=1024点时，直接计算点时，直接计算DFT需要：需要：这对实时性很强的信号处理这对实时性很强的信号处理(如雷达信号处理如雷达信号处理它它对计算速度有十分苛刻的要求对计算速度有十分苛刻的要求)来讲，迫切需要改进来讲，迫切需要改进DFT的计算方法，以减少总的运算次数。的计算方法，以减少总的运算次数。4*N2 =4194304 次实数乘次实数乘2N(2N-1)=4192256 次实数加次实数加现在学习的是第8页，共35页(二二)改善改善DFT运算效率的基本途径运算效率的基本途径基本思路：利用利用DFT运算的系数运算的系数 的固有对称性和周期性，的固有对称性和周期性，改善改善DFT的运算效率。的运算效率。1.合并法：合并合并法：合并DFT运算中的某些项。运算中的某些项。2.分解法：将长序列分解法：将长序列DFT利用对称性和周利用对称性和周期性，分解为短序列期性，分解为短序列DFT。现在学习的是第9页，共35页1.利用利用DFT运算的系数运算的系数 的固有对称性和周期性，的固有对称性和周期性，改善改善DFT的运算效率的运算效率的共轭对称性：的周期性：现在学习的是第10页，共35页2、将长序列、将长序列DFT利用对称性和周期性分解利用对称性和周期性分解为短序列为短序列DFTDFT的运算量与的运算量与N2成正比成正比大点数大点数N的的DFT小点数小点数DFT的组合的组合分分解解减少运算工作量减少运算工作量思路：思路：现在学习的是第11页，共35页把把N点数据分成二半：点数据分成二半：其运算量为：其运算量为：再分二半：再分二半：+=+=这样一直分下去，剩下两点的变换。方法方法现在学习的是第12页，共35页结论结论快速付里叶变换快速付里叶变换(FFT)就是在此特性基础上发展起来，并就是在此特性基础上发展起来，并产生了多种产生了多种FFT算法，其基本上可分成两大类：算法，其基本上可分成两大类：按按抽取方法抽取方法分：分：时间抽取法时间抽取法(DIT);频率抽取法频率抽取法(DIF)按按“基数基数”分：基分：基-2FFT算法；基算法；基-4FFT算法；算法；混合基混合基FFT算法；分裂基算法；分裂基FFT算法算法其它其它方法：线性调频方法：线性调频Z变换变换(CZT法法)现在学习的是第13页，共35页二、基二、基-2按时间抽取的按时间抽取的FFT算法算法(Coolkey-Tukey)（一）算法原理（一）算法原理 设设输入序列长度为输入序列长度为N=2M (M为正整数），将该序列为正整数），将该序列按时间顺序的奇偶分解按时间顺序的奇偶分解为越来越短的子序列，称为基为越来越短的子序列，称为基2按按时间抽取的时间抽取的FFT算法。也称为算法。也称为Coolkey-Tukey算法。算法。特别注意：特别注意：若不满足这个条件，可以人为地加上若干零值若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到（加零补长）使其达到 N=2M序列长度序列长度N必须满足必须满足 N=2M，M为整数为整数.现在学习的是第14页，共35页(二二)算法步骤算法步骤DFT变换：变换：1.分组，变量置换先将先将x(n)按按n的奇偶分为两的奇偶分为两 组，作变量置换组，作变量置换:当当n=偶数时，令偶数时，令n=2r;当当n=奇数时，令奇数时，令n=2r+1;得到：得到：x(2r)=x1(r);x(2r+1)=x2(r);r=0N/2-1;现在学习的是第15页，共35页利用得2.分组序列的分组序列的DFT中中生成两个子序列现在学习的是第16页，共35页X1(k):原序列偶数项的原序列偶数项的DFTX2(k):原序列奇数项的原序列奇数项的DFT现在学习的是第17页，共35页3.结论结论1再应用再应用W系数的周期性，求出用系数的周期性，求出用X1(k),X2(k)表达的后表达的后半部的半部的X(k+N/2)的值。的值。一个一个N点的点的DFT被分解为两个被分解为两个N/2点点DFT。X1(k),X2(k)这两个这两个N/2点的点的DFT按照：按照：现在学习的是第18页，共35页4.求出后半部的表示式求出后半部的表示式看出：后半部的看出：后半部的k值所对应的值所对应的X1(k),X2(k)则完全重复则完全重复了前半部分的了前半部分的k值所对应的值所对应的X1(k),X2(k)的值。的值。现在学习的是第19页，共35页5.结论结论2频域中的频域中的N个点频率成分为：个点频率成分为：只要求出（只要求出（0N/2-1）区间内的各个整数区间内的各个整数k值所对值所对应的应的X1(k),X2(k)值，即可以求出值，即可以求出(0N-1)整个区整个区间内全部间内全部X(k)值，这就是值，这就是FFT能大量节省计算能大量节省计算的的关键。关键。结论：结论：现在学习的是第20页，共35页6.结论结论3由于N=2M，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算加减运算。现在学习的是第21页，共35页（三）蝶形结（三）蝶形结即蝶式计算结构即蝶式计算结构,或蝶式信号流图。或蝶式信号流图。X1(k)X2(k)作图要素：作图要素：(1)左入右出左入右出(2)上加下减上加下减(3)系数标箭头系数标箭头 上面上面频域频域中前中前/后半部分表示式可以用蝶形信号后半部分表示式可以用蝶形信号流图表示如下。流图表示如下。现在学习的是第22页，共35页例子例子先将N=8DFT分解成2个4点DFT：可知：时域上时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上频域上：X(0)X(3)，由X(k)给出 X(4)X(7),由X(k+N/2)给出求求 N=23=8点点FFT变换变换解：（1）先按N=8-N/2=4，做4点的DFT：现在学习的是第23页，共35页将将N=8点分解成点分解成2个个4点的点的DFT的信号流图的信号流图 4点DFTx(0)x(2)x(4)x(6)4点DFTx(1)x(3)x(5)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶数序列奇数序列X(4)X(7)同学们自已写x1(r)x2(r)现在学习的是第24页，共35页(2)N/2(4点点)-N/4(2点点)FFT 因为因为4点点DFT还是比较麻烦，所以再继续分解。还是比较麻烦，所以再继续分解。若将若将N/2(4点点)子序列按奇子序列按奇/偶分解成两个偶分解成两个N/4点（点（2点）子序列。点）子序列。即将即将x1(r)和和x2(r)分解成奇、偶两个分解成奇、偶两个N/4点（点（2点）点的子序列。点）点的子序列。现在学习的是第25页，共35页一个一个2点的点的DFT蝶形流图蝶形流图2点DFT2点DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)现在学习的是第26页，共35页另一个另一个2点的点的DFT蝶形流图蝶形流图2点DFT2点DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)现在学习的是第27页，共35页(3)将将N/4（2点）点）DFT再分解成再分解成2个个1点的点的DFT 最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。现在学习的是第28页，共35页2个个1点的点的DFT蝶形流图蝶形流图 1点DFTx(0)1点DFTx(4)X3(0)X3(1)进一步简化为蝶形流图：X3(0)X3(1)x(0)x(4)现在学习的是第29页，共35页(4)一个完整一个完整N=8的按时间抽取的按时间抽取FFT的运算流图的运算流图 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2现在学习的是第30页，共35页三、基三、基-2按频率抽取的按频率抽取的FFT算法算法(DIF)(Sander-Tukey)(一一)算法原理算法原理 设输入序列长度为设输入序列长度为N=2M(M为正整数，将该序列的为正整数，将该序列的频域的频域的输出序列输出序列X(k)(也是也是M点序列点序列)，按其，按其频域顺序的奇偶分解频域顺序的奇偶分解为为越来越短的子序列，称为基越来越短的子序列，称为基2按频率抽取的按频率抽取的FFT算法。算法。也称为也称为Sander-Tukey算法。算法。现在学习的是第31页，共35页基基-2按时间抽取的按时间抽取的FFT时域时域：按：按奇偶奇偶划分划分 频域频域：按：按前后前后划分划分基基-2按频率抽取的按频率抽取的FFT时域时域：按：按前后前后划分划分 频域频域：按：按奇偶奇偶划分划分现在学习的是第32页，共35页例子例子频域上：X(0),X(2),X(4),X(6)由x1(n)给出 X(1),X(3),X(5),X(7),由x2(n)给出求求 N=23=8点点DIF（1）先按N=8-N/2=4，做4点的DIF：现在学习的是第33页，共35页将将N=8点分解成点分解成2个个4点的点的DIF的信号流图的信号流图 4点DFTx(0)x(1)x(2)x(3)4点DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列x1(n)x2(n)X2(k)现在学习的是第34页，共35页(4)一个完整一个完整N=8的按频率抽取的按频率抽取FFT的运算流图的运算流图 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)m=0m=1m=2现在学习的是第35页，共35页