# 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$