What is error control in Computer Network

Error Correction codes are used to detect and correct the errors when data is transmitted from the sender to the receiver.

Error Correction can be handled in two ways:

• Backward error correction: Once the error is discovered, the receiver requests the sender to retransmit the entire data unit.
• Forward error correction: In this case, the receiver uses the error-correcting code which automatically corrects the errors.

A single additional bit can detect the error, but cannot correct it.

For correcting the errors, one has to know the exact position of the error. For example, If we want to calculate a single-bit error, the error correction code will determine which one of seven bits is in error. To achieve this, we have to add some additional redundant bits.

Suppose r is the number of redundant bits and d is the total number of the data bits. The number of redundant bits r can be calculated by using the formula:

The value of r is calculated by using the above formula. For example, if the value of d is 4, then the possible smallest value that satisfies the above relation would be 3.

To determine the position of the bit which is in error, a technique developed by R.W Hamming is Hamming code which can be applied to any length of the data unit and uses the relationship between data units and redundant units.

Hamming Code

Parity bits: The bit which is appended to the original data of binary bits so that the total number of 1s is even or odd.

Even parity: To check for even parity, if the total number of 1s is even, then the value of the parity bit is 0. If the total number of 1s occurrences is odd, then the value of the parity bit is 1.

Odd Parity: To check for odd parity, if the total number of 1s is even, then the value of parity bit is 1. If the total number of 1s is odd, then the value of parity bit is 0.

Algorithm of Hamming code:

• An information of 'd' bits are added to the redundant bits 'r' to form d+r.
• The location of each of the (d+r) digits is assigned a decimal value.
• The 'r' bits are placed in the positions 1,2,.....2k-1.
• At the receiving end, the parity bits are recalculated. The decimal value of the parity bits determines the position of an error.

Relationship b/w Error position & binary number.

Let's understand the concept of Hamming code through an example:

Suppose the original data is 1010 which is to be sent.

Total number of data bits 'd' = 4 Number of redundant bits r : 2r >= d+r+1 2r>= 4+r+1 Therefore, the value of r is 3 that satisfies the above relation. Total number of bits = d+r = 4+3 = 7;

Determining the position of the redundant bits

The number of redundant bits is 3. The three bits are represented by r1, r2, r4. The position of the redundant bits is calculated with corresponds to the raised power of 2. Therefore, their corresponding positions are 1, 21, 22.

The position of r1 = 1 The position of r2 = 2 The position of r4 = 4

Representation of Data on the addition of parity bits:

Determining the Parity bits

Determining the r1 bit

The r1 bit is calculated by performing a parity check on the bit positions whose binary representation includes 1 in the first position.

We observe from the above figure that the bit positions that includes 1 in the first position are 1, 3, 5, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at these bit positions corresponding to r1 is even, therefore, the value of the r1 bit is 0.

Determining r2 bit

The r2 bit is calculated by performing a parity check on the bit positions whose binary representation includes 1 in the second position.

We observe from the above figure that the bit positions that includes 1 in the second position are 2, 3, 6, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at these bit positions corresponding to r2 is odd, therefore, the value of the r2 bit is 1.

Determining r4 bit

The r4 bit is calculated by performing a parity check on the bit positions whose binary representation includes 1 in the third position.

We observe from the above figure that the bit positions that includes 1 in the third position are 4, 5, 6, 7. Now, we perform the even-parity check at these bit positions. The total number of 1 at these bit positions corresponding to r4 is even, therefore, the value of the r4 bit is 0.

Data transferred is given below:

Suppose the 4th bit is changed from 0 to 1 at the receiving end, then parity bits are recalculated.

R1 bit

The bit positions of the r1 bit are 1,3,5,7

We observe from the above figure that the binary representation of r1 is 1100. Now, we perform the even-parity check, the total number of 1s appearing in the r1 bit is an even number. Therefore, the value of r1 is 0.

R2 bit

The bit positions of r2 bit are 2,3,6,7.

