纠错入门
引言
纠错算法有着广泛的应用。以固态硬盘为例，受温度、制作工艺等影响，数据出错不可避免，因此都会有纠错机制（Error Correcting Code，简称ECC）用于“保护”数据。对于不容易出错的 SLC，可以用汉明码；随着MLC、TLC的普及，对于纠错有着更高的需求，用的是BCH 和 LDPC算法。
本文介绍纠错算法的入门内容：重复编码和汉明码，以及汉明码的原理。
重复编码
最简单的纠错方法是重复，将同一个信息重复多遍，在接受信息后，通过“多数投票法”还原出原始信息。
例如：
原始信息： 0 0 1 0 1
重复编码： 000 000 111 000 111
接收到的信息：001 100 111 010 110
解码结果：0 0 1 0 1，与原始信息一致。
但是，会有纠不回错误的时候，例如：
原始信息： 0 0 1 0 1
重复编码： 000 000 111 000 111
接受到的信息：001 110 111 010 000
解码得到：0 1 1 0 0，与原始信息不同。
观察可知，出错的原因在于信息转输过程中出现了 2 bits 或者 3 bits 翻转。
"2 out of 3"的重复编码，有着两个明显的缺点：
每 3 bit 仅允许出现 1 bit 翻转
传输效率低，传输效率是 有效数据1bit / 总数据3bit = 33%
有没有更高效率的纠错机制呢，例如能达到 50% 70% 甚至 90%呢？再者，如果已知信息传输过程中不会出现过多错误呢，例如每 100 bits 仅出现1 bit 错误?
汉明码
汉明码（Hamming Code）是一种更高效的纠错编码方法，可以将 4 bits 的信息编码成 7 bits，效率为 4/7 = 57.1%。
输入：4 bits 信息，本文用 abcd 表示。
模型：
输出： 4 bits 数据 + 3 bits 校验位共 7 bits，本文用 abcdxyz 表示。
可以这样理解异或运算 ⊕：和为偶数，结果为0；和为奇数，结果为1。
三者相加也是同理，例如 1+1+1=3，3是奇数，因此 1⊕1⊕1=1。
4 bits 信息：abcd 对应 1101
1+1+1=3，为奇数，则 x=a⊕b⊕d=1 1+0+1=2，为偶数，则 y=a⊕c⊕d=0 1+0+1=2，为偶数，则 z=b⊕c⊕d=0
得到编码结果为：1101100
原始信息：abcd
编码信息：abcd xyz
接受信息：0100 101。
解码信息：根据接受到的信息前四位，我们推测出x y z 应为 101，与接受到的信息后三位一致，说明这 7 bits 很大概率在传输过程没有发生 bit 翻转。 推测原始信息 abcd 是 0100。
假设接受到的信息是 1001 010。根据前四位，我们推测出xyz 应为 0 0 1，与后三位不符合，说明至少有 1 bit 在传输过程中出现了翻转。
那如何纠正呢？
这 3 bits 校验数据中，x是相符的，y和z是不相符的；
又因为y=a⊕c⊕d,z=b⊕c⊕d 这两个式子都包括 c 和 d，说明 c 或 d 有一个出错了；
x=a⊕b⊕d 中包括 d，说明 d 没有出错；
推出是 c 在数据传输过程中翻转了，因此解码得到原始信息是 1011。
与重复编码相似，汉明码也不能纠正 2 bits 翻转的情况。例如：
原始信息：0100
编码信息：0100 101
接受信息：0110 001
解码信息：0111，与原始信息不同
重复编码和汉明码的对比表：
名称 | Efficiency | 纠错效果 |
|---|---|---|
"best 2 out of 3" Repetition Code | 1/3(33%) | 1 correction per 3 bits |
Hamming(7,4) Code | 4/7(57.1%) | 1 correction per 7 bits |
汉明码原理
汉明码为何有效呢？原理是什么？
汉明码为 4 bits 的数据 abcd 添加了 3 bits 的校验位（check bits） xyz。3 bits 校验位总共可以表示 23=8 种可能性，正好可以用来表示 7-bit 数据的8种情况——没有错误、第1个比特翻转、第2个比特翻转……第7个比特翻转。如下表所示：
Check-bit states(xyz) | Error States | abcd xyz |
|---|---|---|
√√√ | No errors | √√√√ √√√ |
×√√ | x is wrong | √√√√ ×√√ |
√×√ | y is wrong | √√√√ √×√ |
√√× | z is wrong | √√√√ √√× |
××√ | a is wrong | ×√√√ √√√ |
×√× | b is wrong | √×√√ √√√ |
√×× | c is wrong | √√×√ √√√ |
××× | d is wrong | √√√× √√√ |
（第一列的 × 表示校验位不符合，第三列的 × 表示比特翻转）
这也解释了为什么汉明码只能每 7 bits 纠回 1 bit 错误。如果想纠正更多错误，需要添加更多校验位。
另外，该表格的对应顺序并不是因定的，只是按照通用的表示。
校验位xyz | Error State |
|---|---|
××√ | a is wrong |
×√× | b is wrong |
√×× | c is wrong |
××× | d is wrong |
在这种对应关系下，校验位 x 与 数据 a b d有关，可以构建出公式：
x=a⊕b⊕d
例如: 1010 1__，如果 a b d 中有一位在传输过程中出错，那解码得到的 x 均为0，即
a 出错：0010 0__
b 出错：1110 0__
d 出错：1011 0__
也就是说，如果知道 x 是错误的，可说明 a 或 b 或 d 出错了。
同理，可以写出 y=a⊕c⊕d,z=b⊕c⊕d