第二章數(shù)字信號處理的基本算法

DSP原理與實訓指導新世紀高職高專教材編審委員會組編主編喻宗泉第二章數(shù)字信號處理的基本算法2.1

數(shù)字信號處理的一般程序2.2

傅立葉變換的四種形式2.3

離散信號的傅立葉變換2.4

離散傅立葉變換的運算特征2.5

DFT的快速算法2.6

基-2FFT算法2.7

基-4FFT算法2.8

離散傅立葉反變換快速算法2.1

數(shù)字信號處理的一般程序

要想實現(xiàn)數(shù)字信號處理，一般程序必須經(jīng)過如下幾個階段。（1）首先要獲得數(shù)字信號，得到的數(shù)字信號通常是離散時間信號（2）完成信號之間的傅立葉變換（3）用軟件或硬件完成數(shù)字濾波功能（4）選擇合適的DSP芯片（5）從硬件和軟件兩個方面設(shè)計組成DSP系統(tǒng)（6）用仿真器調(diào)試硬件。（7）用DSP開發(fā)工具調(diào)試軟件程序（8）將軟件脫離開發(fā)系統(tǒng)，裝入實際系統(tǒng)中運行2.1

數(shù)字信號處理的一般程序2.2

傅立葉變換的四種形式將自變量為時間的時域函數(shù)轉(zhuǎn)變成自變量為頻率的頻域函數(shù)，稱為傅立葉變換。反之稱為傅立葉反變換。傅立葉變換反映了時間信號與頻率信號之間的對應(yīng)關(guān)系。

鑒于時間信號有連續(xù)時間信號和離散時間信號之分，與時間函數(shù)對應(yīng)的頻率函數(shù)中，頻率的取值可以為連續(xù)值或離散值，因此傅立葉變換就有四種形式。在DSP領(lǐng)域用得最多的是離散時間信號與離散頻率信號之間的傅立葉變換。2.2

傅立葉變換的四種形式2.2.1連續(xù)時間信號與連續(xù)頻率信號間的傅立葉變換設(shè)連續(xù)時間信號f(t)對應(yīng)的頻譜密度函數(shù)為F(jΩ)，則傅立葉變換為：

傅立葉反變換為：

連續(xù)時間信號與連續(xù)頻率信號間的變換

設(shè)f(t)是周期為T的連續(xù)時間函數(shù)，展開成傅立葉級數(shù)后的系數(shù)為F(jkΩ0)，則由f(t)求取F(jkΩ0)的正變換為：

2.2

傅立葉變換的四種形式2.2.2連續(xù)時間信號與離散頻率信號間的傅立葉變換由F(jkΩ0)求取f(t)的反變換為：

式中k表示諧波次數(shù)，Ω0表示離散頻率兩相鄰譜線間的角頻間隔，且F(jkΩ0)為離散頻譜的非周期函數(shù)。

2.2

傅立葉變換的四種形式2.2.2連續(xù)時間信號與離散頻率信號間的傅立葉變換連續(xù)時間信號與離散頻率信號間的變換

2.2

傅立葉變換的四種形式2.2.3離散時間信號與連續(xù)頻率信號間的傅立葉變換設(shè)f(n)是非周期離散時間信號，對應(yīng)的連續(xù)頻率頻譜密度信號為

式中ω=ΩT表示數(shù)字頻率，Ω表示模擬頻率，T表示將模擬信號數(shù)字化采樣時的抽樣間隔。從離散時間信號求得連續(xù)頻率信號的傅立葉正變換為：從連續(xù)頻率信號求得離散時間信號的反變換為：

2.2

傅立葉變換的四種形式2.2.3離散時間信號與連續(xù)頻率信號間的傅立葉變換離散時間信號與連續(xù)頻率信號間的變換

2.2

傅立葉變換的四種形式2.2.4離散時間信號與離散頻率信號間的傅立葉變換設(shè)f(n)為周期離散時間信號，相應(yīng)的離散頻譜密度為F(k)，則正變換為：

相應(yīng)反變換為：式中f(n)=f(nT)

N是有限長序列的抽樣點數(shù)。2.2

傅立葉變換的四種形式2.2.4離散時間信號與離散頻率信號間的傅立葉變換離散時間信號與離散頻率信號間的變換

2.3

離散信號的傅立葉變換2.3.1離散時間信號的傅立葉變換離散時間信號f(n)的傅立葉變換定義成：上式成立的條件是序列f(n)滿足：如果把f(n)視為模擬信號的抽樣序列，設(shè)抽樣頻率為fs=1/T，其中T是抽樣時間間隔，模擬信號頻率Ωs=2π/T

