Polynomial Codes Over Certain Finite Fields

Original paper: Polynomial Codes Over Certain Finite Fields. Irving S Reed, and Gustave Solomon. 1960

The field \(\mathbb{Z}_{2}\) is a binary field \(\{0,1\}\). Let \(K\) be a finite field extension of \(\mathbb{Z}_{2}\) with \(2^{n}\) elements. We can also write this as \(K = \mathbb{Z}_{2}(\alpha)\) where \(\alpha\) is the root of an irreducible polynomial over \(\mathbb{Z}_{2}\). (see [BROKEN LINK: 3a5b4d34-0eaa-476c-88d9-753827f40c86])

Let there be \(m\) messages \(\{a_{1}, a_{2}, \ldots, a_{m}\}\subset K\).

Encoding:

1. Construct a polynomial \(p(\cdot)\) with all the messages \(a_{i}\) as coefficients.
2. Evaluate it on all the elements from \(K\).
3. The codewords are all the evaluations.

This transforms \(m\) message into \(2^{n}\) codewords.

Decoding:

1. Try reconstructing a polynomial from all combinations of \(\binom{2^{n}, m}\) polynomials
2. Output the majority polynomial

This scheme can tolerate:

1. errors up to \(\lfloor (2^{n} - m )/2 \rfloor\)