《數(shù)字信號(hào)處理》課件1第4章

第4章快速傅里葉變換(FFT)4.1直接計(jì)算DFT的運(yùn)算量及改進(jìn)途徑

4.2時(shí)間抽取法(DIT)基-2FFT算法

4.3頻域抽取法(DIF)基-2FFT算法

4.4快速傅里葉逆變換(IFFT)算法

4.5

FFT算法的工程實(shí)現(xiàn)考慮

習(xí)題

4.1直接計(jì)算DFT的運(yùn)算量及改進(jìn)途徑

4.1.1直接計(jì)算DFT的運(yùn)算量

設(shè)x(n)是長度為N的有限長序列，其N點(diǎn)DFT為

離散傅里葉逆變換(IDFT)為(4.1.2)(4.1.1)上述兩式的差別只在于WN上指數(shù)符號(hào)的不同，以及一個(gè)常數(shù)因子，因此，DFT和IDFT運(yùn)算量基本上是相同的，為

簡便，下面只討論DFT的運(yùn)算量。

由于實(shí)數(shù)序列是復(fù)數(shù)序列的特例，為分析簡便，這里統(tǒng)一考慮x(n)為復(fù)數(shù)序列的情況，而通常也是復(fù)數(shù)，因此，這里以復(fù)數(shù)乘法和復(fù)數(shù)加法的次數(shù)作為運(yùn)算量衡量指標(biāo)。顯然，計(jì)算一個(gè)X(k)值需要N次復(fù)數(shù)乘法，N－1次復(fù)數(shù)加法。而X(k)總共有N個(gè)值，計(jì)算所有X(k)值的運(yùn)算量為復(fù)數(shù)乘法N2次，復(fù)數(shù)加法N(N－1)次。對(duì)于復(fù)數(shù)乘法和加法，實(shí)際上是轉(zhuǎn)化為實(shí)數(shù)進(jìn)行運(yùn)算的，式(4.1.1)可以寫成(4.1.3)可見，1次復(fù)數(shù)乘法相當(dāng)于4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法，1次復(fù)數(shù)加法相當(dāng)于2次實(shí)數(shù)加法。因此，計(jì)算一個(gè)X(k)需要4N次實(shí)數(shù)乘法和2N+2(N－1)=4N－2次復(fù)數(shù)加法，整個(gè)DFT運(yùn)算需要4N2次實(shí)數(shù)乘法和N(4N－2)次實(shí)數(shù)加法。

當(dāng)N

1時(shí)，N(N－1)≈N2，N(4N－2)≈4N2，因此，不管以復(fù)數(shù)還是實(shí)數(shù)進(jìn)行統(tǒng)計(jì)，直接計(jì)算N點(diǎn)DFT的乘法或加法次數(shù)都與N2成正比，隨著N的增加，運(yùn)算量增加越來越快，特別是N很大時(shí)，運(yùn)算量將非?？捎^。例如，N=8時(shí)，次數(shù)為N2=64；N=1024時(shí)，次數(shù)為N2=1048576，超過100萬次。對(duì)于各種實(shí)時(shí)性很強(qiáng)的信號(hào)處理應(yīng)用來說，要求計(jì)算速度特別快，因此必須改進(jìn)DFT的計(jì)算方法，減少運(yùn)算量。＞＞4.1.2減少運(yùn)算量的途徑

由于N點(diǎn)DFT的運(yùn)算量隨N2快速增長，當(dāng)N增加1倍時(shí)，N2增加到4倍。如果能夠?qū)點(diǎn)DFT分解為幾個(gè)較短的DFT，運(yùn)算量將會(huì)大大減少。例如，分解為2個(gè)N/2點(diǎn)DFT，復(fù)數(shù)乘法次數(shù)為 ，運(yùn)算量減少1倍；若分解為4個(gè)點(diǎn)DFT，復(fù)數(shù)乘法次數(shù)為 ，運(yùn)算量將減少為原來的?？梢哉f，正是DFT分解思想形成了快速計(jì)算DFT的基本途徑。以N點(diǎn)DFT分解為2個(gè)N/2點(diǎn)DFT為例，假定N點(diǎn)序列x(n)，n=0，1，2，…，N－1，N為偶數(shù)，那么將x(n)分解為2個(gè)N/2點(diǎn)序列的方法歸納起來有兩個(gè)：奇偶分解和前后分解。

(1)奇偶分解：x(n)分解為偶序列和奇序列，分別表示為

偶序列：x(2r)，r=0，1，2，…，－1

奇序列：x(2r+1)，r=0，1，2，…，－1

(2)前后分解：x(n)前后對(duì)半分解為兩部分，分別為

前半部分：x(r)，r=0，1，2，…，－1

后半部分： ，r=0，1，2，…，－1快速傅里葉變換(FFT)通過不斷地將長序列的DFT分解為短序列的DFT，并利用的特性，來達(dá)到減少DFT運(yùn)算量的目的。為了便于對(duì)N點(diǎn)DFT進(jìn)行分解，通常N取為2的冪級(jí)數(shù)形式，即N=2M，M為整數(shù)。此時(shí)的快速傅里葉變換稱為基-2FFT算法。若序列長度不滿足條件N=2M，可以對(duì)序列補(bǔ)0，使之達(dá)到這一條件。

FFT算法推導(dǎo)過程中，主要利用的對(duì)稱性和周期性，在序列分解后，對(duì)DFT計(jì)算式(4.1.1)中的某些項(xiàng)進(jìn)行合并，從而減小乘法和加法的次數(shù)。稱為旋轉(zhuǎn)因子，其對(duì)稱性和周期性表現(xiàn)為

對(duì)稱性：

周期性：(4.1.4)(4.1.5)(4.1.6)此外，的特性還有

