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

Question

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.

Answer 1

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.