Site Overlay

离散数学:特征值(校验子)解码详解(Syndrome Decoding)

生成矩阵(Generator Matrix)

这是表示编码函数的矩阵。行数表示信息位数量,列数表示码长。典型阵是以单位矩阵打头的生成矩阵,比如下面:

$$
\bold{G}=\left[\begin{array}{llllll}
\color{blue}1 & 0 & 0 & 0 & 1 & 1 \\
0 & \color{blue}1 & 0 & 1 & 0 & 1 \\
0 & 0 & \color{blue}1 & 1 & 1 & 0
\end{array}\right]
$$

我们要表示 $101$ 的编码,只需要第一行加上第三行:

$\begin{bmatrix}1&0&0&0&1&1\end{bmatrix}+\begin{bmatrix}0&0&1&1&1&0\end{bmatrix}=\begin{bmatrix}1&0&1&1&1&1\end{bmatrix}$

信道编码(Channel coding)

假定有生成矩阵:

$$
\mathbf {G^{T}} :={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}
$$

要编码的数据为 $\begin{pmatrix}1&0&1&1\end{pmatrix}^\mathrm{T}$,则编码后的数据是:

$$
{\mathbf {x}}={\mathbf {G}^{\mathrm{T}}}{\mathbf {p}}={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}2\\3\\1\\2\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}
$$

$0110011$

校验矩阵(Parity Check Matrix)

校验矩阵用于检查接收的码字是否存在错误,记作 $\bold{H}$。例如有:

$$
{H} :={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}
$$

则:

$$
{\mathbf {z}}={\mathbf {H}}{\mathbf {r}}={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}2\\4\\2\end{pmatrix}}={\begin{pmatrix}0\\0\\0\end{pmatrix}}
$$

$\bold z$ 称为特征向量(syndrome vector),可以发现结果是零向量,因此没有错误发生。

生成矩阵和校验矩阵的关系

可以相互导出:

$$
\bold{GH}^{T} = \bold 0
$$

特征值解码

最大似然解码的解码函数是通过穷举所有可能的输入实现的,数据空间占用较大。所以发明了特征值解码方法。

【例子】

$\underline{\mathbf{E x}} \mathbf{1}$ Let $C_{1}$ be linear binary [6,3,3] code with generator matrix

$$
\mathrm{G}=\pmatrix{
1 & 0 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 1 & 0
}
$$

and parity check matrix

$$
\mathrm{H}=\pmatrix{0 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 1}
$$

We receive $\vec{v} = \pmatrix{1&1&1&1&0&1}$,is there any error? what is the original message?

【分析与解答】

求陪集首部的特征值

首先求特征值表,前七种可以用零向量和单位向量,最后一种靠试错即可。

$000000$$H \cdot \bar{0} = 000$

$000001$$001$

这里我展开说说吧:

$$
\begin{align}
H \cdot \vec{e_1} &=
\pmatrix{0 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 1}
\color{blue}\pmatrix{0\\0\\0\\0\\0\\1}\\
&=\pmatrix{0\\0\\1}
\end{align}
$$

就是用 $H$ 左乘各种向量,得到的是特征向量。为什么选择 $e_1, \cdots$ 这些单位向量呢?其实选什么都可以,只要算出来的特征值没有和前面重复过就行!选单位向量的话,1 的个数少,好算。

$000010$$010$

$000100$$100$

$001000$$110$

$010000$$101$

$100000$$011$

还差两个,我们随便找点试试:

$000011$$011$,这个不行,重复了。

$000101$$101$,也重复了。这样一个一个尝试,太慢了。有没有什么好办法呢?有!

现在已经找到了的,排序之后是:$000,001,010,011,100,101,110$,还缺什么?$111$,所以我们找

$000111$,计算得到 $\vec{e} = 111$

整理一下:

特征值(校验子) 陪集头(错误向量)
000 000000
001 000001
010 000010
011 100000
100 000100
101 010000
110 001000
111 000111

解码

我们要解码的向量是 $\vec{v} = 111101$,且已知 $\vec{v} = \vec{c} +\vec{e}$(c 是发送的代码字,e 是错误向量,v 是接收的向量)。用奇偶校验矩阵处理 $\vec{v}$

$$
H \cdot \vec{v}=\begin{pmatrix}0&1&1&1&0&0\\ 1&0&1&0&1&0\\ 1&1&0&0&0&1\end{pmatrix}\begin{pmatrix}1\\ 1\\ 1\\ 1\\ 0\\ 1\end{pmatrix}=\begin{pmatrix}1\\ 0\\ 1\end{pmatrix}
$$

得到的特征值是 $101$,查表得错误向量是 $\vec{e} = 010000$,因此 $\vec{c} = \vec{v} - \vec{e} = 111101-010000 = 101101$,从而解码出了传递的数据。

发表评论

电子邮件地址不会被公开。 必填项已用*标注