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.
RS code parameters
m = , t =
Galois Field configuration
Primitive polynomial = , Primitive element =
Generator polynomial roots
Initial root b =
Message
Errors
Galois Field
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
Message
\[M(x) = \]
Errors
\[E(x) = \]
Generator
\[G(x) = \]
Code word
\[T(x) = \]
\[M(x)x^{2t} + (M(x)x^{2t} mod G(x)) = \]
Received code word
Syndromes
Syndrome polynomial
\[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}$.
Berlekamp-massey
Error locator polynomial
$$Λ(x) = $$
Error magnitude polynomial
$$Ω(x) = $$
Chein search
Solving for error locations
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) = $$