编码矩阵是使用修改后的评估点{0 1 2 3 4 5}的 6 x 4 Vandermonde 矩阵,以便矩阵的上部 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/Vandermonde_matrix
https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_ Correction#Systematic_encoding_procedure:_The_message_as_an_initial_sequence_of_values 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 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 视图 Reed Solomon。对于奇数奇偶校验,例如RS(20,17)(3个奇偶校验),编码需要2次矩阵乘法和一次异或,而对于单次擦除只需要异或。对于 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 视图不同,如果 Q 或 R 行丢失,则必须重新计算(而不是使用 XOR 来纠正它)。通过使用对角模式,如果 n 个磁盘中的 1 个出现故障,则在更换磁盘时只需重新生成 Q 和 R 中的 1/n。
http://alamos.math.arizona.edu/RTG16/ECC/raid6.pdf http://alamos.math.arizona.edu/RTG16/ECC/raid6.pdf
请注意,此 pdf 文件的替代方法使用与上述方法相同的有限域 GF(2^8) mod 0x11D,这可能会使比较这些方法变得更容易。