unireedsolomon 1.0.6

安装

对于Python 3.7+

pip install --upgrade unireedsolomon

对于Python 2.7和≤ 3.6

pip install --upgrade unireedsolomon==1.0.5

要安装和编译Cython速度优化的模块cff.pyx和cpolynomial.pyx，它们在编码期间提供约4倍的速度提升，请安装Cython 0.29.x，然后输入

pip install --upgrade unireedsolomon --config-setting="--build-option=--cythonize"

快速入门

>>> import unireedsolomon as rs
>>> coder = rs.RSCoder(20,13)
>>> c = coder.encode("Hello, world!")
>>> print repr(c)
'Hello, world!\x8d\x13\xf4\xf9C\x10\xe5'
>>>
>>> r = "\0"*3 + c[3:]
>>> print repr(r)
'\x00\x00\x00lo, world!\x8d\x13\xf4\xf9C\x10\xe5'
>>>
>>> coder.decode(r)
'Hello, world!'

描述

此库实现了一个纯Python文档化的通用Reed-Solomon错误纠正编解码器，具有数学命名法，兼容Python 3.7+和PyPy 3。

该项目旨在保持注释良好、组织有序的代码，具有广泛的文档和各种算术运算的数学清晰度。

这个库与其它Reed-Solomon库有什么不同？

• 通用：与（几乎）任何其他Reed-Solomon编解码器兼容。这意味着您可以选择参数，以便您可以使用另一个RS编解码器进行编码和解码，或者相反，使用另一个RS编解码器进行编码，然后使用此库进行解码。

• 错误和擦除解码允许同时解码擦除（您知道损坏字符的位置）和错误（您不知道损坏字符的位置）。

• 文档化：遵循文献编程指南，您应该通过阅读代码和注释来理解关于RS所需了解的一切。

• 数学命名法：例如，与大多数其他RS库不同，您将看到不同的数学结构之间的明确区分，例如，Galois域数字与通用多项式对象明显分开，并且两者都与使用这两种结构的Reed-Solomon算法分开。为此目的，选择了面向对象编程来设计库的架构，尽管显然会牺牲一点性能。然而，此库更重视数学清晰度和文档，而不是性能（即使尽可能优化性能）。

• 纯Python意味着除了Python解释器之外没有任何依赖。这意味着此库在将来应该具有弹性（因为它不依赖于随时间可能损坏的外部库，参见软件腐化），并且您可以在任何可以安装Python的系统上使用它（包括在线云服务）。

作者尽力广泛地记录了算法。然而，涉及的许多数学是非平凡的，我们无法在注释中解释所有内容。要了解更多关于算法的信息，请参阅以下资源

• http://en.wikipedia.org/wiki/Reed–Solomon_error_correction

• http://www.cs.duke.edu/courses/spring10/cps296.3/rs_scribe.pdf

• http://www.cs.duke.edu/courses/spring10/cps296.3/decoding_rs_scribe.pdf

• http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/reed_solomon.ps

• http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/rs_decode.ps

此外，这里有一份作者在2010年春季课程中分享的关于实现该库的经验的演示文稿副本。LaTeX源代码位于演示文稿目录中。

http://www.cs.duke.edu/courses/spring10/cps296.3/decoding_rs.pdf

代码最近更新以支持错误和擦除解码（同时进行），并且是通用的（你可以提供参数以与几乎所有其他RS编解码器兼容）。

如果你使用PyPy和快速方法（约1 MB/s），编解码器具有相当的性能，但如果我们放弃面向对象的设计（将所有内容实现为函数），则速度会更快，但这将以牺牲数学清晰度为代价。如果你感兴趣，请查看Tomer Filiba的reedsolo库，它具有完全相同的实现，但没有对象（速度提高约5倍）。

文件

rs.py

包含Reed-Solomon编解码器/解码器对象

polynomial.py

包含多项式对象（纯Python实现）

ff.py

包含表示GF(2^p)域元素的GF2int对象，默认p为8（纯Python实现）

polynomial.pyx

polynomial.py的Cython实现，具有等效函数（可选）

ff.pyx

ff.py的Cython实现，具有等效函数（可选）

文档

unireedsolomon.rs.RSCoder(n, k, generator=3, prim=0x11b, fcr=1, c_exp=8)

