数字信号处理第4章快速傅里叶变换FF

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

1、第4章快速傅里叶变换(FFT)4.1引言4.2基2FFT算法4.3进一步减少运算量的措施4.4分裂基FFT算法4.5离散哈特莱变换(DHT)1课件4.1引言DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。2课件4.2基2FFT算法4.2.1直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列x(

2、n)的DFT为考虑x(n)为复数序列的一般情况，对某一个k值，直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。(4.2.1)3课件如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对称性。其周期性表现为(4.2.2)其对称性表现为或者4课件4.2.2时域抽取法基2FFT基本原理FFT算法基本上分为两大类：时域抽取法FFT(DecimationInTimeFFT,简称DIT-FFT)和频域抽取法FFT(DecimationI

3、nFrequencyFFT,简称DIF―FFT)。下面先介绍DIF―FFT算法。设序列x(n)的长度为N，且满足为自然数按n的奇偶把x(n)分解为两个N/2点的子序列5课件则x(n)的DFT为由于所以6课件其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即(4.2.5)(4.2.6)由于X1(k)和X2(k)均以N/2为周期，且所以X(k)又可表示为前后对半分开两部分(4.2.7)(4.2.8)7课件图4.2.1蝶形运算符号8课件图4.2.2N点DFT的一次时域抽取分解图(N=8)9课件二次分解：与第一次分解相同，将

4、x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即那么，X1(k)又可表示为(4.2.9)10课件式中同理，由X3(k)和X4(k)的周期性和WmN/2的对称性Wk+N/4N/2=-WkN/2最后得到：(4.2.10)11课件用同样的方法可计算出(4.2.11)其中12课件图4.2.3N点DFT的第二次时域抽取分解图(N=8)13课件图4.2.4N点DIT―FFT运算流图(N=8)14课件4.2.3DIT―FFT算法与直接计算DFT运算量的比较每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M

5、级运算总共需要的复数乘次数为复数加次数为例如，N=210=1024时15课件图4.2.5FFT算法与直接计算DFT所需乘法次数的比较曲线16课件4.2.5频域抽取法FFT(DIF―FFT)在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIF―FFT。设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：17课件偶数奇数X(k)分解成偶数组与奇数组，当k取偶数k=2r,r=0,1,…,N/2-1时(4.2.14)18课件当k取奇数(k=2r+1,r=0,1,…,N/2-1)时(4.

6、2.15)将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得(4.2.16)19课件图4.2.10DIF―FFT蝶形运算流图符号20课件图4.2.11DIF―FFT一次分解运算流图(N=8)21课件图4.2.12DIF―FFT二次分解运算流图(N=8)22课件图4.2.13DIF―FFT运算流图(N=8)23课件图4.2.14DIT―FFT的一种变形运算流图24课件图4.2.15DIT―FFT的一种变形运算流图25课件4.2.6IDFT的高效算法上述FFT算法流图也可以用于离散傅里叶逆变换(InverseDiscre

7、teFourierTransform，简称IDFT)。比较DFT和IDFT的运算公式：26课件如果希望直接调用FFT子程序计算IFFT，则可用下面的方法：由于对上式两边同时取共轭，得27课件4.3进一步减少运算量的措施4.3.1多类蝶形单元运算由DIT―FFT运算流图已得出结论，N=2M点FFT共需要MN/2次复数乘法。由(4.2.12)式，当L=1时，只有一种旋转因子W0N=1，所以，第一级不需要乘法运算。28课件综上所述，先除去第一、二两级后，所需复数乘法次数应是从L=3至L=M共减少复数乘法次数为(4.3.1)(4.3.2)因此，DI

8、T―FFT的复乘次数降至(4.3.3)29课件30课件从实数运算考虑，计算N=2M点DIT―FFT所需实数乘法次数为(4.3.4)31课件4.3.2旋转因子的生成在FFT运算中，