[Convolutions, Polynomials and Flipped Kernels]

2025年5月20日 20:01 Tags Math , EE & Embedded

本文讨论多项式乘法、卷积求和以及它们之间的联系。

多项式乘法

假设我们要将一个多项式乘以另一个多项式：

\[(3x^3+x^2+2x+1)\cdot(2x^2+6)\]

这是基础的中学数学——我们首先进行交叉乘法：

\[6x^5+2x^4+4x^3+2x^2+18x^3+6x^2+12x+6\]

然后将所有项加在一起，合并同类项：

\[6x^5+2x^4+22x^3+8x^2+12x+6\]

让我们看看另一种实现相同结果的方法。与其交叉相乘所有项然后相加，不如关注输出中会出现哪些项，以及每个项的系数是什么。这很容易用一个表格来演示，我们将一个多项式水平排列，另一个多项式垂直排列。请注意，我们必须明确表示第二个多项式中 x 的零系数：

图中高亮显示了相加后得到输出中每一项的对角线。例如，要获得输出中 x^3 的系数，我们必须将以下各项相加：

• 第一个多项式中 x^3 的系数，乘以第二个多项式中的常数项（x^0 的系数）
• 第一个多项式中 x^2 的系数，乘以第二个多项式中 的系数
• 第一个多项式中 的系数，乘以第二个多项式中 x^2 的系数

（如果第二个多项式有一个 x^3 项，则需要添加另一个分量）

接下来，让我们转向稍微更抽象的表示：多项式 P 可以表示为系数 P_i 乘以 x 的相应幂的和 [1]:

\[P=\sum_{i}P_i x^i\]

假设我们有两个多项式 P 和 R。将它们相乘后，得到的多项式为 S。根据我们从上面的表格对角线得到的见解，我们可以说对于每个 k：

\[S_k=\sum_{i}P_i\cdot R_{k-i}\]

那么整个多项式 S 为：

\[S=\sum_{k} \left( \sum_{i}P_i\cdot R_{k-i}\right)x^k\]

理解这个公式很重要，因为它是本文的关键。让我们使用我们的示例多项式来了解它是如何工作的。首先，我们将这两个多项式表示为系数序列（从 0 开始，因此常数的系数排在第一位，最高次幂的系数排在最后）：

\[P=[1,2,1,3]\qquad R=[6,0,2]\]

在这种表示法中，P_0 是 P 列表中第一个元素，依此类推。要计算乘积中 x^3 的系数：

\[S_3=\sum_{i}P_i\cdot R_{3-i}\]

展开 P 的所有非零系数的和：

\[S_3=P_0 R_3+P_1 R_2+P_2 R_1+P_3 R_0=0+4+0+18=22\]

类似地，我们会发现 S_4=2，S_2=8，依此类推，得到与之前相同的最终多项式：

\[6x^5+2x^4+22x^3+8x^2+12x+6\]

使用这种配对求和的方法，有一个很好的图形化方法来乘以多项式：

我们从左边的图开始：其中一个多项式保持其原始形式，而另一个多项式则翻转（常数项在前，最高次项在后）。我们将这些多项式垂直对齐，然后将相应的系数相乘：输出的常数项系数只是第一个多项式的常数项系数乘以第二个多项式的常数项系数。

右图显示了下一步：第二个多项式向左移动一项，然后再次垂直对齐。将相应的系数相乘，然后将结果相加，得到输出多项式中 x 的系数。

我们通过向左移动下面的多项式来继续这个过程：

计算 x^2 然后 x^3 的系数。再进行几个步骤：

现在我们有了输出的所有系数。花点时间来说服自己，这种方法等同于之前显示的求和公式，也等同于更靠前的“表格中的对角线”方法。它们都在计算相同的东西 [2]!

希望现在应该清楚为什么第二个多项式需要“翻转”才能执行此过程。这一切都归结于哪些输入项配对来计算每个输出项。如上所示：

