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) = $$