數(shù)字信號(hào)處理-(35)課件

1、第4章 快速傅里葉變換 4.1 引言 4.2 直接計(jì)算DFT的問題及改進(jìn)的途徑 4.3 按時(shí)間抽選的基2-FFT算法（Cooley-Turkey）4.4 按頻率抽取的基2-FFT算法（Sande-Turkey）4.5 離散傅立葉反變換的快速計(jì)算方法 4.6 線性調(diào)頻z變換算法 4.7 FFT實(shí)例分析 4.1 引 言 注意：快速傅里葉變換（FFT）不是一種新的變換，是DFT的一種快速算法。 1. DFT在時(shí)域和頻域都是的，可以采用計(jì)算機(jī)進(jìn)行運(yùn)算；2. 直接計(jì)算DFT的運(yùn)算量很大，即使采用計(jì)算機(jī)運(yùn)算，也不能解決實(shí)時(shí)性問題，影響其實(shí)際應(yīng)用；3. 1965年首次提出了DFT運(yùn)算的一種快速算法，并發(fā)展和

2、形成了一套高速有效的運(yùn)算方法， 統(tǒng)稱為快速傅里葉變換（FFT）的算法。4.2 直接計(jì)算DFT的問題及改進(jìn)的途徑 4.2.1 DFT的運(yùn)算量k=0, 1, , N-1 （4.1） 反變換（IDFT）為 n=0, 1, , N-1 （4.2） 設(shè)x(n)為N點(diǎn)有限長(zhǎng)序列，其DFT為 二者的差別: 1) WN的指數(shù)符號(hào)不同， 2) 差一個(gè)常數(shù)乘因子1/N，IDFT與DFT具有相同的運(yùn)算量， 可以只討論DFT的運(yùn)算量。 x (n)和WNnk都是復(fù)數(shù)，X(k)也是復(fù)數(shù)，完成整個(gè)DFT運(yùn)算共需要：N2次復(fù)數(shù)乘法 N(N-1)次復(fù)數(shù)加法。 X (k)共有N個(gè)值 （k=0，1，N-1）每計(jì)算一個(gè)X(k)值，需

3、要：N次復(fù)數(shù)乘法 N-1次復(fù)數(shù)加法。（4.3） 一次復(fù)數(shù)乘法：4次實(shí)數(shù)乘法 2次實(shí)數(shù)加法 一次復(fù)數(shù)加法：2次實(shí)數(shù)加法 復(fù)數(shù)運(yùn)算實(shí)際上是由實(shí)數(shù)運(yùn)算來完成的，可將DFT運(yùn)算式寫成 整個(gè)DFT運(yùn)算共需要：4N 2次實(shí)數(shù)乘法 2N (2N-1)次實(shí)數(shù)加法。 一次復(fù)乘：4次實(shí)數(shù)乘法 2次實(shí)數(shù)加法 一次復(fù)加：2次實(shí)數(shù)加法 一個(gè)X(k)值：N次復(fù)數(shù)乘法 N-1次復(fù)數(shù)加法每計(jì)算一個(gè)X(k)需要：4N 次 實(shí)數(shù)乘法 2N+2(N-1)=2(2N-1)次 實(shí)數(shù)加法上述統(tǒng)計(jì)與實(shí)際需要的運(yùn)算次數(shù)稍有出入，某些WNnk可能是1或 j，如W0N=1，WN= -1，WNN/4=-j等 但是為了便于和其他運(yùn)算方法作比較， 一

4、般都不考慮這些特殊情況，而是把WNnk都看成復(fù)數(shù)，當(dāng)N很大時(shí)，這種特例的影響很小。因此，直接計(jì)算DFT，乘法次數(shù)和加法次數(shù)都和N2成正比， 當(dāng)N很大時(shí)，運(yùn)算量是很可觀的。 例 根據(jù)式（4.1），對(duì)一幅NN點(diǎn)的二維圖像進(jìn)行DFT變 換，如用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？解: 直接計(jì)算DFT所需復(fù)乘次數(shù)為（N 2)21012次， 用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，需要近3000小時(shí)。 對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理，改進(jìn)方法： 1）提高計(jì)算速度，（這樣，對(duì)計(jì)算速度要求太高了）； 2) 改進(jìn)DFT的計(jì)算方法，以大大減少運(yùn)算次數(shù)。 4.2.2 減少

