Let $q$ be a prime. Number of $q$-ary linear codes with parameters $[n,n-1,2]$ for $n \geq 2$?

543 Views Asked by At

Am I correct to think this way. Using the generator matrix in standard form $G = [ I | A ]$, where $G$ is a $n-1$ by $n$ matrix. Since the distance between code words is 2. $I$ then takes the form of a $n-1$ by $n-1$ matrix.

So to count the number of code words I should count the number of generating matrices and I try to generate the number of possible matrices that would lead to $I$ in RREF, so in the first column have $q^{n-1}-1$ choices, in the second column I would have $q^{n-1}-q$ choices and all the way to then $n-1$ column I would have $q^{n-1}-q^{n-2}$ choices.

Therefore, am I right to say the number of possible $q$-ary linear codes is

$$(q^{n-1}-1)(q^{n-1}-q)\cdots (q^{n-1}-q^{n-2})$$

1

There are 1 best solutions below

0
On BEST ANSWER

If you have a $[n,n-1]$-code $C$ over $\mathbb{F}_{q}$, your parity check matrix $H$ will be $1 \times n$ and have rank $1$. Now your theorem relating the parity check matrix to the minimum distance $d$ of your code should say

"$C$ has minimum distance distance $d$ if and only if

  1. Any $d-1$ columns of $H$ are linearly independent and
  2. There is at least one set of $d$ columns which are linearly dependent."

So that means that $H$ cannot have any nonzero entries. You should convince yourself that two parity check matrices $H$, $H^{\prime}$ determine the same code precisely when they have the same row space, for a matrix with 1 row this means when they are scalar multiples of each other. So we can WLOG assume that the last entry of $H$ is equal to 1, meaning the $[n,n-1,2]$ codes are in one-to-one correspondence with parity check matrices of the form $$H = \begin{bmatrix} h_{1} & h_{2} & \cdots & h_{n-1} & 1 \end{bmatrix}$$ where all of the $h_{i} \neq 0$. This gives $q-1$ choices for each $h_{i}$ for a total of $(q-1)^{n-1}$ codes.