循环冗余校验码（Cyclic Redundancy Check ，CRC)是数据通信领域中最常用的一种差错校..

2017年上半年上午试卷综合知识

第 14 题


知识点	编码数据通信校验码循环冗余校验码
关键词	编码差错校验数据通信校验码校验位循环冗余校验
章/节	数据通信与计算机网络

循环冗余校验码（Cyclic Redundancy Check ，CRC)是数据通信领域中最常用的一种差错校验码，该校验方法中，使用多项式除法（模2除法）运算后的余数为校验字段。若数据信息为n位，则将其左移k位后，被长度为k+1位的生成多项式相除，所得的k位余数即构成k 个校验位，构成n+k位编码。若数据信息为1100，生成多项式为X³+X+1 (即1011) ，则CRC编码是（）。

A. 1100010

B. 1011010

C. 1100011

D. 1011110

相关试题数据通信的基本知识

第67题

2014年上半年

假设网络的生产管理系统采用B/S工作方式，经常上网的用户数为100个，每个用户每分钟产生11各事务处理，平均每个事务处理的数据量大小为0.06MB，则这个系统需要的信息传输速率为（67）。

第68题

2013年上半年

在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和2位终止位，每秒钟传送100个字符，则有效数据速率为（68)。

第14题

2011年上半年

若计算机采用CRC进行差错校验，生成多项式为G（X）=X⁴+X+1，信息字为10110, 则CRC校验码是（14)。

知识点讲解

· 编码

· 数据通信

· 校验码

· 循环冗余校验码

编码

编码过程

在给定了软件设计规格说明书后，下一步的工作就是编写代码。一般来说，编码工作可以分为四个步骤：

（1）确定源程序的标准格式，制订编程规范。

（2）准备编程环境，包括软硬件平台的选择，包括操作系统、编程语言、集成开发环境等。

（3）编写代码。

（4）进行代码审查，以提高编码质量。为提高审查的效率，在代码审查前需要准备一份检查清单，并设定此次审查须找到的bug数量。在审查时，要检查软件规格说明书与编码内容是否一致；代码对硬件和操作系统资源的访问是否正确；中断控制模块是否正确等。

编码准则

在嵌入式系统中，由于资源有限，且实时性和可靠性要求较高，因此，在开发嵌入式软件时，要注意对执行时间、存储空间和开发／维护时间这三种资源的使用进行优化。也就是说，代码的执行速度要越快越好，系统占用的存储空间要越小越好，软件开发和维护的时间要越少越好。

具体来说，在编写代码时，需要做到以下几点：

.保持函数短小精悍。一个函数应该只实现一个功能，如果函数的代码过于复杂，将多个功能混杂在一起，就很难具备可靠性和可维护性。另外，要限制函数的长度，一般来说，一个函数的长度最好不要超过100行。

.封装代码。将数据以及对其进行操作的代码封装在一个实体中，其他代码不能直接访问这些数据。例如，全局变量必须在使用该变量的函数或模块内定义。对代码进行封装的结果就是消除了代码之间的依赖性，提高了对象的内聚性，使封装后的代码对其他行为的依赖性较小。

.消除冗余代码。例如，将一个变量赋给它自己，初始化或设置一个变量后却从不使用它，等等。研究表明，即使是无害的冗余也往往和程序的缺陷高度关联。

.减少实时代码。实时代码不但容易出错、编写成本较高，而且调试成本可能更高。如果可能，最好将对执行时间要求严格的代码转移到一个单独的任务或者程序段中。

.编写优雅流畅的代码。

.遵守代码编写标准并借助检查工具。用自动检验工具寻找缺陷比人工调试便宜，而且能捕捉到通过传统测试检查不到的各种问题。

编码技术

编程规范

在嵌入式软件开发过程中，遵守编程规范，养成良好的编程习惯，这是非常重要的，将直接影响到所编写代码的质量。

编程规范主要涉及的三方面内容：

.命名规则。从编译器的角度，一个合法的变量名由字母、数字和下画线三种字符组成，且第一个字符必须为字母或下画线。但是从程序员的角度，一个好的名字不仅要合法，还要载有足够的信息，做到“见名知意”，并且在语意清晰、不含歧义的前提下，尽可能地简短。

.编码格式。在程序布局时，要使用缩进规则，例如变量的定义和可执行语句要缩进一级，当函数的参数过长时，也要缩进。另外，括弧的使用要整齐配对，要善于使用空格和空行来美化代码。例如，在二元运算符与其运算对象之间，要留有空格；在变量定义和代码之间要留有空行；在不同功能的代码段之间也要用空行隔开。

.注释的书写。注释的典型内容包括：函数的功能描述；设计过程中的决策，如数据结构和算法的选择；错误的处理方式；复杂代码的设计思想等。在书写注释时要注意，注释的内容应该与相应的代码保持一致，同时要避免不必要的注释，过犹不及。

性能优化

由于嵌入式系统对实时性的要求较高，因此一般要求对代码的性能进行优化，使代码的执行速度越快越好。以算术运算为例，在编写代码时，需要仔细地选择和使用算术运算符。一般来说，整数的算术运算最快，其次是带有硬件支持的浮点运算，而用软件来实现的浮点运算是非常慢的。因此，在编码时要遵守以下准则：

.尽量使用整数（char、short、int和long）的加法和减法。

.如果没有硬件支持，尽量避免使用乘法。

.尽量避免使用除法。

.如果没有硬件支持，尽量避免使用浮点数。

下图是一个例子，其中两段代码的功能完全一样，都是对一个结构体数组的各个元素进行初始化，但采用两种不同的方法来实现。下图（a）采用数组下标的方法，在定位第i个数组元素时，需要将i乘以结构体元素的大小，再加上数组的起始地址。下图（b）采用的是指针访问的方法，先把指针fp初始化为数组的起始地址，然后每访问完一个数组元素，就把fp加1，指向下一个元素。在一个奔腾4的PC上，将这两段代码分别重复10 700次，右边这段代码需要1ms，而左边这段代码需要2.13ms。

算术运算性能优化的例子

数据通信

通信或数据传输是计算机网络的主要功能之一，用以在计算机系统之间传送各种信息。利用该功能，地理位置分散的生产单位和业务部门可通过计算机网络连接在一起进行集中控制和管理；或将一个大的项目由分散在不同地理位置的生产单位和业务部门分别处理，实现分布式处理；通过数据通信，也可以实现数据信息的远程传输，实现电子邮件的传送，发布新闻消息和进行电子数据交换，极大地方便了用户，提高了工作效率。

校验码

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

奇偶校验码

奇偶校验码用于并行码的检错。其原理是：在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）码。

循环冗余校验码

这种方式已经被广泛地在网络通信及磁盘存储时采用，所以在历年考试中出现的概率也比较大。先看几个基本概念。

在循环冗余校验码（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的突发错误。使用循环冗余校验码能用很少的校验码检测出大多数的错误，检错能力是非常强的，这是它得到了广泛应用的原因。

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

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