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

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?

-
The simplest way to find a parity check matrix (nothing unique about them!) is described IMHO in azimut's answer. When you extend to BCH-codes you need to represent elements of a finite field in terms of a monomial basis such as in Prof. Caranti's answer. I would like you to study this question. In his kind comments to my answer Prof. Sarwate explains the technical reason for preferring a particular order for the non-zero columns. –  Jyrki Lahtonen Apr 5 '13 at 12:52
@DougSmith: You've got several good answers so far IMHO. Don't you think it would be more than appropriate to accept one of them by clicking on the check mark next to it? –  azimut Apr 8 '13 at 14:30

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.

-

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.

-

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.

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.