Module datamatrix::errorcode [−][src]
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. |