3
$\begingroup$

Consider a linear error-correcting code with symbols in $GF(q)$, with codewords of length $k$ generated from messages of length $n$ and minimum distance $d+1 = k-n+1$. In the cases of interest, $q = 2^8$, $d \le 20$, and $n > 100$. Such a code can be characterized by the parity-check matrix $H$ with $d$ rows and $n$ columns: Codewords $c$ are the column vectors for which $Hc = 0$. What I want is an $H$ which can be used for variable values of $n$ and $k$, up to some "large" limit (but fixed $q$ and limited $d = k-n$). The limit should be substantially above $q$ but doesn't have to be above $q^2$. This reduces to finding a matrix $H$ of elements in $GF(q)$ with perhaps as many as 20 rows and as many as $q^2$ columns, for which given any $d \le 20$ and any $d$ columns of $H$, the square matrix formed by the first $d$ elements of each of the $d$ columns is nonsingular.

This is straightforward if the number of columns of $H$ is $\le q$, because the Vandermonde matrix has this property:

$\begin{bmatrix}1 & 1 & 1 & \dots \\ 0 & 1 & 2 & \dots \\ 0^2 & 1^2 & 2^2 & \dots \\\dots \end{bmatrix}$

However, the Vandermonde matrix cannot be extended to more than $q$ columns.

But given the simplicity of the Vandermonde matrix, I expect that there are relatively simple matrices that have the required properties and many more than $q$ columns.

$\endgroup$
  • 2
    $\begingroup$ Is $q$ prime? Also, standard terminology is $n$ for length and $k$ for dimension of a code. $\endgroup$ – kodlu Apr 19 '15 at 23:31
  • $\begingroup$ $q$ is a prime power, otherwise $GF(q)$ wouldn't exist. In practice, it's $2^8$. And sorry about getting $n$ and $k$ backwards. $\endgroup$ – Dale Apr 20 '15 at 2:28
  • $\begingroup$ :the fact that you wrote integers for entries of the matrix made me think you might be considering prime $q$ only. $\endgroup$ – kodlu Apr 20 '15 at 5:28
  • 2
    $\begingroup$ The main conjecture of MDS codes states that there is no code with length + 1 = dimension + min. distance (writing out since your notation is nonstandard) for length > q+2. You want to relax this to length=dim. + distance but want length up to $q^2$. I doubt it can be done. $\endgroup$ – Felipe Voloch Apr 20 '15 at 12:55
  • 2
    $\begingroup$ Agree with Felipe. This is a tall order. If you can do it for length $>q+2$ you will be famous. With Algebgraic Geometry codes (aka Goppa codes) you can approach this. For example if you settle for $d+1=n-k+1-1$, i.e. minimum distance one less, then using elliptic curves you can manage up to $n\approx q+2\sqrt{q}$. If you allow $d$ to drop by $g$, you can increase the length to $\approx q+2g\sqrt q$ (Hasse-Weil bound). $\endgroup$ – Jyrki Lahtonen Apr 22 '15 at 13:52
2
$\begingroup$

Getting a matrix with more than $q$ columns seems to be problematic. However taking, for example, a $q\times q$ Cauchy matrix would work for $n\leq q$.

A Cauchy matrix is an m×n matrix with elements $a_{ij}$ given by

$$a_{ij}={\frac{1}{x_i-y_j}};\quad x_i-y_j\neq 0,\quad 1 \le i \le m,\quad 1 \le j \le n$$ where $x_i$ and $y_j$ are elements of a field $\mathcal{F}$, and $(x_i)$ and $(y_j)$ are injective sequences, i.e., their elements are distinct. Clearly, when $\mathcal{F}$ is finite $\max(m,n)\leq q$ must hold.

It is easy to see that every submatrix of a Cauchy matrix is itself a Cauchy matrix, since the injectivity is preserved by subsequences of the sequences $(x_i)$ and $(y_j).$

By the way, the vandermonde matrix can have singular submatrices, but in your case the fact that you're only interested in consecutive column entries saves the day.

$\endgroup$
  • $\begingroup$ If $\mathcal{F}$ is finite, then $m + n \le q$, because all the $x_i$ and $y_j$ have to be distinct from one another; otherwise either the determinant is zero or the matrix has an infinite element. Unfortunately, exceeding $q$ columns is the essence of my problem. Nonetheless, the fact that the Cauchy matrix satisfies even stronger properties than the Vandermonde matrix is interesting. $\endgroup$ – Dale Apr 21 '15 at 1:00
  • $\begingroup$ If it is possible please see my question. thanks $\endgroup$ – Amin235 Aug 15 '17 at 10:24

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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