【文章內(nèi)容簡介】 ： x1(r)=x(2r), r=0,1,… ,N/2 – 1 x2(r)=x(2r+1), r=0,1,… ,N/2 – 1 則 x(n)的離散傅里葉變換為： ?? ?? ?? 奇數(shù)偶數(shù) n knNn knN WnxWnxkX )()()( ?? ?? ??? ??? 12/ 0 )12(12/ 0 2 )12()2( N r rkNN r krN WrxWrx krNNrkNkrNNr WrxWWrx212/0 2212/0 1 )()( ?????? ?? 東華理工大學(xué)畢業(yè)設(shè)計 數(shù)字頻譜分析儀的原理 分析 6 krNNrkNkrNNr WrxWWrx 2/12/0 22/12/0 1 )()( ?????? ?? )()()( 21 kXWkXkX kN?? k=0,1,… ,N/2 – 1 并且 X1(k)和 X2(k)都是以 N/2為周期 = )2()2()2( 221 NkXWNkXNkXNkN ????? ? = )()()2( 21 kXWkXNkX kN??? k=0,1,… ,N/2 – 1 其中公式 ??????????)()()2()()()(2121kXWkXNkXkXWkXkXkNkN是一個蝶形運算 同理，可推出： ??????????)()()4()()()(42/3142/31kXWkXNkXkXWkXkXkNkN ， k=0,1,… ,N/4 1 ??????????)()()4()()()(62/5262/52kXWkXNkXkXWkXkXkNkN ， k=0,1,… ,N/4 – 1 …… 分解到最后時，另 k=0時，就只有開始時序列 x（ n）中的兩個輸入來進(jìn)行蝶形運算。 蝶形分解圖 如 圖 22所示： 圖 22 N / 4 點D F TN / 4 點D F TN / 4 點D F TN / 4 點D F Tx ( 0 )x ( 4 )x ( 2 )x ( 6 )x ( 1 )x ( 5 )x ( 3 )x ( 7 )X ( 0 )X ( 1 )X ( 2 )X ( 3 )X ( 4 )X ( 5 )X ( 6 )X ( 7 )W N / 20W N / 21W N / 20W N / 21W N0W N1W N2W N3X 3 ( 0 )X 3 ( 1 )X 4 ( 0 )X 4 ( 1 )X 1 ( 0 )X 1 ( 1 )X 1 ( 2 )X 1 ( 3 )X 2 ( 0 )X 2 ( 3 )X 2 ( 2 )X 2 ( 1 )東華理工大學(xué)畢業(yè)設(shè)計 數(shù)字頻譜分析儀的原理 分析 7 如果存進(jìn)數(shù)組 X 中的序列 x(n)已經(jīng)被時域倒序抽選，設(shè)蝶形運算中的兩個輸入有B個間距，且計算結(jié)果還存放在數(shù)組的原來的位置，那么通過該方法可以來計算蝶形運算，則可表示成如下形式： ??????????????????pNLLLpNLLLWBJXJXBJXWBJXJXJX)()()()()()(1111 ??)2(1 = ??????????)()()2()()()(2121kXWkXNkXkXWkXkXkNkN 其中： p=J*2ML。 J=0,1,… ,2L11； L=1,2,… ,M 下標(biāo) L表示第 L級運算， XL(J)則表示第 L 級運算后數(shù)組元素 X(J)的值。 圖 23 蝶形運算分解圖 上圖中 A 和 B 表示蝶形運算的輸入，他們的值為 X(n)（ n= 0,1,N1）中某一個， C為 kNW2/ 或者是 kNW2/ 。如圖 24表示 N=8點的 FFT運算圖示 。 圖 24 8點 FFT流程圖 上圖可以看出 ： 第一級中，每個蝶形的兩個輸入相距 1 個點；有 4個不同的旋轉(zhuǎn)因子，同一旋轉(zhuǎn)因子對應(yīng)著間隔 4點的 1個蝶形 。 第二級中，每個蝶形的兩個輸入相距 2 個點，有 2個不同的旋轉(zhuǎn)因子，同一旋轉(zhuǎn)因子對應(yīng) 2個相距為 2的 2個蝶形 。 第三級中，每個楔形的輸入相距 1 個點，有 1個不同的旋轉(zhuǎn)因子，同一旋轉(zhuǎn)因子對應(yīng) 4個相距為 1的 4個蝶形。AB CA + B CA B C東華理工大學(xué)畢業(yè)設(shè)計 理論分析 8 第 3 章 理論分析 FFT 原理分析 離散傅里葉變換可以得出有限的長序列 x（ n）和它的頻域表示 x（ k） ? ? 1k0nx)n(x)( nk10n NWD F TkX N ??? ??? ，）（ () ? ? 1n0k1)k()n(x nk10n NWXNXID F T N ???? ??? ，）（ () 其中 NkjNW ?2nk e?? 。式（ ）叫做離散傅立葉正變換，式（ ）叫做離散傅立葉反變換， x（ n）與 X（ k）構(gòu)成了一對離散傅立葉變換對。 根據(jù)上面的公式，計算一個 X（ k），需要進(jìn)行 N1次復(fù)數(shù)加法和 N次復(fù)數(shù)乘法。但是計算全部的 X（ k）（ 0≤ k≤ N1），一共需要 N(N1)次復(fù)數(shù)加法和 N2次復(fù)數(shù)乘法?？梢酝ㄟ^兩次實數(shù)加法和四次實數(shù)乘法來完成一次復(fù)數(shù)乘法，完成一次復(fù)數(shù)加法要兩次實數(shù)加法，因 此直接計算全部的 X（ k）一共需要 （ 4N2）次 實數(shù) 相加和 4N次實數(shù)相乘 。當(dāng) N個 k值 時 ，共需 N（ 4N2）次實數(shù)相加和 N*N次實數(shù)相 乘。，利用 DFT中 WNnk的對稱性和周期性， 可以 改進(jìn) DFT算法 并 減小它的運算量 ， 使整個 DFT計算變 為 一系列 的 迭代 運算， 還 可 以 大幅度提高運算 量 和運算 過程 ， 但當(dāng) N值很大時，計算一個 N點的 DFT要進(jìn)行 N(N1)次復(fù)數(shù)加法與 N2次復(fù)數(shù)乘法。這時計算量就顯得很大了。 FFT的基本思想 就是這些。 FFT大致 上可分 成 兩類，時間抽取法和頻率抽取法 。時間抽取法是將時域信號序列按奇偶分排，而頻域抽取法是將頻域信號按奇偶分排。下面就基 2時間抽取 FFT算法進(jìn)行介紹。 假如序列 x（ n）的長度是 N=2M，且 M是整數(shù)（如果沒有滿足條件可以人為的增補 零值點來得到），為了使最小 DFT運算單元是 2點可以在時域上進(jìn)行奇偶抽取分解成短序列的 DFT。一般來說將 FFT運算當(dāng)中最小的 DFT運算單元稱為基，所以把這種算法叫做基 2時間抽取 FFT（ DITFFT）算法。 把 x（ n）按 n 是奇或偶來分解成兩個子序列，當(dāng) n 是偶數(shù)時，令 n=2r；當(dāng) n 是奇數(shù)時，令 n=2r+1；可得到 x(2r)=x1(r)， x(2r+1)=x2(r)， 1， ......， (N/2)1 則其 DFT 可寫成 東華理工大學(xué)畢業(yè)設(shè)計 理論分析 9 )()()12()r2(x)r(x)r2(x1r2(x)2()k(211)2(021)2(0r1)2(0rrk21 ) kr2(21)2(0rnk211)2(0r)12(nk21)2(0rkXWkXWrxWWWWWrxXkNNrrkNN NNNNNNkrNNN???????????? ??????? ??????） （ ） X1(k)和 X2(k)分別是 N/2 點序列 X1(n)和 X2n)的 DFT， r 和 k 的取值符合 0， 1...，(N/2)1，而 X（ k）是一個 N 點的 DFT，所以式 （ ） 只計算了 X（ k）的前 N/2 的值。由 WNn和 kDFT 的性質(zhì)可以得到 X（ k）后面 N/2 的值 )k()k()2k()2k()2k( 2k122k1 WWXNXWNXNX NNN ?????? ? （ ） 式 ()和式 ()表明，只要計算 出兩個 N/2點的 X2(k) 和 DFT X1(k),通過線性組合，就可以得到全部 N 點的 X（ k）。因為 N=2M，且 N/2=2M1仍是偶數(shù)，所以這樣的分解可以繼續(xù)進(jìn)行下去，當(dāng)最后的單元只需要做 2點 DFT時就可以結(jié)束。 若 )p(mX 和 )q(mX 是輸入數(shù)據(jù)， )p(1m?X 和 )q(1m?X 是輸出數(shù)據(jù)， kNW 是旋轉(zhuǎn)因子，則對于基 2DITDFT 算法，蝶形運算的基本公式如下 kmm1mkmm1m)q()p()p( )q()p()p( NNWXXX WXXX ?? ???? （ ） 其圖形表示如圖 21所示，稱 Xm(p)叫做上結(jié)點， Xm(q)叫做下結(jié)點。 Xm(p) Xm+1(p) Xm(q) WNp Xm+1(q) 1 圖 31 時間抽取蝶形運算單元 用 FFT 變換進(jìn)行頻譜分析 要實現(xiàn) FFT 算法的是否可行，下面舉一個例子說明，先假設(shè)兩個正弦波信號來進(jìn)行采樣，一個設(shè)為 f1=50Hz，另一個就 設(shè)為 f2=200Hz，另外增加一個 高斯白 噪聲。先將最大為 f=1kHz 的輸入信號進(jìn)行采樣，并對 N=2的 10次方個點的做 FFT 分析和處理。通過 Matlab 軟件來進(jìn)行編程與仿真，就可以 得到 采樣信號的時域波形（如圖 1所示）以及頻譜分析曲線（如圖 32所 示）。 東華理工大學(xué)畢業(yè)設(shè)計 理論分析 10 圖 32 信號的時域波形 圖 33 FFT 頻譜分析結(jié)果 由圖 33分析可知，當(dāng)頻率在 f1和 f2的時候，波形信號才顯著，而其它頻率幾乎東華理工大學(xué)畢業(yè)設(shè)計 理論分析 11 沒有顯著波動，波形不明顯 ， 那是因為由 高斯白 噪聲 的 干擾所 導(dǎo)致的 。由此可以說明FFT算法是合理的。 波形