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

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

快速傅立葉變換

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

對每個(gè)特定k,

X(k)的

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

N

個(gè)復(fù)乘；

計(jì)算整個(gè)DFT

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

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

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

Nlog2N

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

8對每一列計(jì)算5點(diǎn)DFT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為k值，表示成L位二進(jìn)制數(shù)，左移L–m位，把右邊空出的位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。（3）的確定：第m級的r取值：四、FFT算法中一些概念

（1）“級”概念將N

點(diǎn)DFT先分成兩個(gè)N/2點(diǎn)DFT，再是四個(gè)N/4點(diǎn)DFT…直至N/2個(gè)兩點(diǎn)DFT.

每分一次稱為“一”級運(yùn)算。因?yàn)镹=2M所以N點(diǎn)DFT可分成M級如上圖所示依次m

=

0,

m

=

1

….

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

每一級都有N/2個(gè)蝶形單元，例如：N=8,則每級都有4個(gè)蝶形單元。每一級的N/2個(gè)蝶形單元可以分成若干組，每一組具有相同的結(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級）推進(jìn)一級，則此系數(shù)為后級系數(shù)中偶數(shù)序號的那一半。鄭州大學(xué)信息工程學(xué)院32

例用FFT算法處理一幅N×N點(diǎn)的二維圖像，如用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？解當(dāng)N=1024點(diǎn)時(shí)，F(xiàn)FT算法處理一幅二維圖像所需復(fù)數(shù)乘法約為 次，僅為直接計(jì)算DFT所需時(shí)間的10萬分之一。即原需要3000小時(shí)，現(xiàn)在只需要2分鐘。按頻率抽?。―IF）的FFT算法與DIT-FFT算法類似分解，但是抽取的是X(k)。即分解X(k)成奇數(shù)與偶數(shù)序號的兩個(gè)序列。設(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點(diǎn)DFTN/2點(diǎn)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ù)，進(jìn)一步分解：N/2→N/4鄭州大學(xué)信息工程學(xué)院39x3(0)x3(1)-1-1x4(0)x4(1)N/4點(diǎn)DFTN/4點(diǎn)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ù)分解，即一個(gè)N/2的DFT分解成兩個(gè)N/4點(diǎn)DFT，直到只計(jì)算2點(diǎn)的DFT，這就是DIF-FFT算法。鄭州大學(xué)信息工程學(xué)院402個(gè)1點(diǎn)的DFT蝶形流圖進(jìn)一步簡化為蝶形流圖：1點(diǎn)DFTx3(0)1點(diǎn)DFTx3(1)X(0)X(4)X(0)X(4)x3(0)x3(1)鄭州大學(xué)信息工程學(xué)院41二、按頻率抽取FFT蝶形運(yùn)算特點(diǎn)1）原位計(jì)算鄭州大學(xué)信息工程學(xué)院42-1L級蝶形運(yùn)算，每級N/2個(gè)蝶形，每個(gè)蝶形結(jié)構(gòu)：

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

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

基4-FFT算法

在DFT中當(dāng)數(shù)據(jù)點(diǎn)數(shù)為4的冪時(shí)，采用基4算法計(jì)算更加有效。(1)按時(shí)間抽取的基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二、實(shí)現(xiàn)算法——直接使用FFT程序的算法共軛FFT共軛乘1/N直接調(diào)用FFT子程序計(jì)算IFFT的方法：三、實(shí)序列的FFT算法1、實(shí)序列的FFT：減少運(yùn)算量x(n)為實(shí)序列，X(k)共軛對稱：只需求得一半2、用一個(gè)N點(diǎn)DFT計(jì)算兩個(gè)實(shí)序列的N點(diǎn)DFT設(shè)x1(n)和x2(n)分別是長度為N的實(shí)序列令y(n)＝x1(n)＋jx2(n)，則

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

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