1、第四章 快速傅立葉變換(FFT),一、直接用DFT計(jì)算的運(yùn)算量與用FFT計(jì)算的運(yùn)算量比較，減少運(yùn)算量的途徑,二、FFT算法中一些概念,按時(shí)間抽取法解過(guò)程的規(guī)律。 1.原位運(yùn)算（in-place) 2.碼位倒讀規(guī)則，亂序輸入，順序輸出 （1）“級(jí)”概念 將N 點(diǎn)DFT先分成兩個(gè)N/2點(diǎn)DFT，再是四個(gè)N/4點(diǎn)DFT直至N/2個(gè)兩點(diǎn)DFT.每分一次稱為“一”級(jí)運(yùn)算。 因?yàn)镹=2M所以N點(diǎn)DFT可分成M級(jí) 依次m=0,m=1.M-1共M級(jí),（2）“組”概念,每一級(jí)都有N/2個(gè)蝶形單元，例如：N=8,則每級(jí)都有4個(gè)蝶形單元。每一級(jí)的N/2個(gè)蝶形單元可以分成若干組，每一組具有相同的結(jié)構(gòu)，相同的 因子分布

2、，第m級(jí)的組數(shù)為：,例：N=8=23，分3級(jí)。 m=0級(jí),分成四組,每組系數(shù)為 m=1級(jí),分成二組,每組系數(shù)為 m=2級(jí),分成一組,每組系數(shù)為,(3) 因子的分布,結(jié)論：每由后向前（m由M-1-0級(jí)）推進(jìn)一級(jí)，則此系數(shù)為后級(jí)系數(shù)中偶數(shù)序號(hào)的那一半。,三、一個(gè)完整N=8的按DIT時(shí)間抽取FFT的運(yùn)算流圖,x(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),m=0,m=1,m=2,一個(gè)完整N=8的按DIF頻率抽取FFT的運(yùn)算流圖,x(0) x(1) x(2) x(3) x(4) x(5) x

3、(6) x(7),X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7),m=0,m=1,m=2,2.直接利用FFT流圖方法的推導(dǎo),可知：只須將頻域成份一個(gè)求共軛變換，即（1）將X(k)的虛部乘以-1，即先取X(k)的共軛，得X*(k)。(2)將X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再對(duì)運(yùn)算結(jié)果取一次共軛變換，并乘以常數(shù)1/N，即可以求出IFFT變換的x(n)的值。,此為DFT可用FFT程序,3.用CZT求解DFT的流圖,6、說(shuō)明1,（1）A為起始樣點(diǎn)位置,6、說(shuō)明2,（2）zk是z平面一段螺線上的等分角上某一采樣點(diǎn)。,6、說(shuō)明3,6、說(shuō)明4,10

4、、CZT運(yùn)算量與直接運(yùn)算量比較,當(dāng)M、N足夠小時(shí)，直接算法運(yùn)算量少。 但M、N值比較大時(shí)（大于50），CZT算法比直接算法的運(yùn)算量少得多。 例M=50，N=50，N*M=2500次 而CZT1600次。,重疊相加法,（1）x(n)為分段，每段長(zhǎng)為p點(diǎn)，p選擇與M數(shù)量組相同。用xi(n)表示x(n)的第i段.,重疊保留法,第三章 離散傅立葉變換（DFT）,一、四種不同的傅立葉變換對(duì) 傅 里 葉 級(jí) 數(shù)(FS)：連 續(xù) 時(shí) 間 , 離 散 頻 率 的 傅 里 葉 變 換 。 連 續(xù) 傅 里 葉 變 換(FT)：連 續(xù) 時(shí) 間 , 連 續(xù) 頻 率 的 傅 里 葉 變 換 。 序 列 的 傅 里 葉

