快速傅氏變換

第四章FFT下頁§4-3DIF的FFT算法§4-4IFFT算法§4-2按時(shí)間抽取(DIT)的FFT算法§4-1引言點(diǎn)擊進(jìn)入目下頁返回上頁§4-5FFT的應(yīng)用§4-1引言一.DFT的計(jì)算工作量

兩者的差別僅在指數(shù)的符號(hào)和因子1/N.下頁返回上頁通常x(n)和 都是復(fù)數(shù),所以計(jì)算一個(gè)X(k)的值需要N次復(fù)數(shù)乘法運(yùn)算,和 次復(fù)數(shù)加法運(yùn)算.那么,所有的X(k)就要N2次復(fù)數(shù)乘法運(yùn)算,N(N-1)次復(fù)數(shù)加法運(yùn)算.當(dāng)N很大時(shí),運(yùn)算量將是驚人的,如N=1024,則要完成1048576次(一百多萬次)運(yùn)算.這樣,難以做到實(shí)時(shí)處理.一個(gè)X(k)的值的工作量,如X(1)下頁返回上頁二.改進(jìn)的途徑1.的對稱性和周期性得:對稱性:周期性:下頁返回上頁

利用上述特性,可以將有些項(xiàng)合并,并將DFT分解為短序列,從而降低運(yùn)算次數(shù),提高運(yùn)算速度.1965年,庫利(cooley)和圖基(Tukey)首先提出FFT算法.對于N點(diǎn)DFT,僅需(N/2)log2N次復(fù)數(shù)乘法運(yùn)算.例如N=1024=210時(shí)，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%,速度提高20倍返回上頁§4-2按時(shí)間抽取(DIT)的FFT算法

—庫利-圖基算法一.算法原理(基2FFT)(一)N/2點(diǎn)DFT1.先將按n的奇偶分為兩組作DFT,設(shè)N=2L,不足時(shí),可補(bǔ)些零。這樣有:n為偶數(shù)時(shí):n為奇數(shù)時(shí):因此，下頁返回由于:所以,上式可表示為:(n為偶數(shù))(n為奇數(shù))下頁返回上頁(A)

其中,這里K的取值為[0，N-1]，上式不是標(biāo)準(zhǔn)的N/2點(diǎn)的DFT,若限定k只取前一半時(shí)，則得到如下兩點(diǎn)結(jié)論。2.兩點(diǎn)結(jié)論:(1)X

(k),X

(k)均為N/2點(diǎn)的DFT。(2)X(k)=X

(k)+W

X

(k)只能確定出X(k)的k=個(gè)；即前一半的結(jié)果。1212kN下頁返回上頁同理,這就是說,X1(k),X2(k)的后一半,分別等于其前一半的值。3.X(k)的后一半的確定由于（周期性）,所以:下頁返回上頁有式(A)得(A)

可見,X(k)的后一半，也完全由X1(k),X2

(k)的前一半所確定。*N點(diǎn)的DFT可由兩個(gè)N/2點(diǎn)的DFT來計(jì)算。又由于,所以下頁返回上頁實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算

前一半4.蝶形運(yùn)算

后一半（N/2個(gè)蝶形)(前一半)(后一半)1111-1由X1(k)、X2(k)表示X(k)的運(yùn)算是一種特殊的運(yùn)算-碟形運(yùn)算下頁返回上頁(1)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù): 復(fù)加次數(shù):(2)兩個(gè)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):

復(fù)加次數(shù):

(3)N/2個(gè)蝶形運(yùn)算的運(yùn)算量:復(fù)乘次數(shù):

復(fù)加次數(shù):

5.計(jì)算工作量分析復(fù)乘:復(fù)加:總共運(yùn)算量:按奇、偶分組后的計(jì)算量：*但是,N點(diǎn)DFT的復(fù)乘為N2;復(fù)加N(N-1);與分解后相比可知,計(jì)算工作點(diǎn)差不多減少

一半。下頁返回上頁

例如N=8

時(shí)的DFT,可以分解為兩個(gè)

