©2018 by macnabbs. Proudly created with Wix.com

 
  • Alibek Jakupov

Information Theory: Step 5 Error control



Here's the 5th step of our introduction to the Information Theory. In this article we are going to cover the techniques that enable reliable delivery of digital data over unreliable communication channels.

Types of error control:

  • Error detection is the detection of errors caused by noise or other impairments during transmission from the transmitter to the receiver.

  • Error correction is the detection of errors and reconstruction of the original, error-free data.

The general idea for achieving error detection and correction is to add some redundancy (i.e., some extra data) to a message, which receivers can use to check consistency of the delivered message, and to recover data determined to be corrupted.


Error correction may generally be realized in different ways:

  • Automatic repeat request (ARQ) (sometimes also referred to as backward error correction): This is an error control technique whereby an error detection scheme is combined with requests for retransmission of erroneous data. Every block of data received is checked using the error detection code used, and if the check fails, retransmission of the data is requested – this may be done repeatedly, until the data can be verified.

  • Forward error correction (FEC): The sender encodes the data using an error-correcting code (ECC) prior to transmission. The additional information (redundancy) added by the code is used by the receiver to recover the original data. In general, the reconstructed data is what is deemed the "most likely" original data.

  • ARQ and FEC may be combined, such that minor errors are corrected without retransmission, and major errors are corrected via a request for retransmission: this is called hybrid automatic repeat-request (HARQ).


Different techniques of coding:

  • Block code

  • Convolutional code


Block codes

  • k - length of each block before coding

  • n - length of each block after coding

  • such codes are denoted (n, k)

  • as before n > k

  • code rate:

R=k/n



So, after decoding there are different combinations: permissible (without errors) and prohibited (with errors).


Parity bits

Parity bit is equal to 0 if number of '1's in code combination is even and equals to 1 otherwise.


Hamming distance


This metrics is applied to strings. We need this to evaluate what is the minimum number of substitutions required to change one string to another, which in fact means that we are evaluating the minimum number of errors that could have transformed one string into the other.



References

  • Arndt C. Information Measures: Information and its Description in Science and Engineering.

  • Thomas Cover. Elements Of Information Theory.