離散時間傅立葉變換

在數學中，離散時間傅立葉變換（DTFT，Discrete-time Fourier Transform）是傅立葉分析的一種形式，適用於連續函數的均勻間隔採樣。離散時間是指對採樣間隔通常以時間為單位的離散數據（樣本）的變換。僅根據這些樣本，它就可以產生原始連續函數的連續傅立葉變換的周期求和的以頻率為變量的函數。在採樣定理所描述的一定理論條件下，可以由DTFT完全恢復出原來的連續函數，因此也能從原來的離散樣本恢復。DTFT本身是頻率的連續函數，但可以通過離散傅立葉變換（DFT）很容易計算得到它的離散樣本（參見對DTFT採樣），而DFT是迄今為止現代傅立葉分析最常用的方法。

這兩種變換都是可逆的。離散時間傅立葉逆變換得到的是原始採樣數據序列。離散傅立葉逆變換是原始序列的周期求和。快速傅立葉變換（FFT）是用於計算DFT的一個周期的演算法，而它的逆變換會產生一個周期的離散傅立葉逆變換。

## 定義

一組離散的實數或複數：xn（n 為所有整數）的離散時間傅立葉變換是產生以頻率為變量的周期函數的一個傅立葉級數。當頻率變量 ω 的單位是歸一化的弧度/樣本時，周期為 2π，而傅立葉級數為：

$$X_{2\pi}(\omega) = \sum_{n=-\infty}^{\infty} x[n] \,e^{-i \omega n}.$$

此頻率域函數的性質源於泊松求和公式。令 X(f) 為任意函數 x(t) 的傅立葉變換，採樣間隔為 T（秒），等價於序列 xn（或與之成正比），即 $T\cdot x(nT)=x[n]$。則以傅立葉級數表示的周期函數是 X(f) 的周期求和。要用以赫茲（周期/秒）為單位的頻率 $\textstyle f$ 的話就會是：

$$X_{1/T}(f) = X_{2\pi}(2\pi f T)\ \stackrel{\mathrm{def}}{=} \sum_{n=-\infty}^{\infty} \underbrace{T\cdot x(nT)}_{x[n]}\ e^{-i 2\pi f T n}\; \stackrel{\mathrm{Poisson\;f.}}{=} \; <pre> \sum_{k=-\infty}^{\infty} X\left(f - k/T\right). </pre>$$

整數 k 的單位為轉/樣本，採樣頻率是 1/T，fs（樣本/秒）。因而 X1/T(f) 含有移位 fs 倍數赫茲了的 X(f) 的精確副本，並加和在一起。對於足夠大的 fs，可以在區間 −fs/2, fs/2 有很少或沒有失真（混疊）地觀察到 k=0 項。在圖1中，該左上角分布的末端在左下圖中被周期求和的混疊遮蓋住了。

我們還注意到 $e^{-i 2\pi f T n}$ 是 $\textstyle \delta(t-nT)$ 的傅立葉變換。因此，DTFT的另一個定義為：

$$X_{1/T}(f) = \mathcal{F}\left \{\sum_{n=-\infty}^{\infty} x[n] \cdot \delta(t-nT)\right \}$$

調製的狄拉克梳狀函數（或衝擊串、衝擊序列）是一個數學抽象，有時被稱為脈衝採樣。

## 頻譜的周期性與混疊

### 頻譜周期性

$F_{DTFT}(e^{i \omega T})$具有周期性：

顯然有:$F_{DTFT}(e^{i \omega T}) \,\!= F_{DTFT}(e^{i (\omega T + 2\pi)})$

### 頻譜混疊

根據DTFT的定義，有

$$F_{DTFT}(e^{i \omega T}) = \int_{-\infty}^{\infty} \sum_{n=-\infty}^{\infty} f(t)\delta(t-nT) e^{-i\omega t} dt = \frac{1}{2\pi}\sum_{n=-\infty}^{\infty} F(\omega - n \Omega) \ , \mbox{where } F(\omega)=\mathfrak{F}\{f(t)\} \ , \Omega=\frac{2\pi}{T}$$

即，f(nT)的DTFT是f(t)的傅立葉變換以Ω為周期的延拓，這也從另一個角度證明了DTFT的周期性。很顯然，如果f(t)的頻譜帶不限於Nyquist間隔（-Ω/2, Ω/2），f(nT)的DTFT必然發生混疊（aliasing）,如右圖所示。混疊使得信號的低頻部分被高頻部分「污染」，造成信號的失真。為避免這種情況，通常在進行進一步的數位訊號處理之前要對採樣序列進行抗混疊濾波（anti-aliasing filtering），這一處理通常是由低通濾波器除去高頻分量實現的。

## DTFT與DFT

DFT（離散傅立葉變換）是對離散周期信號的一種傅立葉變換，對於有限長信號，則相當於對其周期延拓進行變換。在頻域上，DFT的離散譜是對DTFT連續譜的等間隔採樣。

$$F_{DFT}(\omega_k) = \left. F_{DTFT}(e^{i \omega T}) \, \right|_{\omega = 2 \pi \frac{k}{N}} = \left. \sum_{n=0}^{N-1} f(nT) \,e^{-i \omega nT} \, \right|_{\omega = 2 \pi \frac{k}{N}} = \sum_{n=0}^{N-1} f(nT) \,e^{-i 2 \pi \frac{k n T}{N}}$$

### DTFT與DFT頻率解析度

