離散傅里葉變換計算機(jī)代碼

1.C語言實現(xiàn)代碼

intDFT(intdir,intm,double*x1,double*y1)
{
longi,k;
doublearg;
doublecosarg,sinarg;
double*x2=NULL,*y2=NULL;
x2=malloc(m*sizeof(double));
y2=malloc(m*sizeof(double));
if(x2==NULL||y2==NULL)return(FALSE);
for(i=0;i
 

（1）時域和頻域混疊

根據(jù)采樣定理，只有當(dāng)采樣頻率大于信號最高頻率的兩倍時，才能避免頻域混疊。實際信號的持續(xù)時間是有限的，因而從理論上來說，其頻譜寬度是無限的，無論多 大的采樣頻率也不能滿足采樣定理。但是超過一定范圍的高頻分量對信號已沒有多大的影響，因而在工程上總是對信號先進(jìn)行低通濾波

另一方面，DFT得到的頻率函數(shù)也是離散的，其頻域抽樣間隔為F0，即頻率分辨力。為了對全部信號進(jìn)行采樣，必須是抽樣點數(shù)N滿足條件

N=T0/T=fs/F0

從以上兩個公式來看，信號最高頻率分量fc和頻率分辨力F0有矛盾。若要fc增加，則抽樣間隔T就要減小，而FS就要增加，若在抽樣點數(shù)N不變的情況下，必然是F0增加，分辨力下降。唯一有效的方法是增加記錄長度內(nèi)的點數(shù)N，在fc和F0給定的條件下，N必須滿足

N>2fc/F0

（2）截斷效應(yīng)

在實際中遇到的序列x(n)，其長度往往是有限長，甚至是無限長，用DFT對其進(jìn)行譜分析時，必須將其截斷為長度為N的有限長序列

Y(n)=x(n).R_N(n)

根據(jù)頻率卷積定理

Y(e)=1/2Πx(e)*H(e)

|ω|<2π/N叫做主瓣，其余部分叫做旁瓣

（3）頻譜泄露

原序列x(n)的頻譜是離散譜線，經(jīng)截斷后使每根譜線都帶上一個辛格譜，就好像使譜線向兩邊延申，通常將這種是遇上的截斷導(dǎo)致頻譜展寬成為泄露，泄露使得頻譜變得模糊，分辨率降低

（4）譜間干擾

因截斷使主譜線兩邊形成許多旁瓣，引起不同分量間的干擾，成為譜間干擾，這不僅影響頻譜分辨率，嚴(yán)重時強(qiáng)信號的旁瓣可能湮滅弱信號的主譜線。

截斷效應(yīng)是無法完全消除的，只能根據(jù)要求折中選擇有關(guān)參量。

（5）柵欄效應(yīng)

N點DFT是在頻率區(qū)間[0,2π]上對信號的頻譜進(jìn)行N點等間隔采樣，得到的是若干個離散點X(k)，且它們之限制為基頻F0的整數(shù)倍，這部好像在柵欄的一邊通過縫隙看另一邊的景象，只能在離散點的地方看到真實的景象，其余部分頻譜成分被遮攔，所以稱為柵欄效應(yīng)。

減小柵欄效應(yīng)，可以在時域數(shù)據(jù)末端增加一些零值點，是一個周期內(nèi)的點數(shù)增加

（6）信號長度的選擇

在時域內(nèi)對信號長度的選擇會影響DFT運(yùn)算的正確性。實際的信號往往是隨機(jī)的，沒有確定的周期，因此在實際中，應(yīng)經(jīng)可能估計出幾個典型的、帶有一定周期性的信號區(qū)域進(jìn)行頻譜分析，然后在取其平均值，從而得到合理的結(jié)果。

判斷系統(tǒng)是否為最小相位系統(tǒng)的簡單方法是：如果兩個系統(tǒng)的傳遞函數(shù)分子和分母的最高次數(shù)都分別是m，n，則頻率ω趨于無窮時，兩個系統(tǒng)的對數(shù)幅頻曲線斜率均為－20（n－m）dB/dec但對數(shù)相頻曲線卻不同：最小相位系統(tǒng)趨于－90°（n－m），而非最小相位系統(tǒng)卻不這樣。

在工程實際中經(jīng)常遇到的模擬信號xn(t),其頻譜函數(shù)Xn(jΩ)也是連續(xù)函數(shù)，為了利用DFT對xn(t)進(jìn)行譜分析，對xn(t)進(jìn)行時域采樣得到x(n)= xn(nT),再對x(n)進(jìn)行DFT，得到X(k)則是x(n)的傅里葉變換X(ejω)在頻率區(qū)間[0,2π]上的N點等間隔采樣，這里x(n)和X(k)都是有限長序列

然而，傅里葉變換理論證明，時間有限長的信號其頻譜是無限寬的，反之，弱信號的頻譜有限寬的則其持續(xù)時間將為無限長，因此，按采樣定理采樣時，采樣序列應(yīng)為無限長，這不滿足DFT的條件。實際中，對于頻譜很寬的信號，為防止時域采樣后產(chǎn)生‘頻譜混疊’，一般用前置濾波器濾除幅度較小的高頻成分，使信號的帶寬小于折疊頻率；同樣對于持續(xù)時間很長的信號，采樣點數(shù)太多也會導(dǎo)致存儲和計算困難，一般也是截取有限點進(jìn)行計算。上述可以看出，用DFT對模擬信號進(jìn)行譜分析，只能是近似的，其近似程度取決于信號帶寬、采樣頻率和截取長度

模擬信號xn(t)的傅里葉變換對為

X(jΩ)={-∞, ∞}x(t)*exp^-jΩt dt

x（t）=1/2π{-∞, ∞} X(JΩ)*e^jΩt dΩ

用DFT方法計算這對變換對的方法如下：

（a）對xn(t)以T為間隔進(jìn)行采樣，即xn(t)|t=nT= xa(nT)= x(n),由于

t→nT,dt→T, {-∞, ∞}→∑n={-∞, ∞}

因此得到

X(jΩ)≈∑n={-∞, ∞}x(nT)*exp^-jΩnT*T

x（nT）≈1/2π{0, Ωs} X(JΩ)*e^jΩnT Dω

（b）將序列x(n)= xn(t)截斷成包含有N個抽樣點的有限長序列

X(jΩ)≈T∑n={0,N-1}x(nT)*exp^-jΩnT*T

由于時域抽樣，抽樣頻率為fs=1/T,則頻域產(chǎn)生以fs為周期的周期延拓，如果頻域是帶限信號，則有可能不產(chǎn)生頻譜混疊，成為連續(xù)周期頻譜序列，頻譜的周期為fs=1/T

（c）為了數(shù)值計算，頻域上也要抽樣，即在頻域的一個周期中取N個樣點，fs=NF0,每個樣點間隔為F0，頻域抽樣使頻域的積分式變成求和式，而在時域就得到原來已經(jīng)截斷的離散時間序列的周期延拓，時間周期為T0=1/F0。因此有

Ω→kΩ0，dΩ→Ω0，{-∞, ∞} dΩ→∑n={-∞, ∞}Ω0

T0=1/F0=N/fs=NT

Ω0=2ΠF0

Ω0T=Ω0/fs=2π/N

X(jkΩ0)≈T∑n={0,N-1}x(nT)*exp^-jkΩ0nT

DFT的一個重要特點就是隱含的周期性,從表面上看,離散傅里葉變換在時域和頻域都是非周期的,有限長的序列,但實質(zhì)上DFT是從DFS引申出來的,它們的本質(zhì)是一致的,因此DTS的周期性決定DFT具有隱含的周期性?？梢詮囊韵氯齻€不同的角度去理解這種隱含的周期性

(1)從序列DFT與序列FT之間的關(guān)系考慮X(k)是對頻譜X(ejω)在[0,2π]上的N點等間隔采樣，當(dāng)不限定k的取值范圍在[0,N-1]時，那么k的取值就在[0,2π]以外，從而形成了對頻譜X(ejω)的等間隔采樣。由于X(ejω)是周期的，這種采樣就必然形成一個周期序列

(2)從DFT與DFS之間的關(guān)系考慮。X(k)= ∑n={0,N-1}x(n) WNexp^nk，當(dāng)不限定N時，具有周期性

(3)從WN來考慮，當(dāng)不限定N時，具有周期性

1.線性性質(zhì)

如果X1（n）和X2(N)是兩個有限長序列，長度分別為N1和N2，且Y(N)=AX1(N) BX2(N)

式中A,B為常數(shù)，取N=max[N1,N2]，則Y(N）的N點DFT為

Y(K)=DFT[Y(N)]=AX1(K) BX2(K), 0≤K≤N-1;

2.循環(huán)移位特性

設(shè)X(N)為有限長序列，長度為N，則X(N)地循環(huán)移位定義為

Y(N)=X((N M))下標(biāo)nR（N）

式中表明將X(N）以N為周期進(jìn)行周期拓延得到新序列X'(N)=X((N))下標(biāo)n，再將X'(N）左移M位，最后取主值序列得到循環(huán)移位序列Y(N)

（1）物理意義

設(shè)x(n)是長度為N的有限長序列，則其傅里葉變換，Z變換與離散傅里葉變換分別用以下三個關(guān)系式表示

X(e^jω)= ∑n={0,N-1}x(n) e^j-ωn

X(z)= ∑n={0,N-1}x(n)z^-n

X(k)= ∑n={0,N-1}x(n) e^-j2πkn/N

單位圓上的Z變換就是序列的傅里葉變換

離散傅里葉變換是x(n)的頻譜X(ejω)在[0,2π]上的N點等間隔采樣,也就是對序列頻譜的離散化,這就是DFT的物理意義.

離散傅里葉變換（DFT），是傅里葉變換在時域和頻域上都呈現(xiàn)離散的形式，將時域信號的采樣變換為在離散時間傅里葉變換（DTFT）頻域的采樣。在形式上，變換兩端（時域和頻域上）的序列是有限長的，而實際上這兩組序列都應(yīng)當(dāng)被認(rèn)為是離散周期信號的主值序列。即使對有限長的離散信號作DFT，也應(yīng)當(dāng)將其看作經(jīng)過周期延拓成為周期信號再作變換。在實際應(yīng)用中通常采用快速傅里葉變換以高效計算DFT。

離散余弦變換(DCT for Discrete Cosine Transform)是與傅里葉變換相關(guān)的一種變換，它類似于離散傅里葉變換(DFT for Discrete Fourier Transform),但是只使用實數(shù)。離散余弦變換相當(dāng)于一個長度大概是它兩倍的離散傅里葉變換，這個離散傅里葉變換是對一個實偶函數(shù)進(jìn)行的（因為一個實偶函數(shù)的傅里葉變換仍然是一個實偶函數(shù)），在有些變形里面需要將輸入或者輸出的位置移動半個單位(DCT有8種標(biāo)準(zhǔn)類型，其中4種是常見的)。

最常用的一種離散余弦變換的類型是下面給出的第二種類型，通常我們所說的離散余弦變換指的就是這種。它的逆，也就是下面給出的第三種類型，通常相應(yīng)的被稱為"反離散余弦變換"，"逆離散余弦變換"或者"IDCT"。

有兩個相關(guān)的變換，一個是離散正弦變換(DST for Discrete Sine Transform),它相當(dāng)于一個長度大概是它兩倍的實奇函數(shù)的離散傅里葉變換；另一個是改進(jìn)的離散余弦變換(MDCT for Modified Discrete Cosine Transform),它相當(dāng)于對交疊的數(shù)據(jù)進(jìn)行離散余弦變換。

離散余弦變換，尤其是它的第二種類型，經(jīng)常被信號處理和圖像處理使用，用于對信號和圖像(包括靜止圖像和運(yùn)動圖像)進(jìn)行有損數(shù)據(jù)壓縮。這是由于離散余弦變換具有很強(qiáng)的"能量集中"特性:大多數(shù)的自然信號(包括聲音和圖像)的能量都集中在離散余弦變換后的低頻部分，而且當(dāng)信號具有接近馬爾科夫過程(Markov processes)的統(tǒng)計特性時，離散余弦變換的去相關(guān)性接近于K-L變換(Karhunen-Loève 變換--它具有最優(yōu)的去相關(guān)性)的性能。

例如，在靜止圖像編碼標(biāo)準(zhǔn)JPEG中，在運(yùn)動圖像編碼標(biāo)準(zhǔn)MJPEG和MPEG的各個標(biāo)準(zhǔn)中都使用了離散余弦變換。在這些標(biāo)準(zhǔn)制中都使用了二維的第二種類型離散余弦變換，并將結(jié)果進(jìn)行量化之后進(jìn)行熵編碼。這時對應(yīng)第二種類型離散余弦變換中的n通常是8，并用該公式對每個8x8塊的每行進(jìn)行變換，然后每列進(jìn)行變換。得到的是一個8x8的變換系數(shù)矩陣。其中(0,0)位置的元素就是直流分量，矩陣中的其他元素根據(jù)其位置表示不同頻率的交流分量。

一個類似的變換, 改進(jìn)的離散余弦變換被用在高級音頻編碼(AAC for Advanced Audio Coding)，Vorbis 和 MP3 音頻壓縮當(dāng)中。

離散余弦變換也經(jīng)常被用來使用譜方法來解偏微分方程，這時候離散余弦變換的不同的變量對應(yīng)著數(shù)組兩端不同的奇/偶邊界條件。

離散系數(shù)是衡量資料中各觀測值離散程度的一個統(tǒng)計量。當(dāng)進(jìn)行兩個或多個資料離散程度的比較時，如果度量單位與平均數(shù)相同，可以直接利用標(biāo)準(zhǔn)差來比較。如果單位和（或）平均數(shù)不同時，比較其離散程度就不能采用標(biāo)準(zhǔn)差，而需采用標(biāo)準(zhǔn)差與平均數(shù)的比值（相對值）來比較 ：

離散系數(shù)通常可以進(jìn)行多個總體的對比，通過離散系數(shù)大小的比較可以說明不同總體平均指標(biāo)（一般來說是平均數(shù)）的代表性或穩(wěn)定性大小。一般來說，離散系數(shù)越小，說明平均指標(biāo)的代表性越好；離散系數(shù)越大，平均指標(biāo)的代表性越差。

離散系數(shù)只對由比率標(biāo)量計算出來的數(shù)值有意義。舉例來說，對于一個氣溫的分布，使用開爾文或攝氏度來計算的話并不會改變標(biāo)準(zhǔn)差的值，但是溫度的平均值會改變，因此使用不同的溫標(biāo)的話得出的變異系數(shù)是不同的。也就是說，使用區(qū)間標(biāo)量得到的變異系數(shù)是沒有意義的。

離散系數(shù)在概率論的許多分支中都有應(yīng)用，比如說在更新理論、排隊理論和可靠性理論中。在這些理論中，指數(shù)分布通常比正態(tài)分布更為常見。

由于指數(shù)分布的標(biāo)準(zhǔn)差等于其平均值，所以它的離散系數(shù)等于一。離散系數(shù)小于一的分布，比如愛爾朗分布稱為低差別的 ，而離散系數(shù)大于一的分布，如超指數(shù)分布則被稱為高差別的。