循环冗余校验_循环冗余校验原理_在循环冗余校验系统中

CRC。循环冗余校验是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数。

主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。

中文名,循环冗余校验。全称,Cyclic Redundancy Code。原理,除法及余数的原理来作错误侦测。

简介。在数据传输过程中。无论传输系统的设计再怎么完美。

差错总会存在。这种差错可能会导致在链路上传输的一个或者多个帧被破坏。从而接受方接收到错误的数据。为尽量提高接受方收到数据的正确率。在接收方接收数据之前需要对数据进行差错检测。当且仅当检测的结果为正确时接收方才真正收下数据。检测的方式有多种。常见的有奇偶校验。因特网校验和循环冗余校验等。

工作原理。循环冗余校验同其他差错检测方式一样。

通过在要传输的k比特数据D后添加比特冗余位F形成n比特的传输帧T。再将其发送出去。特别的。循环冗余校验提供一个预先设定的比特整数P。并且要求添加的比特F满足：T mod P == 0 ……T = 2n-kD + F …… 基于上述要求。实际应用时。发送方和接收方按以下方式通信：1. 发送方和接收方在通信前。约定好预设整数P。2. 发送方在发送前通过和式确定并填充F。

然后发送。3. 接收方收到数据。进行 result = T mod P 运算。当且仅当result = 0时接收方认为没有差错。发送方在发送数据前需要确定填充的比特F。以下提供了两种等价的方式来确定F。模二运算采用无进位的二进制加法。恰好为异或操作。由于我们最终的目的是式。根据式。我们有/P = 2n-kD / P + F / P …… 现在。我们令2n-kD / P = Q + R / P …… 于是。循环冗余校验

我们有 / P = Q + R / P+ F / P …… 由于采用无进位的二进制加法。因此当我们令 F = R 时。即T = 2n-kD + R。有 / P = Q + R / P+ F / P = Q …… 此时便有式成立。因此利用模二加法我们知。我们需要添加的帧检验序列F为：F = 2n-kD modP …… 该种方法。我们试图对任意的二进制数都构造与其对应的一个二进制系数多项式。构造如下：对于任意k位二进制数D =dk-1…d2d1d0。

其对应的多项式为D = ∑di*Xi。i∊[0, k) …… 例如。D = 110101。则D = X5 + X4 + X2 + 1。运算过程依然是模二的。则此时的CRC过程可描述如下：Xn-kD / P = Q + R / P …… T = Xn-kD + R …… 即。此时的F满足：F = Xn-kD mod P …… 。

常用CRC版本。上面我们介绍了F的求法。

但F依赖于P。因此选取一个合适的P也是CRC的一个关键问题。通常。一个m位的CRC多项式P是由如下两种形式的多项式之一产生的：P = q …… P = q …… 其中q是一种特殊类型的多项式。称为本原多项式。且P满足：下面展示常用CRC版本：。

生成多项式的选择方案。上面我们提供了很多国际标准的CRC生成多项式版本。

但在我们实际的应用当中。我们只需要选择其中的一种作为生成多项式即可。可是我们应该如何做出选择呢？下面我们根据几张8bits-16bits实验仿真图来对不同的标准进行横向和竖向的比较。从而给出一种比较合适的选择方案。注：1. 以下几图中。蓝色虚线为实验者提出的标准最小漏检率曲线。下面我们称为最佳性能曲线。2. 以下图和数据来自《CRC性能分析及生成多项式选取的研究》。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-38616-1.html