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.

I have been reading about residual codes, and showing how to improve upper bounds on the number of codewords for certain types of codes. I've come across one problem that I am having trouble with.

It starts with showing that $B_2(13, 6) \leq 2^4$ by using redisual codes, where $B_2(13, 6)$ is the number of binary linear codewords of length $13$ with a minimum distance of $6$.

Then, it asks to construct a linear binary code that meets this bound.

I am able to show $B_2(13, 6) \leq 2^4$, but I'm having trouble constructing such a code that meets this bound. Can anyone help with this construction? Thanks in advance.

share|improve this question
1  
The first-order binary Reed-Muller code is a $[16, 5, 8]$ code and if we shorten this code by deleting the over-all parity check bit and taking only the remaining codewords of even weight, then we are left with a $[15,4,8]$ linear binary code. Can this be shortened further to a $[13,4,6]$ linear code? –  Dilip Sarwate Nov 7 '12 at 4:47
1  
Thank you Dilip! I was trying to construct this code directly, but I keep forgetting that I can take existing codes and shorten them. In order to obtain a $[13, 4, 6]$ code from the $[15,4,8]$ code, I can delete a nonzero coordinate from the $[15,4,8]$ code, which results in a $[14, 4, 7]$ code. By repeating this procedure with the $[14, 4, 7]$ code, I can obtain my desired $[13, 4, 6]$ code. –  josh Nov 7 '12 at 16:33
    
How did you go about showing B2(13,6) ≤ 2^4? I understand B2(13,6) ≤ 2^5 by showing the nonexistence of a [13,6,6] code. Thanks! –  user104480 Oct 31 '13 at 8:54

1 Answer 1

up vote 5 down vote accepted

Thanks to Dilip in the comments, I was able to come up with a solution. I figured I would post a solution for anyone else interested in the problem.

As mentioned above, consider the first-order binary Reed-Muller code, $\mathcal{R}(1, 4)$. This is a $[2^4, 4+1, 2^{4-1}] = [16, 5, 8]$ code. Then, shorten this code by deleting the over-all parity check bit and taking only the remaining codewords of even weight. By doing this, we we are then left with a $[15, 4, 8]$ (which can be verified by looking at the generator matrix for $\mathcal{R}(1, 4)$).

Now, further shorten this code by deleting a nonzero coordinate. We will be left with a $[14, 4, 7]$ code. By shortening the $[14, 4, 7]$ code by deleting another nonzero coordinate, we will get a $[13, 4, 6]$ code.

share|improve this answer
1  
+1 Thanks for taking the time to write out a solution. –  Dilip Sarwate Nov 7 '12 at 22:21

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.