基于位倒序?qū)ぶ贩絧pt課件(編輯修改稿)
2025-06-06 23:43 本頁面
【文章內(nèi)容簡介】 ? ? FFT算法的運算量與運算特點 ? FFT算法 ? ? ? 離散傅里葉的計算工作量 ???? ???101,1,0 ,)(1)(NknkN NnWkXNnx ?1,1,0 ,)()(10??? ???NkWnxkXNnnkN ?? 通常 X(k), 都是復數(shù)，所以計算一個 X(k)的值需要 N次復數(shù)乘法運算，和 N1次復數(shù)加法運算，那么所有的 X(k)就要 NxN復數(shù)乘法運算， N(N1)復數(shù)加法運算，當 N很大時，計算量就相當驚人，如果當 N=1024時，則要完成 1048576次運算這樣難易做到實時處理。 nkNW? 改進途徑，利用 的周期性和對稱性 nkNW。,)()()(*NknNkNnNnkNnkNnkNWWWWW?????? FFT算法 ? ? 一． 算法原理基于 (2FFT) ? N/2點的 DFT，先將 x(n)按 n的奇偶分成兩組 DFT，不足時補零 ? 這樣 就有： N為偶數(shù)時： N為奇數(shù)時： 1,1,0 ),()12( 1,1,0 ),()2(2221???????NNrrxrxrrxrx???????10)()]([)(NnnkNWnxnxD F TkX????? ?????????????????????1022102110)12(10210102222))(())(()12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX? 由于 ? 所以可表示為 222 )/(222NNN WeeW jjN ?????? ??)()()()()( 211021012222kXWkXWrxWWrxkX kNrrkkNrrkNNNN ???? ??????? X(k)的后一半的確定 rkkrNNN WW222)( ??)()()()2( 1101)(101122222kXWrxWrxkNXNNNNNrrkkrr???? ???????kNkNNkN WWWWNN ????22 )(1,1,0 ),()( 221 ???? NkN kkXWkX ?)2()2()2( 21 2 NkXWNkXNkXNkN ??????蝶形運算 ? 蝶形運算 ( 1 1 1 1 1 )()()( 21 kXWkXk
環(huán)評公示相關推薦
鄂ICP備17016276號-1