數(shù)字信號處理

通信工程學(xué)院

叢玉良、林琳、樸美蘭、王波

2023.08學(xué)習要求：（1）理解提高離散傅里葉變換運算速度的主要方法。（2）了解時間抽選奇偶分解FFT算法。

（3）了解頻率抽選奇偶分解FFT算法。

（4）理解快速傅里葉逆變換（IFFT）的概念。

（5）掌握線性卷積和線性相關(guān)的FFT算法。4.1提高DFT運算速度的主要方法問題提出：設(shè)有限長序列x(n)，非零值長度為N，計算對x(n)進行一次DFT運算，共需多大的運算工作量?一、直接計算DFT計算量1.比較DFT與IDFT之間的運算量2.以DFT為例，計算DFT復(fù)數(shù)運算量計算一個X(k)(一個頻率成分)值，運算量為當k=1要進行N次復(fù)數(shù)乘法+

(N-1)次復(fù)數(shù)加法要完成整個DFT運算，其計算量為N*N次復(fù)數(shù)相乘+N*(N-1)次復(fù)數(shù)加法DFTN2FFTNlog2N

DirectDFTcalculationrequires~N2complexmultiplications.complexityO(N2)NDFT4163210241281638410241048576它是級的計算復(fù)雜度。N=1024時，計算DFT需要一百多萬次的復(fù)數(shù)乘法，很難滿足實時信號處理的要求。二、改善DFT運算速度的基本途徑（1）的周期性：（2）的對稱性：

（3）分解算法復(fù)乘數(shù)復(fù)加數(shù)

r為任意整數(shù)

寫成矩陣形式8次復(fù)數(shù)加法+2次復(fù)數(shù)乘法！對稱性例：

討論4點離散傅立葉變換的計算量。16次復(fù)數(shù)乘法+12次復(fù)數(shù)加法！將其展開有4.2時間抽選奇偶分解FFT算法（庫里-圖基算法）4.2.1算法原理后N/2個點的離散傅立葉變換為利用N/2點DFT隱藏的周期性同理整理有由N/2點DFT求N點DFTX1(k)X2(k)作圖要素：（從左向右計算）(1)左邊兩路為輸入(2)右邊兩路為輸出，右上支路為相加輸出、右下支路為相減輸出(3)線旁數(shù)為加權(quán)值基本蝶形運算需要一次復(fù)乘，兩次復(fù)加。蝶形計算信號流圖N=8每級都由N/2個蝶形單元構(gòu)成。每一級運算都需要N/2次復(fù)乘和N次復(fù)加(每個結(jié)加減各一次)。這樣(N=2M)M級運算共需要：復(fù)乘次數(shù)復(fù)加次數(shù)

4.2.2運算量估計

當x(n)長為N=2M時，要進行M次奇偶分解，分為M級計算。設(shè)L表示級數(shù)，它可以為1~M中任意一值。時間抽取奇偶分解FFT算法，其輸入序列x(n)為倒位序，輸出序列為自然序列。倒位序：將序號n寫成二進制碼，然后將二進制碼首尾倒置，再將倒置的二進制碼譯成十進制數(shù)的排列順序。4.2.3按時間抽取FFT算法的特點自然順序二進制表示倒位二進制倒位序碼0000000010011004201001023011110641000011510110156110011371111117可以“即位運算”。將數(shù)據(jù)存在存儲器內(nèi)，每一級的運算結(jié)果都存入相應(yīng)存儲器，直至最終結(jié)果輸出。每一級包括N/2個基本蝶形運算。第L級運算包括N/2L個群，第L級群之間的間隔為2L，L=1，2，…，M。同一級中各個群的乘數(shù)W分布相同，各級共有2L-1個乘數(shù)。每一個群中，W分布自上而下規(guī)律為的從零開始的正整數(shù)次冪。級數(shù)L群數(shù)N/2L群間隔2L群系數(shù)2L-1每個群W142122423184M=3基本蝶形運算單元

每個基本蝶形運算關(guān)系為4.3頻率抽取奇偶分解4.3.1算法原理把k按奇偶分項

其中

