使用 reed solomon 完全恢复数据

Question

我正在测试 this repository 的 Reed Solomon 算法，以便在发生外部更改时恢复信息。

假设：

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;
    }

我的问题是我不知道为什么算法会失败。我想我有一个概念问题，阅读主题 here and here 后的错误，我不明白为什么不可能。

是否可以根据假设或理论说这是不可能的？

Answer 1

问题中的当前代码失败，因为它设置了

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) ), 但也许其余代码对此有问题。

使用 reed solomon 完全恢复数据

Full recovery data using reed solomon

c++

redundancy

error-correction

reed-solomon