Chirp-Z 轉換

Chirp-Z轉換(Chirp-Z transform)是一種適合於計算當取樣頻率間隔(sampling frequency interval) 與取樣時間間隔(sampling time interval)乘積的倒數不等於信號的時頻分佈面積時的演算法，其為利用摺積來實現任意大小的離散傅立葉變換 DFT) 的快速傅立葉變換演算法。

演算法

離散信號 $x_n$ 的離散傅立葉變換可以寫成下列的形式

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk } \qquad k = 0,\dots,N-1.$

其中 $e^{-\frac{2\pi i}{N} nk }\qquad$ 這項的 $nk$ 可以利用平方式展開得到，如下式所示

$(n-k)^2 = n^2-2nk+k^2\Rightarrow nk=-\frac{(n-k)^2-n^2-k^2}{2}$

所以

$e^{-\frac{2\pi i}{N} nk}=e^{\frac{2\pi i}{N} \frac{(n-k)^2-n^2-k^2}{2}} = e^{\frac{\pi i}{N}(n-k)^2} e^{-\frac{\pi i}{N}n^2} e^{-\frac{\pi i}{N} k^2}$

而將此平方展開式帶回原式我們可以得到

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk } = e^{-\frac{\pi i}{N} k^2}\sum_{n=0}^{N-1} ( x_n e^{-\frac{\pi i}{N}n^2} )e^{\frac{\pi i}{N}(n-k)^2} \qquad k = 0,\dots,N-1.$

因此離散信號 $x_n$ 的離散傅立葉變換現在可以分成三個步驟來實現：

• STEP 1：對於信號 $x_n$ 的每一個取樣點都乘上 $e^{-\frac{\pi i}{N}n^2}$
• STEP 2：接著再與 $e^{\frac{\pi i}{N}n^2}$ 做線性回旋積分
• STEP 3：最後乘上 $e^{-\frac{\pi i}{N}k^2}$

如此即可得到不同頻率成分的 $X_k$ 。

相關條目

• 摺積
• 離散傅立葉變換
• 快速傅立葉變換

參考文獻

• Jian-Jiun Ding, class lecture of Time Frequency Analysis and Wavelet transform, Graduate Institute of Communication Engineering, National Taiwan University, Taipei, Taiwan, 2007.
• http://cnx.org/content/m12013/latest/