，則有f(n)＝f(nT)ω＝ΩT

2.3

離散信號的傅立葉變換2.3.1離散時間信號的傅立葉變換將變換關(guān)系離散化后，設(shè)Ω＝kΩ０，ΩT＝2πfk，則式中N=fs

/f=Ωs/Ω０，代入得對于F(ejω)的傅立葉反變換，有以下定義：2.3

離散信號的傅立葉變換2.3.2周期序列的離散傅立葉級數(shù)DFS設(shè)x(n)是一個任意的以N為周期的離散時間周期序列，因序列有周期性，因此可以展開成如下的傅立葉級數(shù)：式中ak是離散傅立葉級數(shù)的系數(shù)，N是非零的某一個整數(shù)。如果將上式兩邊乘以，并對n在一個周期N內(nèi)求和，即可求得ak。其中，k取值范圍為(-∞，＋∞)中的整數(shù)。2.3

離散信號的傅立葉變換2.3.2周期序列的離散傅立葉級數(shù)DFS如果k發(fā)生變化，就成為周期為N的周期函數(shù)，由此ak成為周期為N的周期序列，若設(shè)：x(k)=Nak則有：x(k)稱為x(n)的離散傅立葉級數(shù)系數(shù)，記為DFS：x(k)=DFS[x(n)]上式就是離散傅立葉級數(shù)DFS的正變換。2.3

離散信號的傅立葉變換2.3.2周期序列的離散傅立葉級數(shù)DFS相應(yīng)的反變換為已知x(k)求x(n)：反變換公式表明如何將周期序列分解成N次諧波，X(k)和x(n)都是周期為N的序列，第k次諧波的頻率是ωk=2πk∕N，其中k=0，1，2，…，N-1，諧波幅值，相位arg[X(k)]，k=0表示直流分量，直流分量幅值為：2.3

離散信號的傅立葉變換2.3.3有限長序列的離散傅立葉變換DFT主值序列和周期延拓1設(shè)f(n)是一個長度為N的有限序列，它的取值特征是n為整數(shù)，且f(n)僅當n從0到N-1時有值，當n為其它值時f(n)為0。下圖就是有限長序列當N=8時的示意圖。2.3

離散信號的傅立葉變換2.3.3有限長序列的離散傅立葉變換DFT如果以N為周期將f(n)進行延拓，延拓結(jié)果獲得一個周期序列x(n)，如圖2-9所示，x(n)和f(n)的關(guān)系如下：將f(n)稱為x(n)的一個主值序列，因為f(n)是x(n)的某一個周期。而周期序列可以看成是主值序列周期延拓的結(jié)果。周期序列x(n)

2.3

離散信號的傅立葉變換2.3.3有限長序列的離散傅立葉變換DFT有限長序列DFT2如果f(n)是有限長時域序列的話，F(xiàn)(k)就是其轉(zhuǎn)換到頻域的有限長頻域序列。由此得到f(n)的離散傅立葉變換：式中k的取值為[0，N-1]。反變換為：式中n的取值為[0，N-1]2.3