5、運(yùn)算量的途徑（2）WNnk的周期性 DFT運(yùn)算，利用系數(shù)Wnk的固有特性，可減少運(yùn)算量： 能否減少運(yùn)算量，從而縮短計(jì)算時(shí)間呢？（1） WNnk的對(duì)稱性 （3） WNnk的可約性 則有 另外 FFT算法基本上可以分成兩大類，按時(shí)間抽選法 (DIT ，Decimation-In-Time）按頻率抽選法 (DIF， Decimation-In-Frequency） 利用這些特性，使DFT運(yùn)算中可以合并有些項(xiàng)；利用WNnk的對(duì)稱性、周期性、可約性，使DFT分解為更少點(diǎn)數(shù)的DFT運(yùn)算。前面提到，DFT的運(yùn)算量與N2 成正比，N 越小DFT的運(yùn)算量越小。快速傅里葉變換算法的基本思想4.3 按時(shí)間抽?。―I

6、T）的基 -2 FFT算法 4.3.1 算法原理設(shè)序列 x (n) 長(zhǎng)度為N，且滿足N=2L，L為正整數(shù)步驟：將 x(n)按 n 先奇后偶分解為兩個(gè)N/2點(diǎn)的子序列 基-2 FFT算法則可將DFT化為 （4.5） （4.4） 利用WNnk的可約性 X1(k) 與 X2(k) 分別是 x1(r) 及 x2(r) 的N/2點(diǎn)DFT： （4.6） （4.7） （4.5） 只是X(k)的前一半的結(jié)果第4章 快速傅里葉變換X1(k)，X2(k)只有N/2個(gè)點(diǎn)，即k=0, 1, , N/2-1。X(k)有N個(gè)點(diǎn)，即k=0, 1, , N-1， 要用X1(k)，X2(k) ，Wk來表達(dá)全部的X(k)值這樣可

7、得到 （4.8） 同理可得 （4.9） 式（3-8）、式（3-9）說明了后半部分k值（N/2kN-1）所對(duì)應(yīng)的X1(k)，2(k)分別等于前半部分k值（0kN/2-1）所對(duì)應(yīng)的X1(k)，X2(k)。 再考慮到WkN 的以下性質(zhì): 這樣，把式（3-8）、式（3-9）、式（3-10）代入式（3-5），就可將X(k)表達(dá)為前后兩部分： （4.10） （4.11） （4.12） 圖 4.1 時(shí)間抽選法蝶形運(yùn)算流圖符號(hào) 圖 4.2 按時(shí)間抽選，將一個(gè)N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT（N=8） N點(diǎn)DFT，一次分解后次復(fù)數(shù)乘法次復(fù)數(shù)加法將N點(diǎn)DFT，進(jìn)行一次分解后，運(yùn)算工作量節(jié)省了近一半N點(diǎn)DFT，不

8、進(jìn)行分解次復(fù)數(shù)加法次復(fù)數(shù)乘法由于N=2L，N/2仍是偶數(shù)可以進(jìn)一步把每個(gè)N/2點(diǎn)子序列分解為兩個(gè)N/4點(diǎn)的子序列（4.13） ， 且 式中 （4.14） （4.15） 圖4.3給出N=8時(shí)，將一個(gè)N/2點(diǎn)DFT分解成兩個(gè)N/4點(diǎn)DFT， 由這兩個(gè)N/4點(diǎn)DFT組合成一個(gè)N/2點(diǎn)DFT的流圖。 圖4.3 由兩個(gè)N/4點(diǎn)DFT組合成一個(gè)N/2點(diǎn)DFT X2(k)也可進(jìn)行同樣的分解： 式中 （4.16） （4.17） 圖4.4 按時(shí)間抽選，將一個(gè)N點(diǎn)DFT分解為四個(gè)N/4點(diǎn)DFT （N=8） 根據(jù)上面同樣的分析知道，利用四個(gè)N/4點(diǎn)的DFT及兩級(jí)蝶形組合運(yùn)算來計(jì)算N點(diǎn)DFT，比只用一次分解蝶形組合方

9、式的計(jì)算量又減少了大約一半。 式中， , 故上式不需要乘法。 類似地, 可求出X4(k)，X5(k)，X6(k)。 這種方法的每一步分解，都是按輸入序列在時(shí)間上的次序是屬于偶數(shù)還是屬于奇數(shù)來分解為兩個(gè)更短的子序列，所以稱為“按時(shí)間抽取法”。 圖 3-5 N=8 按時(shí)間抽取的FFT運(yùn)算流圖4.3.2 按時(shí)間抽取的FFT算法與直接計(jì)算DFT運(yùn)算量的比較 由按時(shí)間抽取法FFT的流圖可見，當(dāng)N=2M時(shí)，共有M級(jí)蝶形， 每級(jí)都由N/2個(gè)蝶形運(yùn)算組成，每個(gè)蝶形需要一次復(fù)乘、 二次復(fù)加，因而每級(jí)運(yùn)算都需N/2次復(fù)乘和N次復(fù)加，這樣M級(jí)運(yùn)算總共需要 復(fù)乘數(shù) 復(fù)加數(shù) 式中，數(shù)學(xué)符號(hào)lb=log2。 實(shí)際計(jì)算量與

10、這個(gè)數(shù)字稍有不同，因?yàn)閃0N=1，NN/2=-1，NN/2=-j，這幾個(gè)系數(shù)都不用乘法運(yùn)算，但是這些情況在直接計(jì)算DFT中也是存在的。此外，當(dāng)N較大時(shí)，這些特例相對(duì)而言就很少。所以，為了統(tǒng)一作比較起見，下面都不考慮這些特例。 由于計(jì)算機(jī)上乘法運(yùn)算所需的時(shí)間比加法運(yùn)算所需的時(shí)間多得多，故以乘法為例，直接DFT復(fù)數(shù)乘法次數(shù)是N2，F(xiàn)FT復(fù)數(shù)乘法次數(shù)是(N/2) lbN。 直接計(jì)算DFT與FFT算法的計(jì)算量之比為 當(dāng)N=2048時(shí)，這一比值為372.4，即直接計(jì)算DFT的運(yùn)算量是FFT運(yùn)算量的372.4倍。當(dāng)點(diǎn)數(shù)N越大時(shí)，F(xiàn)FT的優(yōu)點(diǎn)更為明顯。 （4.20） 例4-2 用FFT算法處理一幅NN點(diǎn)的二

11、維圖像，如用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？ 解 當(dāng)N=1024點(diǎn)時(shí)，F(xiàn)FT算法處理一幅二維圖像所需復(fù)數(shù)乘法約為次，僅為直接計(jì)算DFT所需時(shí)間的10萬分之一。 即原需要3000小時(shí)，現(xiàn)在只需要2 分鐘。 4.3.3 按時(shí)間抽取的FFT算法的特點(diǎn)及DIT-FFT程序框圖 1. 原位運(yùn)算（同址運(yùn)算）這種運(yùn)算是很有規(guī)律，其每級(jí)（每列）計(jì)算都是由N/2 個(gè)蝶形運(yùn)算構(gòu)成的，每一個(gè)蝶形結(jié)構(gòu)完成下述基本迭代運(yùn)算： （4.21a） （4.21b） 式中，m表示第m列迭代，k, j為數(shù)據(jù)所在行數(shù)。式（4.21）的蝶形運(yùn)算如圖4-6所示，由一次復(fù)乘和兩次復(fù)

12、加（減）組成。 圖 4-6 蝶形運(yùn)算單元 當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器后，每一級(jí)運(yùn)算的結(jié)果仍然存儲(chǔ)在這同一組存儲(chǔ)器中，直到最后輸出，中間無需其他的存儲(chǔ)器。每一級(jí)運(yùn)算均可在原位進(jìn)行，這種原位運(yùn)算的結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。2. 倒位序規(guī)律按時(shí)間抽選FFT 輸出X(k) 按自然順序排列在存儲(chǔ)單元 輸入 x(n) 不是按自然順序排列是由于x(n)按標(biāo)號(hào)n先偶后奇不斷分組造成的倒位序的規(guī)律：例如圖4-7 倒位序的形成 表4-1 N=8時(shí)的自然順序二進(jìn)制數(shù)和相應(yīng)的倒位序二進(jìn)制數(shù) 自然順序（I） 二進(jìn)制數(shù) 倒位序二進(jìn)制數(shù) 倒位序（J） 01234567000001010011100101110111000

13、10001011000110101111104261537圖 4-8 N=8 倒位序的變址處理 3. 蝶形運(yùn)算兩節(jié)點(diǎn)的“距離” 以8點(diǎn)FFT為例，其輸入是倒位序的，輸出是自然順序的。 其第一級(jí)（第一列）每個(gè)蝶形的兩節(jié)點(diǎn)間“距離”為1， 第二級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)“距離”為2， 第三級(jí)每個(gè)蝶形的兩節(jié)點(diǎn)“距離”為4。 由此類推得，對(duì)N=2M點(diǎn)FFT，當(dāng)輸入為倒位序， 輸出為正常順序時(shí)，其第m級(jí)運(yùn)算，每個(gè)蝶形的兩節(jié)點(diǎn)“距離”為2m-1。 4. WNr的確定 由于對(duì)第m級(jí)運(yùn)算，一個(gè)DFT蝶形運(yùn)算的兩節(jié)點(diǎn)“距離”為2m-1， 因而（4.22a） （4.22b） 為了完成上兩式運(yùn)算，還必須知道系數(shù)Nr的變換規(guī)

