Chirp Z 变换

Chirp Z 变换也被称为 Bluestein 算法。与离散傅里叶变换类似,Chirp Z 变换是给出多项式 求出 的一种算法,不要求 为单位根。也可用于数论变换。

方法一

令幂级数 且对于 ,对于

通过计算 可得到 。而对于 可构造 后同理,该算法需两次卷积。因为我们从 开始提取系数,所以可以利用循环卷积。

方法二

对于非负整数 考虑

其中 为二项式系数,那么

且对于 那么对于

通过计算 可得到 ,该算法需一次卷积。且 ,可递推计算。