離散傅里葉變換

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

（1）物理意義

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

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的物理意義.

1.線性性質

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

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

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

2.循環移位特性

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

Y(N)=X((N+M))下標nR（N）

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

DFT的一個重要特點就是隱含的周期性，從表面上看，離散傅里葉變換在時域和頻域都是非周期的，有限長的序列，但實質上DFT是從DFS引申出來的，它們的本質是一致的，因此DTS的周期性決定DFT具有隱含的周期性。可以從以下三個不同的角度去理解這種隱含的周期性

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

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

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

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

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

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

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

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

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

（a）對xn(t)以T為間隔進行採樣，即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,則頻域產生以fs為周期的周期延拓，如果頻域是帶限信號，則有可能不產生頻譜混疊，成為連續周期頻譜序列，頻譜的周期為fs=1/T

（c）為了數值計算，頻域上也要抽樣，即在頻域的一個周期中取N個樣點，fs=NF0,每個樣點間隔為F0，頻域抽樣使頻域的積分式變成求和式，而在時域就得到原來已經截斷的離散時間序列的周期延拓，時間周期為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

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

（1）時域和頻域混疊

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

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

N=T0/T=fs/F0

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

N>2fc/F0

（2）截斷效應

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

Y(n)=x(n).R(n)

根據頻率卷積定理

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

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

（3）頻譜泄露

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

（4）譜間干擾

因截斷使主譜線兩邊形成許多旁瓣，引起不同分量間的干擾，成為譜間干擾，這不僅影響頻譜解析度，嚴重時強信號的旁瓣可能湮滅弱信號的主譜線。

截斷效應是無法完全消除的，只能根據要求折中選擇有關參量。

（5）柵欄效應

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

減小柵欄效應，可以在時域數據末端增加一些零值點，是一個周期內的點數增加

（6）信號長度的選擇

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

int DFT(int dir,int m,double *x1,double *y1)

