Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is: How can I construct a generator matrix for a one-error correcting linear code with 8 codewords? What would the values of the parameters [n,k] be and what would the size of the parity check matrix be?

Does this mean that I need to find a Code that is one error-correcting?

I think this means that the minimum distance between two of the vectors is 3?

share|improve this question
1  
Gerry Myerson and Dilip Sarwate have given you excellent hints. Surely the single error correcting Hamming code has been covered in your book. As observed by those gentlemen, you can shorten that code to find one containing exactly 8 codewords (and that is also the shortest possible, i.e. smallest possible $n$). Finding a generator matrix is equivalent to finding a vector space basis. If you want to turn a parity check matrix into a generator matrix, then see this answer. –  Jyrki Lahtonen Feb 12 '12 at 13:13
add comment

3 Answers 3

up vote 3 down vote accepted

If a $[n,k]$ linear binary code has $8$ codewords, you are being told that $k = \log_2 8 = 3$; an $[n,k]$ binary code has $2^k$ codewords. As discussed in Jyrki Lahtonen's answer to another question that you asked today, the Hamming spheres of radius $1$ centered at the $8$ codewords must not have any vectors in common. Since there are $1 + \binom{n}{1} = 1+n$ vectors in each such sphere, and $2^n$ vectors total, $n$ must be large enough so that $$2^n \geq 8(n+1) \Rightarrow n \geq 6.$$ Note also that you are asked for the generator matrix of the code which is a $k\times n$ matrix whose row-space (set of all $2^k$ linear combinations of the rows) is the set of codewords. So you could take the vectors suggested to you by Gerry Myerson as the rows of the generator matrix.

Be aware that shorter codes ($n$ smaller that $9$) can also be found. If you know about single-error-correcting Hamming codes, you can write down a $[7,4]$ code or a $[7,3]$ consisting of all the even weight codewords of the former, that can correct single errors.

share|improve this answer
    
Don't tell anyone, but you can even get the length down to 6 with a little extra effort. –  Gerry Myerson Feb 12 '12 at 5:37
    
@GerryMyerson I am aware of that, but given that the OP is a beginner, I thought that it would be better to point him towards something simpler that he might have learned about already. –  Dilip Sarwate Feb 12 '12 at 12:44
add comment

Yes, it means you need to find some $n$ and some 8 $n$-bit strings with minimum distance 3, and moreover those 8 strings must form a vector space.

One really simple way to do this is to use the vector space generated by the strings 111000000, 000111000, and 000000111. Here, $n=9$. But you can probably find something with a smaller value of $n$, and, in this business, smaller is better.

As for the parameters $n$ and $k$, and the size of the parity check matrix, and the construction of the generator matrix: do you not have a text or some notes defining these things and giving you examples?

By the way, if this is a homework problem, you are encouraged to use the homework tag.

share|improve this answer
    
What exactly do you mean when you say they must form a vector space? Can I not choose any combination that has minimum distance of 3? –  Jackson Hart Feb 12 '12 at 0:02
    
Oh, this isn't a homework question, we have a test soon so I am going through the book and doing as many problems as I can –  Jackson Hart Feb 12 '12 at 0:02
    
So n=9 and k=3 here I am thinking –  Jackson Hart Feb 12 '12 at 0:13
1  
Your question asks for a linear code. That's another way of saying the code words must form a vector space. Since you haven't told me the meanings of $n$ and $k$ (different texts may use different notation), I can't tell you whether $n=9$ and $k=3$, but that does seem likely. –  Gerry Myerson Feb 12 '12 at 2:22
add comment

Since this question is now quite old, I'm going to add the $n=6$ code alluded to:

000000
010101
001111
011010
100110
101001
110011
111100
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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