201ห้องสมุดไป่ตู้年3月4日 4
2.3 CRC 校验
CRC 是一类重要的线性分组码，编码和解码方法简 单，检错和纠错能力强。 它是目前应用最广泛的检错编码方法之一，广泛应 用于通信和测控领域。 原理
在发送端用生成多项式 G (x) 去除发送数据多项式 f (x) ， 求得一个余数多项式。将余数多项式附在数据多项式之后 发送到接收端 在接收端用同样的生成多项式 G (x) 去除接收数据多项式 f (x) ，得到计算余数多项式 通过计算余数多项式与接收余数多项式是否相同来判断是 否在传输过程中出现差错
2013年3月4日 7
4
1
2.3.3 CRC-4 生成校验码算法
设 12 位待发比特序列 100100011100 ， CRC-4 多项式系 数为 10011 ，求校验码。 由 CRC-4 知，其校验码 r 为 4 位，在待发序列后补充 4 位 0 ，得初始码为 1001000111000000 用初始码除以生成多项式系数，得到余数多项式系数
100010000100 ————————— 10011 ⌡ 1001000111000000 10011 ———————— 100111000000 10011 —————— 1000000 10011 ———— 1100
余数多项式系数为 1100 ，故发送 1001000111001100 CRC 编码过程实际上是循环移位的模 2 运算
XOR
xor ←0+0 ←0+1 ←0+0 ←0+1 ←0+0 ←0+0 ←0+0 ←0+0 ←1+0 ←0+1 ←1+0 ←0+1
R0
R0 0 1 0 1 0 0 0 0 0 1 0 1 0 0
XOR 输入
xor ←0+1 ←0+0 ←0+1 ←0+0 ←0+0 ←0+0 ←0+0 ←0+0 ←1+0 ←0+0 ←1+0 ←0+0 输入 清零 1 0 1 0 0 0 0 0 0 0 0 0 0
开始 Register8=0, Input 后填 8 位 0
数据处理完？
Y
N N
Register8 <<=1 Register8 首位 ==1 ？ 结束
Y
Register8 <<=1
N
Input 1 位新数据 ==1 ？
Y
Register8 最低位 = 1
Input 1 位新数据 ==1 ？
N
Y
Register8 最低位 = 1 Register8 ^=0x7 2013年3月4日 13
2013年3月4日
6
2.3.2 标准 CRC 生成多项式
CRC-32
G ( x )= x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x 1 + 1
CRC-ITU
G ( x )= x + x + x + 1
2013年3月4日
11
2.3.4.2 CRC-8 算法分析
R7 的移出位为 1 时，寄存器组才和 00000111 做 XOR 运算 移出位为 0 时，实际不需要运算 每次寄存器左移后，需要读入 1 位新数据到 R0 中 然后判断是否需要做 XOR 运算
2013年3月4日
12
2.3.4.3 CRC-8 处理流程
单播地址：目的地址第一位为 0 ，只被该地址节点接收 多播地址：目的地址第一位为 1 ，被一组节点接收 广播地址：目的地址为全 1 ，被所有节点接收
类型字段： 16 位 (2B), 表示网络层协议类型 0x0800 ，表示网络层为 IP 协议 0x8137 ，表示网络层为 NetWare 的 IXP 协议
2013年3月4日 14
2.4 Ethernet 帧接收流程
开始 启动接收 N
接收完成？ Y 帧太短？ N 地址正确？ N Y
Y 帧拆解 接收成功
Y 校验正确？ N 8 位的整数倍？ Y 帧校验错 N
帧比特错
2013年3月4日 15
2.5 Ethernet 帧发送流程
开始 封装帧 Y 总线忙？ N 启动发送 继续发送 N 发送完成？ Y 发送成功 冲突次数 >16? Y 发送失败
前导码 帧前定界符 目的地址 源地址 类型字段 7B 1B 6B 6B 2B 数据字段 46~1500B 校验字段 4B
前导码： 56 位 (7B), 1010....10 帧前定界符： 8 位 (1B), 10101011 目的 / 源地址： 48 位 (6B), 是物理地址，又称 MAC 地址，如 00-13-d3-a2-42-a8
2013年3月4日
2
2.1 Ethernet
目前使用最广泛的局域网 基于 802.3 协议 通过 MAC 地址 ( 物理地址 ) 实现主机间通信 MAC (Media Access Control) 地址： 6Bytes (48bits)
2013年3月4日
3
2.2 Ethernet 2.0 帧结构
2013年3月4日 10
2.3.4.1 以比特序列 1010 为例
R7 R6 R5 R4 R3 R2
移出位 ← 0 0 0 0 0 0 0 0 1 0 1 0 结果 R7 0 0 0 0 0 0 0 0 1 0 1 0 0 0 R6 0 0 0 0 0 0 0 1 0 1 0 0 0 0 R5 0 0 0 0 0 0 1 0 1 0 0 0 1 1 R4 0 0 0 0 0 1 0 1 0 0 0 1 1 1
2013年3月4日 8
2.3.3 续
接收端校验过程 设发送端发出数据为 1001000111001100 而接收端收到数据为 1001000111101100 除以 CRC-4 多项式，判断余数是否为 0 。
100010000110 ————————— 10011 ⌡ 1001000111101100 10011 ———————— 100111101100 10011 —————— 1101100 10011 ———— 100000 10011 ———— 110
16 12 5
CRC-16
G ( x )= x + x + x + 1
16 15 2
CRC-12
G ( x )= x + x + x + x + x + 1
12 11 3 2 1
CRC-8
G ( x )= x + x + x + 1
8 2 1
CRC-4
G ( x )= x + x + 1
2.3.5 CRC-32 查找表法
串行方法算法简单，易于实现，对任意长 度的生成多项式都适用，但是它一次只能 处理一位数据，效率太低。为了提高处理 效率，可以一次处理 4 位、 8 位、 16 位 或 32 位 查找表法分两步实现： 计算参数表，计算校验码时只要从表中 查找对应的值进行处理即可 计算 CRC 校验码
2013年3月4日 5
2.3.1 CRC 校验算法
帧校验字段：采用 32 位 CRC 校验 校验范围包括目的 / 源地址字段，类型字段和数据字段； 接收端若发现错误，则帧被丢失。 CRC 校验算法： 基于线性编码理论，在 k 位待发数据之后加 r 位校验码，根 据 r 位校验码判断前面 k 位数据中是否有错。 算法： 将待发送的二进制序列作为多项式 f(x) 的系数，除以预先 设定的生成多项式 G(x) ，求得余数多项式 r(x) 并将 r(x) 的 系数作为 r 位校验码发送 接收端将收到的二进制序列作为多项式 f’(x) 的系数，除 以生成多项式 G(x) ，如果余数为 0 ，则传输无差错。
2013年3月4日 16
N
发生冲突？
Y 冲突加强
等待后退延迟时间
计算后退延迟时间 冲突次数加 1 N
2013年3月4日
9
2.3.4 CRC-8 的实现
CRC-8 可由 8 个移位寄存器和 3 个加法器（异或单元） 实现。 8 2 1
G CRC −8 ( x )= x + x + x + 1
XOR R1
R7 R6 R5 R4 R3 R2
XOR
R0
XOR 输入
编码或解码前将所有寄存器清零
输入位作为最右边异或操作的输入之一， 8 个寄存器同时 进行左移一位操作 每次移位时，寄存器同时是上图异或操作的输入之一 每输入 1 位便做一次移位操作，直到待发送的数据全部输 入完毕，此时寄存器组中值便是 CRC-8 的校验码。
XOR
R3 0 0 0 0 1 0 1 0 0 0 1 1 0 0 R2 0 0 0 1 0 1 0 0 0 1 1 0 1 1
R1
xor ←0+0 ←0+0 ←0+1 ←0+0 ←0+1 ←0+0 ←0+0 ←0+0 ←1+0 ←0+1 ←1+1 ←0+1 R1 0 0 1 0 1 0 0 0 0 1 1 1 1 1
网络高级编程技术
主讲：张江山
zhangjs@
2 Ethernet 帧结构解析
帧是网络中基本传输单元，熟悉帧结构对 于理解网络协议的概念、协议执行过程以 及网络层次结构具有重要的意义。 学习目标：