Hamming codes

The $[7,4,3]$-Hamming code over $GF(2)$ having generator matrix

$$\left( \begin{array}{ccccccc} 1& 0& 0& 0& 0& 1& 1\\ 0& 1& 0... ... 0& 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1 \end{array}\right)$$

is obtained by typing

C:=HammingCode(3,GF(2));
G:=GeneratorMat(C);
Display(G);

Encoding a message $w$ using $G$, is simply the map $w\longmapsto wG$. Type

Elements(C);
Size(Elements(C));

From this, you see all the codewords of C and how many there are.

To get the parity check matrix, type

H:=CheckMat(C); Display(H);

Note all the columns of $H$ are distinct and non-zero. To see if a vector in $\mathbb{F}^7$ is a codeword, simply compute $Hv$ and check if it is zero or not. Here's a GAP example:

v := Codeword([0,0,1,1,0,1,0]);
v in C;

(Here

v = [ 1 0 1 1 0 1 0 ]+[1,0,0,0,0,0,0].

which is the code word obtained by encoding $(1,0,1,0)$ plus the error vector $(1,0,0,0,0,0,0)$.

Since this last vector is non-zero, $v$ is not a codeword. If it was a vector received in transmission (with at least one error) then to decode it, hence to find the most likely codeword sent, type

Decode(C,v);

Exercise 3.11.2 (a)   For the parity check matrix $H$ of the binary Hamming code of length $2^3-1=7$, verify $Hc=0$ for three or four codewords c. Decode $(1,1,0,0,0,0,0)$.

(b) Find a parity check matrix of the $3$-ary Hamming code of length $(3^3-1)/(3-1)=13$. Verify $Hc=0$ for three or four codewords $c$. Decode $(1,2,1,2,1,2,1,2,1,2,1,2,1)$.

To get the dimension of the code, type Dimension(C); To get its minimum distance, type MinimumDistance(C);

Exercise 3.11.3   Find the dimension and minimum distance of

(a) the binary Hamming code of length $15$,

(b) the 3-ary Hamming code of length $13$.