Reed Solomon Codes: A Classical Explanation

Ever wondered how satellite communication works when there is so much noise in the environment? Or how can we still play our games on a CD which might have lost some data by little scratches over them? It's all possible because of the efforts of two scientists  Irving S. Reed and Gustave Solomon. In 1960, they introduced the world to an algebraic concept of erasure codes, most commonly known as “Reed-Solomon codes.”

Reed- Solomon code is the subclass of Non-Binary BCH codes. The non-binary BCH codes are different from the binary codes in that they can operate on multiple bits errors rather than individual bits. These codes are based on Galois fields, where arithmetic operations on field elements have a result within the field. These arithmetic operations are handled by an encoder and decoder, which require special-purpose hardware or software. These codes help us to recover corrupted messages over a noisy network. There are two main components of the Reed-Solomon codes, and they are:

1. Encoding 
2. Decoding

The encoder receives the data and before transferring it to the network, it adds some parity in the original data(How to add parity, we will see that later). On the other hand, the decoder detects the corrupted message and recovers the original data.

This concept of recovering data is very important in the blockchain world. Want to know why?

Why is Data Recovery Important in Blockchain?

When you hear about Layer-2 solutions, the most essential part of these solutions is data. The base layer is compelled to provide the guarantee for data availability. We have two possible solutions available to ensure that data is indeed available.

1. Nodes on L1 download the whole data —> This solution comes with the cost of high bandwidth and large hardware requirements. We don’t want to burden the nodes by downloading unnecessary data.  
2. The other solution is Data Availability Sampling, where the sequencer samples the data into chunks, and each node at L1 can download the samples and verify that indeed the data is available.

With the latter approach of Data Availability Sampling, the main problem that arises is how can we make sure that not even 1% of data is withheld by the sequencer. Because if that is the case, then we can’t fully reconstruct the data to validate the state. So here comes the Reed-Solomon in the picture. 

The Reed-Solomon allows us to recover our data by using parity. How do they work? To begin with, let's first get to know the construction and some basic facts about Reed Solomon codes.

Reed Solomon Codes

Reed Solomon codes also refer to error-correcting code that acts on a block of k bits of input data to produce n bits of output data (n,k). RS codes are a family of block codes used for error detection and correction. So in simple words when a sequencer transmits large data using RS codes, he first extends the data by using some parity and then breaks the data into some fixed-size pieces. Each such piece is called a message and the procedure given by the Reed Solomon algorithm encodes each message individually into a codeword.

We have different encoding procedures available for Reed Solomon codes, but we, particularly here will be focusing on the BCH view of Reed Solomon Codes.

RSCodes Parameters 

Error codes are an injective mapping of:

What's the meaning of these parameters involved in this equation?

1- Σ -The Alphabet

The data needs to be encoded is modeled as a string over Alphabet Σ The size of this alphabet is denoted as “q”. If this size value is 2 then the codes are binary codes. Otherwise they are non-binary. In many applications it is useful to consider q to be a prime power, and to identify Σ  as a finite field. 

Galois Finite Field Arithmetic

A finite field performs arithmetic operations such as (+, -, / , *) on field elements in a way that the result always lies in the field. That is the reason we need a special purpose hardware or software encoder and decoder which helps to carry out these operations.

2- The Message Length k

Messages are elements “m” of data stream which have a string length k is called message length or dimension of block. 

3- The Block Length n

The coded message elements “c” of are of length n which will be received by the receiver. Hence they are also called received words. If c=C(m) for some message m, then c is called the codeword of m.

BCH view of Reed Solomon Codes

Every codeword of the Reed–Solomon code is a sequence of function values of a polynomial of degree less than k. In order to obtain a codeword of the Reed–Solomon code the message symbols (each within the q-sized alphabet) are treated as the coefficients of a polynomial p of degree less than k, over the finite field F with q elements. Formally, the set  of codewords C of the Reed–Solomon code is defined as follows:

Encoding Procedure using a systematic way 

There are multiple methods to encode the message using Reed Solomon such as Discrete Fourier transform, data mapping to polynomial but we here for the sake of data availability problem are considering systematic encoding as the best approach due to the below reason.

Systematic encoding can simply append parity to the source block and receivers do not need to recover the original source message if received correctly. This is useful for example if error-correction coding is combined with a hash function for quickly determining the correctness of the received source code. 

We perform mapping of messages x to a polynomial p(x) of degree less than k. 

To compute the polynomial p(x) from x, we use lagrange interpolation. Once it has found, this polynomial will be evaluated at positions a1, a2, . . . an of the field. The a is called the Primitive element of field F. These points are generated by a generator polynomial. 

Generator Polynomial

The generator polynomial G(x) is defined as the polynomial whose roots are sequential powers of the Galois field primitive .

