Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have a question about linear block erasure codes that are described in this paper. I briefly describe the idea behind the linear erasure codes and then I ask my question.

Given a set $d=\langle x_i \in GF(2^q)|i=1,\cdots,k\rangle$ of data packets, the general idea of (systematic) erasure codes is to generate $n-k$ extra packets $e=\langle y_j \in GF(2^q)|j=1,\cdots,n-k\rangle$, such that given any $k$ packets out of the set $\{x_1,\cdots,x_k,y_1,\cdots,y_{n-k}\}$ one is able to decode the original set $d$.

To generate the extra packets, we consider an $(n-k) \times n$ generator matrix $G'$ and compute $e=G'd$.

The paper claims that if the rows of the generator matrix are selected from a Vandermonde matrix:

$$ V=\begin{bmatrix} 1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{k-1}\\ 1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{k-1}\\ 1 & \alpha_3 & \alpha_3^2 & \dots & \alpha_3^{k-1}\\ \vdots & \vdots & \vdots & \ddots &\vdots \\ 1 & \alpha_m & \alpha_m^2 & \dots & \alpha_m^{k-1} \end{bmatrix} $$ where $\alpha_i \in GF(2^q)$ then the computed vector $e$ has the desired property.

Now my question: Assume $n-k=2$, i.e., any loss of 2 packets can be recovered. Let, $$ G'=\begin{bmatrix} 1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{k-1}\\ 1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{k-1} \end{bmatrix} $$

By definition of the erasure codes, the submatrix consisting of any two columns of the matrix $G'$ must have rank 2. But we know that for $\alpha_1, \alpha_2 \in GF(2^q)$ and $\alpha_1 \neq \alpha_2$, we may have $\alpha_1^s = \alpha_2^s$ for some $s$. It means that the matrix

$$ \begin{bmatrix} 1 & \alpha_1^s \\ 1 & \alpha_2^s \end{bmatrix} $$ has rank 1 rather than 2. So, it means that if packets $x_1$ and $x_{s+1}$ are lost, they cannot be recovered using the set $e$. Generally, the fact that an $m\times m$ Vandermonde matrix is non-singular, does not mean that any submatrix of it has full rank, does it?

Did I misunderstood the concept or is it the fault of the paper?

share|improve this question
    
A matrix being nonsingular does not imply that all its submatricies are nonsingular. Here is a simple counterexample: consider a $4\times 4$ identity matrix; it is nonsingular. However, if we consider the $2\times 2$ matrix in the upper right corner, that consists of all 0's, and so is obviously singular. I'm not certain how that pertains to block erasure codes (I do cryptography, not coding theory), however that at least is one statement you made which is not true. –  poncho May 30 at 22:41
    
That's right. My question is that some losses of size $n-k$ (=2 in my example) are not recoverable because the rank of some of the subsets of size $n-k$ of the columns of the $G'$ matrix is not $n-k$. –  Mohsen May 30 at 22:52

1 Answer 1

Ok, I found the answer.

The answer is yes, singular submatrices may happen in a Vandermonde matrix. Look at this paper for an approach to avoid singular submatrices while creating a generator matrix:

http://oatao.univ-toulouse.fr/2176/1/Lacan_2176.pdf

share|improve this answer
    
Please don’t forget to accept your own answer so we know if you are satisfied with the answer you have, which seems to be the case. Otherwise, your question will keep showing up as “unanswered” to us. ;) –  e-sushi May 31 at 20:03
    
And thanks for reporting back the answer for us (you should now be able to accept)! –  owlstead Jun 4 at 7:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.