1、第四章快速傅里葉變換（FFT）,主要內(nèi)容,DIT-FFT算法 DIF-FFT算法 IFFT算法 Chirp-FFT算法 線性卷積的FFT算法,4.1 引言,FFT: Fast Fourier Transform 1965年，Cooley-Turky 發(fā)表文章機(jī)器計(jì)算傅里葉級數(shù)的一種算法，提出FFT算法，解決DFT運(yùn)算量太大，在實(shí)際使用中受限制的問題。 FFT的應(yīng)用。頻譜分析、濾波器實(shí)現(xiàn)、實(shí)時(shí)信號處理等。 DSP芯片實(shí)現(xiàn)。TI公司的TMS 320c30，10MHz時(shí)鐘，基2-FFT1024點(diǎn)FFT時(shí)間15ms。,典型應(yīng)用：信號頻譜計(jì)算、系統(tǒng)分析等,系統(tǒng)分析,頻譜分析與功率譜計(jì)算,4.2 直接計(jì)算

2、DFT的問題及改進(jìn)途徑,1、 DFT與IDFT,2、DFT與IDFT運(yùn)算特點(diǎn),同理：IDFT運(yùn)算量與DFT相同。,3、降低DFT運(yùn)算量的考慮,FFT算法分類:,時(shí)間抽選法 DIT: Decimation-In-Time 頻率抽選法 DIF: Decimation-In-Frequency,4.3 按時(shí)間抽?。―IT）的FFT算法,（Decimation In Time）,1、算法原理 設(shè)序列點(diǎn)數(shù) N = 2L，L 為整數(shù)。 若不滿足，則補(bǔ)零,將序列x(n)按n的奇偶分成兩組：,N為2的整數(shù)冪的FFT算法稱基-2FFT算法。,將N點(diǎn)DFT定義式分解為兩個(gè)長度為N/2的DFT,記： （1）,再利用

3、周期性求X(k)的后半部分,將上式表達(dá)的運(yùn)算用一個(gè)專用“蝶形”信流圖表示。,注：a. 上支路為加法，下支路為減法； b. 乘法運(yùn)算的支路標(biāo)箭頭和系數(shù)。,用“蝶形結(jié)”表示上面運(yùn)算的分解：,分解后的運(yùn)算量：,運(yùn)算量減少了近一半,進(jìn)一步分解,由于 ， 仍為偶數(shù)，因此，兩個(gè) 點(diǎn) DFT又可同樣進(jìn)一步分解為4個(gè) 點(diǎn)的DFT。,“蝶形”信流圖表示,N點(diǎn)DFT分解為四個(gè)N/4點(diǎn)的DFT,類似的分解一直繼續(xù)下去，直到分解為最后的兩類蝶形運(yùn)算為止(2點(diǎn)DFT). 如上述N=8=23，N/4=2點(diǎn)中：,類似進(jìn)一步分解,進(jìn)一步簡化為蝶形流圖：,因此8點(diǎn)FFT時(shí)間抽取方法的信流圖如下,FFT運(yùn)算量與運(yùn)算特點(diǎn),1 N=

4、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ù)很大。,比較DFT,參考P150 表4-1 圖4-6,可以直觀看出，當(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í)間序位的奇偶抽取，故輸入

