數(shù)字信號(hào)處理：第7章快速傅里葉變換FFT

1、第七章 快速傅里葉變換（FFT）第七章學(xué)習(xí)目標(biāo)理解按時(shí)間抽選的基-2FFT算法的算法原理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn)理解按頻率抽選的基-2FFT算法的算法原理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn)理解IFFT算法了解CZT算法理解線性卷積的FFT算法引言FFT: Fast Fourier Transform有限長(zhǎng)序列通過(guò)離散傅里葉變換（DFT）將其頻域離散化成有限長(zhǎng)序列，但其計(jì)算量太大，很難實(shí)時(shí)處理，因此引出了快速傅里葉變換。1965年，Cooley(庫(kù)利)-Turky(圖基) 發(fā)表文章機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法，提出FFT算法，解決DFT運(yùn)算量太大，在實(shí)際使用中受限制的問(wèn)題。FFT并不是一種

2、新的變換形式，它只是DFT的一種快速算法，并且根據(jù)對(duì)序列分解與選取方法的不同產(chǎn)生了多種算法。FFT的應(yīng)用：頻譜分析、濾波器實(shí)現(xiàn)、實(shí)時(shí)信號(hào)處理、離散傅里葉反變換、線性卷積和線性相關(guān)等方面。DSP芯片實(shí)現(xiàn)。TI公司的TMS 320c30，10MHz時(shí)鐘，基2-FFT1024點(diǎn)FFT時(shí)間15ms。7.1 直接計(jì)算DFT的問(wèn)題及改進(jìn)途徑1. 運(yùn)算量復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)X(k)NN 1N個(gè)X(k)(N點(diǎn)DFT)N 2N (N 1)實(shí)數(shù)乘法實(shí)數(shù)加法一次復(fù)乘42一次復(fù)加2一個(gè)X (k)4N2N+2 (N 1)=2 (2N 1)N個(gè)X (k)(N點(diǎn)DFT)4N 22N (2N 1)2.4. FFT算法分類:時(shí)

3、間抽選法 DIT: Decimation-In-Time頻率抽選法 DIF: Decimation-In-Frequency N點(diǎn)DFTN/2點(diǎn)DFTN/4點(diǎn) DFT2點(diǎn) DFT1個(gè) 2個(gè) 4個(gè) N/2個(gè)3. FFT算法的基本思想： 利用DFT系數(shù) 特性，合并DFT運(yùn)算中的某些項(xiàng)，將大點(diǎn)數(shù)的DFT分解成若干個(gè)小點(diǎn)數(shù)的DFT。7.2 按時(shí)間抽取的基-2FFT算法（ DIT ）1、算法原理設(shè)序列點(diǎn)數(shù) N = 2M，M 為整數(shù)。 若不滿足，則補(bǔ)零將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱基-2FFT算法。則x(n)的DFT:兩個(gè)k一樣嗎？只是X(k)前半部分利用周期性求X(k)的

4、后半部分:圖7-1 按時(shí)間抽取蝶形運(yùn)算流圖N點(diǎn)DFT的第一次按時(shí)間抽取過(guò)程：第一步：x(n)按n的奇偶分解成偶序號(hào)序列和奇序號(hào)序列第二步：對(duì)分解后的序列進(jìn)行N/2點(diǎn)DFT第三步：對(duì)兩序列的DFT進(jìn)行蝶形運(yùn)算得到X(k)按n的奇偶分解即圖7-2 一個(gè)N點(diǎn)DFT分解為兩個(gè) 點(diǎn)DFT（N=8）分解后的運(yùn)算量：復(fù)數(shù)乘法復(fù)數(shù)加法N點(diǎn)DFT一個(gè)N / 2點(diǎn)DFTN 2(N / 2)2N (N 1)N / 2 *(N / 2 1)兩個(gè)N / 2點(diǎn)DFTN 2 / 2N (N / 2 1)一個(gè)蝶形12N / 2個(gè)蝶形N / 2N總計(jì)運(yùn)算量減少了近一半N / 2仍為偶數(shù)，進(jìn)一步分解：N / 2 N / 4圖7-

