CRC码一般是指k位信息码之后拼接r位校验码。应用CRC码的关键,是如何从k位信息位简便地得到r位校验位(编码)的值,以及如何判断k+r位的码字是否正确。下面仅就CRC码应用中的问题做简单介绍(有关的理论问题请参阅有关书籍)。
模2运算是指以按位模2相加为基础的四则运算,运算时不考虑位间进位和借位。
上商的原则是:当部分余数的最高位为1时,该位商取1;为0时,该位商取0。当部分的余数的位数小于除数的位数时,该余数即为最后余数。
若将信息位组左移r位,则可表示为多项式M(x) * xr,这样就可以空出初值为0的r个校验位,即
CRC码的码字,是用k个数据位拼接上r个校验位得到的。校验位的值,就是通过对多项式M(x) * xr除以生成多项式G(x)(特定的一个多项式)所得到的余式。为了得到r位余数(校验位),G(x)必须是r+1位的,即为r次的多项式。
将r次余式直接拼接在源数据多项式的右侧,可写成M(x).xr + R(x),并可推导出:
这证明所得到的CRC码字是一个可被G(x)(多项式)数码除尽的数码(多项式)。
例:对四位源信息 1100,来求三个校验位的值,可选择生成多项式为 1011,则有: