Error Correction Capability of Linear Code

From ProofWiki
Jump to navigation Jump to search

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