parity check matrix of $\operatorname{ham}(3,3)$ code - struggling with $q=3$

Question

I am confused about how to represent numbers when constructing a parity check matrix for a $\operatorname{ham}(3,3)$ code.

I know that the dimension of a $\operatorname{ham}(r,q)$ matrix is $k=n-r$ and $\operatorname{ham}(r,q)$ is an $[n,n-r,3]$-code with $r\geq 2$.

We have $n= \dfrac{q^r-1}{q-1}=\dfrac{3^3-1}{3-1}=13$,

and $k=n-r=13-3=10$

So the matrix will have 13 columns and 3 rows. I have the solution as this is a past exam question, but I do not understand how they got the columns as they did. I am assuming instead of usual binary representation with is base 2, it is base 3, but I dont know what this is called and have searched google and I am none the wiser. The columns need to be represented in lexicographical order.

$H= \left( \begin{array}{ccc} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 2 \\ 1 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 \end{array} \right) $

which is a 13 by 3 matrix with columns in lexicographical order.

If this was in field $F_2$ then I would able to work the columns out as they would be the numbers 1-13 written in binary representation.

However, they are not as I dont understand what the base is and how they get the twos. Please help explain how this is done.

Any help much appreciated. Please write in plain English as I am new to coding theory.

Thanks

Answer 1

The columns are ternary vectors, that is, elements from the vector space $\mathbb{F}_3^3$. In a Ham$(3,q)$ code, the $q$ represents the size of the finite field you are working with, which is why in your case you are seeing ternary vectors.

Answer 2

All Hamming codes have distance 3, which implies that the columns of $H$ are pairwise linearly-independent (i.e., you cannot form a linear combination of two columns and obtain the zero vector, you need at least three columns).

Now, two vectors ${\bf x_i} , {\bf x_j}$ are linearly dependent if $a_i {\bf x_i} + a_j {\bf x_j}={\bf 0}$, operating in the respective field: here, $a_i \in \{0,1,2\}$ (not all zero) and the arithmetic is done module $3$. The above can only happen if either one of the vectors is zero, or ${\bf x_i} = {\bf x_j} $ or ${\bf x_i} = 2 {\bf x_j} $.

So, to construct the matrix $H$ the column vectors must be non-zero, distinct, and none of them can be twice another one. Writing all the ternary vectors (as row vectors) in lexicographical order, and striking out the prohibited ones, we get:

(0 0 0) : zero is not allowed

(0 0 1) : this will be the first column of H

(0 0 2) : not allowed, this is twice the previous one

(0 1 0) : second column of H

(0 1 1)

(0 1 2)

(0 2 0) : same as 2 x (0 1 0)

(0 2 1) : same as 2 x (0 1 2)

(0 2 2) : same as 2 x (0 1 1)

(1 0 0)

...

I guess you can go on from here.