一、概要

1、数据的表示：数制及其转换、原码、反码、补码、移码、浮点数、溢出、算术运算、逻辑运算、校验码。

2、计算机系统的组成、体系结构分类及特性：CPU、存储器的组成、性能和基本工作原理、常用I/O设备、通信设备的性能及基本工作原理、I/O接口的功能、类型和特性、CISC/RISC、流水线操作、多处理机、并行处理。

3、存储系统：虚拟存储器基本工作原理、多级存储体系、RAID类型和特性。

4、可靠性与系统性能评测：诊断与容错、系统可靠性分析评价、校验方法、计算机系统性能评测方法。

                                二、数据表示

        数据的表示部分包含了数据转换、原码、反码、补码、移码以及浮点运算知识。其中难点是浮点计算。

1、数制转换

（1）R进制数转换成十进制数

      R进制数转换成十进制数通常使用按权展开法。具体操作方式为：将R进制数的每一位数值用Rk形式表示，即幂的底数是R，指数为k，k与该位和小数点之间的距离有关。当该位位于小数点左边，k值是该位和小数点之间数码的个数，而当该位位于小数点右边，k值是负值，其绝对值是该位和小时点之间数码的个数加1.

     例如二进制数l0100.01的值可计算如下:

按照上面的表示法，即可计算出R进制数十进制的值。

（2）十进制数转换为R进制数

最常用的是“除以R取余法”，如将十进制94转换为二进制数：

将所得的余数从低位到高位排列（1011110）2 就是94的二进制数。

(3)二进制数与八进制数、十六进制数之间的转换

二进制转八进制：将每3个二进制数转换为八进制数；

二进制转十六进制：将每4个二进制数转换为十六进制数；

八进制转二进制：将每个八进制数转换为3位二进制数；

十六进制转二进制；将每个十六进制数转换为4位二进制。

        上面的转换都是以小数点作为计数码个数的起点。八进制数和十六进制数转换，可先转换为二进制数，然后再转换为目标进制。

2、原码、反码、补码、移码

在计算机中，数据编码方式可以有多种，最为常见的有原码、反码、补码、移码。一个正数的原码、反码、补码是相同的，负数则不同。

（1）原码

将最高位用做符号位（0表示正数，1表示负数），其余各位代表数值本身的绝对值的表示形式。这种方式是最容易理解的。

例如,+1 的原码是0000 0001,–1 的原码是1000 0001.

但是直接使用原码在计算时却会有麻烦，比如（1）10 + （-1）10 = 0，如果直接使用原码则：

这样计算的结果是-2，也就是说，使用原码直接参与计算可能会出现错误的结果。所以，原码的符号位不能直接参与计算，必须和其他位分开，这样会增加硬件的开销和复杂性。

（2）反码

正数的反码与原码相同。负数的反码符号位为1，其余各位为该数绝对值的原码按位取反。这个取反的过程使得这种编码称为“反码”。

例如,–1的反码:1111 1110 。

 同样对上面的加法,使用反码的结果是:

这样的结果是负0，而在人们普遍的观念中，0是不分正负的。反码的符号位可以直接参与计算，而且减法也可以转换为加法计算。

（3）补码

正数的补码与原码相同。负数的补码是该数的反码加1，这个数加1救赎“补”。

例如,–1的补码:1111 1110+1 = 1111 1111。

再次做加法是这样的:

直接使用补码进行计算的结果是正确的。

对一个补码表示的数，要计算其原码，只要对它再次求补，可得该数的原码。

由于补码能使符号位与有效值部分一起参加运算，从而简化运算规则，同时它也使减法运算转换为加法运算，进一步简化计算机中运算器的电路，这使得在大部分计算机系统中，数据都使用补码表示。

（3）移码

移码是对补码的符号位取反得到的一种编码。移码只用于表示浮点数的阶码，所以只用于整数。例如，-1的移码为:0111 1111.

3、浮点数计算

在数学中，要表示一个很大的数时，我们常常使用一种称为科学计数法的方式：

                                                     N = M * Re

其中M称为尾数，e是指数，R为基数。

