发布时间 : 星期一 文章(13 - 9)CRC冗余校验码的编译码仿真实现更新完毕开始阅读087f01b3e2bd960591c67734
信源 信宿
编码 译码 信道 ARQ ARQ
信道 图1-5混合纠错方式
1.8 差错编码的特性和能力
1.8.1 海明距离
就是从一个顶点移动到另一个顶点所经历立方体的最少边数。 1.8.2 最小距离
所谓最小距离就是立方体中从一个顶点移到另一个顶点所经历的最少边数 。
1.8.3最小距离与抗干扰能力之间的关系
定理1若一种码的最小距离为d0，则它能检查传输错误个数（检错能力）e应满足：d0>=e+1
定理2若一种码的最小距离为d0，则它能纠正传输错误个数（纠错能力）t应满足：d0>=2t+1
定理3若一种码的最小距离为d0，则它的检错能力和纠错能力应满足：d0>=e+t+1 （e>=t）
1.9 循环冗余校验码（CRC）原理
在计算机通信中用的最广泛检错码是一种漏检错率低得多也便于实现的循环冗余校验码，又称多项式码。这是因为，任何一个二进制数位串组成的代码都可以和一个只含有0和1的两个系数的多项式建立一一对应的关系。一个k位帧
k-1可以看成是从X 到X0的k次多项式的系数序列，这个多项式的阶数为k-1，高
位时X k-1项的系数，下一位是X k-2项的系数，以此类推。例如，1011011有7位，表示成多项式是X6+X4+X3+X+1。
CRC校验的思想是利用线性编码的理论，在发送端根据要传一个n比特的帧或报文，发送器生成一个r比特的序列。这样形成的帧将由（n+r）比特组成。这个帧刚好能够被某个预先确定好的数整除。接收端用相同的数去除外来的帧，如果无余数，则认为无差错。
循环冗余校验码与奇偶校验码不同，后者是字符校验一次，而前者是字符串校验一次。在同步串行通信中，几乎都是用这种校验方法。
一个n位的循环码是由k位信息位加上r位校验位组成的，其中r=n-k。如图1-6所示。
n位循环码
K 位 R 位（ R=n-k ）
信息位 校验位（CRC校验） 图1-6 n位循环码
通常把这样的新组成的二进制位序列叫做循环冗余码（CRC）。表征CRC码的多项式叫生成多项式。K位二进制数加上r位CRC码后，即信息位要向左移（n-r）位，这相当于B（X）乘以X^r B（X）被生成多项式除，得整数多项式加上余数多项式。
由以上分析可知，CRC校验的关键是如何求出余数，此余数即为校验码（CRC校验码）。以前通常用数字电路来实现，而现在用计算机来完成。
二、系统分析
2.1 循环码（13,9）算法设定
循环码是线性分组码的一种，具有严密的代数学理论。循环码除了具有线性分组码的封闭性，即两个循环码组的模二加仍是一个循环码组外，还具有循环性，即一个循环码组循环移位后，将最右端的码组移至左端，仍是一个循环码组。我们由生成多项式g（x）很容易计算出生成矩阵G，g（x）必须为一个常数项不为0的（n-k）次多项式，并且Xn+1是一个因式，本次课程设计选取循环码（13,9）的生成多项式g（x）=x4+x+1。
2.2 循环码（13,9）编码算法分析
2.2.1编码规则
CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为(n,k)码。 它的编码规则是：
1．移位:将原信息码(kbit)左移r位(k+r=n)
2．相除:运用一个生成多项式g(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码。
非常简单，要说明的,模2除就是在除的过程中用模2加，模2加实际上就是我们熟悉的异或运算，就是加法不考虑进位，公式是： 0+0=1+1=0,1+0=0+1=1 由此得到定理：a+b+b=a 也就是‘模2减’和‘模2加’直值表完全相同。有了加减法就可以用来定义模2除法，于是就可以用生成多项式g(x)生成CRC校验码。
2.2.2 编码算法
该编码算法比较简单，只需要三步即可。第一步，将信息码组m(x)乘以x4得到m(x)x4；第二步，计算上式与g(x)的除法，得到商q(x)和余数r（x）；最后，计算编码后的码组多项式g(x)=m(x)x4+r(x)。
2.3 循环码（13,9）译码算法分析
设接收到的码组位R（x），若C(x)=R(x),则说明接收到的码组正确，若该式不成立，则说明接收到的码组错误。且有R(x)=C(x)+E(x),其中E（x）为伴随式。如果要纠正一位错误（若要纠正多位错，则需要监督矩阵的位数），当然，为了提高效率也要增加信息位的长度。实际上，一个16位的码组中有两位都出错的概率要比只错一位的概率小得多。这里，E（x）有24种组合。一个15位的
码组中若哪一位出了错，经过计算，伴随式与错误图样均有一定的关系。
2.4 CRC冗余校验码的实现方法
CRC计算可以靠专用硬件来实现，但对于低成本的微控制器系统，在没有硬件支持的情况下实现CRC检验，其关键问题是如何通过软件来实现CRC计算，也就是CRC算法的问题。到达接收方的数据单元首先到达的是数据，然后是CRC校验码。接收方将整个数据串当作一个整体去除以用来产生循环冗余校验余数的同一个除数。如果数据串无差错地到达接收方，循环冗余校验器将产生余数0。因此数据单元将通过检验。如果在传输中数据单元被改变，除法将产生非零余数，因此数据单元将通不过检验。 2.4.1 CRC校验的硬件实现
尽管CRC在数学上是复杂的，但可以用简单的，便宜的硬件来实现，并且绝大多数是硬件实现。CRC校验编码与译码的电路是相同的。 2.4.2 CRC校验的软件实现
对于带有CPU的嵌入式系统，可以用软件实现CRC校验。其优点是模块代码少，修改方便，可移植性好。但缺点是计算量大，与硬件实现相比，速度较慢。CRC校验程序是根据CRC校验码的产生原理来设计的，通常采用MATLAB进行编译。