Module datamatrix::errorcode

Reed-Solomon error correction codes.

The error correction in a DataMatrix is done using so called Reed-Solomon codes.

Assuming you have never heard of coding theory: By putting some redundancy into the DataMatrix one can recover from, say, detection or printing errors when trying to read a DataMatrix. A clever way to add redundancy is the Reed-Solomon code. The details are relatively math heavy and involve for example "higher" algebra (Galois fields). Any book about coding theory should cover it, for example "Error Correction Coding: Mathematical Methods and Algorithms" by Moon.

While there is only possibility (in this case) for creating such an error code, there are several algorithms for using a code to correct errors, a processs also called decoding in coding theory.

The decoders implemented in this module are:

• A Peterson-Gorenstein-Zierler (PGZ) type algorithm.

  The implementation uses a Levinson-Durbin algorithm to determine the error locator polynomial. See the article "Levinson-Durbin Algorithm Used For Fasy BCH Decoding" by Michael Schmidt and Gerhard P. Fettweis. This approach was empiricially verified to be far superior over a classic LU decomposition.

  Furthermore, to determine the error values the Björck-Pereyra algorithm is used, which was much faster than Forney's algorithm or a naive LU decomposition in our tests.

• Berlekamp-Massey (TODO)

While only one decoder is exported in the API (see decode_block), the other implementations are still in the source code in case someone is interested in them.

Functions

decode_block	Decode the Reed-Solomon code using a PGZ type algorithm.
encode	Compute the Reed-Solomon code used by DataMatrix for error correction.