受 Tetrys 启发的纠错码

这是基于 Tetrys 的 Rust 中纠错码的实现。

Tetrys 草案对 GF(256) 的说明如下

Vandermonde based coefficients over the finite field GF(2^(8)), as defined below. Each coefficient is built as alpha^( (source_symbol_id*coded-symbol_id) % 256), with alpha the root of the primitive polynomial

用于 GF(256) 的不可约多项式是 x^(8) + x^(4) + x^(3) + x^(2) + 1。

如何计算这个多项式的根？根是多项式等于 0 的 x 的值。但这个原始多项式（康威多项式）应该在 GF(2) 中定义，但 0 和 1 都不是这个多项式的根。草案引用了 RFC5510 的第 8.1 节，指出这一点

Note that all the roots of this polynomial are in GF(2^^m) but not in GF(2).

因此，为了找到根，我们必须在 GF256 中而不是 GF(2) 中评估多项式来找到根。

让我们用 galois Python 库来做（注意：确保 numpy>=1.23.3，否则可能会导致错误！）

pip install galois

python
>>> import galois
>>> GF = galois.GF(256)
>>> conway_poly_gf256 = galois.Poly([1, 0, 0, 0, 1, 1, 1, 0, 1], field=GF)
>>> print(conway_poly_gf256) # ensure that the poly is correct
x^8 + x^4 + x^3 + x^2 + 1
>>> conway_poly_gf256.roots()
GF([  2,   4,  16,  29,  76,  95, 133, 157], order=2^8)

从 [ 2, 4, 16, 29, 76, 95, 133, 157] 中的任何根都是好的。我们随机选择了 157 来推导 van der Monde 系数。