Computer_Communication_Networking_L07Data_Link_Error_control.pptx

Data Link error control for Computer Communication Networking. Different aproaches and practical Aproach

1. The Data Link Layer Error Control Dr. Ajay Singh Raghuvanshi Electronics & Communication Engineering, NIT, Raipur

2. Error Detection and Correction Two basic strategies to deal with errors : Include enough redundant information to enable the receiver to deduce what the transmitted data must have been. Error correcting codes. Include only enough redundancy to allow the receiver to deduce that an error has occurred (but not which error). Error detecting codes.

3. Error Detection & Correction Code Hamming codes (Block Code). Binary convolutional codes. Reed-Solomon codes. Low-Density Parity Check codes. Dr.Ajay Singh Raghuvanshi 3 2/28/2022

4. Error Detection & Correction Code For all m number of message bits 2 m possible data messages are legal, but due to the presence of r check bits, n = m + r all 2 n possible code words are used. Only small fraction of 2 m / 2 n =1/2 r are possible will be legal code words. The error-detecting and error-correcting codes of the block code depend on minimum Hamming distance d . To reliably detect x error, one would need a Hamming distance of d = x +1 code or . To correct x errors, one would need a Hamming distance of d = 2 x +1 code.

5. Hamming Code ( n, m ) Codeword: n bits b1 b2 b3 b4 …. Check bits: The bits that are powers of 2 (p1, p2, p4, p8, p16, …). The rest of bits (m3, m5, m6, m7, m9, …) are filled with m data bits. Example of the Hamming code with n = 7 total code length in bits and m = 4 number of message bits is given in the next slide.

6. The Hamming Code Consider a message having four data bits (D) which is to be transmitted as a 7-bit codeword by adding three error control bits. This would be called a (7,4) code. The three bits to be added are three EVEN Parity bits (P), where the parity of each is computed on different subsets of the message bits as shown below. 7 6 5 4 3 2 1 D D D P D P P 7-BIT CODEWORD D - D - D - P (EVEN PARITY) D D - - D P - (EVEN PARITY) D D D P - - - (EVEN PARITY)

7. Hamming Code Why Those Bits? - The three parity bits ( 1,2,4 ) are related to the data bits ( 3,5,6,7 ) as shown at right. In this diagram, each overlapping circle corresponds to one parity bit and defines the four bits contributing to that parity computation. For example, data bit 3 contributes to parity bits 1 and 2 . Each circle (parity bit) encompasses a total of four bits, and each circle must have EVEN parity. Given four data bits, the three parity bits can easily be chosen to ensure this condition. It can be observed that changing any one bit numbered 1..7 uniquely affects the three parity bits. Changing bit 7 affects all three parity bits, while an error in bit 6 affects only parity bits 2 and 4 , and an error in a parity bit affects only that bit. The location of any single bit error is determined directly upon checking the three parity circles.

8. Hamming Code

9. Hamming Code For example, the message 1101 would be sent as 7 6 5 4 3 2 1 1 1 1 1 7-BIT CODEWORD 1 - - 1 - (EVEN PARITY) 1 1 - - 1 1 - (EVEN PARITY) 1 1 - - - (EVEN PARITY) 110 1 10 message 1101 would be sent as

10. Hamming Code It may now be observed that if an error occurs in any of the seven bits, that error will affect different combinations of the three parity bits depending on the bit position. For example, suppose the above message 1100110 is sent and a single bit error occurs such that the code word 1110110 is received: transmitted message received message 1 1 0 0 1 1 0 ------------> 1 1 1 0 1 1 0 BIT: 7 6 5 4 3 2 1 BIT: 7 6 5 4 3 2 1 The above error (in bit 5) can be corrected by examining which of the three parity bits was affected by the bad bit:

11. 7 6 5 4 3 2 1 1 1 1 1 1 7-BIT CODEWORD 1 - 1 - 1 - (EVEN PARITY) NOT! 1 1 1 - - 1 1 - (EVEN PARITY) OK! 1 1 1 - - - (EVEN PARITY) NOT! 1 In fact, the bad parity bits labeled 101 point directly to the bad bit since 101 binary equals 5 . Examination of the 'parity circles' confirms that any single bit error could be corrected in this way. The value of the Hamming code can be summarized: Detection of 2 bit errors (assuming no correction is attempted); Correction of single bit errors; Cost of 3 bits added to a 4-bit message. The ability to correct single bit errors comes at a cost which is less than sending the entire message twice. ( Recall that simply sending a message twice accomplishes no error correction.) transmitted message received message 1 1 0 0 1 1 0 ------------> 1 1 1 0 1 1 0 BIT: 7 6 5 4 3 2 1 BIT: 7 6 5 4 3 2 1

12. Practically Error-Detecting Codes Cost of re-transmission over a network link is much smaller than computational complexity needed to implement error correction. Hence in practical data networks Error detection is employed with retransmission. Dr.Ajay Singh Raghuvanshi 12 2/28/2022