5、序列是混序的，為此需要先進(jìn)行混序處理。 混序規(guī)律： x(n)按n位置進(jìn)行碼位（二進(jìn)制）倒置規(guī)律輸入，而非自然排序，即得到混序排列。所以稱為位倒序處理。 位倒序?qū)崿F(xiàn)： （1）DSP實(shí)現(xiàn)采用位倒序?qū)ぶ?（2）通用計(jì)算機(jī)實(shí)現(xiàn)可以有兩個(gè)方法：一是嚴(yán)格按照位倒序含義進(jìn)行；二是倒進(jìn)位的加N/2。,倒位序,例計(jì)算 ， 。計(jì)算 點(diǎn)FFT。用時(shí)間抽取輸入倒序算法，問倒序前寄存器的數(shù) 和倒序后 的數(shù)據(jù)值？,解：倒序前 倒序 倒序?yàn)?倒序后,DIT FFT中最主要的蝶形運(yùn)算實(shí)現(xiàn),（1）參與蝶形運(yùn)算的兩類結(jié)點(diǎn)（信號）間“距離”（碼地址）與其所處的第幾級蝶形有關(guān)；第m級的“結(jié)距離”為 (即原位計(jì)算迭代） （2）每級迭形

6、結(jié)構(gòu)為,蝶形運(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取值：,DIT算法的其他形式流圖,輸入倒位序輸出自然序 輸入自然序輸出倒位序 輸入輸出均自然序 相同幾何形狀 輸入倒位序輸出自然序 輸入自然序輸出倒位序,參考P154-155,時(shí)間抽取、 輸入自然順序、 輸出倒位序的FFT流圖,例 用FFT算法處理一幅NN點(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ì)算D

7、FT所需時(shí)間的10萬分之一。 即原需要3000小時(shí)，現(xiàn)在只需要2 分鐘。,4.4 按頻率抽取（DIF）的FFT算法,與DIT-FFT算法類似分解，但是抽取的是X(k)。即分解X(k)成奇數(shù)與偶數(shù)序號的兩個(gè)序列。 設(shè)： N = 2L，L 為整數(shù)。將X(k)按k的奇偶分組前，先將輸入x(n)按n的順序分成前后兩半：,（Decimation In Frequency),一、算法原理,下面討論,按k的奇偶將X(k)分成兩部分：,顯然：,令：,用蝶型結(jié)構(gòu)圖表示為：,N/2仍為偶數(shù)，進(jìn)一步分解：N/2 N/4,按照以上思路繼續(xù)分解，即一個(gè)N/2的DFT分解成兩個(gè)N/4點(diǎn)DFT，直到只計(jì)算2點(diǎn)的DFT，這就

8、是DIF-FFT算法。,2個(gè)1點(diǎn)的DFT蝶形流圖,進(jìn)一步簡化為蝶形流圖：,二、按頻率抽取FFT蝶形運(yùn)算特點(diǎn),1）原位計(jì)算,L級蝶形運(yùn)算，每級N/2個(gè)蝶形，每個(gè)蝶形結(jié)構(gòu)：,m表示第m級迭代，k，j表示數(shù)據(jù)所在的行數(shù),2）蝶形運(yùn)算,對N=2L點(diǎn)FFT，輸入自然序，輸出倒位序， 兩節(jié)點(diǎn)距離：2L-m=N / 2m,第m級運(yùn)算：,蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為k值，表示成L位二進(jìn)制數(shù)，左移m-1位，把右邊空出的位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。,存儲(chǔ)單元,輸入序列x(n) : N個(gè)存儲(chǔ)單元,系數(shù) ：N / 2個(gè)存儲(chǔ)單元,三、DIT與DIF的異同,基本蝶形不同,DIT: 先復(fù)乘后加減,DIF: 先減后復(fù)乘,運(yùn)

9、算量相同,都可原位運(yùn)算,DIT和DIF的基本蝶形互為轉(zhuǎn)置,二、實(shí)現(xiàn)算法直接使用FFT程序的算法,直接調(diào)用FFT子程序計(jì)算IFFT的方法：,4.6 線性調(diào)頻Z變換（Chirp-Z變換）算法 （FFT應(yīng)用二）,單位圓與非單位圓采樣 （a） 沿單位圓采樣; (b) 沿AB弧采樣,螺線采樣,zk=AW-k, k=0, 1, , M-1,Chirp-Z變換的線性系統(tǒng)表示,由于系統(tǒng)的單位脈沖響應(yīng) 可以想象為頻率隨時(shí)間(n)呈線性增長的復(fù)指數(shù)序列。在雷達(dá)系統(tǒng)中,這種信號稱為線性調(diào)頻信號（Chirp Signal），因此，這里的變換稱為線性調(diào)頻Z變換。,一、基本算法思路,4.7 線性卷積的FFT算法（FFT應(yīng)

10、用三）,若L點(diǎn)x(n)，M點(diǎn)h(n)， 則直接計(jì)算其線性卷積y(n),需運(yùn)算量：,若系統(tǒng)滿足線性相位，即：,則需運(yùn)算量：,FFT法：以圓周卷積代替線性卷積,N,總運(yùn)算量： 次乘法,比較直接計(jì)算和FFT法計(jì)算的運(yùn)算量,討論：,1）當(dāng),2）當(dāng),x(n)長度很長時(shí)，將x(n)分為L長的若干小的片段，L與M可比擬。,1、重疊相加法,則：,輸出：,其中：,可以用圓周卷積計(jì)算：,選 ，上面圓周卷積可用FFT計(jì)算。,N,由于yi(n)長度為N，而xi(n)長度L ，必有M-1 點(diǎn)重疊， yi(n)應(yīng)相加才能構(gòu)成最后y(n)的。,重疊相加法圖形,和上面的討論一樣， 用FFT法實(shí)現(xiàn)重疊相加法的步驟如下: 計(jì)算N

11、點(diǎn)FFT， H(k)=DFTh(n)； 計(jì)算N點(diǎn)FFT，Xi(k)=DFTxi(n)； 相乘，Yi(k)=Xi(k)H(k)； 計(jì)算N點(diǎn)IFFT，yi(n)=IDFTYi(k)； 將各段yi(n)（包括重疊部分）相加。 重疊相加的名稱是由于各輸出段的重疊部分相加而得名的。,例 已知序列xn=n+2,0n12, hn=1,2,1試?yán)弥丿B相加法計(jì)算線性卷積, 取L=5 。,yn=2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14,解: 重疊相加法,x1n=2, 3, 4, 5, 6,x2n=7, 8, 9, 10, 11,x3n=12

12、,13, 14,y1n=2, 7, 12, 16, 20, 17, 6,y2n= 7, 22, 32, 36, 40, 32, 11,y3n=12, 37, 52, 41, 14,2、重疊保存法,此方法與上述方法稍有不同。 先將x(n)分段，每段L=N-M+1個(gè)點(diǎn)，這是相同的。 不同之處是，序列中補(bǔ)零處不補(bǔ)零，而在每一段的前邊補(bǔ)上前一段保留下來的（M-1）個(gè)輸入序列值， 組成L+M-1點(diǎn)序列xi(n) 。 如果L+M-12m， 則可在每段序列末端補(bǔ)零值點(diǎn)，補(bǔ)到長度為2m，這時(shí)如果用DFT實(shí)現(xiàn)h(n)和xi(n)圓周卷積，則其每段圓周卷積結(jié)果的前（M-1）個(gè)點(diǎn)的值不等于線性卷積值，必須舍去。,重疊保留法示意圖,重疊保留法示意圖,yk=2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14,x1k=0, 0, 2, 3, 4,x2k=3, 4, 5, 6 ,7,x3k=6 ,7 , 8, 9, 10,y1k= x1khk= 11, 4, 2, 7, 12,x4k=9, 10 , 11, 12,13,y2k= x2khk= 23, 17, 16, 20, 24,y3k= x3khk= 35, 29, 28, 32, 36,y4k= x4k