介绍

想象一下你参与了一个新的去中心化区块链，旨在链上存储大量数据——比如 NFT 艺术作品、交易历史和用户生成的档案。网络中的每个节点仅托管总账本的一部分。一些节点意外离线；其他节点可能是恶意的。直接复制每个字节多次是昂贵的，并且会减慢整个区块链的速度。

与此同时，丢失数据不是一个选项：如果关键记录消失，去中心化信任模型就会崩溃。你如何能在不淹没存储成本的情况下保持数据 高度可用？

这就是出错编码（erasure coding）大显身手的地方——将数据分割成碎片，如果被截获或丢失，每个片段都是 不可用 的，但如果你能收集到足够多的生存片段，它们是完全可重构的。与简单的复制（比如存储三份或五份备份）相比，这种方法大大降低了开销，并提供了内置的安全优势，因为没有单个片段揭示你的全部数据。

动机和文章路线图

本文深入探讨了出错编码如何工作，解释了它背后的线性代数、有限域算术、二进制矩阵优化以及其他数学基础。到最后，你将看到区块链项目、云服务以及无数其他以数据为中心的平台如何依赖数学来保护关键任务数据的安全，同时避免重复副本带来的沉重负担。

我们将讨论：

• 出错编码基础：核心定义，突显为何它优于直接复制。
• 数学基础：从柯西矩阵和矩阵乘法到使用子矩阵逆矩阵解码。
• 有限域：素数域 $GF(p)$ 和扩展域 $GF(2^n)$ 如何赋予精确、无损的算术能力。
• 二进制矩阵：将域运算翻译为基于 XOR 的高速实现。
• 实现细节：Python 中的伪代码示例，以及一些关于性能的实用建议。
• 挑战与未来方向：修复的开销、量子时代的考量等等。

让我们深入探讨。

---

出错编码基础

什么是 $[N, K]$ 出错编码？

$[N, K]$ 出错编码将原始数据转化为 $N$ 个编码片段（碎片），具有以下特性：

• 每个碎片的大小大约是原始数据的 $1/K$（不考虑小的开销）。
• 如果你丢失最多 $N - K$ 个碎片，你仍然可以从任何 $K$ 个生存碎片中恢复原始数据。

这意味着你可以获得对故障的容忍（最多 $N - K$），而无需存储多个完整副本。

下面是一个显示概念流动的图示：

flowchart LR
    A[原始数据] --> B[分割成 K 个数据块]
    B --> C[编码成 N 个碎片矩阵乘法]
    C -- 一些碎片丢失 --> D[仅 K 个碎片剩余]
    D --> E[解码子矩阵的逆矩阵]
    E --> F[重构数据]

让我们理解一下上面图示中的内容。

• 我们将数据分成 $K$ 个部分。
• 我们通过一个 $N \times K$ 的编码器矩阵进行乘法，生成 N 个碎片。
• 即使一些碎片消失，只要我们有任何 $K$ 个碎片，我们就可以解码回原始数据。

为什么它比复制更好？

• 降低成本

  • 复制：为了容忍 $F$ 次故障，你需要 $F+1$ 个完整副本（即 $(F+1) \times \text{开销}$）。
  • 出错编码：你可以使用一个 $[S, S-F]$ 的编码（其中 $S$ 是你的存储提供者的总数）。开销为 $\frac{S}{S-F}$，这对于大多数实际值的 $S$ 和 $F$ 通常小于 $F+1$。

  提供者数量 ($S$)	故障次数 ($F$)	复制开销	出错编码开销	存储节省
  4	2	3X	2X	33%
  5	2	3X	1.67X (近似)	~44%

• 增强安全性
  因为每个碎片只是一个片段，没有单个碎片（少于 $K$）揭示原始数据。这是一个内置的“信息切片”层级，可以增强你的安全姿态。

---

数学基础

线性代数基础

出错编码的核心是矩阵乘法。我们将数据块视为向量，然后与编码器矩阵进行乘法乘。以下是一些关键定义：

• 向量 $v$ 在 $\mathbb{R}^K$ 中表示为 $\begin{bmatrix}v_1 \ v_2 \ \dots \ v_K \end{bmatrix}$。
• $(N\times K)$ 矩阵 $M$ 是一个包含 $N$ 行和 $K$ 列的数组。
• 矩阵乘法：$M \cdot v$ 产生一个 $N\times 1$ 向量。

对于出错编码，我们构造一个矩阵 $E$（大小 $N\times K$）。编码后的碎片为：

