|
|
|
这种方式已经被广泛地在网络通信及磁盘存储时采用，所以在历年考试中出现的概率也比较大。先看几个基本概念。
|
|
|
|
在循环冗余校验码（Cyclical Redundancy Check，CRC）中，无一例外地要提到多项式的概念。一个二进制数可以以一个多项式来表示。如1011表示为多项式x3+x1+x0，在这里，x并不表示未知数这个概念，如果把这里的x替换为2，这个多项式的值就是该数的值。从这个转换可以看出多项式最高幂次为n，则转换为二进制数有n+1位。
|
|
|
|
编码的组成是由循环冗余校验码校验由K位信息码，加上R位的校验码。
|
|
|
|
和海明码的校验方程一样，生成多项式非常重要，以至于考试中总是直接给出。
|
|
|
|
由K位信息码如何生成R位的校验码的关键在于生成多项式。这个多项式是编码方和解码方共同约定的，编码方将信息码的多项式除以生成多项式，将得到的余数多项式作为校验码；解码方将收到的信息除生成多项式，如果余数为0，则认为没有错误，如果不为0，余数则作为确定错误位置的依据。
|
|
|
|
生成多项式并非任意指定，必须具备以下条件：最高位和最低位为1，数据发生错误时，余数不为0，对余数补0后，继续做按位除，余数循环出现，这也是冗余循环校验中循环一词的来源。
|
|
|
|
|
|
（1）将K位数据C（x）左移R位，给校验位留下空间，得到移位后的多项式C（x）×xR。
|
|
|
|
（2）将这移位后的信息多项式除生成多项式，得到R位的余数多项式。
|
|
|
|
|
|
例如，信息位为10100110，生成多项式为a(x)=x5+x4+x+1，则
|
|
|
|
|
|
C(x)×xR=x5×(x7+x5+x2+x)=x12+x10+x7+x6
|
|
|
|
|
|
|
|
得到余式为x4+x3，即校验码为11000，所以，得到的CRC码是1010011011000。
|
|
|
|
循环冗余校验码的纠错能力取决于K值和R值。在实践中，K值往往取得非常大，远远大于R的值，提高了编码效率。在这种情况下，循环冗余校验就只能检错不能纠错。一般来说，R位生成多项式可检测出所有双错、奇数位错和突发错位小于或等于R的突发错误。使用循环冗余校验码能用很少的校验码检测出大多数的错误，检错能力是非常强的，这是它得到了广泛应用的原因。
|
|
|
