(完整word版)實序列FFT算法的C語言實現(xiàn)(word文檔良心出品).doc

1、實序列 FFT 算法的 C 語言實現(xiàn)學生： XX指導教師：XX內(nèi)容摘要 ： DFT和IDFT 是數(shù)字信號分析與處理中的一種重要運算和變換，但直接根據(jù)定義計算 DFT時，運算量大，不能實時得到計算結(jié)果。特別是在實際應(yīng)用中，N 都取得比較大，此時，由于乘法和加法的次數(shù)都近似與N 的平方成正比，這將極大增加DFT計算所需時間。為此，提出了許多DFT和 IDFT 的快速算法，稱為快速傅里葉變換（FFT）和快速傅里葉反變換（ IFFT）。本文較為系統(tǒng)地闡述了快速傅里葉變換的算法原理然后用MATLAB實現(xiàn)了快速傅里葉變換。論文首先首要介紹了 FT 與 DFT的定義、 DFT與 FFT的關(guān)系 , 然后重點介

2、紹基 2 時域抽取 FFT算法以及其原理和運算流圖，再應(yīng)用 C語言實現(xiàn)了實序列的 FFT。最后在 Matlab 軟件上進行仿真，仿真結(jié)果驗證了設(shè)計的正確性。關(guān)鍵詞 ： 傅里葉變換快速傅立葉變換Matlab仿真Realization of FFT algorithm for real sequenceWith C programAbstract： DFTand IDFT are important transform and processingindigital signalprocessing.However,therearelargeamountofcomputationbydirectl

3、ycalculating according to the definition of DFT. Especially in the practicalapplication, N is bigger, at this time, because the time of multiplication andaddition are approximately proportional to the square of N, which will greatlyincreasethecalculationtimeneeded forDFT. Therefore,many DFT and IDFT

4、 fastalgorithm are raised, which are called FFT and IFFT.In thispaper relativelysystematicallyelaboratedthefastFouriertransformalgorithmprinciple and use MATLABsoftware to realizethe fastFouriertransform.The paper firstintroducesthedefinitionof FT and DFT,the relationshipbetweenDFT and FFT, and then

5、 mainly introduces DIT-FFT ,including its principle andoperationflowdiagram,and finallyused C language torealizetherealsequenceFFT.The designsare simulatedin Matlabsoftware,theresultsofthe simulationconfirm the exactness of the design.Keywords ： FouriertransformationfastFouriertransformationMatlabsi

6、mulation目錄前言 .11序列的 FT 和 DFT.11.1序列的 FT .11.2序列的 DFT .21.2.1DFT 的定義和計算 .21.2.2實序列的 DFT.22 FFT 算法 .32.1基 2 時域抽取 FFT算法 .32.1.1基本原理 .32.1.2DIT-FFT 算法的運算流圖 .52.1.3DIT-FFT 算法的運算量和存儲量 .52.2實序列的 FFT算法 .63實序列 FFT算法的 C語言實現(xiàn) .73.1VS2010簡介 .73.1.1新建項目 .83.1.2新建文件 .83.2實序列 FFT算法子程序 .93.2.1倒序 .103.2.2蝶形運算 .123.3實

7、序列 FFT算法主程序 .153.3.1原始序列的產(chǎn)生和讀取 .153.3.2計算結(jié)果的顯示和輸出 .163.4運行結(jié)果分析 .163.4.1計算結(jié)果數(shù)據(jù)分析 .173.4.2N 點 DFT波形分析 .174結(jié)束語 .20附錄： .21參考文獻： .27實序列 FFT 算法的 C 語言實現(xiàn)前言在實際的數(shù)字系統(tǒng)中， DFT是一種得到了廣泛的應(yīng)用的、重要的信號處理手段，但它的運算效率非常低。隨著DFT輸入的點數(shù)增加到數(shù)百或數(shù)千，DFT需要的運算量變得非常大。快速傅里葉變換（FFT）可使實現(xiàn)DFT 的運算量下降幾個數(shù)量級，從而使數(shù)字信號處理的速度大大提高1 。FFT 是離散傅立葉變換（ DFT）的快

