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

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

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

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

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

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

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

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

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

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

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

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

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

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

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