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 1


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).

  • $\begingroup$ 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) $\endgroup$
    – NiaBie
    Commented Apr 22, 2019 at 14:17
  • $\begingroup$ We certainly can calculate the syndrome (why not?) en.wikipedia.org/wiki/Hamming(7,4)#Parity_check $\endgroup$
    – leonbloy
    Commented Apr 22, 2019 at 14:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .