Chirp Z 变换

Chirp Z 变换也被称为 Bluestein 算法。与离散傅里叶变换类似，Chirp Z 变换是给出多项式 $A (x) = \sum_{i = 0}^{n} a_{i} x^{i} \in C [x]$ 和 $c \in C ∖ {0}$ 求出 $A (1), A (c), A (c^{2}), \dots$ 的一种算法，不要求 $c$ 为单位根。也可用于数论变换。

方法一

令幂级数 $A_{0} (x) = \sum_{i \geq 0} a_{i} c^{i^{2}} x^{i}$ 且对于 $\forall j > n$ 令 $a_{j} = 0$ 、 $B_{0} (x) = \sum_{i \geq 0} c^{- (i - n)^{2}} x^{i}$ ，对于 $t \geq 0$ 有

\begin{aligned} [x^{n + t}] (A_{0} (x) B_{0} (x)) & = \sum_{i = 0}^{n + t} ([x^{i}] A_{0} (x)) ([x^{n + t - i}] B_{0} (x)) \\ = \sum_{i = 0}^{n + t} a_{i} c^{i^{2} - (i - t)^{2}} \\ = c^{- t^{2}} \sum_{i = 0}^{n + t} a_{i} c^{2 i t} \\ = c^{- t^{2}} A (c^{2 t}) \end{aligned}

通过计算 $c^{t^{2}} [x^{n + t}] (A_{0} (x) B_{0} (x))$ 可得到 $A (1), A (c^{2}), \dots$ 。而对于 $A (c), A (c^{3}), \dots$ 可构造 $A (c x)$ 后同理，该算法需两次卷积。因为我们从 $x^{n}$ 开始提取系数，所以可以利用循环卷积。

方法二

对于非负整数 $k$ 和 $i$ 考虑

k i = (\binom{i + k}{2}) - (\binom{i}{2}) - (\binom{k}{2})

其中 $(\binom{a}{b}) = \frac{a (a - 1) \dots (a - b + 1)}{b!}$ 为二项式系数，那么

A (c^{k}) = c^{- (\binom{k}{2})} \sum_{i = 0}^{n} a_{i} c^{(\binom{i + k}{2}) - (\binom{i}{2})}

令 $A_{0} (x) = \sum_{i} a_{n - i} c^{- (\binom{n - i}{2})} x^{i}$ 且对于 $\forall j > n$ 和 $\forall j < 0$ 令 $a_{j} = 0$ 、 $B_{0} (x) = \sum_{i \geq 0} c^{(\binom{i}{2})} x^{i}$ 那么对于 $t \geq 0$ 有

\begin{aligned} [x^{n + t}] (A_{0} (x) B_{0} (x)) & = \sum_{i = 0}^{n + t} ([x^{n + t - i}] A_{0} (x)) ([x^{i}] B_{0} (x)) \\ = \sum_{i = 0}^{n + t} a_{i - t} c^{(\binom{i}{2}) - (\binom{i - t}{2})} \\ = \sum_{i = - t}^{n} a_{i} c^{(\binom{i + t}{2}) - (\binom{i}{2})} \\ = c^{(\binom{t}{2})} \cdot A (c^{t}) \end{aligned}

通过计算 $c^{- (\binom{t}{2})} [x^{n + t}] (A_{0} (x) B_{0} (x))$ 可得到 $A (1), A (c), \dots$ ，该算法需一次卷积。且 $\forall i \geq 0$ 有 $c^{(\binom{i + 1}{2})} = c^{(\binom{i}{2})} \cdot c^{i}$ ，可递推计算。

本页面最近更新：2021/10/26 21:54:45，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：hly1204, Xeonacid, CornWorld
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用