3.3 相关知识
- 帧
术语“帧”来源于串行线路上的通信。其中，发送者在发送数据的前后分别添加特殊的字符，使它们成为一个帧。Ethernet从某种程度上可以被看做是机器之间的数据链路层连接。
首先我们来认识一下Ethernet帧结构，Ethernet V2.0规范和IEEE 802.3标准中的Ethernet帧结构有一些差别，这里我们按802.3标准的帧结构进行讨论。图3-1给出了Ethernet帧结构图。
如上图所示，802.3标准的Ethernet帧结构由7部分组成。
(1) 前导码与帧前定界符字段
前导码由56位（7 B）的10101010…101010位序列组成。帧前定界符可以视为前导码的延续。1 B的帧前定界符结构为10101011。
如果将前导码与帧前定界符一起看，那么在62位101010…1010位序列之后出现11。在11之后是Ethernet帧的目的地址字段。前导码与帧前定界符主要是保证接收同步，这8 B接收后不需要保留，也不记入帧头长度中。
(2) 目的地址和源地址
目的地址（DA）与源地址（SA）分别表示帧的接收结点地址与发送结点的硬件地址。
- 在Ethernet帧中，目的地址和源地址字段长度可以是2 B或6 B。目前的Ethernet都使用6 B（即48位）长度的地址。
- Ethernet帧的目的地址可以是单播地址（unicast address）、多播地址（multicast address）与广播地址（broadcast address），目的地址的第一位为0表示单播地址，为1表示多播地址，目的地址为全1则表示广播地址。
(3) 长度字段
Ethernet帧用2 B定义数据字段包含的字节数。协议规定，帧数据的最小长度为46 B，最大长度为1500 B。设置最小帧长度的目的是使每个接收结点能够有足够的时间检测到冲突。
(4) 数据字段
帧数据字段的最小长度为46 B。如果帧的LLC数据少于46 B，则应将数据字段填充至46 B。填充字符是任意的，不计入长度字段值中。
(5) 校验字段
帧校验字段（FCS）采用32位的CRC校验。校验的范围包括目的地址字段、源地址字段、长度字段、LLC数据字段。
此处，为了简便起见，采用8位的CRC校验。CRC校验的生成多项式为:
G(X) = X 8 + X 2 + X1 + 1
某些帧结构中还会包括帧类型字段，用来识别此帧所承载的数据的类型。当一个帧到达指定的计算机时，操作系统根据帧类型决定用哪个协议软件模块对它进行处理。自识别帧的主要优点是，可以在同一物理网络中使用多个协议而互不干扰。
- CRC校验
在前一章中我们已经介绍了差错控制在通信中的重要意义，以及简单的差错校验码计算过程。在这里我们进一步介绍循环冗余编码（Cyclic Redundancy Code, CRC）的编码方式。它是一种重要的线性分组码、编码和解码方法，具有简单、检错和纠错能力强等特点，在通信领域广泛地用于实现差错控制。实际上，除数据通信外，CRC在很多领域也是大有用武之地的。
利用CRC进行检错的过程可简单描述如下：在发送端，根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码（CRC码），附在原始信息的后边，构成一个新的二进制码序列（共k + r位），然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则在差错控制理论中称为“生成多项式”。
(1) CRC编码的代数学原理
在代数编码理论中，将一个码组表示为一个多项式，码组中的各码元作为多项式的系数。
例如，1100101 表示为1·x6 + 1·x5 + 0·x4 + 0·x3+1·x2+0·x+1，即 x6+x5+x2+1。
设编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k；生成多项式为G(x)，G(x)的最高幂次等于r；CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x)。
发送方编码的方法是：将P(x)乘以xr（即对应的二进制码序列左移r位），再除以G(x)，得余式即为R(x)。
用公式可以表示为T(x) = xrP(x) + R(x)。
接收方解码的方法是：将T(x)除以G(x)，如果余数为0，则说明传输中无错误发生，否则说明传输有误。
举例来说，设信息码为1100，生成多项式为1011，即P(x) = x3 + x2，G(x) = x3 + x + 1，则可以用以下方法计算CRC。
即R(x) = x。注意到G(x)最高幂次r = 3，得出CRC为010。如果用竖式除法，计算过程为:
1011 1110
1100000 (1100左移3位)
1011
1110
1011
1010
1011
0010
0000
010
因此，T(x) = (x6 + x5) + (x) = x6 + x5 + x，即1100000+010=1100010。
如果传输无误，则
无余式。看一下上面的竖式除法，如果被除数是1100010，显然在商第3个1时，就能除尽。
上述推算过程有助于我们理解CRC的概念。但如果直接编程来实现上面的算法，不仅繁琐，而且效率也不高。实际上在工程中不会直接这样去计算和验证CRC。
表3-1列出了一些标准CRC的资料。
① 生成多项式的最高幂次项的系数固定为1，故在简记式中，将最高的1统一去掉了，如04C11DB7实际上是104C11DB7。
② 前称CRC-CCITT。ITU的前身是CCITT。
(2) CRC的硬件电路实现
图3-2给出了CRC 运算通用电路的方框图。
CRC计算的生成多项式G(x) 通常用n次多项式定义：G(x) = Xn + gn-1Xn-1+…+ giXi + … + g2X2 + g1X + 1，其中gi 为0或1，i= 1，2，…，n-1。通常CRC计算可以用有n个存储器级的移位寄存器实现，如图3-2所示。如果多项式的相应项的系数为1，那么相应的存储器级输入端的模2加法器是有分支的。根据应用的不同，在系统开始工作前将所有的移位寄存器全部置“0”或“1”。
在图3-2中输入端送入的是原始数据序列, 移位寄存器各级的输出b0、b1、…、bn-2、bn-1便是CRC 码字。其中b0 和bn-1分别代表最低有效位(LSB) 和最高有效位(MSB)。
(3) CRC的基本实现
以CRC-8（X 8 + X 2 + X 1 + 1）为例（如图3-3所示），它由多个移位寄存器和加法器组成。编码、解码前将各寄存器初始化为0，输入位作为最右边异或操作的输入之一。三个寄存器上的移位操作同时进行，均为左移一位，左边寄存器的最左一位作为三个异或操作的输入之一。每次移位时，最右边的寄存器内容作为中间异或操作的输入之一，中间的寄存器的内容作为最左边异或操作输入之一，各个异或操作的结果作为与它左边那个寄存器的移入位。重复以上步骤，每输入一位就做一次移位操作，直到输入了所有要计算的数据为止。这时，这个寄存器组中的数据就是CRC-8的结果。图3-3给出了CRC基本实现方法。
CRC的工作原理是：CRC在发送端编码和接收端校验时，都可以利用事先约定的生成多项式G(x)来得到，K位要发送的信息位可对应于一个(k-1)次多项式K(x)，r位冗余位对应于一个(r-1)次多项式R(x)，由r位冗余位组成的n = k + r位码字对应于一个(n-1)次多项式T(x) = X r * K(x) + R(x)。
(4) 循环冗余校验码的特点
CRC校验码的检错能力很强，不仅能检查出离散错误，还能检查出突发错误。CRC校验码具有以下检错能力：
- CRC校验码可检测出所有单个错误。
- CRC校验码可检测出所有奇数位错误。
- CRC校验码可检测出所有双位的错误。
- CRC校验码可检测出所有小于、等于校验位长度的突发错误。
- CRC校验码可以[1-(1/2)k-1] 的概率检测出长度为(K + 1)位的突发错误。