chap4快速傅立葉變換fft-全文預(yù)覽
【正文】 M個(gè) L點(diǎn)的 DFT ? ? ? ? 0111 0 0 0 00, , 0 , 1 , , 1L kLnX k n x n W k L??? ? ?? 1n1n N點(diǎn)的新序列 ? ? ? ? 0039。 N為復(fù)合數(shù)的 FFT算法（續(xù)） 說(shuō)明： 1. ? ? ? ?0111 0 0 0 00, , 0 , 1 , , 1L kLnX k n x n W k L??? ? ?? 1n1n表示將 作為參變量，對(duì) 0n ? ?0,xn1n做 與 之間的 L 1n 0k點(diǎn) DFT，共有 M個(gè)（ ）即：對(duì) x(n)的每一列（ ）做 L點(diǎn) DFT，最后得到 M點(diǎn) DFT. 0 1, 2 , , 1nM??0 1, 2 , , 1nM??2. ? ? ? ?? ? 1001 39。 N為復(fù)合數(shù)的 FFT算法（續(xù)） 同理：對(duì)于 X(k)， k也可以表示成矩陣形式 ? ?10100 , 1 , , 1 ,0 , 1 , , 1 ,k M k k x nkMkL??????將 序 列 的 序 號(hào) 用 矩 陣 表 示表 示 列 號(hào)表 示 行 號(hào)（與 n表示相反） 01012 4 3430 ,1, 2 , 30 ,1, 2NMLkkk? ? ??????1則 ：k=3k例： 1k0kn 0 1 2 3 0 1 2 0 1 2 3 4 5 6 7 8 9 10 11 167。 利用 FFT的基本思想：將大點(diǎn)數(shù) DFT的運(yùn)算盡量分解為小點(diǎn)數(shù)的運(yùn)算，提高運(yùn)算效率。 （ DIF）的 FFT算法（續(xù)） 可見(jiàn)，一個(gè)按頻率抽取地 FFT流圖能夠?qū)崿F(xiàn)按 時(shí)間抽取地 IFFT流圖，同理一個(gè)按時(shí)間抽取的 FFT流圖可以實(shí)現(xiàn)按頻率抽取地 IFFT流圖。 （ DIF）的 FFT算法（續(xù)） 三、 IDFT FFT算法 ——IFFT ? ? ? ? ? ? ? ?1101 ,NN k n k nNNk n ox n X k W X k x n WN?????????兩式相比， 相差一個(gè)負(fù)號(hào)，系數(shù)相差 ， 故：可用 FFT流圖計(jì)算 IFFT。 ? 兩種算法的蝶形運(yùn)算存在差異， W因子相乘的位置不同。 （ DIF）的 FFT算法（續(xù)） 可見(jiàn)： 一個(gè) N=8點(diǎn)的 DFT經(jīng)三級(jí)（ N=23）分解后，變?yōu)? 計(jì)算兩點(diǎn)的 DFT，而這兩點(diǎn)的 DFT實(shí)際上只有加 減運(yùn)算，在每一級(jí)運(yùn)算中，都有 N/2個(gè)蝶形參加 運(yùn)算，其運(yùn)算量同 DIT FFT。 （ DIF）的 FFT算法（續(xù)） 以 N=8為例， DIF FFT算法流圖如下： 先蝶形運(yùn)算，后 FFT： 167。 （ DIF）的 FFT算法（續(xù)） 考慮兩種情況： ? 當(dāng)取偶數(shù)時(shí)： k＝ 2r r=0,1,…,N/2 1 ? 當(dāng)取奇數(shù)時(shí)： k＝ 2r＋ 1 r=0,1,…,N/2 1 ? ? ? ? ? ? ? ?112222002 22NNrn rnNNnnNNX k X r x n x n W x n x n W????? ? ? ?? ? ? ?? ? ? ? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ???? ? ? ? ? ? ? ? ? ?11222120021 22NNrn n rnN N NnnNNX k X r x n x n W x n x n W W?? ???? ? ? ?? ? ? ?? ? ? ? ? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ???令： ? ? ? ?? ? ? ?1222nNNx n x n x nNx n x n x n W??? ? ?????????? ? ?????????則： ? ? ? ?? ? ? ?2112021220221NnrNnNnrNnX r x n WX r x n W?????????r=0,1,2,… ,N/21 可見(jiàn)，上兩式均為 N/2點(diǎn) DFT 167。 FFT算法（續(xù)） 直接計(jì)算與 FFT方法，乘法運(yùn)算比較曲線 167。 參加蝶形運(yùn)算兩點(diǎn)間的距離規(guī)律： 最后一級(jí)的間距最大，每向前推一級(jí)，間距減小一半。 FFT算法（續(xù)） “整序”規(guī)律 將輸入序號(hào)按自然順序排序后，用相應(yīng)位數(shù)的二 進(jìn)制碼表示，再進(jìn)行反序，即可實(shí)現(xiàn)輸入端的整 序。 ? DIT DFT 屬于原位運(yùn)算。 FFT算法（續(xù)） 二、 DIT DFT算法小結(jié)： ? 計(jì)算一個(gè) 的 FFT時(shí)，需經(jīng)過(guò) 級(jí)分解，最終得到 N/2個(gè)兩點(diǎn) DFT。 FFT算法（續(xù)） 這樣， ? ? ? ? ? ?? ? ? ?1 3 2 41 3 2 4kNkNX k X k W X kX k X k W X k???? ??????N ＋40,1, , 14Nk ??? ?2xr 做相同的分解，并分別做傅立葉變換 ? ? ? ?? ? ? ?25262 0 , 1 , 2 , , 142 1 0 , 1 , 2 , , 14Nx l x l lNx l x l l? ? ? ????? ? ? ? ???? ? ? ?? ? ? ?415 5 40416 6 40NlkNrNlkNrX k x l WX k x l W????????167。 FFT算法（續(xù)） 例： N=8 可以分解為兩個(gè) N/2＝ 4點(diǎn)的 DFT N為偶數(shù)時(shí)，記 N為奇數(shù)時(shí)，記 ? ? ? ?? ? ? ?? ? ? ?? ? ? ?111100122436xxxxxxxx????? ? ? ?? ? ? ?? ? ? ?? ? ? ?222201132537xxxxxxxx????分別計(jì)算 N/2＝ 4點(diǎn)的 DFT，得 ? ? ? ?12,X k X k? ? ? ? ? ?? ? ? ? ? ?331 1 4 400332 2 4 400221rk rkrrrk rkrrX k x r W x r WX k x r W x r W??????? ? ?????（ k=0,1,2,3） 167。 結(jié)論： 一個(gè) N點(diǎn)序列的 DFT可由兩個(gè) N/2點(diǎn)的 DFT來(lái)確定。 FFT算法 ——庫(kù)利－圖基算法 一、算法原理（基 2FFT） x(n)按 n的奇偶分為兩組做 DFT，設(shè) 不足時(shí)可在序列末尾補(bǔ)零，這樣有： n為偶數(shù)時(shí)： n為奇數(shù)時(shí)： 因此： 2rN?? ? ? ?? ? ? ?122 , 0 ,1 , , 122 1 , 0 ,1 , , 12Nx r x r rNx r x r r? ? ?? ? ? ?? ? ? ?? ? ? ?10N nkNnX k D F T x n x n W???? ?167。1965年，庫(kù)利（ cooley）和圖基（ Tukey）首先提出 FFT算法，對(duì)于 N點(diǎn) DFT，僅需 次復(fù)數(shù)乘法運(yùn)算。 引言（續(xù)） 分析計(jì)算一個(gè) X(k)的值的工作量 :如 X(1) 考慮一般情況： 都是復(fù)數(shù) 一個(gè) X(k)： N次復(fù)數(shù)乘法，（ N1）次復(fù)數(shù)加法 所有 X(k)： N2次復(fù)數(shù)乘法， N（ N1）次復(fù)數(shù)加法 運(yùn)算量與 N2（序列長(zhǎng)度）成正比！ 當(dāng) N很大時(shí)，如 N=1024,則要完成 1048576次 （一百多萬(wàn)次）運(yùn)算，這樣，難以做到實(shí)時(shí)處理。 引言 一、 DFT的計(jì)算工作量 ? ? ? ? ? ?? ? ? ? ? ?1010011 01NknNnNknNnX k DFT x n x n W k Nx n I DFT X k X k W n NN?????? ? ? ? ?????? ? ? ? ???????兩者的差別僅在指數(shù)的符號(hào)和因子 1/N 167。 引言（續(xù)） 利用上述特性，可以將有些項(xiàng)合并，并將 DFT分解為短序列，從而降低運(yùn)算次數(shù)，提高運(yùn)算速度。 167。 FFT算法（續(xù)） 的后一半也完全由 的前一半所確定。 FFT算法（續(xù)） ：按奇偶分
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1