5、3 一個(gè) 點(diǎn)DFT分解為兩個(gè) 點(diǎn)DFT（N=8）同理：其中：圖7-4 一個(gè)N點(diǎn)DFT分解為四個(gè) 點(diǎn)DFT（N=8）圖7-2 一個(gè)N點(diǎn)DFT分解為兩個(gè) 點(diǎn)DFT（N=8）這樣逐級(jí)分解，直到兩點(diǎn)DFT，兩點(diǎn)DFT不需要乘法運(yùn)算。當(dāng)N = 8時(shí)，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k = 0, 1兩點(diǎn)DFT可用一個(gè)蝶形運(yùn)算實(shí)現(xiàn)例如：2點(diǎn)DFT的運(yùn)算流圖 當(dāng)N = 2M時(shí)，N點(diǎn)DFT可完全分解為M 級(jí)蝶形運(yùn)算，每級(jí)有N/2個(gè)蝶形結(jié)例如：N=8 = 23 M=3 圖7-5 按時(shí)間抽取FFT信號(hào)流圖（N=8）第一級(jí)第二級(jí)第三級(jí)2、運(yùn)算量 當(dāng)N = 2M時(shí)，共有M級(jí)蝶形， 每級(jí)有N/2個(gè)

6、如下的蝶形單元：總共復(fù)數(shù)乘法：復(fù)數(shù)加法：一個(gè)蝶形單元只需一次復(fù)數(shù)乘法，兩次復(fù)數(shù)加法。可以共享直接計(jì)算DFT與FFT算法的計(jì)算量比較FFT復(fù)數(shù)乘法：DFT復(fù)數(shù)乘法：直接計(jì)算DFT與FFT算法所需乘法次數(shù)的比較圖3、算法特點(diǎn)（ ）1）蝶形運(yùn)算圖7-6 按時(shí)間抽取蝶形運(yùn)算結(jié)m表示第m級(jí)迭代，i和j表示數(shù)據(jù)所在的行數(shù)，其中：最后一級(jí)第M級(jí)共有N/2個(gè)系數(shù)，即 ，前推一級(jí)系數(shù)減少一半，只用后一級(jí)的偶序號(hào)上的系數(shù)，即每個(gè)蝶形的兩節(jié)點(diǎn)距離2）同址運(yùn)算(原位運(yùn)算) 兩點(diǎn)構(gòu)成一個(gè)蝶形單元，并且這兩點(diǎn)不再參與別的蝶形單元的運(yùn)算。 當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器以后，每一級(jí)運(yùn)算的結(jié)果仍然存儲(chǔ)在這同一組存儲(chǔ)器中，直到最后輸出，中

7、間無(wú)需其他存儲(chǔ)器。第一級(jí)第二級(jí)第三級(jí)蝶形運(yùn)算單元 由于每一步分解都是按輸入序列在時(shí)間上的奇偶次序，分解成兩個(gè)半長(zhǎng)的子序列，所以稱“按時(shí)間抽取算法”。存儲(chǔ)器3）碼位倒序 輸入序列x(n)的排列次序不符合自然順序。此現(xiàn)象是由于按n的奇偶分組進(jìn)行DFT運(yùn)算而造成的，這種排列方式為“碼位倒序”。 所謂“碼位倒序”，是指按二進(jìn)制表示的數(shù)字首尾位置顛倒，重新按十進(jìn)制讀數(shù)。表 順序和倒序二進(jìn)制數(shù)對(duì)照表例：N =8=234）存儲(chǔ)單元輸入序列x(n) : N個(gè)存儲(chǔ)單元系數(shù) ：N / 2個(gè)存儲(chǔ)單元4.小結(jié) 全部計(jì)算分解為M級(jí)，或稱為M次迭代。 輸入倒序，輸出正序。 每級(jí)都包含N/2個(gè)蝶形單元。 每級(jí)的若干蝶形單元

8、組成“群”。第1級(jí)群數(shù)為N/2，第2級(jí)群數(shù)為N/4，第i級(jí)群數(shù)為N/2i，最后一級(jí)的群數(shù)為1。 每個(gè)蝶形單元都包含乘WNk與-WNk的運(yùn)算（可簡(jiǎn)化為乘WNk與加、減法各一次）。 同一級(jí)中，各個(gè)群的W分布規(guī)律完全相同。7.3 按頻率抽選的基-2FFT算法（ DIF ）1、算法原理 將X(k)按k的奇偶分組前，先將輸入x(n) 按n的順序分成前后兩半：設(shè)序列點(diǎn)數(shù) N = 2M，M 為整數(shù)。 若不滿足，則補(bǔ)零。前一半x(n)：n=0,1,2,N/2-1后一半x(n)：n=N/2,N/2+1,N-1 按k的奇偶將X(k)分成兩部分：當(dāng)k=2r時(shí)：當(dāng)k=2r+1時(shí)：其中： 則圖7-8 按頻率抽取蝶形運(yùn)算

