5線(xiàn)性卷積的fft算法(已修改)
2024-10-16 10:00 本頁(yè)面
【正文】 5. 線(xiàn)性卷積的 FFT算法 3. 頻率抽選 (DIF)基 2 FFT算法 2. 時(shí)間抽選 (DIT)基 2 FFT算法 1. 引言 引言 一 . DFT的計(jì)算量 兩者的差別僅在指數(shù)的符號(hào)和因子 1/N. 1,1,0 ,)()(10??? ???NkWnxkXNnnkN ????? ???101,1,0 ,)(1)(NknkN NnWkXNnx ? 通常 x(n)和 都是復(fù)數(shù) ,所以計(jì)算一個(gè) X(k)的值需要 N次復(fù)數(shù)乘法運(yùn)算 ,和 次 復(fù)數(shù)加法運(yùn)算 .那么 ,所有的 X(k)就要 N2次復(fù) 數(shù)乘法運(yùn)算 ,N(N1)次復(fù)數(shù)加法運(yùn)算 .當(dāng) N很 大時(shí) ,運(yùn)算量將是驚人的 ,如 N=1024,則要完 成 1048576 次 (一百多萬(wàn)次 )運(yùn)算 .這樣 ,難以做到實(shí)時(shí)處理 . nkNW1?N一個(gè) X(k)的值的計(jì)算量 ,如 X(1) 1210 )1()2()1()0()1( ??????? NNNNN WNxWxWxWxX ?二 .改進(jìn)的途徑 1. 的對(duì)稱(chēng)性和周期性 nkNW。)()()()(**NknNkNnNnkNkNNkNkNkNWWWWWorWW????????.),1(1),1()2/(2/)(2)()(2kNNkNjNNNnkNnNNkNnkNknNNkNnNWWeWWeWWWWWN??????????????????????得 : 對(duì)稱(chēng)性 : 周期性 : 利用上述特性 ,可以將有些項(xiàng)合并 ,并 將 DFT分解為短序列 ,從而降低運(yùn)算次數(shù) ,提 高運(yùn)算速度 .1965年 ,庫(kù)利 (cooley)和圖基 (Tukey)首先提出 FFT算法 .對(duì)于 N點(diǎn) DFT,僅需 (N/2)log2N 次復(fù)數(shù)乘法運(yùn)算 .例如 N=1024=210 時(shí)， 需要 (1024/2)log2 210 =512*10=5120次。 5120/1048576=% ,速度提高 20倍 時(shí)間抽選 (DIT)基 2 FFT算法 — 庫(kù)利 圖基算法 一 .算法原理 (基 2FFT) (一 )N/2點(diǎn) DFT 按 n的奇偶分為兩組作 DFT,設(shè) N=2L ,不足時(shí) ,可補(bǔ)些零。這樣有 : n為偶數(shù)時(shí) : n為奇數(shù)時(shí) : 1,1,0 ),()12(1,1,0 ),()2(2221???????NNrrxrxrrxrx???????10)()]([)(NnnkNWnxnxD F TkX因此， )(nx由于 : 所以 ,上式可表示為 : ????? ?????????????????????1022102110)12(10210102222))(())(()12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX(n為偶數(shù) ) (n為奇數(shù) ) 222 )/(222 NNN WeeW jjN ??? ??? ??)()()()()( 211021012222kXWkXWrxWWrxkX kNrrkkNrrkNNNN ???? ?????? 其中 , : (1) X (k),X (k)均為 N/2點(diǎn)的 DFT。 (2) X(k)=X (k)+W X (k)只能確定出 X(k)的 k= 個(gè)； 即 前一半 的結(jié)果。 1 2 1 2 k N ?????????????????10102210101122222222)12()()()2()()(NNNNNNNNrrkrrkrrkrrkWrxWrxkXWrxWrxkX1,1,0 2 ?N? 同理 , 這就是說(shuō) ,X1(k),X2(k)的后一半 ,分別 等于其前一半的值。 (k)的后一半的確定 rkkrNNN WW 222)( ??)()()()2( 1101)(101122222kXWrxWrxkNXNNNNNrrkkrr???? ???????由于 （周期性） ,所以 : )()2( 22 kXkNX ?? 可 見(jiàn) ,X(k)的后一半，也完全由 X1(k), X2 (k)的前一半所確定。 *N點(diǎn)的 DFT可由兩個(gè) N/2點(diǎn)的 DFT來(lái)計(jì)算。 kNkNNkN WWWW NN ???? 22 )()2()2()2( 21 2 NkXWNkXNkXNkN ??????1,1,0 ),()( 221 ???? NkN kkXWkX ?又由于 ,所以 實(shí)現(xiàn)上式運(yùn)算的流圖稱(chēng)作蝶形運(yùn)算 前一半 后一半 （ N/2個(gè)蝶形 ) (前一半 ) (后一半 ) 1 1 1 1 1 )()()()()()(2121kXWkXkXkXWkXkXkNkN????)1,()1,1,0(22????NkkNN??)()()( 21 kXWkXkX kN??)()()2( 21 kXWkXkNX kN???)(1 kX)(2 kXkNW由 X1(k)、 X 2(k)表示 X(k)的運(yùn)算是一種特殊的運(yùn)算 碟形運(yùn)算 (1)N/2點(diǎn)的 DFT運(yùn)算量 :復(fù)乘次數(shù) : 復(fù)加次數(shù) : (2)兩個(gè) N/2點(diǎn)的 DFT運(yùn)算量 :復(fù)乘次數(shù) : 復(fù)加次數(shù) : (3)N/2個(gè)蝶形運(yùn)算的運(yùn)算量 :復(fù)乘次數(shù) : 復(fù)加次數(shù) : 復(fù)乘 : 復(fù)加 : 4)2(22 NN ?)12(2 ?NN22N)12( ?NN2NNN ?? 222)12(2NNNN ???22222 NNN ??總共運(yùn)算量 : 按奇、偶分組后的計(jì)算量： *但是 ,N點(diǎn) DFT的復(fù)乘為 N2 。復(fù)加 N(N1)。與 分解后相比可知 ,計(jì)算工作點(diǎn)差不多減少 一半 。 例如 N=8 時(shí)的 DFT,可以分解為兩個(gè) N/2=4點(diǎn)的 : (1)n為偶數(shù)時(shí) ,即 分別記作 : )(42/ 1 kXD F TN ，得點(diǎn)的進(jìn)行 ?3,2,1,0)2()()(30430411??? ????kWrxWrxkXrrkrrk)。6()3(),4()2(),2()1(),0()0(1111xxxxxxxx????)。6(),4(),2(),0( xxxx (2) n為奇數(shù)時(shí) ,分別記作 : )。7()3(),5()2(),3()1(),1()0(2222xxxxxxxx????3,2,1,0)12()()(30430422???? ????kWrxWrxkXrrkrrk)(42/ 2 kXD F TN ，得點(diǎn)的進(jìn)行 ?3,2,1,0),()()4()()()(2121??????kkXWkXkXkXWkXkXkNkN(3)對(duì) X(k)和 X (k)進(jìn)行蝶形運(yùn)算 ,前半部為 X(0) X(3),后半部分為 X(4) X(7) 整個(gè)過(guò)程如下圖所示 : x1(0)=x(0)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1