\[S_k=\sum_{i}P_i\cdot R_{k-i}\]

虽然索引 i 在 P 中沿一个方向移动（从低次项到高次项），但索引 k-i 在 R 中沿相反的方向移动。

如果这个过程让你想起了计算两个数组之间的卷积，那是因为它确实是！

信号、系统和卷积

信号与系统的理论是一个很大的主题（通常在本科工程学位中教授一到两个学期），但在这里我想重点介绍它的一方面，我发现它非常优雅。

让我们首先定义离散信号和系统，将自己限制在 1D（类似的想法适用于更高维度）：

离散信号：一个有序的数字序列 x[n]，带有整数索引 n\in \left\{ \dots,-2,-1,0,1,2,\dots \right\}。也可以将其视为函数 x:\mathbb{Z} \rightarrow \mathbb{R}。 离散系统：一个将输入信号 x[n] 映射到输出信号 y[n] 的函数。例如，y[n]=2x[n] 是一个将所有信号缩放两倍的系统。

这是一个示例信号：

这是一个 有限 信号。图表中未明确显示的所有值都假定为 0（例如，x[3]=0，x[-1]=0，x[99]=0 等）。

一个非常重要的信号是 离散冲击：

\[\delta[n]=\begin{cases} 1\quad if \quad n=0\\ 0\quad otherwise \end{cases}\]

以图形形式，这是 \delta[n]，以及它的几个时移变体。请注意，我们如何通过在 n 中添加或减去来在水平轴上左右移动信号。花点时间仔细检查一下为什么这可行。

冲击函数很有用，因为我们可以将任何离散信号分解为一系列缩放和移位的冲击函数。我们的示例信号在索引 0、1 和 2 处具有三个非零值；我们可以将其表示如下：

\[x[n]=x[0]\delta[n]+x[1]\delta[n-1]+x[2]\delta[n-2]=2\delta[n]+2\delta[n-1]+\delta[n-2]\]

更一般地，信号 x[n] 可以写成：

\[x[n]=\sum_{k} x[k]\delta[n-k]\]

（对于所有 x[k] 非零的 k）

在信号与系统的研究中，线性和时不变 (LTI) 系统尤为重要。

线性：假设 y_1[n] 是输入信号 x_1[n] 的系统输出，类似地，y_2[n] 是 x_2[n] 的输出。对于输入 a\cdot x_1[n] + b\cdot x_2[n]，线性系统输出 a\cdot y_1[n]+b\cdot y_2[n]，其中 a 和 b 是常数。

时不变：如果我们延迟输入信号一个常数：x_1[n-N]，则输出也类似地延迟：y_1[n-N]。换句话说，系统的响应具有相似的形状，无论何时收到信号（它今天的行为与昨天的行为相似）。

LTI 系统之所以重要，是因为上面讨论的将信号分解为冲击函数。假设我们要表征一个系统：它对任意信号的作用。对于 LTI 系统，我们只需要描述它对冲击的响应！

如果我们的系统对 \delta[n] 的响应是 h[n]，那么：

• 它对 c\cdot \delta[n] 的响应是 c\cdot h[n]，对于任何常数 c，因为系统是线性的。
• 它对 \delta[n-k] 的响应是 h[n-k]，对于任何时移 k，因为系统是时不变的。

我们将结合这些并再次使用线性（注意，在下面的公式中 x[k] 只是常数）；对分解为移位和缩放的冲击函数之和的信号的响应：

\[y[n]=\sum_{k} x[k]\delta[n-k]\]

是：

\[y[n]=\sum_{k} x[k]h[n-k]\]

此操作称为序列 x[n] 和 h[n] 之间的 卷积，并用 \ast 运算符表示：

\[y[n]=x[n]\ast h[n]\]

让我们来看一个例子。假设我们有一个 LTI 系统，它对冲击函数的响应如下：

