# How to write the parity-check matrix of Hamming code?

I have read some questions about this topic, but I am still not clear about some concepts about Hamming code.

If we want to write a parity-check matrix for $$n$$ information positions(with single error-correcting), we will first calculate the number of check positions $$r$$ with solve the inequlity $$2^r-1\ge n + r$$. Then we know that the size of the matrix is $$r\times(n + r)$$. And I know from wikipedia that the matrix of size $$4\times7$$ is $$\begin{pmatrix} 1&1&0&1&1&0&0\\ 1&0&1&1&0&1&0\\ 0&1&1&1&0&0&1\\ \end{pmatrix}$$

But I still have some questions:

1. I am not sure whether the number of column of parity-check matrix is $$2^r-1$$ or $$n + r$$. (For example, what is the number of column of the parity-check matrix for 3 information positions?)
2. I know that the last $$r$$ columns of the matrix is an identity matrix, but I don't know how to write other columns of the matrix. What's the regularity of it? Can I change the order of them?

## 1 Answer

A Hamming code has minimum distance three. This implies that, among the columns of the parity check matrix $$H$$, oen can find three LD (linearly dependent) elements, but there are no two or less LD columns. If you think a little about it, tha just means that $$H$$ has different columns (and different from zero).

Then, to construct the matrix $$H$$ is very simple: fix $$r=n-k$$ (column length), and fill $$H$$ with all the possible different (not zero) columns of length $$r$$. There are $$2^r-1$$ possible columns. The order does not matter (if we want the code to be systematic, we can put the identity on the right).

• So that we can't calculate the syndrome $Hx$ of a received n-tuple $x$ to check whether an error has occured? (I think I may confuse the Hamming code with other conceptions) Commented Apr 22, 2019 at 14:17
• We certainly can calculate the syndrome (why not?) en.wikipedia.org/wiki/Hamming(7,4)#Parity_check Commented Apr 22, 2019 at 14:32