第四章快速傅里葉變換（FFT）快速傅里葉變換（FFT）

離散傅里葉變換（DFT）

N次復(fù)數(shù)乘法，N－1次復(fù)數(shù)加法N快速傅里葉變換（FFT）1965年，圖基和庫(kù)利提出了快速傅里葉變換（FFT），不斷把長(zhǎng)序列分解成短序列，再進(jìn)行DFT，并利用周期性和對(duì)稱性來減少DFT的運(yùn)算次數(shù)。主要內(nèi)容

基2FFT算法

進(jìn)一步減少運(yùn)算量的措施分裂基FFT算法離散哈特萊變換（DHT）快速傅里葉變換（FFT）基2FFT算法快速傅里葉變換（FFT）時(shí)域抽取法FFT（DIT--FFT）頻域抽取法FFT（DIF--FFT）基2快速傅里葉算法IDFT的高效算法ABABCDCD運(yùn)算流圖A-1C-1BD-1-1以N＝4為例快速傅里葉變換（FFT）時(shí)域抽取法FFT（DIT--FFT）快速傅里葉變換（FFT）蝶形運(yùn)算試畫出N＝8的DFT的一次時(shí)域抽取分解圖快速傅里葉變換（FFT）-1-1-1-12個(gè)N/2點(diǎn)DFT運(yùn)算N/2個(gè)蝶形運(yùn)算快速傅里葉變換（FFT）快速傅里葉變換（FFT）-1-1-1-1-1-1-1-1快速傅里葉變換（FFT）-1-1-1-1-1-1-1-1-1-1-1-1快速傅里葉變換（FFT）-1-1-1-1-1-1-1-1-1-1-1-1快速傅里葉變換（FFT）DIT-FFT算法與直接計(jì)算DFT運(yùn)算量的比較快速傅里葉變換（FFT）DIT-FFT的運(yùn)算規(guī)律及編程思想蝶形運(yùn)算的規(guī)律和通式旋轉(zhuǎn)因子的規(guī)律性的存儲(chǔ)問題快速傅里葉變換（FFT）一、原位計(jì)算-1-1-1-1-1-1-1-1-1-1-1-1快速傅里葉變換（FFT）二、旋轉(zhuǎn)因子快速傅里葉變換（FFT）三、蝶形運(yùn)算規(guī)律快速傅里葉變換（FFT）四、編程思想及程序框圖開始送入x(n),MN=2M倒序L=1，MJ=0，B-1B=2L-1P=2M-LJ輸出結(jié)束k=J,N-1,2L快速傅里葉變換（FFT）四、序列的倒序-1-1-1-1-1-1-1-1-1-1-1-1輸出是自然序列，輸入稱為倒位序列，即二進(jìn)制數(shù)倒位快速傅里葉變換（FFT）

快速傅里葉變換（FFT）

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)制n2n1n0

倒位序二進(jìn)制n0n1n2

倒位順序n倒序數(shù)則是在M位二進(jìn)制數(shù)最高位加1，逢2向右進(jìn)位快速傅里葉變換（FFT）LH=N/2J=LHN1=N-2I=1，N1I>=JT=X(I)A(I)=X(J)A(J)=TK=LHNJ<KYJ=J+KJ=J-KK=K/2NY快速傅里葉變換（FFT）頻域抽取法FFT（DIF--FFT）快速傅里葉變換（FFT）快速傅里葉變換（FFT）-1-1-1-1快速傅里葉變換（FFT）-1-1-1-1-1-1-1-1快速傅里葉變換（FFT）-1-1-1-1-1-1-1-1-1-1-1-1快速傅里葉變換（FFT）比較DIF-FFT算法與DIT-FFT算法的異同點(diǎn)：1.運(yùn)算次數(shù)相同相同點(diǎn)2.公式、圖形類似不同點(diǎn)1.DIF-FFT：輸入是自然序列，輸出是到位序列；DIT-FFT：輸入是到位序列，輸出是自然序列。2.DIF-FFT：蝶形運(yùn)算是先乘后加減；DIT-FFT：蝶形運(yùn)算是先加減后乘?？焖俑道锶~變換（FFT）FFT的變形運(yùn)算支路傳輸比不變，改變輸入點(diǎn)，輸出點(diǎn)以及中間節(jié)點(diǎn)的排列-1-1-1-1-1-1-1-1-1-1-1-1快速傅里葉變換（FFT）IDFT的高效算法-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1乘法次數(shù)增加了（N/2)(M-1）次快速傅里葉變換（FFT）進(jìn)一步減少運(yùn)算量措施快速傅里葉變換（FFT）

1.多類蝶形運(yùn)算N=2M點(diǎn)FFT共需MN/2次復(fù)乘快速傅里葉變換（FFT）

1.多類蝶形運(yùn)算快速傅里葉變換（FFT）

1.多類蝶形運(yùn)算快速傅里葉變換（FFT）一類蝶形單元運(yùn)算：包括所有旋轉(zhuǎn)因子

1.多類蝶形運(yùn)算二類蝶形單元運(yùn)算：去掉旋轉(zhuǎn)因子三類蝶形單元運(yùn)算：再去掉旋轉(zhuǎn)因子四類蝶形單元運(yùn)算：再處理旋轉(zhuǎn)因子快速傅里葉變換（FFT）

2.旋轉(zhuǎn)因子的生成一種方法是在每級(jí)運(yùn)算中直接產(chǎn)生；二種方法是在FFT程序開始前預(yù)先計(jì)算出旋轉(zhuǎn)因子，存放在數(shù)組中，作為旋轉(zhuǎn)因子表，在程序執(zhí)行中直接查表?？焖俑道锶~變換（FFT）

3.實(shí)序列的FFT算法例1：設(shè)x(n)是長(zhǎng)度為2N的有限長(zhǎng)實(shí)序列，X(k)為x(n)的2N點(diǎn)DFT。要求：試設(shè)計(jì)用一次N點(diǎn)FFT完成計(jì)算X(k)的高效算法。解：本題的解題思路是DIT－FFT思想；在時(shí)域分別抽取偶數(shù)點(diǎn)和奇數(shù)點(diǎn)x(n)，得到兩個(gè)N點(diǎn)實(shí)序列x1(n)和x2(n)：x1(n)=x(2n),n=0,1,……,N-1

x2(n)=x(2n+1),n=0,1,……,N-1根據(jù)DIT－FFT的思想，只要求得x1(n)和x2(n)的N點(diǎn)DFT，再經(jīng)過簡(jiǎn)單的一級(jí)蝶形運(yùn)算就可得到x(n)的2N點(diǎn)DFT。因?yàn)閤1(n)和x2(n)均為實(shí)序列，所以根據(jù)DFT的共軛對(duì)稱性，可用一次N點(diǎn)FFT求得X1(k)和X2(k)。做法如下：令y(n)=x1(n)+jx2(n)Y(k)=DFT[y(n)]則X1(k)=DFT[x1(n)]=Yep(k)=[Y(k)+Y*(N-k)]/2jX2(k)=DFT[x2(n)]=Yop(k)=[Y(k)-Y*(N-k)]/22N點(diǎn)DFT[x(n)]=X(k)可由X1(k)和X2(k)得到：

