特征值(校验子)解码详解(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$,从而解码出了传递的数据。

最近发布

要查看全部文章,请点击右上角“归档”,下面是最近发布的几篇日志