(完整版)數(shù)字信號(hào)處理教案(東南大學(xué))

PAGEPAGE1數(shù)字信號(hào)處理緒論一、從模擬到數(shù)字1、信號(hào)：信號(hào)傳遞信息的函數(shù)也是獨(dú)立變量的函數(shù)，這個(gè)變量可以是時(shí)間、空間位置等。2、連續(xù)信號(hào)：在某個(gè)時(shí)間區(qū)間，除有限間斷點(diǎn)外所有瞬時(shí)均有確定值。3、模擬信號(hào)是連續(xù)信號(hào)的特例。時(shí)間和幅度均連續(xù)。4、離散信號(hào)：時(shí)間上不連續(xù)，幅度連續(xù)。5、數(shù)字信號(hào)：幅度量化，時(shí)間和幅度均不連續(xù)。A/DA/D變換器通用或?qū)Ｓ糜?jì)算機(jī)采樣保持器D/A變換器模擬低通濾波器模擬信號(hào)數(shù)字信號(hào)模擬信號(hào)數(shù)字信號(hào)處理系統(tǒng)連續(xù)時(shí)間信號(hào)連續(xù)時(shí)間信號(hào)模擬信號(hào)的數(shù)字化模擬信號(hào)的數(shù)字化數(shù)字信號(hào)數(shù)碼量化電平模擬信號(hào)采樣保持信號(hào)量化電平數(shù)碼數(shù)碼量化電平數(shù)字信號(hào)D/A輸出信號(hào)模擬信號(hào)數(shù)字信號(hào)轉(zhuǎn)化成模擬信號(hào)模擬濾波輸出D/A模擬濾波輸出D/A輸出二、數(shù)字信號(hào)處理的主要優(yōu)點(diǎn)數(shù)字信號(hào)處理采用數(shù)字系統(tǒng)完成信號(hào)處理的任務(wù)，它具有數(shù)字系統(tǒng)的一些共同優(yōu)點(diǎn)，例如抗干擾、可靠性強(qiáng)，便于大規(guī)模集成等。除此而外，與傳統(tǒng)的模擬信號(hào)處理方法相比較，它還具有以下一些明顯的優(yōu)點(diǎn)：1、精度高在模擬系統(tǒng)的電路中，元器件精度要達(dá)到10-3以上已經(jīng)不容易了，而數(shù)字系統(tǒng)17位字長可以達(dá)到102、靈活性強(qiáng)數(shù)字信號(hào)處理采用了專用或通用的數(shù)字系統(tǒng)，其性能取決于運(yùn)算程序和乘法器的各系數(shù)，這些均存儲(chǔ)在數(shù)字系統(tǒng)中，只要改變運(yùn)算程序或系數(shù)，即可改變系統(tǒng)的特性參數(shù)，比改變模擬系統(tǒng)方便得多。3、可以實(shí)現(xiàn)模擬系統(tǒng)很難達(dá)到的指標(biāo)或特性例如：有限長單位脈沖響應(yīng)數(shù)字濾波器可以實(shí)現(xiàn)嚴(yán)格的線性相位；在數(shù)字信號(hào)處理中可以將信號(hào)存儲(chǔ)起來，用延遲的方法實(shí)現(xiàn)非因果系統(tǒng)，從而提高了系統(tǒng)的性能指標(biāo)；數(shù)據(jù)壓縮方法可以大大地減少信息傳輸中的信道容量。4、可以實(shí)現(xiàn)多維信號(hào)處理利用龐大的存儲(chǔ)單元，可以存儲(chǔ)二維的圖像信號(hào)或多維的陣列信號(hào)，實(shí)現(xiàn)二維或多維的濾波及譜分析等。5、缺點(diǎn)（1）增加了系統(tǒng)的復(fù)雜性。他需要模擬接口以及比較復(fù)雜的數(shù)字系統(tǒng)。（2）應(yīng)用的頻率范圍受到限制。主要是A/D轉(zhuǎn)換的采樣頻率的限制。（3）系統(tǒng)的功率消耗比較大。數(shù)字信號(hào)處理系統(tǒng)中集成了幾十萬甚至更多的晶體管，而模擬信號(hào)處理系統(tǒng)中大量使用的是電阻、電容、電感等無源器件，隨著系統(tǒng)的復(fù)雜性增加這一矛盾會(huì)更加突出。三、發(fā)展特點(diǎn)(1)由簡單的運(yùn)算走向復(fù)雜的運(yùn)算，目前幾十位乘幾十位的全并行乘法器可以在數(shù)個(gè)納秒的時(shí)間內(nèi)完成一次浮點(diǎn)乘法運(yùn)算，這無論在運(yùn)算速度上和運(yùn)算精度上均為復(fù)雜的數(shù)字信號(hào)處理算法提供了先決條件；(2)由低頻走向高頻，模數(shù)轉(zhuǎn)換器的采樣頻率已高達(dá)數(shù)百兆赫，可以將視頻甚至更高頻率的信號(hào)數(shù)字化后送入計(jì)算機(jī)處理；(3)由一維走向多維，像高分辨率彩色電視、雷達(dá)、石油勘探等多維信號(hào)處理的應(yīng)用領(lǐng)域已與數(shù)字信號(hào)處理結(jié)下了不解之緣。（4）各種數(shù)字信號(hào)處理系統(tǒng)均幾經(jīng)更新?lián)Q代在圖像處理方面，圖像數(shù)據(jù)壓縮是多媒體通信、影碟機(jī)(VCD或DVD)和高清晰度電視(HDTV)的關(guān)鍵技術(shù)。國際上先后制定的標(biāo)準(zhǔn)H.261、JPEG、MPEG—1和MPEG—2中均使用了離散余弦變換(DCT)算法。近年來發(fā)展起來的小波(Wavelet)變換也是一種具有高壓縮比和快速運(yùn)算特點(diǎn)的嶄新壓縮技術(shù)，應(yīng)用前景十分廣闊，可望成為新一代壓縮技術(shù)的標(biāo)準(zhǔn)。年代 特點(diǎn) $/MIPS60年代 大學(xué)探索 $100-$1,00070年代 軍事運(yùn)用 $10-$10080年代 商用成功 $1-$1090年代 進(jìn)入消費(fèi)類電子$0.1-$1今后 生活用品 $0.01-$0.1四、各種數(shù)字信息系統(tǒng)數(shù)字信號(hào)處理不斷開辟新的應(yīng)用領(lǐng)域在機(jī)械制造中，基于FFT算法的頻譜分析儀用于振動(dòng)分析和機(jī)械故障診斷；醫(yī)學(xué)中使用數(shù)字信號(hào)處理技術(shù)對(duì)心電(ECG)和腦電(EEG)等生物電信號(hào)作分析和處理；數(shù)字音頻廣播(DAB)廣泛地使用了數(shù)字信號(hào)處理技術(shù)?？梢哉f，數(shù)字信號(hào)處理技術(shù)已在信息處理領(lǐng)域引起了廣泛的關(guān)注和高度的重視。五、數(shù)字信號(hào)處理系統(tǒng)的實(shí)現(xiàn)軟件實(shí)現(xiàn)軟件實(shí)現(xiàn)是用一臺(tái)通用的數(shù)字計(jì)算機(jī)運(yùn)行數(shù)字信號(hào)處理程序。其優(yōu)點(diǎn)是經(jīng)濟(jì)，一機(jī)可以多用；缺點(diǎn)是處理速度慢，這是由于通用數(shù)字計(jì)算機(jī)的體系結(jié)構(gòu)并不是為某一種特定算法而設(shè)計(jì)的。在許多非實(shí)時(shí)的應(yīng)用場(chǎng)合，可以采用軟件實(shí)現(xiàn)方法。例如，處理一盤混有噪聲的錄像(音)帶，我們可以將圖像(聲音)信號(hào)轉(zhuǎn)換成數(shù)字信號(hào)并存入計(jì)算機(jī)，用較長的時(shí)間一幀幀地處理這些數(shù)據(jù)。處理完畢后，再實(shí)時(shí)地將處理結(jié)果還原成一盤清晰的錄像(音)帶。通用計(jì)算機(jī)即可完成上述任務(wù)，而不必花費(fèi)較大的代價(jià)去設(shè)計(jì)一臺(tái)專用數(shù)字計(jì)算機(jī)。硬件實(shí)現(xiàn)硬件實(shí)現(xiàn)是針對(duì)特定的應(yīng)用目標(biāo)，經(jīng)優(yōu)化，設(shè)計(jì)一專用的軟硬件系統(tǒng)。其優(yōu)點(diǎn)是容易做到實(shí)時(shí)處理，缺點(diǎn)是設(shè)備只能專用。片上系統(tǒng)（SOC,SystemonaChip）隨著大規(guī)模集成電路的發(fā)展，一個(gè)復(fù)雜數(shù)字信號(hào)處理系統(tǒng)已可以集成在一個(gè)芯片上。SOC包含有數(shù)字和模擬電路、模擬和數(shù)字轉(zhuǎn)換電路、微處理器、微控制器以及數(shù)字信號(hào)處理器等。與傳統(tǒng)的集成電路不同的是，嵌入式軟件的設(shè)計(jì)也被集成到了SOC的設(shè)計(jì)流程中，SOC的設(shè)計(jì)方法將以組裝為基礎(chǔ)，采用自上至下的設(shè)計(jì)方法，在設(shè)計(jì)過程中大量重復(fù)使用自行設(shè)計(jì)或其他第三方擁有知識(shí)產(chǎn)權(quán)的IP(IntelligentProperty)模塊。SOC要充分考慮如何合理劃分軟件和硬件所實(shí)現(xiàn)的系統(tǒng)功能以及如何實(shí)現(xiàn)軟、硬件之間的信息傳遞。SOC將是數(shù)字信號(hào)處理系統(tǒng)的一個(gè)新型的實(shí)現(xiàn)方法。并行、復(fù)用和流水并行是指為了完成同一個(gè)任務(wù)，幾個(gè)處理器同時(shí)工作，使系統(tǒng)能勝任單個(gè)處理器所不能完成的任務(wù)；當(dāng)一個(gè)處理器完成單個(gè)任務(wù)(比如一個(gè)濾波器)有很大的富余量時(shí)，可讓其完成多個(gè)任務(wù)，這就是復(fù)用；流水結(jié)構(gòu)也是多處理器完成同一任務(wù)，它與并行結(jié)構(gòu)的主要區(qū)別在于并行的各個(gè)處理器之間數(shù)據(jù)交換不多，而流水結(jié)構(gòu)類似于生產(chǎn)中的流水線，數(shù)據(jù)經(jīng)一道道“工序”處理。采用并行或流水結(jié)構(gòu)，完全取決于數(shù)字信號(hào)處理的運(yùn)算結(jié)構(gòu)。研究內(nèi)容

經(jīng)典的數(shù)字信號(hào)處理限于線性時(shí)不變系統(tǒng)理論,數(shù)字濾波和FFT是常用方法。

