快速傅里葉變換-展示頁
2024-08-30 23:53本頁面
【正文】 0 )1()1()0()0( ???? ????? NNNN WNxWxWxX ?1k? 0 1 1 1 ( 1 ) 1( 1 ) ( 0 ) ( 1 ) ( 1 ) NN N NX x W x W x N W? ? ? ?? ? ? ? ?2k? 0 2 1 2 ( 1 ) 2( 2 ) ( 0 ) ( 1 ) ( 1 ) NN N NX x W x W x N W? ? ? ?? ? ? ? ?1?? Nk 0 1 1 1 ( 1 ) 1( 1 ) ( 0 ) ( 1 ) ( 1 )N N N NN N NX N x W x W x N W? ? ? ? ? ? ?? ? ? ? ? ?N次復(fù)乘， N1次復(fù)加 N個點 10)()]([)(10????? ???NkWnxnxD F TkXNnnkN以 DFT為例： 復(fù)數(shù)乘法 復(fù)數(shù)加法 一個 X(k) N N – 1 N個 X(k) (N點 DFT) N 2 N (N – 1) 實數(shù)乘法 實數(shù)加法 一次復(fù)乘 4 2 一次復(fù)加 2 一個 X (k) 4N 2N+2 (N – 1)=2 (2N – 1) N個 X (k) (N點 DFT) 4N 2 2N (2N – 1) 10()NnkNnx n W???運算量 (a+jb)(c+jd)=(acbd)+j(bc+ad) 例：計算一個 N點 DFT ， 共需 N2次復(fù)乘 。第四章 快速傅立葉變換 Fast Fourier Transform 第一節(jié) 直接計算 DFT的問題及改進途徑 問題的提出 設(shè)有限長序列 x(n)， 非零值長度為 N， 若對 x(n)進行一次 DFT運算，共需 多大的運算工作量 ？ 計算成本 ? 計算速度 ? 2. DFT的運算量 回憶 DFT和 IDFT的變換式： 10)(1)]([)(10????? ???? NnWkXNkXI D F TnxNknk10)()]([)(10????? ???NkWnxnxD F TkXNnnkN1） x(n)為 復(fù)數(shù) ， 也為 復(fù)數(shù) 。 2） DFT與 IDFT的 計算量相當(dāng)。以做一次 復(fù)乘 1μs計，若 N =4096， 所需時間為 ss 171 6 7 7 7 2 1 6)4 0 9 6( 2 ?? ?例：石油勘探，有 24個通道的記錄，每通道波形記 錄長度為 5秒，若每秒抽樣 500點 /秒， 1）每道總抽樣點數(shù)： 500*5=2500點 2） 24道總抽樣點數(shù)： 24*2500=6萬點 3） DFT復(fù)乘運算時間： N2=(60000)2=36*108次 ss 3 6 0 010*36)6 0 0 0 0( 82 ?? ? 由于計算量大，且要求 相當(dāng)大的內(nèi)存 ， 難以實現(xiàn)實時處理 ，限制了 DFT的應(yīng)用。 FFT便是 Cooley amp。 第二節(jié) 改善 DFT運算效率的基本途徑 knNW 利用 DFT運算的系數(shù) 的固有對稱性和周期 性，改善 DFT的運算效率。 N點 DFT N/2點 DFT N/2點 DFT N/4點 DFT N/4點 DFT N/4點 DFT N/4點 DFT ……. 復(fù)乘： 2N 2222 ????????????? NN22N22224444 ??????????????????????????? NNNN42N FFT算法的基本思想： ? 利用 DFT系數(shù)的特性，合并 DFT運算中的某些項 ? 把長序列 DFT→ 短序列 DFT， 從而減少運算量。也稱為 CoolkeyTukey算法。 先將 x(n)按 n的奇偶分為兩組，作變量置換 : 當(dāng) n=偶數(shù)時，令 n=2r。 ? 分組，變量置換 算法步驟 10)()]([)(10????? ???NkWnxnxD F TkXNnnkN得到： 1,...,0)()12( )()2( 221 ???????? Nrrxrxrxrx? 帶入 DFT中 ?????10)()]([)(NnnkNWnxnxD F TkX??????????12/0)12(12/02 )12()2(NrkrNNrrkN WrxWrx????????1010)()(NnnkNNnnkNnnWnxWnx為奇數(shù)為偶數(shù)????????12/02212/021 )()(NrrkNkNNrrkN WrxWWrx所以 ????????12/02212/021 )()()(NrrkNkNNrrkN WrxWWrxkX由于 nNnNjnNjnN WeeW 2/2/2222 ????? －－????????12/02/212/02/1 )()(NrrkNkNNrrkN WrxWWrx)()( 21 kXWkX kN??1,1,0 2 ?? Nk ?1,1,0 ?? Nk ? ? 12 ?N? X1(k)、 X2(k)只有 N/2個點，以 N/2為周期；而 X (k)卻有 N個點，以 N為周期。 rkNkNrN WW 2/)2/( 2/ ?????????? ????12/02/112/0)2/(2/11 )()()2/(NrrkNNrkNrN WrxWrxkNX????????)()2/()()2/(2211kXkNXkXkNX后半部分 前半部分 又考慮到 的對稱性： kNWkNkNNNkNN WWWW ????? 2/)2/()2/()2/()2/( 2)2/(1 kNXWkNXkNX kNN ????? ?有： 1,
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1