Chirp-Z轉換

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

演算法

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.}$

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

${\displaystyle 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}}}$

${\displaystyle 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.}$

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

參考文獻

• 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/