CRC校验字节型算法查表法解读

个人收集整理-ZQCRC校验字节型算法查表法解读校验字节型算法查表法解读(备忘)算法以下为转载: 校验算法已经有成熟和比较经典的现成代码可供我们利用。计算可以靠专用的硬件来实现,但是对于低成本的微控制器系统,在没有硬件支持下实现检验,关键的问题就是如何通过软件来完成计算,也就是算法的问题。校验的基本思想是利用线性编码理论,在发送端根据要传送的位二进制码序列,以一定的规则产生一个校验用的监督码（既码）位,并附在信息后边,构成一个新的二进制码序列数共()位,最后发送出去。在接收端,则根据信息码和码之间所遵循的规则进行检验,以确定传送中 是否出错。b5E2R。b5E2R。接收方收到后，用 () 除多项式，若有余数，则传输有错。.生成多项式。位的码产生的规则是先将要发送的二进制序列数左移位（既乘以）后,再除以一个多项式,最后所得到的余数既是码。任意一个由二进制位串组成的代码都可以和一个系数仅为和取值的多项式一一对应。例如：代码对应的多项式为，而多项式为对应的代码。p1Ean。p1Ean。标准生成多项式如下表：名称 生成多项式 简记式* 标准引用 , , , , , , , 叶子：这里不知道问什么省略了，有些迷惑哦。要是生成多项式要是都省了，那还怎么校验？我猜想可能是中间的全为一吧。DXDiT。DXDiT。生成多项式的最高位固定的，故在简记式中忽略最高位了，如实际是。、基本算法（人工笔算）：以为例进行说明，校验码为位，生成多项式位。假如数据流为字节：、；数据流左移位，相当于扩大倍，再除以生成多项式，做不借位的除法运算（相当于按位异或），所得的余数就是校验码。RTCrp。RTCrp。发送时的数据流为字节：、；、计算机算法（比特型算法）：)将扩大后的数据流（字节）高位（、）放入一个长度为的寄存器；)如果寄存器的首位为，将寄存器左移位(寄存器的最低位从下一个字节获得)，再与生成多项式的简记式异或；否则仅将寄存器左移位(寄存器的最低位从下一个字节获得)；)重复第步，直到数据流（字节）全部移入寄存器；)寄存器中的值则为校验码、。、计算机算法（字节型算法）：表示的次方把按字节排列的数据流表示成数学多项式，设数据流为、，表示成数学表达式为()5PCzV。5PCzV。*，在这里表示为异或运算。设生成多项式为（），码为。则，()，即数据流左移位，再除以生成多项式。先变换、扩大后的形式，()()()()()()()()这样就推导出，字节的校验码为()，即上一字节校验码的高位（）与本字节异或，jLBHr。jLBHr。该结果单独计算校验码（即单字节的位校验码，对单字节可建立表格，预先生成对应的位校验码），所得的校验码与上一字节校验码的低位（）xHAQX。xHAQX。乘以（即左移位）异或。然后依次逐个字节求出，直到。字节型算法的一般描述为：本字节的码，等于上一字节码的低位左移位，与上一字节右移位同本字节异或后所得的码异或。LDAYt。LDAYt。字节型算法如下：)寄存器组初始化为全()。（注意：寄存器组初始化全为时，最后应取反。）)寄存器组向左移位,并保存到寄存器组。)原寄存器组高位（右移位）与数据字节进行异或运算，得出一个指向值表的索引。)索引所指的表值与寄存器组做异或运算。)数据指针加，如果数据没有全部处理完，则重复步骤)。)得出。 ( * , )函数功能：计算数据流* 的位校验码，数据流长度为 ; 初始化() ( ) *) ; 表由函数生成; ; ( )函数功能：生成对应的校验码，其实就是计算机算法（比特型算法）为生成多项式注意，低位先传送时，生成多项式应反转(低位与高位互换)。如为，反转后为 ; ;() )() 反转时() ;：码集选择的原则若设码字长度为，信息字段为位，校验字段为位()，则对于码集中的任一码字，存在且仅存在一个次多项式()，使得Zzz6Z。Zzz6Z。()()()()();其中: ()为次信息多项式， ()为次校验多项式，()称为生成多项式：() ()()发送方通过指定的()产生码字，接收方则通过该()来验证收到的码字。、校验码软件生成方法：借助于多项式除法，其余数为校验字段。例如：信息字段代码为: ；对应()假设生成多项式为：()；则对应()的代码为: () 对应的代码记为：；采用多项式除法:得余数为: (即校验字段为：）发送方：发出的传输字段为: 信息字段 校验字段接收方：使用相同的生成码进行校验:接收到的字段生成码（二进制除法）， 如果能够除尽，则正确。以上字节型算法(红字部分)解读:比特型算法较易理解,这里不做解释.一般我们应用中更多的是用字节型的算法,而大部字节型算法为了提高效率是利用查表法实现的,对于查表法,表是如何产生的,有时迷惑,所以在此对字节型查表法推导过程的理解做一个备忘:dvzfv。dvzfv。由等式一到等式二的推导 和分别为的商和余子式,所以可以进行转换;其它的暂不变;由等式二到等式三的推导:由于只关心余子式,所以可以不理,对与后一字节进行进一步的结合处理,提取();rqyn1。rqyn1。由等式三到等式四的推导:把进一步分解成高低位 ();由等式四到等式五的推导:重新组合得();这样就推导出，字节的校验码为()，即上一字节校验码的高位（）与本字节异或，该结果单独计算校验码