The generator function is generated using a special polynomial. In these codes all the valid codewords are exactly divisible by this generator polynomial. 

To learn the generation process of g(x), you may refer to this link.

The generator matrix G, can always be written as G=[Ix][P], where Ix is the identity matrix of size k.

Now remember our G matrix is equal to the identity matrix multiplied by a polynomial matrix.

G=[Ix][P]

Now the codeword C contains the message m as a prefix, and simply appends error correcting symbols as suffixes. Here instead of sending s(x)=p(x)g(x) , the encoder constructs the transmitting polynomial s(x) such that;

1- The coefficients of k largest monomials(e.g 1,2, . . . k) are equal to the corresponding coefficients of p(x).

2- The lower order coefficients(e.g k, k+1, . . . n) of s(x) are chosen in a way that the polynomial s(x) is completely divisible by generator polynomial g(x).

We construct a message polynomial p(x) by interpreting the message as the coefficients of a polynomial. Next we multiply the message polynomial p(x) by to perform check of t=n-k. Now divide this product with g(x) to find the remainder. 

For example I have a message polynomial of degree 3,  Now I want to extend it with some parity and make an encoding polynomial s(x) of degree 6. For this i must generate a generator polynomial g(x) of degree 6 which might be

Now the largest monomials of the polynomial s(x) such as  x⁶, x⁵, x⁴ will have the same coefficients as p(x).  On the other hand the lower order must have the coefficients in a way that the whole s(x) can be divisible by g(x). 

In this case the s(x) must be equal to Now there might be a case that we don’t get the exact 0 remainder. Hence for that After finding the remainder polynomial sr(x) we can subtract it to itself till we get the 0 remainder.

BCH View Decoding

The decoder views the codeword as a sequence of coefficients. They use a fixed generator polynomial which is known to both sender and receiver. 

Formulation For Decoding

The transmitted message (c₀, c₁, , , ,c_n) is viewed as the coefficients of a polynomial s(x).

As a result of the Reed-Solomon encoding procedure, s(x) is divisible by the generator polynomial g(x):

Since s(x) is a multiple of generator polynomial and inherits all of its roots then we could say:

Since s(x) is a multiple of generator polynomial and inherits all of its roots then we could say:

Therefore;

The transmitted polynomial that has been received by the receiver has error in it which could be defined as:

r(x)=s(x)+e(x) where

The coefficients of the e_i will be zero if the received polynomial does not contain any error at the corresponding power of x, otherwise the value will be non-zero. 

Potentially there could be v error at the i_k distinct positions of x, which could be mathematically define as:

Now we want to design a decoder which could find the number of error v, the positions of error i_k and the error values at those positions e_ik so we can get the original message s(x) by subtracting the error from the received polynomial. 

r(x)-e(x)=s(x)

Syndrome Decoding

The decoder starts by evaluating the polynomial as received at points α¹, . . α^k . The evaluations at these primitive points are called “ syndrome” (S_j). 

Syndromes can be defined as:

The S_j is 0 because s(x) has roots at α^j as we have discussed above. 

“The advantage of looking at the syndromes is that the message polynomial drops out. In other words, the syndromes only relate to the error, and are unaffected by the actual contents of the message being transmitted. If the syndromes are all zero, the algorithm stops here and reports that the message was not corrupted in transit.”

Error Locators and Error Values

We define locators as X_k and values as Y_k.

Hence we can write the syndromes as;

I can map my above equation into a matrix.

Let's solve the leftmost side of the matrix first. In matrix form we can easily solve this equation. As the main problem is finding X_k because then we have the leftmost matrix and we can simply multiply both sides of the equation by its inverse yielding Y_k. The k values are column numbers while the j values are rows.

So let head to our journey of finding error locator X_k using a linear system of equations.We define our Error locator polynomial as A(x).

The zero’s of A(x) are the reciprocal of since x= then the overall equation will become (1- *)=1 - 1=0

So we could say that by evaluation A(x) at we are making the whole polynomial 0.

Now even if we multiply both sides of the equation with YkXj+v where j is an integer 1jv . After multiplication the equation will still remain at 0.

Now for sum k=1 to v and it will still be zero.

Separate each term to its own sum.

We here can separate the unaffected values of A.

These summations are now equivalent to syndromes values, which are already known. Hence we can substitute in the syndrome values.

Subtracting  s_j+v from both sides yields.

Recall that j was chosen to be any integer between 1 and v inclusive, and this equivalence is true for any and all such values. Therefore, we have v linear equations, not just one. This system of linear equations can therefore be solved for the coefficients Λi of the error location polynomial:

Now we have our knows at both sides of the equation so we can easily find the values of A_i. For an example reference of how this is working practically you may see this link.