按时间抽取的基2FFT算法分析

第四章 快速傅里叶变换

有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基２DIT和基２DIF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。

快速傅里叶变换（FFT）是计算离散傅里叶变换（DFT）的快速算法。 DFT的定义式为

knX(k)=?x(n)WNRN(k)

n?0N?1kn在所有复指数值WN的值全部已算好的情况下，要计算一个X(k)需要N

次复数乘法和N－1次复数加法。算出全部N点X(k)共需N次复数乘法和N(N?1)次复数加法。即计算量是与N成正比的。

FFT的基本思想：将大点数的DFT分解为若干个小点数DFT的组合，从而减少运算量。

可使DFT运算量尽量分解为小点数的DFTWN因子具有以下两个特性，运算：

（1） 周期性：WN(k?N)nkn(n?N)k ?WN?WNk ??WN22（2） 对称性：WN

(k?N/2)57

利用这两个性质，可以使DFT运算中有些项合并，以减少乘法次数。例子：求当N＝4时，X(2)的值

X(2)??x(n)W42n?x(0)W40?x(1)W42?x(2)W44?x(3)W46n?03

?[x(0)?x(2)]W40?[x(1)?x(3)]W42＝[x(0)?x(2)]－[x(1)?x(3)]W40(周期性)

(对称性)通过合并，使乘法次数由4次减少到1次，运算量减少。

FFT的算法形式有很多种，但基本上可以分为两大类：按时间抽取（DIT）和按频率抽取（DIF）。

4.1 按时间抽取（DIT）的FTT

为了将大点数的DFT分解为小点数的DFT运算，要求序列的长度N为复合数，最常用的是N?2的情况（M为正整数）。该情况下的变换称为基2FFT。下面讨论基2情况的算法。 先将序列x(n)按奇偶项分解为两组 ?M?x(2r)?x1(r)N r?0,1,?,?1

2?x(2r?1)?x2(r)

将DFT运算也相应分为两组

knX(k)?DFT[x(n)]??x(n)WN

n?0N?1 ?n?0n为偶数N/2?1?x(n)WN?1knN＋n?0n 为奇数N/2?1?x(n)WN?1knN

＝?x(2r)Wr?02rkN??x(2r?1)Wr?0(2r?1)kN

58

＝?x1(r)Wr?0N/2?12rkN?WkNN/2?1r?0?x2rk (r)W2N＝?x1(r)Wr?0N/2?1rkN/2?WkNN/2?1r?0?x2rk2rkrk（因为WN (r)WN?WN/2 /2）

k?X1(k)?WNX2(k)

其中X1(k)、X2(k)分别是x1(n)、x2(n)的N/2点的DFT

X1(k)＝?x1(r)Wr?0N/2?1r?0N/2?1rkN/2N/2?1??x(2r)WNrk/2,0?k?r?0N/2?1N?1 2N?1 2X2(k)＝?x2(r)WrkN/2??x(2r?1)Wr?0rkN/2,0?k?至此，一个N点DFT被分解为两个N/2点的DFT。 上面是否将全部N点的X(k)求解出来了？

分析：X1(k)和X2(k)只有N/2个点（k?0,1,?,N?1），则由2kX(k)?X1(k)?WNX2(k)只能求出X(k)的前N/2个点的DFT，要求出

全部N点的X(k)，需要找出X1(k)、X2(k)和X(k?N/2)的关系，其中k?0,1,?,Nk?1。由式子X(k)?X1(k)?WNX2(k)可得 2k?N/2X(k?N/2)?X1(k?N/2)?WNX2(k?N/2)化简得 kX(k?N/2)＝?X1(k)?WNX2(k)，k?0,1,?,N?1 2这样N点DFT可全部由下式确定出来：

k?N?X(k)?X1(k)?WNX2(k)k?0,1,?,?1 （＊） ?k2??X(k?N/2)?X1(k)?WNX2(k)上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运

59

算。

aka?WNbbkWN-1ka?WNb

图 蝶形运算符号

N2N2通过这样的分解以后，每一个N／2点的DFT只需要()?次复数乘

24N2N2法，两个N/2点的DFT需要2()?次复乘，再加上将两个N／2点

22DFT合并成为N点DFT时有N／2次与W因子相乘，一共需要

N2NN2??次复乘。可见，通过这样的分解，运算量节省了近一半。 222因为N?2，N/2仍然是偶数，因此可以对两个N/2点的DFT再分别作进一步的分解，将两个N/2点的DFT分解成两个N/4点的DFT。

例如对x1(r)，可以在按其偶数部分及奇数部分进行分解：

M?x1(2l)?x3(l)N ? l?0,1,?,?1

4?x1(2l?1)?x4(l)则的运算可相应分为两组：

X1(k)＝?x1(2l)Wl?0N/4?12lkN/2N/4?1??x(2l?1)W1l?0N/4?1l?0(2l?1)kN/2

＝?x3(l)Wl?0N/4?1lkN/4?WkN/2?x4lk(l)WN/4

k?X3(k)?WN/2X4(k) k?0,1,?,N?1 4 60

k2k将系数统一为以Ｎ为周期，即WN/2?WN，可得

2k?N?X1(k)?X3(k)?WNX4(k)k?0,1,?,?1 ?2k4??X1(k?N/4)?X3(k)?WNX4(k)同样，对X2(k)也可进行类似的分解。一直分解下去，最后是２点的DFT，２点DFT的运算也可用碟形符号来表示。这样，对于一个N?2?8的DFT运算，其按时间抽取的分解过程及完整流图如下图所示。

3

61

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库按时间抽取的基2FFT算法分析在线全文阅读。