目前DSP研究熱點(diǎn)：時(shí)變非線性系統(tǒng)、非平穩(wěn)信號(hào)、非高斯信號(hào)

處理方法的發(fā)展：自適應(yīng)濾波、離散小波變換、高階矩分析、盲處理、分形、混沌理論課程介紹基礎(chǔ)理論：離散時(shí)間信號(hào)與系統(tǒng)（ch1）Z變換（ch2）

離散傅立葉變換DFT（ch3）

快速傅立葉變換FFT（ch4）

數(shù)字濾波器

無限長單位脈沖響應(yīng)（IIR）濾波器(ch5)

有限長單位脈沖響應(yīng)（FIR）濾波器(ch6)

第一章離散時(shí)間信號(hào)離散時(shí)間信號(hào)線性移不變系統(tǒng)常系數(shù)線性差分方程連續(xù)時(shí)間信號(hào)的抽樣學(xué)習(xí)要求：熟練掌握和運(yùn)用采樣定理；掌握離散時(shí)間信號(hào)與系統(tǒng)的定義；會(huì)判定系統(tǒng)的因果性和穩(wěn)定性。1.1離散時(shí)間信號(hào)一、主要常用序列（１）單位脈沖序列...0...0123-1nu(n)1……1……N-1n（３）矩形序列（４）實(shí)指數(shù)序列（５）正弦序列x(n)=sin（nω0注意：正弦型序列不一定是周期序列（6）復(fù)指數(shù)序列當(dāng)時(shí)x(n)的實(shí)部和虛部，分別是余弦和正弦序列。二、序列的運(yùn)算1、序列的移位y(n)=x(n-m)當(dāng)m為正時(shí)，x(n-m)表示依次右移m位；x(n+m)表示依次左移m位。2、序列的相加z(n)=x(n)+y(n)是指同序號(hào)n的序列值逐項(xiàng)對(duì)應(yīng)相加得一新序列。3、序列的相乘f(n)=x(n)y(n)是指同序號(hào)(n)的序列值逐項(xiàng)對(duì)應(yīng)相乘。4、序列的翻褶如果有x(n),則x(-n)是以n=0為對(duì)稱軸將x(n)加以翻褶的序列。5、序列的累加表示n以前的所有x(n)的和。6、前向差分和后向差分（先左移后相減）；（先右移后相減）7、序列的尺度變換抽?。簒(n)x(mn),m為正整數(shù)；插值：x(n)x(n/m),m為正整數(shù)。圖1-1序列x(n)及超前序列x(n+1)圖1-5序列x(n)及其累加序列y(n)圖1-2兩序列相加圖1-3序列x(n)及翻褶后的序列x(-n)圖1-7某序列及其抽取序列8、序列的卷積和設(shè)序列x(n),h(n),它們的卷積和y(n)定義為卷積和計(jì)算分四步：折迭(翻褶),位移,相乘,相加。圖1-8x(n)和h(n)的卷積和圖解三、序列的周期性如果存在一個(gè)最小的正整數(shù)N,滿足x(n)=x(n+N),則序列x(n)為周期性序列,N為周期。四、用單位抽樣序列表示任意序列1、任意序列可表示成單位抽樣序列的位移加權(quán)和.2.、x(n)亦可看成x(n)和δ(n)的卷積和五、序列的能量x(n)的能量定義為1-2線性移不變系統(tǒng)一、線性系統(tǒng)系統(tǒng)實(shí)際上表示對(duì)輸入信號(hào)的一種運(yùn)算，所以離散時(shí)間系統(tǒng)就表示對(duì)輸入序列的運(yùn)算，即x(n)x(n)離散時(shí)間系統(tǒng)T[x(n)]y(n)y(n)=T[x(n)]線性系統(tǒng)具有均勻性和迭加性：*加權(quán)信號(hào)和的響應(yīng)=響應(yīng)的加權(quán)和。*先運(yùn)算后系統(tǒng)操作=先系統(tǒng)操作后運(yùn)算。二、移不變系統(tǒng)如T[x(n)]=y(n),則T[x(n-m)]=y(n-m),滿足這樣性質(zhì)的系統(tǒng)稱作移不變系統(tǒng)。即系統(tǒng)參數(shù)不隨時(shí)間變化的系統(tǒng)，亦即輸出波形不隨輸入加入的時(shí)間而變化的系統(tǒng)。*系統(tǒng)操作=函數(shù)操作三、單位抽樣響應(yīng)與卷積和四.線性移不變系統(tǒng)的性質(zhì)1.交換律2.結(jié)合律3.對(duì)加法的分配律五.因果系統(tǒng)某時(shí)刻的輸出只取決于此刻以及以前時(shí)刻的輸入的系統(tǒng)稱作因果系統(tǒng)。*實(shí)際系統(tǒng)一般是因果系統(tǒng)；*對(duì)圖象、已記錄數(shù)據(jù)處理以及平均處理的系統(tǒng)不是因果系統(tǒng)；*y(n)=x(-n)是非因果系統(tǒng),因n<0的輸出決定n>0時(shí)的輸入;線性移不變因果系統(tǒng)的充要條件為h(n)=0，n<0。六.穩(wěn)定系統(tǒng)有界的輸入產(chǎn)生有界的輸出系統(tǒng)。線性移不變穩(wěn)定系統(tǒng)的充要條件是1-3常系數(shù)線性差分方程離散變量n的函數(shù)x(n)及其位移函數(shù)x(n-m)線性疊加而構(gòu)成的方程.一.表示法與解法1.表示法*常系數(shù)：a0,a1,…,aN;b0,b1,…,bM均是常數(shù)（不含n）.*階數(shù)：y(n)變量n的最大序號(hào)與最小序號(hào)之差，如N=N-0.*線性：y(n-k),x(n-m)各項(xiàng)只有一次冪,不含它們的乘積項(xiàng)。2.解法時(shí)域：迭代法，卷積和法;變換域：Z變換法.二.用迭代法求解差分方程1.“松弛”系統(tǒng)的輸出起始狀態(tài)為零的系統(tǒng)，這種系統(tǒng)用的較多，其輸出就是。因此，已知h(n)就可求出y(n)，所以必須知道h(n)的求法.2.迭代法（以求h(n)為例）例:已知常系數(shù)線性差分方程為y(n)-ay(n-1)=x(n)，試求單位抽樣響應(yīng)h(n).解：因果系統(tǒng)有h(n)=0,n<0;方程可寫作:y(n)=ay(n-1)+x(n)

注意：1.一個(gè)常系數(shù)線性差分方程并不一定代表因果系統(tǒng)，也不一定表示線性移不變系統(tǒng)。這些都由邊界條件（初始）所決定。2.我們討論的系統(tǒng)都假定：常系數(shù)線性差分方程就代表線性移不變系統(tǒng)，且多數(shù)代表因果系統(tǒng)。三.系統(tǒng)結(jié)構(gòu)1.系統(tǒng)的輸入與輸出的運(yùn)算關(guān)系的表述方法。2.差分方程可直接得到系統(tǒng)結(jié)構(gòu)。例：y(n)=b0x(n)-a1y(n-1)用⊕表示相加器；用表示乘法器；用表示一位延時(shí)單元。例：差分方程y(n)=b0x(n)-a1y(n-1)表示的系統(tǒng)結(jié)構(gòu)為：1-4連續(xù)時(shí)間信號(hào)的抽樣一.抽樣器與抽樣1.抽樣器2.抽樣對(duì)信號(hào)進(jìn)行時(shí)間上的量化，這是對(duì)信號(hào)作數(shù)字化處理的第一個(gè)環(huán)節(jié)。問題：信號(hào)經(jīng)采樣后發(fā)生的變化（如頻譜的變化）；信號(hào)內(nèi)容是否丟失（采樣序列能否代表原始信號(hào)、如何不失真地還原信號(hào)）；由離散信號(hào)恢復(fù)連續(xù)信號(hào)的條件？2.實(shí)際抽樣與理想抽樣實(shí)際抽樣：p(t)為脈沖序列抽樣器一般由電開關(guān)組成，開關(guān)每隔Ｔ秒短暫地閉合一次，將連續(xù)信號(hào)接通，實(shí)現(xiàn)一次采樣。如開關(guān)每次閉合τ秒，則采樣器的輸出是一串重復(fù)周期為T，寬度為τ的脈沖，脈沖的幅度是這段時(shí)間內(nèi)信號(hào)的幅度，如圖1.1(d)，這一采樣過程可看作是一個(gè)脈沖調(diào)幅過程，脈沖載波是一串周期為T、寬度為τ的矩形脈沖，以P(t)表示,調(diào)制信號(hào)是輸入的連續(xù)信號(hào)xa(t)，則采樣輸出為Xp(t)=Xa(t)P(t)一般τ很小,τ越小，采樣輸出脈沖的幅度越接近輸入信號(hào)在離散時(shí)間點(diǎn)上的瞬時(shí)值。理想抽樣：（沖激序列）當(dāng)抽樣器的電開關(guān)閉合時(shí)間τ→0時(shí)，為理想采樣。采樣序列表示為沖激函數(shù)的序列，這些沖激函數(shù)準(zhǔn)確地出現(xiàn)在采樣瞬間，其積分幅度準(zhǔn)確地等于輸入信號(hào)在采樣瞬間的幅度，即：理想采樣可看作是對(duì)沖激脈沖載波的調(diào)幅過程。理想采樣信號(hào)的數(shù)學(xué)表示：用M(t)表示沖擊載波，

則有理想采樣信號(hào)可表示為：說明：實(shí)際情況下，τ＝0達(dá)不到，但τ<<T時(shí)，實(shí)際采樣接近理想采樣，理想采樣可看作是實(shí)際采樣物理過程的抽象，便于數(shù)學(xué)描述，可集中反映采樣過程的所有本質(zhì)特性，理想采樣對(duì)Z變換分析相當(dāng)重要。3.采樣信號(hào)的頻譜1)頻譜延拓問題：理想采樣信號(hào)的頻譜有何特點(diǎn)，它與連續(xù)信號(hào)頻譜的關(guān)系？對(duì)理想采樣信號(hào)進(jìn)行傅立葉變換，可以證明，理想采樣信號(hào)的頻譜是連續(xù)信號(hào)頻譜的周期延拓，重復(fù)周期為Ws(采樣頻率)，即其中為理想采樣信號(hào)的頻譜，為連續(xù)信號(hào)的付氏變換。顯然，是頻率Ω的連續(xù)函數(shù)。數(shù)字角頻率

如果定義并且將的自變量用ω表示，周期用ωs表示，則ωs=ΩsT=2π即的周期為2π。ω即為數(shù)字角頻率，它是模擬域頻率對(duì)采樣頻率fs的歸一化。數(shù)字角頻率代表了序列值變化快慢的速率，它只有相對(duì)的時(shí)間意義，而沒有絕對(duì)時(shí)間和頻率的意義。2)采樣定理

