生成矩阵(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 $$

特征值解码

[最大似然解码](https://www.pluvet.com/2020/12/26 / 最大似然译码详解(最大似然解码,maximum-likelihood-decoding)/) 的解码函数是通过穷举所有可能的输入实现的,数据空间占用较大。所以发明了特征值解码方法。

【例子】

$\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$,从而解码出了传递的数据。