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

第四章

快速傅里葉變換

（FFT）主要內(nèi)容4.1引言4.2DFT的問題及改進(jìn)途徑4.3時(shí)間抽取（DIT）的FFT算法4.4頻率抽?。―IF）的FFT算法4.5IDFT的FFT算法（FFT應(yīng)用一）§4.1引言FFT:

FastFourierTransform1965年，Cooley-Turky發(fā)表文章《機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法》，提出FFT算法，解決DFT運(yùn)算量太大，在實(shí)際使用中受限制的問題。FFT的應(yīng)用。頻譜分析、濾波器實(shí)現(xiàn)、實(shí)時(shí)信號(hào)處理等。典型應(yīng)用：信號(hào)頻譜計(jì)算、系統(tǒng)分析等

系統(tǒng)分析

頻譜分析與功率譜計(jì)算§4.2直接計(jì)算DFT的問題及改進(jìn)途徑1、DFT與IDFT2、DFT與IDFT運(yùn)算特點(diǎn)復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)X(k)NN–

1N個(gè)X(k)(N點(diǎn)DFT)N2N(N–

1)同理：IDFT運(yùn)算量與DFT相同。實(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)4N22N(2N–

1)3、降低DFT運(yùn)算量的考慮FFT算法分類:時(shí)間抽選法

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

DIF:Decimation-In-Frequency§4.3按時(shí)間抽取（DIT）的FFT算法（DecimationInTime）1、算法原理 設(shè)序列點(diǎn)數(shù)N=2L，L

為整數(shù)。若不滿足，則補(bǔ)零將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱基-2FFT算法。

將N點(diǎn)DFT定義式分解為兩個(gè)長(zhǎng)度為N/2的DFT記：………（1）（這一步利用：）再利用周期性求X(k)的后半部分將上式表達(dá)的運(yùn)算用一個(gè)專用“蝶形”信流圖表示。用“蝶形結(jié)”表示上面運(yùn)算的分解： 分解后的運(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)算量減少了近一半進(jìn)一步分解由于，仍為偶數(shù)，因此，兩個(gè)點(diǎn)DFT又可同樣進(jìn)一步分解為4個(gè)點(diǎn)的DFT?！暗巍毙帕鲌D表示

N點(diǎn)DFT分解為四個(gè)N/4點(diǎn)的DFT這樣逐級(jí)分解，直到2點(diǎn)DFT當(dāng)N=8時(shí)，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1FFT運(yùn)算量與運(yùn)算特點(diǎn)

1．N=2L時(shí)，共有L=log2N級(jí)運(yùn)算；每一級(jí)有N/2個(gè)蝶形結(jié)。2．計(jì)算量：每級(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ù)很大。比較DFT可以直觀看出，當(dāng)點(diǎn)數(shù)N越大時(shí)，F(xiàn)FT的優(yōu)點(diǎn)更突出。按時(shí)間抽取FFT蝶形運(yùn)算特點(diǎn)

1、關(guān)于FFT運(yùn)算的混序與順序處理（位倒序處理）由于輸入序列按時(shí)間序位的奇偶抽取，故輸入序列是混序的，為此需要先進(jìn)行混序處理?；煨蛞?guī)律：

x(n)按n位置進(jìn)行碼位（二進(jìn)制）倒置規(guī)律輸入，而非自然排序，即得到混序排列。所以稱為位倒序處理。倒位序自然序0000000010041001010220101106301100114100101551010113611011177111倒位序例 計(jì)算，。計(jì)算 點(diǎn)FFT。用時(shí)間抽取輸入倒序算法，問倒序前寄存器的數(shù)和倒序后的數(shù)據(jù)值？解：倒序前倒序 倒序?yàn)榈剐蚝驞ITFFT中最主要的蝶形運(yùn)算實(shí)現(xiàn)（1）參與蝶形運(yùn)算的兩類結(jié)點(diǎn)（信號(hào)）間“距離”（碼地址）與其所處的第幾級(jí)蝶形有關(guān)；第m級(jí)的“結(jié)距離”為

(即原位計(jì)算迭代）（2）每級(jí)迭形結(jié)構(gòu)為DIT算法的其他形式流圖只要保持各節(jié)點(diǎn)所連的支路及其傳輸系數(shù)不變，則不論節(jié)點(diǎn)位置怎樣排列所得流圖總是等效的。DIT算法的其他形式流圖輸入倒位序輸出自然序輸入自然序輸出倒位序輸入輸出均自然序相同幾何形狀輸入倒位序輸出自然序輸入自然序輸出倒位序參考P154-155時(shí)間抽取、輸入自然順序、輸出倒位序的FFT流圖

例用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分鐘。

§4.4按頻率抽?。―IF）的FFT算法與DIT-FFT算法類似分解，但是抽取的是X(k)。即分解X(k)成奇數(shù)與偶數(shù)序號(hào)的兩個(gè)序列。設(shè)：N=2L，L為整數(shù)。將X(k)按k的奇偶分組前，先將輸入x(n)按n的順序分成前后兩半：（DecimationInFrequency)一、算法原理下面討論按k的奇偶將X(k)分成兩部分：顯然：令：用蝶型結(jié)構(gòu)圖表示為：x1(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)N/2仍為偶數(shù)，進(jìn)一步分解：N/2→N/4x3(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算法。二、按頻率抽取FFT蝶形運(yùn)算特點(diǎn)1）原位計(jì)算-1L級(jí)蝶形運(yùn)算，每級(jí)N/2個(gè)蝶形，每個(gè)蝶形結(jié)構(gòu)：

m表示第m級(jí)迭代，k，j表示數(shù)據(jù)所在的行數(shù)2）蝶形運(yùn)算對(duì)N=2L點(diǎn)FFT，輸入自然序，輸出倒位序，兩節(jié)點(diǎn)距離：2L-m=N/2m第m級(jí)運(yùn)算：三、DIT與DIF的異同基本蝶形不同DIT:先復(fù)乘后加減DIF:先加減后復(fù)乘運(yùn)算量相同DIT和DIF的基本蝶形互為轉(zhuǎn)置§4.5IDFT的FFT算法

（FFT應(yīng)用一）