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.

1more comment