easy coding theory prob

luther_driggers · New Member Offline Joined: 10 Dec 2004 Posts: 19

The question in the book says : Determine the smallest integer n for which a single-error correcting binary linear code of block length n carrying 62 bits of information per codeword can be constructed.

This mean we need distance 3 which leads me to believe that the question is asking for the corresponding Hamming code. Meaning that I would solve $n=\frac{2^{n-62}-1}{2-1} \Rightarrow n=68$ . The problem is that I have no way to show that I couldn't do it with a smaller n. Any suggestions? Is this a well known fact, because it's not explicit in my text book.

Basically I'm looking for a matrix of the form $H=[A_{62 \times n-62} I_{62} ]$ with coefficients in $Z_2$ and no two columns of H are linearly dependent and n is as small as possible.... maybe it's just obvious that $n \not< 68$

**Posted:** Mon Feb 14, 2005 9:44 pm

jmerry

In order to carry 62 bits of information in the $n$ -bit error-correcting code, we must place $2^{62}$ disjoint unit balls in the $n$ -dimensional hypercube. Each ball has $n+1$ elements, so $\frac{2^n}{n+1}\ge 2^{62}$ . This gives $2^{n-62}\ge n+1$ , which is true when $n>68$ .

You can't do it with 68 or fewer bits. You should be able to do it with 69.

**Posted:** Mon Feb 14, 2005 9:55 pm

luther_driggers · New Member Offline Joined: 10 Dec 2004 Posts: 19

thankyou. btw sorry about the 68 - i was comparing to k for some reason

$2^{68-62}-1=63$

which isn't even what i thought i was looking for. Blush

Your argument is clear.

**Posted:** Wed Feb 16, 2005 12:02 am