14、律。仔細(xì)觀察圖4-5的流圖可以發(fā)現(xiàn)r的變換規(guī)律是： 把式（4.22）中蝶形運(yùn)算兩節(jié)點(diǎn)中的第一個(gè)節(jié)點(diǎn)標(biāo)號(hào)值， 即k值，表示成M位（注意N=2M）二進(jìn)制數(shù)； 把此二進(jìn)制數(shù)乘上2M-m，即將此M位二進(jìn)制數(shù)左移M-m位（注意m是第m級(jí)運(yùn)算），把右邊空出的位置補(bǔ)零， 此數(shù)即為所求r的二進(jìn)制數(shù)。 圖中，WNr因子最后一列有N/2種，順序?yàn)閃N0， WN1， ， 其余可類推。 5. DIT-FFT程序框圖 圖 4-9 DIT-FFT運(yùn)算程序框圖 圖 4-10 倒序程序框圖 4.4 按頻率抽取（DIF）的基 -2 FFT算法 4.4.1 算法原理 仍設(shè)序列點(diǎn)數(shù)為N=2M，M為正整數(shù)。在把輸出X(k)按k的奇偶

15、分組之前，先把輸入序列按前一半、后一半分開（不是按偶數(shù)、 奇數(shù)分開）， 把N點(diǎn)DFT寫成兩部分。 k=0, 1, , N-1 式中，用的是 ，而不是 ，因而這并不是N/2點(diǎn)DFT。 由于 ，故，可得 k=0, 1, , N-1 （4.23） 當(dāng)k為偶數(shù)時(shí)，(-1)k=1；k為奇數(shù)時(shí)，(-1)k=-1。因此，按k的奇偶可將X(k)分為兩部分: （4.24） （4.25） 式（4.24）為前一半輸入與后一半輸入之和的N/2點(diǎn)DFT， 式（4.25）為前一半輸入與后一半輸入之差再與WNn之積的N/2點(diǎn)DFT。 令:（4.27） 圖 4-12 頻率抽取法蝶形運(yùn)算單元 這樣，我們就把一個(gè)N點(diǎn)DFT按k的

