Let $\mathcal{X}$ be a binary linear code of length $n$, rank $k$ and distance $d$. Let $x=$ $\left(x_{1}, \ldots, x_{n}\right) \in \mathcal{X}$ be a codeword with exactly $d$ non-zero digits.

(a) Prove that $n \geqslant d+k-1$ (the Singleton bound).

(b) Prove that truncating $\mathcal{X}$ on the non-zero digits of $x$ produces a code $\mathcal{X}^{\prime}$ of length $n-d$, rank $k-1$ and distance $d^{\prime}$ for some $d^{\prime} \geqslant\left\lceil\frac{d}{2}\right\rceil$. Here $\lceil a\rceil$ is the integer satisfying $a \leqslant\lceil a\rceil<a+1, a \in \mathbb{R}$.

[Hint: Assume the opposite. Then, given $y \in \mathcal{X}$ and its truncation $y^{\prime} \in \mathcal{X}^{\prime}$, consider the coordinates where $x$ and $y$ have 1 in common (i.e. $x_{j}=y_{j}=1$ ) and where they differ $\left(\right.$ e.g. $x_{j}=1$ and $\left.y_{j}=0\right)$.]

(c) Deduce that $n \geqslant d+\sum_{1 \leqslant \ell \leqslant k-1}\left\lceil\frac{d}{2^{\ell}}\right\rceil$ (an improved Singleton bound).