We observe from the above figure that the binary representation of r2 is 1001. Now, we perform the even-parity check, the total number of 1s appearing in the r2 bit is an even number. Therefore, the value of r2 is 0.

R4 bit

The bit positions of r4 bit are 4,5,6,7.

We observe from the above figure that the binary representation of r4 is 1011. Now, we perform the even-parity check, the total number of 1s appearing in the r4 bit is an odd number. Therefore, the value of r4 is 1.

• The binary representation of redundant bits, i.e., r4r2r1 is 100, and its corresponding decimal value is 4. Therefore, the error occurs in a 4th bit position. The bit value must be changed from 1 to 0 to correct the error.

Next Topic#

The purpose of error control is to ensure that the information received by the receiver is exactly the information transmitted by the sender. As the communication channel is highly unreliable, the receiver must be able to deal with the received data, if it contains error. The term error control is defined as the process of identification or correction of error occurred in the transmitted data. There are two types of error control mechanisms. They are:

Forward error control Additional redundant information is transmitted along with the useful data. Hence, the receiver not only detects the error, but also determines the location of the error in the data. This method is not widely used, because of the number of additional redundant information.

Feedback or (backward) error control Along with each character, little additional information is added only for error detection. The receiver performs no error correction. If the received data contains error, then the entire data is retransmitted. Hence, the feedback techniques perform error detection and retransmission.

Error detection There are different error detection schemes used. The type of detection scheme depends on the type of error and the type of transmission (synchronous or asynchronous) also. There are random single bit errors in asynchronous or synchronous mode of transmission and burst error occurs in a group of continuous bits. The most widely used error-detecting codes are the parity, block sum check, and the cyclic redundancy check (CRC) codes.

Parity The most common method of detecting the errors is the use of parity. With this method, the bits of a character to be transmitted are inspected and an extra bit is added before the transmission. This bit is known as the parity bit. The bit is chosen to be a ‘0’ or a ‘1’, in order to keep the total number of ‘1’ s ‘1’ bits in the character odd or even respectively. To compute the parity bit, the number of bits in the character is added first, using modulo-2 addition, the result may be a ‘0’ or a ‘1’. If the parity is chosen as odd, then the additional bit added must make the result into a ‘1’ if the parity chosen is even, then the additional bit must make the result into a ‘0’. Following is an example for the parity generation.  

Block error control When a burst of characters is transmitted, there may be possibilities for single bit or multiple bit error that leads to retransmission of the whole block of characters. Hence, it is necessary to use error-detecting techniques to find out the occurrence of error in the block. The parity method discussed earlier can be extended to a block of data also. A block of character is called as frame. The frame contains one additional column and one additional row. By generating the parity bit for each individual character, the column is created. The last row of the frame is formed by finding the parity bit for each bit position. A sample frame with row and column parity is shown below.

The main advantage of this scheme is the detection of two-bit error. As a simple parity bit can detect only single bit error. If two-bit changes occur in the transmitted data, the resultant parity bit is same as the parity of the transmitted character. In the above scheme, if a two-bit error occurs in a transmitted character, the received parity bit remains the same. But these two bit errors change the column parity at the receiver. Hence, the receiver can identify two-bit errors. But simultaneous occurrence of two-bit errors in two characters at the same column positions can be unnoticed by the receiver. Clearly, the probability of this occurring is much less than the probability of two-bit errors.

The simple parity and block sum check methods are well suited for applications in which random single bit errors are present. More precautionary measures; are to be taken to control continuous error burst. An error burst is defined as the number of bits between two successive error bits, including the two incorrect bits. The length of the error burst is determined from the number B, the difference between the last erroneous bit in a burst and the first erroneous bit of the next burst. In this case, B correct bits separate the two bursts. The following figure illustrates the error bursts that occur in the transmitted sequence of bits.

