快速傅里叶变换课件

第四章快速傅里叶变换第四章快速傅里叶变换11965年库利--图基《计算数学》(MathematicofComputation)“机器计算傅里叶级数的一种算法”——揭开了FFT发展史上的第一页1967年至1968年间FFT的数字硬件制成电子数字计算机——FFT算法迅速发展——DFT走向实用1965年库利--图基《计算数学》(Mathematico2一、直接计算DFT算法——存在的问题及改进途径问题提出：设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT运算，共需多大的运算工作量?(一)存在的问题一、直接计算DFT算法——存在的问题及改进途径问题提出：设有31.比较DFT与IDFT之间的运算量其中x(n)为复数，也为复数所以DFT与IDFT二者计算量相同。1.比较DFT与IDFT之间的运算量其中x(n)为复数，42.DFT的复数运算量计算一个X(k)(一个频率成份)值，运算量为例k=1则要进行完成整个DFT运算，其计算量为：N次复数乘法+(N-1)次复数加法N*N次复数相乘+N*(N-1)次复数加法2.DFT的复数运算量计算一个X(k)(一个频率成份)53.一次复数运算量换算成实数运算量4次复数乘法2次实数加法复数运算要比实数运算复杂，需要的运算时间长。一个复数乘法包括4次实数乘法和2次实数加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)一个复数加法包括2次实数加法。(a+jb)+(c+jd)=(a+c)+j(b+d)2次实数加法3.一次复数运算量换算成实数运算量4次复数乘法2次实数加法复64.计算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)次实数加4.计算DFT需要的实数运算量由此看出：直接计算DFT时，乘7例子例1:当N=1024点时，直接计算DFT需要：这对实时性很强的信号处理(如雷达信号处理——它对计算速度有十分苛刻的要求)来讲，迫切需要改进DFT的计算方法，以减少总的运算次数。4*N2=4194304次实数乘2N(2N-1)=4192256次实数加例子例1:当N=1024点时，直接计算DFT需要：这对实时性8(二)改善DFT运算效率的基本途径基本思路：利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率。1.合并法：合并DFT运算中的某些项。2.分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。(二)改善DFT运算效率的基本途径基本思路：利用DFT运91.利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率的共轭对称性：的周期性：1.利用DFT运算的系数的固有对称性和周102、将长序列DFT利用对称性和周期性分解为短序列DFTDFT的运算量与N2成正比大点数N的DFT小点数DFT的组合分解减少运算工作量思路：2、将长序列DFT利用对称性和周期性分解为短序列DFTDFT11把N点数据分成二半：其运算量为：再分二半：+=+++=这样一直分下去，剩下两点的变换。方法把N点数据分成二半：其运算量为：再分二半：+=+++=这样一12结论快速付里叶变换(FFT)就是在此特性基础上发展起来，并产生了多种FFT算法，其基本上可分成两大类：按抽取方法分：时间抽取法(DIT);频率抽取法(DIF)按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：线性调频Z变换(CZT法)结论快速付里叶变换(FFT)就是在此特性基础上发展起来，并产13二、基--2按时间抽取的FFT算法

(Coolkey-Tukey)（一）算法原理

设输入序列长度为N=2M

