Data Link Layer


[!info]+ The data link layer combines the following 3 functions to achieve the delivery of data from one node to another.

  1. Framing
  2. Flow control
  3. Error control


The data link layer needs to pack bits into frames, so that each frame is distinguishable from another. Framing

Character Count

[!abstract]+ Character Count Use a field in the header to specify the number of the characters in the frame.

  • CharacterCount 易出错

Flag bytes with byte stuffing

[!abstract]+ Flag bytes with byte stuffing

  • 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. Framing-FBBS

Starting and ending flags with bit stuffing

[!abstract ]+ Starting and ending flags with bit stuffing

  • 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.
  • Framing-FBBS

Error Control

[!todo]+ Finally Goal Check Each data frame is correct?

  • Sender send data{k bits} and check bit{n-k}
  • Receiver receive data and Check bit
    • According data calculate check bit compare 2 check bit

Error Control Overview

ErrorControl-sender ErrorControl-Receiver

Parity Check 奇偶校验

[!abstract]+ Parity Check 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. Parity Check

Two-dimensional Parity Check

[!info]+ Two-dimensional Parity Check 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.

[!example]- 2D Parity Check 让我们通过一个具体的例子来说明二维奇偶校验(2D Parity Check)是如何工作的。假设我们有一个由二进制数据组成的3x3矩阵,我们想要通过添加行校验位和列校验位,以及一个额外的校验位来确保数据的完整性。



1 0 1
0 1 0
1 1 0




  • 第一行:1 0 1 有两个1,已经是偶数,所以校验位是0
  • 第二行:0 1 0 有一个1,不是偶数,所以校验位是1
  • 第三行:1 1 0 有两个1,已经是偶数,所以校验位是0


1 0 1 | 0
0 1 0 | 1
1 1 0 | 0



  • 第一列:1 0 1 有两个1,校验位是0
  • 第二列:0 1 1 有两个1,校验位是0
  • 第三列:1 0 0 有一个1,校验位是1
  • 行校验列:0 1 0 有一个1,校验位是1


1 0 1 | 0
0 1 0 | 1
1 1 0 | 0
0 0 1 | 1



1 0 1 | 0
0 1 0 | 1
1 1 0 | 0
0 0 1 | 1


Cyclic Redundancy Check (CRC)

[!info]+ Cyclic Redundancy Check (CRC) 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.

[!abstract]+ CRC Process To compute the checksum for some frame with m bits, corresponding to the polynomial $M(x)$ , we have following steps:

  1. Let $r$ be the degree of $G(x)$.
  2. Append zero bits to the low-order end of the frame so it now contains bits and corresponds to the polynomial $x^{r}M(x)$
  3. Divide $G(x)$ into $x^rM(x)$ using modulo-2 division.
  4. Subtract the remainder from $x^rM(x)$ using modulo-2 subtraction.
  5. Append the remainder to the end of $M(x)$ 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.

[!example]- CRC Example CRC

Error Correction

  • The use of error-correcting codes is often referred to as forward error correction (FEC).
  • Basic concepts
    • Each block of data is mapped into an n-bit block, which consists of m data bits and r redundant. This n-bit block is referred to as an n-bit codeword.
    • Hamming distance is defined as the number of bit positions in which two code-words differ. For example (Hamming distance = 3):

      [!abstract]+ Hamming Distance

      1 0 0 0 1 1 0 1
      0 1 0 0 1 1 0 0
      1 1 0 0 0 0 0 1

When transmission, each m-bits sequence is mapped into n-bit codeword. For example, $01$ is mapped to $00111$ in the codeword table.

Data block Codeword
00 00000
01 00111
10 11001
11 11110

When the receiver receives an invalid codeword (detects an error), then the valid codeword that is closest to it (minimum hamming distance) is selected.

Hamming Code

[!info]+ Hamming code—二进制的妙用 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). 每个检验位对一组特定 位数进行包括其本身 进行奇偶检验

Determine the number of check bits

The number of check bits can be obtained by:

\[2^{c} \geq d + c + 1\]

c is the number of check bit *d is the number of data bit *

Hamming Code Computation Example

Position $\underline1$ $\underline2$ 3 $\underline4$ 5 6 7 $\underline8$ 9 10 11
Value $\underline0$ $\underline0$ 1 $\underline1$ 0 0 1 $\underline0$ 0 0 0

Flow Control