# A question dealing with residual codes.

I've been reading about residual codes, and have come across several statements that I am having trouble showing.

(1.) By using the residual code, one can show that a $[16, 5, 8]$ binary code contains the all-one codeword.

(2.) All $[16, 5, 8]$ binary codes are equivalent.

For Part 1, I'm not sure how to use the residual codes. I'm having trouble with Part 2 as well. Any help would be greatly appreciated. Thanks in advance!

Edit: Below is the definition of a residual code.

Let $\mathcal{C}$ be an $[n,k]$ code and let $c \in \mathcal{C}$ have weight $w$. Let $\mathcal{I}$ be the set of coordinates on which $c$ is nonzero. Then, the residual code of $\mathcal{C}$ with respect to $c$ is the code of length $n-w$ punctured on all the coordinates of $\mathcal{I}$.

Partial Solution: Below is my thought process for solving Part $1$.

Let $\mathcal{C}$ be a $[16, 5, 8]$ binary code. Pick a codeword $c \in \mathcal{C}$ that has a weight of $8$. Then, the residual code $\mathcal{C}_1$ of $\mathcal{C}$ with respect to $c$ is an $[16 - 8, 5-1, d_1] = [8, 4, d_1]$ code, where $d_1 \geq \lceil{\frac{8}{2}}\rceil = 4$. By the Singleton Bound, $d_1 \leq 8 - 4 + 1 = 5$. Thus, $4 \leq d_1 \leq 5$. However, if $d_1 = 5$, then we have equality in the Singleton Bound, which implies $\mathcal{C}_1$ is MDS, which implies $\mathcal{C}_1$ is trivial, a contradiction. Therefore, $d_1 = 4$.

By permuting coordinates, we may assume $\mathcal{C}$ has a generator matrix $$G = \begin{bmatrix}1\ldots 1 & 0 \ldots 0\\G_0 & G_1\end{bmatrix}$$ where the first row is $c$ and $G_1$ is a generator matrix of $C_1$.

Now, every $[8,4,4]$ binary code is equivalent to the extended Hamming code $\widehat{\mathcal{H}_3}$. Thus, $G_1$ is a generator matrix for $\widehat{\mathcal{H}_3}$. Therefore, $G_1$ can take on the following form:

$$G_1 = \begin{matrix} 1&1 &1 &1 &1 &1 &1 &1 \\\ 1 &1 &0 &1 &0 &0 &0 &1 \\\ 1& 0& 0& 0& 0& 1& 1& 1 \\\ 1& 1& 0& 0& 1& 1& 0& 0 \end{matrix}$$

This is where I'm stuck. Can I say the code $\mathcal{C}_0$ corresponding to $G_0$ is also a $[8,4,4]$ code? Clearly $G_0$ is a $4 \times 8$ matrix, and by the Singleton Bound with a similar argument as above, its minimum distance $d_0 \leq 4$. If so, we can make it have the same generator matrix as $G_1$, which will give is the all-one codeword in $\mathcal{C}$.

Then, I think Part $2$ would follow since $G_1$ and $G_0$ are both equivalent to the generator matrix of ${\mathcal{H}_3}$.

-
I hope someone comes along who knows what a residual code is. Also, it wouldn't hurt if you told us where you came across these statements. –  Gerry Myerson Nov 8 '12 at 2:37
My apologies Gerry. I added the definition of residual codes to my question. –  josh Nov 8 '12 at 2:53
@josh: Just out of curiosity, what book is this from? I'm interested in coding theory as well, though I'm just a beginner. –  Snowball Nov 8 '12 at 2:55
In the first part I would use the residual code to show that there cannot exist a word of weight $w$ in the range $9\le w\le 15$. Griesmer bound gives us this. For example the residual code of a weight 10 word would have length $n=6$, $k=4$ and $d\ge3$, but the Griesmer bound tells us that the length of a 4-dim code of minimum distance 3 is at least $3+2+1+1=7>6$. After this I would resort to the bit that the total weight of all the 32 words of a $[16,5,8]$ code must be $2^{5-1}\cdot 16=256$. As $31\cdot8=248<256$, there must be a word of weight $>8$. We saw that $16$ is the only possibility. –  Jyrki Lahtonen Nov 9 '12 at 23:03
I think that then your approach will settle part 2, because at this point we know that the weight enumerator of the code must be $$1+30z^8+z^{16},$$ IOW there are 30 words of weight 8, the all-zero word and the all-ones word. Then you get the extra constraint that the weight 8 word of $G_1$ must be matched with the all zeros word of $G_0$. It sounds like you can then fill in the details. Way past my bedtime anyway, so this will have to do for now. –  Jyrki Lahtonen Nov 9 '12 at 23:09

Thank to Jyrki's comments and assistance, I was able to construct a solution. I will rewrite what was said in the comments and fill in most of the details for anyone else who is interested in the solution.

PART $1$: Let $\mathcal{C}$ be a $[16, 5, 8]$ binary code. We will use residual code $\mathcal{C}_1$ of $\mathcal{C}$ to show no codewords of weight $9 \leq w \leq 15$ exists. An important theorem about residual codes tells us that for $c \in \mathcal{C}$ of weight $w < 2\cdot 8 = 16$, $\mathcal{C}_1$ is a $[16 - w, 4, d_1]$ code, where $d_1 \geq 8 - w + \lceil\frac{w}{2}\rceil$.

Now, we run through all the cases for $9 \leq w \leq 15$ and show that such residual codes cannot exists.

