循环冗余检验算法(CRC)与帧检验序列(FCS)

在数据链路层要解决数据传输的三个问题:

  • 封装成帧
  • 透明传输
  • 差错检验

这里,重点讨论一下差错检测里面最常用的一种检测算法,循环冗余算法(CRC)以及通过这个算法生成的帧检验序列(FCS)

首先,我们知道,数据在传输过程中可能会因为外界的电磁干扰从而使数据产生差错。使原来的0变为1,原来的1变为0。这叫做比特差错。在一段时间内,传输错误的比特占传输比特总数的比率称为误码率。所以说,正因为如此,我们开始采用各种检验差错的措施,而最广泛使用的就是循环冗余检验(CRC)

通过一个例子来说明CRC的原理:

首先在发送端,先把需要发送的数据划分为组,假定每组k个比特。现假定待传送的数据M为101001(k=6)。CRC运算就是在数据M的后面添加供差错检验用的n位冗余码,然后构成一个帧发送出去,一共发送了(k+n)位。

这n位冗余码可以利用以下的这个方法得到:

循环冗余检验算法(CRC)与帧检验序列(FCS)

首先我们在原来的数据后面加n个0,这样原来的数据就相当于左移了3位,也就是M*8,然后将加0之后得到的(k+n)位的数除以双方事先商定好的长度为(n+1)位的除数P,得出的商是Q而余数为R(n位)。接下来,让我们看看这个计算过程:

  • 1、数据前四位是1010,首位是1,除数为1101,所以我们先商1
  • 2、然后写在下面的就是1101,与1010进行不进位加法,结果为1110
  • 3、1110的首位依然是1,继续商1,然后进行不进位加法,结果为0111
  • 4、0111的首位为0,所以商0,然后同样不进位加法,结果为1110
  • 5、就这样一直往后算,直到最后求得余数R

从图中可以看出,最后得出的余数R为001,这个余数R就作为数据M后面添加的n位冗余码。即,R就是所谓的帧检验序列(FCS)

强调一下:循环冗余检验CRC是一种检验方法,而FCS是添加在数据后面的帧检验序列。检错方法有很多,我们也可以选用别的检错方法。

然后,就是接收端接收的时候,对接收到的数据以帧为单位进行CRC检测:把收到的每一帧都除以同样的除数P,然后检测得到的余数R。

如果传输过程中没有差错,那么经过CRC检验后得出的余数一定为0;如果R≠0,那么再传输过程中,肯定会有差错,则这个帧就丢弃。

还有一种情况就是:如果出现误码,余数R仍然等于0。通过实际检测计算,出现这种情况的概率非常非常小。

在数据链路层,发送端帧检验序列FCS的生成和接收端的CRC检验都是用硬件完成的,处理很迅速,因此并不会延误数据的传输。

从上述我们也可以看出,如果想要进行差错检验,加入冗余码,就必须以帧为单位来传送数据,然后每一帧都加入冗余码,一帧一帧发送,接收端一帧一帧检验。

注:CRC检验只能保证接收端接收到的帧没有差错,至于有没有出现帧丢失,帧重复,帧失序,是无法判断的。

过去,由于通信链路质量不好引起差错的概率比较大,所以,我们要求数据链路层向网络层提供可靠传输,增加了帧编号,确认和重传机制。提供可靠传输的协议是高级数据链路控制(HDLC)。但是,现在由于通信链路的质量已经大大提高,误码率大大降低,所以对于现在的Internet采取了区别对待的方法:

  • 对于通信质量良好的有限传输链路,数据链路层不提供可靠传输,如果数据链路层的数据出了差错,则改正差错的的任务就由上层协议来完成。
  • 对于通信质量较差的无线传输链路,数据链路层使用确认和重传机制,向上层提供可靠的传输服务。

通过实践证明,这样做可以提高通信效率。