鄭州大學信息工程學院1DigitalSignalProcessing數字信號處理鄭州大學信息工程學院蔣慧琴第八章DFT的有效計算：

快速傅立葉變換

FFT-FastFourierTransform本章內容1)明確FFT與DFT的關系：只是計算方法的改進，基本沒有引入新的物理概念；2)掌握FFT算法的原理：利用DFT的運算規律及其中某些算子的特殊性質（的周期性和對稱性），找出減少乘法和加法運算次數的有效途徑；3)掌握基-2DIT—FFT和基-2DIF—FFT算法的基本思想及特點（算法思想，運算量，運算流圖，結構規則等）。鄭州大學信息工程學院34

對每個特定k,

X(k)的

DFT的計算：有(N－1)個復加和

N

個復乘；

計算整個DFT

共有N(N-1)個復加和N2

個復乘；通過利用

的對稱性和周期性，整個DFT的復乘計算量可減至為

Nlog2N

FastFourierTransform(FFT).8.1DFT的有效計算：FFT算法(概述)2.用分而治之的方法計算DFT基本原理:把計算長度為的序列的DFT逐次地分解成計算長度較短序列的離散傅里葉變換。將序列儲存在二維數組中，它的每個數據都依賴于下標到下標的映射。計算所得的DFT值儲存在一個類似的排列中，映射是從下標到下標對(p,q)的映射,567例8.1.1考慮時的點DFT的計算

8對每一列計算5點DFT

9當按照從第一行到第五行的順序讀取時，得到如下序列：

出現在輸入數據序列或輸出DFT序列中的重排是大多數FFT算法的一個共有的特性。

算法一1)按列向儲存信號；2)計算每一行的點DFT；3)用乘上所得數組；4)計算每一列的點DFT；5)按行向讀取所得數組。

假如輸入序列按行向存儲，所得變換序列按列向存儲

算法二：1)按行向儲存信號；2)計算每一列的點DFT；3)用相位因子乘上所得數組；4)計算每一行的點DFT；5)按列向讀取所得數組。

10兩種算法其復雜性相同，但它們在計算的排列上不同的。

鄭州大學信息工程學院11FFT算法分類:時間抽選法

DIT:Decimation-In-Time頻率抽選法

DIF:Decimation-In-Frequency按時間抽取（DIT）的FFT算法1、算法原理 設序列點數N=2L，L

為整數。若不滿足，則補零鄭州大學信息工程學院12（DecimationInTime）將序列x(n)按n的奇偶分成兩組：N為2的整數冪的FFT算法稱基-2FFT算法。將N點DFT定義式分解為

兩個長度為N/2的DFT13記：………（1）（這一步利用：）鄭州大學信息工程學院14再利用周期性求X(k)的后半部分將上式表達的運算用一個專用“蝶形”信流圖表示。鄭州大學信息工程學院15注：a.上支路為加法，下支路為減法；

b.乘法運算的支路標箭頭和系數。用“蝶形結”表示上面運算的分解： 鄭州大學信息工程學院16鄭州大學信息工程學院17分解后的運算量：復數乘法復數加法一個N/2點DFT(N/2)2N/2(N/2–1)兩個N/2點DFTN2/2N(N/2–1)一個蝶形12N/2個蝶形N/2N總計運算量減少了近一半鄭州大學信息工程學院18進一步分解由于，仍為偶數，因此，兩個點DFT又可同樣進一步分解為4個點的DFT。鄭州大學信息工程學院19“蝶形”信流圖表示

N點DFT分解為四個N/4點的DFT鄭州大學信息工程學院20鄭州大學信息工程學院21“蝶形”信流圖表示

類似進一步分解類似的分解一直繼續下去，直到分解為最后的兩類蝶形運算為止(2點DFT).如上述N=8=23，N/4=2點中：鄭州大學信息工程學院221點DFTx(0)1點DFTx(4)X3(0)X3(1)鄭州大學信息工程學院23進一步簡化為蝶形流圖：X3(0)X3(1)x(0)x(4)因此8點FFT時間抽取方法的信流圖如下——鄭州大學信息工程學院24FFT運算量與運算特點

1．N=2L時，共有L=log2N級運算；每一級有N/2個蝶形結。2．每一級有N個數據中間數據），且每級只用到本級的轉入中間數據，適合于迭代運算。3．計算量：每級N/2次復乘法，N次復加。（每蝶形只乘一次，加減各一次）。共有L*N/2=N/2log2N次復乘法；復加法L*N=Nlog2N次。與直接DFT定義式運算量相比(倍數)N2/(Nlog2N)。當N大時，此倍數很大。鄭州大學信息工程學院25鄭州大學信息工程學院26比較DFT可以直觀看出，當點數N越大時，FFT的優點更突出。DITFFT中最主要的蝶形運算實現（1）參與蝶形運算的兩類結點（信號）間“距離”（碼地址）與其所處的第幾級蝶形有關；第m級的“結距離”為

