Parity check matrix for the Hamming code Ham(2,7)

Question

I'm trying to figure out how to construct a parity check matrix for a Ham(2,7) where Ham(2,7) is Ham(r,q). I really don't understand where the columns of matrix come from my Text Book says to list all the non-zero r-tuples in V(r,q) with first non-zero entry equal to 1 in lexicographical order but I'm sure how to do that either. Any help or insight would be appreciated. The only thing I have worked out is n=8 and k=6 but I could easily be wrong.

Answer 1

I'm assuming that by $\mathrm{Ham}(2, 7)$ you mean the linear $[7, 4, 3]$ Hamming code, which I'll refer as $\mathscr{C}$ below. Since the code is $(x_1, x_2, x_3, x_4) \mapsto (x_1, x_2, x_3, x_4, x_1 \oplus x_2 \oplus x_3, x_2 \oplus x_3 \oplus x_4, x_3 \oplus x_4 \oplus x_1)$, where the $\oplus$ is the exclusive-or, the (a?) generator matrix is:

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

where the code $\mathscr{C} = \mathrm{im}\ G = \{xG \mid x \in \mathbb{F}_2^4\}$

Since the parity check matrix $H$ is the $7 - 4 = 3$ rank $3 \times 7$ matrix such that $Hc^T = 0 \ \ \ \forall c \in \mathscr{C}$, the following is satisfied : $HG^T = 0$.

The matrix $G$ is in the form $[I_4 \mid A]$. Consider the matrix $H' = [-A^T \mid I_3]$. $\mathrm{rank}\ H' = 3$. What is $H'G^T$? You can prove that $H'G^T = -A^TI_4 + I_3A^T = 0$. Indeed, then, $H = H'$ is a parity check matrix for $\mathscr{C}$. Lets write down $H$ now:

$H = \begin{bmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \\ \end{bmatrix} $

If you read the $H$ in binary the numbers are $[5, 3, 7, 6, 1, 2, 4]$. This is not in lex-order. It will indeed come out to be in lex-order for some $G' \neq G$, but it does not matter. $G$ is indeed a generator matrix for $\mathscr{C}$ and $H$ is the corresponding parity check matrix. Note that what really matters is that the space spanned by the rows of $H$ should be orthogonal to the code $\mathscr{C}$. Since the criterion you mentioned (lex-order) is according to columns, it is not necessary that such a $H$ will be found from our $H$ even by some elementary row operations (for example, because, our $G$ could have some permuted columns).