16、奇偶分解為兩個(gè)N/2點(diǎn)的DFT了。 N=8時(shí)，上述分解過程示于圖4-13。 與時(shí)間抽取法的推導(dǎo)過程一樣，由于N=2M，N/2仍是一個(gè)偶數(shù)，因而可以將每個(gè)N/2點(diǎn)DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點(diǎn)DFT進(jìn)一步分解為兩個(gè)N/4 點(diǎn)DFT。 這兩個(gè)N/4點(diǎn)DFT的輸入也是先將N/2點(diǎn)DFT的輸入上下對(duì)半分開后通過蝶形運(yùn)算而形成的，圖4-14示出了這一步分解的過程。 圖4-13 按頻率抽取的第一次分解 圖 4-14 按頻率抽取的第二次分解 這樣的分解可以一直進(jìn)行到第M次（N=2M），第M次實(shí)際上是做兩點(diǎn)DFT，它只有加減運(yùn)算。 然而，為了有統(tǒng)一的運(yùn)算結(jié)構(gòu)，仍然用一個(gè)系數(shù)為WN0的蝶形運(yùn)

17、算來表示， 這N/2個(gè)兩點(diǎn)DFT的N個(gè)輸出就是x(n)的N點(diǎn)DFT的結(jié)果X(k)。 圖4-15表示一個(gè)N=8 完整的按頻率抽取的基-2 FFT運(yùn)算結(jié)構(gòu)。 圖 4-15 按頻率抽取的FFT（N=8）信號(hào)流圖 4.4.2 按頻率抽取法的運(yùn)算特點(diǎn) 按頻率抽取法的運(yùn)算特點(diǎn)與時(shí)間抽取法基本相同。從圖4-15可以看出，它也是通過(N/2)M個(gè)蝶形運(yùn)算完成的。每一個(gè)蝶形結(jié)構(gòu)完成下述基本迭代運(yùn)算： 式中，m表示m列迭代，k,j為整數(shù)所在行數(shù)，此式的蝶形運(yùn)算如圖4-16所示，也需要一次復(fù)乘和兩次復(fù)加。 圖4-16 頻率抽取法蝶形運(yùn)算單元 1按時(shí)間抽選：輸入是倒位序， 輸出是自然順序； 按頻率抽選：輸入是自然順序

18、， 輸出是倒位序。DIT法與DIF法比較：二、相同點(diǎn) 運(yùn)算量相同一、不同點(diǎn)2按時(shí)間抽選：復(fù)數(shù)乘法出現(xiàn)在加、減運(yùn)算之前； 按頻率抽選：復(fù)數(shù)乘法出現(xiàn)在減法運(yùn)算之后。4.5 離散傅里葉反變換的快速計(jì)算方法 1）DFT中的 IDFT中的 2）IDFT 中有常數(shù)區(qū)別：按時(shí)間抽選的 FFT按頻率抽選的 IFFT按頻率抽選的 FFT按時(shí)間抽選的 IFFT稍作改動(dòng)FFT程序，計(jì)算IFFT的方法按時(shí)間抽選的 IFFT 流圖（N =8） 完全不改變FFT程序，計(jì)算IFFT的方法 4.6* 線性調(diào)頻z變換算法 4.6.1 CZT變換算法原理（4.32） 為適應(yīng)z可以沿z平面更一般的路徑取值，故沿z平面上的一段螺線作

19、等分角的采樣，z的這些采樣點(diǎn)zk為 zk=AW-k k=0, 1, , M-1 （4.33） M為所要分析的復(fù)頻率的點(diǎn)數(shù)，即采樣點(diǎn)的總數(shù)，不一定等于N； A和W都是任意復(fù)數(shù)，可表示為: 已知x(n)（0nN-1）是有限長(zhǎng)序列，其z變換為 將式（ 4.34 ）與式（ 4.35 ）代入式（ 4.33 ）， 可得 （4.34）（4.35）（4.36）因此有 圖4.15 (a) CZT在平面的螺旋線抽樣 采樣點(diǎn)在Z平面上所沿的周線如圖4.15(a)所示。由以上討論和圖4.15(a)可以看出： （1）A0表示起始采樣點(diǎn)z0的矢量半徑長(zhǎng)度，通常A01; 否則z0將處于單位圓|z|=1 的外部。 （2）0表

