信息系统管理工程师考点分析与真题详解

1、信息系统管理工程师考点分析与真题详解第1章计算机科学基础计算机科学是一门包含各种各样与计算和信息处理相关主题的系统学科，从抽象的算法分 析、形式化语法，到具体的如编程语言、程序设计、软件和硬件。作为一门学科，它与数学、 计算机程序设计、软件工程和计算机工程有显着的不同，却通常被混淆，尽管这些学科之间存 在不同程度的交叉和覆盖。根据信息系统管理工程师考试大纲与历年试题分布，本章重点讲述：数制及转换二进制、十进制和十六进制等常用数制及其相互转换数据的表示数的表示：原码、补码、发码，整数和实数的机内表示方法，精度与溢出非数值表示：字符和汉字的机内表示，声音和图像的机内表示校验方法和校验编码算术运算和

2、逻辑运算计算机中二进制的运算方法逻辑代数基本运算数据结构与算法基本概念历年真题详解与模拟题1.1数制及转换1.1.1 数制按进位的原则进行计数，称为进位计数制，简称"数制"或"进制”.在日常生活中经常要用到数制，通常以十进制进行计数，除了十进制计数以外，还有许多非十进制的计数方法。例如，60分钟为1小时，用的是60进制计数法；1星期有7天，是7进制计数法；1年有12个月, 是12进制计数法。当然，在生活中还有许多其他各种各样的进制计数法。在计算机系统中采用二进制，其主要原因是由于电路设计简单、运算简单、工作可靠、逻辑性强。不论是哪一种数制，其计数和运算都有共同的规

3、律和特点。人们最熟悉的是十进制数，但在计算机中，采用二进制数"0"和"1"可以很方便的表示机内的数据与信息。在计算机系统中采用二进制，其主要原因是由于电路设计简单、运算简单、工作可靠、逻辑性强。不论是哪一 种数制，其计数和运算都有共同的规律和特点。1 .十进制数我们熟悉的十进制数有两个主要特点：有十个不同的数字符号：0、1、2、9;低位向高位进、彳t位的规律是“逢十进一"、"借一当十”的计数原则进行计数。例如：L234一5alM1后+ "1乎+3乂加】+ 4乂103+5乂1(?1 + 5乂10'；式中的0称为十进制数

4、的基数1印、 IO1，称为各数位的权-十进制数用D结尾表示口2 .二进制数在二进制中只有两个不同数码：0和1,进位规律是"逢二进一"、"借一当二”的计数原则进行计数。二进制数用 B结尾表示。例如，二进制数1101101L01可表示为(11。11011一01卜k27+1><2s+0心5+1*2*+以/ + 0><宠+卜2】+ 1x20 + 0x2-+1x2'3 .八进制数在八进制中有0、1、2、7八个不同数码，采用"逢八进一"、"借一当八”的计数原则进行 计数。八进制数用 Q结尾表示。例如，八进制数(50

5、3.04可表示为(503.04)q=5汗7)父加-3乂即7Ms44 .十六进制数在十六进制中有 0、1、2、9、A、B、C、D、E、F共十六个不同的数码，采用 "逢十六 进一"、"借一当十六"的计数原则进行计数。十六进制数用H结尾表示。例如十六进制数(AE9.27) h可表示为(4EQ.27)日=4k6+14*161 4 9乂6"拄16" +我16工5 .1.2 数制之间的转换将数由一种数制转换成另一种数制称为数制间的转换。由于计算机采用二进制，但用计算 机解决实际问题时对数值的输入输出通常使用十进制，这就有一个十进制向二进制转换或由

