Chirp Z 变换
Chirp Z 变换也被称为 Bluestein 算法。与离散傅里叶变换类似,Chirp Z 变换是给出多项式 𝐴(𝑥) =∑𝑛𝑖=0𝑎𝑖𝑥𝑖 ∈ℂ[𝑥]
和 𝑐 ∈ℂ ∖{0}
求出 𝐴(1),𝐴(𝑐),𝐴(𝑐2),…
的一种算法,不要求 𝑐
为单位根。也可用于数论变换。
方法一
令幂级数 𝐴0(𝑥) =∑𝑖≥0𝑎𝑖𝑐𝑖2𝑥𝑖
且对于 ∀𝑗 >𝑛
令 𝑎𝑗 =0
、𝐵0(𝑥) =∑𝑖≥0𝑐−(𝑖−𝑛)2𝑥𝑖
,对于 𝑡 ≥0
有
[𝑥𝑛+𝑡](𝐴0(𝑥)𝐵0(𝑥))=𝑛+𝑡∑𝑖=0([𝑥𝑖]𝐴0(𝑥))([𝑥𝑛+𝑡−𝑖]𝐵0(𝑥))=𝑛+𝑡∑𝑖=0𝑎𝑖𝑐𝑖2−(𝑖−𝑡)2=𝑐−𝑡2𝑛+𝑡∑𝑖=0𝑎𝑖𝑐2𝑖𝑡=𝑐−𝑡2𝐴(𝑐2𝑡)
通过计算 𝑐𝑡2[𝑥𝑛+𝑡](𝐴0(𝑥)𝐵0(𝑥))
可得到 𝐴(1),𝐴(𝑐2),…
。而对于 𝐴(𝑐),𝐴(𝑐3),…
可构造 𝐴(𝑐𝑥)
后同理,该算法需两次卷积。因为我们从 𝑥𝑛
开始提取系数,所以可以利用循环卷积。
方法二
对于非负整数 𝑘
和 𝑖
考虑
𝑘𝑖=(𝑖+𝑘2)−(𝑖2)−(𝑘2)
其中 (𝑎𝑏) =𝑎(𝑎−1)⋯(𝑎−𝑏+1)𝑏!
为二项式系数,那么
𝐴(𝑐𝑘)=𝑐−(𝑘2)𝑛∑𝑖=0𝑎𝑖𝑐(𝑖+𝑘2)−(𝑖2)
令 𝐴0(𝑥) =∑𝑖𝑎𝑛−𝑖𝑐−(𝑛−𝑖2)𝑥𝑖
且对于 ∀𝑗 >𝑛
和 ∀𝑗 <0
令 𝑎𝑗 =0
、𝐵0(𝑥) =∑𝑖≥0𝑐(𝑖2)𝑥𝑖
那么对于 𝑡 ≥0
有
[𝑥𝑛+𝑡](𝐴0(𝑥)𝐵0(𝑥))=𝑛+𝑡∑𝑖=0([𝑥𝑛+𝑡−𝑖]𝐴0(𝑥))([𝑥𝑖]𝐵0(𝑥))=𝑛+𝑡∑𝑖=0𝑎𝑖−𝑡𝑐(𝑖2)−(𝑖−𝑡2)=𝑛∑𝑖=−𝑡𝑎𝑖𝑐(𝑖+𝑡2)−(𝑖2)=𝑐(𝑡2)⋅𝐴(𝑐𝑡)
通过计算 𝑐−(𝑡2)[𝑥𝑛+𝑡](𝐴0(𝑥)𝐵0(𝑥))
可得到 𝐴(1),𝐴(𝑐),…
,该算法需一次卷积。且 ∀𝑖 ≥0
有 𝑐(𝑖+12) =𝑐(𝑖2) ⋅𝑐𝑖
,可递推计算。
本页面最近更新:2021/10/26 21:54:45,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:hly1204, Xeonacid, CornWorld
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用