Hamming(3,4) Code

I've been asked to find the parity check matrix of the Ham(3,4) code so I can use syndrome decoding. If we let,

$\mathbb{F_4} = \{0, 1 , \omega, \omega^2 | \omega^2 = \omega + 1 \}$

We have that $n = \frac{4^3 - 1}{3} = 21$, and $r = 3$.

My book says that the parity check matrix should be a $3\times21$ matrix, and that the columns should be the elements of V$(3,4)$ (except $000$.) However, aren't there $4^3 = 64$ elements in V$(3,4)$? In other words, shouldn't the parity check matrix have $63$ columns, not $21$?

Every non-zero vector in $\Bbb{F}_4^3$ has three non-zero scalar multiples. To get the Hamming code you can only use one of them as a column of the check matrix. The reason is easy to understand. If column $j$ is a multiple of column $i$, then you get codewords of weight two with the only non-zero components in those two positions.
There are many ways of avoiding those scalar multiples. One way is to insist that the first non-zero entry is normalized to $1$. There are exactly $21$ vectors in $\Bbb{F}_4^3$ such that the first non-zero component $=1$. The other $42$ vectors are multiples of those $21$.
• Great, thanks! I just realised my book was specifically talking about the case when $q = 2$, which explains why it didn't mention scalar multiples. Commented Mar 27, 2017 at 19:27