20、示起始采樣點(diǎn)z0的相角，它可以是正值或負(fù)值。 （3）0表示兩相鄰采樣點(diǎn)之間的角度差。0為正時(shí)，表示zk的路徑是逆時(shí)針旋轉(zhuǎn)的；0為負(fù)時(shí)，表示zk的路徑是順時(shí)針旋轉(zhuǎn)的。 （4）W0的大小表示螺線的伸展率。W01 時(shí)，隨著k的增加螺線內(nèi)縮; W0M，則只需要求得0nM-1一段N點(diǎn)序列值即可; h(n)也可事先準(zhǔn)備好，不必實(shí)時(shí)分析時(shí)計(jì)算，因此，可不用考慮其計(jì)算量。 同時(shí)，h(n)的L點(diǎn)FFT即H(r)也可預(yù)先計(jì)算好。 （3）計(jì)算G(r)，H(r), q(n), 需要二次L點(diǎn)FFT（或IFFT），共需要 次復(fù)乘。 （4） 計(jì)算Q(r)=G(r)H(r), 需要L次復(fù)乘。 （5）計(jì)算X(zk)= （0kM

21、-1），需要M次復(fù)乘。 綜上所述，CZT總的復(fù)數(shù)乘法次數(shù)為前面說過，直接計(jì)算式（4.37）的X(zk)需要NM次復(fù)數(shù)乘法。可以看出，當(dāng)N, M都較大時(shí)（例如N, M都大于50時(shí)），CZT的FFT算法比直接算法的運(yùn)算量要小得多。 4.7 FFT實(shí)例分析4.7.1 利用FFT分析時(shí)域連續(xù)信號(hào)頻譜 圖 4.17 時(shí)域連續(xù)信號(hào)離散傅里葉分析的處理步驟 一、 基本步驟 前置低通濾波器LPF（預(yù)濾波器）的引入，是為了消除或減少時(shí)域連續(xù)信號(hào)轉(zhuǎn)換成序列時(shí)可能出現(xiàn)的頻譜混疊的影響。 在實(shí)際工作中，時(shí)域離散信號(hào)x(n)的時(shí)寬是很長(zhǎng)的， 甚至是無限長(zhǎng)的（例如語音或音樂信號(hào)）。由于DFT的需要(實(shí)際應(yīng)用FFT計(jì)算)，

22、必須把x(n)限制在一定的時(shí)間區(qū)間之內(nèi)，即進(jìn)行數(shù)據(jù)截?cái)?。?shù)據(jù)的截?cái)嘞喈?dāng)于加窗處理（窗函數(shù)見6.2節(jié)）。 因此， 在計(jì)算FFT之前，用一個(gè)時(shí)域有限的窗函數(shù)w(n)加到x(n)上是非常必要的。xc(t)通過A/D變換器轉(zhuǎn)換(忽略其幅度量化誤差)成采樣序列x(n)，其頻譜用X(ej)表示，它是頻率的周期函數(shù)，即 (4.54) 式中，Xc(j)或 為xc(t)的頻譜。 在實(shí)際應(yīng)用中，前置低通濾波器的阻帶不可能是無限衰減的， 故由Xc(j)周期延拓得到的X(ej)有非零重疊，即出現(xiàn)頻譜混疊現(xiàn)象。 由于進(jìn)行FFT的需要，必須對(duì)序列x(n)進(jìn)行加窗處理，即v(n)=x(n)w(n)，加窗對(duì)頻域的影響，用卷積

23、表示如下: 最后是進(jìn)行FFT運(yùn)算。 加窗后的DFT是 0kN-1 (4.55) 式中，假設(shè)窗函數(shù)長(zhǎng)度L小于或等于DFT長(zhǎng)度N，為進(jìn)行FFT運(yùn)算，這里選擇N為2的整數(shù)冪次即N=2m。 有限長(zhǎng)序列v(n)=x(n)w(n)的DFT相當(dāng)于v(n)傅里葉變換的等間隔采樣。 V(k)便是sc(t)的離散頻率函數(shù)。因?yàn)镈FT對(duì)應(yīng)的數(shù)字域頻率間隔為=2/N，且模擬頻率和數(shù)字頻率間的關(guān)系為=， 其中=2f。所以，離散的頻率函數(shù)第k點(diǎn)對(duì)應(yīng)的模擬頻率為: (4.57) (4.58) (4.56) 由式（4.58）很明顯可看出，數(shù)字域頻率間隔=2/N對(duì)應(yīng)的模擬域譜線間距為 (4.59) 譜線間距，又稱頻譜分辨率（單

24、位：Hz）。所謂頻譜分辨率是指可分辨兩頻率的最小間距。它的意思是，如設(shè)某頻譜分析的F=5Hz，那么信號(hào)中頻率相差小于5Hz的兩個(gè)頻率分量在此頻譜圖中就分辨不出來。 長(zhǎng)度N=16 的時(shí)間信號(hào)v(n)=(1.1)nR16(n)的圖形如圖 4.18(a)所示, 其16點(diǎn)的DFT V(k)的示例如圖4.18 (b)所示。 其中T為采樣時(shí)間間隔（單位：s）；fs為采樣頻率（單位：Hz）；tp為截取連續(xù)時(shí)間信號(hào)的樣本長(zhǎng)度（又稱記錄長(zhǎng)度，單位：s）；F為譜線間距，又稱頻譜分辨率（單位：Hz）。 注意：V(k)示例圖給出的頻率間距F及N個(gè)頻率點(diǎn)之間的頻率fs為對(duì)應(yīng)的模擬域頻率(單位： Hz)。 圖 4.18

