Module datamatrix::errorcode[−][src]

Reed-Solomon error correction codes.

The error correction in a Data Matrix is done using Reed-Solomon codes.

Assuming you have never heard of coding theory: By putting some redundancy into the Data Matrix one can recover from, say, detection or printing errors when trying to read a Data Matrix. 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 way to compute the error code (called encoding), there are several algorithms for error correction (called decoding).

The decoder implemented in this module is syndrome based. Such a decoder is classically made of four main steps:

  1. Compute the syndrome values.
  2. Compute the error locator polynomial
  3. Compute the error locations.
  4. Compute the error values.

We use a Levinson-Durbin algorithm in the second step. See the article "Levinson-Durbin Algorithm Used For Fast BCH Decoding" by Michael Schmidt and Gerhard P. Fettweis. This approach was empiricially verified to be better than a LU decomposition and it did also beat the Berlekamp-Massey algorithm (about 10% faster).

Furthermore, in step four the Björck-Pereyra algorithm is used to determine the error values. It was faster than Forney's algorithm and also faster than a naive LU decomposition in our tests.

The other possibilites mentionend for step 2 and 4 are still in the source code in case someone is interested in them.

Enums

ErrorDecodingError

Signals a failure when correcting errors.

Functions

decode_error

Decode the Reed-Solomon code using a syndrome based decoder.

encode_error

Compute the Reed-Solomon code used by Data Matrix for error correction.