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