離散信號的傅立葉變換2.3.3有限長序列的離散傅立葉變換DFT有限長序列DFT2引進矩陣序列RN(n)：正變換可寫成：反變換表示成：2.4離散傅立葉變換的運算特征2.4.1周期性離散時間信號的傅立葉變換以2π為周期，用式子表示成：式中r=0，±1，±2，…，為正整數(shù)。ω是周期離散時間信號的角頻率，ω＝0的量是信號的直流分量，由于以2π為周期，因此信號的直流分量發(fā)生在ω＝2rπ處，其中r=0，±1，±2，…。信號的低頻分量集中在ω＝2rπ附近。信號的最高頻率位于ω＝π處，于是在π附近集中了信號的最高頻率。2.4離散傅立葉變換的運算特征2.4.1周期性以f(ｎ)＝cosωn為例，如果ω＝2rπ(r=0，±1，±2，…)，周期序列cosωn的譜線呈齒狀，序列幅值維持為常數(shù)不變。如果ω＝(2r＋1)π，則序列幅值從正值跳到負值，從最大跳到最小，再從最小跳到最大。下圖分別畫出了ω不同取值時的兩種cosωn波形。2.4離散傅立葉變換的運算特征2.4.2線性設(shè)有兩個離散序列x(n)和y(n)，相應(yīng)傅立葉變換分別為X(k)和Y(k)：X(k)=DFT[x(n)]Y(k)=DFT[y(n)]則有aX(k)+bY(k)=DFT[ax(n)+by(n)]式中a，b是任意常數(shù)。用文字敘述成：兩個離散序列和的傅立葉變換等于各自離散傅立葉變換之和。2.4離散傅立葉變換的運算特征2.4.2線性現(xiàn)將序列長度的問題說明如下：兩個離散序列的長度相同時，相加后的長度不變。例如設(shè)x(n)和y(n)的長度都是N，則ax(n)+by(n)的長度也是N。兩個離散序列的長度不同時，相加后的長度等于較長序列的長度。例如設(shè)x(n)的長度為Nx，y(n)的長度為Ny。若Nx＞Ny，則ax(n)+by(n)的長度為Nx。反之若Nx＜Ny，則ax(n)+by(n)的長度為Ny。2.4離散傅立葉變換的運算特征2.4.3奇偶對稱性離散時間序列的傅立葉變換與連續(xù)時間傅立葉變換類似，存在條件奇偶對稱性。這一性質(zhì)說的是如果序列f(n)的離散傅立葉變換為F(k)，則f(n)和F(k)具有相同的奇偶性。即：如果f(n)為奇（偶）對稱序列，則F(k)也為奇（偶）對稱序列；反之F(k)為奇（偶）對稱序列，則f(n)也為奇（偶）對稱序列。2.4離散傅立葉變換的運算特征2.4.4共軛對稱性設(shè)f(n)是一個離散時間復序列，由實部和虛部組成。用下標r表示序列的實部；用下標i表示序列的虛部，復序列可以表示成：f(n)=fr(n)+jfi(n)如果f(n)的離散傅立葉變換為F(k)：F(k)=DFT[f(n)]且F(k)的條件共軛偶部和奇部分別用Fe(k)和F0(k)表示，則有如下關(guān)系式成立：Fe(k)=DFT[fr(n)]F0(k)=DFT[fi(n)]2.4離散傅立葉變換的運算特征2.4.5時移特性和頻移特性時移特性又稱為移位性質(zhì)，描述的是離散時間序列信號在延時一段時間后的傅立葉變換取什么樣的形式?？紤]到時域與頻域之間的對偶關(guān)系，可得f(n)的頻移特性:設(shè)f(n)的離散傅立葉變換為F(k)，f(n)為有限長非周期序列。將f(n)以周期N完成周期延拓，得周期序列x(n)，設(shè)移位延時為n0，則f(n+n0)的傅立葉變換為：2.4離散傅立葉變換的運算特征2.4.6頻域卷積特性設(shè)f(n)、h(n)皆是長度為N的有限長序列，且N-1≥n＞0F(k)=DFT[f(n)]H(k)=DFT[h(n)]又設(shè)

y(n)=f(n)·h(n)則式中“﹡”表示卷積和2.4離散傅立葉變換的運算特征2.4.6頻域卷積特性若將自變量改用ejω，則周期為2π，有表示成立，即時域內(nèi)兩離散時間序列相乘，可轉(zhuǎn)化到頻域內(nèi)形成卷積關(guān)系。2.4離散傅立葉變換的運算特征性質(zhì)信號序列傅立葉變換表示周期性f(n)

線性f(n)、x(n)奇偶對稱性f(n)為奇（偶）對稱序列也為奇（偶）對稱序列共軛對稱性f(n)=fr(n)+jfi(n)r：實部i：虛部Fe(k)=DFT[fr(n)]Fo(k)=DFT[fi(n)]e：共軛偶部o：共軛奇部a、b為常數(shù)r=0,±1,±2,…時移特性f(n+n0)頻移特性卷積特性f(n)y(n)=f(n)h(n)Parseval（巴塞菲爾）定理f(n)2.4離散傅立葉變換的運算特征2.5

DFT的快速算法—快速傅立葉變換FFT2.5.1

FFT的種類按照離散時間序列是輸入有序還是輸出有序，F(xiàn)FT算法可分為時域抽取法(DecimationInTimeFFT)和頻域抽取法(DecimationInFrequencyFFT)兩種，前者簡稱DIT-FFT，后者簡稱DIF-FFT。把輸入有限長離散時間序列劃分成兩個子序列分別計算的FFT算法，稱為基-2FFT算法，（或“基2FFT算法”）。把輸入有限長離散時間序列劃分成4個子序列分別計算的FFT算法，稱為基-4FFT算法，（或“基4FFT算法”）。2.5

DFT的快速算法—快速傅立葉變換FFT2.5.2

FFT算法設(shè)計思路設(shè)f(n)是長度為N的有限長序列，它的離散傅立葉變換DFT為：對于所有F(k)的N個值，運算的總次數(shù)為N2次復數(shù)乘法和N×（N-1）次復數(shù)加法。減少運算量的有效做法是將N個點的DFT分成幾個較短的DFT分頭計算，例如等份成M個，每一個短的DFT長度只有N/M。2.5

