若信息码字为111000110，生成多项式G(x)=x<sup>5</sup>+x<sup>3</sup>+x+1，则计算出的..

在循环冗余校验码（Cyclical Redundancy Check，CRC）中，无一例外地要提到多项式的概念。一个二进制数可以以一个多项式来表示。如1011表示为多项式x³+x¹+x⁰，在这里，x并不表示未知数这个概念，如果把这里的x替换为2，这个多项式的值就是该数的值。从这个转换可以看出多项式最高幂次为n，则转换为二进制数有n+1位。

编码的组成是由循环冗余校验码校验由K位信息码，加上R位的校验码。

和海明码的校验方程一样，生成多项式非常重要，以至于考试中总是直接给出。

由K位信息码如何生成R位的校验码的关键在于生成多项式。这个多项式是编码方和解码方共同约定的，编码方将信息码的多项式除以生成多项式，将得到的余数多项式作为校验码；解码方将收到的信息除生成多项式，如果余数为0，则认为没有错误，如果不为0，余数则作为确定错误位置的依据。

生成多项式并非任意指定，必须具备以下条件：最高位和最低位为1，数据发生错误时，余数不为0，对余数补0后，继续做按位除，余数循环出现，这也是冗余循环校验中循环一词的来源。

校验码的生成步骤如下：

（1）将K位数据C（x）左移R位，给校验位留下空间，得到移位后的多项式C（x）×x^R。

（2）将这移位后的信息多项式除生成多项式，得到R位的余数多项式。

（3）将余数作为校验码嵌入信息位左移后的空间。

例如，信息位为10100110，生成多项式为a(x)=x⁵+x⁴+x+1，则

C(x)=x⁷+x⁵+x²+x

C(x)×x^R=x⁵×(x⁷+x⁵+x²+x)=x¹²+x¹⁰+x⁷+x⁶

求余式：

得到余式为x⁴+x³，即校验码为11000，所以，得到的CRC码是1010011011000。

循环冗余校验码的纠错能力取决于K值和R值。在实践中，K值往往取得非常大，远远大于R的值，提高了编码效率。在这种情况下，循环冗余校验就只能检错不能纠错。一般来说，R位生成多项式可检测出所有双错、奇数位错和突发错位小于或等于R的突发错误。使用循环冗余校验码能用很少的校验码检测出大多数的错误，检错能力是非常强的，这是它得到了广泛应用的原因。

校验码

计算机系统运行时，在各个部件之间经常需要进行数据交换，为保证数据传送过程的正确无误，必须引入差错检查机制对数据进行校验，以检测是否有数据传送错误。其基本原理是：在编码中引入一定的冗余位，当被传送的编码中出现错误时就使之成为非法代码而被检测出。

奇偶校验码

奇偶校验码用于并行码的检错。其原理是：在k位数据码之外增加1位校验位，使k+1位码字中取值为1的位数总保持为偶数（偶校验）或奇数（奇校验）。

（1）水平校验：设最高位为校验位。

原有数字位生产新的码字：偶校验奇校验

（2）垂直校验：设4个字节的数据为一组进行垂直奇校验。

第一字节数据：10110011

第二字节数据：11011001

第三字节数据：01010101

第四字节数据：10001100

垂直校验位：01001100

（3）垂直水平校验：设4个字节的数据为一组进行垂直水平奇校验。

水平校验位

第一字节数据：10110011 0

第二字节数据：11011001 0

第三字节数据：01010101 1

第四字节数据：10001100 0

垂直校验位：01001100

海明码

海明码用于多位并行数据检错纠错处理。

实现：为k个数据位设r个校验位，使k+r位的码字（即海明码）能发现k位中任何一位出错且可以纠正。

其数据位k和校验位r必须满足如下关系式：

2^r≥k+r+I

1）海明码的编码规则

设r个校验位P_rP_r_-1…P₁,k个数据位D_k_-1D_k_-2…D₀，产生的海明码为H_r₊_k,H_r₊_k_-1…H₁，则有如下规则。

规则1：Pi在海明码的2ⁱ-1位置，即H_j=P_i,j=2ⁱ-l；数据位则依序从低至高占据海明码中其他的位置。

规则2：海明码中的任意位都是由若干校验位来校验的。其对应关系是：被校验的海明位的下标等于所有参与校验该位的校验位的下标之和，而校验位则是由其自身来校验的。

2）海明码校验

下面以k=8对纠1位错的海明码的编码及校验原理给予说明。

（1）确定r的位数。

当r=4时，有2⁴≥8+4+1，可以满足2^r≥k+r+1。

（2）确定海明码的位置。

由规则1，P_i对应H_j的位置。

如：确定P₄的位置，因j=2^i-1=2^4-1=8，则有P₄在H₈的位置。同理得到以下位置的对应关系：

H₁₂H₁₁H₁₀H₉H₈H₇H₆H₅H₄H₃H₂H₁

D₇D₆D₅D₄P₄D₃D₂D₁P₃D₀P₂P₁

（3）确定编码方案。

由规则2，编码方案如下：

形成H_i与P₁相关的数据位有：S₁=D₀十D₁十D₃十D₄十D₆。

形成H_i与P₂相关的数据位有：S₂=D₀十D₂十D₃十D₅十D₆。

形成H_i与P₃相关的数据位有：S₃=D₁十D₂十D₃十D₇。

形成H_i与P₄相关的数据位有：D₇十D₆十D₅十D₄。

得校验关系：S₄=D₄十D₅十D₆十D₇。

（4）确定纠错译码方案。

设G₁=S₁十P₁；G₂=S₂十P₂；G₃=S₃十P₃；G₄=S₄十P₄。若采用偶校验则G₄~G₁的值全为0时数据正确，反之有错。用对出错位取反的方法即可实现纠错。

例如，G₄~G₁=0111，其值为7，对应于H₇（D₃的位置）。将D₃的值取反就实现了纠错。

循环冗余校验码（CRC）

利用生成多项式为k个数据位产生r个校验位来进行编码，其编码长度为k+r。CRC的代码格式为：

由此可知循环冗余校验码由两部分组成，左边为信息码，右边为校验码，若信息码占k位，则校验码就占n-k位，所以又称为（n,k）码。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5