快速傅里叶变换FF

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

1、本章主要内容引言基2FFT算法进一步减少运算量的措施第4章快速傅里叶变换(FFT)DFT是信号分析与处理中的一种重要变换。但直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。1965年发现了DFT的一种快速算法，使DFT的运算效率提高1－2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了条件，推动了数字处理技术的发展。1984年，提出了分裂基快速算法，使运算效率进一步提高；4.1引言4.2.1直接计算DFT的特点及减少运算量的基本途径直接计算DFT长度为N的有限长序列x(n)

2、的DFT为：2、减少运算量的思路和方法思路：N点DFT的复乘次数等于N2。把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有周期性和对称性。4.2基2FFT算法考虑x(n)为复数序列的一般情况，对某一个k值，直接按上式计算X(k)值需要N次复数乘法、(N-1)次复数加法。方法：分解N为较小值：把序列分解为几个较短的序列，分别计算其DFT值，可使乘法次数大大减少；利用旋转因子WNk的周期性、对称性进行合并、归类处理，以减少DFT的运算次数。周期性：对称性：3、FFT算法思想不断地把长序列的DFT分解成几个短序列的DFT，并利用旋转因子的

3、周期性和对称性来减少DFT的运算次数。4.2基2FFT算法4.2.2时域抽取法基2FFT基本原理FFT算法基本上分为两大类：时域抽取法FFT(简称DIT-FFT)和频域抽取法FFT(简称DIF―FFT)。1、时域抽取法FFT的算法思想：将序列x(n)按n为奇、偶数分为x1(n)、x2(n)两组序列；用2个N/2点DFT来完成一个N点DFT的计算。设序列x(n)的长度为N，且满足：(1)按n的奇偶把x(n)分解为两个N/2点的子序列4.2基2FFT算法为自然数｛(2)用N/2点X1(k)和X2(k)表示序列x(n)的N点DFTX(k)4.2基2FFT算法偶数奇数注意：

4、这里的k的取值范围为0，1，…，N-1由于X1(k)和X2(k)均以N/2为周期，且,X(k)又可表示为:对上式的运算用下图所示的流图符号来表示4.2基2FFT算法这样将N点DFT分解为两个N/2点的DFTX1(k)X2(k)X1(k)+WNkX2(k)X1(k)WNkX2(k)WNk图：蝶形运算符号完成一个蝶形运算需要一次复数乘和两次复数加法运算，经过一次分解后，共需要复数乘和复数加的次数为2(N/2)2+N/2和N2/2｛4.2基2FFT算法N/2点DFTN/2点DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1

5、(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)｛N=8点的DIT-2FFT(时域抽取图)一次分解图(3)第二次分解：将x1(r)按r取奇、偶可分解成2个长度为N/4的子序列x3(l)=x1(2l)、x4(l)=x1(2l+1)，根据上面推导可得：X1(k)=X3(k)+WN/2kX4(k)，k=0,1,…,N/2-1将x2(r)按r取奇、偶可分解成2个长N/4的子序列x5(l)=x2(2l)，l=0,1,…，N/4x6(l)=x2(2l+1)；同理得4.2基2FFT算

6、法l=0,1,…，N/4-1；X1(k+N/2)=X3(k)WN/2kX4(k)，k=0,1,…,N/4-1；X1(k)=X3(k)+WN/2kX4(k)，k=0,1,…,N/4-1；X2(k)=X5(k)+WN/2kX6(k)，k=0,1,…,N/4-1；X2(k+N/2)=X5(k)WN/2kX6(k),k=0,1,…,N/4-1；4.2基2FFT算法N/4点DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(

7、2)X(3)X(4)X(5)X(6)X(7)N/4点DFTN/4点DFTN/4点DFTX3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)WN/20WN/21WN/21WN/20N=8点DFT的二次时域抽取分解图X1(k+N/2)=X3(k)WN/2kX4(k)X1(k)=X3(k)+WN/2kX4(k)X2(k)=X5(k)+WN/2kX6(k)X2(k+N/2)=X5(k)WN/2kX6(k)k=0,1,…,N/4-1；再次分解，对N=8点，可分解三次。4.2基2FFT算法X(5)N=8点DIT-FFT运算流图x(0)