浮点数就是使用这种方法来表示大范围的数，其中指数一般是2，8，16。而且对于特定机器而言，指数是固定不变的，所以在浮点数中指数并不出现。从这个表达式可以看出：浮点数表示的精度取决于尾数的宽度，范围取决于基数的大小和指数的宽度。

浮点数的运算主要有三个步骤：对阶、尾数计数、结果格式化。

（1）对阶

首先计算两个数的指数差，把指数小的向指数大的对齐，并将尾数右移指数差的位数，这样两个浮点数就完成了对阶的操作。可以看出，对阶的过程可能使得指数小的浮点数失去一些有效位。如果两个浮点阶数相差很大，大于指数小的浮点数的位数宽度，那么对阶后那个浮点数的位数就变成了0，即当做机器零处理了。

（2）尾数计算

对阶完成后，两个浮点数尾数就如同定点数，计算过程同定点数计算。

（3）结构格式化

尾数计算后，可能会产生溢出，此时将尾数右移，同时指数加1，如果指数加1后发生了溢出，则表示两个浮点数的运算发生了溢出。

如果尾数计算没有溢出，则尾数不断左移，同时指数减1，直道尾数为格式化数。如果这个过程中，指数小于机器能表达的最小数，则将结果置“机器零”，这种情况称为下溢。

                    三、计算机系统的组成与体系结构

        在计算机系统的组成与体系结构中，计算机体系结构分类、指令系统基数、CISC与RISC、流水线操作等内容是最为重要的。

1、计算机体系结构分类

计算机体系结构分类有多种方式，其中最为常见的是：FLynn分类法与冯氏分类法。

Flynn 分类法是根据指令流、数据流和多倍性三个方面来进行分类的：

2、计算机的硬件组成

计算机硬件系统由运算器、控制器、存储器、输入设备和输出设备五大部件组成。其中运算器和控制器组成中央处理器（CPU）。运算器负责完成算术、逻辑运算功能，通常由ALU（算术/逻辑单元）、寄存器、多路转换器、数据总线组成；控制器则负责依次访问程序指令，进行指令译码，并协调其他设备，通常由计数器（PC）、指令寄存器、指令译码器、状态/条件寄存器、时序发生器、微操作信号发生器组成。

3、指令系统基础

在计算机中，CPU都会定义出自己特定的指令系统，不过都遵循着统一的标准格式。指令的基本格式是由操作码和地址码两个部分组成的。操作码指出该指令要完成什么操作，地址码是提供原始的数据。指令系统中定义操作码的方式可以分为规整型（定长编码）和非规整型（变长编码）两种，如表：

而在指令系统中用来确定如何提供操作或提供操作数地址的方式称为寻址方式和编址方式。操作数可以存放在CPU中的寄存器（用寄存器名操作）、主存储器（指出存储单元地址）、堆栈（先进后出的存储机制，用栈顶指针SP来标出其当前位置）、外存器或外围设备中。不过在运算时，数据均在主存储器中，操作数可以采用以下几种寻址方式：

（1）隐含寻址方式

在指令中不明显地给出而是隐含着操作数的地址。例如，单地址的指令格式，没有在地址字段中指明第二操作数地址，而是规定累加寄存器AC作为第二操作数地址，AC对单地址指令格式来说是隐含地址。

（2）立即寻址方式

指令的地址字段指出的不是操作数的地址，而是操作数本身。这种方式的特点事指令执行时间很短，不需要访问内存取数。“操作数包含在指令中寻址方式”就是立即寻址。

如，单地址的移位指令格式为

这里D不是地址，而是一个操作数。F为标志位，当F = 1 时，操作数进行右移；当F = 0时，操作数进行左移。

（3）直接寻址

特点是：在指令格式的地址字段中直接指出操作数在内存的地址D。

采用直接寻址方式时，指令中的形式地址D就是操作数的有效地址E，即E = D。因此通常把形式地址D又称为直接地址。此时，由寻址模式给予指示。如果用S表示操作数，那么直接寻址的逻辑表达式为S = (E) = (D).

(4)间接寻址方式

间接寻址的情况下，指令地址字段中的形式地址D不是操作数的真正地址，而是操作数地址的指示器，D单元的内容才是操作数的有效地址。

