c++ - 使用 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和 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 - (number of roots/2)), 但也许其余的的代码有这个问题。