汉明重量

定义14 设$G$ 不是零矩阵，则称非零码字中非零元的数量为该码字的汉明重。一个编码中所有非零码字的汉明重的最小值称为$G$的最小汉明重。

汉明距离

定义15 设$x=(x_1,\cdots ,x_n),y=(y_1,\cdots ,y_n)$是两码字。则定义
$$d(x,y):=\sum _{i=1}^n\left(x_i\oplus y_i\right)$$

为它们的汉明距离。

求和号表示的是普通的加法，而求和号里面是二元域的加法。

可以证明，汉明距离确实是一个距离，即满足严格正定性、对称性和三角不等式。

由上述定义可知，一个线性码的最小汉明重等于码字集中的最小汉明距离。

汉明重量与校验矩阵的关系

定理9 设$H$是$G$的校验矩阵，则$H$的任意$t$列线性无关且存在$t+1$列线性相关当且仅当$G$的最小汉明重为$t+1$ 。

证明$G$的最小汉明重为$t+1$ ,当且仅当线性方程组$HX=0$的任意解的非零分量数不低于$t+1$ ,并且可以取到$t+1$ 。而这就当且仅当$H$的任意$t$列线性无关,且存在$t+1$ 列线性相关。

错误图样&最小距离译码规则

设输入$x^n=(x_1,\cdots ,x_n)$,输出$y^n=(y_1,\cdots ,y_n)$ 。如果 $y^n$ 适合$y^{n_k}{H}^{\prime }=0$ ,那么我们就认为输入的码字就是$y^{n_k}$ (当然这其实也不一定，但是信道恰好把一个码字变为另一个码字的概率也不是很大);而如果$y^n{H}^{\prime }\ne 0$ ,那说明传输一定发生了错误。

定义一个向量$E:=(e_1,\cdots ,e_n)$ ,其中如果第官位发生错误，就令 $e_{i_i}=1$,否则令$e_i=0$ 。于是有$y^n=x^n+E$ (时刻不要忘记我们是在二元域上讨论的，这也是二元域加法定义的好处)。记$S=y^{r_k}{H}^{\prime }$,则$S=(x^n+E)H^{\prime }=E{H}^{\prime }$ ,即$S$是一个只与发生错误的位置有关的向量，称为监督子，校验子或伴随式，$E$称为错误图样。

不过即使如此，不同的错误图样仍然有可能诱导出不同的伴随子，究其原因，$S=E{H}^{\prime }$式取转置即得$H{E}^{\prime }=S$ ,而$H$的列数肯定大于行数，因此解必不唯一。

于是需要给出一种译码规则，把$y^{x_k}$映到一个码字。这就是最小距离译码规则：我们选择使得$d(x^n,y^n)$达到最小的那个$x^n\in$Im$G^{\prime }$作为$y^n$的译码。这是为什么呢？
因为假设每个字母翻译错的概率为$p$ ,那么结合实际来看，$p$是个很小的数。计算可知，恰好传输错$t$位的概率为$p^t(1-p{)}^{n-t}$ ,有
$$p^1(1-p{)}^{n-1}>>p^2(1-p{)}^{n-2}>>\cdots >>p^t(1-p{)}^{n-t}>>\cdots$$

所以传输过程中错的位数应该很少，错得越少的概率越大。因此我们就选那个与$y^n$相差位数最少的码字作为译码结果。

检错纠错能力与最小汉明重量

对于最小汉明重为$d$的$(n,k)$线性码，
(1)若$d=2e+1$ ,则该码能纠正$e$个错误；
(2)若$d=l+1$ ,则该码能检测$l$个错误；
(3)若$d=e+l+1(e<l)$ ,则该码能在纠正$e$个错误的同时检测$l$个错误。

证明
(1)设输入$x^n=(x_1,\cdots ,x_n)$,输出$y^n=(y_1,\cdots ,y_n)$,假设发生了$e$ 个错误，即$d(x^n,y^n)=e$ ,又对任意其他码字$z$ ,$d(x,z)\ge d=2e+1$ 。从而由三角不等式得： $d(y^n,z^n)\ge e+1>e=d(x^n,y^n)$ ,从而根据最小距离译码规则必把$y^n$译为$x^n$ 。

(2)假设发生了$l$个错误，则$d(x^n,y^n)=l$ 。而对任意码字$z$ ,$d(x^n,z)\ge l+1$ ,于是立即知道$y^n$不是码字，这就发现了错误。

(3)结合(1)(2)即得。