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

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

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

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

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

4.5

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

習題

4.1直接計算DFT的運算量及改進途徑

4.1.1直接計算DFT的運算量

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

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

簡便，下面只討論DFT的運算量。

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

當N

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

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

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

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

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

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

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

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

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

對稱性：

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

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

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

4.2.1

DIT-FFT算法原理

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

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

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

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

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

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

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

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

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

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

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

對于兩個N/2點DFT，如果直接計算，需要復數(shù)乘法次數(shù)為復數(shù)加法次數(shù)為

因此，經過一次分解后的N點DFT運算量為

復數(shù)乘法：

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

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

當

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

以及

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

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

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

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

依此類推，一個N=2M點DFT通過M－1次分解后，可以分解為N/2個2點DFT，得到M級蝶形運算。對于8點DFT，通過二次分解后，可以得到三次蝶形運算，圖4.2.5給出了完整的8點DIT-FFT蝶形運算流圖。圖4.2.5

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

DIT-FFT運算量分析與比較

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

復數(shù)乘法：

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

由于旋轉因子存在一些特例，如

，

，

，

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

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

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

N點DFT直接計算和DIT-FFT的運算量比較當N

1時，N

log2N，有N2

N·log2N，N(N－1)

N·log2N，因此，與直接計算DFT相比，DIT-FFT的運算量大大減少。表4.2.2列出了不同N值條件下直接計算DFT與DIT-FFT的復數(shù)乘法次數(shù)及比例關系。可以看出，隨著N增大，復數(shù)乘法次數(shù)的比值越大，DIT-FFT的優(yōu)勢越來越明顯。

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

DIT-FFT運算規(guī)律

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

1.原位運算

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

2.位碼倒序

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

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

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

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

(2)若通用計算機的存儲空間足夠，可將順序與位碼倒序十進制數(shù)的對應關系以表的形式存儲起來，通過查表方式來選擇x(n)。此時，只需要一個數(shù)組存儲位碼倒序十進制數(shù)，數(shù)組位置表示順序號，數(shù)組的值代表位碼倒序十進制數(shù)。

(3)若采用數(shù)字信號處理器(DSP)編程，可利用DSP自身的位碼倒序尋址專用指令來完成轉換。以美國TI公司的TMS320C54系列DSP為例，假定N=8，輔助寄存器AR2指向x(0)的存儲單元，輔助寄存器AR0設置為FFT點數(shù)的一半，即AR0=4，那么，位碼倒序尋址的專用指令為

*AR2+0B

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

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

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

對于最后一級蝶形，m=M，旋轉因子有2M－1=N/2個。由于

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

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

DIT-FFT其它形式流圖

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

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

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

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

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

4.3.1

DIF-FFT算法原理

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

由于 ，故

需要說明的是，上式中旋轉因子項是，而不是，因此，上式并不是一個N/2點DFT。式(4.3.2)要根據(jù)k為偶數(shù)或者奇數(shù)，將X(k)分為兩部分進行討論。(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點DFT表達式，其中，式(4.3.3)變換對象是x(n)前半部分和后半部分相加形成的序列，式(4.3.4)變換對象則是x(n)前半部分和后半部分相減后再乘以形成的序列。定義兩個序列為(4.3.5)(4.3.6)將上述兩式分別代入式(4.3.3)和式(4.3.4)，可得

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

利用上述蝶形運算流圖符號，N=8點DFT經過一次分解后，得到的運算流圖如圖4.3.2所示。圖4.3.1

DIF-FFT的蝶形運算流圖符號圖4.3.2

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

當N=8時，經過兩次分解得到的N/4點DFT即為2點DFT，可以直接進行計算，相當于一個基本的蝶形運算符號。一個N=2M點DFT通過M－1次分解后，最后可分解為N/2個2點DFT，形成M級蝶形運算。圖4.3.4給出了完整的8點DIF-FFT蝶形運算流圖。圖4.3.3

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

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

DIF-FFT與DIT-FFT的比較

比較圖4.2.5中DIT-FFT蝶形運算流圖和圖4.3.4中DIF-FFT的蝶形運算流圖，兩者相同點如下：

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

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

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

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

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

(3)基本蝶形運算符號不同。圖4.2.1中DIT-FFT蝶形不同于圖4.3.1中DIF-FFT蝶形，DIT蝶形運算在頻域進行，先乘旋轉因子，后加減法；而DIF蝶形運算在時域進行，先加減法，后乘旋轉因子。基本蝶形的不同才是兩種FFT算法本質上的不同。

DIF-FFT和DIT-FFT的相互關系如下：

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

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

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

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

(1)利用FFT蝶形運算流圖。在FFT流圖的基礎上，按照變換對象、旋轉因子以及有無修正因子三個方面進行適當修改，得到IFFT的蝶形運算流圖。這部分內容在下面詳細討論。

(2)直接調用FFT程序。在用DFT公式計算IDFT的基礎上，通過FFT程序來計算IFFT，這樣，可以沿用FFT的蝶形運算流圖。對IDFT表達式(4.4.1)兩邊取復共軛，可得

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

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

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

DIT-IFFT的蝶形運算流圖(N=8)在實際應用中，為了防止IFFT算法運行過程出現(xiàn)溢出，可以將分攤到每一級蝶形中。由于，因此，正好M級蝶形中每個蝶形輸出均乘以。以圖4.4.2的DIF-IFFT為例，經過防溢出處理后的蝶形運算圖如圖4.4.3所示。圖4.4.3

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

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

4.5

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

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

4.5.1旋轉因子的生成

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

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

旋轉因子的生成通常有兩種方式：預先計算和直接計算。

1.預先計算

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

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

2.直接計算

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

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

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

就旋轉因子本身而言，在計算FFT和DFT時，有很多特殊值，如

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

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

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

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

(1)一個N點FFT計算兩個N點實序列的FFT。

基本做法是將兩個N點實序列分別作為實部和虛部，構成N點復序列，再進行FFT。根據(jù)DFT的共軛對稱性可知，實部FFT對應到復序列FFT的共軛對稱部分，j和虛部的FFT對應到復序列FFT的共軛反對稱部分。具體過程參見第3章中DFT共軛對稱性的應用——兩個實序列的