下面兩節(jié)中將學(xué)習(xí)兩類基-2FFT算法，分別由上述兩種分解方式推導(dǎo)得到，其中，奇偶分解對(duì)應(yīng)于時(shí)間抽取法FFT(Decimation-In-TimeFFT)，簡稱DIT-FFT，前后分解對(duì)應(yīng)于頻率抽取法FFT(Decimation-In-FrequencyFFT)，簡稱DIF-FFT。(4.1.7)

4.2時(shí)間抽取法(DIT)基-2FFT算法

4.2.1

DIT-FFT算法原理

設(shè)序列x(n)長度N=2M，N點(diǎn)DIT-FFT算法對(duì)應(yīng)序列奇偶分解，令x1(r)、x2(r)分別表示偶序列和奇序列，則有

(4.2.2)(4.2.1)根據(jù)DFT的定義式(4.1.1)，有(4.2.3)由于

所以(4.2.4)觀察上式：右邊前一項(xiàng)是序列x1(r)的N/2點(diǎn)DFT，后一項(xiàng)求和部分是序列x2(r)的N/2點(diǎn)DFT，即

對(duì)于N/2點(diǎn)DFTX1(k)和X2(k)，變量k的取值只有X(k)中k的取值的一半。因此，對(duì)于X(k)表達(dá)式(4.2.4)，(4.2.6)(4.2.5)

(1) ：確定X(k)前半部分。

(2) ：確定X(k)的后半部分。(4.2.7)為表述方便，X(k)后半部分表示為 。由于點(diǎn)DFTX1(k)和X2(k)具有周期性，且周期均為N/2，即

而 ，因此，X(k)的后半部分為(4.2.8)由此可見：N點(diǎn)DFT可以分解為兩個(gè)N/2點(diǎn)DFT，按照式(4.2.7)和式(4.2.8)又可組合成N點(diǎn)DFT。因此求X(k)時(shí)，只要求出k=0，1，…，N/2－1時(shí)的X1(k)和X2(k)值，即可得到所有的X(k)值，即k=0，1，…，N－1，從而大大節(jié)省了運(yùn)算量，這也是快速傅里葉變換的特點(diǎn)和好處所在。

式(4.2.7)和式(4.2.8)的運(yùn)算可以用圖4.2.1所示的蝶形運(yùn)算流圖符號(hào)表示。圖中，左側(cè)為兩個(gè)輸入節(jié)點(diǎn)，右側(cè)為兩個(gè)輸出節(jié)點(diǎn)，左下支路上標(biāo)注系數(shù)，沒有標(biāo)注時(shí)系數(shù)默認(rèn)為1，右上支路默認(rèn)為相加運(yùn)算，右下支路為相減運(yùn)算。圖4.2.1

DIT-FFT的蝶形運(yùn)算流圖符號(hào)從圖4.2.1中可以看出，一個(gè)蝶形運(yùn)算需要1次復(fù)數(shù)乘法和2次復(fù)數(shù)加法。

通過采用蝶形運(yùn)算流圖符號(hào)，DIT-FFT經(jīng)過1次DFT分解之后，整個(gè)分解過程可用圖4.2.2所示的運(yùn)算流圖表示，其中DFT點(diǎn)數(shù)N=23=8，蝶形輸出值X(0)～X(3)由式(4.2.7)確定，X(4)～X(7)由式(4.2.8)確定。由于1個(gè)蝶形包括兩個(gè)輸入和兩個(gè)輸出，總共有N/2個(gè)蝶形。圖4.2.2

DIT-FFT的一次分解運(yùn)算流圖(N=8)從圖4.2.2可以看出，一個(gè)N點(diǎn)DFT可以由分解的兩個(gè)N/2點(diǎn)DFT通過N/2個(gè)蝶形進(jìn)行合成得到，總運(yùn)算量包括兩個(gè)N/2點(diǎn)DFT以及N/2個(gè)蝶形的計(jì)算。N/2個(gè)蝶形運(yùn)算需要N/2次復(fù)數(shù)乘法和2×N/2=N次復(fù)數(shù)加法。

對(duì)于兩個(gè)N/2點(diǎn)DFT，如果直接計(jì)算，需要復(fù)數(shù)乘法次數(shù)為復(fù)數(shù)加法次數(shù)為

因此，經(jīng)過一次分解后的N點(diǎn)DFT運(yùn)算量為

復(fù)數(shù)乘法：

復(fù)數(shù)加法：與直接計(jì)算N點(diǎn)DFT的運(yùn)算量相比，一次DFT分解后的運(yùn)算量減少了一半左右。這也充分說明：通過DFT分解可以有效地減少DFT的計(jì)算量。如果針對(duì)N/2點(diǎn)DFT也采用分解措施，將一個(gè)N/2點(diǎn)DFT分解為兩個(gè)N/4點(diǎn)DFT，那么可以進(jìn)一步減少運(yùn)算量。這就是下面討論的DFT的二次分解過程。

不妨以N/2點(diǎn)DFTX1(k)為例，將N/2點(diǎn)序列x1(r)按照奇偶分解方式進(jìn)行分解，得到兩個(gè)N/4點(diǎn)序列，分別為(4.2.10)(4.2.9)則有(4.2.11)上式右邊前一部分、后一部分求和項(xiàng)分別是序列x3(l)和x4(l)的N/4點(diǎn)DFT，即(4.2.12)(4.2.13)因此，當(dāng) 時(shí)，式(4.2.11)可直接表述為

當(dāng)

時(shí)，利用X3(k)、X4(k)周期性

以及

性質(zhì)，X1(k)表示為(4.2.14)(4.2.15)圖4.2.3給出了N=8時(shí)，一個(gè)N/2點(diǎn)DFT分解為兩個(gè)N/4點(diǎn)DFT的蝶形運(yùn)算流圖，即X1(k)分解為X3(k)和X4(k)，同時(shí)由X3(k)和X4(k)通過N/4個(gè)蝶形也可以合成X1(k)。圖4.2.3

