ch4 快速傅里叶变换(FFT)ppt课件.ppt

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

1、第4章快速傅里叶变换（FFT）主要内容4.1引言4.2基2FFT算法4.3进一步减少运算量的措施1一、DFT的运算量估计4.1引言两者的差别仅在指数的符号和因子1/N。2一个X(k)的值的工作量，如X(1)：则计算完全部的X(k)，k=0,1,2,…,N-1，需要共需N次复数乘法N-1次复数加法N×N=N2次复数乘法N×(N-1)N2次复数加法需将每一个x(n)乘以相应的，再加起来。3如果换算成实数运算：一次复乘：(a+jb)(c+jd)=(ac-bd)+j(ad+bc)需4次实乘，2次实加一次复加：(a+jb

2、)+(c+jd)=(a+c)+j(b+d)需2次实加所以，直接计算全部X(k)共需4N2次实乘2N2+2N2=4N2次实加4[例]N=210=1024，总共需实时信号处理对计算速度有十分苛刻的要求。如何能减少DFT运算量？？400万次乘法400万次加法52.对称性：的特征如下：1.周期性：3.可约性：4.正交性：二、提高DFT运算效率的途径65.特殊的:如果充分利用复函数的这些特征，就可以改善DFT的运算效率。为了能利用上述特性，需将x(n)或X(k)这些长序列按一定的规律分解成一些短序列，即重排，以减少运算次数

3、。二、提高DFT运算效率的途径的特征如下：71965年，库利(cooley)和图基(Tukey)首先提出FFT算法。对于N点DFT，仅需(N/2)log2N次复数乘法运算。[例]N=210=1024时：需要的复乘次数(1024/2)log2210=512×10=5120次，直接计算需要的复乘次数为1048576次，5120/1048576=4.88‰,所以利用FFT算法，速度提高200多倍。8一、基(Radix)基2FFT算法的思想就是将长序列划为短序列，短到什么程度？用“基（Radix）”来表示，即基是FFT中

4、用到的最小DFT单元。Radix-2（基2），代表2点DFT。2点DFT实际上只是加减运算。4.2基２FFT算法92点DFT即：10画出流图：2点DFT11二、DIT-FFT算法原理基2FFT算法分为两类：(1)时域抽取法FFT（DIT-FFT,Decimation-In-TimeFFT)，它是库利-图基算法；(2)频域抽取法FFT（DIF-FFT,Decimation-In-FrequencyFFT)。设序列x(n)的长度为：N=2M（0,1,2,……)，按n的奇偶把x(n)分解为两个N/2的子序列。(一）N/

5、2点DFT12n为偶数时：n为奇数时：1.N/2点分解13(n为偶数)(n为奇数)14(1)X1(k)，X2(k)均为N/2点的DFT。(2)只能确定出X(k)的　　　　　　的值，即前一半的结果。其中2.结论15同理，3.X(k)后一半的确定由于（周期性），所以：X1(k)、X2(k)后一半的值，分别等于其前一半的值。16可见，X(k)的后一半，也完全由X1(k)、X2(k)的前一半所确定。又由于，所以：前一半后一半17只要求出0～N/2-1区间内的各个k值所对应的X1(k)、X2(k)的值，即可以求出0～N-1

6、整个区间内的全部X(k)值。这就是FFT能大量节省运算量的关键。N点的DFT可由两个N/2点的DFT来计算。前一半后一半184.蝶形运算碟形运算符号19实现上式运算，共需N/2个蝶形运算。前一半后一半由X1(k)、X2(k)表示X(k)的运算是一种碟形运算：20(1)N/2点的DFT运算量:复乘次数　　　　　，复加次数(2)两个N/2点的DFT运算量:复乘次数　　，复加次数(3)N/2个蝶形运算的运算量:复乘次数　　，复加次数5.运算量分析按奇、偶分组后的计算量：21复乘:复加:但是，N点DFT的复乘为N2，复加

7、N(N-1)；与分解后相比，计算工作量差不多减少一半。5.运算量分析一个N点DFT分解成两个N/2点DFT后的总共运算量：22例：N=8时的DFT，可以分解为两个N/2=4点的DFT。具体方法如下：(1)n为偶数时,即分别记作:进行N/2=4点的DFT，得：23(2)n为奇数时，分别记作：进行N/2=4点的DFT，得：24x1(0)=x(0)x1(1)=x(2)N/2点x1(2)=x(4)DFTx1(3)=x(6)x2(0)=x(1)x2(1)=x(3)N/2点x2(2)=x(5)DFTx2(3)=x(7)X1(

8、0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN2WN1WN0WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)(3)对X1(k)和X2(k)进行蝶形运算,前半部分为X(0)～X(3),后半部分为X(4)～X(7)。25由于N=2M,所以N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。