如果把直接寻址和间接寻址结合起来，指令有如下形式：

寻址特征位 I = 0,表示直接寻址，这时有效地址 E = D; I = 1，表示间接寻址，这时有效地址

E = (D).

间接寻址方式是早期计算机中经常采用的方式，但由于两次访问内存，影响指令执行速度，现在已不大使用。

(5) 寄存器寻址方式和寄存器间接寻址方式

       当操作数不放在内存中,而是放在CPU的通用寄存器中时,可采用寄存器寻址方式。此时指令中给出的操作数地址不是内存的地址单元号,而是通用寄存器的编号。这也就是所说的"操作数在寄存器中的寻址方式".

         寄存器间接寻址方式与寄存器寻址方式的区别在于:指令格式中的寄存器内容不是操作数,而是操作数的地址,该地址指明的操作数在内存中。这也就是所说的"操作数的地址在寄存器中的寻址方式".

(6) 相对寻址方式 

        相对寻址是把程序计数器PC的内容加上指令格式中的形式地址D而形成操作数的有效地址。程序计数器的内容就是当前指令的地址。"相对"寻址,就是相对于当前的指令地址而言的。  采用相对寻址方式的好处是程序员无须用指令的绝对地址编程,所编程序可以放在内存任何地方。此时形式地址D通常称为偏移量,其值可正可负,相对于当前指令地址进行浮动。

(7) 基址寻址方式

         基址寻址方式是将CPU中基址寄存器的内容加上指令格式中的形式地址而形成操作数的有效地址。它的优点是可以扩大寻址能力。与形式地址相比,基址寄存器的位数可以设置得很长,从而可以在较大的存储空间中寻址。

(8) 变址寻址方式

       变址寻址方式与基址寻址方式计算有效地址的方法很相似,它把CPU中某个变址寄存器的内容与偏移量D相加来形成操作数有效地址。但使用变址寻址方式的目的不在于扩大寻址空间,而在于实现程序块的规律性变化。

4. CISC与RISC

为了提高操作系统的效率,人们最初选择了向指令系统中添加更多、更复杂的指令,而随着不断地升级和向后兼容的需要,指令集也越来越大。这种类型的计算机,我们称之为复杂指令计算机CISC.而后来研究发现,计算机指令系统如果使用少量结构简单的指令会提高计算机的性能,这就是精简指令集计算机RISC.计算机执行程序所需的时间P由三方面因素决定:编译后产生的机器指令数I、执行每条指令所需的平均周期数CPI,以及每个机器周期的时间T.它们的关系是P=I x CPI x T.RISC正是通过简化指令的途径使计算机结构更合理,减少指令执行周期数,提高运算速度。虽然RISC编译后产生的机器指令数(I)增多了,但指令所需的周期数(CPI)和每个周期的时间(T)都可以减少。它与CISC可谓各有特色,如表1-5所示。

        典型的RISC处理器包括:DEC的Alpha 21164、IBM的Power PC620、HP的PA-8000、SGIMIPS分部的TS、Sun的Ultra SPARC.目前RISC处理器技术的发展方向是采用并行处理技术(包括超级流水线、超级标量、超长指令字)大幅度提高运算速度。

5. 流水线

        流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的,它们可同时为多条指令的不同部分进行工作,以提高各部件的利用率和指令的平均执行速度。

        指令流水线是将指令执行分成几个子过程,每一个子过程对应一个工位,我们称为流水级或流水节拍,这个工位在计算机里就是可以重叠工作的功能部件,称为流水部件。

如图1-2所示,IF,ID,EX,WD分别是流水线的流水部件。

       流水线要求所有的流水级部件必须在相同的时间内完成各自的子过程。在流水线中,指令流动一步便是一个机器周期,机器周期的长度必须由最慢的流水级部件处理子过程所需的时间来决定。

     那么我们为什么要提出流水线这个概念,以及流水线是如何提高系统吞吐量的呢?下面我们来看几个图,概念自然就清楚了。

图1-3是一个非流水线结构系统执行指令时空图。

