标签: hash

【原始内容来自网络，加入了部分自己的理解。】 概念： CRC ： Cyclic Redundancy Check, 循环冗余校验。 利用除法和余数的原理来对数据进行校验和纠错。特征是信息字段和校验字段的长度可以任意选定。 多项式： 任意一个二进制数可以与一个系数非1即0的多项式相对应，如1011对应多项式为x^3+x+1。一个nbit的二进制数可对应一个(n-1)次幂的多项式。 模二除法： 与算术除法类似，但不向上一位借位，每一位除的结果不影响其他位，实际上就是异或。 生成多项式： 生成多项式也是一个二进制数，它是发送方和接收方的一个约定，在整个传输过程中，这个数始终保持不变。 在发送方，用生成多项式对信息多项式做模二除法，产生校验码。在接收方，用生成多项式对收到的编码多项式做模二除法检测，并确认错误位置。 生成多项式的最高位和最低为必须为1。 常见于标准的生成多项式如下。     原理： 若设码字长度为N，其中信息字段长度为K，校验字段长度为R，则有N=K+R。对于CRC码集中的任一码字，存在且仅存在一个生成多项式g(x)，使得 m(x)*(x^R)+r(x) = V(x) = A(x)g(x)+d(x); 其中，m(x)为(K-1)次原始的信息多项式； r(x)为(R-1)次校验多项式（即校验和，是用m(x)向左移位Rbit后的数对生成多项式做模二除法所得的余数）； g(x)为R次生成多项式； V(x)为发送方传递给接受方的CRC码字； d(x)为V(x)对g(x)做模二除法所得的(R-1)次余数，正确情况下应该为0。   在发送方，根据已知的N、K、R、m(x)、g(x)，计算出r(x)，生成V(x)，作为最终的码字发出； 在接收方，根据已知的N、K、R、V(x)、g(x)，计算得出A(x)、d(x)，若d(x)为0，说明校验结果正确。若d(x)不为0，则说明数据在传输过程中出现了错误。   其他特性： 由于CRC的计算基于除法，任何多项式都无法检测出一组全零数据出现的错误或前面丢失的0； 所有只有一个bit位的错误都可以被至少有两个非0系数的任意多项式检测到； CRC可以检测出所有间隔距离小于生成多项式阶次的两bit错误。 CRC是散列函数（hash算法）的一种，也存在一定的冲突概率。所以生成多项式的设计和选择至关重要。 生成多项式最重要的属性是长度。生成多项式必须是不可分解多项式，即除了1与它自身之外不能被任何其他的多项式整除。   生成多项式的选择还要取决于信息字段的长度。如果我们希望在接收方检测时能明确知道具体的错误位置，那么余数值的集合就要大于等于码字的长度，要满足：2^(R-1) = N，也即：2^(R-1) = (R+K)。 由此可知，CRC-4适合用来检测4bit以内的信息字段； CRC-8适合用来检测120bit以内的信息字段； …