【计算机网络笔记】数据链路层——差错编码

系列文章目录

什么是计算机网络？
什么是网络协议？
计算机网络的结构
数据交换之电路交换
数据交换之报文交换和分组交换
分组交换 vs 电路交换
计算机网络性能（1）——速率、带宽、延迟
计算机网络性能（2）——时延带宽积、丢包率、吞吐量/率
计算机网络体系结构概念
OSI参考模型基本概念
OSI参考模型中非端-端层（物理层、数据链路层、网络层）功能介绍
OSI参考模型中端-端层（传输层、会话层、表示层、应用层）功能介绍
TCP/IP参考模型基本概念，包括五层参考模型
网络应用的体系结构
网络应用进程通信
网络应用对传输服务的需求
Web应用之HTTP协议（涉及HTTP连接类型和HTTP消息格式）
Cookie技术
Web缓存/代理服务器技术
传输层服务概述、传输层 vs. 网络层
传输层——多路复用和多路分用
传输层——UDP简介
传输层——可靠数据传输原理之Rdt协议
传输层——可靠数据传输之流水线机制与滑动窗口协议
传输层——TCP特点与段结构
传输层——TCP的可靠数据传输
TCP连接管理（图解三次握手和四次挥手）
传输层——拥塞控制原理与解决方法
TCP的拥塞控制机制
网络层服务与核心功能
网络层服务模型——虚电路网络
网络层服务模型——数据报网络
Internet网络的网络层——IP协议之IP数据报的结构
IP分片
IP编址与有类IP地址
IP子网划分与子网掩码
CIDR与路由聚合
DHCP协议
网络地址转换(NAT)
ICMP（互联网控制报文协议）
IPv6简介
路由算法之链路状态路由算法
路由算法之距离向量路由算法
路由算法之层次路由
数据链路层概述

---

---

差错编码

差错编码是差错检测和纠正的基础。它的基本原理是在数据基础上增加冗余信息，这个冗余信息建立起了数据比特之间原本不存在的关联关系。接收端收到数据之后判断关联关系是否存在。这种流程其实只是一类差错编码。当然，差错编码不能保证100%可靠。

• D→DR，其中R为差错检测与纠正比特（冗余比特）

差错编码可分为检错码与纠错码。

• 对于检错码，如果编码集的汉明距离ds =r+1，则该差错编 码可以检测r位的差错。汉明距离就是两个码字的比特数不一样的个数。编码集的汉明距离就是这个编码集中任意两个码字的汉明距离的最小值。

  • 例如，编码集 {0000,0101,1010,1111} 的汉明距离ds=2，可以 100%检测1比特差错

• 对于纠错码，如果编码集的汉明距离ds=2r+1，则该差错 编码可以纠正r位的差错

  • 例如，编码集 {000000,010101,101010,111111} 的汉明距离ds=3 ，可以纠正1比特差错，如100010纠正为101010

下面介绍几个常见的差错编码：

奇偶校验码

• 1比特校验位: 检测奇数位差错。所以检错能力是50%。

• 二维奇偶校验：将数据组织成二维矩阵形式，在每一行和每一列都增加一个校验位。如果行和列都满足偶校验就是二维偶校验，如果都满足奇校验就是二维奇校验。能够检测奇数位差错、部分偶数位差错，也能够纠正同一行/列的奇数位错

Internet校验和(Checksum)

发送端:

• 将“数据”(校验内容) 划分为16位的二进制 “整数”序列
• 求和(sum)：补码求和 (最高位进位的“1”， 返回最低位继续加）
• 校验和(Checksum)： sum的反码
• 放入分组(UDP、TCP 、IP)的校验和字段

接收端:

• 与发送端相同算法计算
• 计算得到的"checksum"：
  • 为16位全0（或sum为16位 全1）：无错
  • 否则：有错

循环冗余校验码(CRC)

• 检错能力更强大

• 将数据比特D，视为一个二进制数

• 选择一个r+1位的比特模式 (生成比特模式)，G

• 目标：选择r位的CRC比特，R，满足

  • <D,R>刚好可以被G整除(模2)
  • 接收端检错：利用G除<D,R>，余式全0，无错；否则，有错
  • 可以检测所有突发长度小于r+1位差错

• 广泛应用于实际网络 (以太网，802.11 WiFi，ATM)

这样的过程可以概括为下面的式子：