N/2點(diǎn)DFT分解的蝶形運(yùn)算流圖(N=8)同理，對(duì)于N/2點(diǎn)DFTX2(k)也可以分解為兩個(gè)N/4點(diǎn)DFT：(4.2.16)(4.2.17)其中，X5(k)、X6(k)分別為x2(r)分解的偶序列和奇序列對(duì)應(yīng)的N/4點(diǎn)DFT。(4.2.18)(4.2.19)圖4.2.4給出了N=8點(diǎn)DFT經(jīng)過兩次分解后的蝶形運(yùn)算流圖。與第一次分解后的運(yùn)算量相比，利用4個(gè)N/4點(diǎn)DFT及兩級(jí)蝶形來計(jì)算N點(diǎn)DFT的運(yùn)算量又降低了。圖4.2.4

DIT-FFT的二次分解運(yùn)算流圖(N=8)可以看出，當(dāng)N=8時(shí)，通過兩次DFT分解后，N/4點(diǎn)DFT實(shí)際上為2點(diǎn)DFT，即X3(k)、X4(k)、X5(k)、X6(k)，k=0，1。此時(shí)，2點(diǎn)DFT可以直接進(jìn)行計(jì)算。以X3(k)計(jì)算式(4.2.12)為例，可得

而 ， ，因此有(4.2.20)(4.2.21)(4.2.22)式(4.2.21)和式(4.2.22)表明：2點(diǎn)DFT僅涉及加減法運(yùn)算，不需要乘法運(yùn)算；X4(k)、X5(k)、X6(k)也具有類似特點(diǎn)，它們都可用一個(gè)簡單的2點(diǎn)蝶形運(yùn)算表示。

依此類推，一個(gè)N=2M點(diǎn)DFT通過M－1次分解后，可以分解為N/2個(gè)2點(diǎn)DFT，得到M級(jí)蝶形運(yùn)算。對(duì)于8點(diǎn)DFT，通過二次分解后，可以得到三次蝶形運(yùn)算，圖4.2.5給出了完整的8點(diǎn)DIT-FFT蝶形運(yùn)算流圖。圖4.2.5

DIT-FFT的蝶形運(yùn)算流圖(N=8)圖4.2.5中，旋轉(zhuǎn)因子采用的表示形式；輸出為順序排列，但輸入并不是順序排列，而是在每一次分解過程中，將輸入序列按照時(shí)間上的偶數(shù)和奇數(shù)次序分解為兩個(gè)短序列，相當(dāng)于在時(shí)間上進(jìn)行抽取。最后得到的輸入序列也是非常有規(guī)律的，將在后面進(jìn)行介紹。所以，具有這種時(shí)間抽取關(guān)系的快速傅里葉變換稱為“時(shí)間抽取法FFT(DIT-FFT)”。4.2.2

DIT-FFT運(yùn)算量分析與比較

根據(jù)時(shí)間抽取法FFT算法的蝶形運(yùn)算流圖可知，當(dāng)N=2M時(shí)，共有M級(jí)蝶形運(yùn)算，每級(jí)均有N/2個(gè)蝶形，而每個(gè)蝶形運(yùn)算包含1次復(fù)數(shù)乘法和2次復(fù)數(shù)加法。因此，每一級(jí)蝶形都需要N/2次復(fù)數(shù)乘法和N次復(fù)數(shù)加法。M級(jí)蝶形的總運(yùn)算量為

復(fù)數(shù)乘法：

復(fù)數(shù)加法：(4.2.23)(4.2.24)

由于旋轉(zhuǎn)因子存在一些特例，如

，

，

，

，與這幾個(gè)系數(shù)相乘實(shí)際上不需要乘法運(yùn)算，這種情況在直接計(jì)算DFT時(shí)也存在。但是當(dāng)N較大時(shí)，這種特例相對(duì)較少。為了便于統(tǒng)一比較運(yùn)算量，這里不考慮這些特殊情況。

表4.2.1列出了N點(diǎn)DFT直接計(jì)算和DIT-FFT計(jì)算的運(yùn)算量，兩者復(fù)數(shù)乘法和復(fù)數(shù)加法之比分別為

復(fù)數(shù)乘法之比： (4.2.25)復(fù)數(shù)加法之比：(4.2.26)表4.2.1

N點(diǎn)DFT直接計(jì)算和DIT-FFT的運(yùn)算量比較當(dāng)N

1時(shí)，N

log2N，有N2

N·log2N，N(N－1)

N·log2N，因此，與直接計(jì)算DFT相比，DIT-FFT的運(yùn)算量大大減少。表4.2.2列出了不同N值條件下直接計(jì)算DFT與DIT-FFT的復(fù)數(shù)乘法次數(shù)及比例關(guān)系?？梢钥闯觯S著N增大，復(fù)數(shù)乘法次數(shù)的比值越大，DIT-FFT的優(yōu)勢越來越明顯。

但是也要注意到：當(dāng)N較小時(shí)(如N≤16)，比值也相對(duì)較小，考慮到DIT-FFT實(shí)際編程時(shí)的復(fù)雜性和指令開銷，DIT-FFT的整體運(yùn)算量不一定小于直接計(jì)算DFT。因此，在實(shí)際計(jì)算DFT時(shí)，需要根據(jù)N的大小，在直接計(jì)算和FFT之間靈活選擇。＞＞＞＞＞＞＞＞表4.2.2直接計(jì)算DFT與DIT-FFT的復(fù)數(shù)乘法次數(shù)的比較4.2.3

DIT-FFT運(yùn)算規(guī)律

為了更好地理解和掌握時(shí)間抽取法FFT算法，為算法的實(shí)際編程和硬件實(shí)現(xiàn)打下良好的基礎(chǔ)，下面對(duì)DIT-FFT的運(yùn)算規(guī)律和特點(diǎn)進(jìn)行分析和討論。

1.原位運(yùn)算

