【擦除码】理论和实现



🗓 2024年01月20日     📁 文章归类: 0x58_密码学    

版权声明：本文作者是郭飞。转载随意，标明原文链接即可。
原文链接：https://www.guofei.site/2024/01/20/reed_solomon.html


相关文章：

关于错误

按照信道产生错误的方式，可分为：

  1. random channel 错误按照白噪声发生
  2. burst channel 错误成串集中发生。原因例如外界电火花干扰。
  3. mixed channel 两者都有

差错控制技术

  1. 检错重发。一旦检查到错误，要求发送端重发
  2. 纠错。纠错码不但能发现错误，还能恢复
  3. 反馈校验。接收端把信号原封不动发回去
  4. 跳过错误。特殊情况下才用。

介绍

算法 校验位大小 特点 功能
奇偶校验码（Parity Code） 1个 算法最简单 检测奇数个位的错误，无法纠错
方法：在数据后添加一个校验位，使二进制位1的个数为奇数（或偶数）
用途：内存、串口传输
汉明码（Hamming Code） 1个 算法简单 检测并修正单个位错误；检测双位错误，但不能修正
里德-所罗门码（Reed-Solomon Code） 多个（取决于配置） 强大的纠错能力，广泛用于CD和DVD、无线通信和卫星通信 纠正多个错误。特别擅长突发错误（就是错误集中在较小的区域）
循环冗余校验（Cyclic Redundancy Check, CRC） 多个（取决于CRC多项式长度） 检测随机改变
硬件高效实现		 检测数据传输或存储中的错误
卷积码（Convolutional Code） 取决于码率和约束长度 用于无线通信 错误校正用于连续位流
涡轮码（Turbo Code） 取决于码率和内部组件 高效率 广泛应用于深空通信和移动通信
LDPC码（Low-Density Parity-Check Code） 多个（取决于配置） 接近香农极限 广泛用于高速数据传输和数据广播，如蓝光、Wi-Fi
BCH码（Bose-Chaudhuri-Hocquenghem Code） 多个（取决于配置） 多位错误修正 适用于控制系统和卫星通信
极化码（Polar Code） 取决于码率和长度 接近香农极限 5G通信标准的控制信道编码
字符校验和（Checksum） 可变 简单检测 检测数据包或文件的完整性
TCP/IP/UDP

Reed-Solomon 有 2 个分类

  • Erasure 擦除码。
    • 功能：若干数据丢失。或者若干数据错误，但知道是哪些数据错误（其实是一回事）
    • 原始数据 k 组，加上校验码后为 n 组，传输过程中有丢失，只需要剩下的任意 k 组，就可以还原出结果
    • 应用：传输、存储等可能会丢数据的场景
    • 应用2:秘密分享，把一个秘密分享给 n 个人，要求任意 k 个人在场时能够获取秘密。
  • BCH 纠错码（Error Correction Code）
    • 功能：若干数据错误，但不知道具体哪些数据错误。或者有的知道有的不知道。
    • 应用：QR码、信息传输

checksum 实现

把所有的字节做异或，得到的结果是校验位。

  • 如果数据是类似 Vec<i32>，也可以使用加法而不是异或

异或校验：性能极高，但偶数个同位置的 bit 错误就无法检测到。

fn xor_check(msg: &[u8]) -> u8 {
    msg.iter().fold(0, |acc, &x| acc ^ x)
}

进一步，如果我们还希望定位到哪个数字有错：

  • 把数字写成 nxm 的矩阵，然后对每行每列做 checksum

checksum：性能较快。特定的模式可能绕过，但非常少见

// UDP/TCP/IP 标准 checksum 算法
pub fn checksum(data: &[u8]) -> u16 {
    let mut sum: u32 = 0; // u32 是防止溢出

    // 每2个字节组成一个 16 位整数
    let mut chunks = data.chunks_exact(2);
    for chunk in &mut chunks {
        // from_be_bytes：大端序
        let word = u16::from_be_bytes([chunk[0], chunk[1]]) as u32;
        sum += word;
    }

    // 如果是奇数长度，最后一字节补0成16位
    if let Some(&[last]) = chunks.remainder().first().map(|b| [*b]) {
        sum += (u16::from_be_bytes([last, 0])) as u32;
    }

    // 回卷进位，：把溢出的高 16 位加回来，直到没有进位为止
    while (sum >> 16) != 0 {
        sum = (sum & 0xffff) + (sum >> 16);
    }

    // 取反，符合 TCP/UDP checksum 要求
    !(sum as u16)
}

fn main() {
    let data = b"123ABCxyz";  // 任意字节流
    let sum = checksum(data);
    println!("checksum = 0x{:04x}", sum);
}

玩具级实现：多项式编码

玩具版原理：

  • 3个点可以确定一条抛物线
  • 再取 2 个点，总共 5 个点
  • 任意丢失5个点中的 2 个点，剩余的 3 个点就可以还原整个抛物线，从而还原出全部 5 个点

假设要传输的是 k 个数字 $d_i$，加上校验码后为 n 个数字 $c_i$

  1. 可以确定一个 k - 1 次的多项式 $f(x) = d_0 + d_1 x + d_2 x^2 + … + d_{k-1} x^{k-1}$
  2. 用 n 个数字代入上面的多项式，可以得到 n 对坐标：$(0, c_0), (1, c_1), …, (n, c_n)$
  3. 传输 $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

实际应用中，还需要解决如下问题

  1. 如何保证丢失数据后，使用任意 k 个数据都能获取原始数据。这等价于：保证任选 k 个方程组，都会有解，并且有唯一解。这需要保证矩阵满秩，比如上面选取取自增自然数对应的 Vandermonde 矩阵。
  2. 编码后不希望获得大整数，解码后不希望获得浮点数。
    • 编码前、编码后，都希望都是字节（也就是范围是 0-255 之间的整数），这就需要用到 Finite Field(也就是 Galois Filed)
  3. 如果数据没有丢失，如何跳过计算复杂度较高的解码步骤
    • 最理想的办法：原始数据 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 算法就很容易写了

  1. 写一套 Galois Field 的计算规则
  2. 在这个域上生成一个 $n\times k$ 的 vandermonde 矩阵
  3. 使用高斯消元法（初等列变换），把 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)\)

  4. 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 )\)

  5. 返回 $[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）

\[M= \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)\]

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

您的支持将鼓励我继续创作！