Covering radius and Binary Even weight codes

Question

Stumbled up on the statement: "if we puncture a binary even weight code the covering radius decreases by one", yet I'm having some difficulty proving it.

It's mainly because I don't see where the even weight of the codewords comes into play. I was able to prove that puncturing a binary code would not necessarily change the covering radius with an example, but can't prove said statement. Am I missing an obvious step?

Answer 1

Let $\mathcal{C}$ be your code (of length $n$), and let $\rho$ be its covering radius. To each vector $x\in\Bbb{F}_2^n$ let $d_{\mathcal{C}}(x)$ be the minimum Hamming distance from a codeword of $\mathcal{C}$ to $x$. It follows that $$\rho=\max\{d_{\mathcal{C}}(x)\mid x\in\Bbb{F}_2^n\}.$$

Let $\mathcal{C}'$ be the punctured code. Similarly, for all $x\in\Bbb{F}_2^n$ let $x'$ be the corresponding punctured vector. Consider a vector $y\in\Bbb{F}_2^{n-1}$.

Justify the following:

• There are two vectors, $x$ and $\overline{x}$, differing at the punctured position, such that $x'=y=\overline{x}'$.
• The weights of $x$ and $\overline{x}$ have opposite parities.
• Because all the words of $\mathcal{C}$ have an even weight, the distances $d_{\mathcal{C}}(x)$ and $d_{\mathcal{C}}(\overline{x})$ have opposite parities also.
• Therefore either $d_{\mathcal{C}}(x)$ or $d_{\mathcal{C}}(\overline{x})$ is $\le\rho-1$.
• Therefore $d_{\mathcal{C'}}(y)\le\rho-1$. In other words, the covering radius of $\mathcal{C}'$ is at most $\rho-1$.
• But if $d_{\mathcal{C}}(x)=\rho$, then $d_{\mathcal{C'}}(x')\ge\rho-1$, so the covering radius of $\mathcal{C'}$ is exactly $\rho-1$.