《《快速傅里葉變換》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《快速傅里葉變換》PPT課件（68頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第四章快速傅里葉變換1.引言2.直接計算DFT的問題及改進的途徑3.按時間抽選（DIT）的基2FFT算法4.離散傅里葉反變換（IDFT）的快速計算方法5.N為復合數(shù)的FFT算法混合基算法6.線性調(diào)頻Z變換（Chirp-z變換）算法7.線性卷積與線性相關(guān)的FFT算法 1.引言庫利和圖基發(fā)表的“機器計算傅里葉級數(shù)的一種算法”桑德和圖基的快速算法的出現(xiàn)。主要討論幾種FFT算法。 2.直接計算DFT的問題及改進的途徑 DFT和IDFT的變換公式 4.1式可寫成（4.3） 10 , 0,1, , 1N nkNnX k x n W k N 4.1 101 , 0,1, , 1N nkNkx n X k W

2、 n NN (4-2) 1 10 01 0 Re Im Re ImRe Re Im Im Re Im Im ReN Nnk nk nkN N Nn nN nk nk nk nkN N N NnX k x nW x n j x n W j Wx n W x n W j x n W x n W 存在問題：整個DFT運算總共需要4 次行乘法運算和次加法運算。直接計算DFT，乘法次數(shù)和加法次數(shù)都是和成正比。2N2(2 1) 2 (2 1)N N N N 2N 減少DFT運算工作量的途徑：利用對稱性：（1）的對稱性：（2）的周期性：（3）的可約性：可以得出實際辦法：（1）用上述特性對項合并（2）將長序列

3、的DFT分解為短序列的DFT。 3.按時間抽選的基2FFT算法3.1算法原理先設序列點數(shù)為，按n的奇偶進行分解將DFT化為2LN 利用系數(shù)的可約性，即得（4.5）式中（4.6）（4.7）nkNW 1 12 21 2 2 2 1 20 0N Nrk k rk kN N N Nr rX k x r W W x r W X k W X k 1 12 21 1 2 20 0 2N Nrk rkN Nr rX k x r W x r W 1 12 22 2 2 20 0 2 1N Nrk rkN Nr rX k x r W x r W 應用系數(shù)的周期性可得（4.8）（4.9）再考慮性質(zhì)（4.10）把4.

4、8,4.9,4.10代入4.5式，將X(k)表達成前后兩部分，前部分為（4.11）后部分為 （4.12） 1 12 221 1 2 1 2 10 02 N NNr k rkN Nr rNX k x r W x r W X k 2 22NX k X k 22N k N k kN N N NW W W W 1 2 ,kNX k X k W X k 0,1, , 12Nk 21 21 22 2 2, 0,1, , 12Nr kNkNN N NX k X k W X kNX k W X k k 這樣，4.11、12式只要0-(N/2-1)區(qū)間的所有的值，即可求0到(N-1)區(qū)間所有X(k)值。 4.1

5、1和4.12式用圖41的蝶形符號表示。 N8的情況如圖42 分析：每個蝶形運算需要一次復數(shù)乘法及兩次復數(shù)加（減）法。通過分解后運算工作量差不多減少到一半。 進一步把N/2點子序列再按奇偶部分分解為兩個N/4點的子序列且其中 圖43，給出N8時，在分解為兩個N/4點DFT，由兩個N/4點DFT組合成N/2點DFT的流圖。 也可進行同樣分解：其中 一個N8點DFT就可分解為四個N/42點DFT如圖 序列按奇偶分解標號變化討論（N8）第一次分解：兩個N/2點序列： 第二次分解，每個N/2點子序列按其奇偶分解為兩個N/4點子序列 最后2點DFT按41417進行計算。這種方法的每一步分解都是按輸入序列在

6、時間上的次序是屬于偶數(shù)不是屬于奇數(shù)來分解為兩個更短的子序列，所以稱為“按時間抽選法”。 運算量分析直接DFT復數(shù)算法次數(shù)是 FFT復數(shù)乘法次數(shù)是 DFT和FFT算法的計算量之比為結(jié)論：FFT比DFT更優(yōu)越，當N越大時，優(yōu)點更明顯。 三、按時間抽選的FFT算法特點 1.原位運算每個蝶形結(jié)構(gòu)完成下述基本迭代運算： 4.21的蝶形運算如圖47所示。 2.倒位序規(guī)律 3.倒位序的實現(xiàn)：通過變址運算完成 4.蝶形運算兩結(jié)點的距離：第m級運算，每個蝶形的兩節(jié)點距離為的確定第m級運算由421式寫成其中r的求解方法為 6.存儲單元輸入序列N個單元系數(shù)N/2個單元 四.按時間抽選的FFT算法的其它形式流程圖 4