N/2=4點(diǎn)的DFT.具體方法如下:

(1)n為偶數(shù)時(shí),即

分別記作:

下頁返回上頁(2)n為奇數(shù)時(shí),分別記作:下頁返回上頁

x1(0)=x(0)

x1(1)=x(2)

N/2點(diǎn)

x1(2)=x(4)DFT

x1(3)=x(6)

x2(0)=x(1)

x2(1)=x(3)

N/2點(diǎn)

x2(2)=x(5)

DFT

x2(3)=x(7)

12~~X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN2WN1WN0WN3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)(3)對X

(k)和X

(k)進(jìn)行蝶形運(yùn)算,前半部為

X(0)X(3),后半部分為X(4)X(7)

整個(gè)過程如下圖所示:下頁返回上頁

由于N=2

L

,所以N/2仍為偶數(shù),可以進(jìn)

一步把每個(gè)N/2點(diǎn)的序列再按其奇偶部分

分解為兩個(gè)N/4的子序列。例如，n為偶數(shù)時(shí)的

N/2點(diǎn)分解為:(二)N/4點(diǎn)DFT進(jìn)行N/4點(diǎn)的DFT,得到(偶中偶)(偶中奇)下頁返回上頁從而可得到前N/4的X1(k)后N/4的X1(k)為下頁返回上頁(奇中偶)(奇中奇)同樣對n為奇數(shù)時(shí)，N/2點(diǎn)分為兩個(gè)N/4點(diǎn)

的序列進(jìn)行DFT，則有:下頁返回上頁例如,N=8時(shí)的DFT可分解為四個(gè)N/4的DFT,

具體步驟如下:(1)將原序列x(n)的“偶中偶”部分:構(gòu)成N/4點(diǎn)DFT，從而得到X3(0),X3(1)。下頁返回上頁(2)將原序列x(n)的“偶中奇”部分:構(gòu)成N/4點(diǎn)DFT，從而得到X4(0),X4(1)。(3)將原序列x(n)的“奇中偶”部分:構(gòu)成N/4點(diǎn)DFT，從而得到X5(0),X5(1)。下頁返回上頁(4)將原序列x(n)的“奇中奇”部分:構(gòu)成N/4點(diǎn)DFT，從而得到X6(0),X6(1)。（5）由X3(0),X3(1),X4(0),X4(1)進(jìn)行碟形運(yùn)算,

得到X1(0),X1(1),X1(2),X1(3)。（6）由X5(0),X5(1),X6(0),X6(1)進(jìn)行碟形運(yùn)算,

得到X2(0),X2(1),X2(2),X2(3)。下頁返回上頁

(0)=

(0)=(0)

N/4

(1)=

(2)=(4)

DFT

(0)=

(1)=(2)

N/4

(1)=

(3)=(6)

DFT

(0)=

(0)=(1)

N/4

(1)=

(2)=(5)

DFT

(0)=

(1)=(3)

N/4

(1)=

(3)=(7)

DFT313141415252626202NN02NNWWWW0123NNNN-1-1-1-2-1-1WWWWX

(0)X

(1)X

(0)X

(1)X

(0)X

(1)X

(0)X

(1)33445566X

(0)X

(1)X

(2)X

(3)X

(0)X

(1)X

(2)X

(3)11122221X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)（7）由X1(0),X1(1),X1(2),X1(3)，X2(0),X2(1),X2(2),X2(3)進(jìn)行碟形運(yùn)算,得到X(0),X(1),X(2),X(3)X(4),X(5),X(6),X(7)。下頁返回上頁這樣,又一次分解,得到四個(gè)N/4點(diǎn)DFT,

兩級(jí)蝶形運(yùn)算,其運(yùn)算量有大約減少一半

即為N點(diǎn)DFT的1/4。

對于N=8時(shí)DFT,N/4點(diǎn)即為兩點(diǎn)DFT,因此

下頁返回上頁

亦即,下頁返回上頁

(0)

(4)

(2)

(6)

(1)

(5)

(3)

(7)WN0WN0WN0W0N-1-1-1-1X

(0)X

(1)X

