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

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

1、第二章离散傅里叶变换及其快速算法§2.3快速傅里叶变换（FFT）快速傅里叶变换（FFT）是计算DFT的一种快速有效方法。从前面的讨论中看到，有限长序列在数字技术中占有很重要的地位。有限长序列的一个重要特点是其频域也可以离散化，即离散傅里叶变换（DFT）。虽然频谱分析和DFT运算很重要，但在很长一段时间里，由于DFT运算复杂，并没有得到真正的运用，而频谱分析仍大多采用模拟信号滤波的方法解决，直到1965年首次提出DFT运算的一种快速算法以后，情况才发生了根本变化，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善

2、了一套高速有效的运算方法——快速付里变换（FFT）算法。FFT的出现，使DFT的运算大大简化，运算时间缩短一～二个数量级，使DFT的运算在实际中得到广泛应用。1、DFT运算的特点：一般，x(n)和wnkN都是复数，因此，每计算一个X(k)值，要进行N次复数相乘，和N-1次复数相加，X(k)一共有N个点，故完成全部DFT运算，需要N2次复数相乘和N（N-1）次复数相加，在这些运算中，乘法比加法复杂，需要的运算时间多，尤其是复数相乘，每个复数相乘包括4个实数相乘和2个实数相加，例首先分析有限长序列x(n)进行一次DFT运算所

3、需的运算量。又每个复数相加包括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的运算结构相同，只是多

4、乘一个常数1/N，所以二者的计算量相同。FFT算法的基本思想：考察DFT与IDFT的运算发现，利用以下两个特性可减少运算量：1）系数是一个周期函数，它的周期性和对称性可用来改进运算，提高计算效率。例利用这些周期性和对称性，使DFT运算中有些项可合并；2）利用的周期性和对称性，把长度为N点的大点数的DFT运算依次分解为若干个小点数的DFT。因为DFT的计算量正比于N2，N小，计算量也就小。FFT算法正是基于这样的基本思想发展起来的。它有多种形式，但基本上可分为两类：时间抽取法和频率抽取法。又如因此2、按时间抽取的FFT（N

5、点DFT运算的分解）先从一个特殊情况开始，假定N是2的整数次方，N=2M，M：正整数首先将序列x（n）分解为两组，一组为偶数项，一组为奇数项，将DFT运算也相应分为两组：因为故其中注意到，H（k），G（k）有N/2个点，即k=0，1，…，N/2-1，还必须应用系数wkN的周期性和对称性表示X（k）的N/2～N-1点：由得：可见，一个N点的DFT被分解为两个N/2点的DFT，这两个N/2点的DFT再合成为一个N点DFT.依此类推，G(k)和H(k)可以继续分下去，这种按时间抽取算法是在输入序列分成越来越小的子序列上执行DF

6、T运算，最后再合成为Ｎ点的DFT。蝶形信号流图将G(k)和H(k)合成X(k)运算可归结为：Wa+bWa-bW-W-1a+bWa-bWWabab蝶形运算的简化(a)(b)图(a)为实现这一运算的一般方法，它需要两次乘法、两次加减法。考虑到-bW和bW两个乘法仅相差一负号，可将图(a)简化成图2.7(b)，此时仅需一次乘法、两次加减法。图(b)的运算结构像一蝴蝶通常称作蝶形运算结构简称蝶形结，采用这种表示法，就可以将以上所讨论的分解过程用流图表示。N=23=8的例子。N/2点DFTG(0)G(1)G(2)G(3)X(0)X

7、(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)x(1)x(3)x(5)x(7)WN1WN2WN3-1-1-1-1两个4点DFT组成8点DFT按照这个办法，继续把N/2用２除，由于N=2M，仍然是偶数，可以被２整除，因此可以对两个N/2点的DFT再分别作进一步的分解。即对{G(k)}和{H(k)}的计算，又可以分别通过计算两个长度为N/4=2点的DFT，进一步节省计算量，见图。这样，一个８点的DFT就可以分解为四个２点的DFT。N/4点N

8、/4点N/4点N/4点由四个2点DFT组成8点DFT最后剩下的是2点DFT，它可以用一个蝶形结表示：这样，一个8点的完整的按时间抽取运算的流图由于这种方法每一步分解都是按输入时间序列是属于偶数还是奇数来抽取的，所以称为“按时间抽取法”或“时间抽取法”。按时间抽取的8点FFT时间抽取法FFT的运算特点：（1）蝶形运算（