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}$.
Best Answer
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.