25、時(shí)間信號(hào)v(n)和V(k)的示意圖 由圖可知： (4.60) (4.61) 在實(shí)際應(yīng)用中, 要根據(jù)信號(hào)最高頻率fh和頻譜分辨率F的要求， 來確定T、tp和N的大小。 (4.62) （1）首先，由采樣定理，為保證采樣信號(hào)不失真，fs2fh(fh為信號(hào)頻率的最高頻率分量，也就是前置低通濾波器阻帶的截止頻率)， 即應(yīng)使采樣周期T滿足 （2） 由頻譜分辨率F和T確定N, (4.63) 為了使用FFT運(yùn)算，這里選擇N為2的冪次即N=2m，由式(4.61)可知，N大，分辨率好，但會(huì)增加樣本記錄時(shí)間tp。 （3） 最后由N, T確定最小記錄長(zhǎng)度，tp=NT。 例 4-1 有一頻譜分析用的FFT處理器，其采樣

26、點(diǎn)數(shù)必須是2的整數(shù)冪， 假定沒有采用任何特殊的數(shù)據(jù)處理措施，已給條件為: 頻率分辨率10 Hz;信號(hào)最高頻率4kHz。解 (1) 由分辨率的要求確定最小長(zhǎng)度tp 所以記錄長(zhǎng)度為 試確定以下參量： (1) 最小記錄長(zhǎng)度tp； (2) 最大采樣間隔T（即最小采樣頻率）； (3) 在一個(gè)記錄中的最少點(diǎn)數(shù)N。 (2) 從信號(hào)的最高頻率確定最大可能的采樣間隔T（即最小采樣頻率fs=1/T）。 按采樣定理 即 (3) 最小記錄點(diǎn)數(shù)N應(yīng)滿足 取 如果我們事先不知道信號(hào)的最高頻率，可以根據(jù)信號(hào)的時(shí)域波形圖來估計(jì)它。例如， 某信號(hào)的波形如圖 4.19 所示。 先找出相鄰的波峰與波谷之間的距離，如圖中t1，t2，

27、t3，t4。 然后，選出其中最小的一個(gè)如t4。這里, t4可能就是由信號(hào)的最高頻率分量形成的。 峰與谷之間的距離就是周期的一半。 因此，最高頻率為 知道 fh 后就能確定采樣頻率 圖 4.19 估算信號(hào)最高頻率fh 利用FFT對(duì)連續(xù)信號(hào)進(jìn)行傅里葉分析時(shí)可能造成的誤差如下也就是采樣間隔T滿足 二、 可能出現(xiàn)的誤差 1. 頻譜混疊失真 在圖4.17 的基本步驟中，A/D變換前利用前置低通濾波器進(jìn)行預(yù)濾波，使xc(t)頻譜中最高頻率分量不超過fh。假設(shè)A/D變換器的采樣頻率為fs，按照奈奎斯特采樣定理，為了不產(chǎn)生混疊， 必須滿足 一般應(yīng)取 fs=(2.53.0)fh 如果不滿足fs2fh，就會(huì)產(chǎn)生頻

28、譜混疊失真。 對(duì)于FFT來說，頻率函數(shù)也要采樣，變成離散的序列，其采樣間隔為F(即頻率分辨率)。 由式（4.61）可得 （4.64） （4.65） 從以上和tp兩個(gè)公式來看，信號(hào)的最高頻率分量fh與頻率分辨率F存在矛盾關(guān)系，要想fh增加，則時(shí)域采樣間隔T就一定減小，而fs就增加，由式（4.63）可知，此時(shí)若是固定N，必然要增加F， 即分辨率下降。 反之，要提高分辨率（減小F），就要增加tp，當(dāng)N給定時(shí)， 必然導(dǎo)致T的增加（fs減?。?。 要不產(chǎn)生混疊失真，則必然會(huì)減小高頻容量（信號(hào)的最高頻率分量）fh。 （4.66） 這個(gè)公式是未采用任何特殊數(shù)據(jù)處理（例如加窗處理）的情況下，為實(shí)現(xiàn)基本FFT算法

29、所必須滿足的最低條件。如果加窗處理，相當(dāng)于時(shí)域相乘，則頻域周期卷積，必然加寬頻譜分量， 頻率分辨率就可能變差，為了保證頻率分辨率不變，則須增加數(shù)據(jù)長(zhǎng)度tp。 要想兼顧高頻容量fh與頻率分辨率F，即一個(gè)性能提高而另一個(gè)性能不變（或也得以提高）的惟一辦法就是增加記錄長(zhǎng)度的點(diǎn)數(shù)N， 即要滿足 2. 柵欄效應(yīng) 利用FFT計(jì)算頻譜，只給出離散點(diǎn)k=2k/N或k=2k/(NT)上的頻譜采樣值，而不可能得到連續(xù)頻譜函數(shù)， 這就像通過一個(gè)“柵欄”觀看信號(hào)頻譜， 只能在離散點(diǎn)上看到信號(hào)頻譜， 稱之為“柵欄效應(yīng)” 。這時(shí)，如果在兩個(gè)離散的譜線之間有一個(gè)特別大的頻譜分量，就無法檢測(cè)出來了。 減小柵欄效應(yīng)的一個(gè)方法就

