Я работаю над проектом хранилища объектов, и мне нужно понять Рида Соломона алгоритм исправления ошибок, я просмотрел этот Документ в качестве стартового, а также некоторые дипломная работа.
1. content.sakai. rutgers.edu
2. theseus.fi
но я не могу понять нижнюю часть матрицы идентичности (красный прямоугольник), откуда она исходит. Как выполняется этот расчет?
Кто-нибудь может объяснить это.
Матрица кодирования представляет собой матрицу Вандермонда 6 x 4 с использованием точек оценки {0 1 2 3 4 5}, измененных таким образом, что верхняя часть матрицы 4 x 4 представляет собой единичную матрицу. Чтобы создать матрицу, генерируется матрица Вандермонда 6 x 4 (где matrix[r][c] = pow(r,c) ), а затем умножается на обратную верхнюю часть матрицы 4 x 4 для получения кодирования матрица. Это эквивалентно систематическому кодированию с исходным представлением Рида Соломона, как указано в статье Википедии, на которую вы ссылались выше, что отличается от представления Рида Соломона BCH, на которое ссылаются ссылки 1. и 2.. Пример систематической матрицы кодирования Википедии представляет собой транспонированную версию матрицы кодирования, используемой в вопросе.
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 x 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 умножения матриц и одно XOR, а для одного стирания требуется только XOR. Для стираний e>1 выполняется умножение матрицы (e-1) на n с последующим XOR. Для четного числа четностей, если XOR используется как часть кодирования, то для исправления требуется умножение матрицы e на n или матрица e x n, используемая для кодирования, позволяющая использовать одно XOR для исправления.
Другой альтернативой является Raid 6, где синдромы добавляются к матрице данных, но не образуют правильного кодового слова. Одна из строк синдрома, называемая P, является просто XOR, другая строка, называемая Q, представляет собой последовательные степени 2 в GF (2 ^ 8). Для Raid 6 с 3 четностью третья строка называется R и представляет собой последовательные степени 4 в GF (2 ^ 8). В отличие от стандартного представления BCH, если строка Q или R потеряна, ее необходимо пересчитать (в отличие от использования XOR для ее исправления). При использовании диагонального шаблона, если 1 из n дисков выходит из строя, то при замене диска необходимо регенерировать только 1/n дисков Q и R.
http://alamos.math.arizona.edu/RTG16/ECC/raid6.pdf
Обратите внимание, что в альтернативном методе этого pdf-файла используется то же конечное поле, что и в методе выше, GF(2^8) mod 0x11D, что может упростить сравнение методов.
