Chirp-Z轉換

（重定向自Chirp-Z 轉換

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x(n)z_{k}^{-n}}$
${\displaystyle z_{k}=A\cdot W^{-k},k=0,1,\dots ,M-1}$

布魯斯坦演算法

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

${\displaystyle a_{n}=x_{n}e^{-{\frac {\pi i}{N}}n^{2}}}$
${\displaystyle b_{n}=e^{{\frac {\pi i}{N}}n^{2}},}$

${\displaystyle X_{k}=b_{k}^{*}\sum _{n=0}^{N-1}a_{n}b_{k-n}\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-k)^{2}}}$ 做線性卷積
• STEP 3：最後乘上${\displaystyle e^{-{\frac {\pi i}{N}}k^{2}}}$

${\displaystyle b_{n+N}=e^{{\frac {\pi i}{N}}(n+N)^{2}}=b_{n}e^{{\frac {\pi i}{N}}(2Nn+N^{2})}=(-1)^{N}b_{n}.}$

Z轉換

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}z^{nk}\qquad k=0,\dots ,M-1,}$

參考文獻

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