创建一个新的Reed-Solomon编解码器/解码器对象，配置了给定的n和k值。n是码字的长度，必须小于256；k是消息的长度，必须小于n；generator、prim和fcr参数化将要构建的伽罗瓦场；c_exp是伽罗瓦场范围（即，8表示GF(2^8) = GF(256)），这既是单个符号值的限制，也是消息+ecc的最大长度。

代码将具有错误纠正能力（即，最大可修复符号数）为2*e+v <= (n-k)，其中e是错误数，v是擦除数。

典型的RSCoder是RSCoder(255, 223)

RSCoder.encode(message, poly=False, k=None)

使用Reed-Solomon编码对给定字符串进行编码。返回一个字节字符串，包含k个消息字节和n-k个校验字节在末尾。

如果消息小于k字节长，则假定在前面以空字节填充（即，缩短的Reed-Solomon码）。

返回的序列始终为n字节长。

如果poly不是False，则返回编码的多项式对象而不是将多项式转换回字符串（用于调试）。

可以通过将k设置为[1, n-1]之间的任何值来更改编码时校验/ecc字节的长度。这允许创建一个RSCoder，然后使用可变冗余率使用它。

RSCoder.encode_fast(message, poly=False, k=None)

与encode()相同，但使用更快的算法和优化技巧。

RSCoder.decode(message_ecc, nostrip=False, k=None, erasures_pos=None, only_erasures=False)

给定一个接收到的字符串或字节数组message_ecc（由消息字符串和末尾的ecc符号组成），尝试对其进行解码。如果它是一个有效的码字，或者如果错误（erratas）不超过2*e+v <= (n-k)（称为Singleton界限），则返回消息。

你可以提供一个擦除位置的列表到erasures_pos。例如，如果你有“hella warld”并且你知道a是一个擦除，你可以提供列表erasures_pos=[4, 7]。你可以纠正两倍于错误的擦除数，如果某些提供的擦除是错误的（它们是正确的符号），则没有问题，它们将被很好地修复（但将计入Singleton界限）。你也可以通过设置only_erasures=True来指定你确信只有擦除而没有错误。

消息始终有k字节长，如果消息包含较少，则使用空字节进行左填充（打孔RS码）。解码时，这些前导空字节将被剥离，但这可能在解码二进制数据时导致问题。当nostrip为True时，返回的消息始终为k字节长。这非常有用，可以确保在解码二进制数据时不会丢失数据。

请注意，RS可以纠正消息和ecc符号中的错误。

RSCoder.decode_fast(message_ecc, nostrip=False, k=None, erasures_pos=None, only_erasures=False)

与decode()相同，但使用更快的算法和优化技巧。

RSCoder.check(message_ecc, k=None)

通过测试该代码作为多项式代码是否能整除g，或者校验和的系数全为0，来验证码字（消息+末尾的ecc符号）是否有效。结果并非绝对可靠：如果为False，则可以确定消息已被损坏（或使用了错误的RS参数），但如果为True，则可能是消息是正确的，或者错误太多（即超过Singleton界限）以至于RS无法处理。返回True/False

RSCoder.check_fast(message_ecc, k=None)

与check()相同，但使用更快的算法和优化技巧。

unireedsolomon.ff.find_prime_polynomials(generator=2, c_exp=8, fast_primes=False, single=False)

计算给定生成器和伽罗瓦域特征指数的素多项式列表。然后可以使用此素多项式指定强制性的“prim”参数，特别是如果您正在使用较大的伽罗瓦域（例如，2^16）。

内部API

除了主要的RSCoder对象外，此实现还使用了两个其他对象：Polynomial和GF2int。它们的使用并不特定于编码器，甚至不特定于Reed-Solomon算法，它们只是分别代表多项式和伽罗瓦域基数为2的通用数学结构。

您不需要了解内部API即可使用RS编解码器，这只是为了方便对有兴趣深入了解数学结构的读者进行文档说明。

polynomial.Polynomial(coefficients=[], **sparse)

初始化Polynomial对象有三种方式。1) 使用列表、元组或其他可迭代对象，以降幂顺序使用项目作为系数创建多项式

2) 使用关键字参数，例如x3=5，设置x^3的系数为5

