2
$\begingroup$

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.

  • 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?2012-11-07
  • 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.2012-11-07
  • 0
    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!2013-10-31

1 Answers 1

4

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.