= Solution
Apply part (b) repeatedly. After the first puncturing, the code has rank $k-1$, length $n-d$, and minimum distance at least $\lceil d/2\rceil$. Repeating with a minimum-weight codeword at each stage gives
$$
n\geq d+\left\lceil\frac d2\right\rceil
+\left\lceil\frac d{2^2}\right\rceil+cdots
+\left\lceil\frac d{2^{k-1}}\right\rceil,
$$
because nested ceilings obey
$$
\left\lceil\frac{\lceil d/2^j\rceil}{2}\right\rceil
=\left\lceil\frac d{2^{j+1}}\right\rceil.
$$
Thus
$$
\boxed{n\geq d+\sum_{1\leq l\leq k-1}
\left\lceil\frac d{2^l}\right\rceil},
$$
which is the binary <Griesmer bound>.
Back to article page
