A-A+

CRC编码电路 旧文一篇

2016年12月02日 未分类 暂无评论 阅读 99 次

偶然发现在CSDN上还写过几篇博客,这篇是2011年学习CRC编码电路的时候写的,先贴在这里。想不起来是什么课上学的了……并且我好像也看不太懂了……

 

CRC(Cyclic Redundancy Check)原理:信息码为K位,其后添加R位的冗余校验码,整个编码长度为N(N=K+R),即是一种(N,K)码。CRC码的生成需要指定一个生成多项式G(x),且G(x)为(R+1)次的多项式。对于码M(x),CRC码校验值R(x)=2^R*M(x)%G(x)  [注这里是模2除],整个CRC码C(x)=2^R*M(x)+R(x)。通俗地说,M(x)模2除以G(x),余数添加到M(x)后面,就得到了CRC码。

这里插一段模2运算的知识。模2运算是指以按位模2相加为基础的四则运算,运算时不考虑位间进位和借位。因为不考虑进位和借位,所以模2加与模2减相同。对每一位有:0±0=0,0±1=1,1±0=1,1±1=0。模2乘是用模2加来累加部分积。模2除上商规则为当前余数(第一次为被除数)最高为为1则商1,否则商0,求余数时按模2减来求余数。

例子:信息为100,G(x)=x^2+1即除数为101,则先将信息左移两位(因为G(x)为三位,余数为两位)得10000,在用10000模2除以101,得商101,余数01,因此CRC=10001。

CRC电路

首先说模2除电路:(电路T触发器标识有误,从左到右依次为T3,T2,T1,T0,图中全部标成T3了)

模2除电路示意图

图1 - 模2除电路

模2除的步骤分成两种操作,如果当前余数(第一次为被除数)最高为位0,直接将余数左移一位(应是先减去0000,但减0000等于没减,因此不用做减法),如果当前余数(第一次是被除数)最高为位1,则先模2减G(x),然后减完的余数再左移一位。

图1的解释:T[3...0]即余数,其中四个异或门输入为1011是指定的G(x),"或0000"是指当商0时,不需要做减法,只进行左移。图中异或门的输出端连到左边一位寄存器的输入端,同时实现了模2除和移位。

因为G(x)固定,所以G2端始终是0,即原来为0的Gi,都可以去掉,而将右边一个寄存器的输出端直接连到左边一个的输入端。异或门的输入是G(x),还是0000,取决于商为1还是0,而商为1还是0取决于余数的最高为是1还是0,即取决于T3,所以可以将T3的输出端分别连到各个异或门上。因为只求三位余数,因此T0和G3都不再需要,可以去掉。于是得到下面的化简的图2:

化简后的模2除电路

图2 - 化简后的模2除电路

图2解释:CP为脉冲。

CRC电路在模2除电路基础上,增加开关电路,首先将信息码同时直传到输出端和模2电路,这完成后,模2电路中的寄存器即存放了余数,再将余数输出到CRC电路的输出端。如下图:

图3 - CRC电路示意图

图3为示意图,应该加上脉冲CP,开关K应该为数据选择器MUX,还要计数电路。

 

参考链接

 

http://www.dz3w.com/articlescn/com/0081726.html

http://www.dz3w.com/articlescn/com/0081728.html

主要参考了这些,图1和图2也是出于此处。

标签:

给我留言