如果信號(hào)xa(t)是實(shí)帶限信號(hào)，且最高頻譜不超過Ws/2，即那么理想采樣頻譜中，基帶頻譜以及各次諧波調(diào)制頻譜彼此是不重迭的，用一個(gè)帶寬為Ws/2的理想低通濾波器，可以將各次諧波調(diào)制頻譜濾除，保留不失真的基帶頻譜，從而不失真地還原出原來的連續(xù)信號(hào)。如果信號(hào)最高頻譜超過Ws/2,那么在理想采樣頻譜中,各次調(diào)制頻譜就會(huì)互相交疊,出現(xiàn)頻譜的“混淆”現(xiàn)象，如圖。為簡明起見，圖中將Xa(jW)作為標(biāo)量處理，一般Xa(jW)為復(fù)數(shù),交疊也是復(fù)數(shù)相加。當(dāng)出現(xiàn)頻譜混淆后，一般就不可能無失真地濾出基帶頻譜，用基帶濾波恢復(fù)出來的信號(hào)就要失真。因此，稱采樣頻率的一半Ws/2為折疊頻率，它好像一面鏡子，信號(hào)頻譜超過它時(shí)，就會(huì)被折迭

回來，

造成頻譜混淆。奈奎斯特采樣定理：要使實(shí)信號(hào)采樣后

能夠不失真還原，采樣頻率必須大于信號(hào)最高頻率的兩倍

，即Ωs≥2Ωmax。實(shí)際工作中，為避免頻譜混淆，采樣頻率總是選得

比兩倍信號(hào)最高頻率Wmax更大些，如Ws>(3~5)Wmax。

同時(shí)，為避免高于折疊頻率的雜散頻譜進(jìn)入采樣器造成頻譜混淆，采樣器前常常加一個(gè)保護(hù)性的前置低通濾波器（抗混疊濾波器），阻止高于WS/2頻率分量進(jìn)入?？够殳B濾波器抗混迭濾波器：理想采樣信號(hào)的頻譜是連續(xù)信號(hào)頻譜以采樣頻率為周期的周期延拓，為避免采樣信號(hào)頻譜混迭產(chǎn)生失真而處理頻帶外的高頻分量。

3)采樣信號(hào)的拉氏變換

理想采樣后，信號(hào)的拉氏變換在S平面上沿虛軸周期延拓，也即在S平面上的虛軸上是周期函數(shù)。4、采樣的恢復(fù)（恢復(fù)信號(hào)）如果理想采樣滿足奈奎斯特定理，信號(hào)最高頻率不超過折迭頻率，即則理想采樣的頻譜就不會(huì)產(chǎn)生混疊，因此有，│W│<WS

可見，將采樣信號(hào)通過一個(gè)理想低通濾波器（只讓基帶頻譜通過），其帶寬等于折迭頻率WS/2，頻率特性如圖1.5。采樣信號(hào)通過此濾波器后，就可濾出原信號(hào)的頻譜：也就恢復(fù)了模擬信號(hào)：y(t)=xa(t)。

實(shí)際上，理想低通濾波器是不可能實(shí)現(xiàn)的，但在滿足一定精度的情況下，總可用一個(gè)可實(shí)現(xiàn)網(wǎng)絡(luò)去逼近。5、采樣內(nèi)插公式問題：如何由采樣信號(hào)表示連續(xù)信號(hào)，采樣信號(hào)通過理想低通濾波器G(jW)的響應(yīng)是什么？內(nèi)插公式推導(dǎo)理想低通G(jW)的沖激響應(yīng)為頻域相乘對(duì)應(yīng)時(shí)域卷積，利用卷積公式，則采樣信號(hào)經(jīng)理想低通后的輸出為這里，g(t-nT)稱為內(nèi)插函數(shù)，其特點(diǎn)為：在采樣點(diǎn)nT上，函數(shù)值為1，其余采樣點(diǎn)上為零。

將內(nèi)插函數(shù)代入前面的卷積公式，可得采樣內(nèi)插公式：

采樣內(nèi)插公式告訴我們，連續(xù)函數(shù)xa(t)可以由它的采樣值xa(nT)來表示，它等于xa(nT)乘上對(duì)應(yīng)的內(nèi)插函數(shù)的總和，即其中為內(nèi)插函數(shù)，如圖1.6。

圖1.7為由采樣內(nèi)插恢復(fù)的連續(xù)信號(hào)。圖中，在每一個(gè)采樣點(diǎn)上，由于只有該采樣值對(duì)應(yīng)的內(nèi)插函數(shù)不為零，所以保證了各采樣點(diǎn)上信號(hào)值不變，而采樣之間的信號(hào)則由各采樣值內(nèi)插函數(shù)的波形延伸迭加而成。內(nèi)插公式表明只要滿足采樣頻率高于兩倍信號(hào)最高頻率，整個(gè)連續(xù)信號(hào)就可以用它的采樣值完全代表，而不損失任何信息，這就是奈奎斯特定律?？偨Y(jié)：要想抽樣后能不失真的還原出原信號(hào)，抽樣頻率必須大于等于兩倍原信號(hào)最高頻率分量。即這就是奈奎斯特取樣定理。例1.已知一模擬信號(hào)x(t)=3cos(20πt)+5sin(60πt)+10cos(120πt)，fs=50Hz。試求：抽樣后的x(n)，若從x(n)信號(hào)恢復(fù)成連續(xù)信號(hào)，是否與原模擬信號(hào)一樣，為什么？例3.一個(gè)聲音信號(hào)x(t)=2Acos(10000πt)+2Bcos(30000πt)+2Ccos(50000πt)+2Dcos(60000πt)試問（1）這個(gè)信號(hào)是由哪些頻率構(gòu)成的？(t:ms)（2）信號(hào)的哪些部分是可以聽到的，為什么？（3）如果前置濾波器的截止頻率為20kHz，聽到的是什么？x(tx(t)y(n)ya(t)y(t)fs=40kHz抽樣器D/A前置濾波器H（f）第一章習(xí)題分類：§1.1——1，2，3，4§1.2——5，6，7，8§1.3——9，10§1.4——11綜合題：12提高題：13補(bǔ)充題：14第二章z變換Z變換Z反變換Z變換性質(zhì)Z變換，拉氏變換與DFT傅里葉變換之間的關(guān)系系統(tǒng)響應(yīng)與頻率響應(yīng)學(xué)習(xí)要求：熟練掌握付氏變換、Z變換和系統(tǒng)函數(shù)。2-1引言信號(hào)與系統(tǒng)的分析方法有時(shí)域、變換域兩種。一.時(shí)域分析法1.連續(xù)時(shí)間信號(hào)與系統(tǒng)：信號(hào)的時(shí)域運(yùn)算，時(shí)域分解，經(jīng)典時(shí)域分析法，近代時(shí)域分析法，卷積積分。2.離散時(shí)間信號(hào)與系統(tǒng)：序列的變換與運(yùn)算，卷積和，差分方程的求解。二.變換域分析法1.連續(xù)時(shí)間信號(hào)與系統(tǒng)：信號(hào)與系統(tǒng)的頻域分析、復(fù)頻域分析。2.離散時(shí)間信號(hào)與系統(tǒng)：Z變換，DFT(FFT)。Z變換可將差分方程轉(zhuǎn)化為代數(shù)方程。2.2Z變換一、Z變換的定義利用差分方程可求離散系統(tǒng)的結(jié)構(gòu)及瞬態(tài)解。為了分析系統(tǒng)的另外一些重要特性，如穩(wěn)定性和頻率響應(yīng)等，需要研究離散時(shí)間系統(tǒng)的z變換（類似于模擬系統(tǒng)的拉氏變換），它是分析離散系統(tǒng)和離散信號(hào)的重要工具。

一個(gè)離散序列x（n）的Z變換定義為，其中z為復(fù)變量，是一個(gè)以實(shí)部為橫坐標(biāo)，虛部為縱坐標(biāo)構(gòu)成的平面上的變量，這個(gè)平面也稱z平面。雙邊z變換定義為：

單邊z變換定義為：，即只對(duì)單邊序列（n>=0部分）進(jìn)行z變換。

單邊z變換可以看成是雙邊z變換的一種特例，即因果序列情況下的雙邊z變換。二、z變換的收斂域一般，序列的Z變換并不一定對(duì)任何z值都收斂，z平面上使上述級(jí)數(shù)收斂的區(qū)域稱為“收斂域”。一般Z變換的收斂域?yàn)椋篟x-〈|z|〈Rx+

我們知道，級(jí)數(shù)一致收斂的條件是絕對(duì)值可和，因此z平面的收斂域應(yīng)滿足因?yàn)閷?duì)于實(shí)數(shù)序列，因此，|z|值在一定范圍內(nèi)才能滿足絕對(duì)可和條件，這個(gè)范圍一般表示為Rx-〈|z|〈Rx+。這就是收斂域，一個(gè)以Rx-和Rx+為半徑的兩個(gè)圓所圍成的環(huán)形區(qū)域，Rx-和Rx+稱為收斂半徑，Rx-和Rx+的大小，即收斂域的位置與具體序列有關(guān)，特殊情況為Rx-或Rx+等于0，這時(shí)圓環(huán)變成圓或空心圓。四種序列的Z變換收斂域a.有限長序列

序列,其Z變換,收斂域?yàn)?<|z|<∞。

因?yàn)閄(z)是有限項(xiàng)的級(jí)數(shù)和，只要級(jí)數(shù)每一項(xiàng)有界，有限項(xiàng)和也有界，所以有限長序列z變換的收斂域取決于|z|-n<∞，n1≤n≤n2

顯然|z|在整個(gè)開域（0，∞）都能滿足以上條件，因此有限長序列的收斂域是除0及∞兩個(gè)點(diǎn)（對(duì)應(yīng)n>0和n<0不收斂）以外的整個(gè)Z平面：0<|z|<∞。如果對(duì)n1，n2加以一定的限制，如n1≥0或n2≤0，則根據(jù)條件|z|-n<∞（n1≤n≤n2），收斂域可進(jìn)一步擴(kuò)大為包括0點(diǎn)或∞點(diǎn)的半開域：例1、序列x(n)=δ(n)由于n1=n2=0，其收斂域?yàn)檎麄€(gè)閉域子平面，0例2．矩形序列x（n）=RN（n）等比級(jí)數(shù)求和b.右邊序列指x（n）只在n≥n1，有值，而n〈n1時(shí)，x（n）=0，這時(shí)其收斂域?yàn)槭諗堪霃絉x-以外的z平面，即|z|>Rx-。右邊序列中最重要的一種序列是“因果序列”即n1=0的右邊序列，因果序列只在n≥0有值，n〈0時(shí)，x（n）=0，其z變換為：z變換的收斂域包括∞點(diǎn)是因果序列的特征。證明：

