Полное восстановление данных с использованием Reed Solomon - PullRequest
Новая
       97

Полное восстановление данных с использованием Reed Solomon

0 голосов
/ 25 мая 2018

Я тестирую алгоритм Рида Соломона из этого хранилища , чтобы восстановить информацию в случае каких-либо внешних изменений.

Предполагая: 

m = bits per symbol
k = data
r = redundance 
n = bits per block = r + k = 2^m - 1
t = error correction = (n - k) / 2

Я могу кодифицировать и восстановить информацию, используя следующие параметры: 

m = 8
n = 255
r = 135
k = 120
t = 67

И работает отлично, я могу исправить 67 ошибок.

Мои предположения:

  • Только данные будут повреждены, без избыточности.
  • Для полного восстановления n = 3 * k -> r = 2 * k.
  • Тогда n = 255, поэтому r в этом случае должно быть 170.
  • Так что я должен иметь GF (2 ^ m) и RS [n, k, n - k + 1] для использованияGF (2 ^ 8) и RS [255, 85, 171]

С этими параметрами я получаю ошибку: 

Error - Failed to create sequential root generator!

Это означает, что библиотечная функция make_sequential_root_generator_polynomial: 

const std::size_t field_descriptor                =   8;    /* m = bit per symbol */
const std::size_t generator_polynomial_index      = 120;
const std::size_t generator_polynomial_root_count = 170;    /* root shall be equal to redundance */
const schifra::galois::field field(field_descriptor,
                                   schifra::galois::primitive_polynomial_size06,
                                   schifra::galois::primitive_polynomial06);
    if (
         !schifra::make_sequential_root_generator_polynomial(field,
                                                             generator_polynomial_index,
                                                             generator_polynomial_root_count,
                                                             generator_polynomial)
       )
    {
       std::cout << "Error - Failed to create sequential root generator!" << std::endl;
       return false;
    }

Моя проблема в том, что я не знаю, почему алгоритм не работает.Я думаю, что у меня есть проблема с концепцией, ошибка после прочтения темы здесь и здесь , я не понимаю, почему это невозможно.

Можно ли использовать согласно предположениям или теории сказать, что это невозможно?

1 Ответ

0 голосов
/ 25 мая 2018

Текущий код в вопросе не работает, потому что он устанавливает 

generator_polynomial_index = 120;

и 120 (индекс) + 170 (число корней)> 255 (размер поля), что проверяется в 

make_sequential_root_generator_polynomial()

generator_polynomial_index обычно имеет значение 0 (первый последовательный корень = 1) или 1 (первый последовательный корень = полевой примитив = 2), если только целью не является использование полинома самовзаимного генератора.

Даже в случае самовзаимного поли, для 170 корней, generator_polynomial_index = 128 - (170/2) = 43. Установка его в 120 необычно высока.

Это может бытьвозможно, чтобы это работало, поскольку корни являются последовательными степенями по модулю 255, поэтому они могли просто обернуться, 2 ^ 120, 2 ^ 121, ..., 2 ^ 253, 2 ^ 254, 2 ^ 255 = 2 ^ 0, 2^ 256 = 2 ^ 1, ..., как это делается для самовзаимных полиномов для нечетного числа корней generator_polynomial_index = (255 - (число корней / 2)), но, возможно, остальная часть кода имеет проблемус этим.

...