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