快速傅里葉變換課件

第四章快速傅里葉變換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〕4.1

(4-2)存在問題：整個DFT運算總共需要4次行乘法運算和次加法運算。直接計算DFT，乘法次數(shù)和加法次數(shù)都是和成正比。減少DFT運算工作量的途徑：利用對稱性：〔1〕的對稱性：〔2〕的周期性：〔3〕的可約性：可以得出實際方法：〔1〕用上述特性對項合并〔2〕將長序列的DFT分解為短序列的DFT。3.按時間抽選的基－2FFT算法

－－3.1算法原理先設(shè)序列點數(shù)為，按n的奇偶進行分解將DFT化為利用系數(shù)的可約性，即得〔4.5〕式中〔4.6〕〔4.7〕應(yīng)用系數(shù)的周期性可得〔4.8〕〔4.9〕再考慮性質(zhì)〔4.10〕把4.8,4.9,4.10代入4.5式，將X(k)表達成前后兩局部，前局部為〔4.11〕后局部為〔4.12〕這樣，4.11、12式只要0-(N/2-1)區(qū)間的所有的值，即可求0到(N-1)區(qū)間所有X(k)值。4.11和4.12式用圖4－1的蝶形符號表示。N＝8的情況如圖4－2分析：每個蝶形運算需要一次復數(shù)乘法及兩次復數(shù)加〔減〕法。通過分解后運算工作量差不多減少到一半。進一步把N/2點子序列再按奇偶局部分解為兩個N/4點的子序列且其中圖4－3，給出N＝8時，在分解為兩個N/4點DFT，由兩個N/4點DFT組合成N/2點DFT的流圖。也可進行同樣分解：其中一個N＝8點DFT就可分解為四個N/4＝2點DFT如圖序列按奇偶分解標號變化討論〔N＝8〕第一次分解：兩個N/2點序列：第二次分解，每個N/2點子序列按其奇偶分解為兩個N/4點子序列最后2點DFT按4－14~17進行計算。這種方法的每一步分解都是按輸入序列在時間上的次序是屬于偶數(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的蝶形運算如圖4－7所示。2.倒位序規(guī)律3.倒位序的實現(xiàn)：通過變址運算完成4.蝶形運算兩結(jié)點的距離：第m級運算，每個蝶形的兩節(jié)點距離為確實定第m級運算由4－21式寫成其中r的求解方法為6.存儲單元輸入序列N個單元系數(shù)N/2個單元四.按時間抽選的FFT算法的其它形式流程圖4.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方法?！?〕N是復合數(shù)，即它可以分解成一些成一些因子的乘積，用混合基算法。一.整數(shù)的多基多進制表示形式〔1〕對于二進制，表示為二進制倒序為〔2〕對于r進制，正序倒序〔3〕對于多進制或稱混合基N可以表示成復合數(shù)，，那么對于的任一個正整數(shù)n,可以按L個基表示。正序倒序在這一多進制的表示中可記為例4－1二、的快速算法要計算N點DFT為〔4.39〕設(shè)n是一個復合數(shù)，可將n的數(shù)用下面的公式表達：〔4.40〕同樣，倒序表達為〔4.41〕例：設(shè)，那么那么所以那么排列為同樣，假設(shè)那么所以將4.40式與4.41式代入4.39式，可得上式運用了結(jié)果4.42式可進一步表示為式中N為復合數(shù)的DFT算法的步驟歸納如下：〔1〕將x(n)改寫成利用利用4.44式做個點DFT，得利用4.45式，把N個乘以相應(yīng)的旋轉(zhuǎn)因子，組成。利用4.46式，做個點DFT，得利用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〔N＋1〕混合基算法可節(jié)省的運算量倍數(shù)為乘法加法當時，混合基算法總乘法次數(shù)與直接計算DFT相比，運算量之比4.10線性卷積與線性相關(guān)的FFT算法一、線性卷積的FFT算法1.概念設(shè)x(n)為L點，h(n)為M點，輸出y(n)為y(n)也是有限長序列，其點數(shù)為L＋M－1。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ù)差不多，設(shè)M＝L，那么，那么計算得下表〔2〕當x(n)點數(shù)很多時，即當那么這時當L太大時，表達不出圓周積分的優(yōu)點。解決方法：分段卷積或稱分段過濾1.重疊相加法設(shè)h(n)的點數(shù)為M，信號x(n)為很長的序列。將x(n)分解為很多段，每段為L點，L選擇成和M的數(shù)量級相同，用表示x(n)的第i段〔4.108〕那么輸入序列可表示成〔4.109〕線性卷積為〔4.110〕每一個才可用快速卷積方法來運算，對和補零值點，補到N點。為利用基2算法，取，然后作N點的圓周卷積其方法如圖4－29所示。重疊相加法的步驟總結(jié)〔1〕計算N點FFT，〔2〕計算N點FFT，〔3〕相乘，〔4〕計算N點IFFT，〔5〕將各段〔包括重疊局部相加〕，2.重疊保存法先將x(n)分段，每段補上L＝N－M＋1個點；序列中補零處不補零，而每一段的前邊補上前一段保存下來的〔M－1〕個輸入序列值，組成L＋M－1點序列，如圖4.30a所示。如果，那么可在每段序列未端補零值點，補到長度為2m。二、線性相關(guān)的FFT算法：常稱之為快速相關(guān)，要利用