(0)X

(1)X

(0)X

(1)X

(0)X

(1)33445566WN0WN2WN0WN2-1-1-1-1X

(0)X

(1)X

(2)X

(3)X

(0)X

(1)X

(2)X

(3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)因此,8點(diǎn)DFT的FFT的運(yùn)算流圖如下下頁返回上頁DIT和DIF算法演示DITDIF下頁返回上頁

這種FFT算法,是在時(shí)間上對輸入序列

的次序是屬于偶數(shù)還是屬于奇數(shù)來進(jìn)行分解的,所以稱作按時(shí)間抽取的算法。

二.運(yùn)算量

由上述分析可知,N=8需三級(jí)蝶形運(yùn)算N=2=8,由此可知,N=2L

共需L級(jí)蝶形運(yùn)算,而且每級(jí)都由N/2個(gè)蝶形運(yùn)算

組成,每個(gè)蝶形運(yùn)算有一次復(fù)乘,兩次復(fù)加。(DIT)3下頁返回上頁

因此,N點(diǎn)的FFT的運(yùn)算量為復(fù)乘:mF=（N/2）L=（N/2）log2N復(fù)加:aF=NL=Nlog2N

由于計(jì)算機(jī)的乘法運(yùn)算比加法運(yùn)算所

需的時(shí)間多得多，故以乘法作為比較基準(zhǔn).如表4-1所示）。

下頁返回上頁

(0)=X0(0)

X1(0)

X2(0)X3(0)=X(0)

(4)=X0(1)

X1(1)X2(1)X3(1)=X(1)

(2)=X0(2)

X3(2)=X(2)

(6)=X0(3)

X3(3)=X(3)

(1)=X0(4)

X1(4)X2(4)X3(4)=X(4)

(5)=X0(5)

X3(5)=X(5)

(3)=X0(6)

X3(6)=X(6)

(7)=X0(7)

X1(7)X2(7)X3(7)=X(7)WWWWN0N0N0N0-1-1-1-1WWWWN0N2N0N2-1-1-1-1WWWWNNNN0123...........三.DIT的FFT算法的特點(diǎn)

1.原位運(yùn)算輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲(chǔ)器。下頁返回上頁

設(shè)用m(m=1,2,…,L)表示第m列;用k,j表示蝶形輸入數(shù)據(jù)所在的（上/下）行數(shù)(0,1,2,…,N-1);這時(shí)任何一個(gè)蝶形運(yùn)算可用下面通用式表示，即

由運(yùn)算流圖可知,一共有N個(gè)輸入/出行,一共有l(wèi)og2N=L列（級(jí)）蝶形運(yùn)算(基本迭代運(yùn)算).下頁返回上頁

所以,當(dāng)m=1時(shí),則有（前兩個(gè)蝶形）

下頁返回上頁

當(dāng)m=2時(shí),則有（前兩個(gè)蝶形）

當(dāng)m=3時(shí),則有（前兩個(gè)蝶形）

下頁返回上頁

可見,在某列進(jìn)行蝶形運(yùn)算的任意兩個(gè)節(jié)點(diǎn)(行)k和j的節(jié)點(diǎn)變量就完全可以確定蝶形運(yùn)算的結(jié)果,與其它行(節(jié)點(diǎn))無關(guān)。這樣,蝶形運(yùn)算的兩個(gè)輸出值仍可放回蝶形運(yùn)算的兩個(gè)輸入所在的存儲(chǔ)器中,即實(shí)現(xiàn)所謂原位運(yùn)算。每一組(列)有N/2個(gè)蝶形運(yùn)算,所以只需N個(gè)存儲(chǔ)單元，可以節(jié)

省存儲(chǔ)單元。下頁返回上頁

2

倒位序規(guī)律

由圖可知,輸出X(k)按正常順序排列在存儲(chǔ)單元,而輸入是按順序:這種順序稱作倒位序,即二進(jìn)制數(shù)倒位。下頁返回上頁n=00n=10n=01n=11n=01n=1101010101

