# Parity-check matrix for code with variable block size and minimum distance

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.

• Is $q$ prime? Also, standard terminology is $n$ for length and $k$ for dimension of a code. – kodlu Apr 19 '15 at 23:31
• $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. – Dale Apr 20 '15 at 2:28
• :the fact that you wrote integers for entries of the matrix made me think you might be considering prime $q$ only. – kodlu Apr 20 '15 at 5:28
• 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. – Felipe Voloch Apr 20 '15 at 12:55
• 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). – Jyrki Lahtonen Apr 22 '15 at 13:52

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).$
• 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. – Dale Apr 21 '15 at 1:00