數(shù)字信號處理(中澳雙語8-1)-第二十講

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

快速傅立葉變換

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

對每個特定k,

X(k)的

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

N

個復(fù)乘；

計算整個DFT

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

個復(fù)乘；通過利用

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

Nlog2N

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

8對每一列計算5點DFT

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

出現(xiàn)在輸入數(shù)據(jù)序列或輸出DFT序列中的重排是大多數(shù)FFT算法的一個共有的特性。

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

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

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

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

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

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

DIF:Decimation-In-Frequency按時間抽?。―IT）的FFT算法1、算法原理 設(shè)序列點數(shù)N=2L，L

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

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

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

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

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

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

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

蝶形運算兩節(jié)點的第一個節(jié)點為k值，表示成L位二進制數(shù)，左移L–m位，把右邊空出的位置補零，結(jié)果為r的二進制數(shù)。（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級鄭州大學(xué)信息工程學(xué)院29（2）“組”概念鄭州大學(xué)信息工程學(xué)院30

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

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

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

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

基4-FFT算法

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

（FFT應(yīng)用一）

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

1）、旋轉(zhuǎn)因子WN-kn

的不同；

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

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

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