0
$\begingroup$

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?
$\endgroup$
0
$\begingroup$

A Hamming code has minimum distance 3, which implies that the parity check matrix $H$ has som $3$ LD (linearly dependent) columns, but it has no $2$ or less LD columns. If you think a little about that, that just means that $H$ has different columns (and different from zero) (if you didn't understant the above, please re read it).

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.