线性分组码
线性分组码，有两个特点，一个是线性，一个是分组。线性是指校验位和数据位成线性关系，可以通过线性方程直接求得。分组是指校验位由当前码组的数据位唯一确定。比如（n，k）线性分组码，指码长为n，数据位为k的编码方案。汉明码是线性分组码中的一种。
- 发送方生成码组
- 接收方破译码组
- 生成矩阵和校验矩阵
- 码组形式：k bit数据位+r bit校验位，这样的码被称为系统码。
- 重点在第三部分生成矩阵和校验矩阵。
- 我这里说的数据位，也被称为信息位。
（1）发送方生成码组
n=k+r。数据位为k位，冗余的校验位为r位。满足
2
r
≥
k
+
r
+
1
\Large 2^r \ge k+r+1
2r≥k+r+1。
用k bit数据组成的行向量矩阵m乘以生成矩阵G，即得码组c。
c
1
×
n
=
m
1
×
k
×
G
k
×
n
c_{1\times n} = m_{1\times k}\times G_{k\times n}
c1×n=m1×k×Gk×n
（2）接收方破译码组
将接受到的码组c和校验矩阵H相乘，如果得到0向量，则说明收到的是正确的。
或者，将所有错误情况列举出来查表。
（3）生成矩阵和校验矩阵
一般教科书里面会先讲校验矩阵，再讲生成矩阵，我也准备这样写，但为什么这样写呢？
这要从信道编码出现的原因讲起。信源编码是降冗余，是想要传输速率一定的情况下，发出去更多的符号；信道编码是加冗余，是想要在信道干扰条件一定的情况下，送出去更多的可靠的符号。比如信息位是4位，添加了3位的冗余，那么携带信息的码字有16种，而7比特总共有128种码字。这多出来的的就是112种，就是被禁用的。
而在这128种情况里面，一定有和16种携带信息的向量正交的。我们选出三种线性无关的禁用码字，用来当作校验矩阵。从定义都可以知道，校验矩阵和许用码字的矩阵相乘的结果是一个零向量。那么我们就可以用这个来进行校验。
由线性代数的知识，我们对校验矩阵进行行初等变换，其校验结果是不变的。那么我们就可以把校验矩阵变换成特殊形式，然后就可以轻松降校验矩阵转换为生成矩阵。用生成矩阵生成的码字就可以用校验矩阵进行校验了。
上面的理论显然是非常抽象且枯燥的，现在我举一个例子，（7，4）汉明码。
-
校验矩阵：它的特点是，从左到右分别是1～7的二进制表示。
H
=
[
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
]
H = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}
H=⎣⎡001010011100101110111⎦⎤
-
对上述校验矩阵进行行初等变换，将靠右的部分变为单位阵。
H
=
[
0
1
1
1
1
0
0
1
0
1
1
0
1
0
1
1
0
1
0
0
1
]
=
[
P
,
I
r
×
r
]
H = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1\end{bmatrix} = [P,I_{r\times r}]
H=⎣⎡011101110111100010001⎦⎤=[P,Ir×r]
-
然后得到生成矩阵，生成系统码形式的汉明码的生成矩阵
G
=
[
I
k
×
k
;
P
T
]
=
[
1
0
0
0
0
1
1
0
1
0
0
1
0
1
0
0
1
0
1
1
0
0
0
0
1
1
1
1
]
G = [I_{k\times k};P^T] = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{bmatrix}
G=[Ik×k;PT]=⎣⎢⎢⎡1000010000100001011110111101⎦⎥⎥⎤
- 生成汉明码：
m
=
[
1
,
0
,
1
,
0
]
;
c
=
m
G
=
[
1
,
0
,
1
,
0
,
1
,
0
,
1
]
m = [1,0,1,0] ;c = mG = [1,0,1,0,1,0,1]
m=[1,0,1,0];c=mG=[1,0,1,0,1,0,1]
- 校验：$s = Hc^T = [0;0;0] $
s被称为伴随式。
变换前后的最小汉明距离不变。
贴一段我用来测试上述过程的代码。
import numpy as np
import itertools as it
G = np.array([[1,0,0,0,0,1,1],
[0,1,0,0,1,0,1],
[0,0,1,0,1,1,0],
[0,0,0,1,1,1,1]])
H = np.array([[0,1,1,1,1,0,0],
[1,0,1,1,0,1,0],
[1,1,0,1,0,0,1]])
s = list(it.product(range(2), repeat=4))
M = np.array(s)
C = np.matmul(M,G)%2
D = []
for c in C:
tmp = []
for other_c in C:
if (c!=other_c).any():
tmp.append(sum((c+other_c)%2))
D.append(np.min(tmp))
print("最小汉明距离:",np.min(D))
