Матрица кодирования представляет собой матрицу Вандермонда 6 x 4 с использованием точек оценки {0 1 2 3 4 5}, модифицированных таким образом, что верхняя часть матрицы 4 x 4 является единичной матрицей. Для создания матрицы генерируется матрица Вандермонда 6 x 4 (где matrix [r] [c] = pow (r, c)), а затем умножается на инверсию верхней части матрицы 4 x 4 для получения матрица кодирования. Это эквивалентно «систематическому c кодированию» с «оригинальным представлением» Рида Соломона, как упомянуто в статье Википедии, на которую вы ссылались выше, которое отличается от «представления БЧД» Рида Соломона, который ссылается на 1. и 2. , Систематическая матрица кодирования c из Википедии - это транспонированная версия матрицы кодирования, используемой в вопросе.
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 строки могут быть удалены из матрицы кодирования, в результате чего получается одна из 15 возможных (6 вещей, взятых 4 за раз) 4 x 4 матриц, и все 15 возможных матриц являются обратимыми.
Если только одна строка кодированных данных 6 x 4 неверна, поэтому любая другая строка может быть выбрана произвольно, в результате чего получается одна из 15 4 x 4 обратимых матриц.
Документ кода стирания затем описывает процесс декодирования как умножение подмножества 4 × 4 кодированных данных с помощью обратного подмножества 4 × 4 матрицы кодирования для генерации исходных данных.
На основе показанных данных математика является базовой d на конечном поле GF (2 ^ 8) по модулю 0x11D. Например, кодирование с использованием последней строки матрицы кодирования с последним столбцом матрицы данных имеет вид (0x1c · 0x44) + (0x1b · 0x48) + (0x14 · 0x4 c) + (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 Рида Соломона (для одиночной ошибки, исправление выполняется xor, для двух ошибок путем умножения на матрицу 2x6 (on 6 осколков (включая стертые осколки, которые могут содержать мусор и все еще могут быть исправлены) вместо матрицы 4х4 на 4 осколках.) При желании вместо создания четностей генерируются синдромы, как описано в этом файле PDF Raid 6:
http://alamos.math.arizona.edu/RTG16/ECC/raid6.pdf
Обратите внимание, что альтернативный метод этого файла PDF использует то же конечное поле, что и метод выше, GF (2 ^ 8) mod 0x11D, что может упростить сравнение методы.