Construction of parity check matrix for Hamming code

Question

Can someone please explain how the parity check matrix for a Hamming $[\frac{q^{r}-1}{q-1},\frac{q^{r}-1}{q-1}-r,d=3]$ code is constructed, assuming we don't know what the generator matrix is?

Answer 1

All vectors are assumed to be column vectors.

Discard the zero vector $\mathbf 0$ from $\mathbb F_q^r$ leaving a set $\mathcal A_1$ of $q^r-1$ vectors.

Pick a $\mathbf x_1$ in $\mathcal A_1 = \mathbb F_q^r-\{\mathbf 0\}$ as the first column of the parity check matrix, and then remove the $q-1$ nonzero multiples of $\mathbf x_1$ from $\mathbb F_q^r-\{\mathbf 0\}$ leaving a set $\mathcal A_2$ of $(q^r-1)-(q-1)$ vectors for use in the next step.

Pick a $\mathbf x_2$ in $\mathcal A_2$ as the second column of the parity check matrix, and then remove the $q-1$ nonzero multiples of $\mathbf x_2$ from $\mathcal A_2$ leaving a set $\mathcal A_3$ of $(q^r-1)-2(q-1)$ vectors for use in the next step.

Lather, rinse, and repeat the basic step: Choose one vector from $A_i$ as the $i$-th column of the parity check matrix, and removing its $q-1$ multiples from $\mathcal A_i$ to leave set $A_{i+1}$ for future use. Since we are discarding $q-1$ vectors at each step, the process can continue until we have discarded all $$q^r-1 = (q^{r-1} + q^{r-2} + \cdots + q^2 + q + 1)(q-1)$$ vectors in $$n = q^{r-1} + q^{r-2} + \cdots + q^2 + q + 1 = \frac{q^r-1}{q-1} ~\text{steps}.$$

We have thus created a parity-check matrix with $r$ rows and $n=\frac{q^r-1}{q-1}$ nonzero columns, which defines a $\left[\frac{q^r-1}{q-1}, \frac{q^r-1}{q-1}-r\right]$ code over $\mathbb F_q$. By construction, this code has the property that no nonzero linear combination $a\mathbf x_i+b\mathbf x_j$ of two columns can equal $\mathbf 0$ and so the minimum Hamming weight of the code is at least $3$. I will leave it to you to prove that the minimum distance is in fact exactly equal to $3$ and that the code we have thus constructed is indeed a (single-error-correcting) Hamming code over $\mathbb F_q$.