pyreedsolomon

renamed readme to rest format, cleaned up formatting

Files changed (2)

`+Reed Solomon Encoder and Decoder written in pure Python`
`+=======================================================`
`+`
`+Written from scratch by Andrew Brown <brownan@gmail.com> <brownan@cs.duke.edu>`
`+(c) 2010`
`+`
`+I wrote this code as an exercise in implementing the Reed-Solomon error`
`+correction algorithm. This code is published in the hopes that it will be`
`+useful for others in learning how the algorithm works. (Nothing helps me learn`
`+something better than a good example!)`
`+`
`+My goal was to implement a working Reed-Solomon encoder and decoder in pure`
`+python using no non-standard libraries. I also aimed to keep the code fairly`
`+well commented and organized.`
`+`
`+However, a lot of the math involved is non-trivial and I can't explain it all`
`+in my comments. To learn more about the algorithm, 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`
`+`
`+The last two resources are course notes from Bruce Maggs' class, which I took`
`+this past semester. Those notes were immensely useful and should be read by`
`+anyone wanting to learn the algorithm.`
`+`
`+Last two at Dr. Maggs' old site:`
`+`
`+* 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 I gave to the class Spring 2010 on my`
`+experience implementing this. The LaTeX source is in the presentation`
`+directory.`
`+`
`+http://www.cs.duke.edu/courses/spring10/cps296.3/decoding_rs.pdf`
`+`
`+Files`
`+-----`
`+rs.py`
`+    Holds the Reed-Solomon Encoder/Decoder object`
`+`
`+polynomial.py`
`+    Contains the Polynomial object`
`+`
`+ff.py`
`+    Contains the GF256int object representing an element of the GF(2^8) field`
`+`
`+Documentation`
`+-------------`
`+rs.RSCoder(n, k)`
`+     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`
`+     `
`+     The code will have error correcting power s where 2s = n - k`
`+     `
`+     The typical RSCoder is RSCoder(255, 223)`
`+ `
`+RSCoder Objects`
`+`
`+RSCoder.encode(message, poly=False)`
`+    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.`
`+    `
`+    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)`
`+    `
`+RSCoder.decode(r, nostrip=False)`
`+    Given a received string or byte array r, attempts to decode it. If`
`+    it's a valid codeword, or if there are no more than (n-k)/2 errors, the`
`+    message is returned.`
`+    `
`+    A message always has k bytes, if a message contained less it is left`
`+    padded with null bytes. 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.`
`+`
`+RSCoder.verify(code)`
`+    Verifies the code is valid by testing that the code as a polynomial`
`+    code divides g`
`+    returns True/False`
`+`
`+`
`+Besides the main RSCoder object, two other objects are used in this`
`+implementation. Their use is not specifically tied to the coder.`
`+`
`+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 GF256int 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.GF256int(value)`
`+    Instances of this object are elements of the field GF(2^8)`
`+    Instances are integers in the range 0 to 255`
`+    This field is defined using the irreducable polynomial`
`+    x^8 + x^4 + x^3 + x + 1`
`+    and using 3 as the generator for the exponent table and log table.`
`+`
`+The GF256int class inherits from int and supports all the usual integer`
`+operations. The following methods are overridden for arithmetic in the finite`
`+field GF(2^8)`
`+`
`+::`
`+`
`+    __add__`
`+    __div__`
`+    __mul__`
`+    __neg__`
`+    __pow__`
`+    __radd__`
`+    __rdiv__`
`+    __rmul__`
`+    __rsub__`
`+    __sub__`
`+    inverse()`
`+        Multiplicative inverse in GF(2^8)`
`+`
`+`
`+Examples`
`+--------`
`+>>> import 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!'`
`+`

`-Reed Solomon Encoder and Decoder written in pure Python`
`-=======================================================`
`-`
`-Written from scratch by Andrew Brown <brownan@gmail.com> <brownan@cs.duke.edu>`
`-(c) 2010`
`-`
`-I wrote this code as an exercise in implementing the Reed-Solomon error`
`-correction algorithm. This code is published in the hopes that it will be`
`-useful for others in learning how the algorithm works. (Nothing helps me learn`
`-something better than a good example!)`
`-`
`-My goal was to implement a working Reed-Solomon encoder and decoder in pure`
`-python using no non-standard libraries. I also aimed to keep the code fairly`
`-well commented and organized.`
`-`
`-However, a lot of the math involved is non-trivial and I can't explain it all`
`-in my comments. To learn more about the algorithm, 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`
`-`
`-The last two resources are course notes from Bruce Maggs' class, which I took`
`-this past semester. Those notes were immensely useful and should be read by`
`-anyone wanting to learn the algorithm.`
`-`
`-Last two at Dr. Maggs' old site:`
`-* 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 I gave to the class Spring 2010 on my`
`-experience implementing this. The LaTeX source is in the presentation`
`-directory.`
`-http://www.cs.duke.edu/courses/spring10/cps296.3/decoding_rs.pdf`
`-`
`-Files`
`------`
`-rs.py           Holds the Reed-Solomon Encoder/Decoder object`
`-polynomial.py   Contains the Polynomial object`
`-ff.py           Contains the GF256int object representing an element of the`
`-                GF(2^8) field`
`-`
`-Documentation`
`--------------`
`-rs.RSCoder(n, k)`
`-     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`
`-     `
`-     The code will have error correcting power s where 2s = n - k`
`-     `
`-     The typical RSCoder is RSCoder(255, 223)`
`- `
`-RSCoder Objects`
`-`
`- RSCoder.encode(message, poly=False)`
`-     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.`
`-     `
`-     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)`
`-     `
`- RSCoder.decode(r, nostrip=False)`
`-     Given a received string or byte array r, attempts to decode it. If`
`-     it's a valid codeword, or if there are no more than (n-k)/2 errors, the`
`-     message is returned.`
`-     `
`-     A message always has k bytes, if a message contained less it is left`
`-     padded with null bytes. 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.`
`- `
`- RSCoder.verify(code)`
`-     Verifies the code is valid by testing that the code as a polynomial`
`-     code divides g`
`-     returns True/False`
`-`
`-`
`-Besides the main RSCoder object, two other objects are used in this`
`-implementation. Their use is not specifically tied to the coder.`
`-`
`-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 GF256int 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.GF256int(value)`
`-    Instances of this object are elements of the field GF(2^8)`
`-    Instances are integers in the range 0 to 255`
`-    This field is defined using the irreducable polynomial`
`-    x^8 + x^4 + x^3 + x + 1`
`-    and using 3 as the generator for the exponent table and log table.`
`-`
`-The GF256int class inherits from int and supports all the usual integer`
`-operations. The following methods are overridden for arithmetic in the finite`
`-field GF(2^8)`
`-    __add__`
`-    __div__`
`-    __mul__`
`-    __neg__`
`-    __pow__`
`-    __radd__`
`-    __rdiv__`
`-    __rmul__`
`-    __rsub__`
`-    __sub__`
`-    inverse()`
`-        Multiplicative inverse in GF(2^8)`
`-`
`-`
`-Examples`
`---------`
`->>> import 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!'`
`-`
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.