显然,采用流水线可以大大提升系统资源的利用率,以及整个系统的吞吐量。

(1)计算流水线执行时间

       假定有某种类型的任务,共可分成N个子任务,执行每个子任务需要时间t,则完成该任务所需的时间即为Nt.若以传统的方式,则完成k个任务所需的时间是kNt;而使用流水线技术执行,花费的时间是Nt+(k-1)t.也就是说,除了第一个任务需要完整的时间外,其他都通过并行,节省下了大量的时间,只需一个子任务的单位时间就够了。

     另外要注意的是,如果每个子任务所需的时间不同,则其速度取决于其执行顺序中最慢的那个(也就是流水线周期值等于最慢的那个指令周期),要根据实际情况进行调整。

      例如:若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的时间分别是取指2ns,分析2ns,执行1ns.那么,最长的是2ns,因此100条指令全部执行完毕需要的时间就是:(2ns+2ns+1ns) +(100-1)x 2ns=203ns.

      另外,还应该掌握几个关键的术语:流水线的吞吐率(等于任务数/完成时间),加速比(不采用流水线的执行时间/采用流水线的执行时间)

(2)影响流水性的主要因素

        如图1-4所示,流水线的关键在于"重叠执行",因此如果这个条件不能够满足,流水线就会被破坏。这种破坏主要来自两种情况:

转移指令:因为前面的转移指令还没有完成,流水线无法确定下一条指令的地址,因此也就无法向流水线中添加这条指令。从这里的分析可以看出,无条件跳转指令是不会影响流水线的。

共享资源访问的冲突:也就是后一条指令需要使用的数据,与前一条指令发生的冲突,或者相邻的指令使用了相同的寄存器,这也会使得流水线失败。

响应中断:当有中断请求时,流水线也会停止。对于这种情况有两种响应方式,一种是立即停止--精确断点法,能够立即响应中断;另一种是流水线中的指令继续执行,不再新增指令到流水线--不精确断点法。

                                     四、存储系统

   在整个计算机系统中,存储系统的地位非常重要。

1.Cache  

由于在CPU与存储系统间存在着数据传送带宽的限制,因此在其中设置了Cache(高速缓冲存储器,通常速度比内存快),以提高整体效率。但由于其成本更高,因此Cache的容量要比内存小得多。

(1) Cache原理、命中率、失效率

      使用Cache改善系统性能的主要依据是程序的局部性原理。通俗地说,就是一段时间内,执行的语句常集中于某个局部。而Cache正式将访问集中的内容放在速度更快的Cache上,以提高性能。引入Cache后,CPU在需要数据时,先找Cache,如果没有再找内存。

     如果Cache的访问命中率为h(通常1-h就是Cache的失效率),而Cache的访问周期时间是t1,主存储器的访问周期时间是t2,则整个系统的平均访存时间就应该是:

                                                  t3=h*t1+(1-h)* t2

         从公式可以看出,系统的平均访存时间与命中率有着很密切的关系。灵活地应用这个公式,可以计算出所有情况下的平均访存时间。

例如:设某流水线计算机主存的读/写时间为100ns,有一个指令和数据合一的Cache,已知该Cache的读/写时间为10ns,取指令的命中率为98%,取数的命中率为95%.在执行某类程序时,约有1/5指令需要存/取一个操作数。假设指令流水线在任何时候都不阻塞,则设置Cache后,每条指令的平均访存时间约为多少?其实这是应用该公式的简单数学题:

                  (2%*100ns + 98%*10ns)+ 1/5 x(5%*100ns + 95%*10ns)=14.7ns

(2)Cache存储器的映射机制

      CPU发生访存请求时,会先让Cache判断是否包括,如果命中(即包括请求的内容)就直接使用。这个判断的过程就是Cache地址映射,这个速度应该尽可能快,常见的映射方法有直接映射、全相联映射和组相联映射三种,其原理如图1-5所示。

 直接映射:是一种多对一的映射关系,但一个主存块只能够复制到Cache的一个特定位置上去。Cache的行号i和主存的块号j有函数关系:i=j%m(其中m为Cache总行数)。例如:某Cache容量为16KB(可用14位表示),每行的大小为16B(可用4位表示),则说明其可分为1024行(可用10位表示)。则主存地址的最低四位为Cache的行内地址,中间10位为Cache行号。如果内存地址为1234E8F8H的话,那么最后四位就是1000(对应16进制数的最后一位),而中间10位,则应从E8F(111010001111)中获取,得到1010001111。

