Data Link Layer

Use a field in the header to specify the number of the characters in the frame.

• 
  易出错

• Each frame starts and ends with special bytes.
• If the flag byte’s bit pattern occurs in that data, a special escape byte (ESC) will be inserted just before the bit pattern.
  

• Each frame begins and ends with a special bit pattern, 01111110.
• If the sender encounters five consecutive 1s in the data, a 0 bit will be inserted just after 1s.
• 

Append a parity bit to the end of a block of data (e.g., there are d bits in a block).
分为偶数校验和奇数校验

• Even parity scheme: the sender includes one additional bit and chooses its value such that the total number of 1s in the d+1 bits (the original information plus a parity bit) is even.
• Odd parity scheme: the parity bit value is chosen such that there is an odd number of 1s.
  

Two-dimensional parity is a generalization of single-bit ParityCheck.png

• In this scheme, the data is formed as a rectangular matrix j bits wide and i bits high.
• A parity value is computed for each row and column. It has following properties:
  • A single bit error can be detected.
  • If there is a single error, we can use the column and row indices to identify the bit that was corrupted and correct that error.

CRC treats bit streams as representations of polynomials with coefficients of 0 and 1 only.

• Modulo-2 arithmetic is used for computing CRC.
• In modulo-2, there are no carriers for addition or borrows for subtraction.
• When the polynomial code method is employed, the sender and receiver must agree upon a generator polynomial, G(x) in advance.

To compute the checksum for some frame with m bits, corresponding to the polynomial , we have following steps:

1. Let be the degree of .
2. Append zero bits to the low-order end of the frame so it now contains bits and corresponds to the polynomial
3. Divide into using modulo-2 division.
4. Subtract the remainder from using modulo-2 subtraction.
5. Append the remainder to the end of to form the transmitted data frame.

To detect the error, the receiver divides the checksummed frame by . If there is a remainder, there has been a transmission error.

Design to correct single bit errors.
Consists of two kinds of bits: check-bit and data-bit.
The check-bits are in the positions which are power of 2 (i.e., 1, 2, 4, 8, etc);
The data-bits are in the rest position (3, 5, 6, 7, 9, etc)
Each check bit forces the parity of some collection of bits, including itself, to be even (or odd). 每个检验位对一组特定 位数进行包括其本身 进行奇偶检验