9快速付里叶变换FFT-DIT(4).ppt

《9快速付里叶变换FFT-DIT(4).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、快速傅立叶变换(FFT)FastFourierTransforming快速傅立叶变换FFT0引言1直接计算DFT存在的问题及改进途径2基--2按时间抽取的FFT算法3基--2按频率抽取的FFT算法4离散反傅立叶变换的快速计算方法5线性卷积的FFT算法0引言0.1快速付里叶变换FFTDFT计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT).特别说明：FFT并不是一种新的变换形式,它只是DFT的一种快速算法.并且根据对序列分解与选取方法的不同而产生了FFT的多种算法.FFT在离散傅里叶反变换、线性卷积和线性

2、相关等方面也有重要应用。0.2主要内容直接计算DFT算法存在的问题及改进途径。多种FFT算法(时间抽取算法DIT算法，频率抽取算法DIF算法，线性调频Z变换即CZT法)FFT的应用1直接计算DFT存在的问题及改进途径1.1直接计算DFT计算量1.2改善DFT运算效率的基本途径1.1直接计算DFT计算量问题提出：设有限长序列x(n),非零值长度为N，计算对x(n)进行一次DFT运算，共需多大的运算工作量?比较DFT与IDFT之间的运算量其中均为复数所以DFT与IDFT二者计算量相同。计算DFT复数运算量计算一个X(k)值的运

3、算量：例k=1则要进行N次复数乘法和(N-1)次复数加法要完成整个DFT运算，其计算量为：N*N次复数相乘和N*(N-1)次复数加法复数乘法换算成实数运算量一个复数乘法包括4个实数乘法和2个实数加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)4次实数乘法2次实数加法计算DFT需要的实数运算量每运算一个X(k)的值，需要进行4N次实数相乘和2N+2(N-1)=2(2N-1)次实数相加.整个DFT运算量为：4N2次实数相乘和2N(2N-1)次实数相加.直接计算DFT时，乘法次数与加法次数都和N2成比例。1.W具

4、有周期性2.W具有对称性N点DFT运算可以分解为两组N/2点DFT运算，然后再取和。经过周期性与对称性简化之后,容易发现DFT运算中存在着不必要的重复计算,避免这种重复,是简化运算的关键.DFT的复杂度与点数N有关！算法基础：W的两个性质。1.2改善DFT运算效率的基本途径1.2改善DFT运算效率的基本途径两个途径：1.合并法：合并DFT运算中的某些项。2.分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。的对称性和周期性对称性：周期性：合并法合并DFT运算中的有些项对虚实部而言步骤1：分解成虚实部步骤2：代入

5、DFT中展开：步骤3：合并有些项根据：有：步骤4：结论由此找出其它各项的类似归并方法：乘法次数可以减少一半。例：将长序列DFT利用对称性和周期性分解为短序列DFTDFT的运算量与N2成正比如果大点数N的DFT能分解为若干小点数DFT的组合，则可减少运算工作量。思路方法把N点数据分成二半：运算量：再分二半：+=+++=一直分下去，剩下两点的变换。运算量：运算量：分二半：结论按抽取方法分：时间抽取法(DIT);频率抽取法(DIF)按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：线性

6、调频Z变换(CZT法)2基--2按时间抽取的FFT算法Decimation-in-Time(DIT)(Coolkey-Tukey)2.1算法原理2.2算法步骤2.3蝶形运算2.4FFT算法中的一些概念2.5DITFFT算法与直接计算DFT运算量的比较2.6DITFFT算法的特点2.1算法原理按时间抽取----将该序列按时间顺序的奇偶分解为越来越短的子序列。基数2----N=2M，M为正整数。若不满足这个条件，可以加零补长。分解原则对时间进行奇偶分解对频率进行前后分解2.2算法步骤将x(n)按n的奇偶分为两组，作变量置换

7、:当n=偶数时，令n=2r;当n=奇数时，令n=2r+1;得到：x(2r)=x1(r)；x(2r+1)=x2(r)，r=0…N/2-1步骤1.分组，变量置换将N点数据X(k)分为前后两半:X(k)=X(k)＋X(k+N/2)，k=0,1,…N/2-1考虑前半部分：步骤2.代入DFT中步骤3.求出子序列的DFT由于所以其中步骤4.求出后半部的表示式看出：后半部的k值所对应的X1(k)和X2(k)完全重复了前半部分的k值所对应的X1(k),X2(k)的值。后半部分结论频域中的N个点频率成分为：结论：只要求出（0~N/2-1）区

8、间内的各个整数k值所对应的X1(k)和X2(k)值，即可以求出(0~N-1)整个区间内全部X(k)值结论由于N=2M，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT。两点DFT实际上只是加减运