FFT具有M級、N/2個碟形運算、Nlog2N計算復(fù)雜度當x(n)長為N=2M時，要進行M次分解，分為M級計算。設(shè)L表示級數(shù)，它可以為1~M中任意一值。頻率抽取奇偶分解FFT算法，其輸入序列x(n)為自然序列，輸出序列為倒序列。（見圖4-7）每一級包括N/2個基本蝶形運算。4.3.2按頻率抽取FFT算法的特點第L級運算包括2L-1個群，第L級群之間的間隔為N/2L-1，L=1，2，…，M。群：蝶形圖中任一級相互交叉在一起的蝶形。群間隔是圖中按從上到下的順序，上下兩個群之間對應(yīng)元素序號的增量。同一級中各個群的乘數(shù)W分布相同，各級共有N/2L個乘數(shù)。第L級中，每一個群中，W分布自上而下規(guī)律為的從零開始的正整數(shù)次冪。

級數(shù)L群數(shù)2L-1群間隔N/2L-1群系數(shù)N/2L每個群W118422423421M=3即位運算，第L級蝶形輸入間隔為N/2L，基本蝶形運算關(guān)系為

頻率抽選算法與時間抽選算法的蝶形流程圖之間存在轉(zhuǎn)置關(guān)系。（P100圖4-5、P107圖4-8）4.4離散傅里葉反變換的快速計算IFFT方法1——利用FFT計算IFFT時抽FFT頻抽IFFT頻抽FFT時抽IFFT使用同一程序使用同一程序

IFFT方法24.5其他快速算法簡介

時，DFT的快速算法一般可采用以下幾種方法加以處理：

(1)補零法：基2-FFT。補零后不影響頻譜形狀，增加頻譜抽樣點。

任意基FFT算法：適用于N是一個復(fù)合數(shù)，即它可以分解成一些

因子的乘積。如果要求準確的N點DFT，而N又是質(zhì)數(shù)，則只能采用直接DFT方法，或者用后面將要介紹的CZT(Chirpz變換)方法。p組p=3組長為q=64.5.1復(fù)合數(shù)FFT算法

沿著螺旋線取樣計算z變換，稱其為線性調(diào)頻z變換或ChirpZ變換。沿螺旋線等分角取樣，取樣點值為其中，M為是所要分析復(fù)頻點的點數(shù)。W和A為任意復(fù)數(shù)。4.5.2線性調(diào)頻z變換CZT

z變換的取樣設(shè)線性調(diào)頻z變換的計算流程k4.6.1離散余弦變換定義若x(n)為實數(shù)，DCT也是實數(shù)，上式矩陣形式4.6離散余弦變換（DCT）CN的行列是正交關(guān)系，CN稱為歸一化正交矩陣

DCT反變換(IDCT)定義為CN稱為歸一化正交矩陣

1.線性性質(zhì)2.對稱性質(zhì)3.能量保留定理4.6.2DCT性質(zhì)

4.7短時傅里葉變換

4.7.1短時傅里葉變換的定義及其物理解釋1.短時傅里葉變換的定義短時傅里葉變換的定義有兩種形式定義1:窗函數(shù)的移動

定義2:2.短時傅里葉變換的物理解釋定義2物理解釋定義1物理解釋

4.7.2短時傅里葉變換的性質(zhì)1.線性性質(zhì)2.頻移性質(zhì)——調(diào)制特性

3.時移特性

4.共軛對稱性

當信號是實信號時5.由短時傅里葉變換恢復(fù)信號

4.7.3短時傅里葉變換的時間、頻率分辨率第一種極端情況,

STFT退化為信號的傅里葉變換，沒有任何時間分辨率，卻有最好的頻域分辨率。

第二種極端情況

,STFT退化為信號，有理想的時間分辨率，但不提供任何頻率分辨率。短時傅里葉變換的時間分辨率取決于窗函數(shù)的長度。為了提高信號的時間分辨率，希望w(n)的長度愈短愈好。頻域分辨率取決于窗函數(shù)的頻域函數(shù)寬度，為了提高頻域分辨率，希望盡量加寬w(n)窗口寬度，這樣必然又會降低時域分辨率.時域分辨率和頻域分辨率相互制約.

4.7.