我正在做一个对象存储项目，我需要了解Reed Solomon纠错算法，我已经通过这个Doc作为初学者和一些论文。
1. content.sakai.rutgers.edu
2. theseus.fi
但我似乎无法理解单位矩阵的下部（红色框），它来自哪里。这个计算是如何进行的？
谁能解释一下。
1300 次
1 回答
2
编码矩阵是一个 6 x 4 Vandermonde 矩阵，使用修改后的评估点 {0 1 2 3 4 5} 使得矩阵的上 4 x 4 部分是单位矩阵。为了创建矩阵，生成一个 6 x 4 Vandermonde 矩阵（其中 matrix[r][c] = pow(r,c) ），然后乘以矩阵的上 4 x 4 部分的倒数以产生编码矩阵。这相当于您在上面链接到的维基百科文章中提到的 Reed Solomon 的“原始视图”的“系统编码”，这与链接 1 和 2 的 Reed Solomon 的“BCH 视图”不同。维基百科的示例系统编码矩阵是问题中使用的编码矩阵的转置版本。
https://en.wikipedia.org/wiki/Vandermonde_matrix
生成编码矩阵的代码在这个 github 源文件的底部附近：
Vandermonde inverse upper encoding
matrix part of matrix matrix
01 00 00 00 01 00 00 00
01 01 01 01 01 00 00 00 00 01 00 00
01 02 04 08 x 7b 01 8e f4 = 00 00 01 00
01 03 05 0f 00 7a f4 8e 00 00 00 01
01 04 10 40 7a 7a 7a 7a 1b 1c 12 14
01 05 11 55 1c 1b 14 12
解码分两步进行。首先，恢复任何丢失的数据行，然后使用现在恢复的数据重新生成任何丢失的奇偶校验行。
对于缺失的2行数据，去掉编码矩阵对应的2行，将4×4的子矩阵倒置，用4行不缺失数据和奇偶校验相乘，恢复缺失的2行数据。如果只有 1 行数据丢失，则选择第二个数据行，就好像它丢失了一样，以生成反转矩阵。数据的实际再生只需要逆矩阵的相应行用于矩阵乘法。
一旦数据被恢复，任何丢失的奇偶校验行都将使用编码矩阵的相应行从现在恢复的数据中重新生成。
根据显示的数据，数学基于有限域 GF(2^8) 模 0x11D。例如，使用编码矩阵的最后一行与数据矩阵的最后一列进行编码为 (0x1c·0x44)+(0x1b·0x48)+(0x14·0x4c)+(0x12·0x50) = 0x25（使用有限域数学）。
问题示例没有明确说明 6 x 4 编码矩阵可以编码 4 xn 矩阵，其中 n 是每行的字节数。n == 8 的示例：
encode data encoded data
01 00 00 00 31 32 33 34 35 36 37 38
00 01 00 00 31 32 33 34 35 36 37 38 41 42 43 44 45 46 47 48
00 00 01 00 x 41 42 43 44 45 46 47 48 = 49 4a 4b 4c 4d 4e 4f 50
00 00 00 01 49 4a 4b 4c 4d 4e 4f 50 51 52 53 54 55 56 57 58
1b 1c 12 14 51 52 53 54 55 56 57 58 e8 eb ea ed ec ef ee dc
1c 1b 14 12 f5 f6 f7 f0 f1 f2 f3 a1
assume rows 0 and 4 are erasures and deleted from the matrices:
00 01 00 00 41 42 43 44 45 46 47 48
00 00 01 00 49 4a 4b 4c 4d 4e 4f 50
00 00 00 01 51 52 53 54 55 56 57 58
1c 1b 14 12 f5 f6 f7 f0 f1 f2 f3 a1
invert encode sub-matrix:
inverse encode identity
46 68 8f a0 00 01 00 00 01 00 00 00
01 00 00 00 x 00 00 01 00 = 00 01 00 00
00 01 00 00 00 00 00 01 00 00 01 00
00 00 01 00 1c 1b 14 12 00 00 00 01
reconstruct data using sub-matrices:
inverse encoded data restored data
46 68 8f a0 41 42 43 44 45 46 47 48 31 32 33 34 35 36 37 38
01 00 00 00 x 49 4a 4b 4c 4d 4e 4f 50 = 41 42 43 44 45 46 47 48
00 01 00 00 51 52 53 54 55 56 57 58 49 4a 4b 4c 4d 4e 4f 50
00 00 01 00 f5 f6 f7 f0 f1 f2 f3 a1 51 52 53 54 55 56 57 58
The actual process only uses the rows of the matrices that correspond
to the erased rows that need to be reconstructed.
First data is reconstructed:
sub-inverse encoded data reconstructed data
41 42 43 44 45 46 47 48
46 68 8f a0 x 49 4a 4b 4c 4d 4e 4f 50 = 31 32 33 34 35 36 37 38
51 52 53 54 55 56 57 58
f5 f6 f7 f0 f1 f2 f3 a1
Once data is reconstructed, reconstruct parity
sub-encode data reconstruted parity
31 32 33 34 35 36 37 38
1b 1c 12 14 x 41 42 43 44 45 46 47 48 = e8 eb ea ed ec ef ee dc
49 4a 4b 4c 4d 4e 4f 50
51 52 53 54 55 56 57 58
这种方法的一种替代方法是使用 BCH 视图 Reed Solomon。对于奇数个奇偶校验，例如 RS(20,17)（3 个奇偶校验），编码需要 2 个矩阵乘法和一个 XOR，而对于单个擦除，只需要 XOR。对于 e>1 擦除，执行 (e-1) x n 矩阵乘法，然后执行 XOR。对于偶数个奇偶校验，如果 XOR 用作编码的一部分，则需要 ae 乘以 n 矩阵乘以进行校正，或者使用 exn 矩阵进行编码，从而允许一个 XOR 进行校正。
另一种选择是 Raid 6，其中“综合症”被附加到数据矩阵中，但不形成正确的代码字。其中一个称为 P 的校正子行只是 XOR，称为 Q 的另一行是 GF(2^8) 中 2 的连续幂。对于 3 奇偶校验 Raid 6，第三行称为 R，是 GF(2^8) 中 4 的连续幂。与标准 BCH 视图不同，如果 Q 或 R 行丢失，则必须重新计算（而不是使用 XOR 来纠正它）。通过使用对角线模式，如果 n 个磁盘中有 1 个发生故障，则在更换磁盘时只需重新生成 Q 和 R 的 1/n。
http://alamos.math.arizona.edu/RTG16/ECC/raid6.pdf
请注意，此 pdf 文件的替代方法使用与上述方法相同的有限域，GF(2^8) mod 0x11D，这可能更容易比较这些方法。
于 2020-01-27T15:00:03.133 回答