[信息與通信]fft原理(編輯修改稿)
2025-01-03 22:46 本頁面
【文章內(nèi)容簡介】 / 2 1 10 / 2/ 2 1 / 2 1()02( / 2 )0/ 2 10/22( ) ( ) ( )( ) ( )[ ( ) ( ) ]NNnk nkNNnnNkNNNnnkNNnnNnkNNknNNNX k x n W x n WWx n W x n Wx n x n W???????????????? ? ?? ? ??????/2 ( / 2 ) 1,1,1,( 1 )NN kkNN kWkW ?? ?? ? ?? ??為 數(shù)為 數(shù)偶奇 ?按 k的奇 、 偶把 X(k)進一步分解為兩部分： 2Nnn? ??令/ 2 10/ 2)( ) [ ( ) ( 1 ) ( ]Nk n kNnNX k x n x n W??? ? ? ??? ?/2/ 2 1202/ 2 10211 / 2 1202122()/2/ 2 ))( 2 ) [ ( ) ( ][ ( ) ( ]( ) ( )NNNNNnrnj nrNnrnNnrNNnNnr nrxnNNDFTX r x n x n Wx n x n Wx n W x nw e w????????? ? ???? ? ??????a) k為偶數(shù)，令 k=2r 2 10 , 1 , ...,Nr ??? ?/22/ 2 1( 2 1 )0// 2 102120222()/2/2[ ( ) ( ) ]( 2 1 ) [ ( ) ( ) ]( ) ( )nNNN NNnrNnNnrnNnrnnxNNx n x n WD F TX r x n x n WWx n W x n?????????? ? ????????b) k為奇數(shù)，令 k=2r+1 / 2 2/ 2 21 / 1/ 2 1 / 2001 / 1/ 2 2 / 200/2/2( 2 ) [ ( ) ( ) ] ( )( 2 1 ) { [ ( ) ( ) ] } ( )NNNNnr nrNNnnn nr nrN N NnnNNX r x n x n W x n WX r x n x n W W x n W?????????? ? ? ????? ? ? ? ? ???????2222 Nj n rNnrNnrw e w????按頻率抽取的蝶形運算流圖： 例：以 N=8 按頻率抽取的 FFT 把 8點 DFT分解成兩個 4點的 DFT K為偶數(shù) X(2r) K為奇數(shù) X(2r＋ 1) 將兩個 4點 DFT再分解成四個 2點 DFT 由于 N/2仍是偶數(shù)可以繼續(xù)分解，直到分解為兩兩點的 DFT為止。 下圖是 N=8按頻率抽取的 FFT流圖 頻率抽取法的分解過程： (1)把輸入序列前后對半分； (2)輸出按 k值的奇、偶將 X(k)分解為奇數(shù)組和偶數(shù)組兩部分； (3)輸入如果按順序輸入，輸出則是碼位倒置形式。 按頻率抽取法 FFT的運算特點： （ 1） 蝶形運算的運算量 其運算量與按時間抽取運算量相同 。 即： 復(fù)乘： 復(fù)加： （ 2） 輸入如果是自然順序 ， 輸出則是碼位倒置形式 。 如果要求輸出為自然順序 ， 則需要進行變址運算 。 按頻率抽取的 FFT流圖可以由按時域抽取的 FFT流圖轉(zhuǎn)置 而得到 。 轉(zhuǎn)置指將流圖中所有支路的方向反 ,并將輸入變輸出 ， 輸出變輸入 。 22 lo gFNMN?2l o gF NNa ?01800180 頻率抽取法的基本蝶形圖與時間抽取法的基本蝶形圖有所不同 。 時間抽取法是先乘后加 、 減 ，頻率抽取法是先加 、 減 ， 再乘系數(shù) nNW按頻率抽取的 蝶形運算流圖 按時間抽取的 蝶形運算流圖 按時間抽取的 FFT算法以及按頻率抽取的 FFT算法是DFT的兩種快速算法，這些算法同樣可以用於 IDFT，我們稱為快速傅立葉反變換 (IFFT)。我們把 IDFT公式與 DFT公式作以比較： 10( ) [ ( ) ] ( ) 0 1N nkNnX k D F T x n x n W k N??? ? ? ? ??101( ) [ ( ) ] ( ) 0 1N nkNkx n I D F T X k X k W n NN? ??? ? ? ? ??(1) DFT中的系數(shù) (2) IDFT中要乘以常數(shù) kn knNNWW ??11()2 MN ?167。 IDFT的快速算法 IFFT ??另外一種 IFFT算法的實現(xiàn) 10( ) [ ]( ) ( )NnnkNX k D F T x n x n w???? ?? ?110011( ) ( )1()()NNn k n kNNkkX k W X k WNNFFT X kNnx????????????? ??????? ???? 以上討論的時間抽取或頻率抽取的 FFT運算均可直接用于 IFFT運算。但需要將蝶形系數(shù) 改為 ，每級乘以系數(shù) 1/2 。 nkNWknNW?IFFT計算分為三步： ① 將 X(k)取共軛 (虛部乘以 1) 。 ② 對 直接作 FFT ； ③ 對 FFT的結(jié)果取共軛并乘以 1/N，就得到 x(n)。 )(kX? 按上述方法求得的 IFFT，完全不需要改動FFT程序， FFT和 IFFT可以共用一個程序。 )(kX??總結(jié) FFT和 IFFT蝶形圖的表示方法： 按時間抽取的 FFT 變到 IFFT時，對應(yīng)的流圖應(yīng)該是按頻率抽取的 IFFT。因為： 按時間抽取的 FFT 輸入變量是 x(n) x(n)按奇、偶分解 按頻率抽取的 IFFT 輸入變量是 X(k) X(k)按奇、偶分解 同理，按頻率抽取的 FFT 變到 IFFT時，對應(yīng)的流圖應(yīng)該是按時間抽取的 IFFT。 （ 1）輸入按奇、偶分解： （ 2）輸入按前、后分解： (2 )(2 1)xrxr?偶奇(2 )(2 1)XrXr?偶奇2()()Nxnxn?2()()NXkXk?167。 任意基數(shù)的 FFT算法 前面討論的 FFT算法 ， 序列的長度均滿足 N=2M ，這種情況實際使用得最多 ， 因為它程序簡單 ， 效率 高 ， 使用方便 。 如果不滿足 N=2M, 處理方法有兩種 : ① 補零 : 將 x(n)補零 ,使 N增加到臨近的一個值 ， 滿足 N=2M 。 例如： N=30, 補上 x(30)=x(31)=0 兩個零點 , 使 得滿足 N=25=32, 這樣可直接調(diào)用以 2為基數(shù)的 FFT 運算 。 有限長序列補零后并不影響其頻譜 ， 補零只是頻譜的采樣點數(shù)增加了 。 ()jXe?② 如 ， 如果要求 N點 DFT值 ,幾乎要補一半 0值 (2044個 0)， 顯然用第一種方法處理很不經(jīng)濟 ， 因此 ， 如果要求求準確的 N點 DFT值 ,可采用任意基數(shù)的 FFT算法 ,但其運算效率低于以 2為基數(shù)的 FFT算法 。 ?任意基數(shù)的 FFT算法的基本思想 首先要求 N可以分解成因子乘積的形式 ， N不能是素數(shù) 。 任意基數(shù)的 FFT算法的基本思想仍是把一個大 N點的 FFT盡量分解為小點數(shù)的 FFT。 首先將 N分解為兩個整數(shù) p與 q的乘積 ,即： ， 其步驟為： 12205 2 , 2 409 6NN? ? ?(1)將序列 x(n)分成 p組 p組
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1