8、速算法，可以將一個信號變換到頻域。有些信號在時域上是不易看出有什么特征的，但是如果變換到頻域之后，就很容易了。 FFT 可以將一個信號的頻譜提取出來，這在頻譜分析方面也是經(jīng)常用的。實際中需要做快速傅里葉變換的多為實序列數(shù)據(jù)， 而其變換算法都是以復數(shù)序列作為輸入。本設(shè)計利用頻域的性質(zhì)， 將實序列數(shù)據(jù)變?yōu)閺蛿?shù)序列， 再進行 FFT,以提高效率。本設(shè)計就是要求在熟悉 DFT及 FFT算法基本原理的基礎(chǔ)上， 編制 C 語言程序?qū)崿F(xiàn)實數(shù)序列的 FFT算法。1序列的 FT 和 DFT序列的傅里葉變換（ FourierTransform ，F(xiàn)T）和離散傅里葉變換（ DFT）都是對序列的頻域描述，它們揭示了序

9、列由那些分量構(gòu)成，各分量的幅度和相位大小。1.1序列的 FT序列 x( n) 的傅里葉變換又稱為離散時間傅里葉變換（DTFT），其定義為X (ej )FT x(n)x(n)e j n（ 1.1-1 ）n式中，稱為數(shù)字角頻率。如果已知x n的傅里葉變換Xj)，則可下式求得其時域( )(e表達式1)e j n dx(n)X (ej（ 1.1-2 ）2-上式稱為序列的傅里葉反變換（IFT ）。序列的傅里葉變換是的連續(xù)函數(shù)，且一般情況下為復變函數(shù)，并可表示為X (ej )| X (ej ) | ej ( )其中， | X (ej ) |和( ) 分別稱為幅度譜和相位譜。此外，根據(jù) ej的周期性可知，序

10、列的頻譜及其幅度譜和相位譜都是關(guān)于以 2 為1周期的周期函數(shù)。1.2序列的 DFT序列的 FT變換 X (e j w ) 為的連續(xù)函數(shù)，不便于用計算機程序進行輔助分析和計算。為了便于用計算機輔助求解和分析，提出了離散傅里葉變換（DFT）。1.2.1 DFT的定義和計算長度為 M的有限長序列 x( n) ， n=0M-1，其 N 點 DFT和 IDFT（離散傅里葉反變換）分別定義為X (k)DFT x(n)N1x(n)WNknn0， k=0N-1（1.2.1-1）x(n)IDFT X (k )1 N1X (k)WN nk， n=0N-1（1.2.1-2）N k02j式中， WNe N ，稱為旋轉(zhuǎn)

11、因子。借助于矩陣，可以將以上兩式所示序列的N點和IDFT運算用矩陣表示為DFTX (0)W 0W 0W 0W 0x(0)X (1)W 0W 1 1W 1 2W1 (N 1)x(1)W 0X ( N1)W 0W ( N1 ) 1W(N 1) 2W(N 1)(N 1)x(N 1)x( 0)W 0W 0W 0W 0X (0)x(1)1W 0W 11W 2 1W (N1)1X (1)NW 0x( N 1)W0 W 1(N1)W 2(N1)W (N1)(N1)X(N 1)（ 1.2.1-3 ）（ 1.2.1-4 ）1.2.2實序列的 DFT實際系統(tǒng)中所處理的信號大多數(shù)是實序列，對這些實序列 x( n)

12、，根據(jù)式（1.2.1-1 ）得到N 1N 1N 1X ( Nk)x( n)WN( N k) nx(n)WNNnWN knx(n)WN knn 0n 0n 0則N 1*N 1*N 1*X* (Nk)x(n)Wknx(n)W knx* (n) WknNNNn 0n 0n 0因為 x( n) 為實序列，則 x* (n)x(n) 。此外，有2-j2*j2*-j2WN kn *e N(kn)e N kne NknWNkn因此N 1*N 1X * ( N k)x* ( n) WN knx( n)WNknX (k )n 0n 0或者X ( Nk)X * (k)（1.2.1-5 ）上式說明，所有實數(shù)序列的DF

13、T都具有共軛對稱性。因此，對實序列，只需要計算出其 N點DFT中的前面N 個點，即kN的點，即可根據(jù)共軛對稱性，由式/2=0 /2-1（1.2.1-5）求出另外 N個點，即k NN的點，合起來得到完整的N點。/2= /2-1DFT在式（ 1.2.1-5 ）中分別令 k=0 和 N/2 ，又可得到X(N)X*(0)X (0)X(N / 2) X*(N / 2)以上兩式說明，在實序列的N點中，當k=0和N時一定為實數(shù)。DFT/22 FFT 算法DFT和 IDFT 是數(shù)字信號分析與處理中的一種重要運算和變換，但直接根據(jù)定義計算DFT時，運算量大，不能實時得到計算結(jié)果。特別是在實際應(yīng)用中，N 都取得比

14、較大，此時，由于乘法和加法的次數(shù)都近似與N的平方成正比，這將極大增加DFT計算所需時間。為此，提出了許多 DFT和 IDFT 的快速算法，稱為快速傅里葉變換（FFT）和快速傅里葉反變換（ IFFT） 2 。m分解幾個較FFT 和 IFFT算法的基本思想是根據(jù)旋轉(zhuǎn)因子 W 的對稱性，將 N 點NDFT短的 DFT，從而減少乘法次數(shù)，縮短計算時間。根據(jù)這一思想，出現(xiàn)了許多DFT和 IDFT的快速算法。下面結(jié)合本設(shè)計重點介紹基2 時域抽取 FFT算法。2.1基 2 時域抽取 FFT算法時域抽取 FFT算法（ DIT-FFT）的基本思想是在時域中將N 點序列 x( n) 中的各點按序號的奇偶進行抽取分

15、組，得到兩個N/2 點序列。在計算出兩個N/2 點序列的 DFT后，3通過蝶形運算得到原序列的N點 DFT 。2.1.1基本原理假設(shè)序列 x( n) 的長度為 N=2M，其中 M為正整數(shù)。根據(jù)序號n 的奇偶將 x( n) 分解為3兩個 N/2 點的子序列，即x1 (r )x(2r )x2 (r ), r 0 N / 2 1x(2r 1)則X (k) DFT x(n)x(n)WNknx(n)WNknn 偶數(shù)n 奇數(shù)N / 212krN/2 11)W k( 2r 1)x(2r )Wx(2rr 0Nr 0NN / 21N / 21x1 (r)WN2 krWNkx2 (r)WN2krr 0r 0令N

16、/21N /21X(k )x (r )W 2krx (r )W kr11N1N /2r 0r 0N /21(r )W 2krN /21X(k)xx (r)W kr22N2N /2r 0r0分別為序列x1r)和 x2r)的 N點，則得到(/2DFTX (k) X(k ) W kX( k) ，k N（2.1.1-1）1N2=0 /2-1由于X1(k和 X2k都以N點為周期，且)()/222j2WNk N / 2j( k N / 2 )jkkWNke Ne N e j e N因此式（ 2.1.1-1）可表示為X (k)X1 (k)WNk X 2 ( k)，k=0N/2-1（2.1.1-2）X (kN

17、 /2)X1 (k)WNk X 2 (k)上式代表的運算稱為蝶形運算，可用圖 2.1.1-1所示的流圖符號表示。例如，令上式中的k，則得到一個蝶形運算為=1X (1)X1(1)WN1 X 2 (1)X (1N/2)X1(1)WN1 X 2 (1)通過上述過程，就將序列 xn的 N 點DFT分解為兩個N點的，在得到X1(k)( )/2DFT和X2k)以后，通過 N個蝶形運算即可得到X k)。(/2(4AA+BCCBA-BC圖 2.1.1-1蝶形運算符號重復上述分解過程，繼續(xù)將序列x1( n) 和 x2( n) 按序號的奇偶進行抽取分解，直到最終分解為 N/2 個兩點序列。通過每次抽取分解，都將序

18、列和DFT的點數(shù)縮短一半，同時轉(zhuǎn)換為若干蝶形運算。2.1.2DIT-FFT 算法的運算流圖根據(jù)上述分解過程，容易知道，對N 點 DFT，只需通過 M=log 2N 次抽取，就可以將原來的 N點 DFT分解為 N個 1 點 DFT和 M級蝶形運算，而1 點 DFT就是序列本身。以，從而得到完整的蝶形運算流圖如圖2.1.2-1所示。x(0)X(0)x(4)0X(1)WNx(2)WN0X(2)x(6)02X(3)WNWNx(1)WN0X(4)x(5)0WN1X(5)WN02X(6)x(3)WNWNx(7)023X(7)WNWNWN圖 2.1.2-1 8 點 DIT-FFT 運算流圖2.1.3DIT-

19、FFT 算法的運算量和存儲量根據(jù)上述分解過程，容易知道，對N 點 DFT，只需通過 M=log 2N 次抽取，就可以將根據(jù)上述 DIT-FFT 的基本原理，通過時域抽取，將N 點 DFT轉(zhuǎn)換為 M級蝶形運算，每級5包括 N/2 個蝶形運算，因此 N 點 FFT共包括 MN/2 個蝶形運算。每個蝶形運算需要一次乘法運算和兩次加法運算，則 N點 FFT的運算量為：乘法：MN1 N log2 N22加法： MNN log 2 N而 DFT直接算法共需 N2 次乘法和 N( N-1) 次加法。當 N1 時，采用 FFT算法將大大減少運算次數(shù)，提高運算速度。由圖 2.1.2-1所示運算流圖可知， DIT

20、-FFT 的運算過程很有規(guī)律。在同一級的N/2個蝶形運算中，每個蝶形運算的兩個輸入輸出數(shù)據(jù)只對該蝶形有用，而且都位于同一條水平線上。因此，每個蝶形的兩個輸出數(shù)據(jù)可以只占用輸入數(shù)據(jù)的存儲單位，而不要另外分配存儲單元。這種存儲計算數(shù)據(jù)的方法稱為原位計算。原位計算可以極大地節(jié)省存儲單元。對N 點 FFT 算法，只需要 N 個存儲單元。運算一開始，這 N個單元用于存儲原始序列。 計算過程中，用于存儲各蝶形運算的輸出數(shù)據(jù)。4運算完畢后，這N個單元中存儲的就是輸出N點 FFT 。2.2實序列的 FFT算法實際系統(tǒng)中處理的序列都是實數(shù)序列。如果直接按照前述的FFT算法進行計算，就是將其視為虛部都為0 的復數(shù)

21、序列，這就增加了存儲量，降低了運算效率。處理該問題的方法有很多。例如，通過一個 N 點 FFT同時計算出兩個實數(shù)序列的 N 點 FFT；根據(jù)基 2 時域抽取 FFT 算法的基本思想，用一個 N/2 點 FFT 計算出一個實序列的 N 點 FFT5 。本設(shè)計采用另外一種方法，以減少運算量和存儲量。已經(jīng)知道，實序列的mDFT都具有共軛對稱性，或者說，其實部都是偶對稱的、虛部都是奇對稱的。利用這種共軛對稱性，計算時可以只計算出序列的 N 點DFT中前面 N個點，即 XX N。在得/2+1(0)( /2)到這些點后，利用共軛對稱性，通過簡單的替換就可得到完整的N點。DFT采用這種方法計算時，不需要存儲

22、后面N個點，即NN。此外，/2-1X( /2+1)X(-1)實序列的 N點 DFT中，X(0) 和 X( N/2) 一定為實數(shù)，因此計算過程中也不需要存儲其虛部。這就極大地減少了存儲量。以實序列的 8 點 DFT為例，根據(jù)共軛對稱性有：X *(7)X (1), X * (6)X (2), X *(5)X (3)因此，只需計算出X(0) X(4) ，即可根據(jù)以上各式得到X(5) X(7) ，進而得到完整的8點 DFT。6此外，對實數(shù)序列的8點，X和X一定是實數(shù)，因此計算過程中只需為XDFT (0)(4)(0)和 X(4) 分別分配一個存儲單元。3 實序列 FFT算法的 C語言實現(xiàn)根據(jù)設(shè)計要求，利

23、用VS2010軟件編制了 C 語言程序，實現(xiàn)實序列的基2 時域抽取FFT算法。3.1 VS2010 簡介VS2010提供了兩類容器，以便有效地管理開發(fā)工作所需的項，如引用、數(shù)據(jù)連接、文件夾和文件。 這兩類容器分別叫做解決方案和項目。此外，VS2010還提供解決方案文件夾，用于將相關(guān)的項目組織成項目組，然后對這些項目組執(zhí)行操作。作為查看和管理這些容器及其關(guān)聯(lián)項的界面。為了使集成開發(fā)環(huán)境 (IDE) 能夠應(yīng)用它的各種工具、 設(shè)計器、模板和設(shè)置， Visual Studio 2010（簡稱 VS2010）實現(xiàn)了概念上的容器 （稱為解決方案和項目） 。 另外，Visual Studio 還提供了解決方

24、案文件夾，用于將相關(guān)的項目組織成組，然后對這些項目組執(zhí)行操作。解決方案管理 Visual Studio配置、生成和部署相關(guān)項目集的方式。解決方案可以只包含一個項目，也可以包含由開發(fā)團隊聯(lián)合生成的多個項目。復雜的應(yīng)用程序可能需要多個解決方案。項目包含一組源文件以及相關(guān)的元數(shù)據(jù)，如組件參考和生成說明。生成項目時通常會生成一個或多個輸出文件。根據(jù)實際需要，項目可以簡單，也可以復雜。一個簡單的項目可能由一個窗體或HTML 文檔、源代碼文件和一個項目文件組成。更加復雜的項目可能由這些項以及數(shù)據(jù)庫腳本、存儲過程和對現(xiàn)有XML Web services的引用組成。創(chuàng)建新項目時， VS2010會自動生成一個解

25、決方案。 然后，可以根據(jù)需要將其他項目添加到該解決方案中。也可以創(chuàng)建不包含項目的空白解決方案，從而使用VS2010 編輯器和設(shè)計器修改獨立的文件。因為每個項目或解決方案都由一個目錄及其內(nèi)容組成，所以，可以在 Windows 資源管理器中移動、復制或刪除解決方案和項目。VS2010將解決方案的定義存儲在兩個文件中，即.sln和 .suo 。這兩個文件相當于早期版本中的工作區(qū)文件(.dsw)。解決方案定義文件(.sln)存儲定義解決方案的元數(shù)據(jù)，每當解決方案活動時，都使用構(gòu)建該解決方案并設(shè)置其屬性時存儲在.suo文件中的元數(shù)據(jù)來自定義IDE 。73.1.1新建項目為了調(diào)試本設(shè)計所要求的程序， 首先

26、啟動 VS2010，然后依次選中文件菜單中的新建、項目命令，打開如圖 3.1.1-1 所示的新建項目對話框。圖 3.1.1-1新建項目對話框在該對話框中，選中左邊 Visual C+下面的 Win32，在右邊選中 Win32 控制臺應(yīng)用程序。然后在名稱框中輸入項目名稱。 這里設(shè)定項目名稱為 rfft ，并設(shè)定項目存放的位置為 E 盤。注意，一旦設(shè)定項目名稱后，解決方案的名稱默認與項目名稱相同。單擊確定按鈕，在后面出現(xiàn)的個對話框中都選默認值，在應(yīng)用程序設(shè)置對話框中確保選中“空項目”，之后，即可創(chuàng)建項目 rfft ，同時創(chuàng)建一個同名的解決方案?，F(xiàn)在打開 E 盤，可以看到一個rfft文件夾，其中有一

27、個rfft.sln文件，代表解決方案，同時還有一個rfft子文件，其中有一個文件rfft.vcxproj，代表 rfft項目。3.1.2新建文件為了編輯源程序代碼，在VS2010的文件菜單中選中新建、文件命令，在彈出的新建文件對話框中選中Visual C+、C+文件。單擊打開按鈕后，可以看到在VS2010的工作窗口中出現(xiàn)一個新文件“源1.cpp ”。選中菜單中的另存為命令，將其重新保存為C8語言源程序文件， 這里命名為 rfft.c ，用于新建實序列FFT算法子程序。 注意在另存為對話框中一定要選中 C源程序選項，并找到文件夾 rfft，將文件保存到該文件中。重復上述步驟，再新建一個C語言源程

28、序文件，命名為 mrfft.c ，該文件是主程序文件，用于調(diào)用 rfft.c文件中定義的 rfft 函數(shù)，計算實序列的N點。DFT分別在 mrfft.c 和 rfft.c文件中編輯實序列 FFT算法的子程序和主程序，之后，為了將文件添加到項目中，在VS2010工作窗口左邊的解決方案資源管理器中右鍵單擊項目名稱 rfft ，在彈出的菜單中依次選中添加、現(xiàn)有項命令，找到剛才創(chuàng)建的文件 mrfft.c ，單擊添加按鈕，將其添加到項目和解決方案中。將主程序文件添加到解決方案后，通過生成菜單中的解決方案命令，對程序進行編譯連接。如果沒有錯誤，則生成解決方案，并在rfft文件夾下自動生成一個Debug文件

29、夾，可以看到其中有一個看到其中有一個rfft.exe文件。此時， VS2010窗口中的解決方案資源管理器如圖3.1.2-1所示。項目 rfft下面的 mrfft.c文件是手動加入的，而外部依賴項下面的所有文件（包括子程序文件rfft.c）是通過編譯連接自動加入的。圖 3.1.2-1解決方案資源管理器3.2實序列 FFT算法子程序根據(jù)上述原理編制的實序列FFT 算法子程序參見附錄1。程序中，首先將輸入序列進行倒序排列，然后進行各級蝶形運算。93.2.1倒序由 FFT的運算流圖可知，在進行 FFT運算之前，首先需要將按自然順序送入的輸入序列按照一定的順序排好。 例如，對 N=8點 FFT，原始輸入

30、序列 x(0) 、x(1) 、x(2) 、 、x(7) ，計算時的順序應(yīng)為 x(0) 、x(4) 、x(2) 、 、 x(7) 。這一操作稱為倒序。以 8 點 FFT為例，輸入序列序號的自然順序和倒序如表3.2.1-1所示。表 3.2.1-1順序和倒序?qū)φ毡眄樞虻剐蚴M制二進制十進制二進制0000000010014100201020103011611041001001510151016110301171117111由表 3.2.1-1可知，自然順序序號加1，是在其二進制數(shù)最低位加1，并逢 2 向高位進 1。而倒序序號是在其對應(yīng)的二進制數(shù)最高位加1，逢 2 向低位進位。對于 N=2M，M位二進制

31、數(shù)各位的權(quán)值從左向右依次為 N/2、 N/4、 、 2、 1。因此，在最高位加 1，相當于加 N/2。如果最高位為 0，即序號小于 N/2，則直接加 N/2 得到下一個倒敘序號；否則，先將最高位變?yōu)?0，然后次高位加 1，相當于加 N/4。在次高位加 1 時，同樣需要判斷該位是 0 還是 1，再用同樣的方法進行加 1 運算。依此類推，直到完成最高位加 1，逢 2 向低位進位的運算。形成倒序序號后，將輸入序列x(n) 重新按倒序排列。實現(xiàn)倒序的程序框圖如圖3.2.1-1所示。根據(jù)上述框圖編制的實現(xiàn)倒序的程序代碼如下：10n1N-1i=0:N-1Nij?Yx(i) 和 x(j) 交換kN/2kj+

