啁啾-Z转换(Chirp-Z transform)为离散傅里叶变换(DFT)的一般化,是一种适合于计算当取样频率间隔(sampling frequency interval)与取样时间间隔(sampling time interval)乘积的倒数不等于信号的时频分布面积时的算法,其为利用卷积来实现任意大小的离散傅里叶变换(DFT)的快速傅里叶变换算法。
此卷积动作可以透过卷积理论所实现,其中,由于这些快速傅里叶转换结果的长度 N 不同,导致我们必须透过补零的方式,将快速傅里叶转换的结果补至长度大于或等于 2N - 1,才能精确计算其卷积结果。此外,布鲁斯坦算法提供一个时间复杂度为 O(N log N) 的方式计算质数大小的离散傅里叶转换。
在布鲁斯坦算法的卷积过程中使用补零的方式是值得讨论的。如果我们将讯号补至长度为 M ≥ 2N–1,代表 an 被扩展至长度为 M 的阵列 An,其中当 0 ≤ n < N 时,An = an,否则 An = 0。然而,基于卷积中的 bk–n 项, bn 需要 n 的正值和负值。在阵列中补零的离散傅里叶转换的周期性边界,代表着 -n 等于 M - n。因此,bn 被扩展到长度为 M 的阵列 Bn,其中 B0 = b0,Bn = BM–n = bn(当 0 < n <),否则,Bn = 0。然后根据通常的卷积定理对 A 和 B 进行快速傅里叶转换,逐点相乘,并进行逆快速傅里叶转换以获得 a 和 b 的卷积。
让我们更准确地说明,布鲁斯坦算法的离散傅里叶转换需要什么类型的卷积。如果序列 bn 在具有周期 N 的 n 中是具有周期性的,那么它将是长度为 N 的循环卷积,并且,为了计算上的方便而使用补零的方式。但是,通常情况并非如此:
因此,当 N 为偶数时,卷积是具有周期性的,但在这种情况下,人们通常使用更有效率的快速傅里叶转换算法,例如Cooley-Tukey算法;反之,当 N 为奇数时,bn 是反周期性的,并且具有长度 N 的负循环卷积。然而,当如上所述,使用补零的方式江阵列补到至少 2N−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.