math - 你能解释一下 Reed Solomon 编码部分的单位矩阵吗？

Question

我正在从事一个我需要了解的对象存储项目 Reed Solomon纠错算法，我经历过这个 Doc作为入门和一些论文。
1. content.sakai.rutgers.edu
2. theseus.fi
但我似乎无法理解单位矩阵(红色框)的下半部分，它来自哪里。这个计算是如何完成的？

谁能解释一下。

Answer 1

编码矩阵是一个 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

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Systematic_encoding_procedure:_The_message_as_an_initial_sequence_of_values

生成编码矩阵的代码在这个github源文件的底部附近:

https://github.com/Backblaze/JavaReedSolomon/blob/master/src/main/java/com/backblaze/erasure/ReedSolomon.java

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 x n 矩阵，其中 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 view Reed Solomon。对于奇数个奇偶校验，例如RS(20,17)(3个奇偶校验)，编码需要2次矩阵乘法和1次异或，而对于单删除只需要异或。对于 e>1 删除，执行 (e-1) 乘以 n 矩阵，然后执行 XOR。对于偶数个奇偶校验，如果使用 XOR 作为编码的一部分，则需要一个 e x n 矩阵乘法来校正，或者使用 e x n 矩阵进行编码，允许一个 XOR 进行校正。

另一种选择是 Raid 6，其中“综合症”附加到数据矩阵，但没有形成正确的代码字。其中一个综合征行，称为 P，只是 XOR，另一行称为 Q，是 GF(2^8) 中 2 的连续幂。对于 3 奇偶校验 Raid 6，第三行称为 R，是 GF(2^8) 中 4 的连续幂。与标准 BCH View 不同，如果 Q 或 R 行丢失，则必须重新计算(而不是使用 XOR 来更正它)。通过使用对角线模式，如果 n 个磁盘中有 1 个发生故障，则在更换磁盘时仅需要重新生成 1/n 的 Q 和 R。

http://alamos.math.arizona.edu/RTG16/ECC/raid6.pdf

请注意，此 pdf 文件的替代方法使用与上述方法相同的有限域 GF(2^8) mod 0x11D，这可能更容易比较这些方法。