9、流圖N點(diǎn)DFT的第一次按頻率抽取過(guò)程：第一步：x(n)按n的順序分成前一半序列和后一半序列第三步：對(duì)兩序列進(jìn)行N/2點(diǎn)DFT得到X(k)第二步：前一半和后一半序列進(jìn)行蝶形運(yùn)算得即例如：N=8 = 23 M=3r=0,1,2,3圖7-9 一個(gè)N點(diǎn)DFT分解為兩個(gè) 點(diǎn)DFT（N=8）分解后的運(yùn)算量：N點(diǎn)DFT復(fù)數(shù)乘法N 2復(fù)數(shù)加法N (N 1)一個(gè)N / 2點(diǎn)DFT(N / 2)2N / 2 *(N / 2 1)兩個(gè)N / 2點(diǎn)DFTN 2 / 2N (N / 2 1)一個(gè)蝶形12N / 2個(gè)蝶形N / 2N總計(jì)運(yùn)算量減少了近一半 按r的奇偶將X(2r)分成兩部分：當(dāng)r=2l時(shí)：當(dāng)r=2l+1時(shí)：

10、 按r的奇偶將X(2r)分成兩部分：N /2仍為偶數(shù)，進(jìn)一步分解：N /2 N /4圖7-10 一個(gè) 點(diǎn)DFT分解為兩個(gè) 點(diǎn)DFT（N=8）圖7-10 一個(gè) 點(diǎn)DFT分解為兩個(gè) 點(diǎn)DFT（N=8）圖7-10 一個(gè) 點(diǎn)DFT分解為兩個(gè) 點(diǎn)DFT（N=8）同理：圖7-11 一個(gè)8點(diǎn)DFT分解成四個(gè)兩點(diǎn)DFTN點(diǎn)DFT經(jīng)過(guò)兩次按頻率抽取后：逐級(jí)分解，直到兩點(diǎn)DFT，兩點(diǎn)DFT不需要乘法運(yùn)算。當(dāng)N=8時(shí)，分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,1結(jié)論：兩點(diǎn)DFT可用一個(gè)蝶形運(yùn)算來(lái)實(shí)現(xiàn)蝶形運(yùn)算蝶形運(yùn)算兩點(diǎn)DFT可用一個(gè)蝶形運(yùn)算來(lái)實(shí)現(xiàn)例如：2點(diǎn)DFT的運(yùn)算流圖 當(dāng)N = 2M時(shí)，N點(diǎn)

11、DFT可完全分解為M 級(jí)蝶形運(yùn)算，每級(jí)有N/2個(gè)蝶形結(jié)例如：N=8 = 23 M=3 圖7-12 按頻率抽取FFT信號(hào)流圖（N=8）2、運(yùn)算量當(dāng)N = 2M時(shí)，共有M級(jí)蝶形，每級(jí)N/2個(gè)蝶形，每個(gè)蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。比較DFT： 復(fù)數(shù)乘法：復(fù)數(shù)加法：圖 直接計(jì)算DFT與FFT算法所需乘法次數(shù)的比較3、算法特點(diǎn)（ ）1）蝶形運(yùn)算圖7-13 按頻率抽取蝶形運(yùn)算結(jié)m表示第m級(jí)迭代，i和j表示數(shù)據(jù)所在的行數(shù)，其中：最后一級(jí)第M級(jí)共有N/2個(gè)系數(shù)，即 ，前推一級(jí)系數(shù)減少一半，只用后一級(jí)的偶序號(hào)上的系數(shù)，即每個(gè)蝶形的兩節(jié)點(diǎn)距離2）同址運(yùn)算(原位運(yùn)算) 當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器以后，每一級(jí)運(yùn)算的結(jié)果仍

