使用Reed-Solomon算法实现完全数据恢复

Question

我正在测试来自此存储库的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;
    }

我的问题是，我不知道为什么算法失败了。我认为自己可能存在概念上的问题，在阅读 这里 和 这里 的相关主题后，我仍然不明白为什么不可能。

是否有可能通过基于假设或理论来说明这是不可能的？

- vgonisanz

---

对象字段是否已被创建（字段！= NULL）？ - mahesh

字段已创建，减少了冗余数据。 - vgonisanz

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）），但也许代码的其余部分存在问题。

- rcgldr