$$ \text{编码} = E \times \text{数据向量}. $$

柯西矩阵：保证可逆性

更准确地说，任何矩阵都不行。我们需要任何 $K \times K$ 子矩阵在我们的选择域上是可逆的。柯西矩阵是经典选择：

$$ C_{i,j} = \frac{1}{x_i - y_j}, \quad 1 \leq i \leq N,\ 1 \leq j \leq K, $$

其中 ${x_1, \dots, x_N}$ 和 ${y_1, \dots, y_K}$ 在一个域中都是不同的元素。

• 构建

  • 选择 $N$ 个不同的值 ${x_1, \dots, x_N}$。
  • 选择 $K$ 个不同的值 ${y_1, \dots, y_K}$，它们与 $x_i$ 不重叠。
  • 用 $\frac{1}{x_i - y_j}$ 填充矩阵。

• 为什么子矩阵是可逆的
  每个 $K\times K$ 的子矩阵也是柯西矩阵（只是比大矩阵的小一点）。柯西矩阵的行列式具有一个已知的封闭形式，如果 $x_i$ 和 $y_j$ 集合是不同的，它的值 永远不为零。

简单术语中的编码/解码示例

假设 $K=2$，$N=3$。让 ${x}={1,2,4}$，${y}={0,3}$。那么，

$$ E = \begin{bmatrix} \frac{1}{1-0} & \frac{1}{1-3} \ \frac{1}{2-0} & \frac{1}{2-3} \ \frac{1}{4-0} & \frac{1}{4-3} \end{bmatrix}

\begin{bmatrix} 1 & -\tfrac{1}{2} \ \tfrac{1}{2} & -1 \ \tfrac{1}{4} & 1 \end{bmatrix}. $$

实际警告：我们最终将在一个 有限域 中进行所有算数计算，以避免浮点问题。但这个矩阵展示了结构。

• 编码：
  $$ \begin{bmatrix} \text{碎片 1}\ \text{碎片 2}\ \text{碎片 3}\end{bmatrix}

  E \times \begin{bmatrix} d_1 \ d_2 \end{bmatrix}. $$

• 解码：如果我们只有碎片 1 和 3，我们从第一行和第三行构造 $E$ 的 $2\times2$ 子矩阵，求逆，然后将其乘以 $\begin{bmatrix}\text{碎片 1}\ \text{碎片 3}\end{bmatrix}$ 以得到 $\begin{bmatrix} d_1 \ d_2 \end{bmatrix}$。

---

有限域以实现无损编码

上述分数 $\tfrac{1}{2}, \tfrac{1}{4}, \dots$ 在实际数字系统中可能导致精度问题。有时，有限域通过让每个数字成为具有 精确 模算术的一组元素来解决这个问题。

素数域 $GF(p)$

• 元素：${0, 1, 2, \dots, p-1}$。
• 在 $mod \; p$ 下进行加法和乘法。
• 逆元：元素 $a\neq0$ 总是有一个乘法逆元 $a^{-1}$，使得 $(a \times a^{-1}) \equiv 1\ (\mod p)$。

在 $GF(7)$中的示例

$GF(7)$ 的算术表（加法和乘法）：

加法（$mod \space 7$）：

+	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	2	3	4	5	6	0
2	2	3	4	5	6	0	1
3	3	4	5	6	0	1	2
4	4	5	6	0	1	2	3
5	5	6	0	1	2	3	4
6	6	0	1	2	3	4	5

乘法（$mod \space 7$）：

×	0	1	2	3	4	5	6
0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6
2	0	2	4	6	1	3	5
3	0	3	6	2	5	1	4
4	0	4	1	5	2	6	3
5	0	5	3	1	6	4	2
6	0	6	5	4	3	2	1

示例：$\tfrac{1}{2} \equiv 4\ (\mod 7)$，因为 $2 \times 4 = 8 \equiv 1\ (\mod 7)$。

扩展域 $GF(2^n)$

素数域 $GF(p)$ 对于小字母表或数值数据很好。然而，大多数现实世界数据是二进制的。$GF(2^n)$（例如 $GF(8)$、$GF(16)$、$GF(256)$ 等）通常更自然：

• 元素可以视为 $degree < n$ 的 多项式，系数在 ${0,1}$ 中。
• 算术在一个不可约多项式的 $n$ 次方下进行模运算。
• 加法是位级 XOR。

在 $GF(8) = GF(2^3)$ 中的示例

