Chirp-Z转换

(重定向自Chirp-Z 轉換

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

具体来说,啁啾-Z转换沿着对数螺旋轮廓,计算出有限数量的点 zk 的Z转换,其定义如下:

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

布鲁斯坦算法

编辑

离散信号 的离散傅里叶变换可以写成下列的形式

 

其中 这项的 可以利用平方式展开得到,如下式所示

 

所以

 

而将此平方展开式带回原式我们可以得到

 

上面的累加结果恰为两个序列 anbn 的卷积,两序列的定义如下:

 
 

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

 


因此离散信号   的离散傅里叶变换现在可以分成三个步骤来实现:

  • STEP 1:对于信号 的每一个取样点都乘上 
  • STEP 2:接着再与 做线性卷积
  • STEP 3:最后乘上 

如此即可得到不同频率成分的 

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

在布鲁斯坦算法的卷积过程中使用补零的方式是值得讨论的。如果我们将讯号补至长度为 M ≥ 2N–1,代表 an 被扩展至长度为 M 的阵列 An,其中当 0 ≤ n < N 时,An = an,否则 An = 0。然而,基于卷积中的 bkn 项, bn 需要 n 的正值和负值。在阵列中补零的离散傅里叶转换的周期性边界,代表着 -n 等于 M - n。因此,bn 被扩展到长度为 M 的阵列 Bn,其中 B0 = b0Bn = BMn = bn(当 0 < n &lt),否则,Bn = 0。然后根据通常的卷积定理对 AB 进行快速傅里叶转换,逐点相乘,并进行逆快速傅里叶转换以获得 ab 的卷积。

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

 

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

Z转换

编辑

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

 

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

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

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

相关条目

编辑

参考文献

编辑
  • 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/(页面存档备份,存于互联网档案馆