Code for BCH / Reed-Solomon encoder/decoder pair.

Table of contents

1. Mathematics of Reed Solomon and BCH codes
2. Implementation notes
3. Getting up and running
4. License

This is the introduction

Some (out of order) overview of Reed Solomon and BCH codes, in the context of this code:
A message $m(X)$ is a polynomial with coefficients in a finite field $F$ with $char(F) = 2$.
Meaning, the coefficients of $c(X)$ are bit vectors, addition $\oplus$ of vectors is bitwise XOR (or sum modulu 2), $1$ is the vector with all 0s EXCEPT THE RIGHTMOST COORDINATE, and multiplication $\cdot$ needs to be defined over $F$, such that:
$\forall \alpha 1\cdot \alpha = \alpha \cdot 1 = \alpha$ $\forall \alpha, \beta \in F: \alpha \cdot \beta \in F$
$\forall \alpha, \beta \in F: \beta \cdot \alpha = \alpha \cdot \beta$
$\forall \alpha, \beta, \gamma \in F: \alpha\cdot(\beta \cdot \gamma) = (\alpha\cdot\beta) \cdot \gamma$
$\forall \alpha, \beta, \gamma \in F: \alpha\cdot(\beta \oplus \gamma) = (\alpha\cdot\beta) \oplus (\alpha \cdot \gamma)$
$\forall \alpha, \beta, \gamma \in F: \alpha\cdot(\beta \oplus \gamma) = (\alpha\cdot\beta) \oplus (\alpha \cdot \gamma)$
$\forall \alpha \neq 0 \exists \beta : \alpha \cdot \beta = 1$
Formally, there need to be further axioms here regarding addition, but once I said it's bitwise XOR they are automatically fulfilled.
The above arithmetic is implemented ad-hoc for a field of size $2^8$ as well as $2^7$, in arithmetic.py.
Given a field $F$ we consider $F[x]$, the ring of formal polynomials in variable $x$ over $F$, namely the set of expressions: $${\Sigma_{i=0}^{K}a_i \cdot x^i\ : a_i \in F}$$.
Given a polynomial $g(x)\in F[X]$, we denote the (left) ideal generated by $g(x)$ : $$<g(x)> = {g(x) \cdot a(x): a(x) \in F[x]} $$.
The space of codewords is then the ideal generated by $g(x)$. By definition of $g(x)$, and given a message $m(x)$, we can check if $m(x)$ is a codeword using Euclid's division algorithm (also implemented in arithmetic.py), by computing $m(x)$ modulu $g(x)$ and checking whether it is $0$ modulu $g(x)$.

Implementation notes

The implementation presented here aims for correctness and clarity, rather than performance. At the moment several arithmetic operations were cached into look up tables in a very simple way.
The intent is to present several methods to perform arithmetic using several algorithmic equivalents, with each method appealing to different application (so some methods will work better in, say, Verilog, but one would target latency and another would target gate count).

Getting up and running

Other than cloning this project and setting an environment that has all the requirements (listed in requirements.txt), you would need to let python know where the files are. This can be done either by setting a system environment that has the path to the project, and which the modules are set to look for (REEDSOLOMON), or, hard coding it into the modules. I could have used PIP to package the project, but I like this way better.

License

Feel free to use this project under the MIT license. If you decide to reference it, please use:
@misc{reedSolomonPython,
title = "A python implementation of Reed Solomon and BCH codes",
author = "{Omer S. Sella}",
howpublished = "\url{https://github.com/Omer-Sella/reedSolomon}",\ year = 2024,
}