让不可约多项式为 $y^3 + y + 1$。那么每个元素是一个 3 位图案：$000$、$001$、$010$、…、$111$。

• 加法：$\oplus$（位模式上的 XOR）。
• 乘法：多个多项式的乘法，然后在 $y^3 + y + 1$ 的基础上简化。

$GF(8)$ 中乘法的具体示例

假设我们将 $\alpha = y$（表示 $010$ 的多项式）。那么：

$$ \alpha^3 = \alpha \times \alpha^2 = (y) \times (y^2) = y^3 \equiv y + 1 \quad (\text{mod } y^3 + y + 1), $$

因此 $\alpha^3 = \alpha + 1$。这个恒等式帮助计算更高的幂。

我们来直接乘法：

$$ (y^2 + y + 1) \times (y^2 + 1)\quad \text{mod } (y^3 + y +1). $$

• 多项式乘法：
  $$ (y^2 \cdot y^2) + (y^2 \cdot 1) + (y \cdot y^2) + (y \cdot 1) + (1 \cdot y^2) + (1 \cdot 1) $$ $$ = y^4 + y^2 + y^3 + y + y^2 + 1 $$ $$ = y^4 + y^3 + 2y^2 + y + 1. $$

• 因为我们在 $GF(2^3)$ 中，注意 $2y^2 = 0$（在二进制中系数 2 为 0），所以我们得到：
  $$ y^4 + y^3 + y + 1. $$

• 现在在 $y^3 + y + 1$ 的基础上简化：

  • $y^4 = y \cdot y^3 = y (y+1) = y^2 + y.$
    所以这个表达式变成：
    $$ (y^2 + y) + (y^3 + y + 1) + y + 1. $$ 合并同类项（记住，加法是 XOR，所以重复的项消失）：
    $$ y^2 + y^3 + 1 = y^2 + y + 1 + 1 = y^2 + y. $$

这个结果，$\alpha^2 + \alpha$，是另一个 $GF(8)$ 中的多项式。仔细跟踪这些步骤确保了精确的、 无损 的算术。

---

二进制矩阵实现高效编码

虽然 $GF(2^n)$ 算术在概念上很清晰，但对于大数据来说，直接的多项式乘法可能会消耗大量 CPU。一个常见的优化是将 $GF(2^n)$ 的每个元素表示为一个 $n\times n$ 的二进制矩阵：

• 加法在 $GF(2^n) \leftrightarrow$ 矩阵位的 XOR。
• 乘法在 $GF(2^n) \leftrightarrow$ 矩阵乘法 + XOR 的组合。

而且许多现实系统跳过了显式矩阵表示，而只是简单地在硬件中执行重复的 XOR 操作。例如，如果你只有系数为 $0$ 或 $1$，可以选取一个带有许多 $0/1$ 模式的编码矩阵，因此每行的乘法基本上是：

$$ \text{碎片} = \bigoplus_{\substack{\text{位置 } j \ \text{其中行}[j]=1}} \text{数据块}_j, $$

其中 $\oplus$ 是 XOR。

如何使用扩展域对任意二进制数据进行编码？

在存储或传输原始二进制数据时，使用像 $GF(7)$ 或 $GF(11)$ 这样素数域可能会产生不匹配：每个域元素可能在最近到 2 比特或 3 比特块的对应上产生浪费，增加存储开销。扩展域通过让我每个元素直接代表 $n$ 位串，避免这种情况，从而与二进制数据无缝对接。

例如，$GF(2^3)$ 是一个 8 元素的域，使用 3 位表示（$000$ 到 $111$）并且对不可约多项式进行模算术。在这里，我们将看到：

• $GF(2^3)$ 元素的参考表
• $GF(2^3)$ 中的基本算术
• 一个示例，使用 $[3, 2]$ 编码“CCDCFE”——避免了素数域的比特开销

$GF(2^3)$ 的元素

我们选一个不可约多项式 $y^3 + y + 1 = 0$。将这 8 个元素标记为二进制串 ${000, 001, 010, 011, 100, 101, 110, 111}$。我们还可以将每个元素视为 $y$ 多项式中 $degree < 3$ 的多项式：

元素 #	多项式	3 位表示
0	$0y^2 + 0y + 0$	000
1	$0y^2 + 0y + 1$	001
2	$0y^2 + 1y + 0$	010
3	$0y^2 + 1y + 1$	011
4	$1y^2 + 0y + 0$	100
5	$1y^2 + 0y + 1$	101
6	$1y^2 + 1y + 0$	110
7	$1y^2 + 1y + 1$	111