DFT的快速算法—快速傅立葉變換FFT2.5.2

FFT算法設(shè)計思路計算F(k)總的運算工作量為：與不等分成M時的計算相比，總的工作量下降了1/M。如果把每一個短的DFT繼續(xù)分解成P個更短序列的DFT，計算的工作量將又下降1/P，繼續(xù)等分下去再計算，結(jié)果將使離散傅立葉變換進行得更快，能使DFT的運算速度提高幾個數(shù)量級。此外，利用的周期性質(zhì)、對稱性質(zhì)及一些特殊值還能進一步加快運算速度。利用分解長序列的DFT、的性質(zhì)快速實現(xiàn)DFT運算的算法被稱為快速傅立葉變換(FastFourierTransform，F(xiàn)FT)算法。2.5

DFT的快速算法—快速傅立葉變換FFT2.5.2

FFT算法設(shè)計思路將序列f(n)不斷分成2個的這種FFT算法稱為基-2FFT算法。將序列f(n)不斷分成4個的這種FFT算法稱為基-4FFT算法。2.6基-2FFT算法2.6.1時域抽取法FFT將f(n)分成奇序列和偶序列1設(shè)f(n)的離散傅立葉變換為F(k)，其中n、k的取值范圍均為[0，N-1]。不失一般計，設(shè)長度N為偶數(shù)，若N為奇數(shù)，可補充一個零使N為偶數(shù)。將f(n)分成兩部分，偶數(shù)部分組成一個偶序列，奇數(shù)部分組成一個奇序列，分別用f1(i)和f2(i)表示，偶序列f1(i)為：f1(i)=f(2i)

式中奇序列f2(i)為：f2(i)=f(2i+1)

2.6基-2FFT算法2.6.1時域抽取法FFT將f(n)分成奇序列和偶序列1各自的離散傅立葉變換：F1(k)=DFT[f1(i)]F2(k)=DFT[f2(i)]有2.6基-2FFT算法2.6.1時域抽取法FFT將f(n)分成奇序列和偶序列1考慮到f1(i)=f(2i)，

f2(i)=f(2i+1)且則F(k)可寫成：2.6基-2FFT算法2.6.1時域抽取法FFT將f(n)分成奇序列和偶序列1上式表明，按照n的奇偶性能將f(n)分解成兩個序列f1(i)和f2(i)，每個序列的長度均為N/2。而N個點的離散傅立葉變換F(k)又可以分解成兩個N/2點的DFT進行運算，F(xiàn)1(k)和F2(k)就分別是f1(i)和f2(i)的N/2點DFT。這里，k的取值為k=0，1，2，…，N/2-1。如果F1(k)和F2(k)的表達式代入到F(k)中，考慮到2.6基-2FFT算法2.6.1時域抽取法FFT將f(n)分成奇序列和偶序列1利用F1(k)和F2(k)的隱含周期性，則有:2.6基-2FFT算法2.6.1時域抽取法FFT將f(n)分成奇序列和偶序列1F1(k)、F2(k)的前半部分值(k取值[0，N/2-1])與后半部分值(k取值[N/2，N-1])相等。由離散傅立葉變換的對稱性：能把F(k)分解成前后兩部分。其中前半部分的自變量為k：[0，N/2-1]，F(xiàn)(k)表示成：2.6基-2FFT算法2.6.1時域抽取法FFT將f(n)分成奇序列和偶序列1后半部分的自變量為k：[N/2，N-1]，F(xiàn)(k+N/2)表示成：因此，F(xiàn)(k)的所有值可通過以下方法求出：只需求得奇、偶序列前半個區(qū)間(k取值[0，N/2-1])內(nèi)所有F1(k)、F2(k)之值。2.6基-2FFT算法2.6.1時域抽取法FFT蝶形流程2使用流程圖來表示信號的輸入輸出間關(guān)系，是一種直觀表示FFT的方法。例如方程組：可以用流程圖表示，如圖所示，該圖稱為蝶形流程圖。2.6基-2FFT算法2.6.1時域抽取法FFT蝶形流程2圖中F1(k)、F2(k)是輸入，F(xiàn)(k)、F(k+N/2)是輸出，輸入信號前的系數(shù)標注在箭頭處，箭頭前沒有標注的表示流程系數(shù)為1，箭頭表示信號的流向，相交點表示求和。蝶形流程圖