7、.5離散傅里葉反變換的快速計算方法從IDFT公式與DFT公式比較可知，只要把DFT運算中的每一個系數(shù)變成，最后再乘常數(shù)1/N，則以上所有按時間抽選或按頻率抽選的FFT都可以拿來運算IDFT。 不改FFT的程序計算IFFT方法：對4.29式取共軛因而 4.6N為復合數(shù)的FFT算法混合基算法當N不滿足時，可有以下幾種辦法（1）將x(n)補一些零值點的辦法（2）如要求準確的N點DFT，而N又是素數(shù)，則只能采用直接DFT方法，或者用CZT方法。（3）N是復合數(shù)，即它可以分解成一些成一些因子的乘積，用混合基算法。 一.整數(shù)的多基多進制表示形式（1）對于二進制，表示為二進制倒序為（2）對于r進制，正序倒序

8、 （3）對于多進制或稱混合基 N可以表示成復合數(shù)，則對于 的任一個正整數(shù)n,可以按L個基表示。正序倒序 在這一多進制的表示中可記為 例41 二、的快速算法要計算N點DFT為（4.39）設n是一個復合數(shù)，可將n的數(shù)用下面的公式表達：（4.40）同樣，倒序表達為（4.41） 例：設，則那么所以則排列為1 24, 2r r 同樣，若則所以 將4.40式與4.41式代入4.39式，可得上式運用了結(jié)果 4.42式可進一步表示為 式中 N為復合數(shù)的DFT算法的步驟歸納如下：（1）將x(n)改寫成利用利用4.44式做個點DFT，得利用4.45式，把N個乘以相應的旋轉(zhuǎn)因子，組成。利用4.46式，做個點DFT，

9、得利用4.47式，進行整序，得到其中 對于重寫n和k的表達式則4.44式變成 此時有兩組4點DFT。4.45,46式分別變成后一式子共有4組2點DFT，4.47式變成 算法可以采用先乘旋轉(zhuǎn)因子再算DFT的算法當N為一個復合數(shù)時，可以分解為一些因子的乘積 2.N為復合數(shù)時FFT運算量的估計當時，運算量為復數(shù)乘法復數(shù)加法直接計算N個點DFT工作量加法乘法：N（N1） 混合基算法可節(jié)省的運算量倍數(shù)為乘法加法 當時，混合基算法總乘法次數(shù)與直接計算DFT相比，運算量之比 4.10 線性卷積與線性相關(guān)的FFT算法一、線性卷積的FFT算法 1.概念設x(n)為L點，h(n)為M點，輸出y(n)為 y(n)也

10、是有限長序列，其點數(shù)為LM1。 2.線性卷積運算量乘法次數(shù) 線性相位濾波器滿足條件運算結(jié)構(gòu)如圖5.26,5.27所示線性相位FIR濾波器的乘法運算量 用FFT法（圓周卷積）來代替這線性卷積時，不產(chǎn)生混疊條件是使x(n),h(n)都補零值點，補到至少N=M+L-1，即然后計算圓周卷積此時y(n)能代表線性卷積結(jié)果。 用FFT計算y(n)步驟如下：（1）求，N點（2）求，N點（3）計算；（4）求，N點 工作量分析 FFT計算工作量（4.105）用線性相位濾波器來比較直接計算線性卷積和FFT法計算線性卷積時比值（4.106） 運算量分析：（1）x(n)與h(n)點數(shù)差不多，設ML，則，則計算得下表

11、（2）當x(n)點數(shù)很多時，即當則這時當L太大時，體現(xiàn)不出圓周積分的優(yōu)點。解決辦法：分段卷積或稱分段過濾 1.重疊相加法設h(n)的點數(shù)為M，信號x(n)為很長的序列。將x(n)分解為很多段，每段為L點，L選擇成和M的數(shù)量級相同，用表示x(n)的第i段（4.108）則輸入序列可表示成（4.109）線性卷積為（4.110） 每一個才可用快速卷積辦法來運算，對和補零值點，補到N點。為利用基2算法，取，然后作N點的圓周卷積其方法如圖429所示。 重疊相加法的步驟總結(jié)（1）計算N點FFT，（2）計算N點FFT，（3）相乘，（4）計算N點IFFT，（5）將各段（包括重疊部分相加）， 2.重疊保留法先將x(n)分段，每段補上LNM1個點；序列中補零處不補零，而每一段的前邊補上前一段保留下來的（M1）個輸入序列值，組成LM1點序列，如圖4.30a所示。如果，則可在每段序列未端補零值點，補到長度為2m。 二、線性相關(guān)的FFT算法：常稱之為快速相關(guān)，要利用補零值點的辦法避免混疊失真。設x(n)為L點，y(n)為M點，需求線性相關(guān)（4.115）利用FFT法求線性相關(guān)是用圓周相關(guān)代替線性相關(guān)，選擇令 其計算步驟如下：（1）求N點FFT，（2）求N點FFT，（3）求乘積，（4）求N點IFFT，同樣，可以只利用已有的FFT程序計算IFFT，求 再見！