30、是要使頻域采樣更密，即增加頻域采樣點(diǎn)數(shù)N， 在不改變時(shí)域數(shù)據(jù)的情況下，必然是在數(shù)據(jù)末端添加一些零值點(diǎn)，使一個(gè)周期內(nèi)的點(diǎn)數(shù)增加，但并不改變?cè)械挠涗洈?shù)據(jù)。 頻譜采樣為2k/N，N增加，必然使樣點(diǎn)間距更近（單位圓上樣點(diǎn)更多），譜線更密，譜線變密后原來看不到的譜分量就有可能看到了。 必須指出，補(bǔ)零以改變計(jì)算FFT的周期時(shí)，所用窗函數(shù)的寬度不能改變。 換句話說，必須按照數(shù)據(jù)記錄的原來的實(shí)際長(zhǎng)度選擇窗函數(shù)， 而不能按照補(bǔ)了零值點(diǎn)后的長(zhǎng)度來選擇窗函數(shù)。 補(bǔ)零不能提高頻率分辨率，這是因?yàn)閿?shù)據(jù)的實(shí)際長(zhǎng)度仍為補(bǔ)零前的數(shù)據(jù)長(zhǎng)度。 3. 頻譜泄漏與譜間干擾 對(duì)信號(hào)進(jìn)行FFT計(jì)算，首先必須使其變成有限時(shí)寬的信號(hào)， 這

31、就相當(dāng)于信號(hào)在時(shí)域乘一個(gè)窗函數(shù)如矩形窗，窗內(nèi)數(shù)據(jù)并不改變。 時(shí)域相乘即v(n)=x(n)w(n)， 加窗對(duì)頻域的影響，可用卷積公式卷積的結(jié)果，得到的頻譜V(ej)與原來的頻譜X(ej)不同，有失真。這種失真主要會(huì)造成頻譜“擴(kuò)散”（拖尾、 變寬），即“頻譜泄漏”。 頻譜泄漏是由于截取有限長(zhǎng)信號(hào)所造成的。 對(duì)具有單一譜線的正弦波來說，它必須是無限長(zhǎng)的。即，如果輸入信號(hào)是無限長(zhǎng)的，那么FFT就能計(jì)算出完全正確的單一線頻譜。 可是實(shí)際上，只能取有限長(zhǎng)記錄樣本。 如果在該有限長(zhǎng)記錄樣本中，正弦信號(hào)又不是整數(shù)個(gè)周期時(shí)，就會(huì)產(chǎn)生泄漏。 例 周期為N=16的余弦信號(hào) x(n)=cos(6n）（2）截取的長(zhǎng)度為

32、13，則其16點(diǎn)FFT的譜圖見 4.20 下圖。 由圖可見，頻譜不再是單一的譜線，能量散布到整個(gè)頻譜的各處。 這種能量散布到其他譜線位置的現(xiàn)象即為“頻譜泄漏”。 （1）截取一個(gè)周期長(zhǎng)度 x1(n)=cos(6n/16)R16(n), 其16點(diǎn)FFT的譜圖見 4.20上圖，圖 4.20 余弦信號(hào)頻譜泄漏示例圖 泄漏將會(huì)導(dǎo)致頻譜的擴(kuò)展， 從而使最高頻率有可能超過折疊頻率（fs/2），因此，頻譜泄漏也會(huì)造成混疊失真。 泄漏將會(huì)降低頻譜的分辨率。由于在主譜線兩邊形成很多旁瓣，引起不同頻率分量間的干擾(簡(jiǎn)稱譜間干擾)， 特別是強(qiáng)信號(hào)譜的旁瓣可能湮沒弱信號(hào)的主譜線，或者把強(qiáng)信號(hào)譜的旁瓣誤認(rèn)為是另一信號(hào)的譜

33、線，從而造成假信號(hào)，這樣就會(huì)使譜分析產(chǎn)生較大偏差。 在進(jìn)行FFT運(yùn)算時(shí)，要注意的兩點(diǎn)問題：第一，時(shí)域截?cái)嗍潜厝坏?，從而頻譜泄漏和譜間干擾也是不可避免的。為盡量減小泄漏和譜間干擾的影響，需增加窗的時(shí)域?qū)挾?頻域主瓣變窄)，但這又導(dǎo)致運(yùn)算量及存儲(chǔ)量的增加；第二，數(shù)據(jù)不要突然截?cái)?，也就是不要加矩形窗，而是加各種緩變的窗（例如：三角形窗、升余弦窗、改進(jìn)的升余弦窗等），使得窗譜的旁瓣能量更小，卷積后造成的泄漏減小，這個(gè)問題在FIR濾波器設(shè)計(jì)一章中會(huì)討論。 4.7.2 線性卷積和線性相關(guān)的FFT算法 一、線性卷積的FFT算法 以FIR濾波器為例，因?yàn)樗妮敵龅扔谟邢揲L(zhǎng)單位脈沖響應(yīng)h(n)與有限長(zhǎng)輸入信號(hào)x

