UniReedSolomon
==============
|PyPI-Status| |PyPI-Versions| |PyPI-Downloads|
|Build-Status| |Coverage|
UniReedSolomon is a pure-Python universal Reed-Solomon error correction codec with fully documented code and mathematical nomenclatura, compatible with Python 2.7 up to 3.8 and also PyPy 2 and 3.
If you are just starting with Reed-Solomon error correction codes, please see the `Wikiversity tutorial <https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders>`_.
------------------------------------
.. contents:: Table of contents
:backlinks: top
:local:
Installation
------------
.. code:: sh
pip install --upgrade unireedsolomon
.. note::
When installing from source using ``python setup.py install``, the setup.py will try to build the Cython optimized module ``cff.pyx`` and ``cpolynomial.pyx`` if both Cython and a C compiler (eg, gcc) are installed, which provides ~4x speed boost during encoding. Although it should be done by default if Cython is installed, the compilation of Cython modules can be forced with ``python setup.py build_ext --inplace``. You can override this behavior by typing: ``python setup.py install --nocython`` to force the install only the pure python module without building the Cython modules.
Pre-transpiled ``cff.c`` and ``cpolynomial.c`` files are also available, and can be compiled with a C compiler without Cython by typing: ``python setup.py install --compile``.
Quickstart
----------
>>> 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!'
Description
-----------
This library implements a pure-Python documented universal Reed-Solomon
error correction codec with a mathematical nomenclatura, compatible with
Python 2.7 up to 3.7+ and also with PyPy 2 and PyPy 3.
The project aims to keep a well commented and organized code with
an extensive documentation and mathematical clarity of the various
arithmetic operations.
How does this library differs from other Reed-Solomon libraries?
* **universal**: compatibility with (almost) any other Reed-Solomon codec. This means that you can choose the parameters so that you can either encode data and decode it with another RS codec, or on the opposite encode data with another RS codec and decode this data with this library.
* **errors-and-erasures decoding** allows to decode both erasures (where you know the position of the corrupted characters) and errors (where you don't know where are the corrupted characters) at the same time (because you can decode more erasures than errors, so if you can provide even a few know corrupted characters positions, this can help a lot the decoder to repair the message).
* **documented**: following literate programming guidelines, you should understand everything you need about RS by reading the code and the comments.
* **mathematical nomenclatura**: for example, contrary to most other RS libraries, you will see a clear distinction between the different mathematical constructs, such as the Galois Fields numbers are clearly separated from the generic Polynomial objects, and both are separated from the Reed-Solomon algorithm, which makes use of both of those constructs. For this purpose, object-oriented programming was chosen to design the architecture of the library, although obviously at the expense of a bit of performance. However, this library favors mathematical clarity and documentation over performance (even if performance is optimized whenever possible).
* **pure-Python** means that there are no dependencies whatsoever apart from the Python interpreter. This means that this library should be resilient in the future (since it doesn't depend on external libraries who can become broken with time, see software rot), and you can use it on any system where Python can be installed (including online cloud services).
The authors tried their best to extensively document the algorithms.
However, a lot of the math involved is non-trivial and we can't explain it all
in the comments. To learn more about the algorithms, see these resources:
* `<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>`_
Also, here's a copy of the presentation one of the authors gave to the class Spring 2010 on his
experience implementing this library. The LaTeX source is in the presentation directory.
`<http://www.cs.duke.edu/courses/spring10/cps296.3/decoding_rs.pdf>`_
The code was lately updated to support errors-and-erasures decoding (both at the same
time), and to be universal (you can supply the parameters to be compatible with almost
any other RS codec).
The codec has decent performances if you use PyPy with the fast methods (~1 MB/s),
but it would be faster if we drop the object-oriented design (implementing everything in
functions), but this would be at the expense of mathematical clarity. If you are interested,
see the reedsolo library by Tomer Filiba, which is exactly the same implementation but
only functional without objects (results in about 5x speedup).
Files
-----
rs.py
Holds the Reed-Solomon Encoder/Decoder object
polynomial.py
Contains the Polynomial object (pure-python)
ff.py
Contains the GF2int object representing an element of the GF(2^p) field, with p being 8 by default (pure-python)
polynomial.pyx
Cython implementation of polynomial.py with equivalent functions (optional)
ff.pyx
Cython implementation of ff.py with equivalent functions (optional)
Documentation
-------------
unireedsolomon.rs.RSCoder(n, k, generator=3, prim=0x11b, fcr=1, c_exp=8)
Creates a new Reed-Solomon Encoder/Decoder object configured with
the given n and k values.
n is the length of a codeword, must be less than 256
k is the length of the message, must be less than n
generator, prim and fcr parametrize the Galois Field that will be built
c_exp is the Galois Field range (ie, 8 means GF(2^8) = GF(256)), which is both the limit for one symbol's value, and the maximum length of a message+ecc.
The code will have error correcting power (ie, maximum number of repairable symbols) of `2*e+v <= (n-k)`, where e is the number of errors and v the number of erasures.
The typical RSCoder is RSCoder(255, 223)
RSCoder.encode(message, poly=False, k=None)
Encode a given string with reed-solomon encoding. Returns a byte
string with the k message bytes and n-k parity bytes at the end.
If a message is < k bytes long, it is assumed to be padded at the front
with null bytes (ie, a shortened Reed-Solomon code).
The sequence returned is always n bytes long.
If poly is not False, returns the encoded Polynomial object instead of
the polynomial translated back to a string (useful for debugging)
You can change the length (number) of parity/ecc bytes at encoding
by setting k to any value between [1, n-1]. This allows to create only
one RSCoder and then use it with a variable redundancy rate.
RSCoder.encode_fast(message, poly=False, k=None)
Same as encode() but using faster algorithms and optimization tricks.
RSCoder.decode(message_ecc, nostrip=False, k=None, erasures_pos=None, only_erasures=False):
Given a received string or byte array message_ecc (composed of
a message string + ecc symbols at the end), attempts to decode it.
If it's a valid codeword, or if there are no more than `2*e+v <= (n-k)` erratas
(called the Singleton bound), the message is returned.
You can provide the erasures positions as a list to erasures_pos.
For example, if you have "hella warld" and you know that `a` is an erasure,
you can provide the list erasures_pos=[4, 7]. You can correct twice as many
erasures than errors, and if some provided erasures are wrong (they are correct
symbols), then there's no problem, they will be repaired just fine (but will count
towards the Singleton bound). You can also specify that you are sure there are
only erasures and no errors at all by setting only_erasures=True.
A message always has k bytes, if a message contained less it is left
padded with null bytes (punctured RS code). When decoded, these leading
null bytes are stripped, but that can cause problems if decoding binary data.
When nostrip is True, messages returned are always k bytes long. This is
useful to make sure no data is lost when decoding binary data.
Note that RS can correct errors both in the message and the ecc symbols.
RSCoder.decode_fast(message_ecc, nostrip=False, k=None, erasures_pos=None, only_erasures=False):
Same as decode() but using faster algorithms and optimization tricks.
RSCoder.check(message_ecc, k=None)
Verifies the codeword (message + ecc symbols at the end) is valid by testing
that the code as a polynomial code divides g, or that the syndrome is
all 0 coefficients. The result is not foolproof: if it's False, you're sure the
message was corrupted (or that you used the wrong RS parameters),
but if it's True, it's either that the message is correct, or that there are
too many errors (ie, more than the Singleton bound) for RS to do anything about it.
returns True/False
RSCoder.check_fast(message_ecc, k=None)
Same as check() but using faster algorithms and optimization tricks.
unireedsolomon.ff.find_prime_polynomials(generator=2, c_exp=8, fast_primes=False, single=False)
Compute the list of prime polynomials for the given generator and
galois field characteristic exponent. You can then use this prime polynomial
to specify the mandatory "prim" parameter, particularly if you are using
a larger Galois Field (eg, 2^16).
Internal API
-------------
Besides the main RSCoder object, two other objects are used in this
implementation: Polynomial and GF2int. Their use is not specifically tied
to the coder or even to the Reed-Solomon algorithm, they are just generic
mathematical constructs respectively representing polynomials and
Galois field's number of base 2.
You do not need to know about the internal API to use the RS codec,
this is just left as a documentation for the reader interested into dwelling
inside the mathematical constructs.
polynomial.Polynomial(coefficients=[], \**sparse)
There are three ways to initialize a Polynomial object.
1) With a list, tuple, or other iterable, creates a polynomial using
the items as coefficients in order of decreasing power
2) With keyword arguments such as for example x3=5, sets the
coefficient of x^3 to be 5
3) With no arguments, creates an empty polynomial, equivalent to
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 objects export the following standard functions that perform the
expected operations using polynomial arithmetic. Arithmetic of the coefficients
is determined by the type passed in, so integers or GF2int objects could be
used, the Polynomial class is agnostic to the type of the coefficients.
::
__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)
Instances of this object are elements of the field GF(2^p) and instances are integers
in the range 0 to `(2^p)-1`.
By default, the field is GF(2^8) and instances are integers in the range 0 to 255
and is defined using the irreducable polynomial 0x11b or in binary form:
x^8 + x^4 + x^3 + x + 1
and using 3 as the generator for the exponent table and log table.
You can however use other parameters for the Galois Field, using the
init_lut() function.
ff.find_prime_polynomials(generator=2, c_exp=8, fast_primes=False, single=False)
Find the list of prime polynomials to use to generate the look-up tables
for your field.
ff.init_lut(generator=3, prim=0x11b, c_exp=8)
Generate the look-up tables given the parameters. This effectively parametrize
your Galois Field (ie, generator=2, prim=0x1002d, c_exp=16) will generate
a GF(2^16) field.
The GF2int class inherits from int and supports all the usual integer
operations. The following methods are overridden for arithmetic in the finite
field GF(2^p)
::
__add__
__div__
__mul__
__neg__
__pow__
__radd__
__rdiv__
__rmul__
__rsub__
__sub__
inverse()
Multiplicative inverse in GF(2^p)
Example implementations
-----------------------
Image Encoder
~~~~~~~~~~~~~
imageencode.py is an example script that encodes codewords as rows in an image.
It requires PIL to run.
Usage: python imageencode.py [-d] <image file>
Without the -d flag, imageencode.py will encode text from standard in and
output it to the image file. With -d, imageencode.py will read in the data from
the image and output to standard out the decoded text.
An example is included: ``exampleimage.png``. Try decoding it as-is, then open
it up in an image editor and paint some vertical stripes on it. As long as no
more than 16 pixels per row are disturbed, the text will be decoded correctly.
Then draw more stripes such that more than 16 pixels per row are disturbed and
verify that the message is decoded improperly.
Notice how the parity data looks different--the last 32 pixels of each row are
colored differently. That's because this particular image contains encoded
ASCII text, which generally only has bytes from a small range (the alphabet and
printable punctuation). The parity data, however, is binary and contains bytes
from the full range 0-255. Also note that either the data area or the parity
area (or both!) can be disturbed as long as no more than 16 bytes per row are
disturbed.
Cython implementation
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
If either a C compiler or Cython is found, rs.py will automatically load the Cython implementations
(the \*.pyx files).
These are provided as optimized versions of the pure-python implementations, with equivalent
functionalities. The goal was to get a speedup, which is the case, but using PyPy on the pure-python
implementation provides a significantly higher speedup than the Cython implementation.
The Cython implementations are still provided for the interested reader, but the casual user is
not advised to use them. If you want to encode and decode fast, use PyPy.
Recommended reading
-------------------
* "`Reed-Solomon codes for coders <https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders>`_", free practical beginner's tutorial with Python code examples on WikiVersity. Partially written by one of the authors of the present software.
* "Algebraic codes for data transmission", Blahut, Richard E., 2003, Cambridge university press. `Readable online on Google Books <https://books.google.fr/books?id=eQs2i-R9-oYC&lpg=PR11&ots=atCPQJm3OJ&dq=%22Algebraic%20codes%20for%20data%20transmission%22%2C%20Blahut%2C%20Richard%20E.%2C%202003%2C%20Cambridge%20university%20press.&lr&hl=fr&pg=PA193#v=onepage&q=%22Algebraic%20codes%20for%20data%20transmission%22,%20Blahut,%20Richard%20E.,%202003,%20Cambridge%20university%20press.&f=false>`_. This book was pivotal in helping to understand the intricacies of the universal Berlekamp-Massey algorithm (see figures 7.5 and 7.10).
Authors and licence
-------------------
Written from scratch by Andrew Brown <brownan@gmail.com> <brownan@cs.duke.edu>
(c) 2010.
Upgraded and maintained by Stephen Karl Larroque <LRQ3000@gmail.com> in 2015-2020.
Licensed under the MIT License.
.. |PyPI-Status| image:: https://img.shields.io/pypi/v/unireedsolomon.svg
:target: https://pypi.org/project/unireedsolomon
.. |PyPI-Versions| image:: https://img.shields.io/pypi/pyversions/unireedsolomon.svg?logo=python&logoColor=white
:target: https://pypi.org/project/unireedsolomon
.. |PyPI-Downloads| image:: https://img.shields.io/pypi/dm/unireedsolomon.svg?label=pypi%20downloads&logo=python&logoColor=white
:target: https://pypi.org/project/unireedsolomon
.. |Build-Status| image:: https://travis-ci.org/lrq3000/unireedsolomon.svg?branch=master
:target: https://travis-ci.org/lrq3000/unireedsolomon
.. |Coverage| image:: https://coveralls.io/repos/lrq3000/unireedsolomon/badge.svg?branch=master&service=github
:target: https://coveralls.io/github/lrq3000/unireedsolomon?branch=master
Raw data
{
"_id": null,
"home_page": "https://github.com/lrq3000/unireedsolomon",
"name": "unireedsolomon",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "error correction erasure reed solomon repair file network packet",
"author": "Andrew Brown, Stephen Larroque",
"author_email": "lrq3000@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/67/3e/ae82790513175c8faa50d656ad79cbe8412ad63fba9168807dfdeac11197/unireedsolomon-1.0.5.tar.gz",
"platform": "any",
"description": "UniReedSolomon\n==============\n\n|PyPI-Status| |PyPI-Versions| |PyPI-Downloads|\n\n|Build-Status| |Coverage|\n\nUniReedSolomon is a pure-Python universal Reed-Solomon error correction codec with fully documented code and mathematical nomenclatura, compatible with Python 2.7 up to 3.8 and also PyPy 2 and 3.\n\nIf you are just starting with Reed-Solomon error correction codes, please see the `Wikiversity tutorial <https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders>`_.\n\n------------------------------------\n\n.. contents:: Table of contents\n :backlinks: top\n :local:\n\n\nInstallation\n------------\n\n.. code:: sh\n\n pip install --upgrade unireedsolomon\n\n.. note::\n\n When installing from source using ``python setup.py install``, the setup.py will try to build the Cython optimized module ``cff.pyx`` and ``cpolynomial.pyx`` if both Cython and a C compiler (eg, gcc) are installed, which provides ~4x speed boost during encoding. Although it should be done by default if Cython is installed, the compilation of Cython modules can be forced with ``python setup.py build_ext --inplace``. You can override this behavior by typing: ``python setup.py install --nocython`` to force the install only the pure python module without building the Cython modules.\n\n Pre-transpiled ``cff.c`` and ``cpolynomial.c`` files are also available, and can be compiled with a C compiler without Cython by typing: ``python setup.py install --compile``.\n\nQuickstart\n----------\n>>> import unireedsolomon as rs\n>>> coder = rs.RSCoder(20,13)\n>>> c = coder.encode(\"Hello, world!\")\n>>> print repr(c)\n'Hello, world!\\x8d\\x13\\xf4\\xf9C\\x10\\xe5'\n>>>\n>>> r = \"\\0\"*3 + c[3:]\n>>> print repr(r)\n'\\x00\\x00\\x00lo, world!\\x8d\\x13\\xf4\\xf9C\\x10\\xe5'\n>>>\n>>> coder.decode(r)\n'Hello, world!'\n\nDescription\n-----------\nThis library implements a pure-Python documented universal Reed-Solomon\nerror correction codec with a mathematical nomenclatura, compatible with\nPython 2.7 up to 3.7+ and also with PyPy 2 and PyPy 3.\n\nThe project aims to keep a well commented and organized code with\nan extensive documentation and mathematical clarity of the various\narithmetic operations.\n\nHow does this library differs from other Reed-Solomon libraries?\n\n* **universal**: compatibility with (almost) any other Reed-Solomon codec. This means that you can choose the parameters so that you can either encode data and decode it with another RS codec, or on the opposite encode data with another RS codec and decode this data with this library.\n* **errors-and-erasures decoding** allows to decode both erasures (where you know the position of the corrupted characters) and errors (where you don't know where are the corrupted characters) at the same time (because you can decode more erasures than errors, so if you can provide even a few know corrupted characters positions, this can help a lot the decoder to repair the message).\n* **documented**: following literate programming guidelines, you should understand everything you need about RS by reading the code and the comments.\n* **mathematical nomenclatura**: for example, contrary to most other RS libraries, you will see a clear distinction between the different mathematical constructs, such as the Galois Fields numbers are clearly separated from the generic Polynomial objects, and both are separated from the Reed-Solomon algorithm, which makes use of both of those constructs. For this purpose, object-oriented programming was chosen to design the architecture of the library, although obviously at the expense of a bit of performance. However, this library favors mathematical clarity and documentation over performance (even if performance is optimized whenever possible).\n* **pure-Python** means that there are no dependencies whatsoever apart from the Python interpreter. This means that this library should be resilient in the future (since it doesn't depend on external libraries who can become broken with time, see software rot), and you can use it on any system where Python can be installed (including online cloud services).\n\nThe authors tried their best to extensively document the algorithms.\nHowever, a lot of the math involved is non-trivial and we can't explain it all\nin the comments. To learn more about the algorithms, see these resources:\n\n* `<http://en.wikipedia.org/wiki/Reed\u00e2\u20ac\u201cSolomon_error_correction>`_\n* `<http://www.cs.duke.edu/courses/spring10/cps296.3/rs_scribe.pdf>`_\n* `<http://www.cs.duke.edu/courses/spring10/cps296.3/decoding_rs_scribe.pdf>`_\n* `<http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/reed_solomon.ps>`_\n* `<http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/rs_decode.ps>`_\n\nAlso, here's a copy of the presentation one of the authors gave to the class Spring 2010 on his\nexperience implementing this library. The LaTeX source is in the presentation directory.\n\n`<http://www.cs.duke.edu/courses/spring10/cps296.3/decoding_rs.pdf>`_\n\nThe code was lately updated to support errors-and-erasures decoding (both at the same\ntime), and to be universal (you can supply the parameters to be compatible with almost\nany other RS codec).\n\nThe codec has decent performances if you use PyPy with the fast methods (~1 MB/s),\nbut it would be faster if we drop the object-oriented design (implementing everything in\nfunctions), but this would be at the expense of mathematical clarity. If you are interested,\nsee the reedsolo library by Tomer Filiba, which is exactly the same implementation but\nonly functional without objects (results in about 5x speedup).\n\nFiles\n-----\nrs.py\n Holds the Reed-Solomon Encoder/Decoder object\n\npolynomial.py\n Contains the Polynomial object (pure-python)\n\nff.py\n Contains the GF2int object representing an element of the GF(2^p) field, with p being 8 by default (pure-python)\n\npolynomial.pyx\n Cython implementation of polynomial.py with equivalent functions (optional)\n\nff.pyx\n Cython implementation of ff.py with equivalent functions (optional)\n\nDocumentation\n-------------\nunireedsolomon.rs.RSCoder(n, k, generator=3, prim=0x11b, fcr=1, c_exp=8)\n Creates a new Reed-Solomon Encoder/Decoder object configured with\n the given n and k values.\n n is the length of a codeword, must be less than 256\n k is the length of the message, must be less than n\n generator, prim and fcr parametrize the Galois Field that will be built\n c_exp is the Galois Field range (ie, 8 means GF(2^8) = GF(256)), which is both the limit for one symbol's value, and the maximum length of a message+ecc.\n\n The code will have error correcting power (ie, maximum number of repairable symbols) of `2*e+v <= (n-k)`, where e is the number of errors and v the number of erasures.\n\n The typical RSCoder is RSCoder(255, 223)\n\nRSCoder.encode(message, poly=False, k=None)\n Encode a given string with reed-solomon encoding. Returns a byte\n string with the k message bytes and n-k parity bytes at the end.\n\n If a message is < k bytes long, it is assumed to be padded at the front\n with null bytes (ie, a shortened Reed-Solomon code).\n\n The sequence returned is always n bytes long.\n\n If poly is not False, returns the encoded Polynomial object instead of\n the polynomial translated back to a string (useful for debugging)\n\n You can change the length (number) of parity/ecc bytes at encoding\n by setting k to any value between [1, n-1]. This allows to create only\n one RSCoder and then use it with a variable redundancy rate.\n\nRSCoder.encode_fast(message, poly=False, k=None)\n Same as encode() but using faster algorithms and optimization tricks.\n\nRSCoder.decode(message_ecc, nostrip=False, k=None, erasures_pos=None, only_erasures=False):\n Given a received string or byte array message_ecc (composed of\n a message string + ecc symbols at the end), attempts to decode it.\n If it's a valid codeword, or if there are no more than `2*e+v <= (n-k)` erratas\n (called the Singleton bound), the message is returned.\n\n You can provide the erasures positions as a list to erasures_pos.\n For example, if you have \"hella warld\" and you know that `a` is an erasure,\n you can provide the list erasures_pos=[4, 7]. You can correct twice as many\n erasures than errors, and if some provided erasures are wrong (they are correct\n symbols), then there's no problem, they will be repaired just fine (but will count\n towards the Singleton bound). You can also specify that you are sure there are\n only erasures and no errors at all by setting only_erasures=True.\n\n A message always has k bytes, if a message contained less it is left\n padded with null bytes (punctured RS code). When decoded, these leading\n null bytes are stripped, but that can cause problems if decoding binary data.\n When nostrip is True, messages returned are always k bytes long. This is\n useful to make sure no data is lost when decoding binary data.\n\n Note that RS can correct errors both in the message and the ecc symbols.\n\nRSCoder.decode_fast(message_ecc, nostrip=False, k=None, erasures_pos=None, only_erasures=False):\n Same as decode() but using faster algorithms and optimization tricks.\n\nRSCoder.check(message_ecc, k=None)\n Verifies the codeword (message + ecc symbols at the end) is valid by testing\n that the code as a polynomial code divides g, or that the syndrome is\n all 0 coefficients. The result is not foolproof: if it's False, you're sure the\n message was corrupted (or that you used the wrong RS parameters),\n but if it's True, it's either that the message is correct, or that there are\n too many errors (ie, more than the Singleton bound) for RS to do anything about it.\n returns True/False\n\nRSCoder.check_fast(message_ecc, k=None)\n Same as check() but using faster algorithms and optimization tricks.\n\nunireedsolomon.ff.find_prime_polynomials(generator=2, c_exp=8, fast_primes=False, single=False)\n Compute the list of prime polynomials for the given generator and\n galois field characteristic exponent. You can then use this prime polynomial\n to specify the mandatory \"prim\" parameter, particularly if you are using\n a larger Galois Field (eg, 2^16).\n\n\nInternal API\n-------------\nBesides the main RSCoder object, two other objects are used in this\nimplementation: Polynomial and GF2int. Their use is not specifically tied\nto the coder or even to the Reed-Solomon algorithm, they are just generic\nmathematical constructs respectively representing polynomials and\nGalois field's number of base 2.\n\nYou do not need to know about the internal API to use the RS codec,\nthis is just left as a documentation for the reader interested into dwelling\ninside the mathematical constructs.\n\npolynomial.Polynomial(coefficients=[], \\**sparse)\n There are three ways to initialize a Polynomial object.\n 1) With a list, tuple, or other iterable, creates a polynomial using\n the items as coefficients in order of decreasing power\n\n 2) With keyword arguments such as for example x3=5, sets the\n coefficient of x^3 to be 5\n\n 3) With no arguments, creates an empty polynomial, equivalent to\n Polynomial([0])\n\n >>> print Polynomial([5, 0, 0, 0, 0, 0])\n 5x^5\n\n >>> print Polynomial(x32=5, x64=8)\n 8x^64 + 5x^32\n\n >>> print Polynomial(x5=5, x9=4, x0=2) \n 4x^9 + 5x^5 + 2\n\nPolynomial objects export the following standard functions that perform the\nexpected operations using polynomial arithmetic. Arithmetic of the coefficients\nis determined by the type passed in, so integers or GF2int objects could be\nused, the Polynomial class is agnostic to the type of the coefficients.\n\n::\n\n __add__\n __divmod__\n __eq__\n __floordiv__\n __hash__\n __len__\n __mod__\n __mul__\n __ne__\n __neg__\n __sub__\n evaluate(x)\n degree()\n Returns the degree of the polynomial\n get_coefficient(degree)\n Returns the coefficient of the specified term\n\nff.GF2int(value)\n Instances of this object are elements of the field GF(2^p) and instances are integers\n in the range 0 to `(2^p)-1`.\n By default, the field is GF(2^8) and instances are integers in the range 0 to 255\n and is defined using the irreducable polynomial 0x11b or in binary form:\n x^8 + x^4 + x^3 + x + 1\n and using 3 as the generator for the exponent table and log table.\n\n You can however use other parameters for the Galois Field, using the\n init_lut() function.\n\nff.find_prime_polynomials(generator=2, c_exp=8, fast_primes=False, single=False)\n Find the list of prime polynomials to use to generate the look-up tables\n for your field.\n\nff.init_lut(generator=3, prim=0x11b, c_exp=8)\n Generate the look-up tables given the parameters. This effectively parametrize\n your Galois Field (ie, generator=2, prim=0x1002d, c_exp=16) will generate\n a GF(2^16) field.\n\nThe GF2int class inherits from int and supports all the usual integer\noperations. The following methods are overridden for arithmetic in the finite\nfield GF(2^p)\n\n::\n\n __add__\n __div__\n __mul__\n __neg__\n __pow__\n __radd__\n __rdiv__\n __rmul__\n __rsub__\n __sub__\n inverse()\n Multiplicative inverse in GF(2^p)\n\nExample implementations\n-----------------------\n\nImage Encoder\n~~~~~~~~~~~~~\nimageencode.py is an example script that encodes codewords as rows in an image.\nIt requires PIL to run.\n\nUsage: python imageencode.py [-d] <image file>\n\nWithout the -d flag, imageencode.py will encode text from standard in and\noutput it to the image file. With -d, imageencode.py will read in the data from\nthe image and output to standard out the decoded text.\n\nAn example is included: ``exampleimage.png``. Try decoding it as-is, then open\nit up in an image editor and paint some vertical stripes on it. As long as no\nmore than 16 pixels per row are disturbed, the text will be decoded correctly.\nThen draw more stripes such that more than 16 pixels per row are disturbed and\nverify that the message is decoded improperly.\n\nNotice how the parity data looks different--the last 32 pixels of each row are\ncolored differently. That's because this particular image contains encoded\nASCII text, which generally only has bytes from a small range (the alphabet and\nprintable punctuation). The parity data, however, is binary and contains bytes\nfrom the full range 0-255. Also note that either the data area or the parity\narea (or both!) can be disturbed as long as no more than 16 bytes per row are\ndisturbed.\n\nCython implementation\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\nIf either a C compiler or Cython is found, rs.py will automatically load the Cython implementations\n(the \\*.pyx files).\nThese are provided as optimized versions of the pure-python implementations, with equivalent\nfunctionalities. The goal was to get a speedup, which is the case, but using PyPy on the pure-python\nimplementation provides a significantly higher speedup than the Cython implementation.\nThe Cython implementations are still provided for the interested reader, but the casual user is\nnot advised to use them. If you want to encode and decode fast, use PyPy.\n\nRecommended reading\n-------------------\n\n* \"`Reed-Solomon codes for coders <https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders>`_\", free practical beginner's tutorial with Python code examples on WikiVersity. Partially written by one of the authors of the present software.\n* \"Algebraic codes for data transmission\", Blahut, Richard E., 2003, Cambridge university press. `Readable online on Google Books <https://books.google.fr/books?id=eQs2i-R9-oYC&lpg=PR11&ots=atCPQJm3OJ&dq=%22Algebraic%20codes%20for%20data%20transmission%22%2C%20Blahut%2C%20Richard%20E.%2C%202003%2C%20Cambridge%20university%20press.&lr&hl=fr&pg=PA193#v=onepage&q=%22Algebraic%20codes%20for%20data%20transmission%22,%20Blahut,%20Richard%20E.,%202003,%20Cambridge%20university%20press.&f=false>`_. This book was pivotal in helping to understand the intricacies of the universal Berlekamp-Massey algorithm (see figures 7.5 and 7.10).\n\nAuthors and licence\n-------------------\nWritten from scratch by Andrew Brown <brownan@gmail.com> <brownan@cs.duke.edu>\n(c) 2010.\n\nUpgraded and maintained by Stephen Karl Larroque <LRQ3000@gmail.com> in 2015-2020.\n\nLicensed under the MIT License.\n\n\n.. |PyPI-Status| image:: https://img.shields.io/pypi/v/unireedsolomon.svg\n :target: https://pypi.org/project/unireedsolomon\n.. |PyPI-Versions| image:: https://img.shields.io/pypi/pyversions/unireedsolomon.svg?logo=python&logoColor=white\n :target: https://pypi.org/project/unireedsolomon\n.. |PyPI-Downloads| image:: https://img.shields.io/pypi/dm/unireedsolomon.svg?label=pypi%20downloads&logo=python&logoColor=white\n :target: https://pypi.org/project/unireedsolomon\n.. |Build-Status| image:: https://travis-ci.org/lrq3000/unireedsolomon.svg?branch=master\n :target: https://travis-ci.org/lrq3000/unireedsolomon\n.. |Coverage| image:: https://coveralls.io/repos/lrq3000/unireedsolomon/badge.svg?branch=master&service=github\n :target: https://coveralls.io/github/lrq3000/unireedsolomon?branch=master\n\n\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Universal errors-and-erasures Reed Solomon codec (error correcting code) in pure Python with extensive documentation",
"version": "1.0.5",
"split_keywords": [
"error",
"correction",
"erasure",
"reed",
"solomon",
"repair",
"file",
"network",
"packet"
],
"urls": [
{
"comment_text": "",
"digests": {
"md5": "64fec932d603a907ab254cd261496662",
"sha256": "355223ad1c826cba96e220b21c907d4fecee88e1a3c301a113b52f1af43ef68f"
},
"downloads": -1,
"filename": "unireedsolomon-1.0.5-py3-none-any.whl",
"has_sig": false,
"md5_digest": "64fec932d603a907ab254cd261496662",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 60613,
"upload_time": "2021-01-06T05:51:19",
"upload_time_iso_8601": "2021-01-06T05:51:19.333323Z",
"url": "https://files.pythonhosted.org/packages/4f/67/d60e23bfea0e05780fbd20c22571a5b28abd8c61186bf1e48b636ec7e5e9/unireedsolomon-1.0.5-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"md5": "3bdff4701c11df55eff6f732912c8367",
"sha256": "1aece5e33e71058430eacdab67fa06948ae0b5a7d82094a03fbce6e8f63b0b1e"
},
"downloads": -1,
"filename": "unireedsolomon-1.0.5.tar.gz",
"has_sig": false,
"md5_digest": "3bdff4701c11df55eff6f732912c8367",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 74609,
"upload_time": "2021-01-06T05:51:20",
"upload_time_iso_8601": "2021-01-06T05:51:20.724361Z",
"url": "https://files.pythonhosted.org/packages/67/3e/ae82790513175c8faa50d656ad79cbe8412ad63fba9168807dfdeac11197/unireedsolomon-1.0.5.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2021-01-06 05:51:20",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "lrq3000",
"github_project": "unireedsolomon",
"travis_ci": true,
"coveralls": true,
"github_actions": false,
"requirements": [],
"lcname": "unireedsolomon"
}
JSON