從圖4.2.5所示的DIT-FFT蝶形運(yùn)算流圖中可以看出：N=2M點(diǎn)FFT共有M級(jí)蝶形運(yùn)算，每級(jí)由N/2個(gè)蝶形構(gòu)成。在同一級(jí)中，每個(gè)蝶形的輸入和輸出都位于同一水平線上，并且每個(gè)輸入只參與本蝶形運(yùn)算，與其它蝶形無關(guān)。該特性意味著蝶形的輸出可以直接存入輸入所占用的存儲(chǔ)單元，這就是原位計(jì)算的特點(diǎn)。通過原位計(jì)算，每一級(jí)的N/2蝶形運(yùn)算完成后，所有輸出存入原輸入的存儲(chǔ)位置，然后開始下一級(jí)的蝶形運(yùn)算，只不過蝶形運(yùn)算的組合關(guān)系有所不同。這種原位計(jì)算結(jié)構(gòu)只需要N個(gè)存儲(chǔ)單元，節(jié)省了存儲(chǔ)開銷，降低了設(shè)備成本。

2.位碼倒序

觀察圖4.2.5所示的蝶形運(yùn)算流圖的輸入輸出可以看出，輸出序列是按照X(0)，X(1)，…，X(7)的順序排列，而輸入序列次序是x(0)，x(4)，…，x(7)，看起來似乎很亂，但實(shí)際上是有規(guī)律的，這種規(guī)律稱為位碼倒序。首先看看輸入序列是如何形成x(0)，x(4)，…，x(7)排列的。造成這種排列關(guān)系的原因是序列x(n)不斷地按照n的偶奇特性進(jìn)行分解。假設(shè)n用二進(jìn)制數(shù)表示為(n2n1n0)，那么，第一次分解是按照n0=0和n0=1分解為偶數(shù)序列和奇數(shù)序列，第二次分解是分別針對(duì)偶數(shù)序列和奇數(shù)序列，按照n1=0和n1=1進(jìn)行偶奇分解，最后得到的2點(diǎn)序列是按照n2=0和n2=1排列的。這種不斷分解為偶數(shù)序列和奇數(shù)序列的過程可用圖

4.2.6表示。圖4.2.6形成位碼倒序的樹狀圖若DIT-FFT輸入順序編號(hào)0，1，2，…，7用二進(jìn)制碼(n2n1n0)表示，那么圖4.2.6中DIT-FFT輸入序列可表示為x(n0n1n2)，其序號(hào)(n0n1n2)實(shí)際上是二進(jìn)制碼(n2n1n0)的比特左右反轉(zhuǎn)結(jié)果，兩者形成倒序關(guān)系。因此稱為位碼倒序。

表4.2.3列出了N=8時(shí)順序二進(jìn)制數(shù)及對(duì)應(yīng)的倒序二進(jìn)制數(shù)。給定順序的輸入序列x(n)，計(jì)算DIT-FFT時(shí)，將位碼倒序十進(jìn)制數(shù)作為序號(hào)來選擇x(n)。表4.2.3順序二進(jìn)制數(shù)與倒序二進(jìn)制數(shù)的對(duì)照表在實(shí)際編程實(shí)現(xiàn)DIT-FFT算法的過程中，可以采取以下方式：

(1)若采用通用計(jì)算機(jī)編程，可按照表4.2.3，依次將十進(jìn)制順序轉(zhuǎn)換為二進(jìn)制數(shù)、位碼倒序二進(jìn)制數(shù)以及最后的位碼倒序十進(jìn)制數(shù)，并依據(jù)位碼倒序十進(jìn)制數(shù)來選擇x(n)作為DIT-FFT的輸入。

(2)若通用計(jì)算機(jī)的存儲(chǔ)空間足夠，可將順序與位碼倒序十進(jìn)制數(shù)的對(duì)應(yīng)關(guān)系以表的形式存儲(chǔ)起來，通過查表方式來選擇x(n)。此時(shí)，只需要一個(gè)數(shù)組存儲(chǔ)位碼倒序十進(jìn)制數(shù)，數(shù)組位置表示順序號(hào)，數(shù)組的值代表位碼倒序十進(jìn)制數(shù)。

(3)若采用數(shù)字信號(hào)處理器(DSP)編程，可利用DSP自身的位碼倒序?qū)ぶ穼Ｓ弥噶顏硗瓿赊D(zhuǎn)換。以美國TI公司的TMS320C54系列DSP為例，假定N=8，輔助寄存器AR2指向x(0)的存儲(chǔ)單元，輔助寄存器AR0設(shè)置為FFT點(diǎn)數(shù)的一半，即AR0=4，那么，位碼倒序?qū)ぶ返膶Ｓ弥噶顬?/p>

*AR2+0B

該指令表示用反向進(jìn)位的方式將AR0加至AR2上，即加法按比特從高位向低位進(jìn)位，然后再賦值給AR2，*表示AR2指向地址的數(shù)值。注意到AR2初始地址低3位必須為零，以便進(jìn)行反向進(jìn)位。以低3位運(yùn)算為例，初始值為0，以反向進(jìn)位方式依次加4，可以得到4、2、6、1、5、3、7。運(yùn)算完畢后，AR0=4始終固定不變，AR2則按照位碼倒序的方式依次指向x(0)，x(4)，…，x(7)。

3.蝶形運(yùn)算規(guī)律

從圖4.2.5中N=8點(diǎn)DIT-FFT蝶形運(yùn)算流圖可以看出，從左至右，第一級(jí)蝶形對(duì)應(yīng)2點(diǎn)FFT，輸入數(shù)據(jù)相距1點(diǎn)，或者說蝶形張口大小為1；第二級(jí)蝶形輸入數(shù)據(jù)相距2點(diǎn)，蝶形張口大小為2；第三級(jí)蝶形輸入數(shù)據(jù)相距4點(diǎn)，蝶形張口大小為4。依此類推，對(duì)于N=2M點(diǎn)DIT-FFT，從左至右第m級(jí)蝶形輸入數(shù)據(jù)相距2m－1點(diǎn)，蝶形張口大小也為2m－1。利用蝶形張口大小的特點(diǎn)，便于從前一級(jí)輸出中選擇相應(yīng)數(shù)據(jù)作為輸入，來進(jìn)行本級(jí)的蝶形運(yùn)算。與蝶形運(yùn)算密切相關(guān)的有旋轉(zhuǎn)因子，觀察圖4.2.5可知，旋轉(zhuǎn)因子的個(gè)數(shù)與蝶形級(jí)數(shù)有關(guān)，第m級(jí)蝶形的旋轉(zhuǎn)因子有2m－1個(gè)，可以表示為

