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 with 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 a way that they can operate on multiple bits error 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 the corrupted messages over a noisy network. There are two main components of the Reed-Solomon codes and they are:
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?
When you heard about Layer-2 solutions, the most essential part of these solutions are 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.
With the later approach of Data Availability Sampling the main problem arises is how can we make sure that not even a 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 the 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 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 a large data using RS codes, he first extends the data by using some parity and then break 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.
Error codes is an injective mapping of:
What's the meaning of these parameters involved in this equation?
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.
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.
Messages are elements “m” of data stream which have a string length k is called message length or dimension of block.
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.
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:
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.
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.
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 x6, x5, x4 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.
The decoder views the codeword as a sequence of coefficients. They use a fixed generator polynomial which is known to both sender and receiver.
The transmitted message (c0, c1, , , ,cn) 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:
The transmitted polynomial that has been received by the receiver has error in it which could be defined as:
The coefficients of the ei 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 ik 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 ik and the error values at those positions eik so we can get the original message s(x) by subtracting the error from the received polynomial.
The decoder starts by evaluating the polynomial as received at points α1, . . αk . The evaluations at these primitive points are called “ syndrome” (Sj).
Syndromes can be defined as:
The Sj 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.”
We define locators as Xk and values as Yk.
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 Xk because then we have the leftmost matrix and we can simply multiply both sides of the equation by its inverse yielding Yk. The k values are column numbers while the j values are rows.
So let head to our journey of finding error locator Xk 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 sj+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 knowns at both sides of the equation so we can easily find the values of Ai. For an example reference of how this is working practically you may see this link.
After solving for Ai(error locators) , I can simply put the values of Ai matrix to the equation where with using syndrome values i can get the error values Yi.
This is how you can understand the general mathematical overview of Reed-Solomon erasure codes.
To read on Data Sampling and Fraud Proofs.