如果n1<0,則選擇任一整數(shù)n2>0,使得由于第一項(xiàng)為有限長序列的Z變換，在（0，∞）收斂。對(duì)于第二項(xiàng)，總能在（0，∞）找到|z|=R（如R≥2MAX[X(n)])滿足所以X(z)在|z|=R上收斂。

由此可進(jìn)一步證明，在R圓以外，即R<|z|<∞，x（Z）也必收斂。

再看第二項(xiàng)，由于n>n2≥0，|Z|>R，因此|z|-n<R-n，故

∴由此證明右邊序列的收斂域?yàn)閨z|〉Rx-。c.左邊序列

序列x（n）只在n≤n2有值，n〉n2時(shí)，x（n）=0其收斂域在收斂半徑為Rx+的圓內(nèi)，即|Z|〈Rx+。證明：

如x（z）在|z|=R上收斂，即則在0〈|z|〈R上也必收斂，任選一整數(shù)n1≤0，∴整個(gè)級(jí)數(shù)在|z|〈R上有收斂域|z|<Rx+。d.雙邊序列

可看作一個(gè)左邊序列和一個(gè)右邊序列之和，因此雙邊序列z變換的收斂域是這兩個(gè)序列z變換收斂域的公共部分。

如果Rx+>Rx-，則存在公共的收斂區(qū)間，X（z）有收斂域，Rx-<|z|<Rx-如果Rx+<Rx-，無公共收斂區(qū)間，X（z）無收斂域，不收斂。z變換收斂域的特點(diǎn)：收斂域是一個(gè)圓環(huán)，有時(shí)可向內(nèi)收縮到原點(diǎn)，有時(shí)可向外擴(kuò)展到∞，只有x（n）=δ（n）的收斂域是整個(gè)z平面；在收斂域內(nèi)沒有極點(diǎn)，x（z）在收斂域內(nèi)每一點(diǎn)上都是解析函數(shù)。z變換表示法：級(jí)數(shù)形式；解析表達(dá)式（注意只表示收斂域上的函數(shù)，同時(shí)要注明收斂域）。2.3反Z變換已知函數(shù)X(z)及其收斂域，反過來求序列x(n)的變換稱為逆z變換，常用Z-1[X(z)]表示。若則逆z變換的一般公式為逆z變換是一個(gè)對(duì)X（z）zn-1進(jìn)行的圍線積分，積分路徑C是一條在X（z）收斂環(huán)域（Rx-，Rx+）以內(nèi)反時(shí)針方向繞原點(diǎn)一周的單圍線。證明：設(shè)積分路徑C在半徑為R的圓上，k=n-m，即z=Rejθ，Rx-<R<Rx+，則這個(gè)公式稱為柯西積分定理。因此或直接計(jì)算圍線積分比較麻煩，一般不采用此法求Z反變換。

求解逆z變換的常用方法有：冪級(jí)數(shù)留數(shù)定律法部分分式法

如果得到的z變換是冪級(jí)數(shù)形式的，則可以看出，序列值x(n)是冪級(jí)數(shù)中z-n項(xiàng)的系數(shù)，如果已經(jīng)給出X(z)的函數(shù)表示，我們常?？梢酝茖?dǎo)它的冪級(jí)數(shù)展開式或者利用已知的冪級(jí)數(shù)展開式。用長除法可獲得冪級(jí)數(shù)展開式。

對(duì)于有理的z變換，圍線積分通常可用留數(shù)定律計(jì)算，x(n)＝∑Res[X(z)zn-1，zk]，即為X(z)zn-1在圍線C內(nèi)所有極點(diǎn){zk}上留數(shù)值的總和。

如果zk是單階極點(diǎn)，則Res[X(z)zn-1，zk]＝(ｚ－zk)X(z)zn-1=zk；

如果zk是N階極點(diǎn)，則。

常用序列z變換：2.4z變換的性質(zhì)

z變換的許多重要性質(zhì)在數(shù)字信號(hào)處理中常常要用到。序列z變換收斂域1)x(n)X(z)Rx-<|z|<Rx+2)y(n)Y(z)Ry-<|z|<Ry+3)ax(n)+by(n)aX(z)＋bY(z)max[Rx-+Ry-]<|z|<min[Rx+,Ry+]4)x(n+no)znoX(z)Rx-<|z|<Rx+5)anx(n)X(a-1z)|a|Rx-<|z|<|a|Rx+6)nx(n)Rx-<|z|<Rx+7)x*(n)X*(z*)Rx-<|z|<Rx+8)x(-n)X(1/z)1/Rx-<|z|<1/Rx+9)x(n)*y(n)X(z)Y(z)max[Rx-+Ry-]<|z|<min[Rx+,Ry+]10)x(n)y(n)Rx-Ry-<|z|<Rx+Ry+11)x(0)=x(∞)(因果序列)|z|>Rx-12)x(∞)=Res[X(z),1](z-1)X(z)收斂于|z|≥1

z變換的性質(zhì)可由正反z變換的定義直接推導(dǎo)而得。

例：性質(zhì)5）

性質(zhì)6）帕塞伐爾（Parseval）定理——z變換的重要性質(zhì)之一

若有兩序列x（n），y（n），且X（z）=Z[x（n）]Rx-〈|z|〈Rx+Y（z）=Z[y（n）]Ry-〈|z|〈Ry+

它們的收斂域滿足條件：Rx-Ry-〈1，Rx+Ry+〉1則，C所在收斂域在X(v)和Y*(1/v*)兩者收斂區(qū)域的重迭范圍內(nèi)Max[Rx-,1/Ry+]<|v|<min[Rx+,1/Ry-]。證明：令w（n）=x(n)*y(n)

利用復(fù)序列共軛及復(fù)數(shù)乘積特性：則由于假設(shè)條件中已規(guī)定收斂域滿足

Rx-Ry-〈1〈Rx+Ry+因此|z|=1在收斂域內(nèi)，即W(z)在單位圓上收斂，W(z)|z=1存在， 又因因此。

證畢。如果X(v)、Y(v)在單位圓上收斂，則選取單位圓為圍線積分途徑，這時(shí)v=ejω序列能量的計(jì)算：

Parseval定理的一個(gè)重要應(yīng)用是計(jì)算序列能量。因

可見，時(shí)域中對(duì)序列求能量與頻域中求能量是一致的。2.5Z變換，拉氏變換與DFT傅里葉變換之間的關(guān)系序列的z變換：即連續(xù)時(shí)間信號(hào)的Laplace變換：即連續(xù)時(shí)間信號(hào)的Fourier變換：即一.Z變換與拉氏變換的關(guān)系1.理想抽樣信號(hào)的拉氏變換設(shè)為連續(xù)信號(hào)，為其理想抽樣信號(hào)，它們的Laplace變換分別為：則而故序列x(n)的z變換為，考慮到,顯然，當(dāng)時(shí)，序列x(n)的z變換就等于理想抽樣信號(hào)的拉氏變換。2.Z變換與拉氏變換的關(guān)系(S、Z平面映射關(guān)系）S平面用直角坐標(biāo)表示為：Z平面用極坐標(biāo)表示為：又由于所以有：因此， ;這就是說，Z的模只與S的實(shí)部相對(duì)應(yīng),Z的相角只與S虛部Ω相對(duì)應(yīng)。(1).r與σ的關(guān)系σ=0,即S平面的虛軸r=1,即Z平面單位圓；σ<0,即S的左半平面r<1,即Z的單位圓內(nèi)；σ>0,即S的右半平面r>1,即Z的單位圓外。(2).ω與Ω的關(guān)系（ω=ΩT）Ω=0，S平面的實(shí)軸， ω=0，Z平面正實(shí)軸；

(常數(shù))，S:平行實(shí)軸的直線，,Z:始于原點(diǎn)的射線；

S:寬 的水平條帶，整個(gè)z平面.二.Z變換和傅氏變換的關(guān)系連續(xù)信號(hào)經(jīng)理想抽樣后,其頻譜產(chǎn)生周期延拓，即我們知道,傅氏變換是拉氏變換在虛軸S=jΩ的特例,因而映射到Z平面上為單位圓。因此,這就是說,（抽樣）序列在單位圓上的Z變換,就等于理想抽樣信號(hào)傅氏變換。用數(shù)字頻率ω作為Z平面的單位圓的參數(shù)，ω表示Z平面的輻角，模擬頻率Ω為s平面虛軸，則有所以，序列在單位圓上的Z變換為序列的傅氏變換。2.6系統(tǒng)函數(shù)與頻率響應(yīng)一、系統(tǒng)函數(shù)1、定義

我們知道，用單位脈沖響應(yīng)h(n)可以表示線性時(shí)不變離散系統(tǒng)，這時(shí)y（n）=x（n）*h（n）兩邊取z變換

Y(z)=X(z)H(z)則定義為系統(tǒng)函數(shù)。它是單位脈沖響應(yīng)的z變換。單位圓上的系統(tǒng)函數(shù)z=ejω就是系統(tǒng)的頻率響應(yīng)。所以可以用單位脈沖響應(yīng)的z變換來描述線性時(shí)不變離散系統(tǒng)。2、幾種常用系統(tǒng)因果系統(tǒng)——單位脈沖響應(yīng)h（n）是因果序列的系統(tǒng)，其系統(tǒng)函數(shù)H(z)具有包括∞點(diǎn)的收斂域：Rx-<|Z|≤∞穩(wěn)定系統(tǒng)：單位脈沖響應(yīng)h（n）滿足絕對(duì)可和，

因此穩(wěn)定系統(tǒng)的H（z）必須在單位圓上收斂，即H(ejω)存在。因果穩(wěn)定系統(tǒng)：最普遍最重要的一種系統(tǒng)，其系統(tǒng)函數(shù)H（z）必須在從單位圓到∞的整個(gè)領(lǐng)域收斂，即1≤∣Z|≤∞，H（z）的全部極點(diǎn)在單位圓以內(nèi)。因此，因果穩(wěn)定系統(tǒng)的系統(tǒng)函數(shù)的全部極點(diǎn)必須在單位圓以內(nèi)。3、差分方程與系統(tǒng)函數(shù)

我們知道，線性時(shí)不變離散系統(tǒng)也可用差分方程表示，考慮N階差分方程兩邊取z變換：于是上式的分子與分母多項(xiàng)式也可用因子的形式來表示式中{ci}是H（z）在z平面上的零點(diǎn)，{di}是H（z）在z平面上的極點(diǎn)，因此，除比例常數(shù)A以外，整個(gè)系統(tǒng)函數(shù)可以由全部零、極點(diǎn)來唯一確定。4、系統(tǒng)函數(shù)的收斂域

用系統(tǒng)函數(shù)H（z）表示一個(gè)系統(tǒng)時(shí)，H（z）的收斂域?qū)Υ_定系統(tǒng)性質(zhì)很重要。相同的系統(tǒng)函數(shù),收斂域不同,所代表的系統(tǒng)可能完全不同。

例1：已知系統(tǒng)函數(shù)為求系統(tǒng)的單位脈沖響應(yīng)及系統(tǒng)性質(zhì)。