34、(n)的離散線性卷積。 設(shè)x(n)為L(zhǎng)點(diǎn)，h(n)為M點(diǎn)， 輸出y(n)為 y(n)也是有限長(zhǎng)序列，其點(diǎn)數(shù)為L(zhǎng)+M-1 點(diǎn)。 下面首先討論直接計(jì)算線性卷積的運(yùn)算量。 由于每一個(gè)x(n)的輸入值都必須和全部的h(n)值相乘一次，因而總共需要LM次乘法，這就是直接計(jì)算的乘法次數(shù)，以md表示為 md=LM （4.67） 對(duì)于線性相位FIR濾波器，滿足 （4-68）（4-69）其加權(quán)系數(shù)約減少了一半，因而相乘次數(shù)大約可以減少一半，即 用FFT算法也就是用圓周卷積來代替這一線性卷積時(shí)，為了不產(chǎn)生混疊，其必要條件是使x(n)，h(n)都補(bǔ)零值點(diǎn)，補(bǔ)到至少N=M+L-1， 即: 0nL-1 LnN-1 0n

35、M-1 MnN-1 然后計(jì)算圓周卷積 N用FFT計(jì)算y(n)的步驟如下： 求H(k)=DFTh(n)，N點(diǎn)； 求X(k)=DFTx(n), N點(diǎn)； 求y(n)=IDFTY(k)，N點(diǎn)。 計(jì)算Y(k)=X(k)H(k); 步驟、都可用FFT來完成。 此時(shí)的工作量如下： 三次FFT運(yùn)算共需要 次相乘，還有步驟的N次相乘，因此共需要相乘次數(shù)為 （4.70） 比較直接計(jì)算線性卷積(簡(jiǎn)稱直接法)和FFT法計(jì)算線性卷積(簡(jiǎn)稱FFT法)這兩種方法的乘法次數(shù)。當(dāng)與點(diǎn)數(shù)差不多時(shí)，時(shí)，則 例如，設(shè)式（4.69）與式（4.70）的比值為Km，這樣可得下表： M=L81632641282565121024204840

36、96Km0.5720.9411.62.785.928.821629.2453.999.9當(dāng)x(n)的點(diǎn)數(shù)很多時(shí)，即當(dāng)LM，通常不允許等x(n)全部采集齊后再進(jìn)行卷積; 否則，使輸出相對(duì)于輸入有較長(zhǎng)的延時(shí)。此外，若N=L+M-1 太大，h(n)必須補(bǔ)很多個(gè)零值點(diǎn)，很不經(jīng)濟(jì)，且FFT的計(jì)算時(shí)間也要很長(zhǎng)。這時(shí)FFT法的優(yōu)點(diǎn)就表現(xiàn)不出來了。因此需要采用分段卷積或稱分段過濾的辦法。即將x(n)分成點(diǎn)數(shù)和h(n)相仿的段，分別求出每段的卷積結(jié)果，然后用一定方式把它們合在一起，便得到總的輸出，其中每一段的卷積均采用FFT方法處理。有兩種分段卷積的辦法: 重疊相加法和重疊保留法。 2重疊相加法 設(shè)h(n)的點(diǎn)

37、數(shù)為M，信號(hào)x(n)為很長(zhǎng)的序列。我們將x(n)分解為很多段，每段為L(zhǎng)點(diǎn)，L選擇成和M的數(shù)量級(jí)相同，用xi(n)表示x(n)的第i段： iLn(i+1)L-1 其他n i=0, 1, （4.72） 則輸入序列可表示成 （4.73）這樣，x(n)和h(n)的線性卷積等于各xi(n)與h(n)的線性卷積之和，即 （4.74） 每一個(gè)xi(n)*h(n)都可用上面討論的快速卷積辦法來運(yùn)算。 由于xi(n)*h(n)為L(zhǎng)+M-1 點(diǎn)，故先對(duì)xi(n)及h(n)補(bǔ)零值點(diǎn)，補(bǔ)到N點(diǎn)。 為便于利用基-2 FFT算法，一般取N=2mL+M-1，然后作N點(diǎn)的圓周卷積： N 由于xi(n)為L(zhǎng)點(diǎn)，而yi(n)為（L+M-1）點(diǎn)（設(shè)N=L+M-1）， 故相鄰兩段輸出序列必然有（M-1）個(gè)點(diǎn)發(fā)生重疊，即前一段的后（M-1）個(gè)點(diǎn)和后一段的前（M-1）個(gè)點(diǎn)相重疊，如圖4.21 所示。按照式（4.74），應(yīng)該將重疊部分相加再和不重疊的部分共同組成輸出y(n)。 圖 4.21 重疊相加法圖形 圖 4.21重疊相加法圖形