介绍
| 算法 | 校验位大小 | 特点 | 功能 |
|---|---|---|---|
| 汉明码（Hamming Code） | 1个 | 算法简单 | 检测并修正单个位错误；检测双位错误，但不能修正 |
| 里德-所罗门码（Reed-Solomon Code） | 多个（取决于配置） | 强大的纠错能力，广泛用于CD和DVD、无线通信和卫星通信 | 纠正多个错误。特别擅长突发错误（就是错误集中在较小的区域） |
| 奇偶校验码（Parity Code） | 1个 | 算法最简单 | 只能检测奇数个位的错误，无法纠错 |
| 循环冗余校验（Cyclic Redundancy Check, CRC） | 多个（取决于CRC多项式长度） | 检测随机改变 | 检测数据传输或存储中的错误 |
| 卷积码（Convolutional Code） | 取决于码率和约束长度 | 用于无线通信 | 错误校正用于连续位流 |
| 涡轮码（Turbo Code） | 取决于码率和内部组件 | 高效率 | 广泛应用于深空通信和移动通信 |
| LDPC码（Low-Density Parity-Check Code） | 多个（取决于配置） | 接近香农极限 | 用于高速数据传输和数据广播 |
| BCH码（Bose-Chaudhuri-Hocquenghem Code） | 多个（取决于配置） | 多位错误修正 | 适用于控制系统和卫星通信 |
| 极化码（Polar Code） | 取决于码率和长度 | 实现香农极限的一种方法 | 5G通信标准的控制信道编码 |
| 字符校验和（Checksum） | 可变 | 简单检测 | 检测数据包或文件的完整性 |
分类
- Erasure 擦除码。
- 功能：若干数据丢失。或者若干数据错误，但知道是哪些数据错误（其实是一回事）
- 原始数据 k 组，加上校验码后为 n 组，传输过程中有丢失，只需要剩下的任意 k 组，就可以还原出结果
- 应用：传输、存储等可能会丢数据的场景
- 应用2:秘密分享，把一个秘密分享给 n 个人，要求任意 k 个人在场时能够获取秘密。
- BCH 纠错码（Error Correction Code）
- 功能：若干数据错误，但不知道具体哪些数据错误。或者有的知道有的不知道。
- 应用：QR码、信息传输
玩具级实现：多项式编码
玩具版原理：
- 3个点可以确定一条抛物线
- 再取 2 个点，总共 5 个点
- 任意丢失5个点中的 2 个点，剩余的 3 个点就可以还原整个抛物线，从而还原出全部 5 个点
假设要传输的是 k 个数字 $d_i$，加上校验码后为 n 个数字 $c_i$
- 可以确定一个 k - 1 次的多项式 $f(x) = d_0 + d_1 x + d_2 x^2 + … + d_{k-1} x^{k-1}$
- 用 n 个数字代入上面的多项式，可以得到 n 对坐标：$(0, c_0), (1, c_1), …, (n, c_n)$
- 传输 $c_0, c_1, … ,c_n$ ，如果发生数据丢失，只剩下 k 个数据，仍然可以还原得到多项式，从而得到原始数据
用矩阵表示上面的过程（假设 $k=6, n=9$）
\[\left ( \begin{array}{l} c_0\\ c_1\\ c_2\\ c_3\\ c_4\\ c_5\\ c_6\\ c_7\\ c_8 \end{array} \right )= \left ( \begin{array}{l} 1 & 0^1 & 0^2 & 0^3 & 0^4 & 0^5 \\ 1 & 1^1 & 1^2 & 1^3 & 1^4 & 1^5 \\ 1 & 2^1 & 2^2 & 2^3 & 2^4 & 2^5 \\ 1 & 3^1 & 3^2 & 3^3 & 3^4 & 3^5 \\ 1 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 \\ 1 & 5^1 & 5^2 & 5^3 & 5^4 & 5^5 \\ 1 & 6^1 & 6^2 & 6^3 & 6^4 & 6^5 \\ 1 & 7^1 & 7^2 & 7^3 & 7^4 & 7^5 \\ 1 & 8^1 & 8^2 & 8^3 & 8^4 & 8^5 \\ \end{array}\right) \left ( \begin{array}{l} d_0\\ d_1\\ d_2\\ d_3\\ d_4\\ d_5 \end{array} \right )\]玩具版 python 实现
下面的代码，假设原始数据是 6 个(d)，传输 9 个数据(c)，传输过程中丢失了 3 个数据
import numpy as np
k = 6 # 6个原始数据
n = 9 # 加上校验码共 9 个数据
d = np.array([1, 4, 6, 3, 2, 2]).reshape(-1, 1)
print("原始数据", d.flatten())
V = np.vander(np.arange(n), N=k, increasing=True)
def encode(d, k, n):
c = V @ d
return c
c = encode(d, k, n)
print("带校验码的数据:", c.flatten())
# 假设丢了3个：序号 [0, 4, 8] 对应的数据丢失
loss_idx = [0, 4, 8]
c[loss_idx, :] = -1
print("传输后丢失：", c.flatten())
def reconstruct(c, k, n):
valid_idx = [i for i in range(n) if i not in loss_idx]
c1 = c[valid_idx, :]
V1 = V[valid_idx, :]
d_recover = np.linalg.solve(V1, c1.flatten())
return d_recover
d_recover = reconstruct(c, k, n)
print("擦除码还原后的数据：", d_recover)
运行结果：
原始数据 [1 4 6 3 2 2]
带校验码的数据: [ 1 18 153 796 2865 8046 19033 39768 75681]
传输后丢失： [ -1 18 153 796 -1 8046 19033 39768 -1]
擦除码还原后的数据： [1. 4. 6. 3. 2. 2.]
工业级实现：Reed-Solomon
实际应用中，还需要解决如下问题
- 如何保证丢失数据后，使用任意 k 个数据都能获取原始数据。这等价于：保证任选 k 个方程组，都会有解，并且有唯一解。这需要保证矩阵满秩，比如上面选取取自增自然数对应的 Vandermonde 矩阵。
- 编码后不希望获得大整数，解码后不希望获得浮点数。
- 编码前、编码后，都希望都是字节（也就是范围是 0-255 之间的整数），这就需要用到 Finite Field(也就是 Galois Filed)
- 如果数据没有丢失，如何跳过计算复杂度较高的解码步骤
- 最理想的办法：原始数据 d(k个)，与编码后的数据 c（n个）的前 k 个，完全一样。这样如果前 k 个不丢失，那么就直接是原始数据了。
1960 年提出的 Reed-Solomon 编码可以解决以上问题
引入知识1：伽罗瓦域
Galois Field 也称为有限域，有 p^n 个元素的 Galois Field 记作 ( GF(p^n) )
（相关知识，参见 群、环、域）
假设这个域是定义在 uint8 上的，也就是 GF(2^8) 它有一些性质：
- $x \oplus y = x - y = x \mathrm {XOR} y$，因此满足了加法的交换律和结合律
- $x \oplus x = 0$，也就是每个元素都有对应的加法逆元
- $x \otimes y = \exp [\log[x] + \log[y]]$
Reed-Solomon 算法中，超参数可以这样选取：
- primitive element（本原元）取 $\alpha=2$，
- irreducible polynomial（不可约等多项式）取 0x11d（也就是 $x^8+x^4+x^3+x+1$，当 x=2时的值）
在这个定义下有这些性质
- $x \otimes 2 = (x«1)\mathrm {XOR} ((x \& 0x80)?0x1d:0)$
- $x^0 = 1$
- 用上面两个可以计算出所有的 $2^k$，计算得知 $2^0 = 2^{255} = 1$，因此 $2^k$ 是周期函数，进而可以实现计算出一个 exp 表，用于快速做 exp 计算.
- 经过计算 $2^k (k=0,1,…,254)$ 对应的 255个数字，正好也是 1-255 这 255 个数字
- 因此，还可以用对应关系计算出一个 log 表，用于快速计算。做 log 计算
使用以上方法，可以保证乘法运算和加法运算封闭在 u8 范围内，从而矩阵积的结果在 u8 范围内。这就解决了上面提出的一个问题：编码后不希望出现大整数，而是在 u8 范围内；解码时不希望出现浮点数，也是在 u8 范围内。
- vandermonde 矩阵可以有多种类型，因此 Reed-Solomon 算法可能有很多种。
- 选取 vandermonde 矩阵，是因为它是线性无关的
引入知识2：系统码
接上面，引入伽罗瓦域后，可以保证运算之后的结果封闭在 u8 范围内。本部分解决之前提出的另一个问题：想办法把编码后的数据的前 k 行，与原始数据一样。
上面的想法用符号表示是：
\[\left ( \begin{array}{l} d_0\\ d_1\\ d_2\\ d_3\\ d_4\\ d_5\\ c_6\\ c_7\\ c_8 \end{array} \right )= \left ( \begin{array}{l} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ g_{00} & g_{01} & g_{02} & g_{03} & g_{04} & g_{05} \\ g_{10} & g_{11} & g_{12} & g_{13} & g_{14} & g_{15} \\ g_{20} & g_{21} & g_{22} & g_{23} & g_{24} & g_{25} \end{array}\right) \left ( \begin{array}{l} d_0\\ d_1\\ d_2\\ d_3\\ d_4\\ d_5 \end{array} \right )\]用分块矩阵表示：
\[\left [ \begin{array}{l} d\\ c \end{array} \right ]= \left [ \begin{array}{l} I_k \\ G \end{array}\right] d\]也就是 $c=G\cdot d$，传输过程中传的就是 $[d\mid c]$
问题变成了这个：
如果寻找一个矩阵 $A_{n\times k}$，其任意 k 行是线性无关的，并且其上部是单位矩阵。
我们的思路是从上面的 Vandermonde 矩阵开始构造，因为 Vandermonde 矩阵本身满足“任意 k 行线性无关”，
根据线性代数知识，以下方法是等价的
- 办法1: $A_{n\times k}=V_{n\times k} \cdot V_{k\times k}^{-1}$
- 办法2:做增广矩阵，用高斯消元，求矩阵的逆
- 办法3:初等列变换。（我的代码里面这么做）
- 办法4:vandermonde 矩阵特殊，有特殊的求逆的方法，复杂度为 $O(n^2)$（一般矩阵求逆复杂度为 $O(n^3)$）
encode
有了以上两个理论推导，encode 算法就很容易写了
- 写一套 Galois Field 的计算规则
- 在这个域上生成一个 $n\times k$ 的 vandermonde 矩阵
- 使用高斯消元法（初等列变换），把 vandermonde 矩阵上部变成单位矩阵，从而得到 一个 $k\times k$ 的单位矩阵，以及下部的矩阵 $G_{(n-k)\times k}$，用矩阵表示（下面的箭头表示初等列变换）：
\(\left ( \begin{array}{l} 1 & 0^1 & 0^2 & 0^3 & 0^4 & 0^5 \\ 1 & 1^1 & 1^2 & 1^3 & 1^4 & 1^5 \\ 1 & 2^1 & 2^2 & 2^3 & 2^4 & 2^5 \\ 1 & 3^1 & 3^2 & 3^3 & 3^4 & 3^5 \\ 1 & 4^1 & 4^2 & 4^3 & 4^4 & 4^5 \\ 1 & 5^1 & 5^2 & 5^3 & 5^4 & 5^5 \\ 1 & 6^1 & 6^2 & 6^3 & 6^4 & 6^5 \\ 1 & 7^1 & 7^2 & 7^3 & 7^4 & 7^5 \\ 1 & 8^1 & 8^2 & 8^3 & 8^4 & 8^5 \\ \end{array}\right) \Rightarrow \left ( \begin{array}{l} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ g_{00} & g_{01} & g_{02} & g_{03} & g_{04} & g_{05} \\ g_{10} & g_{11} & g_{12} & g_{13} & g_{14} & g_{15} \\ g_{20} & g_{21} & g_{22} & g_{23} & g_{24} & g_{25} \end{array}\right)\) -
encode 算法：用矩阵点积得到 $c=G\cdot m$，用矩阵表示：
\(\left ( \begin{array}{l} c_6\\ c_7\\ c_8 \end{array} \right )= \left ( \begin{array}{l} g_{00} & g_{01} & g_{02} & g_{03} & g_{04} & g_{05} \\ g_{10} & g_{11} & g_{12} & g_{13} & g_{14} & g_{15} \\ g_{20} & g_{21} & g_{22} & g_{23} & g_{24} & g_{25} \end{array}\right) \left ( \begin{array}{l} d_0\\ d_1\\ d_2\\ d_3\\ d_4\\ d_5 \end{array} \right )\) - 返回 $[d\mid c]$
decode
如果数据区域没有丢失，那么就不需要计算，直接返回。
如果数据区域丢失，列算式：
假设丢失了3个： $d_2, d_3, c_7$，那么：
\[\left ( \begin{array}{l} d_0\\ d_1\\ ??\\ ??\\ d_4\\ d_5\\ c_6\\ ??\\ c_8 \end{array} \right )= \left ( \begin{array}{l} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ g_{00} & g_{01} & g_{02} & g_{03} & g_{04} & g_{05} \\ g_{10} & g_{11} & g_{12} & g_{13} & g_{14} & g_{15} \\ g_{20} & g_{21} & g_{22} & g_{23} & g_{24} & g_{25} \end{array}\right) \left ( \begin{array}{l} d_0\\ d_1\\ d_2\\ d_3\\ d_4\\ d_5 \end{array} \right )\]根据矩阵积计算的性质，可以把未知的行删掉，得到：
\[\left ( \begin{array}{l} d_0\\ d_1\\ d_4\\ d_5\\ c_6\\ c_8 \end{array} \right )= \left ( \begin{array}{l} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ g_{00} & g_{01} & g_{02} & g_{03} & g_{04} & g_{05} \\ g_{20} & g_{21} & g_{22} & g_{23} & g_{24} & g_{25} \end{array}\right) \left ( \begin{array}{l} d_0\\ d_1\\ d_2\\ d_3\\ d_4\\ d_5 \end{array} \right )\]从而计算出结果：
\[\left ( \begin{array}{l} d_0\\ d_1\\ d_2\\ d_3\\ d_4\\ d_5 \end{array} \right ) = \left ( \begin{array}{l} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ g_{00} & g_{01} & g_{02} & g_{03} & g_{04} & g_{05} \\ g_{20} & g_{21} & g_{22} & g_{23} & g_{24} & g_{25} \end{array}\right) ^{-1} \left ( \begin{array}{l} d_0\\ d_1\\ d_4\\ d_5\\ c_6\\ c_8 \end{array} \right )\]如何计算上面矩阵的逆呢？
- 根据前面的推导，矩阵 V 任选 k 行必然是线性无关的，因此上面的矩阵（记为 $B $）也必然有逆矩阵
- 对增广矩阵 $[B\mid I]$ 做初等行变换，得到 $[I \mid B^{-1}]$
然后是 decode 过程：
- $d=B^{-1} m’$
block
以上已经实现了擦除码，但还不能在工业界落地。这是因为实际上的数据量较大。因此需要做一个小设计
举例来说我们要对一个字符串 "github.com/guofei9987" 做编码（假设这个字符串很长），那么我们这样编码（下面选取列数为4，实际上可以任意选取）（不够的补0）
encode 阶段：
\[\left ( \begin{array}{l} c_{00} & c_{01} & c_{02} & c_{03} \\ c_{10} & c_{11} & c_{12} & c_{13} \\ c_{20} & c_{21} & c_{22} & c_{23} \end{array} \right )= \left ( \begin{array}{l} g_{00} & g_{01} & g_{02} & g_{03} & g_{04} & g_{05} \\ g_{10} & g_{11} & g_{12} & g_{13} & g_{14} & g_{15} \\ g_{20} & g_{21} & g_{22} & g_{23} & g_{24} & g_{25} \end{array}\right) \left ( \begin{array}{l} 'g' & 'i' & 't' & 'h'\\ 'u' & 'b' & '.' & 'c'\\ 'o' & 'm' & '/' & 'g'\\ 'u' & 'o' & 'f' & 'e'\\ 'i' & '9' & '9' & '8'\\ '7' & '0' & '0' & '0' \end{array}\right)\]最终获得带擦除码的数据：
\[\left ( \begin{array}{l} 'g' & 'i' & 't' & 'h'\\ 'u' & 'b' & '.' & 'c'\\ 'o' & 'm' & '/' & 'g'\\ 'u' & 'o' & 'f' & 'e'\\ 'i' & '9' & '9' & '8'\\ '7' & '0' & '0' & '0'\\ c_{00} & c_{01} & c_{02} & c_{03} \\ c_{10} & c_{11} & c_{12} & c_{13} \\ c_{20} & c_{21} & c_{22} & c_{23} \end{array} \right )\]decode 阶段
参考上面的 decode 部分，同样写成矩阵形式，同样假设 2、3、7 行丢失
\[\left ( \begin{array}{l} d_{00} & d_{01} & d_{02} & d_{03} & d_{04} \\ d_{10} & d_{11} & d_{12} & d_{13} & d_{14} \\ d_{20} & d_{21} & d_{22} & d_{23} & d_{24} \\ d_{30} & d_{31} & d_{32} & d_{33} & d_{34} \\ d_{40} & d_{41} & d_{42} & d_{43} & d_{44} \\ d_{50} & d_{51} & d_{52} & d_{53} & d_{54} \end{array} \right ) = \left ( \begin{array}{l} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ g_{00} & g_{01} & g_{02} & g_{03} & g_{04} & g_{05} \\ g_{20} & g_{21} & g_{22} & g_{23} & g_{24} & g_{25} \end{array}\right) ^{-1} \left ( \begin{array}{l} d_{00} & d_{01} & d_{02} & d_{03} & d_{04} \\ d_{10} & d_{11} & d_{12} & d_{13} & d_{14} \\ d_{40} & d_{41} & d_{42} & d_{43} & d_{44} \\ d_{50} & d_{51} & d_{52} & d_{53} & d_{54} \\ c_{00} & c_{01} & c_{02} & c_{03} & c_{04} \\ c_{20} & c_{21} & c_{22} & c_{23} & c_{24} \\ \end{array} \right )\]参考文献
https://www.bilibili.com/video/BV1CC4y1S7CL
https://github.com/chenshuo/notes
