1 编码
1.1 信息(Message)
有限的 01 序列
1.2 码字(Word)
长度为 $m$ 的 0 和 1 的序列
1.3 群
集合 $B$ 是在模 2 加运算下的群
- $B^m=B\times B\times \cdots \times B$ 是定义了运算 $\oplus$ 的群：$(x_1,x_2,\cdots,x_m)\oplus (y_1,y_2,\cdots,y_m)=(x_1+y_1,x_2+y_2,\cdots,x_m+y_m)$
- $B^m$ 可简写成 $b_1b_2\cdots b_m$
1.4 编码函数
定义一一对应的编码函数 $e: B^m \rightarrow B^n$, 如果 $b \in B^m$，则 $e(b)$ 称为 $b$ 的码字(Word).
1.5 差错检测
如果 $x=e(b)$ 在传输过程中出现了 $h$ 个错误 ($1 \le h \le k$) ，称为发生了小于等于 $k$ 个错误，则 $x_t$ 不是一个码字。
1.6 权值
$x \in B^n$, $x$ 的权值 $\vert x\vert $ 为 $x$ 中 $1$ 的个数.
1.7 海明距离(Hamming distance)
令 $x$ 和 $y$ 是 $B^m$ 的码字，$\delta(x, y)=\vert x \oplus y\vert $ ($x \oplus y$) 的权值.
也就是有几位不同.
- $\delta(x, y) = \delta(y, x)$
- $\delta(x, y) \ge 0$
- $\delta(x,y) = 0 \text{ iff } x=y$
- $\delta(x, y) \le \delta(x, z) + \delta(z, y)$
1.8 最小距离(Minimum distance)
最小距离是所有不同码字中距离最小的那一个。
\[\min\{\delta(e(x),e(y))\vert ,x,y\in B^m\}\]1.9 定理
如果一个 $B^m \rightarrow B^n$ 的编码函数可以检测 $k$ 的错误，则当且仅当它的最小距离最少是 $k+1$。
2 群码
如果存在一个 $B^m \rightarrow B^n$ 的编码函数 $e$ ，并且 $e(B^m)={e(b)\vert e(b) \in B^n}$ 是 $B^n$ 的子群，则 $e$ 是一个群码。
2.1 定理一
如果一个编码函数$e$ 是群码，则它的最小距离是其中最小非零码字的权值。
2.2 定理二
令 $0 \le m < n$, $r = n - m$，$\mathbf{H}$ 是 $n \times r$ 的布尔矩阵，则函数 $f_H: B^n \rightarrow B^r$ 定义为 $f_H(x)=x * \mathbf{H}, x \in B^n$ 是 $B^n$ 到 $B^r$ 到同态。
2.3 推论一
2.2 中的 $m, n, r, \mathbf{H}$，$N={x \in B^n\vert x * \mathbf{H} = 0}$ 是 $B^n$ 的正规子群。
2.4 一致性检验矩阵
\[\mathbf{H}=\begin{bmatrix}\mathbf{H}_{m\times r} \\ \mathbf{I}_r \end{bmatrix}\]2.4.1 构造编码函数
$H=e_H(B^m)=B^m * \begin{bmatrix}I_m & H_{m\times r}\end{bmatrix}$
2.4.2 定理一
如果 $x=e_H(b), b \in B^m$, 则 $x * \mathbf{H}=0$
2.4.3 推论二
$e_H(B^m)={e_H(b)\vert b \in B^m}$ 是 $B^n$ 的子群。
3 译码
若 $e: B^m\rightarrow B^n$，定义一个满射的函数 $d$，是和 $e$ 相关联的译码函数。当传输信道无噪声的时候，$d \cdot e=1_{B^m}$
3.1 极大似然技术
如果收到一个码字 $x_t$，计算对于每一个码字的 $\delta(x^{(i)},x_t)$ ，并选取第一个距离最小的码字
\[\min_{1\le i \le 2^m}\{\delta(x^{(i)},x_t\}=\delta(x^{(s)},x_t)\]3.2 定理一
$(e, d)$ 能纠正 $k$ 个错误，当且仅当 $e$ 的最小距离为 $2k+1$.
3.3 构造译码函数
如果 $K$ 是 $G$ 的子群，则 $K$ 在 $G$ 中点每一个左陪集都和 $K$ 有相同数量的元素。
若接收到了 $x^t$，$N=e(B^m)$，则 $x_t$ 的左陪集为 $x_t \oplus N={\epsilon_1, \epsilon_2, \cdots, \epsilon_{2m}}$, $\epsilon_i=x_t \oplus x^{(i)}$
如果 $\epsilon_j$ 是陪集元素中具有最小权值的元素，则 $x^{(j)}$ 是距离 $x_t$ 的码字，则 $\epsilon_j$ 称为陪集头.
STEP 1：确定所有 $N$ 的左陪集
STEP 2：对于每一个陪集，找到陪集头
STEP 3：如果收到 $x^t$，确定 $x^t$ 属于哪一个$N$ 的陪集
STEP 4：令$\epsilon$ 为陪集头，计算 $x=x_t \oplus \epsilon$，如果 $x = e(b)$ 则 $d(x_t)=b$.