(即原位計算迭代）（2）每級迭形結構為鄭州大學信息工程學院27鄭州大學信息工程學院28

蝶形運算兩節點的第一個節點為k值，表示成L位二進制數，左移L–m位，把右邊空出的位置補零，結果為r的二進制數。（3）的確定：第m級的r取值：四、FFT算法中一些概念

（1）“級”概念將N

點DFT先分成兩個N/2點DFT，再是四個N/4點DFT…直至N/2個兩點DFT.

每分一次稱為“一”級運算。因為N=2M所以N點DFT可分成M級如上圖所示依次m

=

0,

m

=

1

….

M-1共M級鄭州大學信息工程學院29（2）“組”概念鄭州大學信息工程學院30

每一級都有N/2個蝶形單元，例如：N=8,則每級都有4個蝶形單元。每一級的N/2個蝶形單元可以分成若干組，每一組具有相同的結構，相同的因子分布，第m級的組數為：例：N=8=23，分3級。m=0級,分成四組,每組系數為m=1級,分成二組,每組系數為m=2級,分成一組,每組系數為(3)因子的分布鄭州大學信息工程學院31結論：每由后向前（m由M-1-->0級）推進一級，則此系數為后級系數中偶數序號的那一半。鄭州大學信息工程學院32

例用FFT算法處理一幅N×N點的二維圖像，如用每秒可做10萬次復數乘法的計算機，當N=1024時，問需要多少時間（不考慮加法運算時間）？解當N=1024點時，FFT算法處理一幅二維圖像所需復數乘法約為 次，僅為直接計算DFT所需時間的10萬分之一。即原需要3000小時，現在只需要2分鐘。按頻率抽取（DIF）的FFT算法與DIT-FFT算法類似分解，但是抽取的是X(k)。即分解X(k)成奇數與偶數序號的兩個序列。設：N=2L，L為整數。將X(k)按k的奇偶分組前，先將輸入x(n)按n的順序分成前后兩半：33（DecimationInFrequency)一、算法原理鄭州大學信息工程學院34下面討論鄭州大學信息工程學院35按k的奇偶將X(k)分成兩部分：顯然：鄭州大學信息工程學院36令：用蝶型結構圖表示為：鄭州大學信息工程學院37x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2點DFTN/2點DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)鄭州大學信息工程學院38N/2仍為偶數，進一步分解：N/2→N/4鄭州大學信息工程學院39x3(0)x3(1)-1-1x4(0)x4(1)N/4點DFTN/4點DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)按照以上思路繼續分解，即一個N/2的DFT分解成兩個N/4點DFT，直到只計算2點的DFT，這就是DIF-FFT算法。鄭州大學信息工程學院402個1點的DFT蝶形流圖進一步簡化為蝶形流圖：1點DFTx3(0)1點DFTx3(1)X(0)X(4)X(0)X(4)x3(0)x3(1)鄭州大學信息工程學院41二、按頻率抽取FFT蝶形運算特點1）原位計算鄭州大學信息工程學院42-1L級蝶形運算，每級N/2個蝶形，每個蝶形結構：

m表示第m級迭代，k，j表示數據所在的行數鄭州大學信息工程學院432）蝶形運算對N=2L點FFT，輸入自然序，輸出倒位序，兩節點距離：2L-m=N/2m第m級運算：鄭州大學信息工程學院44

蝶形運算兩節點的第一個節點為k值，表示成L位二進制數，左移m-1位，把右邊空出的位置補零，結果為r的二進制數。存儲單元輸入序列x(n):N個存儲單元系數：N/2個存儲單元鄭州大學信息工程學院45三、DIT與DIF的異同基本蝶形不同DIT:先復乘后加減DIF:先減后復乘運算量相同都可原位運算DIT和DIF的基本蝶形互為轉置4、

基4-FFT算法

在DFT中當數據點數為4的冪時，采用基4算法計算更加有效。(1)按時間抽取的基4-FFT算法(2)按頻率抽取的基4-FFT算法46IDFT的FFT算法

（FFT應用一）

一、從定義比較分析鄭州大學信息工程學院47與DFT的比較：

1）、旋轉因子WN-kn

的不同；

2）、結果還要乘1/N。鄭州大學信息工程學院48二、實現算法——直接使用FFT程序的算法共軛FFT共軛乘1/N直接調用FFT子程序計算IFFT的方法：三、實序列的FFT算法1、實序列的FFT：減少運算量x(n)為實序列，X(k)共軛對稱：只需求得一半2、用一個N點DFT計算兩個實序列的N點DFT設x1(n)和x2(n)分別是長度為N的實序列令y(n)＝x1(n)＋jx2(n)，則

Y(k)=DFT[y(n)]

493、用一個N點DFT計算2N點實序列的DFT設x(n)為2N點實序列，按x(n)的序號為偶數和奇數抽取序列，分別作為新構造序列的實部和虛部，即則y(n)為N點復序列50對y(n)進行N點FFT,輸出Y(k),則根據D