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