数据链路层：组帧、差错控制与CRC/海明码。
3.1 数据链路层的功能
数据链路层工作于物理层之上，核心功能是在相邻节点间的单一通信链路上，以帧为基本单位实现数据的可靠传输与处理。
- 链路：网络中两节点间的物理通道（双绞线、光纤、微波等）。
- 数据链路：在物理链路基础上，通过硬件与软件实现数据传输协议构建的逻辑通道。
1. 为网络层提供服务
数据链路层向网络层提供以下三类服务：
| 服务类型 | 特点 | 适用场景 |
|---|---|---|
| 无确认的无连接服务 | 无需建立链路，直接发送，接收方不回确认，丢失帧由上层处理 | 实时通信、低误码率信道（如以太网） |
| 有确认的无连接服务 | 无需建立链路，但每帧需确认，超时重传 | 误码率较高的无线通信 |
| 有确认的面向连接服务 | 建立链路 → 传输帧 → 释放链路，每帧确认，可靠性最高 | 对可靠性和实时性要求严格的场景 |
注意：无确认的面向连接服务在实际中不存在。
2. 链路管理
- 数据链路层连接的建立、维持和释放过程（主要针对面向连接的服务）。
- 包括：确认对方就绪状态、交换初始化信息、维持连接、释放连接。
- 多站点共享信道时的资源分配与管理也属于链路管理范畴。
3. 帧定界、帧同步与透明传输
| 概念 | 定义 |
|---|---|
| 帧结构 | 在网络层数据报前后添加首部和尾部（含控制信息） |
| 帧定界 | 利用首部和尾部界定帧的边界 |
| 帧同步 | 接收方从比特流中精准识别帧的起始与结束位置 |
| 透明传输 | 数据链路层不干预数据内容，通过机制避免数据中特殊字符被误判为帧边界 |
| MTU | 最大传送单元，平衡传输效率与可靠性 |
4. 流量控制
- 目的：限制发送方的发送速率，使其不超过接收方的接收能力，避免数据丢失或缓冲区溢出。
不同层的流量控制：
| 层次 | 控制对象 |
|---|---|
| 数据链路层 | 相邻节点之间 |
| 网络层 | 整个网络 |
| 传输层 | 端到端 |
注意：OSI体系中流量控制主要在数据链路层；TCP/IP体系中主要在传输层。
5. 差错控制
- 目的：发送方确定接收方是否正确收到数据。
| 差错类型 | 描述 | 处理方式 |
|---|---|---|
| 位错 | 帧中某些位出现差错 | CRC检错 + ARQ重传 |
| 帧错 | 帧丢失、重复或失序 | 定时器 + 编号机制 |
3.2 组帧
四种组帧方法对比
| 方法 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 字符计数法 | 帧头部用计数字段标明帧内字符数 | 简单直接 | 计数字段出错会导致帧同步失效 |
| 字符填充的首尾定界符法 | 用SOH/EOT标识帧边界，数据中特殊字符前加转义字符ESC | 定界符明显，便于识别 | 需字符填充，增加复杂性 |
| 零比特填充的首尾标志法 | 用01111110标识边界，数据中每5个1后插入0 | 比特级操作，适合硬件实现 | 需填充/移除逻辑 |
| 违规编码法 | 使用正常编码中不出现的码组标识边界 | 无需填充，识别简单 | 仅适用于冗余编码环境 |
3.3 差错控制
差错控制策略
- ARQ（自动重传请求）：检测出错时通知发送端重发，直到正确接收。
- FEC（前向纠错）：检测出错时能定位并纠正错误。
3.3.1 检错编码
1. 奇偶校验码
- 在数据末尾添加一位校验位。
- 奇校验：数据中1的个数为奇数时校验位=0，偶数时=1。
- 偶校验：数据中1的个数为偶数时校验位=0，奇数时=1。
- 优点：实现简单，计算开销低。
- 缺点：只能检测奇数个比特错误，无法检测偶数个错误。
2. 循环冗余码（CRC）
- 将数据视为多项式，通过生成多项式进行模2除法，余数作为校验码（FCS）附加到数据后。
- 模2除法：加法不进位，减法不借位（异或操作）。
CRC编码步骤：
- 双方商定生成多项式$G(x)$，设$G(x)$有$r+1$位，最高位和最低位必须为1。
- 在帧尾部加上$r$个0。
- 用$G(x)$对扩展后的数据进行模2除法，得到余数$R(x)$（FCS）。
- 将校验码附加在原始数据之后传输。
- 接收端用$G(x)$整除收到的数据帧，余数为0则无差错，否则丢弃。
3.3.2 纠错编码
海明码
- 在数据中插入冗余校验位，使数据和校验位的组合能唯一标识错误位置。
关键概念：
- 海明距离：两个二进制字符串之间相应位不同的位数。
- 检错d位：编码集海明距离至少为$d+1$。
- 纠错d位：编码集海明距离至少为$2d+1$。
冗余校验位数量：
- 设数据位数为$n$，校验位数为$r$，需满足：$2^r \geq n + r + 1$
- 校验位插入位置：自右向左$2^i$（1,2,4,8…）位置。
习题
在数据链路层中，以下哪种服务适用于实时通信或误码率较低的通信信道？
A. 无确认的无连接服务在数据链路层中，透明传输的含义是：
C. 数据在传输过程中不被修改或解释在数据链路层中，流量控制的主要目的是：
C. 限制发送方的数据流量在数据链路层中，帧同步的主要作用是：
A. 确定帧的起始与终止在字符计数法中，如果帧长度字段出错，会导致什么问题？
D. 帧边界错误在字符填充的首尾定界符法中，如果数据中出现与定界符相同的字符，发送方会如何处理？
C. 在该字符前插入转义字符在违规编码法中，帧的定界符通常采用什么方式实现？
C. 使用物理层违规编码奇偶校验码可以检测出（A. 奇数）个错误。
已知两个二进制字符串为10110和11011，它们的海明距离是（B. 3）
若一个编码系统的海明距离为7，则它最多可以（C. 检错6位，纠错3位）
CRC计算题（谢希仁3-07）
- 数据：1101011011，$G(x)=x^4+x+1$（10011）
- 计算余数：
- 数据后加4个0：11010110110000
- 模2除10011，得余数1110
- 最后一个1变0（1101011010）→ 能被整除？能发现（余数不为0）
- 最后两个1变0（1101011000）→ 能发现
- CRC检验后是否变成可靠传输？否，CRC只能检测错误，不能纠错，且不能检测所有错误（如帧丢失、重复等）。
零比特填充题（谢希仁3-10）
- 原始比特串：0110111111111100
- 遇到5个1插入0：01101111101111100 → 01101111101111100
- 接收端数据：0001110111110111110110
- 删除5个1后的0：0001110111110111110110 → 00011101111111111110
- 原始比特串：0110111111111100
笔记结束