$\bullet$ $w = 9 \Rightarrow C_1$ is a $[7, 4, d_1]$ code, with $d_1 \geq 4$. By the Singleton Bound, $d_1 \leq 7 - 4 + 1 = 4$. Thus, $d_1 = 4 \Rightarrow \mathcal{C}_1$ is a binary MDS code $\Rightarrow$ $\mathcal{C}_1$ is trivial, a contradiction. Thus, such a code doesn't exist.

$\bullet$ $w = 10 \Rightarrow C_1$ is a $[6, 4, d_1]$ code, with $d_1 \geq 3$. By the Singleton Bound, $d_1 \leq 6 - 4 + 1 = 3$. Thus, $d_1 = 3 \Rightarrow$ such a code doesn't exist by the same argument for $w=9$.

$\bullet$ $w = 11 \Rightarrow C_1$ is a $[5, 4, d_1]$ code, with $d_1 \geq 3$. By the Singleton Bound, $d_1 \leq 5 - 4 + 1 = 2$. If $d_1 = 2$, such a code doesn't exits (as before). If $d_1 = 3$, we also get nonexistence due to the Sphere Packing Bound as $2^4 > \frac{2^5}{{5\choose 0} + {5\choose 1} }$.

$\bullet$ $w = 12 \Rightarrow C_1$ is a $[4, 4, d_1]$ code, with $d_1 \geq 2$. By the Singleton Bound, $d_1 \leq 4 - 4 + 1 = 1$. Therefore, such a code doesn't exists.

$\bullet$ $w = 13, 14, 15 \Rightarrow n < 4 = k$, which doesn't happen in any $[n,k,d]$ code.

Now, we use the following fact. For a non-trivial binary $[n,k,d]$ code $\mathcal{C}$, the sums of the weights of the codewords in $\mathcal{C}$ is $n \cdot 2^{k-1}$. Therefore, the sums of the weights of the codewords in our $[16, 5, 8]$ code $\mathcal{C}$ is $16\cdot 2^{5-1} = 16 \cdot 16 = 256$. Since $\mathcal{C}$ is linear, it contains the all-zero codeword, so we only have to consider $31$ of the codewords. Since $31 \cdot 8 = 248 < 256$, there must be a codeword of weight $> 8$. Since we showed $w \neq 9, \ldots 15$, this codeword must be of weight $16$. Therefore $\mathcal{C}$ contains the all-one codeword.

PART $2$:First note that since $\mathcal{C}$ contains the all-one codeword, then $A_i = A_{16-i}$, for $0 \leq i \leq 16$. $A_i$ denotes the number of codewords in $\mathcal{C}$ of weight $i$.

Since $\mathcal{C}$ contains the all-one codeword, $A_0 = A_{16} = 1$. Since the minimum distance is $8$, $A_1 = \ldots = A_7 = 0$, which implies that $A_{15} = \ldots A_{9} = 0$. Therefore, $A_8 = 30$ since the $A_i$'s range over all the 32 codewords of $\mathcal{C}$.

Now, Pick a codeword $c \in \mathcal{C}$ that has a weight of $8$. Then, the residual code $\mathcal{C}_1$ of $\mathcal{C}$ with respect to $c$ is an $[16 - 8, 5-1, d_1] = [8, 8, d']$ code, where $d_1 \geq \lceil{\frac{8}{2}}\rceil = 4$. By the Singleton Bound, $d_1 \leq 8 - 4 + 1 = 5$. Thus, $4 \leq d_1 \leq 5$. However, if $d_1 = 5$, then we have equality in the Singleton Bound, which implies $\mathcal{C}_1$ is MDS, which implies $\mathcal{C}_1$ is trivial, a contradiction. Therefore, $d_1 = 4$.

By permuting coordinates, we may assume $\mathcal{C}$ has a generator matrix $$G = \begin{bmatrix}1\ldots 1 & 0 \ldots 0\\G_0 & G_1\end{bmatrix}$$ where the first row is $c$ and $G_1$ is a generator matrix of $C_1$.

Now, every $[8,4,4]$ binary code is equivalent to the extended Hamming code $\widehat{\mathcal{H}_3}$. Thus, $C_1$ is equivalent to $\widehat{\mathcal{H}_3}$, and $G_1$ is a generator matrix for $\widehat{\mathcal{H}_3}$. Therefore, $G_1$ can take on the following form:

$$G_1 = \begin{matrix} 1&1 &1 &1 &1 &1 &1 &1 \\\ 1 &1 &0 &1 &0 &0 &0 &1 \\\ 1& 0& 0& 0& 0& 1& 1& 1 \\\ 1& 1& 0& 0& 1& 1& 0& 0 \end{matrix}$$

Now, notice that the row of weight $8$ in $G_1$ will be matched with the all-zero word in $G_0$ due to the weight distribution in $\mathcal{C}$. Furthremore, every other row of $G_1$ (being a row of weight $4$) will correspond to a row of weight $4$ in $G_0$, again due to the weight distribution of $\mathcal{C}$.

Therefore, the minimum weight of any nonzero codeword in $\mathcal{C}_0$, the code corresponding to $G_0$, would be $4$. Since $\mathcal{C}_0$ is linear, this is the same as the minimum distance. Thus, $C_0$ is also a $[8,4,4]$ binar code, which is also equivalent to $\widehat{\mathcal{H}_3}$. Since both $C_1$ and $C_2$ are equivalent to $\widehat{\mathcal{H}_3}$, all binary $[16,5,8]$ codes would be equivalent.

-