(n2)x(000)0x(100)4x(010)2x(110)6x(001)1x(101)5x(011)3x(111)7（偶）（奇）

這是由奇偶分組造成的,以N=8為例

說明如下:下頁返回上頁

3.倒位序?qū)崿F(xiàn)

輸入序列先按自然順序存入存儲(chǔ)單

元,然后經(jīng)變址運(yùn)算來實(shí)現(xiàn)倒位序排列

設(shè)輸入序列的序號(hào)為n,二進(jìn)制為

(n2n1n0)2,倒位序順序用

表示,其倒位序二進(jìn)制為(n0n1n2)2,例如，N=8時(shí)如下表：

下頁返回上頁

00

0

00

0

00

10

0

11

0

04

20

1

00

1

02

30

1

11

1

06

41

0

00

0

11

51

0

11

0

15

61

1

00

1

13

71

1

11

1

17自然順序n二進(jìn)制nnn倒位序二進(jìn)制nnn倒位順序n^210012下頁返回上頁A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)變址處理方法存儲(chǔ)單元自然順序變址倒位序4.蝶形運(yùn)算兩節(jié)點(diǎn)的距離:2m-1

其中,m表示第m列,且m=1,…,L

例如N=8=23,第一級(jí)(列)距離為21-1=1,第二級(jí)(列)距離為22-1=2，

第三級(jí)(列)距離為23-1=4。下頁返回上頁Nr的確定(僅給出方法)

考慮蝶形運(yùn)算兩節(jié)點(diǎn)的距離為2m-1,蝶

形運(yùn)算可表為

Xm(k)=Xm-1(k)+Xm-1(k+2m-1)WNr

Xm(k+2m-1)=Xm-1(k)-Xm-1(k+2m-1)WNr

由于N為已知,所以將r的值確定即可。為此，令k=(n2n1n0)2,再將k=(n2n1n0)2

左移(L-m)位,右邊位置補(bǔ)零,就可得到(r)2

的值，即(r)2=(k)22L-m。下頁返回上頁

例如N=8=23

(1)k=2,m=3

的r值,∵k=2=(010)2

左移L-m=3-3=0,∴

r=(010)2=2;(2)k=3,m=3

的r值;k=

3=(011)2,左移0位,r=3；(3)k=5,m=2的值;k=5=(101)2

左移L-m=1位

r=(010)2=2。下頁返回上頁

6.存儲(chǔ)單元

存輸入序列(n),n=0,1,,N-1,計(jì)N

個(gè)單元;

存放系數(shù),r=0,1,,（N/2）-1,

需N/2個(gè)存儲(chǔ)單元；共計(jì)(N+N/2)個(gè)存儲(chǔ)單元。返回上頁§4-3按頻率抽?。―IF）的FFT算法(桑德—圖基算法)

一.算法原理

點(diǎn)DFT的另一種表達(dá)形式下頁返回

由于

故

因此

X(k)可表為

下頁返回上頁

點(diǎn)DFT按k的奇偶分組可分為兩個(gè)N/2的DFT

當(dāng)k為偶數(shù),即k=2r時(shí),(-1)k=1；

當(dāng)k為奇數(shù),即k=2r+1時(shí)(-1)k=-1。這時(shí)

X(k)

可分為兩部分：

k為偶數(shù)時(shí)：下頁上頁返回可見,上面兩式均為N/2的DFT。K為奇數(shù)時(shí)下頁上頁返回K為偶數(shù)時(shí)3.蝶形運(yùn)算-1下頁上頁返回**N點(diǎn)長的經(jīng)過這兩種函數(shù)關(guān)系分解成兩個(gè)N/2長的子序列和，運(yùn)算量將為降為原來的一半。-1-1-1-1WWWWNNNN01234.N=8時(shí),按k的奇偶分解過程先蝶形運(yùn)算，后DFT:下頁上頁返回

5.仿照DIT的方法再將N/2點(diǎn)DFT按k的奇偶分解為兩個(gè)N/4點(diǎn)的DFT,如此進(jìn)行下去,直至分解為2點(diǎn)DFT。

下頁上頁返回

(0)X(0)