對(duì)于最后一級(jí)蝶形，m=M，旋轉(zhuǎn)因子有2M－1=N/2個(gè)。由于

因此，最后一級(jí)蝶形的旋轉(zhuǎn)因子均包含著前面M－1級(jí)蝶形的旋轉(zhuǎn)因子，所有旋轉(zhuǎn)因子以集合形式表示為

。(4.2.28)(4.2.27)表4.2.4給出了不同蝶形級(jí)數(shù)下的蝶形張口大小和旋轉(zhuǎn)因子。在實(shí)際DSP編程實(shí)現(xiàn)DIT-FFT時(shí)，可以將旋轉(zhuǎn)因子 制作成表的形式，然后根據(jù)式(4.2.27)中蝶形級(jí)數(shù)與WN指數(shù)k·2M－m的關(guān)系，查表得到當(dāng)前蝶形運(yùn)算所需要的旋轉(zhuǎn)因子。這樣可以避免直接計(jì)算復(fù)指數(shù)，能夠減少FFT運(yùn)算量。表4.2.4蝶形張口大小和旋轉(zhuǎn)因子與蝶形級(jí)數(shù)的關(guān)系4.2.4

DIT-FFT其它形式流圖

對(duì)于時(shí)間抽取法FFT算法，圖4.2.5的蝶形運(yùn)算流圖并不是唯一的，只要能夠保持各節(jié)點(diǎn)間的支路及其傳輸系數(shù)不變，不論如何改變輸入節(jié)點(diǎn)、輸出節(jié)點(diǎn)以及中間節(jié)點(diǎn)的排列順序，所得到的運(yùn)算流圖是等效的。這樣，通過對(duì)圖4.2.5進(jìn)行變形，就可以得到DIT-FFT其它形式的運(yùn)算流圖。

圖4.2.5中，蝶形運(yùn)算流圖的輸入為倒序，輸出為順序。通過變形，圖4.2.7給出了輸入為順序、輸出為倒序的運(yùn)算流圖形式，該流圖同樣具有原位計(jì)算的特點(diǎn)，其旋轉(zhuǎn)因子、運(yùn)算量也與圖4.2.5相同，只是在蝶形張口大小次序和旋轉(zhuǎn)因子排列上有所差別。若從左至右來看蝶形張口，圖4.2.5中是由小變大，而圖4.2.7中是由大變小。圖4.2.7

DIT-FFT的變形運(yùn)算流圖(輸入順序、輸出倒序)對(duì)于旋轉(zhuǎn)因子，圖4.2.5中最后一級(jí)按照 順序排列，而圖4.2.7中最后一級(jí)是按照 排列的，并且前一級(jí)的旋轉(zhuǎn)因子正好是本級(jí)上一半蝶形運(yùn)算的旋轉(zhuǎn)因子，順序也不變。這種流圖形式就是最初由庫利和圖基給出的時(shí)間抽取法FFT。

如果要獲得輸入和輸出均是順序排列的運(yùn)算流圖，可以對(duì)圖4.2.7的最后一級(jí)蝶形輸出進(jìn)行調(diào)整，得到圖4.2.8所示的運(yùn)算流圖。該流圖的旋轉(zhuǎn)因子、運(yùn)算量均與圖4.2.7相同，但是在最后一級(jí)上不能采用原位計(jì)算。圖4.2.8

DIT-FFT的變形運(yùn)算流圖(輸入順序、輸出順序) 4.3頻域抽取法(DIF)基-2FFT算法

4.3.1

DIF-FFT算法原理

設(shè)序列x(n)長度N=2M，N點(diǎn)DIF-FFT算法對(duì)應(yīng)著x(n)前后對(duì)半分解為兩部分，即前半部分x(n)和后半部分 。根據(jù)DFT的定義有(4.3.1)

由于 ，故

需要說明的是，上式中旋轉(zhuǎn)因子項(xiàng)是，而不是，因此，上式并不是一個(gè)N/2點(diǎn)DFT。式(4.3.2)要根據(jù)k為偶數(shù)或者奇數(shù)，將X(k)分為兩部分進(jìn)行討論。(4.3.2)

(1)k為偶數(shù)。令k=2r，

，則有(4.3.3)

(1)k為奇數(shù)。令k=2r+1，

，則有(4.3.4)可以看出，式(4.3.3)和式(4.3.4)都是N/2點(diǎn)DFT表達(dá)式，其中，式(4.3.3)變換對(duì)象是x(n)前半部分和后半部分相加形成的序列，式(4.3.4)變換對(duì)象則是x(n)前半部分和后半部分相減后再乘以形成的序列。定義兩個(gè)序列為(4.3.5)(4.3.6)將上述兩式分別代入式(4.3.3)和式(4.3.4)，可得

式(4.3.7)和式(4.3.8)表明：N點(diǎn)DFT按照k的奇偶特性，可以分解為兩個(gè)N/2點(diǎn)DFT。具體方法是將x(n)前后對(duì)半分解為兩部分，合成兩個(gè)新的N/2點(diǎn)序列，再進(jìn)行N/2點(diǎn)DFT。合成序列x1(n)、x2(n)與x(n)的關(guān)系可用圖4.3.1所示的蝶形運(yùn)算流圖符號(hào)表示。(4.3.7)(4.3.8)

