Finding the parity check matrix for $(15, 11)$ Hamming Codes

Question

I understand how Hamming Codes and their error detection works, but I'm confused how the parity check matrix is found. How exactly is this computed?

Answer 1

The duals of the Hamming codes are the Simplex codes, so the parity check matrix of a Hamming code is the generator matrix of a Simplex code.

For a generator matrix of a Simplex code of dimension $k$ over the binary alphabet, you just put all non-zero vectors in $\mathbb{F}_2^k$ as columns into a matrix.

For example a generator matrix of a binary Simplex code of dimension $4$ is given by $$\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \end{pmatrix}$$

By duality, this is a check matrix of a binary $(15,11)$ Hamming code.

For general alphabets $\mathbb{F}_q$, you have to select a system of projective representatives of the non-zero vectors in $\mathbb{F}_q^k$ for the columns.

Answer 2

At worst you could simply search for vectors orthogonal to the generator matrix until you found a complete set of them for a parity check. But fortunately, given an $m\times n$ generator matrix in standard form, there is a trick to computing a parity matrix.

So $G=\begin{bmatrix}I_m& A\end{bmatrix}$ where $I_m$ is the identity matrix, and $A$ is an $m\times (n-m)$ matrix.

A parity matrix is given by $H=\begin{bmatrix}-A\\I_{n-m} \end{bmatrix}$ (you can just check by block-multiplication of matrices.)

To get to other generator matrices, notice that you're free to operate with row operations on the left of $G$. That is, $(RG)H=0$ by associativity of matrix multiplication. So you can make $RG$ turn into some generator for an equivalent code. For binary codes, the only equivalence will be permuting columns of the generator. By permuting the columns of $G$ and rows of $H$ in parallel, you will retain the relation $GH=0$ and will be able to change $G$ into your generator.

In summary, a way to go about computing the parity check matrix is the following. Permute the columns of the generator so that the first $n$ are linearly independent. Put the result in reduced row-echelon form. Use the trick above to find a parity matrix $H$ for this matrix, and then apply the inverse permutation on the rows of $H$ to get back to a parity for your original generator.

Answer 3

My preferred approach is algebraic. Note that I prefer to construct the parity check matrix first, and then deduce a matrix for the code, using exactly the same trick as rschwieb. (My parity check matrix is the transpose of his.) Constructing the parity check matrix first has some advantages IMHO, such as yielding directly immediately that the code is cyclic.

Construct the field with 16 elements as $\mathbf{F}_{2}[\alpha]$, with $\alpha$ a primitive element, so that the powers $1, \alpha, \dots, \alpha^{14}$ are distinct.

Now write the element $1, \alpha, \dots, \alpha^{14}$ as column vectors with respect to the basis $1, \alpha, \alpha^2, \alpha^3$ of $\mathbf{F}_{2}[\alpha]$ as a vector space over $\mathbf{F}_{2}$. So $$ 1 \mapsto \begin{bmatrix}0\\0\\0\\1\end{bmatrix},\quad \alpha \mapsto \begin{bmatrix}0\\0\\1\\0\end{bmatrix},\quad \alpha^2 \mapsto \begin{bmatrix}0\\1\\0\\0\end{bmatrix},\quad \alpha^3 \mapsto \begin{bmatrix}1\\0\\0\\0\end{bmatrix},\quad \alpha^4 \mapsto \begin{bmatrix}a_3\\a_2\\a_1\\a_0\end{bmatrix},\quad \text{etc,} $$ where $x^4+a_3 x^3 + a_2 x^2 + a_1 x + a_0$ is the minimal polynomial of $\alpha$ over $\mathbf{F}_{2}$.

Then these column vectors are the columns, written right-to-left, of the parity check matrix.

Erno Lancaster edited this adding

This uses the fact that the Hamming code is the set of all polynomials of degree $< 15$ with $\alpha$ as a root. In other words, a Hamming code is also a $t = 1$ BCH code.