3) 不带参数，创建一个空多项式，相当于Polynomial([0])

>>> print Polynomial([5, 0, 0, 0, 0, 0])
5x^5

>>> print Polynomial(x32=5, x64=8)
8x^64 + 5x^32

>>> print Polynomial(x5=5, x9=4, x0=2)
4x^9 + 5x^5 + 2

Polynomial对象导出以下标准函数，这些函数使用多项式算术执行预期的操作。系数的算术由传入的类型确定，因此可以使用整数或GF2int对象，Polynomial类对系数的类型不敏感。

__add__
__divmod__
__eq__
__floordiv__
__hash__
__len__
__mod__
__mul__
__ne__
__neg__
__sub__
evaluate(x)
degree()
    Returns the degree of the polynomial
get_coefficient(degree)
    Returns the coefficient of the specified term

ff.GF2int(value)

此对象的实例是GF(2^p)域的元素，实例是范围0到(2^p)-1的整数。默认情况下，域是GF(2^8)，实例是范围0到255的整数，并使用不可约多项式0x11b定义，其二进制形式为：x^8 + x^4 + x^3 + x + 1，并使用3作为指数表和日志表的生成器。

但是，您可以使用其他参数为伽罗瓦域，使用init_lut()函数。

ff.find_prime_polynomials(generator=2, c_exp=8, fast_primes=False, single=False)

找到用于为您字段生成查找表的素多项式列表。

ff.init_lut(generator=3, prim=0x11b, c_exp=8)

给定参数生成查找表。这实际上为您的高斯域（即，生成器=2，prim=0x1002d，c_exp=16）生成一个GF(2^16)域。

GF2int类继承自int并支持所有常规整数操作。以下方法被覆盖，用于有限域GF(2^p)中的算术

__add__
__div__
__mul__
__neg__
__pow__
__radd__
__rdiv__
__rmul__
__rsub__
__sub__
inverse()
    Multiplicative inverse in GF(2^p)

边缘情况

尽管在可能和资源消耗不过度的情况下实施了合理性检查，但在某些情况下，如果不引发异常，则消息将无法正确解码

• 如果提供了不正确的擦除位置，则解码算法将仅信任提供的位置并创建一个错误的校验和，从而导致解码消息不正确。在可靠性至关重要的情况下，始终在解码后使用check()方法检查解码是否出错。

• 里德-所罗门算法受Singleton Bound的限制，这不仅限制了它相对于纠错符号数量的纠错和擦除能力，还限制了它检查消息是否可解码的能力。实际上，如果错误和擦除的数量大于Singleton Bound，解码器就无法从数学上确切地知道是否存在错误，它可能非常可能是有效的消息（尽管不是你期望的消息，但从数学上来说是有效的）。因此，当消息被篡改超过Singleton Bound时，解码器可能会抛出异常，但也可能返回一个数学上有效但仍然被篡改的消息。使用check()方法也无法解决这个问题。为了解决这个问题，一种解决方案是并行使用奇偶校验或哈希函数与里德-所罗门编解码器：使用里德-所罗门编解码器修复消息，使用奇偶校验或哈希函数检查是否存在错误。由于奇偶校验和哈希函数的工作方式，它们产生假阴性的可能性比里德-所罗门算法小得多。这是一个普遍的规则：纠错码在纠正消息方面效率很高，但在检测错误方面效率不高，哈希和奇偶校验函数是这一目的的合适工具。

示例实现

使用unireedsolomon的项目

• 一些学术出版物使用了unireedsolomon，参见此列表。

推荐阅读

• “为编码者设计的里德-所罗门码”，WikiVersity上提供的免费实用入门教程，包含Python代码示例。部分由本软件的作者之一编写。

• “数据传输的代数码”，Blahut, Richard E.，2003，剑桥大学出版社。可在Google Books上在线阅读[在线阅读]。本书在帮助理解通用Berlekamp-Massey算法的复杂性方面起到了关键作用（参见第7.5图和第7.10图）。

作者和许可

由Andrew Brown从头编写 <brownan@gmail.com> <brownan@cs.duke.edu> （c）2010。

由Stephen Karl Larroque在2015-2020年升级和维护 <LRQ3000@gmail.com>。

在MIT许可证下发布。