Sudoku error correction

Forward error correction (FEC) is a method of adding extra information (redundancy) to a message so that if any part is lost the data can be reconstructed without re-requesting from the sender. In a network protocol this is advantageous when either there is a significant number of receivers, e.g. internet radio, or the communications link to the sender is slow or expensive, e.g. deep space probes.

As a terse example of FEC, if a message comprised of nine numbers 1-9, and we added eight redundant numbers we end up with something like a Sudoku board:

As per the rules of Sudoku, if some numbers were missing we could determine the lost numbers from the neighbours on the same line or box.

Reed-Solomon encoding creates a graph based on a polynomial function that each point matches a byte in the data stream, x is the location in the stream, y is the value. For example, in the polynomial graph below imagine every red point being a byte of information in a transmission group. The graph can be extended to include extra data points, here marked in green. These points are extra redundant information, called parity data. As the parity points follow the same line it is possible to use these points to re-construct the original graph polynomial function. Once this function is calculated any missing real data points can be recovered by substituting the x location values.

The benefit over convential selective "Automatic Repeat reQuest" (ARQ), is that one parity point can recover any one lost original data point. The disadvantage is the extra time to perform the calculations, however in hardware systems these calculations can be implemented directly in hardware using a slightly different form called BCH Code.

Both forms of code are popular in software projects, notable examples include Luigi Rizzo's RMDP, Peter Brian Clements PAR Parity Archives, and Phil Karn's DSP and FEC library (e.g. Linux software modems). However the results are in different forms, Vandermonde calculations produce vector space coefficients, and BCH's Linear Shift Feedback Register produces polynomial space coefficients. Microsoft's PGM implementation uses Rizzo's implementation, and so for initial compatibility OpenPGM will use a Vandermonde matrix calculation.