Error detection and correction

To clean the transmission errors introduced by the Earth's atmosphere (left), Goddard scientists applied the Reed-Solomon (right) error correction, which is commonly used on CD and DVD. Typical errors include missing pixels (white) and false signals (black). The white strip indicates a brief period during which the transmission was paused.

In mathematics, computer science and information theory, error detection and correction is an important practice for the maintenance and integrity of data through different procedures and devices such as reliable storage media The Acme Commodity and Phrase Code used in telegrams is considered a precursor of this type of technology.

Introduction

Communication between several computers continually produces a movement of data, generally through channels not designed for this purpose (telephone line), and that introduce external noise that causes transmission errors.

Therefore, we must ensure that if such movement causes errors, they can be detected. The method of detecting and correcting errors is to include additional bits called redundancy in the transmitted data blocks.

Two basic strategies have been developed to handle errors:

• Include sufficient redundant information in each data block so that mistaken bits can be detected and corrected. Used error correction codes.

• Include only the redundant information needed in each data block to detect errors. In this case the number of redundancy bits is lower. Used error detection codes.

If we consider a data block made up of m data bits and r redundancy, the final length of the block will be n, where n = m + r.

Type of detector codes

Simple parity (horizontal parity)

It consists of adding an extra bit to the string that we want to send, and that will tell us if the number of ones (bits set to 1) is even or odd. If it is even, we will include this bit with value = 0, and if it is not, we will include it with value = 1.

Example of a simple parity bit generation:

We want to send the chain “1110100”:
1.o We count the amount of a that there are: 4 a2. Number of a It's pair so we add a bit with value = 0
3.o The chain sent is 11101000

The receiver now repeats the operation of counting the number of "ones" there are (minus the last bit) and if it matches, there has been no error.

Problems with this method:

There is a high probability that cases where there has been an error will get through, and that the error will not be detected, as it happens if two numbers are changed in the transmission instead of one.

An example of generator polynomial normally used in WAN networks is: g(x)=x16+x12+x5+1{displaystyle g(x)=x^{16}+x^{12}+x^{5}

The calculations carried out by the transmitting equipment to calculate its CRC (Cyclic Redundancy Check) are:

1. Add as many zeros on the right to the original message as the grade of the generator polynomial
2. Divide the message with the zeros included between the generator polynomial
3. The rest obtained from the division is added to the message with the zeros included
4. The result obtained is sent

These operations are usually built into the hardware so they can be computed more quickly, but in theory polynomials are used to make the calculations easier.

Example of obtaining CRC:

Data:
Message encoded in binary: 1101001
Polynomial generator:      x  4   + x + 1   {displaystyle x^{4}+x+1} Operations:

1.o Get the polynomial equivalent to the message:      x  6   +  x  5   +  x  3   + 1   {displaystyle x^{6}+x^{5}+x^{3}+1} 2. Multiply the message by      x  4     {displaystyle x^{4}}  (Add 4 zeros on the right):      x  10   +  x  9   +  x  7   +  x  4     {displaystyle x^{10}+x^{9}+x^{7}+x^{4} 3.o Split the message into binary by the generator polynomial and remove the rest:      x  2   + 1   {displaystyle x^{2}+1} 4.o Concatenate the message with the rest (in module 2 also):      x  10   +  x  9   +  x  7   +  x  4   +  x  2   + 1   {displaystyle x^{10}+x^{9}+x^{7}+x^{4}{2}+x^{2} 5.o Transmit the message

The receiving computer must check the CRC code to detect whether or not errors have occurred.

Example of receptor calculations:

1.o Through the corresponding protocol they agree to the generator polynomial
2. Divide the code received between the generator polynomial
3.o Check the rest of the operation

3.1 If the rest is zero, there have been no mistakes
3.2 Process the message

3.1 If the rest is different from zero, it means mistakes have occurred.
3.2 Send the message

3.2 Try to correct errors by correcting codes

In summary, this method requires a generator polynomial that, chosen correctly, can detect a large number of errors:

• Simple Errors: All
• Double Errors: All
• Errors in odd bit positions: all
• Raphae errors with a length less than the grade of the generator polynomial: all
• Other bursts: a high and close to 100%

Checksum

It is a simple but efficient method only with short strings of words, which is why it is often used in important frame headers or other important strings and in combination with other methods.

Functionality: it is to group the message to transmit in chains of a certain length L not very large, for example 16 bits. Considering each string as an integer numbered according to the numbering system 2L− − 1{displaystyle 2^{L}-1}. Then the value of all the words in which the message is divided is added, and the result is added to the message to transmit, but changed from sign.

With this, all the receiver has to do is add all the strings, and if the result is 0 there are no errors.

Example:

101001110101

1.o Agree the length of each chain: 3

2. Agree the numbering system:      2  3   − −  1 = 7   {displaystyle 2^{3}-1=7} 3.o Split the message: 101 001 110 101

4.o Associate each chain with an integer: 5 1 6 5

5.o Add all values and add the number changed sign: -17

6.o Send 5 1 6 5 -17 coded in binary

The receiver:

1.o Add all values; if the sum is 0, process the message; if not, there has been an error.

This method, being simpler, is optimal to be implemented in software since it can achieve computational speeds similar to the implementation in hardware

Check-Based Hamming Distance

binary hypercubus dimension four.

If we want to detect d bit errors in a word of n bits, we can add to each word of n bits d+1 predetermined bits at the end, so that there remains a word of n+d+1 bits with a minimum distance of Hamming of d+1. In this way, if one receives a word of n+d+1 bits that does not match any code word (with a Hamming distance x <= d+1 the word does not belong to the code) it correctly detects if it is a word wrong. Furthermore, d or less errors will never become a valid word because the Hamming distance between each valid word is at least d+1, and such errors lead only to invalid words being correctly detected. Given a set of m*n bits, we can detect x <= d bits errors correctly using the same method on all n-bit words. In fact, we can detect a maximum of m*d errors if all n-bit words are transmitted with a maximum of d errors.

Example

Words to send:

1. 000001
2. 000001
3. 000010

Encoded with minimum Hamming distance = 2

000001 0000

000001 0011

000010 1100

If the received words have a Hamming distance < 2 are wrong words.

List of error detection and correction methods

• Verified digit
• FEC (Forward Error Correction)
• Golay Binary Code
• Code Hamming
• Bit of parity
• Reed-Solomon