线性码

本文是 https://youtu.be/kO6UlCY6idg?si=YRKOIPThcXF6lyvs 的笔记，内容包括：

• 生成矩阵 Generator Matrix G

• 最小汉明距离 Minimum Distance d

• 奇偶校验矩阵 Parity-Check Matrix H

生成矩阵

"Best 2 out of 3" Repetition Code 是将数据从一维变换成三维：

• 0 -> 000

• 1 -> 111

在这个三维空间中，000 和 111 被视为有效字码（valid code），其它如：001, 100, 010, 101, 110, 011等则是无效字码（invalid code）。当接受到的数据是这些无效字码时，说明传输过程中出现了比特翻转。

可视化如下：

解码过程，就是找离无效字码最近的有效字码。例如，当接受到 001 时，找到最近的有效字码是 000；接受到 110 时，找到最近的有效字码是 111。

重复编码的生成矩阵（Generator Matrix G）是 [1 1 1]：

0[1 1 1]−>[0 0 0] 1[1 1 1]−>[1 1 1]

"Hamming (7,4) Code" 是将数据从四维变换成七维，例如，

• 0010 -> 0010011

• 1100 -> 1100011

在这个七维空间中，有 128 个 codewords，其中仅有16个是有效字码（valid code），在下表蓝色高亮的部分。

七维空间的可视化如下图，右侧的红点表示的是有效字码：

汉明码是将输入的数据位 [a b c d] 编码为 [a b c d x y z]，用生成矩阵表示如下：

矩阵的前四列是 Identity Matrix，作用是复制 abcd；后三列负责生成校验位，倒数第三列对应 x=a⊕b⊕d，倒数第二列对应 y=a⊕c⊕d，最后一列对应 z=b⊕c⊕d，

汉明码生成矩阵示例，Message 是 1101：

最小距离

Hamming Weight w(⋅)

