2
$\begingroup$

Let $C$ be a binary $[n,k]$ linear code. If $C$ has a codeword of odd weight then the codewords of even weightin $C$ form an $[n,k-1]$ binary linear code. Can you prove that?

$\endgroup$
1
$\begingroup$

Let $E \subset C$ be the code containing all the codewords of even weight in $C$. In order to show that the code is linear, we only need to show that it is closed under addition. In other words, we need to show that if $a, b \in E$, then $a + b \in E$.

Note that $a + b$ surely is in the original code $C$, because $C$ is linear. This means that it is sufficient to show that $a + b$ is of even weight.

Suppose that $a$ is of weight $2m_1$, $b$ is of weight $2m_2$, and the $1$s in $a$ and $b$ overlap at $r$ places. Then, the weight of $a + b$ is $2m_1 + 2m_2 - 2r$, which surely is even. Thus, $E$ is closed under addition and is a linear code!

You can show that the dimension of $E$ is precisely $1$ less than that of $C$ (i.e. that half of the codewords in $C$ are of even weight) by showing that there are equally many codewords of odd weight and even weight in $C$.

Using similar reasoning as before, it can be shown that the sum of two codewords of odd weights is of even weight and that the sum of codewords of weights of different parities is of odd weight.

Let $c \in C$ be a codeword of odd weight. All the sums obtained by adding $c$ and a codeword of odd weight are thus of even weight. Furthermore, they are all distinct, because $C$ is a group. This means that there are at least as many words of even weight as of odd weight in $C$.

Similarly, the sums obtained by adding $c$ and the codewords of even weight indicate that there are at least as many codewords of odd weight as of even weight in $C$.

Therefore, the amount of even codewords in $C$ must be precisely the same as the amount of odd codewords in $C$. In other words, half of the codewords in $C$ is of even weight, which means that the dimension of the code $E$ of even-weighted codewords is $1$ less than that of $C$.

$\endgroup$
3
$\begingroup$

Hint: Consider the linear mapping $f$ from $C$ to $GF(2)$ defined by $$ f:(a_1,a_2,\ldots,a_n)\mapsto a_1+a_2+\cdots+a_n. $$ Show that this is onto. Apply the rank-nullity theorem (familiar from linear algebra) to it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.