X(k)=X1(k)+W2NkX2(k)X(k+N)=X1(k)-W2NkX2(k),k=0,1,…,N-1這樣，通過一次N點(diǎn)FFT計(jì)算完成了計(jì)算2N點(diǎn)DFT。例2：設(shè)x(n)是長(zhǎng)度為2N的有限長(zhǎng)實(shí)序列，X(k)為x(n)的2N點(diǎn)DFT。若已知X(k)，要求：試設(shè)計(jì)用一次N點(diǎn)IFFT完成計(jì)算x(n)的高效算法。解：設(shè)x1(n)=x(2n),n=0,1,……,N-1

x2(n)=x(2n+1),n=0,1,……,N-1 X1(k)=DFT[x1(n)],k=1,1,…,N-1

X2(k)=DFT[x2(n)],k=1,1,…,N-1

由DIT－FFT的算法，有以下關(guān)系式：

X(k)=X1(k)+W2NkX2(k),k=1,1,…,N-1X(k+N)=X1(k)-W2NkX2(k)

由以上兩可解出X1(k)和X2(k)。

X1(k)=[X(k)+X(k+N)]/2X2(k)=W2N-k[X(k)–X(k+N)]/2由上面分析可得出運(yùn)算過程如下： （1）由X(k)計(jì)算出X1(k)和X2(k)； （2）由X1(k)和X2(k)構(gòu)成N點(diǎn)頻域序列Y(k)：

Y(k)=X1(k)+jX2(k)=Yep(k)+Yop(k)其中Yep(k)=X1(k)，Yop(k)=jX2(k)，進(jìn)行N點(diǎn)IFFT運(yùn)算，得到

y(n)=IFFT[Y(k)]=Re[y(n)]+jIm[y(n)],n=0,1,…,N-1由DFT的共軛對(duì)稱性

Re[y(n)]=[y(n)+y*(n)]/2=DFT[Yep(k)]=x1(n)jIm[y(n)]=[y(n)-y*(n)]/2=DFT[Yop(k)]=jx2(n)由x1(n)和x2(n)合成x(n)：當(dāng)n=偶數(shù)（n=0,1,…,2N-1）時(shí)x(n)=x1(n/2)當(dāng)n=奇數(shù)（n=0,1,…,2N-1）時(shí)x(n)=x2((n-1)/2)分裂基FFT算法快速傅里葉變換（FFT）1984年，法國(guó)的杜梅爾和霍爾曼將基2和基4分解糅合在一起，提出了分裂基FFT算法，其運(yùn)算量有所減少，運(yùn)算流圖相似，運(yùn)算程序較短，是一種實(shí)用的高效算法?？焖俑道锶~變換（FFT）快速傅里葉變換（FFT）快速傅里葉變換（FFT）快速傅里葉變換（FFT）快速傅里葉變換（FFT）快速傅里葉變換（FFT）L形蝶形圖一個(gè)N點(diǎn)DFT可分解成一個(gè)N/2點(diǎn)DFT和兩個(gè)N/4點(diǎn)DFT快速傅里葉變換（FFT）-1-1-j-1快速傅里葉變換（FFT）離散哈特萊變換（DHT）快速傅里葉變換（FFT）計(jì)算出X(k)的前N/2個(gè)值，則后N/2個(gè)值可求直接對(duì)實(shí)序列進(jìn)行實(shí)數(shù)域變換的離散哈特萊變換快速傅里葉變換（FFT）證明：快速傅里葉變換（FFT）證明：快速傅里葉變換（FFT）

DHT的核函數(shù)是DFT核函數(shù)的實(shí)部與虛部之和快速傅里葉變換（FFT）快速傅里葉變換（FFT）1.DHT是實(shí)值變換2.DHT的正反變換具有相同形式DHT的主要優(yōu)點(diǎn)：3.DHT與DFT間的關(guān)系簡(jiǎn)單快速傅里葉變換（FFT）

1.DFT的線性快速傅里葉變換（FFT）

2.X(N-n）的DHT快速傅里葉變換（FFT）證明：快速傅里葉變換（FFT）

3.循環(huán)移位性質(zhì)快速傅里葉變換（