error detection and correction

Error detection and correction (EDAC) is a collection of techniques which allows reliable delivery of digital data over unreliable communication channels.

Typically, messages are strings of ones and zeroes which we encode as elements of the vector space $Z_{2}^{n}$ (e.g. the Hamming space) called codewords. A set of codewords is called a code.

An error correcting code is a code for which it is possible to detect and correct some number of errors.

To correct $t$ errors, we need that for all possible received messages $x \in Z_{2}^{n}$ and codewords $y \in C$ , that there is no $z \in C$ such that $d_{H} (x, y) \leq t$ and $d_{H} (x, z) \leq t$ where $y \neq z$ ;
in other words, there must be only one way to have had $t$ errors.

Formally,

Let $C$ be a code with minimum Hamming distance $d$ .
Let $t$ be the largest integer such that $t < \frac{d}{2}$
Then $C$ can correct up to $t$ errors.
Such a code is called $t$ -error correcting.

A t-error correcting code is called perfect if

| C | \cdot ((\binom{n}{0}) + \dots + (\binom{n}{t})) = 2^{n}

i.e. every element of the Hamming space is Hamming distance $\leq t$ from some codeword.