《快速傅里葉變換》PPT課件

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

1、第四章快速傅里葉變換1.引言2.直接計(jì)算DFT的問(wèn)題及改進(jìn)的途徑3.按時(shí)間抽選（DIT）的基2FFT算法4.離散傅里葉反變換（IDFT）的快速計(jì)算方法5.N為復(fù)合數(shù)的FFT算法混合基算法6.線性調(diào)頻Z變換（Chirp-z變換）算法7.線性卷積與線性相關(guān)的FFT算法 1.引言庫(kù)利和圖基發(fā)表的“機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法”桑德和圖基的快速算法的出現(xiàn)。主要討論幾種FFT算法。 2.直接計(jì)算DFT的問(wèn)題及改進(jìn)的途徑 DFT和IDFT的變換公式 4.1式可寫(xiě)成（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 存在問(wèn)題：整個(gè)DFT運(yùn)算總共需要4 次行乘法運(yùn)算和次加法運(yùn)算。直接計(jì)算DFT，乘法次數(shù)和加法次數(shù)都是和成正比。2N2(2 1) 2 (2 1)N N N N 2N 減少DFT運(yùn)算工作量的途徑：利用對(duì)稱性：（1）的對(duì)稱性：（2）的周期性：（3）的可約性：可以得出實(shí)際辦法：（1）用上述特性對(duì)項(xiàng)合并（2）將長(zhǎng)序列

3、的DFT分解為短序列的DFT。 3.按時(shí)間抽選的基2FFT算法3.1算法原理先設(shè)序列點(diǎn)數(shù)為，按n的奇偶進(jì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 應(yīng)用系數(shù)的周期性可得（4.8）（4.9）再考慮性質(zhì)（4.10）把4.

4、8,4.9,4.10代入4.5式，將X(k)表達(dá)成前后兩部分，前部分為（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的蝶形符號(hào)表示。 N8的情況如圖42 分析：每個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘法及兩次復(fù)數(shù)加（減）法。通過(guò)分解后運(yùn)算工作量差不多減少到一半。 進(jìn)一步把N/2點(diǎn)子序列再按奇偶部分分解為兩個(gè)N/4點(diǎn)的子序列且其中 圖43，給出N8時(shí)，在分解為兩個(gè)N/4點(diǎn)DFT，由兩個(gè)N/4點(diǎn)DFT組合成N/2點(diǎn)DFT的流圖。 也可進(jìn)行同樣分解：其中 一個(gè)N8點(diǎn)DFT就可分解為四個(gè)N/42點(diǎn)DFT如圖 序列按奇偶分解標(biāo)號(hào)變化討論（N8）第一次分解：兩個(gè)N/2點(diǎn)序列： 第二次分解，每個(gè)N/2點(diǎn)子序列按其奇偶分解為兩個(gè)N/4點(diǎn)子序列 最后2點(diǎn)DFT按41417進(jìn)行計(jì)算。這種方法的每一步分解都是按輸入序列在

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

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

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

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

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

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