$GF(2^3)$ 中的算术

现在，让我们理解 $GF(2^3)$ 中算术操作是如何工作的。

加法

• 采用在 3 位表示上的按位 XOR 执行。
• 多项式视图：系数按模 2 相加。
• 示例：$6 + 7$ 在二进制中是 110 $\oplus$ 111 = 001（即 1）。

减法

• 在特征为 2 的情况下，减法与加法相同（因为每个元素都是其自身的负值）。
• 示例：$6 - 6 = 110 \oplus 110 = 000 = 0$。

乘法

• 乘法多项式，然后在 $y^3 + y + 1$ 下模运算。

• 示例：$6 \times 7$ 意味着

  $$ (y^2 + y) \;\times\; (y^2 + y + 1) = (y^4 + y^3 + y^2) + (y^3 + y^2 + y) =(y^4 + y) $$

  $$ = y(y^3 + 1) = y(y + 1 + 1) = y*y = y^2 \;\;\text{mod}\;\; (y^3 + y +1). $$

  经多项式扩展和减少，结果是 $y^2$，即 100（元素 #4）。

$GF(2^3)$ 的乘法表可能如下所示：

$*$	000	001	010	011	100	101	110	111
000	000	000	000	000	000	000	000	000
001	000	001	010	011	100	101	110	111
010	000	010	100	110	011	001	111	101
011	000	011	110	101	111	100	001	010
100	000	100	011	111	110	010	101	001
101	000	101	001	100	010	111	011	110
110	000	110	111	001	101	011	010	100
111	000	111	101	010	001	110	100	011

除法

在 $GF(2^n)$ 中，除法一开始看起来不太寻常。一般来说，$GF(2^n)$ 中的除法是通过乘以乘法逆元来完成的。

我们来看看到底该如何计算：

$$ \frac{6}{7} \quad\text{in}\quad GF(2^3). $$

第 1 步：将数字表示为二进制和多项式

让我们将每个数字映射到其 3 位二进制串，然后到相应的 $y$ 多项式：

十进制	二进制	多项式
6	110	$y^2 + y$
7	111	$y^2 + y + 1$

我们的目标是在 $GF(2^3)$ 中计算：

$$ \frac{6}{7} \;=\; 6 \;\times\; 7^{-1}, $$ 其中 $7^{-1}$ 由 $7 \times 7^{-1} = 1$ 定义。

第 2 步：找到 7 的逆元（$7^{-1}$）

我们测试所有非零元素以找到 $\alpha$，使得 $7 \times \alpha = 1$。

每个产品 $7 \times \alpha$ 是通过使用多项式乘法在多项式 $y^3 + y + 1$（不可约多项式）下计算的。以下是如何做的：

1. $7 \times 1$（二进制 001）
   $$ (y^2 + y + 1) \times 1 = y^2 + y + 1 \quad (\text{= 7, 二进制 111}). $$

2. $7 \times 2$（二进制 010 = $y$）
   $$ (y^2 + y + 1) \times y = y^3 + y^2 + y. $$
   使用 $y^3 \equiv y + 1$ 进行简化：
   $$ (y + 1) + y^2 + y = y^2 + 1 \quad (\text{= 5, 二进制 101}). $$

3. $7 \times 5$（二进制 101 = $y^2 + 1$）
   $$ (y^2 + y + 1)(y^2 + 1) = y^4 + y^3 + y^2 + y^2 + y + 1. $$
   简化（$y^2 + y^2 = 0$）并且简化 $y^4 = y^2 + y$，$y^3 = y + 1$：
   $$ (y^2 + y) + (y + 1) + y + 1 = 1 \quad (\text{= 1, 二进制 001}). $$
   这确认了 $7^{-1} = 5$。

逆元测试结果

候选 $\alpha$	计算 $7 \times \alpha$	结果
001 (1)	7	≠ 1
010 (2)	5	≠ 1
011 (3)	4	≠ 1
100 (4)	6	≠ 1
101 (5)	1	✅ = 1
110 (6)	2	≠ 1
111 (7)	3	≠ 1

第 3 步：执行除法 $\,6 \div 7\,$

现在计算：
$$ 6 \div 7 = 6 \times 5 = (y^2 + y)(y^2 + 1). $$

多项式乘法 $$ (y^2 + y)(y^2 + 1) = y^4 + y^3 + y^2 + y. $$

在 $y^3 + y + 1$ 上模运算

