Prove that $A_3(4,3)=9$ and construct the correspoding code.

Question

• $A_q(n,d)$ is the maximum $M$ (number of codewords) such that a $q$-ary $(n, M, d)$-code exists.

I know that according to Gilbert-Varshamov bound:

$$A_q(n,d) \left( \binom {n}{0} + \binom{n}{1} (q-1)+ \dotsb +\binom{n}{e}(q-1)^e\right) \leq q^n. $$

In our case we solve that for $n=4$, $d=3$ and $e=1$ (the errors that it can correct) and we have that $A_3(4,3)$ $\leq 9$. I assume that the code $C$ contains the $0000$. Since $d = 3$ (minimum distance) so every codeword would have weight $\geq 3$.

How many codewords with weight $=3$ and weight$=4$ should be in the code? And which are these?(NOTE: we have $q=3$)

How can I prove that $A_3(4,3)=9$ ? Is there a standard way to construct such codes?

Thank you for your time!

Answer 1

Using Hamming bound I found that $A_3(4,3)\leq9$. I have $n=4$ and $q=3$. I want to find a code with $3^2$ codewords. So $k=2$. I know that the check matrix is an $(n-k)\times n$ matrix. Also,I know that $d=3$ so I want to construct a check matrix $H\in M_{2\times 4}(\Bbb F_3)$ where there aren't two columns linearly dependent (that means the columns are pairwise linearly independent). I have:

$$H= \begin{bmatrix} 2 & 1 & 1 & 0\\ 1 & 1 & 0 & 1 \\ \end{bmatrix}$$ (Check: $column3 + column4 = column2$)

And the generator matrix G would be:

$$G=\begin{bmatrix} 1 & 0 & 1 & 2\\ 0 & 1 & 2 & 2 \\ \end{bmatrix}.$$

So, now it's easy to find the code.

$$C=\{0000,1012,0122,2021,0211,1101,2110,1220,2202\} \subset \Bbb F_3^4.$$

We notice that every distance between the codewords is equal to $3$ and that there are no words of weight $4$.

So, we have proved that $A_3(4,3)=9$.

Answer 2

Another way to solve this (But without the construction of the code)

By using the following lemma:

Lemma:If q is a prime power and $n=\frac{q^r-1}{q-1}$ for some $r\geq2$, then $A_q(n,3)= q^{n-r}$ .

In our case, we have $n=4$ and $q=3$ so we search an r such that $n=\frac{3^r-1}{3-1}=4$.It is obvious that $r=2$ satisfies the equation. So, $A_3(4,3)= 3^{4-2}=9$ .