相联映射:将主存中一个块的地址与块的内容一起存于Cache的行中。速度更快,但控制复杂。

组相联映射:是前两种方式的折中方案。它将Cache中的块再分成组。然后通过直接映射方式决定组号,再通过相联映射的方式决定Cache中的块号。

要注意的是,在Cache映射中,主存和Cache存储器将均分成容量相同的块。

例如:容量为64块的Cache采用组相联方式映像,字块大小为128个字,每4块为一组。若主存容量为4096块,且以字编址,那么主存地址应该为多少位?主存区号为多少位?这样的题目,首先根据主存与Cache块的容量需一致,因此内存也是128个字,因此共有12*4096个字,即219(27+212)个字,因此主存地址需要19位;而内存所需要分为4096/64块,即26,因此主存区号需要6位。

(3)Cache淘汰算法

当Cache数据已满,并且出现未命中情况时,就是淘汰一些老的数据,更新一些新的数据。而选择淘汰什么数据的方法就是淘汰算法,常见的方法有三种:随机淘汰、先进先出(FIFO)淘汰(淘汰最早调入Cache的数据)、最近最少使用(LRU)淘汰法。其中平均命中率最高的是LRU算法。

(4)Cache存储器的写操作

在使用Cache时,需要保证其数据与主存一致,因此在写Cache时就需要考虑与主存间的同步问题,通常使用以下三种方法:写直达(写Cache时,同时写主存)、写回(写Cache时不马上写主存,而是等其淘汰时回写)、标记法。

2. 主存(内存)

(1)主存储器的种类

RAM:随机存储器,可读写,断电后数据无法保存,只能暂存数据。

SRAM:静态随机存储器,在不断电时信息能够一直保持。  

DRAM:动态随机存储器,需要定时刷新以维持信息不丢失。  

ROM:只读存储器,出厂前用掩膜技术写入,常用于存放BIOS和微程序控制。  

PROM:可编程ROM,只能够一次写入,需用特殊电子设备进行写入。

  EPROM:可擦除的PROM,用紫外线照射15~20分钟可擦去所有信息,可写入多次。 

 E2PROM:电可擦除ERPOM,可以写入,但速度慢。  

闪速存储器:现在U盘使用的种类,可以快速写入。  

           记忆时,抓住几个关键英文字母。A,即Access,说明读写都行;O,即Only,说明只读;P,即Programmable,说明可通过特殊电子设备写入;E,即Erasable,说明可擦写;E平方说明是两个E,第二个E是电子。

(2)主存储器的组成

          实际的存储器总是由一片或多片存储器配以控制电路构成的(如图1-6所示)。其容量为WxB,W是存储单元(word,即字)的数量,B表示每个word由多少bit(位)组成。如果某一芯片规格为w?b,则组成W?B的存储器需要用(W/w)x(B/b)个芯片。

(3)主存储器的地址编码

        主存储器(内存)采用的是随机存取方式,需对每个数据块进行编码,而在主存储器中数据块是以       word来标识的,即每个字一个地址,通常采用的是16进制表示。例如,按字节编址,地址从A4000H到CBFFFH,则表示有(CBFFF-A4000)+1个字节,28000H个,也就是163840个字节,等于160KB.

          要注意的是,编址的基础可以是字节,也可以是字(字是由1个或多个字节组成的),要算地址位数,首先应计算要编址的字或字节数,然后求2的对数即可得到。

                       五、可靠性与系统性能评测

1. 可靠性计算

      可靠性计算主要涉及三种系统,即串联系统、并联系统和冗余系统,其中串联系统和并联系统的可靠性计算都非常简单,只要了解其概念,公式很容易记住。冗余系统要复杂一些。

(1)串联系统