2.6基-2FFT算法2.6.1時域抽取法FFTN=8點DFT分解3設(shè)N=8對f(n)和F(k)進行分解，其中f(n)有f(0)，f(1)，…，f(7)；F(k)有F(0)，F(xiàn)(1)，…，F(xiàn)(7)?？紤]到n=0，1，2，…，7，將f(n)分成偶數(shù)序列f1(i)和奇數(shù)序列f2(i)，i=0，1，2，3。f1(i)由f(0)，f(2)，f(4)，f(6)組成；f2(i)由f(1)，f(3)，f(5)，f(7)組成。它們的DFT分別用F1(k)(k=0，1，2，3)和F2(k)(k=0，1，2，3)表示。如圖所示。f(n)分解

2.6基-2FFT算法2.6.1時域抽取法FFTN=8點DFT分解32.6基-2FFT算法2.6.1時域抽取法FFTN=8點DFT分解3設(shè)k=0，1，2，3，F(xiàn)(k)的產(chǎn)生用得：2.6基-2FFT算法2.6.1時域抽取法FFTN=8點DFT分解3F(0)～F(3)的產(chǎn)生

由此畫成如圖所示：2.6基-2FFT算法2.6.1時域抽取法FFTN=8點DFT分解3而F(k+N/2)的產(chǎn)生用得：由此畫成圖如圖所示：2.6基-2FFT算法2.6.1時域抽取法FFTN=8點DFT分解3F(4)～F(7)的產(chǎn)生

2.6基-2FFT算法2.6.1時域抽取法FFTN=8點DFT分解3如果將上述三圖合在一起，便可以畫出由f(n)→F(k)的流程，如下圖所示。由f(n)到F(k)的流程

再看f1(i)和f2(i)，i=0，1，2，3，它們雖然分別是f(n)的偶、奇序列，但它們各自的長度N/2=4仍然為偶數(shù)。既然為偶數(shù)，就可以將f1(i)分解成兩個序列：一個奇數(shù)序列、一個偶數(shù)序列，這樣分解后每個序列的長度應(yīng)為N/4=2。同理，f2(i)也可以分解長度為N/4的兩個序列。2.6基-2FFT算法2.6.1時域抽取法FFTN=8點DFT分解32.6基-2FFT算法2.6.1時域抽取法FFTN=8點DFT分解3一個f(n)被分解成了4個序列

2.6基-2FFT算法2.6.1時域抽取法FFTN=8點DFT分解3繼續(xù)進行奇偶劃分，這樣一個f(n)可被分解成8個序列：2.6基-2FFT算法2.6.1時域抽取法FFT自然順序和倒位順序4在DFT分解流程中，從輸入f(n)到輸出F(k)遵循著自然順序和倒位順序的規(guī)律。以N=8為例，輸入f(n)有8個：f(0)，f(1)，…，f(7)；輸出F(k)也有8個：F(0)，F(xiàn)(1)，…，F(xiàn)(7)。即n=0，1，…，7；k=0，1，…，7。如果n和k都用二進制數(shù)表示，則n=000，001，010，…，111；k=000，001，010，…，111。二進制數(shù)從小到大的排列順序稱為自然順序，將二進制數(shù)的最高位變成最低位，次高位變成次低位，…，這樣形成的排列順序為倒位順序。用式子來表示，如果n2n1n0為自然順序，則n0n1n2就是倒位順序，其中n0、n1、n2僅取值0或1。2.6基-2FFT算法2.6.1時域抽取法FFT自然順序和倒位順序4本節(jié)討論的N=8點f(n)分解成8個序列例子中，f(n)遵循倒位順序，F(xiàn)(k)遵循自然順序。2.6基-2FFT算法2.6.1時域抽取法FFT自然順序和倒位順序4產(chǎn)生自然順序及倒位順序的原因是在時域抽取的FFT算法中，不停頓地對輸入序列進行奇偶分組，分組過程形成了一個倒位序列的樹狀圖，如圖所示。2.6基-2FFT算法f(n)自然順序F(k)倒位順序的FFT流程圖

2.6.1時域抽取法FFT其他形式的FFT流程52.6.1時域抽取法FFT其他形式的FFT流程52.6基-2FFT算法f(n)自然順序F(k)自然順序的FFT流程圖

時域抽取法FFT的要點是將輸入時間序列按n為偶數(shù)和奇數(shù)不斷分解；頻域抽取法FFT的要點是將輸出頻域序列按k為偶數(shù)和奇數(shù)不斷分解。設(shè)f(n)的離散傅立葉變換為F(k)，且0≤n≤N-1，0≤k≤N-1。又設(shè)N為偶數(shù)，若N為奇數(shù)，則添加一個零使其為偶數(shù)。若設(shè)，