离散傅里叶变换及其快速算法(I)

《离散傅里叶变换及其快速算法(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.3快速傅里叶变换(FFT)一、直接计算DFT的问题及改进的途径二、按时间抽取的基2FFT算法三、按频率抽取的基2FFT算法四、离散傅立叶反变换的快速算法五、N为组合数的FFT算法六、Chirp——z变换一、直接计算DFT的问题及改进的途径1.直接计算DFT的问题长度为N的有限长序列x(n)的DFT为考虑x(n)为复数序列的一般情况，对某一个k值，直接按(1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。(1)X（k）一共有N个点，故完成全部DFT运算，需要N2次复数相乘和N（N-1）次复数相加，在这些运算中，乘法比加法复杂，需要的运算时间多，尤其是复数相乘，每个复

2、数相乘包括4个实数相乘和2个实数相加，例又每个复数相加包括2个实数相加，所以，每计算一个X（k）要进行4N次实数相乘和2N+2（N-1）=2（2N-1）次实数相加，因此，整个DFT运算需要4N2实数相乘和2N（2N-1）次实数相加。从上面的分析看到，在DFT计算中，不论是乘法和加法，运算量均与N2成正比。因此，N较大时，运算量十分可观。例，计算N=10点的DFT，需要100次复数相乘，而N=1024点时，需要1048576（一百多万）次复数乘法，如果要求实时处理，则要求有很高的计算速度才能完成上述计算量。反变换IDFT与DFT的运算结构相同，只是多乘一个常数1/N，所以二者的计

3、算量相同。DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。2.减少运算量的基本途径显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子具有明显的周期性和对称性。其周期性表现为其对称性表现为或者二、按时间抽取的基2FFT算法按n的奇偶把x(n)分解为两个N/2点的子序列。偶数项为一组，奇数项为一组。FFT算法基本上分为

4、两大类时域抽取法FFT(DecimationInTimeFFT,简称DIT-FFT)频域抽取法FFT(DecimationInFrequencyFFT,简称DIF―FFT)。为自然数1.DIF―FFT算法。设序列x(n)的长度为N，且满足则x(n)的DFT为所以由于于是，一个N点的DFT被分解为两个N/2点的DFT了，这两个N/2点的DFT再按照上式合并成一个N点DFT。（1）,只有N/2个点，而却有N个点，要用,表达全部值，还必须利用系数的周期特性。即，同样又考虑到的对称性：将上述三个式子代入式(1),就可将表达为前后两部分：(2)蝶形运算流图符号(3)式（2）、（3）可以用

5、上图的“蝶形结”来表示。通过上述分解后，每个N/2点DFT只需要(N/2)2=N2/4次复数相乘。依此类推，X1(k)和X2(k)可以继续分下去，这种按时间抽取算法是在输入序列分成越来越小的子序列上执行DFT运算，最后再合成为Ｎ点的DFT。蝶形信号流图将X1(k)和X2(k)合成X(k)运算可归结为：Wa+bWa-bW-W-1a+bWa-bWWabab蝶形运算的简化(a)(b)图(a)为实现这一运算的一般方法，它需要两次乘法、两次加减法。考虑到-bW和bW两个乘法仅相差一负号，可将图(a)简化成图(b)，此时仅需一次乘法、两次加减法。图(b)的运算结构像一蝴蝶通常称作蝶形运算结

6、构简称蝶形结，采用这种表示法，就可以将以上所讨论的分解过程用流图表示。两个N/2点的DFT需要2(N/2)2=N2/2次复乘，再加上将两个N/2点的DFT合成为N点DFT时蝶形结前的N/2次复乘，一共需要次复乘。可见，分解后运算量大约节省了一倍。既然这样的分解是有效的，由于N/2仍然是偶数，因此可以对两个N/2点的DFT再分别作进一步分解。如右图所示：N/4点DFTN/4点DFTN=23=8的例子。N/2点DFTG(0)G(1)G(2)G(3)X(0)X(1)X(2)X(3)x(0)x(2)x(4)x(6)N/2点DFTH(0)H(1)H(2)H(3)X(4)X(5)X(6)X

7、(7)x(1)x(3)x(5)x(7)WN1WN2WN3-1-1-1-1两个4点DFT组成8点DFT与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即那么，X1(k)又可表示为式中同理，由X3(k)和X4(k)的周期性和WmN/2的对称性Wk+N/4N/2=-WkN/2最后得到：用同样的方法可计算出其中N/4点N/4点N/4点N/4点由四个2点DFT组成8点DFT最后剩下的是2点DFT，它可以用一个蝶形结表示：这样，一个8点的完整的按时间抽取运算的流图由