序列卷积的方便算法

序列卷积的方便算法

——杨 曦


序列 卷 积 的 计 算 我 们 常 常 遇 到， 但 能 用 的 方 法 老 师 教 过 两 种： 图 解 法 和 列 表 法。 图 解 法 主 要 用 来 解 释 卷 积 的 定 义， 实 际 做 起 来 不 胜 其 繁； 列 表 法 虽 然 简 单， 不 过 要 先 划 表 线 (当 然 熟 了 也 可 不 用)， 标 注 离 散 时 间， 最 后 还 要 斜 向 相 加， 做 起 来 也 不 利 索。 这 里 介 绍 一 种 谁 都 会 做 的 方 法， 做 起 来 极 快。 其 实 无 线 电 系 的 瞎 子 都 能 证 明， 但 注 意 到 此 的 人 似 乎 极 少， 是 以 吾 推 荐 之。
本 方 法 的“ 奥 妙” 在 于： 两 个 多 项 式 的 积 的 系 数 序 列， 正 是 以 这 两 个 多 项 式 系 数 构 成 的 两 个 序 列 的 序 列 卷 积， 多 项 式 的 指 数 等 于 序 列 对 应 点 的 离 散 时 间。

例: {a}:  a[-1]=2, a[0]=1, a[1]=3,  a[2]=4 
    {b}:  b[2]=.5, b[3]=4, b[4]=-1, b[5]=2

计  算 c=a*b 。

解：               2    1    3    4
         ×       .5    4   -1    2 
        ————————————————       
                   4    2    6    8
             -2   -1   -3   -4
        8     4   12   16
  ＋1  .5   1.5    2
 ————————————————————
    1  8.5  3.5   17   15    2    8

∴ c[1]=1,  c[2]=8.5, c[3]=3.5, c[4]=17
   c[5]=15, c[6]=2    c[7]=8

不 难 看 出， 其 实 这 种 方 法 与 列 表 法 无 异。 不 过 把 表 斜 着 列， 从 而 竖 着 相 加 而 已。