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