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

離散傅里葉變換（DFT）

N次復數乘法，N－1次復數加法N快速傅里葉變換（FFT）1965年，圖基和庫利提出了快速傅里葉變換（FFT），不斷把長序列分解成短序列，再進行DFT，并利用周期性和對稱性來減少DFT的運算次數。主要內容

基2FFT算法

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

倒位序二進制n0n1n2

倒位順序n倒序數則是在M位二進制數最高位加1，逢2向右進位快速傅里葉變換（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算法的異同點：1.運算次數相同相同點2.公式、圖形類似不同點1.DIF-FFT：輸入是自然序列，輸出是到位序列；DIT-FFT：輸入是到位序列，輸出是自然序列。2.DIF-FFT：蝶形運算是先乘后加減；DIT-FFT：蝶形運算是先加減后乘。快速傅里葉變換（FFT）FFT的變形運算支路傳輸比不變，改變輸入點，輸出點以及中間節點的排列-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乘法次數增加了（N/2)(M-1）次快速傅里葉變換（FFT）進一步減少運算量措施快速傅里葉變換（FFT）

1.多類蝶形運算N=2M點FFT共需MN/2次復乘快速傅里葉變換（FFT）

1.多類蝶形運算快速傅里葉變換（FFT）

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

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

2.旋轉因子的生成一種方法是在每級運算中直接產生；二種方法是在FFT程序開始前預先計算出旋轉因子，存放在數組中，作為旋轉因子表，在程序執行中直接查表。快速傅里葉變換（FFT）

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

x2(n)=x(2n+1),n=0,1,……,N-1根據DIT－FFT的思想，只要求得x1(n)和x2(n)的N點DFT，再經過簡單的一級蝶形運算就可得到x(n)的2N點DFT。因為x1(n)和x2(n)均為實序列，所以根據DFT的共軛對稱性，可用一次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點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點FFT計算完成了計算2N點DFT。例2：設x(n)是長度為2N的有限長實序列，X(k)為x(n)的2N點DFT。若已知X(k)，要求：試設計用一次N點IFFT完成計算x(n)的高效算法。解：設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的算法，有以下關系式：

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由上面分析可得出運算過程如下： （1）由X(k)計算出X1(k)和X2(k)； （2）由X1(k)和X2(k)構成N點頻域序列Y(k)：

Y(k)=X1(k)+jX2(k)=Yep(k)+Yop(k)其中Yep(k)=X1(k)，Yop(k)=jX2(k)，進行N點IFFT運算，得到

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

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)：當n=偶數（n=0,1,…,2N-1）時x(n)=x1(n/2)當n=奇數（n=0,1,…,2N-1）時x(n)=x2((n-1)/2)分裂基FFT算法快速傅里葉變換（FFT）1984年，法國的杜梅爾和霍爾曼將基2和基4分解糅合在一起，提出了分裂基FFT算法，其運算量有所減少，運算流圖相似，運算程序較短，是一種實用的高效算法。快速傅里葉變換（FFT）快速傅里葉變換（FFT）快速傅里葉變換（FFT）快速傅里葉變換（FFT）快速傅里葉變換（FFT）快速傅里葉變換（FFT）L形蝶形圖一個N點DFT可分解成一個N/2點DFT和兩個N/4點DFT快速傅里葉變換（FFT）-1-1-j-1快速傅里葉變換（FFT）離散哈特萊變換（DHT）快速傅里葉變換（FFT）計算出X(k)的前N/2個值，則后N/2個值可求直接對實序列進行實數域變換的離散哈特萊變換快速傅里葉變換（FFT）證明：快速傅里葉變換（FFT）證明：快速傅里葉變換（FFT）

DHT的核函數是DFT核函數的實部與虛部之和快速傅里葉變換（FFT）快速傅里葉變換（FFT）1.DHT是實值變換2.DHT的正反變換具有相同形式DHT的主要優點：3.DHT與DFT間的關系簡單快速傅里葉變換（FFT）

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

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

3.循環移位性質快速傅里葉變換（