系統(tǒng)函數(shù)H（z）有兩個(gè)極點(diǎn)，z1=0.5,z2=10。收斂域包括∞點(diǎn)，因此系統(tǒng)一定是因果系統(tǒng)，但單位圓不在收斂域內(nèi)，因此可判定系統(tǒng)是不穩(wěn)定的。

例2：系統(tǒng)函數(shù)不變,但收斂域不同求單位脈沖響應(yīng)及系統(tǒng)性質(zhì)。

解:收斂域是包括單位圓而不包括∞點(diǎn)的有限環(huán)域，判定系統(tǒng)是穩(wěn)定的,但是非因果的。

用留數(shù)定理求H(z)的反變換:注意到極點(diǎn)z2=10在積分圍線（收斂域內(nèi)的圍線）以外,并且要考慮n<0時(shí),有一n階極點(diǎn)出現(xiàn)在z=0處，因此由于存在u(-n-1)項(xiàng)，因此系統(tǒng)是非因果的，同時(shí)也不難證明h(n)是絕對(duì)可積的，所以系統(tǒng)是穩(wěn)定的.以上兩例表明,同一個(gè)系統(tǒng)函數(shù),由于收斂域不同,它們所代表的系統(tǒng)完全不同。二、系統(tǒng)頻響的幾何確定法

用極點(diǎn)和零點(diǎn)表示系統(tǒng)函數(shù)的優(yōu)點(diǎn)是，它提供了一種有效的求系統(tǒng)頻率響應(yīng)的幾何方法。

一個(gè)N階的系統(tǒng)函數(shù)可用它的零極點(diǎn)表示為系統(tǒng)的頻響為:在z平面上,ejω-ci可用一根由零點(diǎn)ci指向單位圓上ejω點(diǎn)的向量來表示，而ejω-di可用極點(diǎn)di指向ejω的向量表示。于是令則

分析上式表明，頻響的模函數(shù)由從各零、極點(diǎn)指向ejω點(diǎn)的向量幅度來確定，而頻響的相位函數(shù)則由這些向量的幅角來確定，當(dāng)頻率ω由0—2π時(shí)，這些向量的終端點(diǎn)沿單位圓反時(shí)針方向旋轉(zhuǎn)一圈，由此可估算出整個(gè)系統(tǒng)的頻響來。

其基本原理是，當(dāng)單位圓上的ejω點(diǎn)在極點(diǎn)di附近時(shí)，向量最短，qi出現(xiàn)極小值，頻響在這附近可能出現(xiàn)峰值，且極點(diǎn)di越靠近單位圓，qi的極小值越小，頻響出現(xiàn)的峰值越尖銳，當(dāng)di處在單位圓上時(shí)，qi的極小值為零，相應(yīng)的頻響將出現(xiàn)∞，這相當(dāng)于在該頻率處出現(xiàn)無耗（Q=∞）諧振，當(dāng)極點(diǎn)超出單位圓時(shí)系統(tǒng)就處于不穩(wěn)定狀態(tài)。對(duì)于現(xiàn)實(shí)系統(tǒng)，這是不希望的。

對(duì)于零點(diǎn)位置，頻響將正好相反，ejω點(diǎn)越接近某零點(diǎn)ci，頻響越低，因此在零點(diǎn)附近，頻響出現(xiàn)谷點(diǎn)，零點(diǎn)越接近單位圓，谷點(diǎn)越接近零，零點(diǎn)處于單位圓上時(shí)，谷點(diǎn)為零，即在零點(diǎn)所在頻率上出現(xiàn)傳輸零點(diǎn)，零點(diǎn)可以位于單位圓以外，不受穩(wěn)定性約束。

這種幾何方法為我們認(rèn)識(shí)零、極點(diǎn)分布對(duì)系統(tǒng)性能的影響提供了一個(gè)直觀的概念，這一概念對(duì)系統(tǒng)的分析和設(shè)計(jì)都十分重要。例3.有限長單位脈沖響應(yīng)0<a<1求其頻率響應(yīng)特性。

解：如果a為正實(shí)數(shù)，H（z）的零點(diǎn)為這些零點(diǎn)分布在|z|=a的圓周上，對(duì)圓周進(jìn)行M等分，它的第一個(gè)零點(diǎn)k=0，恰好與分母上的極點(diǎn)（z-a）抵消，因此，整個(gè)函數(shù)H（z）共有

左圖給出M=8，0〈a〈1時(shí)的系統(tǒng)特性，幅頻的峰值出現(xiàn)在ω=0，因?yàn)樵撎師o零點(diǎn)（被極點(diǎn)對(duì)消），每一零點(diǎn)附近的頻率響應(yīng)均有陷落，呈現(xiàn)出M次起伏，當(dāng)M無限增大時(shí)，波紋趨于平滑，系統(tǒng)函數(shù)趨于書上例4一階系統(tǒng)的結(jié)果。

第三章離散付里葉變換離散付里葉級(jí)數(shù)（DFS）——周期序列離散付里葉變換（DFT）學(xué)習(xí)要求：熟練掌握和運(yùn)用DFT及其有關(guān)性質(zhì)。引言：一、DFT是重要的變換1.分析有限長序列的有用工具。2.在信號(hào)處理的理論上有重要意義。3.在運(yùn)算方法上起核心作用，譜分析、卷積、相關(guān)都可以通過DFT在計(jì)算機(jī)上實(shí)現(xiàn)。二、DFT是現(xiàn)代信號(hào)處理橋梁 DFT要解決兩個(gè)問題：一是離散與量化，二是快速運(yùn)算。傅氏變換的幾種可能形式：非周期連續(xù)時(shí)間、連續(xù)頻率的傅氏變換傅氏變換周期連續(xù)時(shí)間、離散頻率的傅里葉變換傅氏級(jí)數(shù)*時(shí)域周期為Tp,頻域譜線間隔為2π/Tp離散時(shí)間、周期連續(xù)頻率的傅氏變換序列的傅氏變換離散時(shí)間、離散頻率的傅氏變換DFT結(jié)論:時(shí)間函數(shù) 頻率函數(shù) 連續(xù)、非周期性 非周期、連續(xù)連續(xù)、周期性 非周期、離散離散、非周期性周期、連續(xù)離散、周期性周期、離散3-1周期序列的離散付里葉級(jí)數(shù)（DFS）前面我們討論用付里葉變換和z變換來描述一般的序列和線性時(shí)不變離散系統(tǒng)。但有時(shí)序列是有限長序列，如FIR系統(tǒng)的單位脈沖響應(yīng)就是一個(gè)有限長序列。對(duì)于這種情況，正如本章要討論的，可以導(dǎo)出另一種付里葉表示式，稱作離散付里葉變換(DFT)。離散付里葉變換是有限長序列付里葉表示式，它本身也是一個(gè)序列，而不是一個(gè)連續(xù)函數(shù)，它相當(dāng)于把信號(hào)的付里葉變換進(jìn)行等頻率間隔取樣。離散付里葉變換除了作為有限長序列的一種付里葉表示式在理論上相當(dāng)重要外，由于存在計(jì)算離散付里葉變換有效算法，因而其在實(shí)現(xiàn)各種數(shù)字信號(hào)處理算法時(shí)起著核心作用。為了便于更好地理解DFT的概念，先討論周期序列及其離散付里葉級(jí)數(shù)（DFS）表示。離散付里葉級(jí)數(shù)（DFS）

我們用來表示一個(gè)周期為N的周期序列，即，k為任意整數(shù)，N為周期。

一個(gè)周期序列的離散付里葉級(jí)數(shù)為：系數(shù)本身也是一個(gè)周期序列，周期為N。（系數(shù)的求解）

說明：周期序列不能進(jìn)行Z變換，因?yàn)槠湓趎=-￥到+￥都周而復(fù)始永不衰減，在整個(gè)z平面上任何地方找不到一個(gè)衰減因子│z│能使序列絕對(duì)可和：即z平面上沒有收斂域。但是，正象連續(xù)時(shí)間周期信號(hào)可用付氏級(jí)數(shù)表達(dá)，周期序列也可用離散的付氏級(jí)數(shù)來表示，也即用周期為N的正弦序列來表示。

周期為N的正弦序列其基頻成分為：

K次諧波序列為：

但離散級(jí)數(shù)所有諧波成分中只有N個(gè)是獨(dú)立的，這是與連續(xù)付氏級(jí)數(shù)的不同之處，因?yàn)橐虼?/p>

將周期序列展成離散付里葉級(jí)數(shù)時(shí)，只要取k=0到(N-1)這N個(gè)獨(dú)立的諧波分量，N以上的部分都可合并到這N個(gè)獨(dú)立的諧波分量中，所以一個(gè)周期序列的離散付里葉級(jí)數(shù)只需包含這N個(gè)復(fù)指數(shù)。

周期序列的離散付里葉級(jí)數(shù)(DFS)變換對(duì)：說明。習(xí)慣上：記，稱為旋轉(zhuǎn)因子，則DFS變換對(duì)可寫為DFS[·]——離散付里葉級(jí)數(shù)變換IDFS[·]——離散付里葉級(jí)數(shù)反變換

DFS變換對(duì)公式表明，一個(gè)周期序列雖然是無窮長序列，但是只要知道它一個(gè)周期的內(nèi)容（一個(gè)周期內(nèi)信號(hào)的變化情況），其它的內(nèi)容也就都知道了，所以這種無窮長序列實(shí)際上只有N個(gè)序列值的信息是有用的，因此周期序列與有限長序列有著本質(zhì)的聯(lián)系。DFS的主要特性。假設(shè)都是周期為N的兩個(gè)周期序列，各自的離散付里葉級(jí)數(shù)為：a,b為任意常數(shù)

1）線性

2）序列移位移位序列——證明因?yàn)榧岸际且訬為周期的函數(shù)，所以有

由于與對(duì)稱的特點(diǎn)，同樣的方法可證明

3）周期卷積

若，則，或。證明：

這是一個(gè)卷積公式，但與前面討論的線性卷積的差別在于，這里的卷積過程只限于一個(gè)周期內(nèi)（即m=0~N-1），所以稱為周期期卷積。

由于DFS與IDFS的對(duì)稱性，對(duì)周期序列乘積，存在著頻域的周期卷積公式：若則

3-2離散付里葉變換（DFT）

從上節(jié)的討論，我們知道周期序列實(shí)際上只有有限個(gè)序列值有意義，因此它的許多特性可沿用到有限長序列上。離散付里葉變換周期序列的主值區(qū)間和主值序列。定義一個(gè)有限長序列x(n)，長為N，（只有n=0～N-1個(gè)點(diǎn)上有非零值，其余為零.）