利用上述蝶形運(yùn)算流圖符號(hào)，N=8點(diǎn)DFT經(jīng)過一次分解后，得到的運(yùn)算流圖如圖4.3.2所示。圖4.3.1

DIF-FFT的蝶形運(yùn)算流圖符號(hào)圖4.3.2

DIF-FFT一次分解的運(yùn)算流圖(N=8)與時(shí)間抽取法的推導(dǎo)過程一樣，由于N=2M，N/2仍為偶數(shù)，在圖4.3.2的基礎(chǔ)上，可以將每個(gè)N/2點(diǎn)DFT進(jìn)一步分解為兩個(gè)N/4點(diǎn)DFT。這相當(dāng)于分別將x1(n)和x2(n)進(jìn)行前后對(duì)半分解后，通過蝶形運(yùn)算，合成為4個(gè)N/4點(diǎn)序列，再進(jìn)行DFT。圖4.3.3給出了N=8點(diǎn)DFT經(jīng)過二次分解后的運(yùn)算流圖。

當(dāng)N=8時(shí)，經(jīng)過兩次分解得到的N/4點(diǎn)DFT即為2點(diǎn)DFT，可以直接進(jìn)行計(jì)算，相當(dāng)于一個(gè)基本的蝶形運(yùn)算符號(hào)。一個(gè)N=2M點(diǎn)DFT通過M－1次分解后，最后可分解為N/2個(gè)2點(diǎn)DFT，形成M級(jí)蝶形運(yùn)算。圖4.3.4給出了完整的8點(diǎn)DIF-FFT蝶形運(yùn)算流圖。圖4.3.3

DIF-FFT二次分解的運(yùn)算流圖(N=8)圖4.3.4

DIF-FFT的蝶形運(yùn)算流圖(N=8)觀察圖4.3.4可知，DIF-FFT的蝶形運(yùn)算流圖仍具有原位計(jì)算的特點(diǎn)，其輸入序列是順序的，而輸出是倒序的。這是由于每一級(jí)分解的輸出都按照k的奇偶次序分成為兩部分，這相當(dāng)于在頻率上進(jìn)行抽取，最后得到位碼倒序的輸出。因此，具有這種頻率抽取關(guān)系的快速傅里葉變換稱為“頻率抽取法FFT(DIF-FFT)”。4.3.2

DIF-FFT與DIT-FFT的比較

比較圖4.2.5中DIT-FFT蝶形運(yùn)算流圖和圖4.3.4中DIF-FFT的蝶形運(yùn)算流圖，兩者相同點(diǎn)如下：

(1)原位運(yùn)算。對(duì)于DIT-FFT和DIF-FFT，每個(gè)蝶形的輸入和輸出都位于同一水平線上，并且每個(gè)輸入只參與本蝶形運(yùn)算，蝶形的輸出可直接存入輸入所占用的存儲(chǔ)單元。

(2)運(yùn)算量相同。當(dāng)N=2M時(shí)，DIT-FFT和DIF-FFT都有M級(jí)蝶形運(yùn)算，每級(jí)均有個(gè)蝶形，復(fù)數(shù)乘法總數(shù)為log2N次，復(fù)數(shù)加法總數(shù)為N·log2N次。

DIT-FFT和DIF-FFT的差異如下：

(1)輸入和輸出排列次序不同。DIT-FFT輸入為倒序、輸出為順序，DIF-FFT輸入為順序、輸出為倒序。DIT-FFT的輸入序列的倒序由于序列不斷進(jìn)行奇偶分解所致，而DIF-FFT輸出的倒序是由于序列前后對(duì)半分解后，其合成子序列正好對(duì)應(yīng)著頻率的奇偶部分。DIT和DIF在名稱上也體現(xiàn)了這種不同點(diǎn)。

(2)蝶形張口大小和旋轉(zhuǎn)因子次序的不同。從左至右來看，DIT-FFT蝶形張口由小到大，旋轉(zhuǎn)因子由少到多；而DIF-FFT正好相反，蝶形張口由大到小，旋轉(zhuǎn)因子由多到少。

(3)基本蝶形運(yùn)算符號(hào)不同。圖4.2.1中DIT-FFT蝶形不同于圖4.3.1中DIF-FFT蝶形，DIT蝶形運(yùn)算在頻域進(jìn)行，先乘旋轉(zhuǎn)因子，后加減法；而DIF蝶形運(yùn)算在時(shí)域進(jìn)行，先加減法，后乘旋轉(zhuǎn)因子?；镜蔚牟煌攀莾煞NFFT算法本質(zhì)上的不同。

DIF-FFT和DIT-FFT的相互關(guān)系如下：

(1)基本蝶形運(yùn)算符號(hào)的轉(zhuǎn)置關(guān)系。若將圖4.2.1中的DIT的基本蝶形進(jìn)行轉(zhuǎn)置，這里轉(zhuǎn)置包括蝶形180°左右翻轉(zhuǎn)、支路方向反向以及輸入輸出交換，就可以得到圖4.3.1DIF的基本蝶形；同理，將DIF的基本蝶形加以轉(zhuǎn)置，也可得到DIT的基本蝶形。

(2)蝶形運(yùn)算流圖的轉(zhuǎn)置關(guān)系。對(duì)比圖4.2.5DIT和圖4.3.4DIF的兩種蝶形運(yùn)算流圖，可以互相轉(zhuǎn)置。這種特性有助于加深對(duì)兩種FFT算法的理解和把握。 4.4快速傅里葉逆變換(IFFT)算法

本節(jié)研究離散傅里葉逆變換(IDFT)的快速算法，即快速傅里葉逆變換(InverseFastFourierTransform，IFFT)。比較IDFT與DFT的計(jì)算公式：(4.4.2)(4.4.1)可以看出，兩者的差異在于變換對(duì)象(X(k)、x(n))、旋轉(zhuǎn)因子(、)以及有無修正因子(1/N)的不同。若從公式計(jì)算角度來看，只需要DFT公式中的旋轉(zhuǎn)因子換成，最后乘以1/N，就可以計(jì)算IDFT。

