Describe how the mechanism of error correction and detection is handled by the Data link layer in detail.

Answer:-

The optical fiber in telecommunications networks, have tiny error rates so that transmission errors are a rare occurrence. But other channels, especially wireless links and aging local loops, have error rates that are orders of magnitude larger. For these links, transmission errors are the norm.

One strategy is to include enough redundant information to enable the receiver to deduce what the transmitted data must have been. The other is to include only enough redundancy to allow the receiver to deduce that an error has occurred (but not which error) and have it request a retransmission. The former strategy uses error-correcting codes and the latter uses error-detecting codes. The use of error-correcting codes is often referred to as FEC (Forward Error Correction)

it is cheaper to use an error-detecting code and just retransmit the occasional block found to be faulty, FEC is used on noisy channels because retransmissions are just as likely to be in error as the first transmission.

Error-Correcting Codes

We will examine four different error-correcting codes:

Hamming codes.

Binary convolutional codes.
Reed-Solomon codes.
Low-Density Parity Check codes.

All of these codes add redundancy to the information that is sent. A frame con- sists of m data (i.e., message) bits and r redundant (i.e. check) bits. In a block code, the r check bits are computed solely as a function of the m data bits with which they are associated, as though the m bits were looked up in a large table to find their corresponding r check bits.

In a systematic code, the m data bits are sent directly, along with the check bits, rather than being encoded themselves before they are sent. In a linear code, the r check bits are computed as a linear function of the m data bits.

Exclusive OR (XOR) or modulo 2 addition is a popu- lar choice. This means that encoding can be done with operations such as matrix multiplications or simple logic circuits.

Let the total length of a block be n (i.e., n m r). We will describe this as an (n,m ) code. An n-bit unit containing data and check bits is referred to as an n- bit code word

The code rate, or simply rate, is the fraction of the codeword that carries information that is not redundant, or m/n. The rates used in practice vary widely.

To understand how errors can be handled, it is necessary to first look closely at what an error really is.

Given any two codewords that may be transmitted or received—say, 10001001 and 10110001—it is possible to determine how many corresponding bits differ. In this case, 3 bits differ. To determine how many bits differ, just XOR the two codewords and count the number of 1 bits in the result.

For example:
10001001
10110001
00111000

The number of bit positions in which two codewords differ is called Hamming distance (Hamming, 1950). Its significance is that if two codewords are a Hamming distance d apart, it will require d single-bit errors to convert one into the other.

In Hamming codes the bits of the codeword are numbered consecutively, starting with bit 1 at the left end, bit 2 to its immediate right, and so on. The bits that are powers of 2 (1, 2, 4, 8, 16, etc.) are check bits. The rest (3, 5, 6, 7, 9, etc.) are filled up with the m data bits. This pattern is shown for an (11,7) Hamming code with 7 data bits and 4 check bits in Fig. 3-6.