编码数据（codeword）中非零的个数，在二进制中也就是 1 的个数。（The number of non-zero digits in a codeword(# of 1s)）

例如，w(00110)=2,w(111)=3,w(0001)=1

Hamming Distance D(⋅,⋅)

两个字码之间不同的比特个数。（The number of digits where two codewords differ）

例如，D(000,111)=3，3个bit都不同。从几何视角看距离是3：

D(00110,00111)=1，第 5 个 bit 不同。

D(0000,1001)=2，第 1 和第 4 个 bit 不同。

D(c,00000)=w(c)，上面说过汉明权重 w(c) 是 codeword 中所有非 0 的个数；即有效字码与全 0 字码的汉明距离是该有效字码的汉明权重。

Minimum Distance d

任意两个有效字码间最小的汉明距离（Smallest Hamming distance between any two (valid) codewords），数学公式表示为 c⃗1​,c⃗2​min​D(c⃗1​−c⃗1​,c⃗2​−c⃗1​)

"Best 2 out of 3" Repetition Code

Generator Matrix：[1 1 1]

"Best 2 out of 3" Repetition Code 只有 000 和 111，则其最小汉明距离是 3。

Generator Matrix：

（这个矩阵的作用：前2位取第1个bit，后2位取第2个bit）

通过一一比较汉明距离得出，最小汉明距离：d=2

Generator Matrix:

（这个矩阵的作用：前3位取第1个bit，最后1位取第2个bit）

通过一一比较汉明距离得出，最小汉明距离：d=1

上述两个例子的几何视角如下：

最小汉明距离可以让我们知道在传输过程中允许有多少个bit翻转：知道 d，可检测出错个数是 d−1 ，可纠回出错个数是 [2d−1​]。

具体见下表，c1 和 c2 表示有效字码，两个圆圈中的一条横线表示 1 个 bit 翻转：

1. d=1，无法检测到错误，也无法纠错。例如，c1=0,c2=1；在接受端，如果接受到的数据是 0，无法判断接受到的数据是否正确。

2. d=2，可以检测到出现 1 个错误，但无法纠错。例如，将 0 或 1 重复编码 2 次，c1=00,c2=11；在接受端，如果接受到的数据是 10 或 01，我们可以肯定数据传输过程中出现了 1 个错误，但无法确定是原先的数据是 0 还是 1。

3. d=3，可以检测到出现 2 个错误，可纠错 1 个bit。例如，将 0 或 1 重复编码 3 次, c1=000,c2=111；在接受端，如果接受到的数据是 001，我们可以确定该数据在传输过程中出现了翻转，可能是 1 bit 出错或 2 bit 出错；假设仅有 1 个 bit 翻转，那么可解码得到原先的数据是 0，也就纠回了 1 bit 的错误。

4. 其它同理。

那汉明码的 Minimum Distance 怎么找呢？如果通过排列组合不同 Codeword 来找会非常麻烦，幸运的是有更好的方式来找。

转化过程如下：同时将两个有效字码减去同一个字码，得到最小汉明距离是 0 和 两个有效字码差值 之间的距离，

这不会改变我们需要得到的距离结果，因为通过减去一个字码，我们实际上只是将有效字码在空间中滑动，而不会改变它们之间的距离。（by subtracting a code word we're basically just sliding valid codewords over in space without changing the distance between them）

又因为：

1. 线性码（Linear Codes）规定任何两个有效字码相加仍然是有效字码（Sum of any two valid codewords is another valid codeword）

2. 前文提到有效字码与全 0 字码的汉明距离是该有效字码的汉明权重 ：D(c,00000)=w(c)

所以：

因此，通过得到所有字码中最小的汉明权重，我们可以得到需要的最小汉明距离：d=c⃗min​w(c⃗)。

补充：线性码（Linear Codes）规定任何两个有效字码相加仍然是有效字码。

"Hamming (7,4) Code" ，字码中 1 个数最少为 3，则最少汉明距离 d=3；再结合前面说过的“最小距离作用”，可知 "Hamming (7,4) Code" 能够纠错 [2d−1​]=1 bit的错误。

校验矩阵

为了纠错，我们需要奇偶校验矩阵H：

• 如果 c 是有效字码, 那么两者相乘得 0 : HcT=0⃗。

• 反之，如果 c 是无效字码, 那么两者相乘结果非0。

"best 2 of 3" 的奇偶校验矩阵推导如下：

一、原始等式

二、右边为0

将等号右边移到等号左边得

三、异或表示

由于是二进制，减法运算等同于异或运算，

四、矩阵表示

属于 Linear Equations，用矩阵表示

Hamming (7,4) code 的奇偶校验矩阵推导如下 :

一、原始等式

二、右边为0

将等号右边移到等号左边得

三、异或表示

由于是二进制，减法运算等同于异或运算，

四、矩阵表示

属于 Linear Equations，用矩阵表示

例子：codeword c=[1 1 0 1 1 0 0]，Hc⃗T=0⃗：

c⃗T 的 1st, 2nd, 4th, 5th 为 1，表示将 H 中的 1st, 2nd, 4th, 5th 列进行相加，这4列每一行加完后都是偶数。由于我们是用异或运算 ⊕ ，加完后全为偶数表示运算后的结果为全 0 的列向量。根据定义，这说明 1101100 是有效字码。

取有效字码加上一个错误向量（error vector），就将 H 分成了两部分。与有效字码相乘的部分结果为 0，因此结果只剩下错误的部分，这个向量称为症候向量（syndrome vector）：

通过症候向量可以得出是哪个 bit 在传输过程中出现了错误。

取上述例子的有效字码 c⃗=[1 1 0 1 1 0 0]，加上一个表示 2nd 比特翻转的错误向量 e⃗=[0 1 0 0 0 0 0]。H 与 c⃗ 相乘得 [0 0 0]；H 与 e⃗ 相乘，就是取 H的 2nd 列，得到症候向量 [1 0 1]：

由于得到的结果是 H 的 2nd 列，说明是第 2 个比特在数据传输过程中出错。（后面会解释为什么）

通过上述公式推导不难看出症候向量与有效字码无关，只与错误向量有关。

用另一个有效字码 q=[0 0 1 0 0 1 1] ，加上相同的错误向量 e=[0 1 0 0 0 0 0] ，会得到相同的结果[1 0 1]，依然是 H的 2nd 列：

然而，如果是加上两个错误向量，得到的结果会将 H 对应的两个列向量相加，导致不能判断是哪个 bit 出错。

这也再一次说明了为什么汉明码仅允许 1 bit 出错。

例如，加上两个错误向量[0 0 0 0 1 0 0] 和 [0 0 0 0 0 1 0]，其结果就是将H 的5th 和 6th 列向量相加，得到 H的 1st 列向量。在接受端会误以为是 1st bit 在数据传输过程中出现了错误，没有起到纠错效果：

前文“汉明码原理”中 提过：

将该表进行翻转，并去掉没有出错的行，如下图右侧所示。可以看到 7 个状态与 H 的 7 列完美对应起来（× 与 1 对应，√ 与 0 对应）：

1. 1st 比特出错用 ××√ 表示，正好对应 H的 1st 列[1 1 0]

2. 2st 比特出错用 ×√× 表示，正好对应 H的 2nd 列 [1 0 1]

3. 以此类推

也就是说，按顺序排列这些错误状态对应的症候向量，可得到奇偶校验矩阵：

通过奇偶校验矩阵H还可以得到最小汉明距离 d。

前面提过：d=c⃗min​w(c⃗)，“找最小汉明距离d”可以转换成“找有效字码 c 中 1 的个数最少是多少”。

又因为H 与 有效字码 c⃗T 相乘得 0，我们可以将“找最小汉明距离d”转换成 "c 中 1 最少是多少才能让Hc⃗T=0"

1. c仅有 1 个 1 不能得到 Hc⃗T=0，除非 H 中有一列为全 0。

2. c仅有 2 个 1 不能得到Hc⃗T=0，除非 H 中有两列是重复的，才能让两个列向量相加得 0。

3. c 有 3 个 1 可以得到 Hc⃗T=0，将H中的 2st、5th、7th 列向量相加可以得0 。

则c 中 1 最少是 3 才能让Hc⃗T=0，这再一次说明 d=3。

一般汉明码

一般汉明码（General Hamming Codes）有以下特点：

1. 奇偶检验矩阵 H 的所有列是 0 和 1 的所有可能组合（除了全 0）

2. H 有 r 行和 2r−1列

3. H 中的 r 列向量用于校验位

Hamming (7,4) code，为 4 bit 数据 abcd 添加 3 bit 校验位 xyz，编码成 abcdxyz，奇偶校验矩阵 H是：

1. H 是 3 行 7=23−1 列矩阵

2. 前 4 列用于复制数据 abcd，后 3 列用于校验位 xyz。这 3 列向量每列仅有 1 个 1。

将这个矩阵的顺序重新排列，可得：

观察这个矩阵发现，

1. 从最左边的列向量往右，刚好对应十进制的 1~7。

2. 对应的顺序有了变化，x 对应 1st 列，y 对应 2nd 列，z 对应 4th 列（刚好是 20,21,22）。

令 r=4，可以得到 Hamming (15, 11) code。这种编码方式为 11 bit 数据 abcdefghijk 添加 4 bit 校验位 xyzw，编码成 abcdefghijkxyzw， H 是：

1. 从左往右列向量对应十进制的 1~15

2. x 对应 1st 列，y 对应 2nd 列，z 对应 4th 列， z 对应 8th 列。这 4 列向量每列仅有 1 个 1。

行视角看，校验矩阵每一行对应一条公式：