5、變 換(DTFT):離 散 時(shí) 間 , 連 續(xù) 頻 率 的 傅 里 葉 變 換. 離 散 傅 里 葉 變 換(DFT):離 散 時(shí) 間 , 離 散 頻 率 的 傅 里 葉 變 換,四種付里葉變換形式的歸納,二、DFS定義,設(shè) 為周 期 為 N 的 周 期 序 列 , 則 其 離 散 傅 里 葉 級(jí) 數(shù) (DFS) 變 換 對(duì) 為 : 正 變 換 反變換 其中:,三、DFT,1、定義 正變換 反變換 X(k)、x(n)為有限長(zhǎng)序列的離散付里葉變換對(duì)，已知其中一個(gè)序列就能確定另一個(gè)序列。,2、DFT性質(zhì),時(shí)移特性 已知 DFTx(n)=X(k) 則 DFTx(n+m)NRN(n)=WN-mkX(k

6、) 頻移特性 設(shè)頻域N點(diǎn)，有限長(zhǎng)序列X(k) 則,3、圓 周 卷 積 與 線 性 卷 積 的 性 質(zhì) 對(duì) 比,4、奇偶虛實(shí)關(guān)系表,四、頻域抽樣理論,長(zhǎng)度為M的有限長(zhǎng)序列,頻域抽樣不失真的條件： 頻域抽樣點(diǎn)數(shù)N要大于或等于序列長(zhǎng)度M, 即滿足NM.此時(shí)可得到 表明長(zhǎng)度為N(或小于N)的有限長(zhǎng)序列可用它的z變換在單位圓上的N個(gè)均分點(diǎn)上的抽樣值精確地表示.,五、DFT 做 傅 里 葉 變 換 (級(jí) 數(shù)) 的逼 近 時(shí) 所 產(chǎn) 生 的 問(wèn) 題,混 疊 現(xiàn) 象: 頻 譜 泄 漏 柵 欄 效 應(yīng),1、混 疊 現(xiàn) 象,利 用 DFT 逼 近 連 續(xù) 時(shí) 間 信 號(hào) 的 傅 里 葉 變 換 ,為 避 免 混

7、疊 失 真, 要求滿足抽樣定理，即奈奎斯特準(zhǔn)則： fs2fh 其中fs為抽 樣 頻 率 , fh 為信號(hào)最高頻率.但此條件只規(guī)定出fs的下限為fh , 其上限要受抽樣間隔 F的約束. 抽 樣 間 隔 F 即 頻 率 分 辨 力, 它是 記 錄 長(zhǎng) 度的 倒 數(shù), 即 Tp = 1 / F 若 抽 樣 點(diǎn) 數(shù) 為 N, 則 抽 樣 間 隔 與 fs 的 關(guān) 系 為 F = fs / N 2fh /N,混 疊 現(xiàn) 象的結(jié)論,由F = fs / N 2fh /N 看出： 在 N 給 定 時(shí), 為 避 免混 疊 失 真 而 一 味 提 高 抽 樣 頻 率 fs , 必 然 導(dǎo) 致 F 增 加, 即 頻

8、 率 分 辨 力 下 降; 反 之, 若 要 提 高 頻 率 分 辨 力 即 減 小 F, 則 導(dǎo) 致 減 小fs, 最 終 必 須 減 小 信 號(hào) 的 高 頻 容 量. 以 上 兩 點(diǎn) 結(jié) 論 都 是 在記錄長(zhǎng)度內(nèi)抽樣點(diǎn)數(shù) N 給 定 的 條 件 下 得 到 的. 所 以 在 高 頻 容 量 fh 與 頻 率 分 辨 力 F 參 數(shù) 中, 保 持 其 中 一 個(gè) 不 變 而 使 另 一 個(gè) 性 能 得 以 提 高 的 唯 一 辦 法, 就 是 增 加 記 錄 長(zhǎng) 度 內(nèi) 的 點(diǎn) 數(shù) N, 即 fh 和 F 都 給 定 時(shí), 則 N 必 須 滿 足 N 2fh /F 這是未采用任何特殊數(shù)據(jù)處理

9、（例如加窗）情況下，為實(shí)現(xiàn)基本DFT算法所必須滿足條件。,2、頻 譜 泄 漏注 意 點(diǎn),由于我們無(wú)法取無(wú)數(shù)個(gè)點(diǎn)，所以在DFT時(shí)，時(shí)域的截?cái)嗍潜厝坏模蚨孤┮彩潜厝淮嬖诘摹?為了減少頻率泄漏可采用： （1）適當(dāng)加大窗口寬度，增加M值； （2）采用適當(dāng)形狀的窗函數(shù)截?cái)?指出：泄漏是不能與混疊完全分開(kāi)的。,3、減 小 柵 欄 效 應(yīng)方 法,減 小 柵 欄 效 應(yīng) 的 一 個(gè) 方 法 是 在 所 取 數(shù) 據(jù) 的 末 端 加 一 些 零 值 點(diǎn), 使 一 個(gè) 周 期 內(nèi) 點(diǎn) 數(shù) 增 加, 但 是 不 改 變 原 有 的 記 錄 數(shù) 據(jù). 這種方法 等 效 于 加 長(zhǎng) 了 周 期 Tp . 因 公 式 F = 1/ Tp (F是 抽 樣 間 隔). Tp 增 加, 抽 樣 間 隔 變 小, 從 而 能 保 持 原 來(lái) 頻 譜 形 式 不 變 的 情 況 下 使 譜 線 變 密, 也 就 使 頻 譜 抽 樣 點(diǎn) 數(shù) 增 加. 這 樣, 原 來(lái) 看 不 到 的 頻 譜 分 量 就 有 可 能 看 到 了