# Constructing a Linear Binary Code

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.

-
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
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

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.