Reed-Solomon Error Correction – Encoding#
Reed-Solomon codes are an especially powerful tool for efficient multi-bit error detection and correction. The following is my understanding of the algorithm after reading my professor’s presentation and correcting several erroneous details.
Galois Field Arithmetic#
In Reed-Solomon codes, a symbol is defined a sequence of multiple bits. Each symbol will be corrected as a whole instead of on a bit-by-bit basis. Usually 8 bits are used. However, for the sake of simplicity, we will use 3 bits in the following section (and 2 for the actual encoding/decoding process).
To manipulate symbols, we will need finite-field arithmetic (since bits are discrete and finite),
in this case Galois Field arithmetic, commonly denoted as
Let’s take a look at
polynomial |
binary |
decimal |
|
---|---|---|---|
000 |
0 |
||
001 |
1 |
||
010 |
2 |
||
100 |
4 |
||
011 |
3 |
||
110 |
6 |
||
111 |
7 |
||
101 |
5 |
The table shown above has the following properties:
can be considered a dummy variable.The leftmost column contains increasing powers of
.These powers correspond to a polynomial of
. , andAn irreducible polymonial
can be used to construct the rest of the table. is a root of , i.e. , so is .Whenever
or is encountered, substitute it with
Important
Addition in
In
, addition is by default. Therefore, simple xor must be used term by term and there are no carries. Subtraction is equivalent to addition.For example,
, and .In the case of
,The coefficients of the polynomial are the bits of the symbol.
The decimal representations of the binary bits are also shown.
Mutiplication#
Multiplication of symbols in
For example, in
polynomial |
binary |
decimal |
|
---|---|---|---|
00 |
0 |
||
01 |
1 |
||
10 |
2 |
||
11 |
3 |
with the generator polynomial being
Then
The complete multiplication table is as follows:
multiplier |
multiplicand |
product |
---|---|---|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
2 |
0 |
0 |
3 |
0 |
1 |
1 |
1 |
1 |
2 |
1 |
1 |
3 |
1 |
2 |
2 |
3 |
2 |
3 |
1 |
3 |
3 |
2 |
Important
The division mentioned above is
Now we are ready to dive into the code itself.
Caution
From now on, we’re going to abandon the polynomial representation of symbols and use only
Encoding a Reed-Solomon Code#
A complete Reed-solomon Code consists of
are data symbols, and are check symbols, where
When
Polynomial Representation of the Message#
To encode a string of data, first the data must be separated into
where
The Code Generator Polynomial#
To encode the message, we need another magic polynomial, the code generator polynomial:
where:
should be understood as a decimal number is an arbitrary constant, but is usually set to
Encoding#
The trick is to divide a shifted version of the message polynomial by the code generator polynomial:
where
Important
Arithmetic When Dealing with Messages
You may have noticed I have been constantly emphasizing the necessity to forget the previous polynomial arithmetic
we did to symbols. This is because we need a very similar but different polynomial arithmetic
system when dealing with messages, where coefficients can be arbitrary decimal integers, instead of only
Addition is still equivalent to subtraction and done with a simple xor. However, instead of doing it term by term, it is done bit by bit
Multiplication follows the multiplication table we’ve derived earlier.
Polynomial division is still done in the normal manner.
We can rewrite the equation as
Adding
The left hand side is the Reed-Solomon code (
In reality,
Example of Encoding#
(A quick reminder that
Since we only have one data symbol in
Binary message:
We’ll discuss decoding in the next article.
Citations and Credits#
Clarke, C. K. P. “R&d white paper.” Reed-Solomon error correction,” WHP 31 (2002).
Shankar, Priti. “Decoding Reed-Solomon Codes Using Euclid’s Algorithm.” Resonance, vol. 12, no. 4, Apr. 2007, pp. 37–51. DOI.org (Crossref), https://doi.org/10.1007/s12045-007-0037-y.
Huge thanks to my professor Mr. Thomas Riordan for making the best out of both papers.