1. 用 $y^4 = y^2 + y$ 和 $y^3 = y + 1$ 替换：
   $$ (y^2 + y) + (y^3 + y + 1) + y + 1. $$
2. 简化（系数模 2）：
   $$ \cancel{y^2} + \cancel{y}+ \cancel{y} + 1 + \cancel{y^2} + y = y + 1 \quad (\text{= 3, 二进制 011}). $$

因此我们得到， $$ \frac{6}{7} = 3 \quad \text{in} \quad GF(2^3). $$

(二进制：110 ÷ 111 = 011)

编码示例：在 $GF(2^3)$ 中用 $[3, 2]$ 编码“CCDCFE”

假设你要对短旋律“C, C, D, C, F, E”进行出错编码（每个音符映射到数字 2、2、3、2、5、4），但现在你想避免块的膨胀。你选择 $GF(2^3)$，它直接处理 3 位块——没有比特浪费。让我们一起处理编码/解码细节。

将音符映射到 $GF(2^3)$ 元素

我们有旋律：C, C, D, C, F, E。假设我们指定以下数值表示：

• C → 2
• D → 3
• E → 4
• F → 5

这些数字在 $GF(2^3)$ 中是元素，如果我们用二进制解释它们：

• 2 → 010 (多项式 $y$)
• 3 → 011 ($y + 1$)
• 4 → 100 ($y^2$)
• 5 → 101 ($y^2 + 1$)

因此，序列“CCDCFE”的表示为：[2, 2, 3, 2, 5, 4]。

将数据分块（K=2）

对于一个 $[3,2]$ 出错编码，每个数据块大小为 $K=2$。将 6 个音符序列分成为 3 个块：

1. 块 1: $[C, C]$ = $[2, 2]$
2. 块 2: $[D, C]$ = $[3, 2]$
3. 块 3: $[F, E]$ = $[5, 4]$

选择编码器矩阵（N=3, K=2）

我们需要一个 $3 \times 2$ 的矩阵 $E$ 在 $GF(2^3)$ 中，其中每个 $2 \times 2$ 的子矩阵都是可逆的。这是成功的 $[3,2]$ 出错编码的关键要求：任意两个碎片都应该足以重构两个原始数据块。

一种经典的方法，如前所述，是通过选择不同的 ${x_1,\dots,x_N}$ 和 ${y_1,\dots,y_K}$ 在我们的域中并让

$$ C_{i,j} = \frac{1}{x_i - y_j}. $$

然而，有时一个“类似柯西”的矩阵或其他经过仔细选择的矩阵也可以工作——只要它满足可逆性的标准。在这个示例中，我们使用：

$$ E \;=\; \begin{bmatrix} 1 & 1\ 2 & 3\ 4 & 5 \end{bmatrix} \quad \text{in } GF(2^3). $$

以下是它为何有效：

• 不同的元素：每一行都有唯一的领域元素（如二进制中的 001、010、011、100、101）。
• 子矩阵的可逆性：如果你选择 任意 两行（形成一个 $2\times2$ 的子矩阵）并在 $GF(2^3)$ 中计算它的行列式，你将得到一个非零结果——意味着它是可逆的。

在实践中，你可以通过计算每对的行列式来验证子矩阵的可逆性，通过有限域算术完成。这一步通常在离线或通过代码完成，确保你拥有一个确保可逆的矩阵，而不必严格依赖于 $\frac{1}{x_i - y_j}$ 公式。

因此，尽管你可以显式构造一个矩阵来使用正式的柯西定义，但只要确保所有 $2\times2$ 的小行列式是可逆的，这就足够了。我们的示例 $\begin{bmatrix}1 & 1\2 & 3\4 & 5\end{bmatrix}$ 符合该条件，因此作为有效的 $[3,2]$ 编码器。

因此，我们可以使用：

$$ E \;=\; \begin{bmatrix} 1 & 1\ 2 & 3\ 4 & 5 \end{bmatrix}, $$ 其中每个条目都是 $GF(2^3)$ 中的一个元素。在二进制/多项式形式中：

• $1$ 是 001 （$y^0$）
• $2$ 是 010 （$y$）
• $3$ 是 011 （$y + 1$）
• $4$ 是 100 （$y^2$）
• $5$ 是 101 （$y^2 + 1$）

编码每个数据块

为了编码一个块 $\begin{bmatrix} x \ y \end{bmatrix}$，我们计算：