N 點序列f(n)（n=0, ... ,N-1）的DFT離散譜對應於對f(nT) 連續譜（即DTFT）的N點採樣，因此DFT的頻率解析度$\Delta \omega = 2\pi/N$。為了提高頻率解析度，可以考慮增加在DTFT頻域上的採樣點數，對偶在時域就是增加對時域信號 f(n) 的採樣數。對於有限長信號f(n)，在時刻0 至N-1以外的值實際上是已知的——都為0。因此，只要在序列f(n) 前後補零就增加了在時域的採樣，假設在f(n)前後補上M-N（其中M>N）個零，則補零之後序列的DFT的頻率解析度就相應提高到$\Delta \omega = 2\pi/M$。相關證明如下：

假設在f(n)之後補上M-N個0，則其DFT為

$$\sum_{n=0}^{M-1} f(n) \,e^{-i 2 \pi \frac{k n}{M}} \mbox{, where } k \in \{0, 1, \ldots, M - 1\}$$

由於n=N,...,M-1時f(n)=0，所以有

$$\sum_{n=0}^{N-1} f(n) \,e^{-i 2 \pi \frac{k n}{M}} + \sum_{n=N}^{M-1} f(n) \,e^{-i 2 \pi \frac{k n}{M}} = \sum_{n=0}^{N-1} f(n) \,e^{-i 2 \pi \frac{k n}{M}}$$

通過上式可以清楚的看到，f(n)補零之後的DFT增加了在f(nT)連續頻域譜上的採樣。採樣點數從N增加到M，從而提高了DFT頻譜的解析度。另一方面，補零之後在頻域採樣的位置發生了變化，因此可以觀察到其他的頻點。

如圖2所示，對信號$f(t) = 0.5 \cos (2 \pi f_1 t) + \cos (2 \pi f_2 t)$（其中$f_1=300 Hz$，$f_2 = 250Hz$）按照$f_s = 1000 Hz$採樣。$f_1$與$f_2$對應的數字角頻率分別為$\omega_1 = 0.6\pi$，$\omega_{2} = 0.5\pi$。上圖為取10個採樣點作DFT，可在0.6π處看到對應的頻率分量，然而由於採樣點少，看不到0.5π處的分量。下圖為補2個零之後的DFT離散譜，可以見到離散譜的解析度提高到了π/6，而且能夠觀察到10點DFT無法看到的0.5π頻率分量。另外，虛線為DTFT連續譜，可見，DFT確實是在頻域對DTFT的採樣。

但是我們可以看到，即使是10點DTFT的連續譜也不能分辨$f_1$與$f_2$（只有一個峰）。這是因為10點DTFT的解析度為fs/10 = 100 Hz，大於f1 - f2 = 50 Hz。所以，只有採樣的點數超過20（即解析度小於50Hz），才能分辨出$f_1$與$f_2$這兩個頻率分量（如圖3所示）。而前面提到的對有限長信號補零作DFT以提高頻譜解析度的說法，也只是針對在DTFT連續譜上採樣而言，只有增加採樣點數和提高採樣頻率才能真正提高離散譜的解析度。

### 以DFT近似DTFT

前面提到，在時間序列前後補零之後作DFT可以增加在DTFT上的採樣點數。可以想見，如果補上無窮多個零，則可以得到無窮多個DTFT連續譜上的採樣點，從而以DFT逼近DTFT。即，使得離散譜的解析度足夠小，即為連續譜。

這種想法顯然是錯誤的，首先應該注意到，DFT的周期型，雖然進行DFT的序列x(k)是有限長序列，但是DFT隱含對x(k)的周期延拓，x(k)是信號序列，周期延拓後還是原來的信號，如果對x(k)進行補零後，1.補零後序列長度不是原信號序列長度的整數倍，那麼補零後的序列就不再是原信號的序列，已經破壞了原信號的資訊。2.補零後序列長度是原信號序列的整數倍，原信號資訊沒有被破壞，仍能通過DFT後獲得原信號資訊，但是補零後序列的DFT雖然頻率步長小了，可以觀察的頻譜資訊更豐富了，但是這些額外的頻譜並不是原信號的頻譜，而是窗函數的頻譜資訊，也就是包絡線是窗函數的形狀。所以補零並沒有給出關於原信號頻譜的更多資訊。補零並不能使補零後的DFT結果的包絡線和原信號頻譜的包絡線一致。

## DTFT與Z變換

離散時間傅立葉變換可以被看作Z變換的特例。Z變換被定義為：

$$F(z) = \sum_{n=-\infty}^{\infty} f(n) \,z^{-n}$$

如果在z平面的單位圓（$z = e^{i \omega}$）上對信號$f(n)$做Z變換：

$$\left. F(z) \right|_{z = e^{i \omega}} = \sum_{n=-\infty}^{\infty} f(n) \,e^{-in\omega} = F(e^{i \omega})$$

此即為$f(n)$的離散時間傅立葉變換。因此通常用$F(e^{i \omega})$，而不是$F(\omega)$表示DTFT。

## 參考文獻

- Alan V. Oppenheim and Ronald W. Schafer : Discrete-Time Signal Processing, Prentice Hall Signal Processing Series, ISBN 978-0-13-754920-7
- Boaz Porat : A Course in Digital Signal Processing, pp. 27-29, pp. 104-105, John Wiley and Sons, ISBN 978-0-471-14961-3
- Sophocles J. Orfanidis : Introduction to Signal Processing, Prentice Hall International, Inc., ISBN 7-32-03059-6