知识卡片
卷积可由变换后的逐点乘积求得
设a、b是两个长度n的系数向量,卷积cₖ=Σᵢ₊ⱼ₌ₖaᵢbⱼ就是对应多项式乘积的第k个系数。先把a、b补零到2n,DFT会把它们变成在2n个单位根上的求值向量;多项式乘法在点值表示下只需逐点相乘。再做逆DFT,即恢复出卷积系数:
a⊗b=DFT₂ₙ⁻¹(DFT₂ₙ(a)·DFT₂ₙ(b))
补零使乘积的最高可能次项仍被单独存放,防止高次系数回绕到低次位置而变成长n的循环卷积。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第30章 多项式与快速傅里叶变换 · 查看原书依据
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 2n and · denotes the componentwise product of two 2n-element vectors.
参考来源
- 位置:《算法导论(第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.