(1)X(4)

(2)X(2)

(3)X(6)

(4)X(1)

(5)X(5)

(6)X(3)

(7)X(7)-1-1-1-1WWWWNNNN0123-1-1-1-1WWWWNNNN0202-1-1-1-1WWWWNNNN0000例如N=8時(shí)DIF的FFT流圖如下：下頁上頁返回

每級(jí)(列)都是由N/2個(gè)蝶形運(yùn)算構(gòu)

成,即

-1WNr下頁上頁返回三.蝶形運(yùn)算兩節(jié)點(diǎn)的距離一般公式為2L-m=N/2m

例如N=23=8：(1)m=1時(shí)的距離為8/2=4；(2)m=2

時(shí)的距離為8/4=2;(3)m=3

時(shí)的距離為8/8=1。下頁上頁返回r的求法：

k=(n2n1n0),左移m-1位,右邊空出補(bǔ)零,得(r)2,亦即(r)2=(k)2

2m-1.例如,N=8:(1)m=1,k=2,k=(010)2

左移0位,(r)2=(010)2=2;(2)m=2,k=1,k=(001)2

左移1位,(r)2=(010)2=2;(3)m=2,k=5,k=(101)2

左移1位,(r)2=(010)2=2.四.的計(jì)算

由于DIF蝶形運(yùn)算的兩節(jié)點(diǎn)的距離為

N/2m,

所以蝶形運(yùn)算可表為：下頁上頁返回1.相同點(diǎn)

(1)進(jìn)行原位運(yùn)算；

(2)運(yùn)算量相同,均為（N/2)

Log2N次復(fù)乘,N

Log2N次復(fù)加。

2.不同點(diǎn)

(1)DIT輸入為倒位序,輸出為自然順序；

DIF正好與此相反。但DIT也有輸入為自然順序,輸出為倒位序的情況。五.DIF法與DIT法的異同下頁上頁返回(2)蝶形運(yùn)算不同a.(DIT)用矩陣表示=11下頁上頁返回b.(DIF)用矩陣表示=11下頁上頁返回(3)兩種蝶形運(yùn)算的關(guān)系互為轉(zhuǎn)置（矩陣）；

將流圖的所有支路方向都反向,交換輸入和輸出，即可得到另一種蝶形。a.(DIT)b.(DIF)1111下頁上頁返回原位運(yùn)算FFT的特點(diǎn)（N=2L）上頁返回

§4-4IFFT算法一、稍微變動(dòng)FFT程序和參數(shù)可實(shí)現(xiàn)IFFT

下頁返回上頁IFFT的快速算法實(shí)現(xiàn)可以有三種手段：比較兩式可知,只要DFT的每個(gè)系數(shù)

換成,最后再乘以常數(shù)1/N就可以得到IDFT的快速算法--IFFT。另外,可以將常數(shù)1/N分配到每級(jí)運(yùn)算中,∵,也就是每級(jí)蝶形運(yùn)算均乘以1/2。

下頁返回上頁二、不改(FFT)的程序直接實(shí)現(xiàn)IFFT

下頁返回上頁這就是說,先將X(k)取共軛,即將X(k)的虛部乘-1，直接利用FFT程序計(jì)算DFT；然后再取一次共軛；最后再乘1/N,即得(n)。所以FFT,IFFT可用一個(gè)子程序。下頁返回上頁IFFT時(shí)間抽取IFFT流圖（N=8)返回上頁三、第三種方法—原理§4-5

FFT的應(yīng)用FFT是DFT的快速算法,因而DFT的理論、性質(zhì)在FFT中也是有效的.如離散傅里葉反變換、線性卷積與線性相關(guān)都可以用FFT算法來減少其計(jì)算量.下頁返回線性卷積的FFT算法一.線性卷積的長度

設(shè)一離散線性移不變系統(tǒng)的沖激響應(yīng)為,其輸入信號(hào)為.其輸出為.并且

的長度為L點(diǎn),的長度為M點(diǎn),則：

下頁返回上頁以實(shí)例說明：01

2

3123.。1。下頁