Data Link Layer Error Detection Techniques

Data Link Layer Error Control-Error Detection Techniques Error Detection Techniques Parity Checker CRC (Cyclic Redundency Check) Checksum Parity Checker Parity Checker:- In this approach, an extra bit is added to the data before transmission Types of parity checker:- Even Parity-...

Data Link Layer Error Control-Error Detection Techniques Error Detection Techniques Parity Checker CRC (Cyclic Redundency Check) Checksum Parity Checker Parity Checker:- In this approach, an extra bit is added to the data before transmission Types of parity checker:- Even Parity- Number of 1’s in the given word should be even Odd Parity- Number of 1’s in the given word should be odd Limitations of parity checker Not suitable for detection of burst error Unable to detect the location of erroneous bit and correct the same. Parity Checker Parity Checker  Two- dimensional parity-checker A better approach is the two-dimensional parity check. In this method, the dataword is organized in a table (rows and columns). It can detect up to three bit error  Two- dimensional parity-checker A better approach is the two-dimensional parity check. In this method, the dataword is organized in a table (rows and columns). It can detect up to three bit error Two-dimensional parity-check code Two-dimensional parity-check code Two-dimensional parity-check code Two-dimensional parity-check code Error affecting 4 bit may not be detected Cyclic Redundancy Check Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a codeword is cyclically shifted (rotated), the result is another codeword. It is based on the concept of binary division  Cyclic Redundancy Check The divisor in a cyclic code is normally called the generator polynomial or simply the generator.  Division in CRC encoder Message= 1001 Sender appends number of zeros in message equals to degree of generator polynomial Divide the appended message with generated polynomial using modulo 2 arithmetic Remainder becomes CRC Remove the appended zeros from message and append the calculated CRC Send the code word to receiver  Division in the CRC decoder for two cases At receiver Side Receiver takes the code word It divides the codeword with same generator polynomial using modulo 2 arithmetic If remainder contains all zero bits, message is accepted otherwise it is discarded CRC division using polynomials  Cyclic Redundancy Check If the generator has more than one term and the coefficient of x0 is 1, all single errors can be caught. If a generator cannot divide xt + 1 (t between 2 and n – 1), then all isolated double errors can be detected. The variable 𝑛n represents the length of the data/message (in bits) that is being transmitted and checked for errors using CRC. A generator that contains a factor of x + 1 can detect all CHECKSUM In this method, each data word is added to the previous data word and total sum (checksum) is calculated. Data along with checksum is then transmitted. This method detects all odd bit error; Even bit error may or may not be detected Idea of Checksum Suppose data is a list of five 4-bit numbers (7, 11, 12, 0, 6), Sender will send (7, 11, 12, 0, 6, 36), where 36 is the sum of the original numbers. The receiver adds the five numbers and compares the result with the sum. If the two are the same, the receiver assumes no error, accepts the five numbers and discards the sum If the two are not same, the receiver assumes there is an error somewhere and the data are not accepted. To make the job of the receiver easier if we send the negative (complement) of the sum, called the checksum. In this case, we send (7, 11, 12, 0, 6, −36). The receiver can add all the numbers received (including the checksum). Exampl e: Checksu m  Internet Checksum Sender Receiver 1. The message is divided into 16- 1. The message (including bit words. checksum) is divided into 16-bit 2. The value of the checksum word words. is set to 0. 2. All words are added using one’s 3. All words including the checksum complement addition. are added using one’s complement 3. The sum is complemented and addition. becomes the new checksum. 4. The sum is complemented and 4. If the value of checksum is 0, the becomes the checksum. message is accepted; otherwise, it