信息码添四个零,去除多项式,得到余数,为****
Computer Networks 自顶向下方法书里有！
设编码前的原始信息多项式为P(x),P(x)的最高幂次加1等于k；生成多项式为G(x),G(x)的最高幂次等于r；CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x).
发送方编码方法：将P(x)乘以xr(即对应的二进制码序列左移r位),再除以G(x),所得余式即为R(x).用公式表示为T(x)=xrP(x)+R(x)
接收方解码方法：将T(x)除以G(x),得到一个数,如果这个余数为0,则说明传输中无错误发生,否则说明传输有误.
如果用竖式除法(计算机的模二,计算过程为
如果传输无误,
上述推算过程,有助于我们理解CRC的概念.但直接编程来实现上面的算法,不仅繁琐,效率也不高.实际上在工程中不会直接这样去计算和验证CRC.
下表中列出了一些见于标准的CRC资料：
名称 生成多项式 简记式* 应用举例
备注：
（1）生成多项式是标准规定的
①.、将X的最高次幂为R的生成多项式G(X)转换成对应的R+1位二进制数.
解：
①.010000
①.011
------------------
0001000
011
得到的余位011,所以最终编码为：1010 011
* CRC.C——CRC程序库 */
/* 以上为CRC除数的定义 */
#define NIL 0
/* 以上两个宏可以代替函数crcupdate和crcrevupdate */
#include #include #include /* 函数crchware是传统的CRC算法,其返回值即CRC值 */ unsigned short crchware(data,genpoly,accum)
unsigned short data;/* 输入的数据 */
unsigned short genpoly;/* CRC除数 */
unsigned short accum;/* CRC累加器值 */
{
static int i;
accum=(accum1)^genpoly;
else
accum=1;
data=1;
}
return (accum);
/* 函数mk-crctbl利用函数crchware建立内存中的CRC数值表 */
unsigned short *mk-crctbl(poly,crcfn);
unsigned short poly;/* CRC除数--CRC生成多项式 */
Runsigned short (*crcfn)();/* 指向CRC函数(例如crchware)的指针 */
/* unsigned short */malloc(); */
unsigned short *crctp;
int i;
return 0;
crctp=(*crcfn)(i,poly,0);
return crctp;
/* 函数mk-crctbl的使用范例 */
if((crctblp=mk-crctbl(CRCCCITT,crchware))==NIL)
puts("insuff memory for CRC lookup table.\n");
return 1; */
/* 函数crcupdate用以用查表法计算CRC值并更新CRC累加器值 */
void crcupdate(data,accum,crctab)
unsigned short *accum;/* 指向CRC累加器的指针 */
unsigned short *crctab;/* 指向内存中CRC表的指针 */
static short comb-val;
/* 函数crcrevhware是传统的CRC算法的反序算法,其返回值即CRC值 */
unsigned short crcrevhware(data,genpoly,accum)
unsigned short data;
unsigned short genpoly;
unsigned short accum;
if((data^accum)0x0001)
return accum;
/* 函数crcrevupdate用以用反序查表法计算CRC值并更新CRC累加器值 */
void crcrevupdate(data,accum,crcrevtab)
unsigned short *accum;
这几天一直在看CRC校验算法.CRC版本众多,网站上实现算法一大坨,可一开始根本搞不清楚那个是哪个.连续上百度,哔哩哔哩,知乎看了很多解读CRC算法的,终于有了一些眉目,打算写下来,方便日后参考.
CRC算法核心其实只有一种,即二进制除法的实现,版本众多的原因主要有以下几个原因：
CRC字段的长度
多项式公式
初始值
输出是否水平翻转
输入是否水平翻转
结果异或值
我绝大多数的文章都只谈到了CRC字段的长度和多项式公式,没有涉及剩余的三项在crc算法中的应用.
多项式公式 是我们二进制多项式算法中的除数.不同的算法往往取的多项式是不一样的.
初始值 ,是指CRC字段的初始值.常常是从0和全是1中选择.
输入反转. 具体的操作方法实施将输入的数据按照字节为单位进行水平反转.比如01000001,翻转结果是10000010.
输出翻转 .输出翻转的操作与输入翻转操作是一样的.只是输出翻转是将整个CRC字段进行水平翻转.
结果异或值 ,是用来和 通过上述的算法算出来的结果 进行异或的一个数据值.如果这个值是0的话,那么就相当于没有进行异或.
为什么需要这么多看起来乱七八糟的种类呢.这些算法分别针对不同的数据的检验.针对不同的数据的特性,比如说某些数据,一开始就会有大量的零,如果不采用输入翻转或者初始值的话,那么这些0就对于校验结果没有任何影响.这就如我们想要的结果有出入了,我们希望校验结果和数据是一一对应的,并且是唯一的.如果不唯一那么,校验结果也就失去了意义.所以呢这么多算法的出现,主要原因就是为了适应不同的数据字符串的特点.
下面就是一些例子了.
验证网站：
CRC意思是循环冗余码校验.
校验原理：（M-R）/G=Q+0/G
说明：以接收到的校验码除以约定的除数,若余数为0,则可认为接收到的数据是正确的.
例：有效信息1101,生成多项式样1011
循环校验码解：
扩展资料：
CRC码集选择的原则：
若设码字长度为N,信息字段为K位,校验字段为R位（N=K+R）,则对于CRC码集中的任一码字,存在且仅存在一个R次多项式g（x）,使得
V（x）=A（x）g（x）=xRm（x）+r（x）；
其中：m（x）为K次信息多项式,r（x）为R-1次校验多项式,
g（x）称为生成多项式：
发送方通过指定的g（x）产生CRC码字,接收方则通过该g（x）来验证收到的CRC码字.