# Error Correction Capability of Linear Code

## Theorem

Let $C$ be a linear code.

Let $C$ have a minimum distance $d$.

Then $C$ corrects $e$ transmission errors for all $e$ such that $2 e + 1 \le d$.

## Proof

Let $C$ be a linear code whose master code is $V$.

Let $c \in C$ be a transmitted codeword.

Let $v$ be the received word from $c$.

By definition, $v$ is an element of $V$.

Let $v$ have a distance $e$ from $c$, where $2 e + 1 \le d$.

Thus there have been $e$ transmission errors.

Aiming for a contradiction, suppose $c_1$ is a codeword of $C$, distinct from $c$, such that $\map d {v, c_1} \le e$.

Then:

\(\displaystyle \map d {c, c_1}\) | \(\le\) | \(\displaystyle \map d {c, v} + \map d {v, c_1}\) | |||||||||||

\(\displaystyle \) | \(\le\) | \(\displaystyle e + e\) | |||||||||||

\(\displaystyle \) | \(<\) | \(\displaystyle d\) |

So $c_1$ has a distance from $c$ less than $d$.

But $C$ has a minimum distance $d$.

Thus $c_1$ cannot be a codeword of $C$.

From this contradiction it follows that there is no codeword of $C$ closer to $v$ than $c$.

Hence there is a unique codeword of $C$ which has the smallest distance from $v$.

Hence it can be understood that $C$ has corrected the transmission errors of $v$.

$\blacksquare$

## Sources

- 1996: John F. Humphreys:
*A Course in Group Theory*... (previous) ... (next): Chapter $6$: Error-correcting codes: Proposition $6.10$