$$ \begin{bmatrix} \text{碎片}_1\ \text{碎片}_2\ \text{碎片}_3 \end{bmatrix} = E \times \begin{bmatrix} x\ y\end{bmatrix}. $$

这样每个块就生成 3 个输出碎片。让我们详细处理每个块：

块 1: [2, 2]

• 数据向量：$[2, 2]$

• 乘法：

• 碎片 1 = $[1, 1] \cdot [2, 2]$

  • 在 $GF(2^3)$ 中，加法是 XOR，所以 $(1\times2) \oplus (1\times2)$。
  • $1 \times 2 = 2$。然后 $2 \oplus 2 = 0$。所以碎片 1 = 000。

• 碎片 2 = $[2, 3] \cdot [2, 2]$

  • $2 \times 2 = (y) \times (y) = y^2 = 4$（十进制，即 100）。
  • $3 \times 2 = (y + 1) \times y = y^2 + y = 6$（十进制，即 110）。
  • 然后将它们 XOR 起来：$4 \oplus 6 = 100 \oplus 110 = 010 = 2。
  • 所以碎片 2 = 010（十进制 2）。

• 碎片 3 = $[4, 5] \cdot [2, 2]$

  • $4 \times 2 = (y^2) \times (y) = y^3$。
    因为在我们的不可约多项式中 $y^3 = y + 1$，所以是 011 = 3。
  • $5 \times 2 = (y^2 + 1) \times y = y^3 + y$。
    • $y^3 = y + 1$，因此 $y^3 + y = (y + 1) \oplus y = 1$。
    • 这是 001（在十进制中即 1）。
  • 将它们 XOR：$3 \oplus 1 = 011 \oplus 001 = 010 = 2。
  • 所以碎片 3 = 010（十进制 2）。

因此，块 1 编码为碎片向量 = $[0,\; 2,\; 2]$。

块 2: [3, 2]

• 数据向量：$[3, 2]$

• 乘法：

• 碎片 1 = $[1, 1] \cdot [3, 2]$

  • $1 \times 3 \oplus 1 \times 2 = 3 \oplus 2 = 011 \oplus 010 = 001 = 1。

