2
$\begingroup$

My question is about using a Vandermonde matrix vs a Cauchy matrix in erasure coding. In the Reed-Solomon (RS) code, encoding is done by multiplying a $N\times K$ ($N>K$) matrix with the code words to produce $N$ symbols ($K + M$ redundancy). A systematic code is a code where the $K$ symbols are the original codewords. This means that the first $K\times K$ matrix is the identity matrix. The multiplication is usually carried out in a finite field $GF(2^w)$. For the matrix to be a proper RS encoding matrix it is required that each $K\times K$ submatrix would be invertible, since this way we can cope with $M$ losses and still recover the original information.

In most places I've seen, generating such systematic encoding matrix is either done by:

  1. Taking a Vandermonde matrix and linearly transforming it to a systematic encoding matrix where the first $K\times K$ submatrix is the identity matrix. As described here: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.155&rep=rep1&type=pdf

  2. Taking a $K\times K$ identity matrix and augmenting it with a Cauchy matrix. As described here: https://www.researchgate.net/profile/James_Plank/publication/221137246_Optimizing_Cauchy_Reed-Solomon_Codes_for_Fault-Tolerant_Network_Storage_Applications/links/5432a4f40cf22395f29c3027/Optimizing-Cauchy-Reed-Solomon-Codes-for-Fault-Tolerant-Network-Storage-Applications.pdf

My question is why the second method isn't used with the Vandermonde matrix? Meaning instead of linearly transforming the Vandermonde matrix to have a $K\times K$ identity part, taking a $K\times K$ identity matrix and augmenting the with rows from the Vandermonde matrix ?

I know that the Vandermonde matrix over a finite field might not be invertible (as opposed to the Cauchy matrix), but I assume we choose an invertible one.

Also according to this paper (https://www.cs.utexas.edu/~diz/pubs/erasure.pdf which introduced using a Cauchy matrix for erasure coding), we have the following requirement for a systematic encoding matrix :

Theorem 2.2: Let $C$ be a an ($n-m\times m$)-matrix over $GF[2^L]$. The matrix (Identity $K\times K|C$) is the generator matrix of a systematic MDS code with packet size $L$ if and only if every square submatrix of $C$ is invertible .

So a Vandermonde matrix that is invertible should fit this.

Does anyone know ?

$\endgroup$
3
  • 1
    $\begingroup$ I don't have time to think about this now, but it looks like it me related to the problem in paper handled in MATH.SE. $\endgroup$ Nov 7, 2020 at 22:19
  • $\begingroup$ Thanks Jykri . What is not clear to me is how does the theorem I gave at the end of the question given here (cs.utexas.edu/~diz/pubs/erasure.pdf) doesn't contradict your claim on the independence of n out of 2n rows in the generator matrix ?what am I missing $\endgroup$
    – Avi
    Nov 13, 2020 at 12:02
  • $\begingroup$ If augmenting identity matrix with vandermonde matrix, and may a K*K submatrix is irreversible, but when augmenting it with a Cauchy matrix any is reversible, so is a MDS systematic code. $\endgroup$
    – qxxiao
    Apr 19, 2021 at 6:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.