根據(jù)上述對(duì)IDFT和DFT的兩個(gè)層面比較分析，IFFT的計(jì)算可以有兩種方式：

(1)利用FFT蝶形運(yùn)算流圖。在FFT流圖的基礎(chǔ)上，按照變換對(duì)象、旋轉(zhuǎn)因子以及有無修正因子三個(gè)方面進(jìn)行適當(dāng)修改，得到IFFT的蝶形運(yùn)算流圖。這部分內(nèi)容在下面詳細(xì)討論。

(2)直接調(diào)用FFT程序。在用DFT公式計(jì)算IDFT的基礎(chǔ)上，通過FFT程序來計(jì)算IFFT，這樣，可以沿用FFT的蝶形運(yùn)算流圖。對(duì)IDFT表達(dá)式(4.4.1)兩邊取復(fù)共軛，可得

因此(4.4.3)(4.4.4)式(4.4.4)表明，利用FFT計(jì)算IDFT的過程如下：先將X(k)取共軛，然后直接調(diào)用FFT程序，計(jì)算結(jié)果取共軛后再乘以1/N。該方法雖然需要兩次取共軛，但FFT和IFFT算法可以共有一個(gè)程序，使用很方便，在實(shí)際應(yīng)用中大多采用這種方法。

下面重點(diǎn)討論IFFT的第一種計(jì)算方式——蝶形運(yùn)算流圖。若基于圖4.2.5所示的DIT-FFT蝶形運(yùn)算流圖，輸入x(n)要換成X(k)，旋轉(zhuǎn)因子變?yōu)?，輸出換成x(n)后再乘以1/N，這樣得到圖4.4.1所示的IFFT蝶形運(yùn)算圖?？梢钥闯?，原DIT-FFT的時(shí)間抽取變?yōu)镮FFT的頻率抽取，因此，該IFFT算法稱為頻率抽取法IFFT(DIF-IFFT)。圖4.4.1

DIF-IFFT的蝶形運(yùn)算流圖(N=8)若基于圖4.3.4所示的DIF-FFT蝶形運(yùn)算流圖，同樣也需要修改三個(gè)方面：輸入x(n)換成X(k)，旋轉(zhuǎn)因子變?yōu)椋敵鰮Q成x(n)后再乘以1/N，這樣得到的IFFT蝶形運(yùn)算圖如圖4.4.2所示的。圖中，原DIF-FFT的頻率抽取變?yōu)镮FFT的時(shí)間抽取，因此，該IFFT算法稱為時(shí)間抽取法IFFT(DIT-IFFT)。圖4.4.2

DIT-IFFT的蝶形運(yùn)算流圖(N=8)在實(shí)際應(yīng)用中，為了防止IFFT算法運(yùn)行過程出現(xiàn)溢出，可以將分?jǐn)偟矫恳患?jí)蝶形中。由于，因此，正好M級(jí)蝶形中每個(gè)蝶形輸出均乘以。以圖4.4.2的DIF-IFFT為例，經(jīng)過防溢出處理后的蝶形運(yùn)算圖如圖4.4.3所示。圖4.4.3

DIT-IFFT的蝶形運(yùn)算流圖(N=8，防止溢出)下面關(guān)于溢出問題展開進(jìn)一步討論。

由于在實(shí)際DSP編程實(shí)現(xiàn)過程中，數(shù)值的表示存在著位數(shù)的限制，如定點(diǎn)DSP為16位(bit)，最高位表示符號(hào)位，可表示的整數(shù)值介于－32768～32767之間，浮點(diǎn)DSP則通常為32位。在進(jìn)行FFT或者IFFT運(yùn)算時(shí)，難免會(huì)出現(xiàn)溢出的問題。如定點(diǎn)DSP對(duì)一個(gè)單音進(jìn)行頻譜分析，其頻域上的單頻成分就非常高，很容易溢出。在這種情況下，可以考慮在某幾級(jí)蝶形運(yùn)算中再乘以1/2，避免數(shù)值溢出；同時(shí)，可以設(shè)置DSP的防溢出控制位，來限定最大值和最小值，避免數(shù)值溢出后出現(xiàn)正負(fù)數(shù)顛倒。

4.5

FFT算法的工程實(shí)現(xiàn)考慮

前面幾節(jié)討論的FFT和IFFT算法由于結(jié)構(gòu)非常有規(guī)律，算法編程效率高，在實(shí)際數(shù)字信號(hào)處理中有著廣泛的應(yīng)用。下面將討論FFT算法在工程實(shí)現(xiàn)時(shí)需要考慮的問題。

4.5.1旋轉(zhuǎn)因子的生成

在FFT算法中，如何有效且快速地生成旋轉(zhuǎn)因子是一個(gè)關(guān)鍵，直接涉及到蝶形中的乘法運(yùn)算。以為例，k=0，1，2，…，－1，共有個(gè)復(fù)指數(shù)值，可展開為實(shí)部和虛部的形式：

可以看出，的生成包括余弦值和正弦值的計(jì)算，在編程實(shí)現(xiàn)時(shí)如何快速產(chǎn)生直接影響運(yùn)算速度。

旋轉(zhuǎn)因子的生成通常有兩種方式：預(yù)先計(jì)算和直接計(jì)算。

1.預(yù)先計(jì)算

