Chirp Z 變換

Chirp Z 變換也被稱為 Bluestein 算法。與離散傅里葉變換類似，Chirp Z 變換是給出多項式 \(A(x)=\sum_{i=0}^na_ix^i\in\mathbb{C}\lbrack x\rbrack\) 和 \(c\in\mathbb{C}\setminus \{0\}\) 求出 \(A(1),A(c),A(c^2),\dots\) 的一種算法，不要求 \(c\) 為單位根。也可用於數論變換。

方法一

令冪級數 \(A_0(x)=\sum_{i\geq 0}a_ic^{i^2}x^i\) 且對於 \(\forall j\gt n\) 令 \(a_j=0\)、\(B_0(x)=\sum _ {i\geq 0}c^{-(i-n)^2}x^i\)，對於 \(t\geq 0\) 有

\[ \begin{aligned} \lbrack x^{n+t}\rbrack (A_0(x)B_0(x))&=\sum_{i=0}^{n+t}\left(\lbrack x^i\rbrack A_0(x)\right)\left(\lbrack x^{n+t-i}\rbrack B_0(x)\right)\\ &=\sum_{i=0}^{n+t}a_ic^{i^2-(i-t)^2}\\ &=c^{-t^2}\sum_{i=0}^{n+t}a_ic^{2it}\\ &=c^{-t^2}A(c^{2t}) \end{aligned} \]

通過計算 \(c^{t^2}\lbrack x^{n+t}\rbrack (A_0(x)B_0(x))\) 可得到 \(A(1),A(c^2),\dots\)。而對於 \(A(c),A(c^3),\dots\) 可構造 \(A(cx)\) 後同理，該算法需兩次卷積。因為我們從 \(x^n\) 開始提取係數，所以可以利用循環卷積。

方法二

對於非負整數 \(k\) 和 \(i\) 考慮

\[ ki=\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2} \]

其中 \(\binom{a}{b}=\frac{a(a-1)\cdots (a-b+1)}{b!}\) 為二項式係數，那麼

\[ A(c^k)=c^{-\binom{k}{2}}\sum _ {i=0}^na_ic^{\binom{i+k}{2}-\binom{i}{2}} \]

令 \(A_0(x)=\sum_{i}a_{n-i}c^{-\binom{n-i}{2}}x^i\) 且對於 \(\forall j\gt n\) 和 \(\forall j\lt 0\) 令 \(a_j=0\)、\(B_0(x)=\sum_{i\geq 0}c^{\binom{i}{2}}x^i\) 那麼對於 \(t\geq 0\) 有

\[ \begin{aligned} \lbrack x^{n+t}\rbrack (A_0(x)B_0(x))&=\sum _ {i=0}^{n+t}\left(\lbrack x^{n+t-i}\rbrack A_0(x)\right)\left(\lbrack x^{i}\rbrack B_0(x)\right)\\ &=\sum_{i=0}^{n+t}a_{i-t}c^{\binom{i}{2}-\binom{i-t}{2}}\\ &=\sum_{i=-t}^na_ic^{\binom{i+t}{2}-\binom{i}{2}}\\ &=c^{\binom{t}{2}}\cdot A(c^t) \end{aligned} \]

通過計算 \(c^{-\binom{t}{2}}\lbrack x^{n+t}\rbrack (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\)，可遞推計算。

---

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