相关运算、卷积运算与Toeplitz矩阵的关系

设序列\(x[n]\)和\(y[n]\)的长度分别为\(N\)和\(M\)，则两者的相关及卷积运算可以分别表示为：

\[\begin{cases} R_{xy}[m]=\sum_{n=-\infty}^{\infty}{x[n]y[n+m]}\\ R_{yx}[m]=\sum_{n=-\infty}^{\infty}{y[n]x[n+m]} \tag{1} \end{cases} \]

\[\begin{cases} C_{xy}[m]=\sum_{n=-\infty}^{\infty}{x[n]y[m-n]}\\ C_{yx}[m]=\sum_{n=-\infty}^{\infty}{y[n]x[m-n]} \tag{2} \end{cases} \]

其中\(R_{xy} \neq R_{yx}\)，\(C_{xy}=C_{yx}\)，且\(R_{xy}[m]=\sum_{n=-\infty}^{\infty}{x[n]y[n+m]}=\sum_{n=-\infty}^{\infty}{x[n]y[m-(-n)]}=x[n]*y[-n]\)。以下通过简单的例子说明(1)(2)的计算方法：设\(x[n]=[1,2]\)，\(y[n]=[4,5,6]\)，则\(R_{xy}[m]\)的计算步骤如下：

(1)将\(x[n]\)和\(y[n+m]\)表示出来，其中\(x[n]\)恒为原始序列，\(y[n+m]\)表示对\(y[n]\)序列线性左移(\(m>0\))或右移(\(m < 0\))\(m\)位；

(2)将\(x[n]\)和\(y[n+m]\)各个位数对齐(因长度不一致导致的两个序列不对齐的情况，对应数位等效于与0对齐)，形成竖式；

(3)对应位置处的数相乘，并把所有相乘结果进行累加。

对于本文例子，具体操作示意如下：

\[\begin{array} & 6 & 0\\ 1 & 2\\ \hline 6 & 0 \rightarrow 6 \end{array} \begin{array} & 5 & 6 \\ 1 & 2 \\ \hline 5 & 12 \rightarrow 17 \end{array} \begin{array} & 4 & 5 \\ 1 & 2 \\ \hline 4 & 10 \rightarrow 14 \end{array} \begin{array} & 0 & 4 \\ 1 & 2 \\ \hline 0 & 8 \rightarrow 8 \end{array} \tag{3} \]

上面每个竖式分别对应\(m=2,1,0,-1\)的情况，所以本例中\(R_{xy}=[6,17,14,8]\)，由此可见长度为\(N\)，\(M\)的两个序列的自相关结果长度为\(N+M-1\)。

\(C_{xy}[m]\)的计算步骤与上述步骤相似，只是在所有运算之前需要对其中一个序列进行反转，所以其具体实现步骤可以简单描述为：

(1)将\(x[n]\)和\(y[m-n]\)表示出来，其中\(x[n]\)恒为原始序列，\(y[m-n]\)表示先对原始序列进行反转得到\(y[-n]\)，然后再将\(y[-n]\)序列线性左移(\(m>0\))或右移(\(m < 0\))\(m\)位，在本例中反转后的\(y[-n]=[6,5,4]\)；

(2)将\(x[n]\)和\(y[m-n]\)各个位数对齐，(因长度不一致导致的两个序列不对齐的情况，对应数位等效于与0对齐)形成竖式；

(3)对应位置处的数相乘，并把所有相乘结果进行累加。

对于本文例子，具体操作示意如下：

\[\begin{array} & 4 & 0 \\ 1 & 2 \\ \hline 4 & 0 \rightarrow 4 \end{array} \begin{array} & 5 & 4 \\ 1 & 2 \\ \hline 5 & 8 \rightarrow 13 \end{array} \begin{array} & 6 & 5 \\ 1 & 2 \\ \hline 6 & 10 \rightarrow 16 \end{array} \begin{array} & 0 & 6 \\ 1 & 2 \\ \hline 0 & 12 \rightarrow 12 \end{array} \tag{4} \]

上面每个竖式分别对应\(m=-1,0,1,2\)的情况，所以本例中\(C_{xy}=[12,16,13,4]\)，由此可见长度为\(N\)，\(M\)的两个序列的线性卷积长度为\(N+M-1\)。

上面的(3)(4)两个式子可以分别表示为矩阵形式：

\[\vec{R}_{xy}= \begin{bmatrix} 6 \\ 17\\ 14\\ 8\\ \end{bmatrix} = \begin{bmatrix} 6 & 0 \\ 5 & 6 \\ 4 & 5 \\ 0 & 4 \\ \end{bmatrix} \begin{bmatrix} 1\\ 2\\ \end{bmatrix} =\boldsymbol{T} \vec{x} \]

\[\vec{C}_{xy}= \begin{bmatrix} 4 \\ 13\\ 16\\ 12\\ \end{bmatrix} = \begin{bmatrix} 4 & 0 \\ 5 & 4 \\ 6 & 5 \\ 0 & 6 \\ \end{bmatrix} \begin{bmatrix} 1\\ 2\\ \end{bmatrix} =\boldsymbol{T} \vec{x} \]

从上面的式子可以看出，矩阵\(\boldsymbol{T}\)每条对角线元素分别相同，是一个Toeplitz矩阵，所以两个序列之间的相关或线性卷积运算可以表示为由其中一个序列的元素组成的Toeplitz矩阵和另一个序列的乘积，一般地，设序列\(x[n]=[x_1,...,x_N]\)，\(y[n]=[y_1,...,y_M]\)，则有

\[\vec{R}_{xy}= \begin{bmatrix} y_M & 0 & 0 & \cdots & 0 \\ y_{M-1} & y_M & 0 & \cdots & 0 \\ y_{M-2} & y_{M-1} & y_{M} & \ddots & \vdots \\ \vdots & \ddots & \ddots & \cdots & \vdots \\ y_1 & y_2 & \ddots & y_{M-1} & y_M \\ 0 & y_1 & \cdots & y_{M-2} & y_{M-1} \\ \vdots & \ddots & \cdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & y_1 \end{bmatrix} \begin{bmatrix} x_1\\ \vdots\\ x_N\\ \end{bmatrix} \tag{5} \]

\[\vec{C}_{xy}= \begin{bmatrix} y_1 & 0 & 0 & \cdots & 0 \\ y_2 & y_1 & 0 & \cdots & 0 \\ y_3 & y_2 & y_1 & \ddots & \vdots \\ \vdots & \ddots & \ddots & \cdots & \vdots \\ y_M & y_{M-1} & \ddots & y_2 & y_1 \\ 0 & y_M & \cdots & y_3 & y_2 \\ \vdots & \ddots & \cdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & y_M \end{bmatrix} \begin{bmatrix} x_1\\ \vdots\\ x_N\\ \end{bmatrix} \tag{6} \]

从上面的表达式可以看出，两个序列的相关运算和线性卷积运算对应的Toeplitz矩阵的形式一样，但是序列元素在矩阵中的位置不一样，且此时Toeplitz矩阵是一个\((N+M-1) \times N\)的矩阵。采用矩阵形式表示容易进行后续分析与计算，因此在相关运算和线性卷积运算中，Toeplitz矩阵很常见，它的相关性质可以参考《托普利兹矩阵》。