32、1?Yjj-kkk/2Nj j+k圖 3.2.1-1倒序程序框圖n1=n-1;for(j=0,i=0;in1;i+) if(ij) xtmp=xj;xj=xi;xi=xtmp;k=n/2;while(k(j+1) j=j-k; k=k/2;j=j+k;11代碼中， i 和 j 分別為自然序號和倒序序號，設(shè)置i 從 0 到 N-1，共循環(huán) N 次。在每次循環(huán)中，當ij時，將 x(i)和 x(j)交換，否則不交換。代碼中之后的while循環(huán)語句用于實現(xiàn)倒序值j 的計算，以便下次循環(huán)實現(xiàn)相應(yīng)一對數(shù)據(jù)的交換。3.2.2蝶形運算將輸入序列倒序后，進行各級蝶形運算。程序中首先用如下語句：for(j=1,i

33、=1;i16;i+) m=i;j=2*j;if(j=n) break;求得 N點 FFT蝶形運算的級數(shù)。 之后，進行第一級蝶形運算， 再用 k 控制共循環(huán) m-1 次，依次進行后面各級蝶形運算。由 FFT 算法的運算流圖可知，對第一級中的每個蝶形運算，旋轉(zhuǎn)因子都為WN0 =1。再考慮到輸入序列各點都是實數(shù)，因此將序列中相鄰每兩輸入數(shù)據(jù)直接相加減，即得到第一級各蝶形的輸出。相應(yīng)的代碼如下：for(i=0;in;i+=2) xtmp=xi; xi=xtmp+xi+1;xi+1=xtmp-xi+1;在后面各級蝶形運算中， 由運算流圖可知， 有些蝶形所需的旋轉(zhuǎn)因子仍然為WN0 =1。對這些旋轉(zhuǎn)因子對應(yīng)

34、的蝶形運算，同樣化簡為將其兩個輸入數(shù)據(jù)直接相加減，以得到該蝶形的兩個輸出。實現(xiàn)這一運算的主要代碼如下：xtmp=xi;xi=xtmp+xi+n2;xi+n2=xtmp-xi+n2;其中， n2=2k-1 ， k=2m。例如，對第二級蝶形， k=2，則 n2=2。因此利用以上三條語句將第二級蝶形中 WN0 對應(yīng)的各蝶形運算的輸入輸出直接加減，結(jié)果再放回原單元。對第三12級蝶形， k=3，則 n2=4。利用以上三條語句將第三級蝶形中WN0 對應(yīng)的各蝶形運算的輸入輸出直接加減，結(jié)果再放回原單元。對 8 點 FFT，第二級有兩個這樣的蝶形，第三級有一個這樣的蝶形。程序中用 i 和 n1 控制，其中 n

35、1=2k， i 每次循環(huán)遞增 n1。對第二級， n1=4，則每次循環(huán) i 從 0 到 7 遞增 4，因此上述三條語句共執(zhí)行2 次，實現(xiàn)的運算是：x(0)=x(0)+x(2);x(2)=x(0)-x(2)x(4)=x(4)+x(6);x(6)=x(4)-x(6)對第三級， n1=8，因此上述語句只執(zhí)行1 次，實現(xiàn)的運算是：x(0)=x(0)+x(4);x(4)=x(0)-x(4)程序中還有如下語句：xi+n2+n4=-xi+n2+n4;該語句的作用是將蝶形運算中的某些數(shù)據(jù)直接取負。例如，對8 點 FFT，在進行第二級運算時，將 x(3) 和 x(7) 取負；在進行第三級運算時，將x(6) 取負。

36、后面將解釋為什么要這樣做。程序中后面的語句用于執(zhí)行旋轉(zhuǎn)因子不為WN0 時對應(yīng)的其它蝶形運算。用j 控制從1（n4-1 ），共循環(huán) n4-1 次，其中 n4=2k-2 。對第二級， n4=1，因此該循環(huán)一次也不執(zhí)行。對第三級， n4=2，因此該循環(huán)執(zhí)行1 次。為了解釋該循環(huán)中各語句的功能，以8 點 FFT為例，推導第三級蝶形運算的輸出結(jié)1果。以旋轉(zhuǎn)因子WN 對應(yīng)的蝶形為例，該蝶形中的一個輸出為X 3 (1)X 2 (1)WN1 X 2 (5)（3.2.2-1 ）其中下標 2 和 3 分別代表第 2 和第 3 級蝶形的輸出。根據(jù)運算流圖，第2 級的輸出中，有X2(1)X1 (1)WN2 X1(3)X2(5)X 1(5)WN2 X1(7)將以上兩式代入式（ 3.2.2-1 ）得到X 3(1)X1(1)WN2 X1 (3)WN1 X 1(5)WN2 X1 (7)2 其中， WN2W82-j2e 8=-j ，則13X 3 (1) X1 (1) jX1 (3)WN1 X1(5)jX1(7)（3.2.2-2）上式中，第一級蝶形的輸出X1(1)、X1、X1(5)和 X1(7)都是由原序列通過直接加(3)減得到的，因此都為實數(shù)。由此得到第三級的輸出中，X3(1) 的實部和虛部分別為X3r (1)X1(1)C1X1(5) S1X1(7)（3.2.