為了利用周期序列的特性，假定周期序列，是由有限長序列x(n)以周期為N延拓而成的，它們的關(guān)系為：對(duì)于周期序列，定義其第一個(gè)周期n=0～N-1為的“主值區(qū)間”，主值區(qū)間上的序列為主值序列x(n)。x(n)與的關(guān)系可描述為：數(shù)學(xué)表示式為：其中RN（n）為矩形序列，符號(hào)（（n））N是余數(shù)運(yùn)算表達(dá)式，表示n對(duì)N求余數(shù)。

例：是周期為N=8的序列，求n=11和n=-2對(duì)N的余數(shù)因此的主值區(qū)間和主值序列：

周期序列的離散付氏級(jí)數(shù)也是一個(gè)周期序列，因而也可給它定義一個(gè)主值區(qū)間0≤k≤N-1和主值序列X(k)。有限長序列離散付里葉變換。考慮到周期序列的離散付里葉級(jí)數(shù)變換（DFS）和反變換（IDFS）公式中，求和都只限于主值區(qū)間（求和0～N-1），它們完全適用于主值序列x(n)與X(k)，因而我們可得到一個(gè)新的定義——有限長序列離散付里葉變換定義。

長度為N的有限長序列x(n)，其離散付里葉變換X(k)仍是一個(gè)長度為N的頻域有限長序列，它們的關(guān)系為

x(n)與X(k)是一個(gè)有限長序列離散付里葉變換對(duì)，已知x(n)能唯一地確定X(k)，同樣已知X(k)也能唯一地確定x(n)，實(shí)際上x(n)與X(k)都是長度為N的序列（復(fù)序列）都有N個(gè)獨(dú)立值，因而具有等量的信息。

例：是一個(gè)N=12的有限長序列，由DFT得。DFT特性

DFT的一些主要特性都與周期序列的DFS有關(guān)。

假定x(n)與y(n)是長度為N的有限長序列，其各自的離散付里葉變換分別為X(k)=DFT[x(n)]，Y(k)=DFT[y(n)](1)線性性

DFT[ax(n)+by(n)]=aX(k)+bY(k),a,b為任意常數(shù)(2)圓周移位

有限長序列x(n)的圓周移位定義為：f(n)=x((n+m))NRN(n)

圖的說明：x((n+m))N表示x(n)的周期延拓序列的移位：x((n+m))N=

x((n+m))NRN(n)表示對(duì)移位的周期序列取主值序列。所以f(n)仍然是一個(gè)長度為N的有限長序列。f（n）實(shí)際上可看作序列x（n）排列在一個(gè)N等分圓周上，并向左旋轉(zhuǎn)m位。

序列圓周移位后的DFT為：F(k)=DFT[f(n)]=WN-mkX(k)

證：利用周期序列的移位特性：利用

實(shí)際上，利用WN-mk的周期性，將f(n)=x((n+m))NRN(n)代入DFT定義式，同樣很容易證明。

同樣，對(duì)于頻域有限長序列X(k)的圓周移位，有如下反變換特性IDFT[X((k+l))NRN(k)]=WnlNx(n)

(3)圓周卷積

若F（k）=X（k）Y（k）

則

或

證：這個(gè)卷積可看作是周期序列卷積后再取其主值序列。將F（k）周期延拓，得

則根據(jù)DFS的周期卷積公式：

因0≤m≤N-1時(shí)，x((m))N=x(m)，因此經(jīng)過簡單的換元可證明這一卷積過程與周期卷積是一樣的，只是在這里只取結(jié)果的主值序列。由于卷積過程只在主值區(qū)間0≤m≤N-1內(nèi)進(jìn)行，所以，y((n-m))N實(shí)際上就是y（m）的圓周移位，上面的卷積稱為“圓周卷積”，習(xí)慣上常用符號(hào)""表示圓周卷積，以區(qū)別于線性卷積。

同樣，若f(n)=x(n)y(n)則所以，離散時(shí)間序列（或離散傅立葉變換）的圓周卷積與離散傅立葉變換（或離散時(shí)間序列）的乘積相對(duì)應(yīng)。這就說明圓周卷積的運(yùn)算可利用離散傅立葉變換轉(zhuǎn)換成乘積實(shí)現(xiàn)。（傅立葉變換的應(yīng)用）

(4)有限長序列的線性卷積與圓周卷積（圓周卷積的應(yīng)用）

有限長序列的線性卷積等于圓周卷積，而不產(chǎn)生混淆的必要條件是延拓周期L≥N+M-1,其中N、M為兩個(gè)有限長序列的長度。

問題的產(chǎn)生：

實(shí)際應(yīng)用中，大多數(shù)是求解線性卷積，如信號(hào)x（n）通過系統(tǒng)h（n），其輸出就是線性卷積y（n）=x（n）*h（n）。而圓周卷積比起線性卷積，在運(yùn)算速度上有很大的優(yōu)越性，它可以采用離散傅立葉變換的乘積實(shí)現(xiàn)，而快速付里葉變換（FFT）技術(shù)又大大提高了離散傅立葉變換的計(jì)算速度，所以若能利用圓周卷積求線性卷積，會(huì)帶來很大的方便。

問題：如果x（n）和h（n）為有限長序列，在什么條件下，x（n）與h（n）的線性卷積能用圓周卷積代替而不產(chǎn)生失真？

分析：

假定x（n）為有限長序列，長度為N

y（n）為有限長序列，長度為M它們的線性卷積f（n）=x（n）*y（n）也應(yīng)是有限長序列，

對(duì)于x（m），其非零區(qū)間為0≤m≤N-1，對(duì)于y(n-m)其非零區(qū)間為0≤n-m≤M-1。這兩個(gè)不等式相加，得：0≤n≤N+M-2，在這區(qū)間以外不是x（m）=0，就是y（n-m）=0，因而f（n）=0。因此f（n）是一個(gè)長度為N+M-1的有限長序列。

再看圓周卷積，重新構(gòu)造兩個(gè)序列x（n）、y（n），均為長度為L≧max{N,M}的有限長序列，在這兩個(gè)L長序列中，x（n）只有前N個(gè)是非零值，后L-N個(gè)為補(bǔ)充的零值，同樣，y（n）只有前M個(gè)是非零值，后L-M個(gè)為補(bǔ)充的零值。為了分析x（n）與y（n）的圓周卷積，先看x（n），y（n）的周期延拓：它們的周期卷積為其中f（n）就是線性卷積，也就是說，x（n）、y（n）周期延拓后的周期卷積是x（n）、y（n）線性卷積的周期延拓，周期為L。

根據(jù)前面的分析，f（n）具有N+M-1個(gè)非零序列值，因此，如果周期卷積的周期L<N+M-1，那么f（n）周期延拓后，必然有一部分非零序列值要重疊，出現(xiàn)混淆現(xiàn)象，只有L≥N+M-1時(shí)，才不會(huì)產(chǎn)生交疊，這時(shí)f（n）的周期延拓中每一個(gè)周期L內(nèi)，前N+M-1個(gè)序列值是f（n）的全部非零序列值，而剩下的L-（N+M-1）點(diǎn)上的序列則是補(bǔ)充的零值。而圓周卷積正是周期卷積取主值序列：

所以使圓周卷積等于線性卷積而不產(chǎn)生混淆的必要條件是L≥N+M-1。

(5)共軛對(duì)稱性

設(shè)x*(n)為x(n)的共軛復(fù)數(shù)序列，則DFT[x*(n)]=X*(N-k)證明：DFT[x*(n)]0≤k≤N-1

由于

因此DFT[x*(n)]]

值得說明的是，當(dāng)k=0時(shí)，應(yīng)為X*(N-0)=X*(0)，因?yàn)榘炊xX（k）只有N個(gè)值，即0≤k≤N-1，而X(N)已超出主值之間，但一般習(xí)慣于認(rèn)為X（k）是分布在N等分的圓周上，它的末點(diǎn)就是它的起始點(diǎn)，即X(N)=x(0)，因此仍采用習(xí)慣表示式DFT[x*（n）]=X*(N-k)。

今后在所有對(duì)稱特性討論中，凡遇到X(N)均應(yīng)理解為X(N)=x(0)。

DFT形式下的Paseval定理

可利用圓周卷積和共軛對(duì)稱特性證明之。

顯然，當(dāng)y（n）=x（n）時(shí)，即為有限長序列的能量

復(fù)序列的實(shí)部與虛部的DFT變換：以xr(n)和xi(n)表示序列x(n)的實(shí)部與虛部，則

顯然，證明因x(n)=xr(n)+jxi(n)，所以以Xe（k）和X0（K）表示實(shí)部與虛部序列的DFT，則Xe(k)與Xo(k)對(duì)稱特性：

因

故,因此Xe(k)具有共軛偶對(duì)稱特性，稱Xe(k)為X(k)的共軛偶對(duì)稱分量。

同樣的方法可得到X0(k)=-X*0(N-k),即Xo(k)具有共軛奇對(duì)稱特性，稱Xo(k)為X(k)的共軛奇對(duì)稱分量。

對(duì)于純實(shí)數(shù)序列x（n），即x（n）=xr（n），X（k）只有共軛偶對(duì)稱部分，即X（k）=Xe（k），所以，實(shí)數(shù)序列的DFT滿足共軛對(duì)稱性，利用這一特性，只要知道一半數(shù)目的X（k），就可得到另一半的X（k），這一特點(diǎn)在DFT運(yùn)算中可以加以利用，以提高運(yùn)算效率。

X（k）的實(shí)部、虛部與x（n）的共軛偶部與共軛奇部的關(guān)系：根據(jù)x（n）與X（k）的對(duì)稱性，同樣可找到X（k）的實(shí)部、虛部與x（n）的共軛偶部與共軛奇部的關(guān)系。

分別以xe（n）及x0（n）表示序列x（n）的圓周共軛偶部與圓周共軛奇部：

同樣應(yīng)從圓周意義上理解x（N-0）=x（0）。可以證明:DFT[xe（n）]=Re[X（k）]

DFT[x0（n）]=jIm[X（k）](6)選頻性

對(duì)復(fù)指數(shù)函數(shù)進(jìn)行采樣得復(fù)序列x(n)0≤n≤N-1其中q為整數(shù)。當(dāng)ω0=2π/N時(shí)，,其離散付里葉變換為

可見，當(dāng)輸入信號(hào)的頻率為qω0時(shí)，X(K)的N個(gè)值中只有X（q）=N，其余皆為零，如果輸入信號(hào)為若干個(gè)不同頻率的信號(hào)的組合，經(jīng)離散付里葉變換后，不同的k上，X（k）將有一一對(duì)應(yīng)的輸出，因此，離散付里葉變換實(shí)質(zhì)上對(duì)頻率具有選擇性。（7）DFT與Z變換

有限長序列可以進(jìn)行z變換。

比較z變換與DFT變換，可見，當(dāng)z=w-kN時(shí)，,即

