Let's say I have 8 codewords and I want to find a linear code that is one-error correcting. I want to use a (7,4) Hamming Code and I need to find a generator matrix and a parity check matrix.

Could I could find a parity check matrix of the right size and correct d(C) and then find a generator matrix from the parity check matrix?

  • $\begingroup$ The $(n-k)\times n$ parity-check matrix $H$ defines the code as all (row) vectors $C$ such that $HC^T = \mathbf 0$. A linear binary code can correct single errors if its parity-check matrix has the property that all $n$ columns are distinct nonzero binary vectors; that's all that is needed. Think why it must be that $n \leq 2^{n-k}-1$. $\endgroup$ Feb 15, 2012 at 20:22
  • $\begingroup$ I am second guessing myself. Maybe k=3 instead since 2^3=8. I am sort of confused because I am not sure how to make a generator matrix. Maybe I could just use (111000000), (000111000), and (000000111). Is there an easier way? $\endgroup$ Feb 15, 2012 at 20:30
  • $\begingroup$ What does "Let's say I have $8$ codewords" mean? Have you been given $8$ specific codewords, e.g. $000000$, $000111$, $111000$, etc. (and if so, are you sure they form a linear code?) or have you been asked to find the generator matrix or parity check matrix of a code that can correct one error and just happens to have $8$ codewords? To paraphrase a famous person, it all depends on what meaning you have for "have" $\endgroup$ Feb 15, 2012 at 22:57

1 Answer 1


The question is very confusing. You say you have 8 codewords. Then you say you want to find a linear code. What, if any, is the connection between the 8 codewords you have and the linear code you want to find?

Then you say you want to use a $(7,4)$ Hamming code. But a $(7,4)$ Hamming code has 16 codewords, so how does this relate to the 8 codewords you say you have?

Then you say you need to find a generator matrix and a parity check matrix. Do you need these for the $(7,4)$ Hamming code? or is this for the 8 codewords you have?

The only part of the question I feel comfortable answering is, yes, you can find a generator matrix from a parity check matrix. Any good text or notes on coding theory should show you how to do that.

Then in the comments you ask whether there is an easier way than just using $(111000000)$, $(000111000)$, and $(000000111)$. I don't know if there is an easier way, since I can't figure out what you are trying to accomplish (see my first three paragraphs). But you can certainly use those vectors to form the generator matrix for an 8-word, 1-error-correcting linear code and, while there may be better ways, I can't imagine a simpler one.

It seems to me that questions about forming generator matrices and turning parity check matrices into generator matrices were answered in your earlier question, Coding Theory and Generating a matrix.


You must log in to answer this question.

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