知识卡片

普通读书笔记卡 · 3692.a.1.a.1

卷积可由变换后的逐点乘积求得

理解等级:中级

设a、b是两个长度n的系数向量,卷积cₖ=Σᵢ₊ⱼ₌ₖaᵢbⱼ就是对应多项式乘积的第k个系数。先把a、b补零到2n,DFT会把它们变成在2n个单位根上的求值向量;多项式乘法在点值表示下只需逐点相乘。再做逆DFT,即恢复出卷积系数:

a⊗b=DFT₂ₙ⁻¹(DFT₂ₙ(a)·DFT₂ₙ(b))

补零使乘积的最高可能次项仍被单独存放,防止高次系数回绕到低次位置而变成长n的循环卷积。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第30章《多项式与快速傅里叶变换》(OEBPS/chapter030.xhtml,文本字符[20000,25000))。 - 结论依据:定理30.8及 `OEBPS/images/Art_P1100.jpg` 的卷积公式;前提是 n 为2的幂,a、b 各从 n 补零至2n,乘积在2n维逐分量计算。 - 公式图核读:a⊗b=DFT₂ₙ⁻¹(DFT₂ₙ(a)·DFT₂ₙ(b)),右侧 a、b 指补零后的2n维向量。 - 原始内容:Theorem 30.8 (Convolution theorem) For any two vectors a and b of length n , where n is an exact power of 2, where the vectors a and b are padded with 0s to length 2 n and · denotes the componentwise product of two 2 n -element vectors.