[proofplan] The proof rests on the [triangle inequality](/page/Triangle%20Inequality) for the Hamming metric and the definition of minimum distance $d = \min\{d(c_1, c_2) : c_1, c_2 \in C,\, c_1 \ne c_2\}$. For detection: any word at distance between $1$ and $d-1$ from a codeword cannot be a different codeword, because every pair of distinct codewords is at distance at least $d$. For correction: if $x$ lies within distance $e = \lfloor (d-1)/2 \rfloor$ of some codeword $c_1$, the triangle inequality forces every other codeword to lie at distance strictly greater than $e$ from $x$, so $c_1$ is uniquely closest. Sharpness in each case follows by constructing witness codewords at the boundary $d(c_1, c_2) = d$. [/proofplan] [step:Record definitions and the Hamming triangle inequality] Let $n$ denote the blocklength, so $C \subseteq \mathbb{F}_2^n$ (the argument works for any alphabet; we write $\mathbb{F}_2^n$ for concreteness). Recall that the Hamming distance \begin{align*} d : \mathbb{F}_2^n \times \mathbb{F}_2^n &\to \{0, 1, \dots, n\} \end{align*} is a metric, so for any $u, v, w \in \mathbb{F}_2^n$, \begin{align*} d(u, w) \le d(u, v) + d(v, w). \end{align*} The minimum distance of $C$ is $d = \min\{d(c_1, c_2) : c_1, c_2 \in C, \; c_1 \ne c_2\}$, so $d(c_1, c_2) \ge d$ for every pair of distinct codewords $c_1, c_2 \in C$. Set $e = \lfloor \frac{d-1}{2} \rfloor$; this integer satisfies $2e \le d - 1$, equivalently $d - e \ge e + 1 > e$. A code is **$t$-error detecting** if every received word $x$ with $1 \le d(x, c) \le t$ for some $c \in C$ satisfies $x \notin C$ (so the channel corruption is detected as non-codeword). A code is **$t$-error correcting** if every received word $x$ with $d(x, c) \le t$ for some $c \in C$ has $c$ as its unique closest codeword (so minimum distance decoding recovers $c$). [/step] [step:Prove $(d-1)$-error detection] Suppose $c \in C$ is sent and $x \in \mathbb{F}_2^n$ is received with $1 \le d(x, c) \le d - 1$. We must show $x \notin C$. Assume for contradiction that $x \in C$. Then $x$ and $c$ are two codewords with $d(x, c) \ge 1 > 0$, so $x \ne c$, and the minimum distance hypothesis gives \begin{align*} d(x, c) \ge d. \end{align*} This contradicts $d(x, c) \le d - 1$. Hence $x \notin C$, and the error is detected. Since this holds for every $c \in C$ and every $x$ at distance between $1$ and $d-1$ from $c$, the code is $(d-1)$-error detecting. [/step] [step:Exhibit an undetectable pattern of exactly $d$ errors] By definition of $d$, there exist distinct codewords $c_1, c_2 \in C$ with $d(c_1, c_2) = d$. Let $c_1$ be transmitted and let the channel corrupt $c_1$ in exactly those $d$ coordinates where $c_1$ and $c_2$ disagree; the received word is then $c_2$. Since $c_2 \in C$, the received word is a codeword, so the decoder accepts it without detecting any error. Thus a pattern of exactly $d$ errors has gone undetected, which proves the sharpness claim in (i). [/step] [step:Prove $e$-error correction via the triangle inequality] Suppose $c_1 \in C$ is sent and $x \in \mathbb{F}_2^n$ is received with $d(x, c_1) \le e$. We claim that $c_1$ is the unique codeword achieving $\min_{c \in C} d(x, c)$. Let $c_2 \in C \setminus \{c_1\}$ be any other codeword. By the triangle inequality applied to the triple $(c_1, x, c_2)$, \begin{align*} d(c_1, c_2) \le d(c_1, x) + d(x, c_2), \end{align*} so \begin{align*} d(x, c_2) \ge d(c_1, c_2) - d(c_1, x) \ge d - e \ge e + 1 > e \ge d(x, c_1), \end{align*} using $d(c_1, c_2) \ge d$ (minimum distance), $d(c_1, x) \le e$ (hypothesis), and $d - e \ge e + 1$ (definition of $e$). Hence $d(x, c_2) > d(x, c_1)$ for every $c_2 \in C \setminus \{c_1\}$, so $c_1$ is the unique closest codeword and minimum distance decoding returns $c_1$. This shows $C$ is $e$-error correcting. [guided] We want to show that if $x$ is at Hamming distance at most $e = \lfloor (d-1)/2 \rfloor$ from a codeword $c_1$, then $c_1$ is the unique closest codeword to $x$. The natural tool is the triangle inequality — distance is a metric on $\mathbb{F}_2^n$, so for any three points $c_1, x, c_2$, \begin{align*} d(c_1, c_2) \le d(c_1, x) + d(x, c_2), \end{align*} which rearranges to \begin{align*} d(x, c_2) \ge d(c_1, c_2) - d(c_1, x). \end{align*} Now we bound each term using our hypotheses. Because $c_1 \ne c_2$ are both codewords, $d(c_1, c_2) \ge d$ by the definition of minimum distance. Because $d(c_1, x) \le e$ by hypothesis, we can strip off at most $e$ from the right-hand side. Combining: \begin{align*} d(x, c_2) \ge d - e. \end{align*} The crucial arithmetic is then: is $d - e > e$? By definition $e = \lfloor (d-1)/2 \rfloor$, so $2e \le d - 1$, equivalently $d - e \ge e + 1$. Hence \begin{align*} d(x, c_2) \ge d - e \ge e + 1 > e \ge d(x, c_1). \end{align*} In words, every codeword other than $c_1$ is strictly farther from $x$ than $c_1$ is. Minimum distance decoding — which returns the unique nearest codeword when one exists — therefore returns $c_1$. Notice where the floor function enters: if $d$ is odd, $d - 1$ is even and $e = (d-1)/2$, with $d - e = (d+1)/2 = e + 1$; the bound is exactly tight. If $d$ is even, $e = (d-2)/2$, with $d - e = (d+2)/2 = e + 2$; we have an extra unit of slack. Either way $d - e \ge e + 1$, and this strict inequality is what makes the nearest-codeword unique rather than merely one of the minimisers. Geometrically this is the classical ball-packing argument: the closed Hamming balls $B(c, e)$ centred at distinct codewords are pairwise disjoint, precisely because any point in $B(c_1, e)$ is strictly closer to $c_1$ than to any other codeword. [/guided] [/step] [step:Exhibit an uncorrectable pattern of $e + 1$ errors] We show there exists a pattern of exactly $e + 1$ errors on which minimum distance decoding may fail. Pick distinct codewords $c_1, c_2 \in C$ with $d(c_1, c_2) = d$; such a pair exists by definition of $d$. Let $S \subseteq \{1, \dots, n\}$ be the set of $d$ coordinates in which $c_1$ and $c_2$ disagree, and let $S' \subseteq S$ be any subset of size $e + 1$ (possible since $|S| = d \ge e + 1$ as $2e \le d - 1 < d$). Define a received word $x \in \mathbb{F}_2^n$ coordinate by coordinate: \begin{align*} x_i = \begin{cases} (c_2)_i & \text{if } i \in S' \\ (c_1)_i & \text{if } i \notin S'. \end{cases} \end{align*} We compute the two relevant distances. - For $i \in S'$, we have $x_i = (c_2)_i \ne (c_1)_i$, so $x$ and $c_1$ disagree on $S'$. For $i \notin S'$, we have $x_i = (c_1)_i$, so $x$ and $c_1$ agree. Hence $d(x, c_1) = |S'| = e + 1$. - For $i \in S'$, we have $x_i = (c_2)_i$, so $x$ and $c_2$ agree. For $i \in S \setminus S'$, we have $x_i = (c_1)_i \ne (c_2)_i$, so they disagree. For $i \notin S$, we have $x_i = (c_1)_i = (c_2)_i$ (since $c_1$ and $c_2$ agree off $S$), so $x$ and $c_2$ agree. Hence $d(x, c_2) = |S \setminus S'| = d - (e + 1)$. Using $2e \le d - 1 < d$, the quantity $d - (e + 1) \le d - 1 - e \le e$ if $d$ is odd (so $2e = d - 1$ and $d - (e+1) = e$), and $d - (e+1) \le e + 1$ if $d$ is even. In particular \begin{align*} d(x, c_2) = d - (e + 1) \le e + 1 = d(x, c_1). \end{align*} Therefore $c_1$ is **not** the unique closest codeword to $x$ — the codeword $c_2$ is at most as close. If the channel sent $c_1$ and produced exactly the $e + 1$ errors on the coordinates in $S'$, the decoder, faced with $x$, cannot reliably distinguish $c_1$ from $c_2$. Consequently $C$ cannot correct all patterns of $e + 1$ errors, which is the sharpness claim in (ii). [guided] We want to construct an explicit "bad" error pattern of size $e + 1$ that minimum distance decoding cannot correct. The idea is to start with a pair of codewords at the smallest possible distance — namely $d(c_1, c_2) = d$, which exists because $d$ is attained — and then corrupt $c_1$ by flipping bits that bring it closer to $c_2$. Specifically, let $S$ be the $d$ coordinates where $c_1$ and $c_2$ differ. Pick a subset $S' \subseteq S$ of size $e + 1$ (we need $e + 1 \le d$, which holds because $2e \le d - 1 < d$). Flip $c_1$ in exactly the coordinates of $S'$: this is $e + 1$ bit flips. Call the result $x$. Now $x$ agrees with $c_2$ on $S'$ (we flipped $c_1$ towards $c_2$ there), so $x$ and $c_2$ differ only on the remaining $d - (e+1)$ coordinates of $S \setminus S'$. Hence \begin{align*} d(x, c_2) = d - (e + 1), \qquad d(x, c_1) = e + 1. \end{align*} How do these compare? We have \begin{align*} d(x, c_2) = d - (e+1) \le d - 1 - e \le e = d(x, c_1) - 1 \end{align*} when $d$ is odd (so $2e = d - 1$), and \begin{align*} d(x, c_2) = d - (e+1) \le e + 1 = d(x, c_1) \end{align*} when $d$ is even (so $2e = d - 2$). In either case $d(x, c_2) \le d(x, c_1)$. Even in the best sub-case we have a tie or we have $c_2$ strictly closer — in neither case is $c_1$ uniquely closest. The decoder faced with $x$ has no way to recover $c_1$: either it picks $c_2$ outright (strict case) or it must break a tie (boundary case). A $(e+1)$-error correcting code would, by definition, always return $c_1$ on such a received word; our $C$ cannot. The takeaway is that the minimum distance $d$ controls the error capability *exactly*: the floor $\lfloor (d-1)/2 \rfloor$ is both achieved and sharp. Pushing one bit further into the gap between two closest codewords breaks decoding. [/guided] [/step] [step:Conclude parts (i) and (ii)] Parts (i) and (ii) have been established in full: every error of weight at most $d - 1$ is detectable (with the pattern of $d$ errors transforming $c_1 \to c_2$ providing the sharpness witness), and every error of weight at most $e = \lfloor (d-1)/2 \rfloor$ is correctable by nearest-codeword decoding (with the pattern above providing the sharpness witness for $e + 1$). This completes the proof. [/step]