12、然存儲(chǔ)在這同一組存儲(chǔ)器中，直到最后輸出，中間無(wú)需其他存儲(chǔ)器。3）碼位倒序X(k)按k的碼位倒序輸出，x(n)按n的自然順序輸入4、DIT與DIF的異同基本蝶形不同DIT: 先復(fù)乘后加減DIF: 先減后復(fù)乘運(yùn)算量相同都可原位運(yùn)算DIT和DIF的基本蝶形互為轉(zhuǎn)置復(fù)乘數(shù)復(fù)加數(shù)輸入輸出順序不同DIT: 輸入碼位倒序，輸出自然順序DIF: 輸出碼位倒序，輸如自然順序DITDIF 將流圖的所有支路方向都反向，并且交換輸入與輸出，但節(jié)點(diǎn)變量值不交換，這樣即可從一種流圖得到另一種。 這樣，對(duì)每一種按時(shí)間抽取的FFT流圖都存在一個(gè)按頻率抽取的FFT流圖，反之亦然。 頻率抽取法與時(shí)間抽取法實(shí)質(zhì)上是兩種等價(jià)的FFT

13、運(yùn)算。轉(zhuǎn)置定理直接DFT方法 / CZT方法：當(dāng)要求準(zhǔn)確的N點(diǎn)DFT，且N是素?cái)?shù)時(shí)7.4 N為復(fù)合數(shù)的FFT算法混合基算法基-2FFT算法：補(bǔ)零使?jié)M足混合基FFT算法：N是復(fù)合數(shù)7.5 快速傅里葉反變換（IFFT）算法比較：IDFT:DFT:改變FFT的IFFT程序 圖7-15 按時(shí)間抽取IFFT信號(hào)流圖（N=8）共軛FFT共軛乘1/ N直接調(diào)用FFT子程序計(jì)算IFFT的方法：直接用FFT程序的IFFT程序7.6 線性調(diào)頻 z變換（CZT)算法FFT不適用于：只研究信號(hào)的某一頻段，要求對(duì)該頻段抽樣密集，提高分辨率；研究非單位圓上的抽樣值；需要準(zhǔn)確計(jì)算N點(diǎn)DFT，且N為大的素?cái)?shù)；等等。CZT算法

14、：對(duì)z變換采用螺線抽樣，chirp-z變換線性調(diào)頻 z變換1、算法原理 N點(diǎn)有限長(zhǎng)序列，其z變換：沿z平面上的一段螺線作等分角抽樣，抽樣點(diǎn)zk：其中：M為要分析的復(fù)頻譜點(diǎn)數(shù) 則圖7-16 CZT計(jì)算路徑 螺旋采樣 抽樣點(diǎn)：:起始抽樣點(diǎn)的相角:相鄰抽樣點(diǎn)的角度差:分析路徑的盤(pán)旋趨勢(shì)(螺線的伸展率)W01:向內(nèi)盤(pán)旋(內(nèi)縮) W01:向外盤(pán)旋(外伸) :逆時(shí)針 :順時(shí)針圖7-16 CZT計(jì)算路徑:起始抽樣點(diǎn)的矢量半徑長(zhǎng)度譜分析的起始點(diǎn)位置求抽樣點(diǎn)處的z變換：令令圖7-17 CZT運(yùn)算流圖其中： 卷積可以通過(guò)圓周卷積來(lái)實(shí)現(xiàn)，這樣可借用FFT快速算法。2、CZT的實(shí)現(xiàn)步驟(自學(xué))圖7-17 CZT運(yùn)算流圖取前M個(gè)點(diǎn)圖7-18 CZT變換的圓周卷積1) 選擇 ，且2) 形成L點(diǎn)序列f(n)：遞歸法求解求f(n) 的L點(diǎn)DFT：3）形成L點(diǎn)序列h(n):或求h(n) 的L點(diǎn)DFT：4）求乘積5）取g(n)的前M個(gè)點(diǎn)得g(k)6）求抽樣點(diǎn)的z變換:求G(k) 的L點(diǎn)IDFT：說(shuō)明令3、CZT算法的特點(diǎn) 可計(jì)算單位圓上任一段曲線上的Z變換，可任意給定起止頻率； 周線不必是z平面上的圓，在語(yǔ)音分析中螺旋周線具有