Chirp-Z转换

啁啾-Z转换（Chirp-Z transform）为离散傅立叶变换（DFT）的一般化，是一种适合于计算当取样频率间隔（sampling frequency interval）与取样时间间隔（sampling time interval）乘积的倒数不等于信号的时频分布面积时的演算法，其为利用卷积来实现任意大小的离散傅立叶变换（DFT）的快速傅立叶变换演算法。

具体来说，啁啾-Z转换沿著对数螺旋轮廓，计算出有限数量的点 z_k 的Z转换，其定义如下：

X_{k}=\sum _{n=0}^{N-1}x(n)z_{k}^{-n}

z_{k}=A\cdot W^{-k},k=0,1,\dots ,M-1

其中A为起始点，W为点与点之间的比率，M为需要计算的点的数量。

布鲁斯坦演算法

离散信号 $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.

上面的累加结果恰为两个序列 a_n 及 b_n 的卷积，两序列的定义如下：

a_{n}=x_{n}e^{-{\frac {\pi i}{N}}n^{2}}

b_{n}=e^{{\frac {\pi i}{N}}n^{2}},

而产生的卷积结果会再乘上 N 个相位的参数 b_k^*：

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

如此即可得到不同频率成分的 $X_{k}$ 。

此卷积动作可以透过卷积理论所实现，其中，由于这些快速傅立叶转换结果的长度 N 不同，导致我们必须透过补零的方式，将快速傅立叶转换的结果补至长度大于或等于 2N - 1，才能精确计算其卷积结果。此外，布鲁斯坦演算法提供一个时间复杂度为 O(N log N) 的方式计算质数大小的离散傅立叶转换。

在布鲁斯坦演算法的卷积过程中使用补零的方式是值得讨论的。如果我们将讯号补至长度为 M ≥ 2N–1，代表 a_n 被扩展至长度为 M 的阵列 A_n，其中当 0 ≤ n < N 时，A_n = a_n，否则 A_n = 0。然而，基于卷积中的 b_k–n 项， b_n 需要 n 的正值和负值。在阵列中补零的离散傅立叶转换的周期性边界，代表著 -n 等于 M - n。因此，b_n 被扩展到长度为 M 的阵列 B_n，其中 B₀ = b₀，B_n = B_M–n = b_n(当 0 < n &lt)，否则，B_n = 0。然后根据通常的卷积定理对 A 和 B 进行快速傅立叶转换，逐点相乘，并进行逆快速傅立叶转换以获得 a 和 b 的卷积。

让我们更准确地说明，布鲁斯坦演算法的离散傅立叶转换需要什么类型的卷积。如果序列 b_n 在具有周期 N 的 n 中是具有周期性的，那么它将是长度为 N 的循环卷积，并且，为了计算上的方便而使用补零的方式。但是，通常情况并非如此：

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}.

因此，当 N 为偶数时，卷积是具有周期性的，但在这种情况下，人们通常使用更有效率的快速傅立叶转换演算法，例如Cooley-Tukey演算法；反之，当 N 为奇数时，b_n 是反周期性的，并且具有长度 N 的负循环卷积。然而，当如上所述，使用补零的方式江阵列补到至少 2N−1 的长度时，两者之间的差异消失。

Z转换

上述提到的布鲁斯坦演算法也可以基于单方面的Z转换，用以计算更一般化的转换(Rabiner et al, 1969)，特别是具有以下形式的转换：

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

其中 z 为任意复数，N以及M分别为输入及输出的数量。

由前面所提到的布鲁斯坦演算法，我们可以进行如此的转换。例如，获得讯号某一部分频谱中的内插值，以及在传递函数分析中增加任意极点，皆为其应用之一。

该演算法被称为啁啾-Z转换演算法，是因为在傅立叶转换的情境(|z| = 1)下，一序列 b_n 是一复数正弦波，而在雷达系统中则被称作“啁啾”。

参考文献

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/（页面存档备份，存于互联网档案馆）

布鲁斯坦演算法

Z转换

相关条目

参考文献