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

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

離散傅里葉變換（DFT）

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

基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的運算規(guī)律及編程思想蝶形運算的規(guī)律和通式旋轉因子的規(guī)律性的存儲問題快速傅里葉變換（FFT）一、原位計算-1-1-1-1-1-1-1-1-1-1-1-1快速傅里葉變換（FFT）二、旋轉因子快速傅里葉變換（FFT）三、蝶形運算規(guī)律快速傅里葉變換（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輸出是自然序列，輸入稱為倒位序列，即二進制數(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二進制n2n1n0

倒位序二進制n0n1n2

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

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

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

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

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

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

3.實序列的FFT算法例1：設x(n)是長度為2N的有限長實序列，X(k)為x(n)的2N點DFT。要求：試設計用一次N點FFT完成計算X(k)的高效算法。解：本題的解題思路是DIT－FFT思想；在時域分別抽取偶數(shù)點和奇數(shù)點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根據(jù)DIT－FFT的思想，只要求得x1(n)和x2(n)的N點DFT，再經過簡單的一級蝶形運算就可得到x(n)的2N點DFT。因為x1(n)和x2(n)均為實序列，所以根據(jù)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=偶數(shù)（n=0,1,…,2N-1）時x(n)=x1(n/2)當n=奇數(shù)（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個值可求直接對實序列進行實數(shù)域變換的離散哈特萊變換快速傅里葉變換（FFT）證明：快速傅里葉變換（FFT）證明：快速傅里葉變換（FFT）

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

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

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

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