，是z平面單位圓上幅角為的點(diǎn)，即將z平面上的單位圓N等分后的第k點(diǎn)，所以X(k)也就是z變換在單位圓上等距離的采樣值，如圖2.4所示。同樣，X（k）也可看作是序列付氏變換X（ejω）的采樣，采樣間隔為ωN=2π/N,小結(jié)：第一章討論的采樣定律，采樣定律告訴我們，一個(gè)頻帶有限的信號(hào)，可以對(duì)它進(jìn)行時(shí)域采樣而不丟失任何信息，現(xiàn)在DFT變換進(jìn)一步告訴我們，對(duì)于時(shí)間有限的信號(hào)（有限長序列），也可以對(duì)其進(jìn)行頻域采樣，而不丟失任何信息，這正反應(yīng)了傅立葉變換中時(shí)域、頻域的對(duì)稱關(guān)系。但是它卻有十分重要的意義，我們看到，由于時(shí)域上的采樣，使我們能夠采用數(shù)字技術(shù)來處理這些時(shí)域上的信號(hào)（序列），而DFT理論使得不僅在時(shí)域，在頻域也可采用數(shù)字處理技術(shù)。第四章快速傅里葉變換（FFT）按時(shí)間抽選（DIT）的基-2FFT算法線性卷積與線性相關(guān)的FFT算法學(xué)習(xí)要求：掌握FFT的基本思想和運(yùn)算規(guī)律；能熟練運(yùn)用FFT進(jìn)行信號(hào)頻譜分析。快速付里葉變換（FFT）是計(jì)算DFT的一種快速有效方法。

從前面的討論中看到，有限長序列在數(shù)字技術(shù)中占有很重要的地位。有限長序列的一個(gè)重要特點(diǎn)是其頻域也可以離散化，即離散付里葉變換（DFT）。

數(shù)字信號(hào)處理中DFT運(yùn)算的用途：在FIR濾波器設(shè)計(jì)中，經(jīng)常要由h（n）求H（k），或從H(k)求h(n)；因?yàn)樾盘?hào)序列的DFT本身就是信號(hào)頻譜的采樣集，所以DFT可直接用于分析信號(hào)的頻譜。頻譜分析在數(shù)字信號(hào)處理中用途廣泛：如通過語言信號(hào)的頻譜分析實(shí)現(xiàn)語音通訊的頻帶壓縮、聲納信號(hào)的頻譜分析用以區(qū)分水面與水下目標(biāo)、在各種測(cè)量儀器中，頻譜分析用得更多，這些都需要DFT運(yùn)算。雖然頻譜分析和DFT運(yùn)算很重要，但在很長一段時(shí)間里，由于DFT運(yùn)算復(fù)雜，并沒有得到真正的運(yùn)用，而頻譜分析仍大多采用模擬信號(hào)濾波的方法解決，直到1965年首次提出DFT運(yùn)算的一種快速算法以后，情況才發(fā)生了根本變化，人們開始認(rèn)識(shí)到DFT運(yùn)算的一些內(nèi)在規(guī)律，從而很快地發(fā)展和完善了一套高速有效的運(yùn)算方法——快速付里變換（FFT）算法，F(xiàn)FT的出現(xiàn)，使DFT的運(yùn)算大大簡化，運(yùn)算時(shí)間縮短一～二個(gè)數(shù)量級(jí)，使DFT的運(yùn)算在實(shí)際中得到廣泛應(yīng)用。4-1按時(shí)間抽選（DIT）的基-2FFT算法DFT運(yùn)算的特點(diǎn)

首先分析對(duì)限長序列x（n）進(jìn)行一次DFT運(yùn)算所需的運(yùn)算量。一般，x(n)和wnkN都是復(fù)數(shù)，因此，每計(jì)算一個(gè)X（k）值，要進(jìn)行N次復(fù)數(shù)相乘，和N-1次復(fù)數(shù)相加，X（k）一共有N個(gè)點(diǎn)，故完成全部DFT運(yùn)算，需要N2次復(fù)數(shù)相乘和N（N-1）次復(fù)數(shù)相加，在這些運(yùn)算中，乘法比加法復(fù)雜，需要的運(yùn)算時(shí)間多，尤其是復(fù)數(shù)相乘，每個(gè)復(fù)數(shù)相乘包括4個(gè)實(shí)數(shù)相乘和2個(gè)實(shí)數(shù)相加，每個(gè)復(fù)數(shù)相加包括2個(gè)實(shí)數(shù)相加，例如所以，每計(jì)算一個(gè)X（k）要進(jìn)行4N次實(shí)數(shù)相乘和2N+2(N-1)=2(2N-1)次實(shí)數(shù)相加，因此，整個(gè)DFT運(yùn)算需要4N2實(shí)數(shù)相乘和2N（2N-1）次實(shí)數(shù)相加。