基本思想是預(yù)先計(jì)算出來所有N/2個(gè)值，以表的形式存儲(chǔ)起來，供查找使用。該方法稱為查表法，適用于FFT點(diǎn)數(shù)N已知的情況，且N不宜過大；否則，占用內(nèi)存過多。從相位上看，相當(dāng)于將2π分成N等份，取前N/2個(gè)弧度值2πk/N(k=0，1，2，…，N/2－1)。(4.5.1)由于式(4.5.1)包括余弦值和正弦值，按照常理可以分開制成余弦表和正弦表。但是，考慮到余弦和正弦在相位上相差π/2，即sin(α+π/2)=cosα，可以將余弦表和正弦表合成一張表，相位覆蓋［0，2π］，共N個(gè)弧度值2πk/N(k=0，1，2，…，N－1)，只計(jì)算N個(gè)正弦值，構(gòu)成一張正弦表。查表時(shí)，首先查找正弦值，然后向前搜索π/2，即N/4個(gè)弧度值，即可得到對(duì)應(yīng)的余弦值。合成一張［0，2π］正弦表的好處是該表可同時(shí)用于除計(jì)算旋轉(zhuǎn)因子之外的其它場合，如查表計(jì)算任意相位的余弦值或正弦值、產(chǎn)生數(shù)字頻率等，這在數(shù)字信號(hào)處理領(lǐng)域特別是數(shù)字通信中常常出現(xiàn)。下面討論如何查表得到任意相位的正弦值。假設(shè)相位α∈［0，2π)，單位為弧度，在N個(gè)弧度值2πk/N中α對(duì)應(yīng)的位置可表示為

其中，［·］表示向下取整，即不超過的最大整數(shù)。當(dāng)然，也可以采用四舍五入。通過查正弦表中nα位置，其對(duì)應(yīng)的值即為正弦值。通過查表計(jì)算正弦值的實(shí)質(zhì)是查找相鄰相位及其正弦值來進(jìn)行逼近，其精度高低與N的大小密切相關(guān)。若N值比較大，逼近誤差較小，精度較高，但同時(shí)內(nèi)存開銷較大；若N值比較小，逼近誤差較大，精度有限。(4.5.2)在實(shí)際中N值通常是確定的，為了進(jìn)一步提高計(jì)算精度，基于給定的正弦表，可以通過內(nèi)插獲得更高的精度。如N=512，相鄰相位差約為0.7°，比較小，連續(xù)正弦波可以用所有離散正弦值的直線連接來逼近。此時(shí)，利用α的左右相鄰相位進(jìn)行線性內(nèi)插即可得到所需要的正弦值，其計(jì)算公式為(4.5.3)

2.直接計(jì)算

基本思想是運(yùn)用Taylor級(jí)數(shù)展開式，直接計(jì)算余弦值和正弦值。余弦和正弦的Tylor公式為

直接計(jì)算的特點(diǎn)是精度很高，但是運(yùn)算量比較大，適合于非實(shí)時(shí)性處理。(4.5.4)(4.5.5)4.5.2旋轉(zhuǎn)因子的使用

一旦旋轉(zhuǎn)因子生成好了，就可以直接參與蝶形乘法運(yùn)算，按照FFT蝶形運(yùn)算流圖，逐級(jí)完成整個(gè)FFT計(jì)算。那么，是否還有必要專門討論如何使用旋轉(zhuǎn)因子呢？實(shí)際上還是非常有必要的，因?yàn)樵趯?shí)現(xiàn)FFT或DFT時(shí)，可能使用DSP、FPGA或者通用計(jì)算機(jī)，不同的實(shí)現(xiàn)方式有不同的特點(diǎn)，對(duì)旋轉(zhuǎn)因子的使用和處理方式也不同。

就旋轉(zhuǎn)因子本身而言，在計(jì)算FFT和DFT時(shí)，有很多特殊值，如

這樣，可以不需要采用乘法甚至加減法，只需要簡單的操作即可。鑒于通常情況下乘法的運(yùn)算量要大于加法，針對(duì)這些特殊值作特別的編程處理，似乎可以降低運(yùn)算量。但是，特殊編程處理增加了程序的復(fù)雜性，是否值得要取決于乘法和加法有多大差異，這與實(shí)現(xiàn)FFT或DFT的器件密切相關(guān)。

(1)若采用數(shù)字信號(hào)處理芯片(DSP)，由于DSP通常擁有專門的乘法指令，其指令運(yùn)算時(shí)間與加減法指令一樣，因此，完全可以進(jìn)行乘法運(yùn)算，沒有必要針對(duì)旋轉(zhuǎn)因子作特殊編程處理。

(2)若采用FPGA或通用計(jì)算機(jī)，由于乘法運(yùn)算單元占用的硬件和運(yùn)算資源通常要大大超過加減法，因此，根據(jù)實(shí)際FPGA型號(hào)或者計(jì)算機(jī)的資源狀況，可在直接進(jìn)行乘法運(yùn)算和特殊編程處理之間進(jìn)行合理選擇。4.5.3實(shí)序列的FFT計(jì)算

在實(shí)際工作中，序列x(n)通常為實(shí)數(shù)序列，如模擬信號(hào)經(jīng)過A/D采樣后為實(shí)數(shù)字信號(hào)。如果直接按照FFT蝶形流圖進(jìn)行計(jì)算，需要將x(n)看做虛部為零的復(fù)序列，而由DFT的共軛對(duì)稱性可知，實(shí)序列的FFT具有共軛對(duì)稱性。如果能夠利用實(shí)序列及其FFT的特點(diǎn)，可以降低FFT的運(yùn)算量。

(1)一個(gè)N點(diǎn)FFT計(jì)算兩個(gè)N點(diǎn)實(shí)序列的FFT。

基本做法是將兩個(gè)N點(diǎn)實(shí)序列分別作為實(shí)部和虛部，構(gòu)成N點(diǎn)復(fù)序列，再進(jìn)行FFT。根據(jù)DFT的共軛對(duì)稱性可知，實(shí)部FFT對(duì)應(yīng)到復(fù)序列FFT的共軛對(duì)稱部分，j和虛部的FFT對(duì)應(yīng)到復(fù)序列FFT的共軛反對(duì)稱部分。具體過程參見第3章中DFT共軛對(duì)稱性的應(yīng)用——兩個(gè)實(shí)序列的