An interactive demo of Reed-Solomon error correction coding. The demo shows the workings of the CODEC in detail and allows the user to configure the RS code parameters and test case.

Get the OCaml library and demo code on github.

Introduction

Reed-Solomon (RS) codes are a forward error correction technique that allows a communications system to detect and correct transmission errors. RS codes are generally systematic block codes and are defined by the following parameters.

• symbol size in bits (\$m\$)
• message size in symbols (\$k\$)
• code word size in symbols (\$n\$)
• number of correctable symbols (\$t\$)

The following relationships exist between these parameters;

\[ n = 2^m-1 \]

\[ n - k = 2t \]

From an encoding point of view we take \$m\$ bits to form a symbol and \$k\$ symbols to form a message. The encoder then calculates \$2t\$ symbols which are appended to the message to form the code word which is transmitted (\$k+2t\$ = \$n\$ symbols, or \$nm\$ bits).

The decoder receives \$n\$ symbols and if there are \$t\$ or less corrupt symbols it will correctly reproduce the initial message of \$k\$ symbols.

The theory of RS codes is well explained in this BBC whitepaper among various other resources.

Configuration

Start by configuring the code parameters. Set \$m\$, the symbol size in bits, and \$t\$, the error correction capability of the code. Optionally the initial root, \$b\$, of the generator polynomial can be set.

Next configure the specific Galois field to use by providing the primitive polynomial and element. These are specified in decimal form.

Finally the message and error patterns are configured.

m = , t =

Galois Field configuration

Primitive polynomial = , Primitive element =

Initial root b =

Reed-Solomon algorithm

Click calculate to run the Reed-Solomon CODEC. Polynomial coefficients can be displayed in either decimal form or as powers of the primitive element, and may be rendered in either ascending or descending order.

Decimal Descending

\[M(x) = \]

\[E(x) = \]

\[G(x) = \]

Code word

\[T(x) = \]

\[M(x)x^{2t} + (M(x)x^{2t} mod G(x)) = \]

\[S(x) = \]

Euclid

The final step will generate \$s_{n} = γΛ(x)\$ and \$r_{n} = γΩ(x)\$. To get normalized form divide both polynomials by the constant coefficient of \$s_{n}\$.

\$\$Λ(x) = \$\$

\$\$Ω(x) = \$\$

Forney

\$\$ Y_{j} = X_{j}^{1-b}{Ω(X_{j}^{-1})} / {Λ'(X_{j}^{-1})} = \$\$

Calculated error polynomial

\$\$ E_{calc}(x) = \$\$

Corrected polynomial

\$\$ R_{calc}(x) = R(x) + E_{calc}(x) = \$\$