{

long i,k;

double arg;

double cosarg,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

{

x2[i]=0;

y2[i]=0;

arg=-dir*2.0*3.141592654*(double)i/(double)m;

for(k=0;k

{

cosarg=cos(k*arg);

sinarg=sin(k*arg);

x2[i]+=(x1[k]*cosarg-y1[k]*sinarg);

y2[i]+=(x1[k]*sinarg+y1[k]*cosarg);

}

}

if(dir==1)

{

for(i=0;i

{

x1[i]=x2[i]/(double)m;

y1[i]=y2[i]/(double)m;

}

}

else

{

for(i=0;i

{

x1[i]=x2[i];

y1[i]=y2[i];

}

}

free(x2);

free(y2);

return(TRUE);

}

對換實例

---

變換對

對於N點序列 {x[n ]} 0 ≤ n < N ，它的離散傅里葉變換（DFT）為

其中e 是自然對數的底數，i 是虛數單位。通常以符號F表示這一變換，即

離散傅里葉變換的逆變換（IDFT）為：

可以記為：

實際上，DFT和IDFT變換式中和式前面乘上的歸一化係數並不重要。在上面的定義中，DFT和IDFT前的係數分別為1 和1/N。有時會將這兩個係數都改成

，這樣就有，即DFT成為酉變換。

幾何觀點

由於周期為N的離散信號構成N維歐幾里得空間，定義其上任意兩向量x,y內積為：

那麼我們有對於 上的一組正交基：

將向量x在此基上進行分解，可以得到：

令，此即為離散傅里葉變換。又，我們有：

此即為離散傅里葉變換的逆變換。

事實上由內積的性質我們有：

特別的令x=y，我們有：

圓周卷積

對於任意N維向量，我們定義 為 中各項向前循環移 位。那麼對於N維任意向量 我們定義其圓周卷積為如下向量：

我們容易知道，即圓周卷積可交換。同樣圓周卷積可結合即，證明如下：

易知： ，所以此數列第 項為：

同理可證，的第 項為：

顯然：

因此，我們有。事實上，對於任意N維向量x，我們有：

因此：

由圓周卷積的結合性我們有：

即有：

因此離散傅里葉變換可將圓周卷積變為乘積運算。

從連續到離散

連續時間信號x(t) 以及它的連續傅里葉變換（CT）?

x

( ω)

都是連續的。由於數字系統只能處理有限長的、離散的信號，因此必須將x 和?

x

都離散化，並且建立對應於連續傅里葉變換的映射。

數字系統只能處理有限長的信號，為此假設x(t)時限於[0, L]，再通過時域採樣將x(t)離散化，就可以得到有限長的離散信號。設採樣周期為T，則時域採樣點數N=L/T。

x discrete (t) = x (t) N - 1

Σ

n = 0 δ(t-nT) = N - 1

Σ

n = 0 x (nT) δ(t-nT)

它的傅里葉變換為

?

x

discrete ( ω) = N - 1

Σ

n = 0 x (nT)F δ(t-nT) = 1

––

T N - 1

Σ

n = 0 x (nT)e - i 2 π n ω T

這就是x(t)時域採樣的連續傅里葉變換，也就是離散時間傅里葉變換，它在頻域依然是連續的。

類似的，頻域信號也應當在帶限、離散化之後才能由數字系統處理。依據採樣定理，時域採樣若要能完全重建原信號，頻域信號?

x

( ω)

應當帶限於(0,1/T)。由於時域信號時限於[0, L]，由採樣定理以及時頻對偶的關係，頻域的採樣間隔應為1/L。故，頻域採樣點數為

1/T

–––––

1/L = N

即頻域採樣的點數和時域採樣同為N，頻域採樣點為 { ω k = k/NT} 0 ≤ k < N 在DTFT頻域上採樣：

?

x

[k ] = ?

x

discrete ( ω k ) = 1

––

T N - 1

Σ

n = 0 f[n ]e - i 2 π

– – – – –

N n k

令T=1，將其歸一化，就得到前面定義的離散傅里葉變換。因此，DFT就是先將信號在時域離散化，求其連續傅里葉變換后，再在頻域離散化的結果。

DFT與CT

下面考察離散傅里葉變換與連續傅里葉變換的關係。

Fx ( ω) = ?

x

( ω) = 1

––

L ∫ L

0 x (t)e - i ω t dt

其採樣為

?

x

( ω k ) = 1

––

L ∫ L

0 x (t)e - i ω k t dt

將這個積分以黎曼和的形式近似，有

?

x

( ω k ) ≈ 1

––

L N - 1

Σ

n = 0 x[n ] e - i ω k n T T = 1

––

N ?

x

[k ]

DFT與DTFT

參見離散時間傅里葉變換

離散時間傅里葉變換（DTFT）是在時域上對連續傅里葉變換的採樣。DFT則是在頻域上對DTFT的均勻採樣。離散信號x[n ]（n=0,...,N-1）的DTFT為：

?

x

(e i ω ) = N - 1

Σ

n = 0 x[n ] e - i n ω

對?

x

(e i ω )

在離散的頻點{ ω k = k 2 π

–––––

N } 0 ≤ k < N

上採樣

?

x

[k ] = ?

x

(e i ω k ) = N - 1

Σ

n = 0 x[n ]e - i 2 π

– – – – –

N k n k = 0, …,N-1

即為x 的DFT。由於DTFT在頻域是周期的，所以在DTFT頻域上的均勻採樣也應是周期的。?

x

[k ]

實際上是這個周期序列的主值序列。

柵欄效應

N 點序列的DFT只能在有限的N個頻點上觀察頻譜，這相當於從柵欄的縫隙中觀察景色，對於了解信號在整個頻域上的特性是不夠的。為了觀察到其他頻率的信息，需要對原信號x[n]做一些處理，以便在不同的頻點上採樣。

將原來在DTFT頻域上的採樣點數增加到M 點，這樣採樣點位置變為{ ω ' k = e i k 2 π

– – – – –

M } 0 ≤ k < M

。則對應的DFT成為

?

x

'[k ] = ?

x

(e ik ω ' k ) = N - 1

Σ

n = 0 x[n ]e - i 2 π

– – – – –

M k n

若在序列x[n] 之後補上M-N個零，設為x'[n]，則上式變為

?

x

'[k ] = M - 1

Σ

n = 0 x '[n ]e - i 2 π

– – – – –

M k n = Fx '

因此將x[n]補零再做DFT就可以得到x[n]的DTFT在其他頻率上的值，相當於移動了柵欄，因而能夠從其他位置進行觀察。

頻譜解析度

N 點DFT的頻譜解析度是2 π/N。一節指出可以通過補零觀察到更多的頻點，但是這並不意味著補零能夠提高真正的頻譜解析度。這是因為x[n] 實際上是x(t) 採樣的主值序列，而將x[n]補零得到的x'[n]周期延拓之後與原來的序列並不相同，也不是x(t) 的採樣。因此?

x

'

與?

x

是不同離散信號的頻譜。對於補零至M點的x'的DFT，只能說它的解析度2 π/M僅具有計算上的意義，?

x

'

並不是真正的、物理意義上的頻譜。頻譜解析度的提高只能通過提高採樣頻率實現。

基本性質

---

1.線性性質

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

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

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

2.循環移位特性

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

Y(N)=X((N+M))下標nR（N）

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

計算機代碼

---

基本信息

中文名

離散傅里葉變換

外文名

discreteFourier transform

應用學科

通信

特點

傅里葉、離散

時域信號

離散時間傅里葉變換