從上面的分析看到，在DFT計(jì)算中，不論是乘法和加法，運(yùn)算量均與N2成正比，因此，N較大時(shí)，運(yùn)算工作是十分可觀，例，計(jì)算N=10點(diǎn)的DFT，需要100次復(fù)數(shù)相乘，而N=`1024點(diǎn)時(shí)，需要1048576（一百多萬）次復(fù)數(shù)乘法，如果信號(hào)要求實(shí)時(shí)處理，則要求有很快的計(jì)算速度才能完成上述計(jì)算量。反變換IDFT與DFT的運(yùn)算結(jié)構(gòu)相同，只是多乘一個(gè)常數(shù)1/N，所以二者的計(jì)算量相同。FFT算法的基本思想：

仔細(xì)考察DFT與IDFT的運(yùn)算發(fā)現(xiàn)，利用以下兩個(gè)特性可減少運(yùn)算量：

1）系數(shù)是一個(gè)周期函數(shù)，它的周期性和對(duì)稱性可利用來改進(jìn)運(yùn)算，提高計(jì)算效率。

例，又如因此

利用這些周期性和對(duì)稱性，DFT運(yùn)算中有些項(xiàng)可合并；

2）利用WNnk的周期性和對(duì)稱性，把長度為N點(diǎn)的大點(diǎn)數(shù)的DFT運(yùn)算分解為若干個(gè)小點(diǎn)數(shù)的DFT。因?yàn)镈FT的計(jì)算量正比于N2，N小，計(jì)算量也就小。

FFT算法正是基于這樣的基本思想發(fā)展起來的。它有多種形式，但基本上可分為兩類，時(shí)間抽取法和頻率抽取法。按時(shí)間抽取的FFT（N點(diǎn)DFT運(yùn)算的分解）

先從一個(gè)特殊情況開始，假定N是2的整數(shù)次方，N=2M，M：正整數(shù)

將N點(diǎn)的DFT分解為兩個(gè)N/2點(diǎn)的DFT：

首先將序列x（n）分解為兩組，一組為偶數(shù)項(xiàng)，一組為奇數(shù)項(xiàng)

r=0,1，…，N/2-1將DFT運(yùn)算也相應(yīng)分為兩組：

(1)其中X1（k）和X2（k）分別是x1（r）和x2（r）的N/2點(diǎn)DFT。推導(dǎo)因?yàn)楣势渲蠿1（k）和X2（k）分別是x1（r）和x2（r）的N/2點(diǎn)DFT：

可見，一個(gè)N點(diǎn)的DFT可以分解為兩個(gè)N/2點(diǎn)的DFT，這兩個(gè)N/2點(diǎn)的DFT再按照上面（1）式合成為一個(gè)N點(diǎn)DFT，注意到，X1（k），X2（k）有N/2個(gè)點(diǎn)，即k=0，1，…，N/2-1，由（1）式得到X（k）只有N/2點(diǎn)，而實(shí)際上X（k）有N個(gè)點(diǎn)，即k=0，1，…，N-1，要用X1（k），X2（k）表示全部X（K）值，還必須應(yīng)用系數(shù)w的周期性和對(duì)稱性。X(k)的(N/2)～N-1點(diǎn)表示：

由X(k)=X1（k）+wkNX2（k）,k=0,1,2,…,N/2-1（2a）

得：，因?yàn)?

且

同樣。

考慮到WNk對(duì)稱性：。

故（2b）

（2a）式表示了X（k）前半部分k=0～N/2-1時(shí)的組成方式，（2b）式則表示了后半部分k=N/2～N-1時(shí)的組成方式。這兩式所表示的運(yùn)算過程可用一個(gè)稱作蝶形的信號(hào)流圖來表示。蝶形信號(hào)流圖：

如圖1（a）所示，圖中左面兩支為輸入，中間以一個(gè)小圓圈表示加、減運(yùn)算，右上支為相加輸出，右下支為相減輸出，如果在某一支路上信號(hào)需要進(jìn)行乘法運(yùn)算，則在該支路上標(biāo)以箭頭，并將相乘的系數(shù)標(biāo)在簡頭邊，這樣（2a），（2b）所表示的運(yùn)算，可用圖1（b）所表示的“蝶形結(jié)”來表示。采用這種表示法，可將以上以討論的分解過程用計(jì)算流圖來表示。圖2.6所示為N=23=8的例子。通過這樣分解以后，每一個(gè)N/2點(diǎn)DFT只需要(N/2)2=N2/4次復(fù)數(shù)乘法運(yùn)算，兩個(gè)N/2點(diǎn)的DFT需要2(N/2)2=N2/2次復(fù)乘，再加上將兩個(gè)N/2點(diǎn)DFT合成為N點(diǎn)DFT時(shí)，在蝶形結(jié)前的N/2次復(fù)乘，共需要(N/2)2+N/2≈N2/2次復(fù)乘，由此可見，經(jīng)過這樣的分解處理，運(yùn)算量差不多節(jié)省了一倍。將N/2點(diǎn)的DFT分解為兩個(gè)N/4點(diǎn)的DFT：

既然這樣分解是有效的，由于N=2M，N/2仍然是偶數(shù)，因此可對(duì)兩個(gè)N/2點(diǎn)的DFT再分別作進(jìn)一步分解，例如對(duì)x1（r）和x2（r）可以再按其偶數(shù)部分及奇數(shù)部分分解為兩個(gè)N/4點(diǎn)的DFT，

l=0,1,…，N/4-1而同樣X2(k)也可這樣分解，并且將系數(shù)統(tǒng)一為，這樣一個(gè)8點(diǎn)DFT就可分解為四個(gè)2點(diǎn)的DFT，如圖2.7所示。2點(diǎn)DFT的表示：

最后剩下的是2點(diǎn)DFT，它可以用一個(gè)蝶形結(jié)表示，例如，x（0），x（4）所組成的2點(diǎn)DFT就可表示式：這樣，一個(gè)8點(diǎn)的完整的按時(shí)間抽取運(yùn)算的流圖如圖2.8所示。

由于這種方法每一步分解都是按輸入時(shí)間序列是屬于偶數(shù)還是奇數(shù)來抽取的，所以稱為“按時(shí)間抽取法”或“時(shí)間抽取法”。時(shí)間抽取法FFT的運(yùn)算特點(diǎn)：（1）蝶形運(yùn)算對(duì)于任何一個(gè)2的整數(shù)冪N=2M，總是可以通過M次分解最后完全成為2點(diǎn)的DFT運(yùn)算。這樣的M次分解，就構(gòu)成從x(n)到X(k)的M級(jí)運(yùn)算過程。從上面的流圖可看到，每一級(jí)運(yùn)算都由N/2個(gè)蝶形運(yùn)算構(gòu)成。因此每一級(jí)運(yùn)算都需要（1/2）次復(fù)乘和N次復(fù)加(每個(gè)結(jié)作加、減各一次)，這樣，經(jīng)過時(shí)間抽取后M級(jí)運(yùn)算總共需要的運(yùn)算：復(fù)乘復(fù)加N·M=Nlog2N當(dāng)然，實(shí)際運(yùn)算量與這個(gè)數(shù)字稍有出入，因?yàn)閃這幾個(gè)系數(shù)實(shí)際上都不用乘法運(yùn)算，因此在上面N=8的例子中，實(shí)際上只有兩個(gè)系數(shù)WN1及WN3是需要乘法運(yùn)算的。

用時(shí)間抽取法所需的計(jì)算量，不論是復(fù)乘還是復(fù)加都與Nlog2N成正比，而直接運(yùn)算時(shí)則與N2成正比。例N=2048，N2=4194304，(N/2)log2N=11264，N2/[(N/2)log2N]=392.4倍。FFT顯然要比直接法快得多。（2）原位計(jì)算

當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后，每一級(jí)運(yùn)算的結(jié)果仍然儲(chǔ)存在同一組存儲(chǔ)器中，直到最后輸出，中間無需其它存儲(chǔ)器，這叫原位計(jì)算。

例如，N=8的FFT運(yùn)算，輸入x(0)，x(4)，x(2)，x(6)…，x(7)可分別存入A(1)，A(2)，…，A(8)這8個(gè)存儲(chǔ)單元中，在第一級(jí)運(yùn)算中，首先是存儲(chǔ)單元A(1)，A(2)中x(0)，x(4)進(jìn)入蝶形運(yùn)算，x(0)，x(4)輸入運(yùn)算器后，其數(shù)值不再需要保存，因此蝶形運(yùn)算的結(jié)果可仍然送回存儲(chǔ)單元A(1)，A(2)中保存，然后A(3)，A(4)中x(2)，x(6)再進(jìn)入蝶形運(yùn)算，其結(jié)果再送回A(3)，A(4)，一直到算完A(7)，A(8)，則完成了第一級(jí)運(yùn)算過程。第二級(jí)運(yùn)算仍可采用這種原位的方式，但是進(jìn)入蝶形結(jié)的組合關(guān)系不同，首先進(jìn)入蝶形結(jié)的是A(1)、A(3)存儲(chǔ)單元中的數(shù)據(jù)，運(yùn)算結(jié)果仍可送回A(1)、A(3)保存，然后進(jìn)入蝶形結(jié)的是A(2)、A(4)…，依此類推，每一級(jí)運(yùn)算均可在原位進(jìn)行，這種原位運(yùn)算結(jié)構(gòu)可節(jié)省存儲(chǔ)單元，降低設(shè)備成本，還可節(jié)省找地址的時(shí)間。（3）序數(shù)重排對(duì)按時(shí)間抽取FFT的原位運(yùn)算結(jié)構(gòu)，當(dāng)運(yùn)算完畢時(shí)，這種結(jié)構(gòu)存儲(chǔ)單元A(1)、A(2)，…，A(8)中正好順序存放著X(0)，X(1)，X(2)，…，X(7)，因此可直接按順序輸出，但這種原位運(yùn)算的輸入x(n)卻不能按這種自然順序存入存儲(chǔ)單元中，而是按X(0)，X(4)，X(2)，X(6)，…，X(7)的順序存入存儲(chǔ)單元，這種順序看起來相當(dāng)雜亂，然而它也是有規(guī)律的。當(dāng)用二進(jìn)制表示這個(gè)順序時(shí)，它正好是“碼位倒置”的順序。例如，原來的自然順序應(yīng)是x(1)的地方，現(xiàn)在放著x(4)，用二進(jìn)制碼表示這一規(guī)律時(shí)，則是在x(001)處放著x(100)，x(011)處放著x(110)。即將自然順序的二進(jìn)制碼位倒置過來，第一位碼變成最末位碼，這樣倒置以后的順序正是輸入所需要的順序。下表列出N=8時(shí)按碼位倒置規(guī)律所得的順序，其結(jié)果與按時(shí)間抽取FFT流圖中的輸入順序是一致的。表碼位倒置順序自然順序二進(jìn)碼表示碼位倒置碼位倒置順序0000000010011004201001023011110641000011510110156110010371111117

在實(shí)際運(yùn)算中，一般直接將輸入數(shù)據(jù)x（n）按碼位倒置的順序排好輸入很不方便，總是先按自然順序輸入存儲(chǔ)單元，然后再通過變址運(yùn)算將自然順序的存儲(chǔ)轉(zhuǎn)換成碼位倒置順序的存儲(chǔ)，然后進(jìn)行FFT的原位計(jì)算。目前有許多通用DSP芯片支持這種碼位倒置的尋址功能。（4）蝶形類型隨迭代次數(shù)成倍增加觀察8點(diǎn)FFT的三次迭代運(yùn)算第一級(jí)迭代，只有一種類型的蝶形運(yùn)算系數(shù)W08第二級(jí)迭代，有二種類型的蝶形運(yùn)算系數(shù)W08、W28，參加運(yùn)算的兩個(gè)數(shù)據(jù)點(diǎn)間隔為2。第三級(jí)迭代，有四類蝶形運(yùn)算系數(shù)W08、W18、W28、W38，參加運(yùn)算的兩個(gè)數(shù)據(jù)點(diǎn)間隔為4。

所以，每次迭代的蝶形類型比上一次蝶代增加一倍，數(shù)據(jù)點(diǎn)間隔也增大一倍。4-2FFT應(yīng)用用FFT估計(jì)信號(hào)的頻譜

在離散付里葉變換一節(jié)，我們講到，離散付里葉變換X(k)可看成是z變換在單位圓上的等距離采樣值同樣，X（k）也可看作是序列付氏變換X（ejω）的采樣，采樣間隔為ωN=2π/N由此看出，離散付里葉變換實(shí)質(zhì)上是其頻譜的離散頻域采樣，對(duì)頻率具有選擇性（ωk=2πk/N），在這些點(diǎn)上反映了信號(hào)的頻譜。

我們知道，采樣定律說明一個(gè)頻帶有限的信號(hào)，可以對(duì)它進(jìn)行時(shí)域采樣而不丟失任何信息，DFT變換則說明對(duì)于時(shí)間有限的信號(hào)（有限長序列），也可以對(duì)其進(jìn)行頻域采樣，而不丟失任何信息。所以只要時(shí)間序列足夠長，采樣足夠密，頻域采樣也就可較好地反映信號(hào)的頻譜趨勢(shì)，所以FFT可以用以進(jìn)行連續(xù)信號(hào)的頻譜分析。

當(dāng)然，這里作了幾次近似處理：

1）用離散采樣信號(hào)的傅立葉變換來代替連續(xù)信號(hào)的頻譜，只有在嚴(yán)格滿足采樣定理的前提下，頻譜才不會(huì)有畸變，否則只是近似；

2）用有限長序列來代替無限長離散采樣信號(hào)。實(shí)數(shù)序列的FFT

以上討論的FFT算法都是復(fù)數(shù)運(yùn)算,包括序列x(n)也認(rèn)為是復(fù)數(shù),但大多數(shù)場(chǎng)合,信號(hào)是實(shí)數(shù)序列,任何實(shí)數(shù)都可看成虛部為零的復(fù)數(shù),例如,求某實(shí)信號(hào)y(n)的復(fù)譜,可認(rèn)為是將實(shí)信號(hào)加上數(shù)值為零的虛部變成復(fù)信號(hào)(x(n)+j0),再用FFT求其離散付里葉變換。這種作法很不經(jīng)濟(jì),因?yàn)榘褜?shí)序列變成復(fù)序列,存儲(chǔ)器要增加一倍,且計(jì)算機(jī)運(yùn)行時(shí),即使虛部為零,也要進(jìn)行涉及虛部的運(yùn)算,浪費(fèi)了運(yùn)算量。合理的解決方法是利用復(fù)數(shù)據(jù)FFT對(duì)實(shí)數(shù)據(jù)進(jìn)行有效計(jì)算,下面介紹兩種方法。（1）一個(gè)N點(diǎn)FFT同時(shí)計(jì)算兩個(gè)N點(diǎn)實(shí)序列的DFT

設(shè)x1(n),x2(n)是彼此獨(dú)立的兩個(gè)N點(diǎn)實(shí)序列,且X1(k)=DFT[x1(n)]，X2(k)=DFT[x2(n)]

可通過一次FFT運(yùn)算同時(shí)獲得X1(k),X2(k)。算法如下：

首先將x1(n),x2(n)分別當(dāng)作一復(fù)序列的實(shí)部及虛部,令x(n)=x1(n)+jx2(n)通過FFT運(yùn)算可獲得x(n)的DFT值X(k)=DFT[x1(n)]+jDFT[x2(n)]=X1(k)+jX2(k)利用離散付里葉變換的共軛對(duì)稱性有了x(n)的FFT運(yùn)算結(jié)果X(k),由上式即可得到X1(k),X2(k)的值。

(2)用一個(gè)N點(diǎn)的FFT運(yùn)算獲得一個(gè)2N點(diǎn)實(shí)序列的DFT設(shè)x(n)是2N點(diǎn)的實(shí)序列,現(xiàn)人為地將x(n)分為偶數(shù)組x1(n)和奇數(shù)組x2(n)

x1(n)=x(2n)n=0,1,…,N-1

x2(n)=x(2n+1)n=0,1,…,N-1然后將x1(n)及x2(n)組成一個(gè)復(fù)序列y(n)=x1(n)+jx2(k)通過N點(diǎn)FFT運(yùn)算可得到Y(jié)(k)=X1(k)+jX2(k)

根據(jù)前面的討論，得到為求2N點(diǎn)x（n）所對(duì)應(yīng)的X（k），需求出X（k）與X1（k），X2（k）的關(guān)系而

所以X(k)=X1(k)+W2NkX2(k)。

這樣，由x1(n)及x2(n)組成復(fù)序列，經(jīng)FFT運(yùn)算求得Y(k)后，再利用共軛對(duì)稱性求出X1(k),X2(k)，最后利用上式求出X(k),從而達(dá)到了用一個(gè)N點(diǎn)的FFT計(jì)算一個(gè)2N點(diǎn)實(shí)序列DFT的目的。用FFT計(jì)算相關(guān)函數(shù)相關(guān)概念很重要，互相關(guān)運(yùn)算廣泛應(yīng)用于信號(hào)分析與統(tǒng)計(jì)分析，如通過相關(guān)函數(shù)峰值的檢測(cè)測(cè)量