响应具有 h[0]=1，h[1]=3，其他所有地方都为零。回想一下本节顶部的示例信号（序列 2、2、1）。我们可以将其分解为一系列缩放和移位的冲击函数，然后计算系统对每个冲击函数的响应。像这样：

顶行显示了分解为缩放和移位的冲击函数的输入信号；底行是每个输入的相应系统响应。如果我们仔细地将每个 n 的响应相加，我们将得到系统对我们输入的响应 y[n]：

现在，让我们计算相同的输出，但这次使用卷积求和。首先，我们将信号 x 和冲击响应 h 表示为序列（就像我们对多项式所做的那样），x[0] 在前，然后 x[1] 等：

\[x=[2,2,1]\qquad h=[1, 3]\]

卷积求和为：

\[y[n]=\sum_{k} x[k]h[n-k]\]

回想一下，k 的范围是 x 中所有非零元素。让我们计算 y[n] 的每个元素（注意 h 仅在索引 0 和 1 处非零）：

\[\begin{align*} y[0]&=x[0]h[0]=2\\ y[1]&=x[0]h[1]+x[1]h[0]=8\\ y[2]&=x[1]h[1]+x[2]h[0]=7\\ y[3]&=x[2]h[1]=3 \end{align*}\]

y 的所有后续值均为零，因为 k 的范围仅到 2，并且 h[4-2]=h[2]=0。

如果您仔细观察此计算，您会注意到 h 相对于 x 是“翻转”的，就像多项式一样：

• 我们从 x[n]（黑色）和翻转的 h[n]（蓝色）开始，并将第一个非零元素对齐。这将计算 y[0]
• 在后续步骤中，h[n] 每次向右滑动一个元素，并通过将对齐的 x 和 h 的元素积相加来计算 y 的下一个值。

就像多项式一样 [3]，输入之一被翻转的原因从卷积求和的定义中可以清楚地看出，其中一个索引增加 (k)，而另一个索引减少 (n-k)。

卷积的性质

卷积运算具有 许多有用的代数性质：线性、结合性、交换性、分配性等。

交换律意味着在以图形方式计算卷积时，哪个信号被“翻转”并不重要，因为：

\[y[n]=x[n]\ast h[n]=h[n]\ast x[n]\]

因此：

\[y[n]=\sum_{k} x[k]h[n-k]=\sum_{k} x[n-k]h[k]\]

但是卷积最重要的性质是它在频域中的行为。如果我们将 \mathcal{F}(f) 表示为信号 f 的傅里叶变换，则 卷积定理指出：

\[\mathcal{F}(f\ast g)=\mathcal{F}(f)\cdot\mathcal{F}(g)\]

卷积的傅里叶变换等于其操作数的傅里叶变换之间的简单乘法。这个事实——以及像 FFT 这样的高级算法——使得 实现卷积 非常高效。

这是一个深刻而引人入胜的话题，但我们将其留到以后再讲。

[1]| 理论上，-\infty<i<\infty, 但我们只关心非零系数。因此，我们不会指定求和范围；相反，\sum_{i} 表示“对所有非零系数求和” ---|--- [2]| 作为一个很棒的练习，探索一下相同的技术如何用于将两个数字相乘，将每个数字视为 10 的后续幂的多项式。最终只需要考虑进位，但它效果非常好！这篇博文 提供了更多信息，如果您有兴趣。 ---|--- [3]| 多项式和信号之间的行为相似性非常美妙，并且远非偶然。事实上，如果我们采用具有加法和乘法的多项式，我们会得到一个 环，它与具有类似运算的有限序列环同构。即使像“延迟”或“右移”这样的操作也可以通过将多项式乘以幂 x 来模拟（如果我们想要“左移”，则可以为负数）。这种同构广泛应用于数学；例如，普通生成函数 使用它将序列表示为多项式，然后以代数方式操作它们。在信号处理中，它也用于 Z 变换。 ---|--- 如有意见，请发送电子邮件给我。 © 2003-2025 Eli Bendersky 回到顶部