使用里德所罗门完全恢复数据

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

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

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

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, ...，因为这是对奇数根的自互易多项式完成的有这个问题。