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'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}$.

share|improve this question
    
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
1  
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
1  
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
show 2 more comments

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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.