假设一个系统由n个子系统组成,当且仅当所有的子系统都能正常工作时,系统才能正常工作,这种系统称为串联系统,如图1-7所示。

设系统各个子系统的可靠性分别用表示,则系统的可靠性:

如果系统的各个子系统的失效率分别用来表示,则系统的失效率:

(2)并联系统

       假如一个系统由n个子系统组成,只要有一个子系统能够正常工作,系统就能正常工作,如图1-8所示。

设系统各个子系统的可靠性分别用 R1,R2...Rn表示,则系统的可靠性

R = 1 - (1 - R1) x (1 - R2) x ... x (1 - Rn)

假如所有子系统的失效率均为l,则系统的失效率为μ:

      在并联系统中只有一个子系统是真正需要的,其余n-1个子系统都被称为冗余子系统。该系统随着冗余子系统数量的增加,其平均无故障时间也会增加。

(3)模冗余系统

m模冗余系统由m个(m=2n+1为奇数)相同的子系统和一个表决器组成,经过表决器表决后,m个子系统中占多数相同结果的输出可作为系统的输出,如图1-9所示。

在m个子系统中,只有n+1个或n+1个以上的子系统能正常工作,系统就能正常工作并输出正确结果。假设表决器是完全可靠的,每个子系统的可靠性为R0,则m模冗余系统的可靠性为:

2.系统性能评价

      无论是生产厂商还是用户,都需要某种方法来衡量计算机系统的性能,但由于系统很复杂、体系结 构和实现的策略多样,因此很难采用统一的标准去评测所有的计算机。

(1)常用方法

时钟频率:即主频(常听到的CPU主频1.8GHz等),通常主频越高,速度越快。但这种比较只能够在相同体系结构的机器上比较,对于异构系统而言,难以保证其有效性。

指令执行速度:在早期,我们经常使用每秒执行的加法指令(由于当时各种指令的速度大致相同或等比例)总数来作为衡量其性能的重要指标,其单位为KIPS(每秒千条指令)、MIPS(每秒百万条指令)。

等效指令法:随着计算机指令系统的发展,使用单种指令的MIPS值的局限性日益暴露,后来就出现了改进的吉普森混合指令速度法。它通过统计各类指令在程序中所占的比例,进行折算。

数据处理速率(PDR)法:它采用固定的比例法来计算数据处理的速度,而且还仅对CPU和主存的速度进行度量,因此有很大的局限性。

核心程序法:把应用程序中用得最频繁的那部分核心程序作为评价计算机性能的标准程序,在不同机器上运行,测其执行时间,作为各类机器性能评价的依据。

(2)基准测试程序  

基准程序法是目前一致承认的测试性能较好的方法,有多种不同的基准程序,用于不同的测试项目。 

 整数测试程序:Dhrystone是一个用来测试编译器和CPU处理整数指令和控制功能有效性的基准测试程序。  

浮点测试程序:在计算机科学和工程应用领域,浮点计算工作量占很大比例,因此有许多此类基准测试程序。  

理论峰值浮点速度:MELOPS,与处理器时钟周期、并行流水线功能部件数相关,是直接计算出来的理论值。

Linpack基准测试程序:主要测试向量性能和高速缓存性能。

Whetstone基准测试程序:综合性测试程序,除测试浮点操作外,还测试整数计算和功能调用等性能。

SPEC基准程序:是由几十家世界知名计算机大厂商支持的非盈利的合作组织,开发共同认可的标准基准程序。

TPC基准程序:是事务处理委员会编写的,共包括TPC-A,TPC-B,TPC-C,TPC-D和TPC-E五种,每一种都有一定的适用范围。

3.校验码

       为了实现数据的自动检错与纠错,引入了校验码。而最简单的就是奇偶校验码,它分为奇校验和偶校验两种,均是添加1位校验位,根据信息码中1的个数来决定校验位的取值,使得填入校验位后,使得1的个数为奇数(奇校验)或偶数(偶校验)。这方面知识更深入的考察点主要包括以下几个方面:

(1)海明码距

      海明的冗余数据位检测和纠正代码差错的理论和方法指出:可以在数据代码上添加若干冗余位组成码字。而将一个码字变成另一个码字时必须改变的最小位数就是码字之间海明距离,简称码距。从这里将得出:没有加冗余校验码的任何编码,它们的码距就是1,即只要改一位,就可以变成另一个码字了;而奇偶校验码则添加了1位校验码,使得要变成另一个码字最少要修改两位,这就使其码距变成2了;根据定义得知,码距是不同码字的海明距离的最小值。判断码距时,可以列出一些码进行判断,找出最小的位数即可。

     另外,还需要记住以下几个关键的关系:

    可查出多少位错误:根据海明的研究发现,可以发现"≤码距-1"位的错误。  

    可以纠正多少位错误:根据海明的研究发现,可以纠正"<码距/2"位的错误,因此如果要能够纠正n位错误,则所需最小的码距应该是"2n+1".

(2)海明校验码

要计算海明校验码,首先要知道海明校验码是放置在2的幂次位上的,即"1、2、4、8、16、32......",而对于信息位为m的原始数据,需加入k位的校验码,它满足m+k+1<2k.计算时总令人感到头痛。而有一种简单的方法,则是从第1位开始写,遇到校验位留下空格。例如:原始信息为101101100,并采用偶校验则:

然后根据以下公式填充校验位"1、2、4、8":

Bit 1=B3 B5 B7 B9 B11 B13 = 1 0 1 0 1 0 =1

Bit 2=B3 B6 B7 B10 B11 = 1 1 1 1 1 =1

Bit 4=B5 B6 B7 B12 B13 = 0 1 1 0 0 =0

Bit 8=B9 B10 B11 B12 B13 = 0 1 1 0 0=0

(注:?指的是异或运算;Bn代表位数)

然后将结果填入,得到:

而如果给出一个加入了校验码的信息,并说明有一位错误,要找出,则可以采用基本相同的方

法,假如给出的是:

可根据以下公式计算:

Bit 1=B1 B3 B5 B7 B9 B11 B13 = 1 1 0 1 0 0 0 =1

Bit 2=B2 B3 B6 B7 B10 B11 = 1 1 1 1 1 0 =1

Bit 4=B4 B5 B6 B7 B12 B13 = 0 0 1 1 0 0 =0

Bit 8=B8 B9 B10 B11 B12 B13 =0 0 1 0 0 0=1

      然后从高位往下写,得到1101,即十进制的11,因此出错的位数为第11位。而剩下的问题就是这个公 式如何来的?首先计算校验码时,1、2、4、8位都是空的,因此在公式的左边;当进行校验时,1、2、4、8位都已经有值,因此要参与计算。而这些值是根据右表得到的,也就是生成B1、B2、B4、B8四个公式,而公式中要参与计算的位,是在表格中出现"1"的那个位。要说明的是,右边的表格,就是对数据位的二进制描述。

      由于海明码距在计算和纠错过程中,计算都过于复杂,无法很容易地使用硬件实现,因此在实际的应用中并不是应用得很广泛。

(3)CRC校验码

由于CRC的实现原理十分易于用硬件实现,因此被广泛地应用于计算机网络上的差错控制。而CRC的考察点主要有两个:计算CRC校验码;验算一个加了CRC校验的码是否有错误。

计算CRC校验码

    要计算CRC校验码,需根据CRC生成多项式进行。例如:原始报文为"11001010101",其生成多项式为:"x4+x3+x+1".在计算时,是在原始报文的后面若干个0(等于校验码的位数,而生成多项式的最高幂次就是校验位的位数,即使用该生成多项式产生的校验码为4位)作为被除数,除以生成多项式所对应的二进制数(根据其幂次的值决定,得到11011,因为生成多项式中除了没有x2之外,其他位都有)。然后使用模2除,得到的商就是校验码。

然后将0011添加到原始报文的后面就是结果:110010101010011。

检查信息码是否有CRC错误

要想检查信息码是否出现了CRC错误的计算很简单,只需用待检查的信息码做被除数,除以生成多项式,如果能够整除就说明没有错误,否则就是出错了。另外要注意的是,当CRC检查出现错误时,它是不会进行纠错的,通常是让信息的发送方重发一遍。