I've been looking at an erasure code by Luigi Rizzo which is based on Vandermonde matrices, since this code is used in Outernet. In fact, it is the code implemented by the zfec library. Luigi Rizzo describes his code in a paper from 1997, but the paper can be very confusing and misleading because it describes the mathematics in very little detail. I needed to go to the source code to understand how it works. Actually, the idea behind this code is very simple. Here I do a mathematical description of the code and show that it is the same as a Reed-Solomon code. This is rather weird, because Luigi Rizzo makes no mention of Reed-Solomon codes, which were first described in 1960.
Let be a field. Recall that an linear code over can be given in terms of a generator matrix , which is an matrix with entries in and rank . A message is encoded as , where is computed as (here I always consider vectors as columns). The code is called systematic if has the form
so that for . Note that this is really a property of the matrix , since the code is defined just as the image of .
We are interested in designing an systematic code that works as an erasure code and is able to correct up to erasures. This means that we should be able to compute from even if only of the components of are known. This condition is equivalent to the condition that every submatrix of is invertible. To see this, note that if we regard the equation as a linear system for and consider only the equations for which we know the value of , then we obtain a reduced linear system , where is the vector of the components of which we know and is the correspondent submatrix of . Therefore, needs to be invertible so that we can find in terms of .
An idea to find such a matrix is to use Vandermonde matrices. If , the Vandermonde matrix is
Its determinant is
so the Vandermonde matrix is invertible if and only if the elements are distinct.
The matrix is constructed in the following way: we choose distinct elements and we put
write and define
so that has the required form to give a systematic code. This matrix satisfies the condition that every submatrix of is invertible, because such a submatrix is of the form , where is the corresponding submatrix of . Note that is a Vandermonde matrix constructed with distinct elements, and hence invertible, so is also invertible. In the intended application, is the finite field with elements, so up to distinct elements can be chosen, and can be at most .
The keen reader will have noticed that this construction looks very much like a Reed-Solomon code. In fact, the code described by Luigi Rizzo is the same as a Reed-Solomon code. The only difference is that Luigi Rizzo is only concerned with recovering erasures, which is much easier than recovering errors. The fact that Luigi Rizzo doesn't mention Reed-Solomon codes makes me suspect he didn't have a good knowledge of coding theory. The authors of zfec seem more knowledgeable and they mention that zfec is a Reed-Solomon code, albeit only in some of the comments in the source code. This doesn't seem to be widespread knowledge, so I'll say it again clearly:
zfec is just a Reed-Solomon code used as an erasure code
To see that this code is the same as a Reed-Solomon code, let us recall the systemmatic encoding of Reed-Solomon codes. As above, is the finite field with elements. To construct an Reed-Solomon code over , we choose distinct elements . Given , there is a unique polynomial of degree less than such that for . Indeed, , where the vector is obtained as . Here denotes the Vandermonde matrix as above. The message is encoded to produce , where for . Thus, , where and are defined as above. We see that the systematic generator matrix for this Reed-Solomon code is the same as the generator matrix considered by Luigi Rizzo.