13. Error-Detecting Codes Linear, systematic block codes Parity. Checksums. Cyclic Redundancy Checks (CRCs). Interleaving Dr.Ajay Singh Raghuvanshi 13 2/28/2022

14. Dr.Ajay Singh Raghuvanshi 14 2/28/2022 Parity is the simplest form of error checking. It adds one bit to the pattern and then requires that the modulo-2 sum of all the bits of the pattern and the parity bit have a defined answer. The answer is 0 for even parity and 1 for odd parity Parity Vertical Redundancy Check (VRC) Append a single bit at the end of data block such that the number of ones is even  Even Parity (odd parity is similar) 0110011  0110011 0110001  0110001 1 VRC is also known as Parity Check Performance: Detects all odd-number errors in a data block

15. Dr.Ajay Singh Raghuvanshi 15 2/28/2022 Parity Check Algorithm

16. Dr.Ajay Singh Raghuvanshi 16 2/28/2022 Longitudinal Redundancy Check (LRC) Organize data into a table and create a parity for each column 11100111 11011101 00111001 10101001 11100111 11011101 00111001 10101001 10101010 11100111 11011101 00111001 10101001 10101010 Original Data LRC Longitudinal Redundancy Check

17. 17 2/28/2022 Two-dimension Parity Check Performance can be improved by using two-dimensional parity check, which organizes the block of bits in the form of a table. Parity check bits are calculated for each row, which is equivalent to a simple parity check bit. Parity check bits are also calculated for all columns then both are sent along with the data. At the receiving end these are compared with the parity bits calculated on the received data Interleaving of parity bits to detect a burst error.

18. Dr.Ajay Singh Raghuvanshi 18 2/28/2022 In checksum error detection scheme, the data is divided into k segments each of m bits. In the sender’s end the segments are added using 1’s complement arithmetic to get the sum. The sum is complemented to get the checksum. The checksum segment is sent along with the data segments Checksum Like LRC, but it uses one’s complement arithmetic Performance The checksum detects all errors involving an odd number of bits. It also detects most errors involving even number of bits

19. Dr.Ajay Singh Raghuvanshi 19 2/28/2022 At Sender End At Receiver End

20. Dr.Ajay Singh Raghuvanshi 20 2/28/2022 Cyclic Redundancy Checks (CRC) This Cyclic Redundancy Check is the most powerful and easy to implement technique. Unlike checksum scheme, which is based on addition, CRC is based on binary division. In CRC, a sequence of redundant bits, called cyclic redundancy check bits, are appended to the end of data unit so that the resulting data unit becomes exactly divisible by a second, pre-determined binary number. At the destination, the incoming data unit is divided by the same number. If at this step there is no remainder, the data unit is assumed to be correct and is therefore accepted

21. Dr.Ajay Singh Raghuvanshi 21 2/28/2022

22. Dr.Ajay Singh Raghuvanshi 22 2/28/2022

23. Generator Polynomial Dr.Ajay Singh Raghuvanshi 23 2/28/2022 Let us assume k message bits and n bits of redundancy Associate bits with coefficients of a polynomial 1 0 1 1 0 1 1 1x 6 +0x 5 +1x 4 +1x 3 +0x 2 +1x+1 P(x) = x 6 +x 4 +x 3 +x+1 xxxxxxxxxx yyyy k bits n bits Block of length k+n

24. Dr.Ajay Singh Raghuvanshi 24 2/28/2022 Sending Multiply M(x) by x n Divide x n M (x) by P(x) Ignore the quotient and keep the reminder C(x) Form and send F(x) = x n M (x)+C(x) Receiving Receive F’(x) Divide F’(x) by P(x) Accept if remainder is 0, reject otherwise Theory of CRC

25. Dr.Ajay Singh Raghuvanshi 25 2/28/2022 Remainder 0 Remainder 0 Note: Binary modular addition is equivalent to binary modular subtraction  C(x)+C(x)=0 Proof of CRC Generation

26. Dr.Ajay Singh Raghuvanshi 26 2/28/2022 CRC 12 = x 12 +x 11 +x 3 +x 2 +x+1 CRC 16 = X 16 + X 15 + X 2 + 1 CRC CCITT = X 16 + X 12 + X 5 + 1 CRC 32 = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 7 + X 5 + X 4 + X 2 + 1 Some Standard CRC Generator Polynomials

27. Dr.Ajay Singh Raghuvanshi 27 2/28/2022 Performance CRC is a very effective error detection technique. If the divisor is chosen according to the previously mentioned rules, its performance can be summarized as follows: CRC can detect all single-bit errors CRC can detect all double-bit errors (three 1’s) CRC can detect any odd number of errors (X+1) CRC can detect all burst errors of less than the degree of the polynomial. CRC detects most of the larger burst errors with a high probability. For example, CRC-12 detects 99.97% of errors with a length 12 or more.