代数编码

检错码和纠错码

(n, m)-block code:
- 编码函数$E: \mathbb Z_2^m \to \mathbb Z_2^n$
- 译码函数$E: \mathbb Z_2^n \to \mathbb Z_2^m$
距离
权weight: 1的个数
$\omega (x) = d(x, 0)$
$d(x, y) = \omega(x + y)$
$d_{min} = 2n + 1$的编码可以纠任意小于等于n的错

group code: 编码为$\mathbb Z_2^n$的子群
验证group code: 只需检查任意两个编码之和仍然是合法编码
如果x和y都是二元组, 那么$\omega(x+y)=d(x, y)$
在group code C中, $d_{min}=\min\{\omega(x): x \ne 0\}$
x和y的内积: $x \cdot y = x_1y_1 + \cdots + x_ny_n = x^{\top}y$
null space: 所有x满足$Hx=0$. 记作$Null(H)$
$H\in \mathbb M _{m\times n}(\mathbb Z_2)$, $Null(H)$ is a group code, 称为线性编码
理想的编码过程: 构造一个$n \times (n-m)$的01矩阵$G$, 对于每个信息$x$, $Gx$可以得到一个$y$, $y$是群码字. 这里的m是校验位个数.

奇偶校验矩阵$H$:
- $m\times n$矩阵$H$最后m列为$I_m$, 那么这个矩阵就是奇偶校验矩阵(canonical parity-check matrix), $H=(A|I_m)$.
- $C$为$G$生成的编码, 则$y\in C$当且仅当$Hy = 0$. 而且$C$是$H$的线性编码.
- 若$y\in Null(H)$, 则$y$前$n - m$位任意, 后$m$位由$Hy = 0$计算得
生成矩阵$G$:
- $H=(A|I_m)$, ($A$是任取的), 则标准生成矩阵(standard generator matrix)$G = (\frac{I_{n-m}}{A})$, $G$是$n\times (n-m)$矩阵.
- $G$是$n\times k$标准生成阵, 则$C= \{y:Gx=y ~for ~x \in \mathbb Z_2^k\}$为$(n, k)$-block code, $C$也为group code.
codeword 计算:
- 计算$Null(H)$
- 计算$Gx$
$H$和$G$关系:
- $HG = 0$
- 存在$x$满足 $Gx=y$ 当且仅当 $Hy = 0$
纠错和检错能力:
- 检错能力: $Null(H)$是单检错码当且仅当$H$中任意一列都不全$0$
- 纠错能力: $Null(H)$是单纠错码当且仅当$H$无$0$列, 且没有相同列
- $d(c) =$ H中最小的线性相关的列向量的数量

检验是否是codeword: $Hx$是否为0; $Hx$定义为$x$的$syndrome$.
$x=c+e$, $c$为正确编码, $e$为传播错误, 则$x$和$e$的$syndrome$相同.
单纠错方法: $H$的线性编码是单纠错的, 接受的$n$元组为$r$.
- 若$r$的$syndrome$为0, 则$r$正确;
- 否则$r$的$syndrome$和$H$的哪一列相同就说明哪一位错误;
- 如果没有相同的, 说明错误位数大于1, 则无法纠错.