Logo der Uni Stuttgart
Error-Correcting Codes

The error-correcting codes are a tool aimed to improve the reliability of transmissions over a noisy channel. The idea is to send more data over the channel than the amount of information to be transferred. This is called redundancy. If this redundancy is well structured, it will be possible to correct errors caused by the channel, to find the intial information, which is sent at the beginning despite the noise.
A large family of error correcting codes is composed of codes consisting of blocks. The information will be devided in constant blocks and each block is transmitted independently with a reasonable redundancy. The largest subfamily of these codes is the family of linear codes, which are introduced in the following:

Code 1:

The repetition code is the simplest error-correcting code. It consists on repeating each transmitted symbol n-times.
Example for n=3:

  • Bit sequence to be encoded : 10010
  • Encoded sequence : 111 000 000 111 000

The repetition code has a hamming distance d=n.

  • It is able to correct $\lfloor \frac{\mathbf{n}-1}{2} \rfloor$errors pro codeword.
  • If the number of errors exceeds $\lfloor \frac{\mathbf{n}-1}{2} \rfloor$errors pro codeword,the transmitted codewords will be "wrongly" corrected by the decoder.

Repetition codes which have an odd length are perfect codes.

The repetition code of length 3 corresponds to the binary (3,1) hamming code.

Codes 2,3:
  • Are codes with a code rate r=$\frac{\mathbf{k}}{\mathbf{n}}$=$\frac{1}{2}$

The following matrices explain how to calculate the redundant bits for the above coding schemes :

\begin{align*} M_{code2}= \left(\begin{array}{cc|cc} 0 &0&0&0\\ 0&1&1&0\\ 1&0&1&1\\ 0&1&0&1 \end{array} \right) \end{align*}
  • the encoding rule is $\mathbf{c}=(\mathbf{u},{\mathbf{u}_{1}} \oplus {\mathbf{u}_{2}},\mathbf{u}_{1}$)
\begin{align*} M_{code3}= \left(\begin{array}{ccc|ccc} 0&0&0&0&0&0\\ 0&0&1&0&1&1\\ 0&1&0&1&0&1\\ 0&1&1&1&1&0\\ 1&0&0&1&1&0\\ 1&0&1&1&0&1\\ 1&1&0&0&1&1\\ 1&1&1&0&0&0 \end{array} \right) \end{align*}
  • the encoding rule is $\mathbf{c}=(\mathbf{u},{\mathbf{u}_{1}} \oplus {\mathbf{u}_{2}},{\mathbf{u}_{1}} \oplus {\mathbf{u}_{3}},{\mathbf{u}_{2}} \oplus {\mathbf{u}_{3}}$)

Code 4:

Hamming codes are a category of linear codes of Forward Error Correcting(FEC) codes.
The notation (7,4) means that the codewords have a length of 7 bits.

  • the original message is composed of 4 bits
  • the other bits called "redundant bits" are added to detect and correct errors.

4 Data Bits + 3 Additional Check Bits = 7 Bit Hamming Code

The transmitted message $d= d_1d_2d_3d_4$ is mapped to a codeword $P_1P_2d_1P_3d_2d_3d_4$ where the parity bits are calculated by using the following equations:

\begin{align*} P_1 &= {d_1} \oplus{d_2} \oplus{d_4}\\ P_2 &= {d_1} \oplus{d_3} \oplus{d_4}\\ P_3 &= {d_2} \oplus{d_3} \oplus{d_4} \end{align*}

Hamming(7,4) with extra parity bit (Hamming(8,4)):

the same [7,4] example from above with an extra parity bit $P_4= {P_1}\oplus{P_2}\oplus{d_1}\oplus{P_3}\oplus{d_2}\oplus{d_3}\oplus{d_4}$

Hamming codes are called "perfect codes": they achieve the highest possible rate for codes with their block length and minimum distance of three.

the characteristics of the above mentioned (8,4)hamming code can be summarized as follows:

  • code rate r=$\frac{\mathbf{k}}{\mathbf{n}}$=$\frac{1}{2}$
  • detect up to two-bits errors(no correction is attempted)
  • correct one-bit errors
  • the minimal hamming distance between any 2 correct codewords is 3.