Chirp Z 变换

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

方法一

令幂级数 且对于 令 、，对于 有

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

方法二

对于非负整数 和 考虑

其中 为二项式系数，那么

令 且对于 和 令 、 那么对于 有

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