• 碎片 2 = $[2, 3] \cdot [3, 2]$

  • $2 \times 3 = (y) \times (y + 1)$。这是 $y^2 + y$，即 110 = 6。
  • $3 \times 2 = (y + 1) \times y$。同样，也得到 110 = 6。
  • 将它们 XOR: 110 $\oplus 110`` =000` = 0。

• 碎片 3 = $[4,5] \cdot [3,2]$

  • $4 \times 3 = (y^2) \times (y + 1) = y^3 + y^2$。
    • $y^3 = (y + 1)$，所以 $y^3 + y^2 = (y + 1) \oplus (y^2)$。这是 011 $\oplus $ 100 = 111 = 7（十进制）。
  • $5 \times 2 = (y^2 + 1) \times y = y^3 + y$。这是 1，如前所述。
  • 将它们 XOR：111 $\oplus $ 001 = 110 = 6（十进制）。

因此，块 2 → $[1, 0, 6]$ (十进制) 即 [001, 000, 110]（二进制）。

块 3: [5, 4]

• 数据向量：$[5, 4]$

• 乘法：

• 碎片 1 = $[1, 1]\cdot [5, 4]$

  • $5 \oplus 4 = 101 \oplus 100 = 001 = 1。

• 碎片 2 = $[2, 3]\cdot [5, 4]$

  • $2 \times 5 = (y) \times (y^2 + 1) = y^3 + y = 1$ （如前所述）。
  • $3 \times 4 = (y + 1) \times (y^2)$。
    • 这是 $y^3 + y^2$。用 $y^3 = y + 1$ 更新，得到 $y + 1 \oplus y^2 =$ 011 $\oplus $ 100 = 111 = 7。
  • 将它们 XOR：001 $\oplus $ 111 = 110（十进制是 6）。

这样，我们已经逐步翻译并符合了你希望的格式操作。- Shard 3 = $[4,5]\cdot [5,4]$

• $4 \times 5 = (y^2)\times (y^2+1) = y^4 + y^2.$
  • $y^4 = y \times y^3 = y(y+1)= y^2 + y$. 所以 $y^4 + y^2 = (y^2+y)\oplus y^2 = y$.
  • 这就是 010 = 2 在十进制中。
• $5 \times 4 = (y^2+1)\times(y^2) = y^4 + y^2$. 相同的展开，亦为 010 = 2。
• 进行异或运算： 2 $\oplus$ 2 = 0。

因此，块 3 → $[1,6,0]$。

最终编码的碎片

将所有内容汇总，每个块的编码碎片（十进制）如下：

• 块 1 = $\bigl[0,\; 2,\; 2\bigr]$
• 块 2 = $\bigl[1,\; 0,\; 6\bigr]$
• 块 3 = $\bigl[1,\; 6,\; 0\bigr]$

以二进制（每个3位）表示：

• 块 1 碎片 = [000, 010, 010]
• 块 2 碎片 = [001, 000, 110]
• 块 3 碎片 = [001, 110, 000]

每一行存储在一个单独的代码碎片中（Shard 1, Shard 2, Shard 3）。如果任何单个碎片失败，你可以从剩下的两个碎片中进行解码。

解码示例

假设在块 2 中我们丢失了碎片 2，但保留了碎片 1 和碎片 3：

• 已知：

  • 碎片 1 = 001（十进制 1）
  • 碎片 3 = 110（十进制 6）

• 对应的行： $E$ 中的行 #1 和 #3：

  $$ E' = \begin{bmatrix} 1 & 1 \ 4 & 5 \end{bmatrix} \ (\text{在 GF}(2^3)). $$

• $E'$ 的逆：

  • 我们计算 $\det(E')$，并在 $GF(2^3)$ 中进行标准的多项式反演。（省略以简洁，实际上使用多项式算术或小型查找表的方法。）

• 恢复原始 $\begin{bmatrix}x\ y\end{bmatrix}$ = $(E')^{-1} \cdot [\text{Shard1}, \text{Shard3}]^T$.

你会发现 $[3, 2]$ 出现，确认数据块 [3,2]（D, C）。

这种方法与二进制数据完美匹配。没有“未使用的排列”或部分位被浪费——每个可能的 3 位字符串都是一个有效的元素。

---

实际实现

算法伪代码

sequenceDiagram
    participant U as 用户数据
    participant S as 云/存储中的碎片
    participant E as 编码器/解码器
    U ->> E: 提供数据块
    E ->> E: 编码（GF(2^n) 中的矩阵乘法）
    E ->> S: 分发 N 个碎片
    Note over S: 一些碎片丢失/失败
    S ->> E: 提供任何 K 余下的碎片
    E ->> E: 解码（子矩阵反演）
    E ->> U: 返回原始数据

让我们演示在 $GF(8)$ 中简化的 $[4, 2]$ 码。我们将展示每个步骤如何与数学相结合：

编码器构造（类似于 Cauchy 或定制设计）：

给定 GF(8) 的不可约多项式 p(y)，
定义大小为 (4 x 2) 的 encoder_matrix E，每个条目在 GF(8) 中。

示例（不一定是最小的）:
E = [
  [1, 1],  # 行 0
  [2, 3],  # 行 1
  [4, 5],  # 行 2
  [6, 7]   # 行 3
]

编码：

function encode_block(data_vector):
    # data_vector 在 GF(8) 中的长度为 2
    # encoder_matrix E 规模为 4 x 2

    shards = E * data_vector   # 在 GF(8) 中矩阵乘法
    return shards  # 长度 4

解码：

function decode_shards(shards_subset, row_indices):
    # shards_subset 的长度 K=2（从 4 中任意选 2 个碎片）
    # row_indices 是它们来自 E 的哪些行（例如，[0,2]）

    E_sub = submatrix(E, row_indices)  # 形状 2 x 2
    E_sub_inv = invert(E_sub in GF(8)) # 在 GF(8) 中查找矩阵逆

    data_vector = E_sub_inv * shards_subset
    return data_vector

使用 $GF(7)$ 的逐步示例

下面，我们在 $GF(7)$ 中进行一个显式示例。假设：

• $K = 2, N = 3$.
• 数据向量 = $[2, 2]$ 在 $GF(7)$ 中。
• 编码器矩阵：

$$ E= \begin{bmatrix} \frac{1}{2} & 1 \ \frac{1}{3} & \frac{1}{2} \ \frac{1}{4} & \frac{1}{3} \end{bmatrix} \quad (\text{全操作模 }7). $$

我们在 $GF(7)$ 中解释 $\frac{1}{2}\equiv4$, $\frac{1}{3}\equiv5$, $\frac{1}{4}\equiv2$。因此：

$$ E = \begin{bmatrix} 4 & 1 \ 5 & 4 \ 2 & 5 \end{bmatrix} \ (\mod 7). $$

• 编码：

$$ \begin{bmatrix} \text{Shard1}\ \text{Shard2}\ \text{Shard3}\end{bmatrix}

\begin{bmatrix} 4 & 1 \ 5 & 4 \ 2 & 5 \end{bmatrix} \cdot \begin{bmatrix}2\2\end{bmatrix}

\begin{bmatrix} (4\times2 + 1\times2)\mod7\ (5\times2 + 4\times2)\mod7\ (2\times2 + 5\times2)\mod7 \end{bmatrix}. $$

也就是：

• Shard1 = $(8 + 2)\mod7 = 10 \mod7 = 3$.
• Shard2 = $(10 + 8)\mod7 = 18 \mod7 = 4$.
• Shard3 = $(4 + 10)\mod7 = 14 \mod7 = 0$.

因此，$\text{shards}=[3,4,0]$。

• 解码（假设我们只有碎片 1 和 3）。那么 $\text{shards_subset}=[3, 0]$ 来自 $E$ 的行 [0, 2]。子矩阵为：

$$ E'= \begin{bmatrix} 4 & 1\ 2 & 5 \end{bmatrix}. $$

计算其在 $GF(7)$ 中的逆。行列式 $\Delta = 4\times5 - 1\times2 = 20 - 2 = 18 \equiv 4 \ (\mod7)$。$\Delta=4$ 的逆是 $2$，因为 $4\times2=8\equiv1\ (\mod7)$。

逆矩阵为：

$$ (E')^{-1} = \frac{1}{\Delta} \begin{bmatrix} 5 & -1 \ -2 & 4 \end{bmatrix}

2 \times \begin{bmatrix} 5 & 6 \
5 & 4
\end{bmatrix}

\begin{bmatrix} 10 & 12\ 10 & 8 \end{bmatrix} \mod7

\begin{bmatrix} 3 & 5\ 3 & 1 \end{bmatrix}. $$

现在乘以 $(E')^{-1}\times[3,0]^T$：

$$ \begin{bmatrix} 3 & 5\ 3 & 1 \end{bmatrix} \cdot \begin{bmatrix} 3\ 0 \end{bmatrix}

\begin{bmatrix} (3\times3 + 5\times0)\mod7\ (3\times3 + 1\times0)\mod7 \end{bmatrix}

\begin{bmatrix} 9\mod7\ 9\mod7 \end{bmatrix}

\begin{bmatrix} 2\ 2 \end{bmatrix}. $$

我们准确恢复

$$ \begin{bmatrix}2\ 2\end{bmatrix} $$

——我们的原始数据向量。

---

挑战与未来

• 修复开销：
  当一个碎片丢失时，你可以通过从任何 $K$ 生存的碎片解码并重新编码来重新生成它。这可能是带宽密集型的。高级解决方案（如局部重建码）通过添加局部奇偶校验碎片来缓解这一点。

• 量子威胁：
  纠删编码本身并不受到量子计算的威胁（它是线性代数）。然而，通常在其“之上”运行的加密层必须适应后量子方法。

• 实现复杂性：

  • 协调多个云服务提供商或物理硬盘。
  • 跟踪丢失的碎片并协调修复。
  • 确保有限域算术的代码正确性——错误可能是微妙的。

---

我写过关于以 Reed Solomon 码实现以太坊 Danksharding 中的纠删编码的文章。你可以在 这里 阅读。

结论

纠删编码架起了抽象线性代数与实际数据可靠性之间的桥梁。通过将数据分割为碎片，我们获得了：

• 耐久性：能够容忍多个故障，开销小于复制。
• 安全性：没有单个碎片可以透露整个文件。
• 效率：高度优化的开销，特别是在扩展存储时。

随着数据量的激增，纠删编码变得势在必行。掌握有限域算术和矩阵力学的知识，你已经准备好实施或优化纠删编码系统。现在就应用它，以保护你的数据免受意外存储故障的影响，并且做到经济高效。

---

附录与进一步阅读

• 完整的 $GF(2^n)$ 实现示例：如 galois (Python) 和 Intel ISA-L Erasure Coding (C) 提供生产级构建块。
• Cauchy 矩阵
• 局部重建码
• 汉明码 - 误差校正的起源第 1 部分
• 汉明码 - 误差校正的起源第 2 部分
• 以太坊 Danksharding 中的误差纠正 - 利用广义 Reed-Solomon 码为以太坊的可扩展性提供支持

• 原文链接： github.com/thogiti/thogi...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～