(M为正整数），将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。特别注意：若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到N=2M序列长度N必须满足N=2M，M为整数.二、基--2按时间抽取的FFT算法

(Coolkey-Tuk14(二)算法步骤DFT变换：1.分组，变量置换先将x(n)按n的奇偶分为两组，作变量置换:当n=偶数时，令n=2r;当n=奇数时，令n=2r+1;得到：x(2r)=x1(r);x(2r+1)=x2(r);r=0…N/2-1;(二)算法步骤DFT变换：1.分组，变量置换先将x(n15利用得2.分组序列的DFT中生成两个子序列利用得2.分组序列的DFT中生成两个子序列16X1(k):原序列偶数项的DFTX2(k):原序列奇数项的DFTX1(k):原序列偶数项的DFTX2(k):原序列奇173.结论1再应用W系数的周期性，求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：3.结论1再应用W系数的周期性，求出用X1(k),X2(k184.求出后半部的表示式看出：后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。4.求出后半部的表示式看出：后半部的k值所对应的X1(k),195.结论2频域中的N个点频率成分为：只要求出（0~N/2-1）区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0~N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。结论：5.结论2频域中的N个点频率成分为：只要求出（0~N/2-1206.结论3由于N=2M，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。6.结论3由于N=2M，因此N/2仍为偶数，可以依照上面方法21（三）蝶形结即蝶式计算结构,或蝶式信号流图。X1(k)X2(k)作图要素：(1)左入右出(2)上加下减(3)系数标箭头上面频域中前/后半部分表示式可以用蝶形信号流图表示如下。（三）蝶形结即蝶式计算结构,或蝶式信号流图。X1(k)X2(22例子先将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：例子先将N=8DFT分解成2个4点DFT：求N=23=8点23将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)将N=8点分解成2个4点的DFT的信号流图4点x(0)4点24(2)N/2(4点)-->N/4(2点)FFT因为4点DFT还是比较麻烦，所以再继续分解。若将N/2(4点)子序列按奇/偶分解成两个N/4点（2点）子序列。即将x1(r)和x2(r)分解成奇、偶两个N/4点（2点）点的子序列。(2)N/2(4点)-->N/4(2点)FFT25一个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)一个2点的DFT蝶形流图2点DFT2点DFTx(0)x(2)26另一个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)另一个2点的DFT蝶形流图2点DFT2点DFTx(1)x(327(3)将N/4（2点）DFT再分解成2个1点的DFT最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。(3)将N/4（2点）DFT再分解成2个1点的DFT282个1点的DFT蝶形流图1点DFTx(0)1点DFTx(4)X3(0)X3(1)进一步简化为蝶形流图：X3(0)X3(1)x(0)x(4)2个1点的DFT蝶形流图1点DFTx(0)1点DFTx(429(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(4)一个完整N=8的按时间抽取FFT的运算流图x(0)X30三、基--2按频率抽取的FFT算法(DIF)(Sander-Tukey)(一)算法原理

设输入序列长度为N=2M(M为正整数，将该序列的频域的输出序列X(k)(也是M点序列)，按其频域顺序的奇偶分解为越来越短的子序列，称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。三、基--2按频率抽取的FFT算法(DIF)(Sande31基--2按时间抽取的FFT时域：按奇偶划分频域：按前后划分基--2按频率抽取的FFT时域：按前后划分频域：按奇偶划分基--2按时间抽取的FFT时域：按奇偶划分32例子频域上：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：例子频域上：X(0),X(2),X(4),X(6)由x1(n33将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)将N=8点分解成2个4点的DIF的信号流图4点x(0)4点34(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(4)一个完整N=8的按频率抽取FFT的运算流图x(0)X35DIF与DIT比较相同之处：（1）DIF与DIT两种算法均为原位运算。（2）DIF与DIT运算量相同。它们都需要DIF与DIT比较相同之处：36不同之处：（1）DIF与DIT两种算法结构倒过来。DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读”程序。DIT为输入乱序，输出顺序。先运行“二进制倒读”程序，再进行求DFT。（2）DIF与DIT根本区别：在于蝶形结不同。DIT的复数相乘出现在减法之前。DIF的复数相乘出现在减法之后。不同之处：37第四章快速傅里叶变换第四章快速傅里叶变换381965年库利--图基《计算数学》(MathematicofComputation)“机器计算傅里叶级数的一种算法”——揭开了FFT发展史上的第一页1967年至1968年间FFT的数字硬件制成电子数字计算机——FFT算法迅速发展——DFT走向实用1965年库利--图基《计算数学》(Mathematico39一、直接计算DFT算法——存在的问题及改进途径问题提出：设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT运算，共需多大的运算工作量?(一)存在的问题一、直接计算DFT算法——存在的问题及改进途径问题提出：设有401.比较DFT与IDFT之间的运算量其中x(n)为复数，也为复数所以DFT与IDFT二者计算量相同。1.比较DFT与IDFT之间的运算量其中x(n)为复数，412.DFT的复数运算量计算一个X(k)(一个频率成份)值，运算量为例k=1则要进行完成整个DFT运算，其计算量为：N次复数乘法+(N-1)次复数加法N*N次复数相乘+N*(N-1)次复数加法2.DFT的复数运算量计算一个X(k)(一个频率成份)423.一次复数运算量换算成实数运算量4次复数乘法2次实数加法复数运算要比实数运算复杂，需要的运算时间长。一个复数乘法包括4次实数乘法和2次实数加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)一个复数加法包括2次实数加法。(a+jb)+(c+jd)=(a+c)+j(b+d)2次实数加法3.一次复数运算量换算成实数运算量4次复数乘法2次实数加法复434.计算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)次实数加4.计算DFT需要的实数运算量由此看出：直接计算DFT时，乘44例子例1:当N=1024点时，直接计算DFT需要：这对实时性很强的信号处理(如雷达信号处理——它对计算速度有十分苛刻的要求)来讲，迫切需要改进DFT的计算方法，以减少总的运算次数。4*N2=4194304次实数乘2N(2N-1)=4192256次实数加例子例1:当N=1024点时，直接计算DFT需要：这对实时性45(二)改善DFT运算效率的基本途径基本思路：利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率。1.合并法：合并DFT运算中的某些项。2.分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。(二)改善DFT运算效率的基本途径基本思路：利用DFT运461.利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率的共轭对称性：的周期性：1.利用DFT运算的系数的固有对称性和周472、将长序列DFT利用对称性和周期性分解为短序列DFTDFT的运算量与N2成正比大点数N的DFT小点数DFT的组合分解减少运算工作量思路：2、将长序列DFT利用对称性和周期性分解为短序列DFTDFT48把N点数据分成二半：其运算量为：再分二半：+=+++=这样一直分下去，剩下两点的变换。方法把N点数据分成二半：其运算量为：再分二半：+=+++=这样一49结论快速付里叶变换(FFT)就是在此特性基础上发展起来，并产生了多种FFT算法，其基本上可分成两大类：按抽取方法分：时间抽取法(DIT);频率抽取法(DIF)按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：线性调频Z变换(CZT法)结论快速付里叶变换(FFT)就是在此特性基础上发展起来，并产50二、基--2按时间抽取的FFT算法

(Coolkey-Tukey)（一）算法原理

设输入序列长度为N=2M

(M为正整数），将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。特别注意：若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到N=2M序列长度N必须满足N=2M，M为整数.二、基--2按时间抽取的FFT算法

(Coolkey-Tuk51(二)算法步骤DFT变换：1.分组，变量置换先将x(n)按n的奇偶分为两组，作变量置换:当n=偶数时，令n=2r;当n=奇数时，令n=2r+1;得到：x(2r)=x1(r);x(2r+1)=x2(r);r=0…N/2-1;(二)算法步骤DFT变换：1.分组，变量置换先将x(n52利用得2.分组序列的DFT中生成两个子序列利用得2.分组序列的DFT中生成两个子序列53X1(k):原序列偶数项的DFTX2(k):原序列奇数项的DFTX1(k):原序列偶数项的DFTX2(k):原序列奇543.结论1再应用W系数的周期性，求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：3.结论1再应用W系数的周期性，求出用X1(k),X2(k554.求出后半部的表示式看出：后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。4.求出后半部的表示式看出：后半部的k值所对应的X1(k),565.结论2频域中的N个点频率成分为：只要求出（0~N/2-1）区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0~N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。结论：5.结论2频域中的N个点频率成分为：只要求出（0~N/2-1576.结论3由于N=2M，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。6.结论3由于N=2M，因此N/2仍为偶数，可以依照上面方法58（三）蝶形结即蝶式计算结构,或蝶式信号流图。X1(k)X2(k)作图要素：(1)左入右出(2)上加下减(3)系数标箭头上面频域中前/后半部分表示式可以用蝶形信号流图表示如下。（三）蝶形结即蝶式计算结构,或蝶式信号流图。X1(k)X2(59例子先将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：例子先将N=8DFT分解成2个4点DFT：求N=23=8点60将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)将N=8点分解成2个4点的DFT的信号流图4点x(0)4点61(2)N/2(4点)-->N/4(2点)FFT因为4点DFT还是比较麻烦，所以再继续分解。若将N/2(4点)子序列按奇/偶分解成两个N/4点（2点）子序列。即将x1(r)和x2(r)分解成奇、偶两个N/4点（2点）点的子序列。(2)N/2(4点)-->N/4(2点)FFT62一个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)一个2点的DFT蝶形流图2点DFT2点DFTx(0)x(2)63另一个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)另一个2点的DFT蝶形流图2点DFT2点DFTx(1)x(364(3)将N/4（2点）DFT再分解成2个1点的DFT最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。(3)将N/4（2点）DFT再分解成2个1点的DFT652个1点的DFT蝶形流图1点DFTx(0)1点DFTx(4)X3(0)X3(1)进一步简化为蝶形流图：X3(0)X3(1)x(0)x(4)2个1点的DFT蝶形流图1点DFTx(0)1点DFTx(466(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=