6、二 进制向十进制转换的过程。也就是说，在使用计算机进行数据处理时首先必须把输入的十进制 数转换成计算机所能接受的二进制数；计算机在运行结束后，再把二进制数转换为人们所习惯 的十进制数输出。下面是数制之间的转化方法：1 .二、八、十六进制转十进制的方法：乘权相加法。例如：(11。1。110淬1父寸一工乂2#-0,23-1¥2#刊翼23个1，2二1乂21-。内：=(214)结(2365>=2x83xS5x81+5xS0=(19)ia(4BFL4x141146415x160-(1215)10带小数的情况：(H0.011)：=lx22-hlx21-lx2X2-U1x2-2+lx2-3-

7、 (5.375)14(5 76斤> 叙+7对吩虾=(5 .皎75) io(D.lC)if= 13x161x16-12x16=(13.1093 75)ij2 .十进制化二进制的方法：整数部分除二取余法，小数部分乘二取整法。图1-1所示为整数部分除二取余过程，(43)10= (101011 ) 2.图1-2所示为小数部分乘二取整过程,(0.375 ) 10=(0.011 ) 2.图1-1整麴部分除二取余法0 375乘二型整法乂 2 0750 0乂 20.500 1乂 2 0 000 1表1-3各种进位制的对应关系图i二小数部分乘二取整法3 .二进制转八进制的方法二进制转八进制的方法，是对二进

8、制以小数点为分隔，往前往后每三位划为一组，不足三 位补0,按表1-1用对应的八进制数字代入即可。例如：(10111如1.01100111) =010,111,011.011,001,110=(273.316 ) 8皿二姗00001001I2010S01141005101611071114 .二进制转十六进制的方法二进制转十六进制的方法，是对二进制以小数点为分隔，往前往后每四位划为一组，不足 四位补0,按表1-2用对应的十六进制数字代入即可。例如：(1011101001100111) =1011,1011.0110,0111=(BB.67) 16表1-2 1位数十六进制与二进制对应表J AKW二

9、的00000J00012001030011401005010160110T01118100091001A101。BW11C上侬D1101E1110F1111表1-3列出了二、八、十、十六进制数之间的对应关系，熟记这些对应关系对后续内容的 学习会有较大的帮助。AatwtA3!«Q0Q09100111111110ID10*2LO2211lOlt13B31133?1100!<C41004413110115r1.2数据的表示1 .2.1数的表示2 .常用数值编码由于机器数在计算时，如果符号位和数值位同时参与运算，则可能会产生错误结果；而如 果单独考虑符号问题，又会增加运算器件的实现难度

10、。因此，为了使计算机能够方便地对数值 进行各种算术逻辑运算，必须对数值型数据进行二进制编码处理。所谓编码是采用少量的基本 符号（如0和1 ）,按照一定的组合原则，来表示大量复杂多样信息的技术。编码的优劣直接影 响到计算机处理信息的速度。数值型数据的常用编码方法包括：原码、反码和补码。原码原码的编码规则是：符号位0表示正，1表示负，数值部分用该数绝对值的二进制数表示。当整数时，小数点隐含在最低位之后；当纯小数时，小数点隐含在符号位和数值位之间，均不 占位，通常用X原表示数X的原码。例如，设机器字长为 8位，+1原=00000001 +127 原=01111111 +0 原=00000000-1原

11、=10000001 -127 原=11111111 -0 原=10000000显然，按原码的编码规则，零有两种表示形式。原码表示法简明易懂，与其真值的转换方便，比较容易进行乘除运算。但是在进行加减运算时，原码运算很不方便。由于符号位不能和数值一样参与运算，所以要根据两数的符号情况，同号相加，异号相减，还要根据两数的绝对值大小，令大数减去小数，最后还要判断结果的符号。这样不仅要求运算器既能作加法，又能作减法，还必须附加许多条件判断的处理，最终既增加了运算器的实现复杂性，又延长了运算的时间。反码反码的编码规则是：符号位 0表示正，1表示负，正数的反码等于原码，负数的反码等于原码除符号位外按位取反，

12、即0变1,1变0.通常用X反表示数X的反码。例如，设机器字长为 8位。+1反=00000001+127反=01111111+0反=00000000-1反=11111110 -127反=10000000 -0 反=11111111显然，按反码的编码规则零也有两种表示形式。反码很容易由原码获得，但同样不方便运算，一般在求补码的过程中用到反码。补码补码的编码规则是：符号位 0表示正，1表示负，正数的补码等于原码，负数的补码等于反码末位加1.通常用X补表示数X的补码。例如，设机器字长为 8位，+1补=00000001 +127补=01111111 +0补=00000000-1补=11111111 -1

13、27补=10000001 -0 补=00000000显然，按补码的编码规则，零有唯一的表示形式。补码的概念来源于数学上的"模"和补数。例如，将钟表的时针顺时针拨快5小时和逆时针拨慢 7小时，最后指示的位置相同，则称 5和-7互为模12情况下的补数。计算机中机器数受机器字长限制，所以是有限字长的数字系统。对于整数来说，机器字长为n位（含符号位），模是2n;对于有符号纯小数来说，模是 2.求补运算通常利用反码来实现。例如，求 X=+1011,Y= -1101的原码，反码和补码。求解过程：X原=01011 Y原=11101凶反=01011 Y反=10010凶补=01011 Y 补

14、=10011采用补码进行加减运算十分方便。通过对负数的编码处理，允许符号位和数值一起参与运算，可以把减法运算转化为加法运算。不论求和求差，也不论操作数为正为负，运算时一律只做加法，从而大大简化运算器的设计，加快了运算速度。例如， （-9） + （-5）的运算如下：-9补=11110111 11110111-5补=11111011+11111011因为机器字长的限制，丢失高位1,运算结果机器数为11110010,是-14的补码形式。目前,由于计算机中最多的运算是加减运算，为了简化运算器设计，加快运算速度，有些计算机在数 值表示，存储，运算时均采用补码表示法，也有些计算机，数用原码进行存储和传送，

15、运算时 采用补码，还有些计算机在进行加减法时采用补码运算，而在进行乘除法时采用原码运算。2.整数和实数的机内表示方法在计算机内部，并不显式地表示出小数点，而是通过对小数点的位置加以规定来表示。所以，整数和实数在机内的表示是不同的。整数整数没有小数部分，因此可以认为小数点固定在数的最右边。整数可以分为无符号整数和有符号整数两类。无符号整数的所有二进制位全部用来表示数值的大小，常被用来表示计算机中的地址。有符号整数通常最高位表示数的正负号，而其他位表示数值的大小。一般把计算机能够直接处理的二进制位数称为机器字长。整数表示的数值是精确的，但可以表示的数值范围受机器字长的限制。现代计算机的机器字长一般

16、为8、16、32、64、128位等，每种情况可以表示的整数范围不同。实数在进行科学计算时，计算机处理更多的是实数。实数是既有整数部分又有小数部分的数，纯小数可看作实数的特例。因为实数可能很大或者很小，所以人们一般采用"浮点数表示法”来表示，即把一个实数的范围和精度用阶码和尾数两部分来分别表示。例如，0.3429 X 106，其中0.3429称为尾数，6称为阶码。由于阶码可以取不同数值，使得小数点的位置不固定，对于一个实数可以有多种表示形式，所以称为浮点数表示法。例如，十进制实数-12345.6789 可以表示为：-0.123456789 X105,-12.3456789 X103,-

17、12345.6789 X100,-1234567.89 X10 2.二进制的表示类似，例如， 1010.1011可表示为：10.101011 X210 ,101010.11 X2 -10,0.10101011 X2100.在计算机中，为了提高数据表示精度，必须唯一地规定小数点的位置，因此规定浮点数必须写成规格化的形式，即当尾数不为0时，其绝对值大于等于 0.5且小于1.尾数表示数值的有效数字，是纯小数，其位数将影响数的精度，其符号决定数的符号。阶码相当于数学中的指数，其大小用来指示尾数中的小数点应当向左或向右移动的位数，其位数将决定数的表示范围。在 浮点数表示中，数符和阶符通常各占一位，并且约

18、定小数点的位置在数符和尾数之间。一个浮点数的机内表示形式。3.精度和溢出现代数字计算机是有限字长的数字系统，机器数表示的范围受到机器字长和数据类型的限制，一旦机器字长和数据类型确定了，机器数所能表示的数的范围和精度也就确定了。所谓精度，是指可以给出的有效数字的位数。一般来说，机器字长越长，可以表示的数的范围越大，精度越高；当字长相同时，浮点数通常比整数可以表示的数的范围要大；浮点数表示时，阶码位数越多，可以表示的数的范围越大，尾数位数越多，可以表示的数的精度越高。如果一个数的大小超出了计算机所能表示的数的范围，则产生"溢出".如果两个正数相加，结果大于机器所能表示的最大正数

19、，称为"上溢”;如果两个负数相加，结果小于机器所能表示的最小负数，称为"下溢".例如，字长为n位的有符号整数，最高1位为符号位，数值位为n-1位,用补码表示时，数的表示范围为 -2n-12n-1-1, 一旦运算时发生结果超出此范围的情况，就产生溢出。产生溢出时，将造成运算结果错误。所以当产生溢出时， 计算机状态字寄存器 （PSW）的溢出标志位将自动置为 1,否则为0.在计算机中有很多判断溢出的方法，一般通过逻辑电路自动检测到溢出后执行相应的中断处理。要想尽量避免产生溢出错误，在设计计算机硬件时可以考虑增加机器字长以表示更大范围的数值。1.2.2 非数值表示1.字符

20、的表不由于计算机是以二进制的形式存储、运算、识别和处理数据的，因此，字母和各种字符也必须按特定的规则变为二进制编码才能输入计算机。字符编码实际上就是为每一个字符确定一 个对应的整数值，以及相对应的二进制编码。但是，由于字符（包括拉丁字母）与整数值之间 没有什么必然的联系，某一个字符究竟对应哪个整数完全可以任意规定。为了信息交换中的统 一性，人们已经建立了一些字符编码标准，常用的有ASCII （American Standard Code forInformation Interchange,美国标准信息交换代码）字符编码标准以及旧M公司提出的EBCDIC代码等，其中以 ASCII码使用的范围最

21、广泛。国际标准化组织（ISO）和我国都颁发了与 ASCII 一致的编码标准（ISO-646 和 GB-1988-80 ）。ASCII编码标准用7位二进制数编码，用来表示128种不同的字符，如表 1-4所示。其中的95个编码对应键盘上能输入，并且可以显示和打印的95个字符。这95个字符可分为几大类：大写、小写各 26个英文字母；09共10个数字；通用的运算符和标点符号：+、-、X、/、=、！等。另外的33个字符，其编码值为 031和127,即000 0000000 0001 和111 1111,不对应任何一个可显示或打印的实际字符，它们被用作控制码，控制计算机某些外围设备的工作特性和某些计算机软

22、件的运行情况。例如，编码 0000010 （码值为10）表示"换行”.由7位编码构成的ASC n码基本字符集能表示的字符只有128个，不能满足信息处理的需要，所以又对 ASCH码字符集进行扩充，采用一个字节（8位二进制位数）表示一个字符，编码范围：0000000011111111,一共可表示256种字符和图形符号，成为扩充的ASCH码字符集。表1-4 ASCII字符集|二进制00。001on1<M>101110ill0NULDELSP0pp1ODOLSOHDCIIIAQgq21010STXDC22BRbr3OOHETXDC3.3CSc$4OI00EOTDC4s4DTdt5

23、OLDEENQHAK%5EUeu601LDACKSYW&6FVfV7OHLBELETB7Gwew81000BSCAN'(eHXbKg1001MTEM)giViy141010LFSUB*jzjz1011VTESC+VK(k(121100FFFSLII1 -1311011-F:=M)m)111L0SORShlAn1511HSFUS/0。DEL对计算机字符的处理实际上是对字符编码进行处理。例如：比较字符A和E的大小，实际上是对A和E的ASCII码65和69进行比较。字符输入时，按一下键，该键所对应的ASCII码即存入计算机。把一文本文件中的所有字符录入到计算机，计算机里存放的实际上是

24、一大串 ASCII 码。2 .汉字表示法英文是拼音文字，一个不超过128种字符的字符集，就可满足英文处理的需要。汉字是象形结构，字数多，字形复杂，计算机存储和处理都比较复杂。用计算机处理汉字，首先要解决汉字编码问题。根据统计，在人们日常生活交往中经常使用的汉字约有四五千个。原则上，两个字节可以表示256 X256=65536 种不同的符号，作为汉字编码表示的基础是可行的。我国国家标准局采用了加以修正的两字节汉字编码方案，只用了两个字节的低 7位，该方案可以容纳 128 X128=16384 种不同的汉字，彳！为了与标准ASCII码兼容，每个字节只能用 94个编码。国家标准汉字字符集 GB231

25、2-80 共收集了 7445个汉字和图形符号，其中汉字6763个,分为二级，一级汉字 3755个，二级汉字 3008个，另外还包括：一般符号202个：包括间隔符、标点、运算符和制表符号；序号60个：它们是120 （20个）、（1） （20）、和（一） （+）;数字22个：09、I XH;英文字母52个；日文假名169个（ 83,86 ）;希腊字母48个；俄文字母66个；汉语拼音符号26个；汉语注音字母 37个。每个汉字符号都对应一个国标码和一个区位码，国标码是一个四位十六进制数，区位码是一个四位十进制数。因为十六进制数很少用到，所以常用的是区位码，它的前两位叫做区码，后两位叫做位码，区的序号和

26、位的序号都是从194.相应地，国标码的第一字节可视为存放位置的行号，从21H7EH,第二字节可视为存放位置的列号，也从 21H7EH,如表1-5所示。表1-5 GB2312-80 字符集结构0030212223242536 7C TO 7E00-20123456-929394212F115非汉字图形符号（常用符号、数字序号、俄、法、希睹字母、日文假名等）16 55一锻汉字3755个）5a什防BT二辗汉字（3006个）73 7183 94空白区7E例如：汉字第一字节第二字节国标码区位码啊 001100000010000130211601水 01001011 00101110432E4314在国标

27、码中，一个汉字占两个字节，每个字节最高位为0,为了在计算机中将 ASCII码和国标码区分开，一般将国标码的最高位置为1,变换后的国标码就叫做汉字机内码。因为历史和地域原因， 汉字有不少编码标准。 最常见的是 GB2312和BIG5.在Unicode （统 一码）被完全接受前，它们将共存相当长的一段时间。Unicode 码是由Unicode 学术学会制定的字符编码系统，旨在支持多种语言书面文本的交换、处理和显示。 Unicode码4.0版本于2003年推出，该版本包括了中文简体字、日文平 假名、片假名、泰文、韩文、阿拉伯文等世界主要语系的文字。3 .图形数字化编码在计算机中，图形（Graphic

28、s ）和图像（Image ）是两个不同的概念，图形一般指使用绘 画软件绘制出的由直线、曲线等组成的画面，图形文件中存放的是描述图形的指令，以矢量图 形文件存储。图像则是由扫描仪、数码相机等输入的画面，数字化后以点阵（位图）形式存储。点阵表示法一幅图像可以看作由排列成若干行、若干列的黑白或彩色的光点组成，每个光点叫做一个像素（Pixels）,从而形成一个像素点阵列。阵列中的像素总数决定了图像的精细程度。像素的 数目越多，图像越精细，其细节的分辨程度也就越高，但同时也必然要占用更大的存储空间。对图像的点阵表示，其行列数的乘积称为图像的分辨率。例如，若一个图像的阵列共有 480行,每行640个点，则

29、该图像的分辨率为640 X480像素。在计算机中存储和处理图像同样要用二进制数字编码的形式。将每个像素点用若干个二进制位进行编码，表示图像颜色的过程就叫做图像数字化。描述图像的重要属性是图像分辨率和颜色深度，因此图像数字化编码可以分为以下几类。黑白色如果一个像素点只有黑白两种颜色，那么只用一个二进位就可以表示一个像素。这时，一个 640 X480 的像素阵列需要 640 X480/8=38400B=37.5KB.256色灰度由黑白二色像素构成的图像也可以用像素的灰度来模拟彩色显示，一个像素的灰度就是像素的亮度，即介于纯黑和纯白之间的各种情况。计算机中采用分级方式表示灰度：例如分成256个不同的

30、灰度级别（可以用0到255的数表示），用8个二进位就能表示一个像素的灰度。采用灰度方式，使图像的表现力增强了，但同时存储一幅图像所需要的存储量也增加了。例如采用上述256级灰度，与采用 256种颜色一样，表示一幅640 X480像素的图像就需要大约 30万个字节（300KB ）。真彩色图像显示通过不同的强度混合而成。所谓"真彩色”的图像显示，就是用三个字节表示一个像素点的色彩，其中每个字节表示一种基色的强度，强度分成256个级别。由此可知，要表示一个640X480像素的"真彩色"的点阵图像，需要将近 1MB的存储空间。由此可见，图像点阵表示法的缺点是：保存一幅图像

31、所需的存储空间很大。因此后来又发展出了许多压缩图像文件格式来节省存储空间，常用的有 BMP、JPEG、GIF、AVI、MPEG矢量表不法基本原理是用直线逼近曲线，用直线段两端点位置表示直线段。采用这类方法表示图形存储量非常少。矢量图形由矢量定义的直线和曲线组成，Adobe Illustrator 、CorelDraw、CAD等软件是以矢量图形为基础进行创作的。矢量图形根据轮廓的几何特性进行描述，图形的轮廓 画出后，被放在特定位置并填充颜色，移动、缩放或更改颜色不会降低图形的品质。矢量图形与分辨率无关， 可以将它缩放到任意大小和以任意分辨率在输出设备上打印出来， 都不会影响清晰度。1 .2.3

32、校验方法和校验编码计算机中数据在进行存储和传输过程中可能会发生错误。为了及时发现和纠正这类错误， 在数据传输（存储）过程中要进行校验，常用的校验方法就是奇偶校验方法、循环冗余校验方 法、海明码校验方法。奇偶校验法是计算机中广泛采用的检查传输数据准确性的方法2 .奇偶校验方法奇偶校验方法的原理是在每组数据信息上附加一个校验位，校验位的取值（0或1 ）取决于这组信息中1'的个数和校验方式（奇或偶校验）。如果采用奇校验，则这组数据加上校验码位 后数据中1'的个数应为奇数个。如果采用偶校验，则这组数据加上校验码位后数据中1'的个数应为偶数个。例如：奇偶校验方法八位信息'

33、10101011'中共有5个'1',附加校验位后变为九位。 若采用奇 校验，则附加的校验位应取0'值，彳证1的个数为奇数个即 0 10101011 ;若采用偶校验则附 加的校验位应取'1'值即1 10101011 .奇偶校验的特点:奇偶校验法使数据的码距为2,因而可检出数据传送过程中奇数个数位出错的情况;实际中两位同时出错的概率极低，奇偶校验法简便可靠易行，但它只能发现错误，却不知错在何处，因而不能自动纠正。3 .海明码校验方法海明码校验方法以奇偶校验法为基础，其校验位不是一个而是一组，故其码距大于2 .海明码校验方法能够检测出具体错误并纠正原理

34、是在数据中加入r个校验位，将数据的码距按照一定规则拉长。r个校验位可以表示 2r个信息，除一个表示无误信息外，其余2r-1信息可以用来标明错误的具体位置，但由于校验位本身也可能在传送中出错，所以只有2r-1-r个信息可用，即r位校验码只可标明 2r-1-r个错误信息。例如：用4个校验位能可靠传输 24-1-4=11 位信息；而要校验32位数据则需至少6个校 验位。如要能检测与自动校正一位错并发现两位错此时校验位的位数r和数据位的位数 k应满足下述关系：2r-1叁k+r.根据表1-6，可计算出数据位 k与校验位r的对应关系。表1-6 数据位k与校验位r的对应关系K值最小的值45 "11

35、5:12 z 26627 57758 1208编码方法（以四个校验位进行说明）四个校验位最多可以校验11位数据。设：D10D9D8D7D6D5D4D3D2D1D0 为11个数据位，P4P3P2P1分别为四个校验码，则编码规则是：海明码的总位数等于数据位与校验位之和；每个校验位 Pi排放在2i-1的位置，例如 P4排放在第24-1=8位，其余数据位依序排列。海明码的每一位用多个校验位一起进行校即：D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1验，被校验的位号等于校验它的各校验位位号和;各校验位的值为它参与校验的数据位的异或。表1-7海明码校验表海明码位号参与屣 neafcft隹号

36、娄与的校监位PliP1H2P22P2H3DI2* 1 (3=2+1)P2,F1H4PS4P3H5D24* 1 (S=4+l)P饵P1H6D34* 2 (6=4+2)P&P2H704% 2, i (7=4+2+1)P3,P2flFlHBP48P4H9D58， 1(9=8+1)P4,P1H1006甘.2(10=9+2)P4J之H11D7& 2， 1 (11=8+2+1)风 PaP1H12DS& 4P4,F3H13D9& d+ 1(148X+DP4,PXP1H14DIO号 m 2(14=8+4+2)Pd,P3flF2H15Dll际 4, 2, 1 (15=8+4+2+

37、1)P4, P3#2,P1各校验位形成公式:P1=D0D1D3D4D6D8D10P2=D0D2D3D5D6D9D10P3=D1D2D3D7D8D9D10P4=D4D5D6D7D8D9D10(4)Pi则取反。这样 Pi连同按上述方式Pi的取值是采用偶校验时的取值，当采用奇校验时, 数据位一起形成了海明码的各位。检查纠错（以四个校验位进行说明）海明码数据传送到接收方后，再将各校验位的值与它所参与校验的数据位的异或结果进行异或运算。运算结果称为校验和，校验和共有四个。对偶校验来说，如果校验和不为零则传输过程中间有错误，而错误的具体位置则由四个校验和依序排列后直接指明。如果四个校验和S4s3s2S1依

38、序排列后等于(1001 ) 2= (9) 10时，就表明海明码的第九位也就是D4发生了错误，此时只要将 D4取反，也就纠正了错误。校验和Si的表达式：S1 =D0D1D3D4D6D8D10P1S2 =D0D2D3D5D6D9D10P2S3 =D1D2D3D7D8D9D10P3S4 =D4D5D6D7D8D9D10P4当采用偶校验方式其传送数据正确时，校验和S1 S4的值分别都为0;当采用奇校验方式其传送数据正确时，校验和S1 S4的值分别都为1.当不为上述值时，传送就发生了错误。例如：采用4位校验位、偶校验方式，写出10110100110 的海明码。解：已知 D10D9D8D7D6D5D4D3

39、D2D1D0=10110100110,由于被校验位的位号等于校验它的各校验位位号之和以及各校验位的取值等于它参与校验的数据位取值的异或，所以校验位的取值以及所求海明码为：P1=D0D1D3D4D6D8D10=1P2=D0D2D3D5D6D9D10=1P3=D1D2D3D7D8D9D10=1P4=D4 D5 D6 D7 D8 D9 D10=0D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1=101101000111011传送正确时校验和的值为 0,如果不等于0,则是几就是第几位出错，是 7则是第7位D3出 错，此时将其取反即可纠正错误。4 .循环冗余校验方法(CRC码)循环冗余校验

40、方法是通过某种数学公式建立信息位和校验位之间的约定关系-能够校验传送信息的对错，并且能自动修正错误。广泛用于通信和磁介存储器中。CRC编码格式是在k位信息后加r位检验码。U N+1_ W _ 1I Cl ICZ CK 1 TC ，二信息位年位)|校啜位行位)|CRC码的编码方法CRC整个编码长度为 n=k+r 位，故CRC码又叫(n,k)码。其编码方法如下：假设被传 送的k位二进制信息位用 C (x)表示，系统选定的生成多项式用G (X)表示，将C (x)左移G (X)的最高次哥(即等于需要添加的校验位的位数r),写作C (x) * 2r然后将其C (x)*2r除以生成多项式 G (x),所得

41、商用Q (x)表示，余数用 R (x)表示。则：C (x) *2r/G (x) =Q (x) +R (x) /G (x)两边同时乘以 G (x)并左移 R (x)得到：C (x) *2r-R (x) =Q (x) *G (x)。由于CRC 编码采用的加、减法是按位加减法，即不考虑进位与借位，运算规则为： 0+0=0,0+1=1,1+0=1,1+1=0故有：C (x) *2r+R (x) =Q (x) *G (x) 式中，等式左边即为所求的n位CRC码，其中余数表达式R (x)就是校验位(r位)。且等式两边都是 G (x)的倍数。发送信息时将等式左边生成的n位CRC码送给对方。当接收方接到 n位

42、编码后，同样除以 G (x),如果传输正确则余数为0,否则则可以根据余数的数值确定是哪位数据出错。例如有一个(7,4)码(即CRC码为7位，信息码为4位)，已确定生成多项式为：G (X)=X3+X+1= 1011被传输的信息 C (x) =1001,求 C (x)的 CRC 码。解：C (x)左移r=n*=3 位，即：C (x) *2r=1001*23, 将上式模2采用除法 除以给定的 G (x) =1011:1001000/1011=1010+110/1011,得到余数表达式： R (x) =110 所求 CRC码为：C (x) *23+R (x) =1001000+110=1001110收

43、到的CRC码除以约定的生成多项式(x),如果余数为0则传输无误，否则传输错误,根据所得余数值就可找出错误并取反纠正。表1-8详细说明了 CRC码1001110在传送时某一表1-8 CRC码的查错表十六港制0000010001200103001140100501016011070111i8100091001A1010BWilCL100D1101E1110FUllG (X) =1011.位出错后的判断与纠正方法C (X) =1001生成多项式 G (x)的确定G (x)是一个约定的除数，用来产生校验码。从检错和纠错的要求出发，它并不是随意选择的，它应满足下列要求：任何一位发生错误都应使余数不为0;

44、不同位发生错误应使余数不同；余数继续模2除，应使余数循环；CRC的译码与纠错将收到的循环校验码用约定的生成多项式G (X)去除，如果码字无误则余数应为0,如有某一位出错，则余数不为0,不同位数出错余数不同。如果循环码有一位出错，用G (X)作模2除将得到一个不为 0的余数、如果对余数补1个0继续除下去我们将发现一个现象；各次余数将按表1-8顺序循环、例如第七位出错，余数将为OO1,补0后再除，第二次余数为 010,以后依次为100,011,，反复循环，这是一个有价值的特点。如果我们在求出余数不为0后，一边对余数补 0继续做模2除，同时让被检错的校验码字循环左移。表 1-8说明当出现余数(101

45、 )时，出错位也移到 A1位置、对通过异或门将它纠正后在下一次移位时送回A1.继续移满一个循环(对 7,4码共移七次)就得到一个纠正后的码字。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件、当位数增多时 循环码校验能有效地降低硬件代价。1.3算术运算和逻辑运算1.3.1 二进制的算术运算1.加法运算规则0+0=00+1=11+0=1 1+1=102 .减法运算规则0-0=00-1=1 （向高位借 1）1-0=1 1-1=03 .乘法运算规则0X0=0 0X1=0 1X0=0 1X1=11.3.2 逻辑运算1 .基本运算逻辑乘，也称"与"运算，运算符为"

46、"或"A".0 0=0 0 1=0 1 0=0 1 1=1使用逻辑变量时，AB可以写成AB逻辑加，也乘"或"运算,运算符为"+"或，.0+0=00+1=11+0=1 1+1=1逻辑非，也称"反"运算，运算符是在逻辑值或变量符号上加-0=1-1=02 .常用运算异或运算：AB=A B+A B1.3.3 基本公式1.0,1 律A 0=0 A 1=AA+0=AA+1=12 .交换律A+B=B+AA B=B A3 .结合律'A+B+C=(A+B ) +C=A+(B+C) A B C= (A B) C=A

47、(BC)4 .分配律A ( B+C ) =A B+A C5 .重叠律A+A+ +A=AA A - A=A6 .互补律A + A=1A A=07 .吸收律A+A B=A A (A+B ) =AA+A B=A+B A (A+B ) =A B8 .对合律对一个逻辑变量两次取反仍是它本身9 .德摩根定理A+B=A BA B=A+B1.3.4 逻辑代数的应用1 .逻辑表达式化简例如：F=A B+A B+A B=A B+A ( B+B )（利用分配律）=A B+A(利用互补律以及 0,1律)=A+B(利用吸收律)2.对指定位进行运算假设变量 A有八位，内容是 d7d6d5d4d3d2d1d0.将变量A的d

48、5位清零，A ( 11011111 ) -A.将变量A的各位置1,A+ (11111111 ) -A.1.4 数据结构与算法基本概念1.4.1 什么是数据结构随着计算机的飞速发展，再把计算机简单地看作是进行数值计算机的工具，把数据仅理解 为纯数值性的信息，就显得太狭隘了。现代计算机科学的观点，是把计算机程序处理的一切数 值的、非数值的信息，乃至程序统称为数据( Data ),而计算机则是加工处理数据的工具。由于数据的表示方法和组织形式直接关系到程序对数据的处理效率，而系统程序和许多应用程序的规模很多，结构相当复杂，处理对象又多为非数值性数据。因此，仅凭程序员的经验 和技巧已难以设计出效率高、可

49、靠性强的程序。于是，就要求人们对计算机程序加工的对象进行系统的研究，即研究数据的特性以及数据之间存在的关系-数据结构(Data Structure )。计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序、进行测试、调整至得 到最终解答。寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象 之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。1.4.2 数据结构基本术语下面介绍一下数据结构的常用名词和术

50、语的含义。数据(Data )是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。数据元素(Data Element )简称元素，是数据的基本单位，通常作为一个整体进行考虑和处理。对于一个文件而言，每个记录就是它的数据元素；对于一个字符串而言，每个字符就是它的数据元素。数据和数据元素是相对而言的。有时，一个数据元素可以由若干个数据项(DataItem )组成。数据记录(Data Record )简称记录，它是数据处理领域组织数据的基本单位，数据的每个数据元素在许多应用场合被组织成记录的结构。一个数据记录由一个或多个数据项组成，每个数据项可以是简单数据项，也可以是

51、组合数据项。关键项(Key Item )指得失在一个表或者文件中，若所有记录的某个数据项的值都不同，也就是每个值能唯一标识一个记录时，则可以把这个数据项作为记录的关键数据项，简称关键项。其中关键项的每一个值称作所在的记录的关键字( Key Word or Key )。数据处理(Data Processing )是指对数据进行查找、插入、删除、合并、排序、统计、简单计算、转换、输入、输出等的操作过程。数据结构(Data Structure ),简单地说，指数据以及相互之间的关系。它是研究数据元素(Data Element )之间抽象化的相互关系和这种关系在计算机中的存储表示(即所谓数据的逻辑结构

52、和物理结构)，并对这种结构定义相适应的运算，设计出相应的算法， 而且确保经过这些 运算后所得到的新结构仍然是原来的结构类型。数据类型(Data Type)是对数据的取值范围、每一数据的结构以及允许施加操作的一种描述。换言之，它是一个值的集合和定义在这个值集上的一组操作的总称。数据对象(Data Object )简称对象，是性质相同的数据元素的集合，是数据的一个子集。如25为一个整形数据对象，'A'为一个字符数据数据对象等。除了上述常见概念之外，数据结构还有许多的别的概念，例如算法、线性结构、集合、图、树等。1.4.3 算法的描述算法(Algorithm )就是解决特定问题的方法

53、。描述一个算法可以采用文字描述，也可以采用传统流程图、N-S或者PAD图等。作为一个算法应该具备以下5个特性：有穷性。一个算法必须在执行有穷步之后结束。确定性。算法的每一步都应该具有确切的含义，没有二义性。可行性。算法的每一步都必须是可行的。输入。一个算法可以有 0个或者0个以上的输入量。输出。一个算法执行结束后至少要有一个输出量，表示算法对输入量进行运算和处理的结果。注意，算法和程序是有区别的一程序未必能满足有穷性。算法可以借助各种工具描述出来。一个算法可以是自然语言、数字语言或约定的符号来描述，也可以采用计算机高级程序语言来描述。如流程图、Pascal语言、C语言、伪代码或决策表等。1.4.4 算法评价一般而言，设计一个"好”的算法应该考虑到以下目标。正确(Correctness )。算法主要是为了便于人的阅读和交流；可读性(Re