Cyclic Redundancy Check (CRC) CRC is the most widely used error – detecting method alternative to the simple parity check codes. Instead of adding the number of bits to obtain the desired parity, in CRC a sequence of ‘extra’ redundant bits are added at the end of data. These bits are known as CRC bits. The CRC bits are derived from the original data bits. The method of deriving the CRC bits at the sending side is given below:

Step 1: A sequence of bit stream is formed by appending n ‘0’ bits to the data at the end.

Step 2: A predetermined devisor of length n+ 1 bits is used to divide the sequence and the remainder is calculated. The remainder is known as CRC.

Step 3: The remainder replaces the extra bits added to the data at the beginning.

Step 4: The combined sequence of data plus CRC is transmitted by the sender.

At the receiving end the received data plus CRC is again divided by the same divisor as used at the sending side. If the remainder is zero then it is presumed that the data is error – free and the receiver accepts the data, on the other hand if the remainder is non-zero, the data is considered as corrupted and the received data is discarded. For example, consider the 6-bit data sequence “100110”. Let us choose a 3-bit divisor 110at the sending side. As per the step 1, two 0s are added to the data sequence and the new sequence is “10011000”. As per the second step, the new sequence is divided by 110 (Modulo-2 division is used), and produces a remainder of 10. This is the CRC. As stated in step 3, this CRC code is added to the data sequence to produce a sequence “10011010” and then transmitted.

At the receiver side, if the received sequence does not contain an error, the sequence “10011010” is again divided by the same divisor 110 and the remainder is 00. If an error is made in one or two bits (corrupted), then the remainder will not be a 00, hence, the receiver rejects the data.

Checksum Another method of error detection, often used in higher order layers is checksum.

Checksum is computed at the sending end using the following steps.

Step 1: The data sequence is divided into ‘K’ words of same size n (8 or 16 bits).

Step 2: All words are added using l’s complement addition and the sum is computed.

Step 3: The l’s complement of the sum, known as checksum is transmitted with the data.

At the receiver side, the following steps are carried out after receiving the data with checksum

Step 1: The data sequence is divided into ‘K+1’ words of same size ‘n’ (8 or 16 bits).

Step 2: All words are added using l’s complement addition and the sum is computed.

Step 3: The sum is complemented, if it is 0, the data is error – free and is accepted; otherwise the received data is discarded.

Error correcting codes Techniques covered so far deal with error detection only. When error detecting techniques are used, and the receiver receives the data with error, the receiver discards the data and asks for retransmission. On the other hand, error-correcting codes are used to identify the error bits in the received data and correct them. The main problem with error-correcting codes is that they require more redundancy bits than the error-detecting codes. This leads to wastage of transmission bandwidth.

Single-bit error correction The key issue in error-correction is to identify the position of invalid error bit, in order to correct it. For example, when 7-bit ASCII code is transmitted, the error-correcting code must identify the position of the bit that contains an error. Hence, at least three redundant bits are used to identify the possibility of error in the seven positions in an ASCII character. However, if an error occurs at the redundant bits themselves, to identify it, additional bits are required. Hence the total number of bits in the transmitted data contains m+k bits. M is the number of message bits and K is the number of redundant bits.

The calculation of the total number of redundant bits for single bit error correction is straightforward. One bit is used for ensuring that the received data is error-free. Other bits are used to indicate one out of M message and K redundant bits that may contain an error. Hence, the value of K must be chosen such that 2K <: M+K+ 1. For example to correct single bit error in 7-bit ASCII code, at least 4 redundant bits are needed. Hence, the transmitted data contains 11bits for each data units.

Hamming codes RW. Hamming illustrated the concept of hamming distance, which is useful in considering the properties of codes. Hamming distance is defined as the number of bit positions by which two states differ from each other. This parameter is very useful for error-detection and correction. Hamming introduced a code for single bit error correction by inserting multiple parity check bits at selected positions of data before transmission. The receiver recalculates the check – bits, compares it with the received check – bits, and determines the error bit. For 4~bitcode three check – bits are required for error-correction as shown in Figure.