Link layer Error Detection Code (EDC)

Link layer is the second layer in the five layer model of network. Link layer packet is called 'frame', and the purpose of link layer is to put datagram (from network layer) into a frame.

 

Frame = [headers, EDC(error detection code), datagram, trailers]

 

Out of services that link layer provides, error detection and correction are two things that we will focus our discussion on. Error detection and correction are implemented by putting some extra bits, called EDC, into the frame alongside the datagram. EDC is mechanism dependent, and we will look at Parity checking mechanism and Cyclic Redundancy check as two methods that can generate EDC.

 

Parity checking mechanism (EDC)

As said, we decide on error detection method, then calculate EDC to be appended to the datagram (to form a frame. Below, we discuss 3 methods that can be used to generate EDC, and how error can be detected and perhaps be corrected.

Single bit parity (single bit error can be detected, not corrected)

Single bit parity is where we have one-bit EDC. We generate it by looking at datagram, and counting number of 1's.

1. count number of 1's in the datagram byte representation

2. if the number of 1's is odd, we append '1' as a parity bit (EDC)

3. otherwise, we append '0' as a parity bit (EDC)

 

We say that error occurred if there was a corruption of one bit ('single bit parity').

Note: this is under even parity error detection scheme, and we have not discussed other schemes in the lecture.

Two dimentional bit parity (single bit error can be detected AND corrected)

We have multiple parity bits EDC in this case. We arrange datagram byte representation into 2D array, and calculate parity bits (as above) row by row, and column by column. Also, we calculate parity bit of parity bits.

We detect single bit error if we find incorrect parity bit. Note here that we can also correct single bit error, since single bit error will cause one incorrect row parity and one incorrect column parity, which will pinpoint location of the single bit that caused the error.

 

CRC (cyclic redundancy check), (powerful error detection than above, no error correction)

This one provides powerful error detection coding.

Method: 

- decide on (n+1)-bit byte string (G) that will be shared between sender and receiver

- append n zeros to the datagram bytestring representation (blue 0's in the diagram)

- do XOR operation (in a similar fashion to division) until you get n-bit remainder, which will be EDC to be appended (we call it CRC in this case).

 

Diagram below shows calculation of CRC when G = 100000111, n = 8.

 

- We send [Datagram bytestring, CRC] to the reciever

- The receiver does the same operation as the sender, except that: instead of 0's appended, we have CRC appended; instead of dividing until we get n-bit CRC, we divide until we get n-bit 0 (indicates no error, otherwise there is an error)