计算机基础题.doc

21
第1章 计算机科学基础知识
第1章 计算机科学基础知识
1.1 考试大纲
（1）数制及其转换
· 二进制、八进制、十进制和十六进制等常用数制及其相互转换
（2）计算机内数据的表示
· 数的表示
· 非数值表示（字符和汉字的表示、声音表示、图像表示）
（3）算术运算和逻辑运算
· 计算机中的二进制数运算方法
· 逻辑代数的基本运算
（4）其他数学基础知识
· 常用数值计算
· 排列组合、概率论应用、应用统计（数据的统计分析）
· 编码基础
· 命题逻辑、谓词逻辑、形式逻辑的基础知识
· 运筹基本方法
1.2 历年试题考点回顾
无论是作为计算机技术与软件专业的学生，还是从事计算机技术与软件方面的工程技术人员来讲，计算机科学基础知识是必备的也是最基本的知识。因此从考核的角度来讲，本部分的内容主要体现在程序员级别的考试中。对于软件设计师级别考试，并不是每次考试都直接考核本部分的知识点，而是通过对其他知识点的考核间接运用本部分的内容。从2004～2009年历年的12次软件设计师考试来看，对于本部分内容的直接考核，2004年上半年、下半年，2005年下半年，2006年下半年，2007年上半年、下半年，2008年上半年没有涉及；2005年上半年，2006年上半年，2008年下半年，2009年上半年、下半年的考试中关于本部分的知识点占2分左右。考核的知识点主要围绕：原码、反码、补码和移码等数字编码；浮点数的表示与运算；校验方法和校验码（奇偶校验码、海明校验码和循环冗余校验码）。出现过的题型主要有：补码、移码适合在什么场合使用；原码、反码、补码、移码如何表示±0；浮点数的表示形式；浮点数的加减运算（对阶）、相乘运算（结果规格化）；几种校验方法的比较；海明校验码中数据位与校验位的关系等。
1.3 典型例题
【例1-1】 多项式214＋211＋24＋21＋20表示为十六进制数为 （1） ，表示为十进制数为 （2） 。
（1）A．4813H B．8026H C．2410H D．EB410H
（2）A．18448 B．9232 C．18451 D．36902
【解析】
这一类型的题目考查的知识点是数制间的转换。
解答此类题目的一般思路是：将给出的多项式表达成二进制的形式，然后再将二进制数转换成十六进制数的形式。至于将多项式表示为对应的十进制数形式，即可以采用将给出的多项式直接求和，也可以采用十六进制数转换为十进制数的方法。
针对这道题目，多项式214＋211＋24＋21＋20表示为二进制数为100100000010011B，则对应的十六进制数为4813H，对应的十进制数为18451，所以答案应该是（1）A，（2）C。
【例1-2】 在计算机中，最适合进行数字加减运算的数字编码是 （1） ，最适合表示浮点数阶码的数字编码是 （2） 。
（1）A．原码 B．反码 C．补码 D．移码
（2）A．原码 B．反码 C．补码 D．移码
【解析】
这一类型的题目考查的知识点是机内数据的表示形式。
各种数据在计算机中表示的形式称为机器数，其特点是采用二进制计数制，数的符号用0、1表示，小数点则隐含表示而不占位置。机器数对应的实际数值称为数的真值。
机器数有无符号数和带符号数之分。无符号数表示正数，在机器数中没有符号位。对于无符号数，若约定小数点的位置在机器数的最低位之后，则是纯整数；若约定小数点的位置在机器数的最高位之前，则是纯小数。对于带符号数，机器数的最高位是表示正、负的符号位，其余位则表示数值。若约定小数点的位置在机器数的最低数值位之后，则是纯整数；若约定小数点的位置在机器数的最高数值位之前（符号位之后），则是纯小数。
为了便于运算，带符号的机器数可采用原码、反码、补码和移码等不同的编码方法，机器数的这些编码方法称为码制。
正数的原码、反码、补码完全相同，其符号位为0，其余位取值不变。对于负数，负数的原码其符号位为1，其余各位取值不变；负数的反码其符号位为1，其余各位在原码基础上按位取反；负数的补码其符号位为1，其余各位在原码的基础上按位求反，再在末位上加1。
对于原码加减，操作数与运算结果均用原码表示。当两个相同符号的原码数相加时，只需将数值部分直接相加，运算结果的符号与两个加数的符号相同。若两个加数的符号相异，则应进行减法运算，其方法是先比较两个数绝对值的大小，然后用绝对值大者的绝对值减去绝对值小者的绝对值，结果的符号取绝对值大者的符号。由于原码加减运算时符号位要单独处理，使得运算较复杂，因此在计算机中很少被采用。
为了简化运算方法，常采用补码表示法，以便符号位也能作为数值的一部分参与运算。补码加法的运算法则是和的补码等于补码求和。补码减法的运算法则是差的补码等于被减数的补码加上减数取负后的补码。负数补码表示的实质是将负数映射到正数域，所以可将减法运算化为加法运算，这也是引入补码的原因。与原码减运算相比，补码减运算的过程要简便得多。在补码加减运算中，符号位和数值位一样参加运算，无须作特殊处理。因此，多数计算机都采用补码加减运算法。
移码是机器数的又一种表示方法，又称增码，多表示浮点数的阶码。移码的符号位，用1表示正号，用0表示负号，其求法是把其补码的符号位直接变反即可。
解答此类题目的一般思路是对机器数的编码要熟悉，知道其适用的场合。另外，对原码、反码、补码和移码，还要熟练掌握几种编码中0的表示以及几种编码所能表示的数的范围。
针对这道题目，在计算机中，最适合进行数字加减运算的数字编码是补码，最适合表示浮点数阶码的数字编码是移码，所以答案应该是（1）C，（2）D。
【例1-3】 计算机中常采用原码、反码、补码和移码表示数据，其中±0编码相同的是 。
A．原码和补码 B．反码和补码 C．补码和移码 D．原码和移码
【解析】
这一类型的题目考查的知识点是机内数据编码0的表示。
书写的真值包括数值部分及其符号（+/–），真值在计算机中的表示称为机器数，机器数的表示方法有原码、反码、补码和移码。要注意正、负数的区别，正数的原码、反码、补码完全相同，其符号位为0，其余位取值不变。对于负数，负数的原码其符号位为1，其余各位取值不变；负数的反码其符号位为1，其余各位在原码基础上按位取反；负数的补码其符号位为1，其余各位在原码的基础上按位取反，再在末位上加1。
移码是机器数的又一种表示方法，又称增码，多表示浮点数的阶码。移码的符号位，用1表示正号，用0表示负号，其求法是把其补码的符号位直接取反即可。
4种编码中数值0的表示不同，以8位编码为例。
（+0）原=00000000 （–0）原=10000000
（+0）反=00000000 （–0）反=11111111
（+0）补=00000000 （–0）补=00000000
（+0）移=10000000 （–0）移=10000000
解答此类题目的一般思路是对机器数的编码要熟悉，特别是原码、反码和补码，要熟练掌握几种编码中0的表示以及几种编码所能表示的数的范围。
针对这道题目，在4种编码0的表示中，原码、反码有+0和–0之分，即0的编码有2个；补码、移码无+0和–0之分，即0的编码只有1个。在供选择的答案中，±0编码相同的是补码和移码，所以答案应该是C。
【例1-4】 一定点数字长n位，且最高位是符号位，小数点位于最低位的后面，则该机器数所能表示的最小值是 。
A．1–2n–1 B．–2n–1 C．–2n–1–1 D．–2n
【解析】
这一类型的题目考查的知识点是定点数的表示范围。
所谓定点数，就是小数点的位置固定不变的数。小数点的位置通常有两种约定形式：定点整数（纯整数，小数点在最低有效数值位之后）和定点小数（纯小数，小数点在最高有效数值位之前）。
设机器字长为n，各种码制表示下的带符号数的范围如表1-1所示。
表1-1 机器字长为n时表示的带符号数的范围
码 制
定 点 整 数
定 点 小 数
原码
–(2 n–1–1)～+(2 n–1–1)
–(1–2–( n–1))～+(1–2–( n–1))
反码
–(2 n–1–1)～+(2 n–1–1)
–(1–2–(n–1))～+(1–2–( n–1))
补码
–2 n–1～+(2 n–1–1)
–1～+(1–2–( n–1))
移码
–2 n–1～+(2 n–1–1)
–1～+(1–2–( n–1))
解答此类题目的一般思路是首先清楚所给数是定点整数还是定点小数，然后确定对应码制的表示范围，最后得到要求的结果。要注意，由于字长为n位，且最高位为符号位，因此2的幂次是n–1，而不是n，这是容易出错的地方。
针对这道题目，按题意，该定点数是一个带符号的整数。最小值出现在符号为负，各位为全0时，此时该数应用补码表示，所以答案应该是B。
【例1-5】 某计算机中，浮点数的阶码占8位，尾数占40位（字长共48位），阶码用补码表示，尾数用原码表示，当基数为2时，数的表示范围是 。
A．–(1–2–39)×2–128～(1–2–39)×2127 B．–(1–2–40)×2–127～(1–2–40)×2127
C．–(1–2–40)×2–128～(1–2–40)×2127 D．–(1–2–39)×2–256～(1–2–39)×2255
【解析】
这一类型的题目考查的知识点是浮点数的表示范围。
当机器字长为n时，定点数的补码和移码可表示2n–1个数，而其原码和反码只能表示2n–1–1个数（0占用了两个编码）。因为定点数所能表示的数值范围比较小，运算中很容易因结果超出范围而溢出，所以引入了浮点数。浮点数是小数点位置不固定的数，它能表示更大范围的数。
二进制数N的浮点数表示方法为
N=2EF
式中，E称为阶码；F称为尾数。
在浮点数表示法中，阶码通常为带符号的纯整数，尾数为带符号的纯小数。浮点数的一般表示格式为

阶符
阶码
尾符
尾数

一个数的浮点表示不是唯一的。当小数点的位置改变时，阶码也随之改变，因此可用多种浮点形式表示同一个数。
浮点数所能表示的数值范围主要由阶码决定，所表示数值的精度由尾数决定。
对浮点数N：当N为最大正数时，F是最大正数，E是最大正数；当N为最小正数时，F是最大正数，E是最小负数；当N为最大负数时，F是最大负数，E是最小负数；当N为最小负数时，F是最小负数，E是最大正数。
解答此类题目的一般思路是首先明确阶码和尾数采用什么编码，然后计算阶码和尾数的表示范围，最后组合得到浮点数的表示范围。一定要注意题目中阶码E和尾数F指定的是什么编码（原码、反码、补码或移码），否则很容易出错。
针对这道题目，阶码用补码表示，尾数用原码表示，这个浮点数的格式为：
47 46 … 40 39 38 … 0
↑ ↑ ↑ ↑
阶符 阶码 尾符 尾数
阶码的表示范围：–128～+127（即10000000～01111111）
尾数表示的范围：–(1–2–39)～(1–2–39)
最小数为：–(1–2–39)×2–128
最大数为：(1–2–39)×2127
这个浮点数的表示范围为–(1–2–39)×2–128～(1–2–39)×2127，所以答案应该是A。
【例1-6】 计算机中16位浮点数的表示格式为：
0 3 4 15
阶码
尾数（含尾符）

其中，阶码4位（含1位符号）为定点整数；尾数12位（含1位符号）为定点小数。设一个数机器码为1110001010000000。
若阶码为移码且尾数为原码，则其十进制真值为 （1）
若阶码为移码且尾数为反码，则其十进制真值为 （2）
若阶码为补码且尾数为原码，则其十进制真值为 （3）
若阶码为补码且尾数为补码，则其十进制真值为 （4） ，将其规格化后的机器码为
（5） 。
（1）～（4）A．0.078125 B．20
C．1.25 D．20.969375
（5） A．1110001010000000 B．11110101000000
C．1101010100000000 D．11110001010000
【解析】
这一类型的题目考查的知识点是浮点数的表示及其规格化。
为了充分利用尾数来表示更多的有效数字，即提高数据的表示精度，通常采用规格化浮点数。规定浮点数在运算结束将运算结果存到机器中时，必须是规格化的浮点数。规格化浮点数尾数的最高数值位是有效数字，即正尾数0.5≤F<1，负尾数–1<F≤–0.5。
要求规格化以后，其尾数部分是正数时为0.1×××的形式；是负数时，对于原码为1.1×××的形式，对于补码为1.0×××的形式，可以通过尾数小数点的左右移动和阶码的变化实现。
此类题通常给出计算机中的浮点数表示形式，给出机器码，并指出阶码和尾数的编码，求它的十进制真值；或已知十进制真值，求内码表示。只要了解它的结构和表达形式及转换关系，不管如何考，都可以做到游刃有余。
解答此类题目的一般思路是对给定的机器码按给定的浮点数格式得到阶码和尾数，然后将阶码变为十进制数，最后得到浮点数的十进制真值。判断如果给定的浮点数机器码不是规格化表示，则可将其表示为规格化的机器码。规格化时，先看给定的浮点数机器码的尾数是用什么码表示，然后看看是否已是规格化数，如不是，将尾数小数点移位，但要注意，为保持浮点数的真值不变，阶码一定要相应地调整。另外在解答此类题目时，还要注意题目条件中给出的阶码和尾数是用什么码表示的，否则很容易出错，而得不到正确的 结果。
针对这道题目，对所给机器码1110 0010 1000 0000，按所规定的浮点数表示形式，可知阶码为1110（最高位为阶符1），尾数为001010000000（最高位为尾符0）。
（1）若阶码为移码，1110表示为十进制数＋6，尾数为原码，表示＋0.0101B，则浮点数为26×0.0101B=010100B=20。
（2）若阶码为移码，尾数为反码，因为该尾数为正，其原码与反码相同，所以结果 同（1）。
（3）若阶码为补码，1110表示为十进制数－2，尾数为原码，即＋0.0101，该浮点数为2–2×0.0101B=0.000101B=0.078125D。
（4）若阶码为补码，且尾数也为补码，因该尾数为正数，所以结果同（3）。
（5）将（4）中的浮点数用规格化数形式表示。2–2×0.0101B=2–3×0.101B，阶码–3的补码为1101，因为浮点数规格化要求尾数最高数据位为有效数据位，即尾数绝对值≥0.5。实际判断时，对于尾数以补码表示时，看符号位与最高位是否不同，如不相同即为规格化数，如相同即为非规格化数，故规格化后的机器码为1101 010100000000。
对于本题（5），就给出的机器码来说，就是使其尾数001010000000左移一位成为010100000000，相当于尾数数值乘2，相应地其阶码就应减1，即–2减1得–3。
所以答案应该是（1）B，（2）B，（3）A，（4）A，（5）C。
【例1-7】 计算机在进行浮点数的相加（减）运算之前先进行对阶操作，若x的阶码大于y的阶码，则应将 。
A．x的阶码缩小至与y的阶码相同，且使x的尾数部分进行算术左移
B．x的阶码缩小至与y的阶码相同，且使x的尾数部分进行算术右移
C．y的阶码扩大至与x的阶码相同，且使y的尾数部分进行算术左移
D．y的阶码扩大至与x的阶码相同，且使y的尾数部分进行算术右移
【解析】
这一类型的题目考查的知识点是浮点数的加减运算。
设浮点数，，求X±Y的步骤一般分为5步。
（1）对阶。
使小阶向大阶看齐，达到使两个数的阶码相同。令，把阶码小的数的尾数右移位，使其阶码加上。
现以，，求为例说明。
若两数均以补码表示，并用双符号位，即
[X]补=00 01, 00.1101 （阶码 尾数）
[Y]补=00 11, 11.0110 （阶码 尾数）
k=j–i=0011–0001=0010 即将X尾数右移2位
[X]补=00 11, 00.0011 （阶码 尾数） 对阶完成
（2）求尾数和（差）。
得到：00.0011+11.0110=11.1001
即
[X+Y ]补=0011, 11.1001 （阶码 尾数）
（3）结果规格化并判断溢出。
对于补码尾数：
若无溢出，即符号位为00（正数），11（负数），向左格式化。规格化结果为00.1×××（正数）或11.0×××（负数）。规则：尾数每左移1位，阶码减1。
若有溢出，即符号位为01（正溢出－上溢），10（负溢出－下溢），向右格式化。规格化结果为00.1×××（正数）或11.0×××（负数）。规则：尾数右移1位，阶码加1。
对于上例
[X+Y]补=0011, 11.1001 （阶码 尾数）
不是规格化数，尾数左移1位，得到
[X+Y]补=0010, 11.0010 （阶码 尾数）
（4）舍入。
在对阶或向右规格化时，尾数要向右移位，其低位部分会被丢掉，应进行舍入处理。常用方法有：
① 截断法：将溢出的末尾数据全部截去。
② 末位恒1法：将要保留的末位数据恒置1。
③ 0舍1入法：若右移时被丢掉数位的最高位为0则舍去，为1则将尾数的末位加1（相当于四舍五入）。
（5）阶码溢出判断。
若阶码溢出，则表示浮点数的运算结果溢出。
若阶码正常，则加（减）运算正常结束；若阶码下溢，则置结果为0；若阶码上溢，则置溢出标志。
解答此类题目的一般思路是要熟练掌握浮点数加减运算的5个步骤。实际运算可能出现的问题是：
① 对阶不正确。要注意对阶操作总是使小阶向大阶对齐，即小阶的尾数向右移位，每右移一位，其阶码加1，直到两数的阶码相等为止，右移的位数等于阶差。同时要注意符号位的移位及尾数右移的舍入处理。
② 运算结果未规格化。对尾数求和运算后对浮点数进行规格化处理。
另外，对于浮点乘除法运算：
① 阶码运算：阶码求和（乘法）或阶码求差（除法）。
② 浮点数的尾数处理：浮点数中尾数进行乘除法运算，其结果也要规格化并进行舍入处理。
针对这道题目，主要是浮点加减法的对阶问题，其关键是小阶向大阶对齐，小阶的尾数向右移位，根据题意，x的阶码大于y的阶码，因此应使y的阶码扩大至与x的阶码相同，且使y的尾数部分进行算术右移，所以答案应该是D。
【例1-8】 用二进制加法器对二–十进制编码的十进制数求和，当和的个位十进制数 二–十进制编码不大于1001且向高位无进位时， （1） ；当和不大于100l且向高位有进位时， （2） ；当和大于1001时， （3） 。
（1）～（3）A．不需进行修正 B．需进行加6修正
C．需进行减6修正 D．进行加6或减6修正，需进一步判别
【解析】
这一类型的题目考查的知识点是二–十进制编码的加法运算规则。
在二–十进制编码中，每位十进制数与不大于1001的二进制数相同，但求得的和可能大于1001，因而需要进行修正。4位二进制数逢16进位，二–十进制数逢10进位，两者相差6。所以在进行二–十进制编码加法运算时需要遵循以下规则。
（1）当和不大于1001且向高位无进位时，不需进行修正。
（2）当和不大于1001且向高位有进位时，需要进行加6修正。
（3）当和大于1001时，需要进行加6修正。
解答此类题目的一般思路是要正确理解二进制数、十进制数、BCD码，注意其相互关系及运算法则。
针对这道题目，根据上述论述，答案应该是（1）A，（2）B，（3）B。
【例1-9】 X、Y是两个单字节带符号的整数，已知[X]补=10100111，[Y]补=11011011，现执行减法运算，其X–Y的结果应等于 。
A．10000010 B．11001100 C．11001101 D．00110011
【解析】
这一类型的题目考查的知识点是二进制数的运算方法。
计算机中通常只设置加法器，减法运算是转换为加法运算来实现的。对原码表示的机器数进行运算时，符号位和数值位需要分别处理，因此计算机的加、减运算中常采用机器数的补码表示形式。
补码加法的运算法则是：和的补码等于补码的和，即[X+Y]补=[X]补+[Y]补。
补码减法的运算法则是：差的补码等于被减数的补码加上减数取负后的补码，即 [X–Y]补=[X]补+[–Y]补。因此，在补码表示中，可将减法运算转换为加法运算。
解答此类题目的一般思路是将减法运算转换为补码加法运算。由于[X–Y]补=[X]补+[–Y]补，故需求[–Y]补，而已知[Y]补，求[–Y]补的法则是：对[Y]补包括符号位“求反且最末位加1”，即可得到[–Y]补。要注意：已知[X]补，求[–X]补时一定要把符号位也一同“求反加1”（无论正负）；这与已知[X]原求[X]补不同（负数时），其符号位不变。
针对这道题目，根据已知确定X、Y均是负数，且是补码的表示形式。
因为[Y]补=11011011 有[–Y]补=00100101
则[X–Y]补=[X]补+[–Y]补=10100111+00100101=11001100
所以X–Y= –0110100
结果为–0110100或11001100，所以答案应该是B。
【例1-10】 设X=+1000001，Y=+1000011，采用双符号位判决法求得的[X＋Y]补结果为 。
A．0 0000100 B．01 0000100 C．00110110 D．10 0110110
【解析】
这一类型的题目考查的知识点是补码的运算及其溢出。
在确定了运算的字长和数据的表示方法后，数据的范围也就确定了。一旦运算结果超出所能表示的数据范围，就会发生溢出。溢出时，运算结果肯定是错误的。
当两个同符号的数相加（或者是相异符号数相减）时，运算结果有可能产生溢出。
常用的溢出检测机制主要有进位判决法和双符号位判决法。
（1）双符号位判决法。
若采用两位表示符号，即00表示正号、11表示负号，则溢出时两个符号位就不一致了，从而可以判定发生了溢出。
（2）进位判决法。
令表示最高数值位向最高位的进位，表示符号位的进位，则表示溢出。
解答此类题目的一般思路是：将所给带符号数的符号位用双符号位表示，然后转换成补码，进行补码运算，得到结果。要注意，结果溢出和结果产生进位是两个概念，溢出表示运算结果出错，进位表示最高位产生了进位但结果并未出错。
针对这道题目，由于X和Y均为正数，因此用双符号位表示的补码[X]补=00 1000001，[Y]补=00 1000011，经计算，[X＋Y]补=01 0000100，实际上，运算结果产生了正溢出。所以答案应该是B。
【例1-11】 假定下列字符码中最后一位是奇偶校验位，但没有数据错误，采用奇校验的字符码是 。
A．11001111 B．11010110 C．11010111 D．11001001
【解析】
这一类型的题目考查的知识点是数据的奇偶校验。
计算机系统运行时，在各个部件之间经常需要进行数据交换，为保证数据传送过程的正确无误，必须引入差错检查机制对数据进行校验，以检测是否有数据传送错误。其基本原理是：在编码中引入一定的冗余位，使得当被传送的编码中出现错误时就成为非法代码而被测出。
奇偶校验码用于并行码的检错。其原理是：在k位数据码之外增加1位检验位，使k+1位码字中取值为1的位数总保持为偶数（偶校验）或奇数（奇校验）。
目前应用的奇偶校验码主要有3种：水平奇偶校验码、垂直奇偶校验码和水平垂直校验码。
（1）水平奇偶校验码：对每一个数据的编码添加检验位，使信息位与检验位处于同 一行。
（2）垂直奇偶校验码：把数据分成若干组，每一个数据占一行，排列整齐，再加一行校验码，针对同一组中的每一列采用奇校验或偶校验。
（3）水平垂直奇偶校验码：在垂直奇偶校验码的基础上，对每一个数据再增加一位水平校验位，便构成了水平垂直奇偶校验码。
解答此类题目的一般思路是对于水平奇偶校验和垂直奇偶校验来讲，加入1位检验位使得构成的码字中取值为1的位数若为偶数则是偶校验，若为奇数则是奇校验。对于水平垂直奇偶校验的题目，一般解法为：先找一行或一列完整的已知数据，确定出该行（或列）是奇校验还是偶校验，并假设行与列都采用同一种校验（这个假设是否正确，在全部做完后可以得到验证），然后找只有一个未知数的行或列，根据校验性质确定该未知数，这样不断做下去，就能求出所有未知数。但要注意，因为其利用的是编码中1的个数的奇偶性作为依据，所以一般不能发现偶数位错误。
针对这道题目，采用奇校验，则校验码中1的个数应为奇数，在供选择的答案中，只有校验码11010110中1的个数为5是奇数，其他3个校验码中1的个数均为偶数，所以答案应该是B。
【例1-12】 对于16位的数据，需要 （1） 个校验位才能构成海明码。在某个海明码的排列方式D9D8D7D6D5D4P4D3D2D1P3D0P2P1中，Di（0≤i≤9）表示数据位，Pj（1≤j≤4）表示校验位，数据位D8由 （2） 进行校验。
（1）A．3 B．4 C．5 D．6
（2）A．P4P2P1 B．P4P3P2 C．P4P3P1 D．P3P2P1
【解析】
这一类型的题目考查的知识点是数据的海明码校验。
海明码是利用奇偶性来检错和纠错，通过在n个数据位之间插入k个校验位，扩大数据编码的码距。
若能纠正1位错，k个校验位可以有2k个编码，其中一个用以表示数据无差错（即奇偶测试位G4G3G2G1全为真），而剩下2k–1个编码则可用来指示哪一位数据出错了。由于n个数据位和k个校验位都有可能出错，因此k必须满足

海明码的编码规则：
设k个检验位为PkPk–1…P1，n个数据位Dn–1Dn–2…D0，产生的海明码为Hk+nHk+n–1…H1，则有Pi在海明码的第2i–1位置（即分别占据1、2、4、8、…位置），即Hj=Pi，j=2i–1；数据位则依次从低到高占据海明码中剩下的位置。
海明码中的任一位都是由若干检验位来校验的。其对应关系如下：被校验的海明位的下标等于所有参与校验该位的校验位的下标之和，而校验位则由其自身来校验。例如，对8位数据位D7D6…D0进行海明校验，需要4位校验位（23–1=7，24–1=15>8+4），令其为P4P3P2P1。生成海明码H12H11…H1，则编码过程如下。
（1）确定D与P在海明码中的位置，即
H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1
D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1
（2）确定校验关系，如表1-2所示。
表1-2中最后一列对应关系表示P4P3P2P1中哪些位参与了校验：1表示该校验位参与了校验，0表示没用到该校验位。
表1-2 海明码的校验关系表
海 明 码
下 标
校 验 位 组
对应关系P4P3P2P1
H1（P1）
1
P1
0001
H2（P2）
2
P2
0010
H3（D0）
3=1+2
P1，P2
0011
H4（P3）
4
P3
0100
H5（D1）
5=1+4
P1，P3
0101
H6（D2）
6=2+4
P2，P3
0110
H7（D3）
7=1+2+4
P1，P2，P3
0111
H8（P4）
8
P4
1000
H9（D4）
9=1+8
P1，P4
1001
H10（D5）
10=2+8
P2，P4
1010
H11（D6）
11=1+2+8
P1，P2，P4
1011
H12（D7）
12=4+8
P3，P4
1100
（3）确定校验位的取值。从表1-2中可以分别列出P4、P3、P2、P1参与校验的位：
P1校验：P1，D0，D1，D3，D4，D6。
P2校验：P2，D0，D2，D3，D5，D6。
P3校验：P3，D1，D2，D3，D7。
P4校验：P4，D4，D5，D6，D7。
若使用偶校验，则

若使用奇校验，则各位取偶校验值的反。
（4）检测错误。只需计算

若采用偶校验，则G1～G4值为全0时，数据正确（奇校验则应为全1）。当G4G3G2G1不全为0时，则说明发生了差错。例如，当G4G3G2G1=0101时，从表1-2中对应关系找到P1P3对应H5即匹配项D1，即D1位出错，对其求反即可纠正该错误。
解答此类题目的一般思路是对n个数据位之间插入k个校验位，必须满足：

同时对表1-2要会自己推导，以此确定校验关系。
针对这道题目，当n=16时，k=5。数据位D8对应的海明位置为H13，而其下标13=8+4+1，对应检验位P4P3P1，所以答案应该是（1）C，（2）C。
【例1-13】 码是一些码字组成的集合。一对码字之间的海明距离是 （1） ，一个码的海明距离是所有不同码字的海明距离的 （2） 。如果要检查出d位错，那么码的海明距离是 （3） 。如果信息长度为5位，要求纠正1位错，按照海明编码，需要增加的校验位是 （4） 。
（1）A．码字之间不同的位数 B．两个码字之间相同的位数
C．两个码字的校验和之和 D．两个码字的校验和之差
（2）A．平均值 B．最大值 C．最小值 D．任意值
（3）A．d–1 B．d+1 C．2d–1 D．2d+l
（4）A．3 B．4 C．5 D．6
【解析】
这一类型的题目考查的知识点是数据的海明码校验。
校验码的抗干扰能力取决于码组之间的距离。两个等长码之间对应位不同的数目称为这两个码组的海明距离，简称码距。
设有任意分组码，如果要在码组内检测或纠正错误，需要保证码距的最小距离。
（1）检测e个随机错误，则要求码的最小距离为

（2）纠正t个随机错误，则要求码的最小距离为

（3）纠正t个随机错误，同时检测e（e>t）个随机错误，则要求码的最小距离为

海明码是可以纠正一位随机错误的差错检测纠错码。通过在数据代码上加入若干冗余位组成码字。在传输过程中，发送方发送足够的冗余位，使接收方能够检测并纠正每个数据块中的单个位错。设有n位信息位，增加k位冗余位，可以组成n＋k位的码字，检错或纠错时，则要求下面的关系式成立，即

解答此类题目的一般思路是熟练掌握海明码校验的具体方法，同时要理解其含义，还要理解和掌握相关知识点。
针对这道题目，一对码字之间的海明距离表示的是码字之间不同的位数，一个码的海明距离是所有不同码字的海明距离的最小值。如果要检查出d位错，那么码的海明距离是d+1。如果信息长度为5位，要求纠正1位错，按照海明编码，需要增加的校验位应该满足n＋k＋l≤2k，因此是4。所以答案应该是（1）A，（2）C，（3）B，（4）B。
【例1-14】 为了进行差错控制，必须对传送的数据帧进行校验。在局域网中广泛使用的校验方法是 （1） 校验。CRC-16标准规定的生成多项式为G(X )=X16+X15+X2+l，它产生的校验码是 （2） 位，接收端发现错误后采取的措施是 （3） 。如果CRC的生成多项式为G(X )=X4+X+1，信息码字为10110，则计算出的CRC校验码是 （4） 。
（1）A．奇偶（Parity） B．海明（Hamming）
C．格雷（Gray） D．循环冗余（Cyclic redundancy）
（2）A．2 B．4 C．16 D．32
（3）A．自动纠错 B．报告上层协议
C．自动请求重发 D．重新生成原始数据
（4）A．0100 B．1010 C．0111 D．1111
【解析】
这一类型的题目考查的知识点是循环冗余码校验。
循环冗余检验是一种十分常用的检错技术，能检测多位差错。在数据传输过程中，数据M(X )一方面直接输出到通信线路上；另一方面在时钟脉冲的作用下，逐位进入CRC校验电路，并随着数据一同传输给接收方。CRC的检错能力很强，比较简单，在局域网中有广泛的应用。
任何一个由二进制数位串组成的代码，都可以和一个只含有“0”和“1”两个系数的多项式建立一一对应的关系。例如，如果要发送的信息M(X )的二进制代码为1010111，则多项式为

即

由此可见，k位要发送的信息位，可对应于一个k–1次多项式。如果传输的码字总长为n位，则n=k+r，r是冗余位的位数。在数据传输过程中，发生器生成一个多项式G(X )，当G(X )为n位时，其冗余位最多为n–1位，对应一个（n–1）次多项式R(X )。在校验时，发送方和接收方根据的原理，在发送方将M(X )与R(X )一起发送时，则接收端满足，所以接收端只要满足余数为0即可。
当接收端发现错误后，采取自动请求重传的措施来保证接收正确。
CRC校验具有很强的检错能力，实际中采用硬件电路实现，比较简单，在局域网中有广泛的应用，如在以太网中就是使用CRC来校验数据的传输是否有差错的，通常采用CRC-32生成多项式作为标准校验式。
为了能对不同场合下的各种错误模式进行校验，主要有4种不同的CRC生成多项式的国际标准。
CRC-CCITT G(X ) = X16+X12+X5+l
CRC-16 G(X ) = X16+X15+X2+l
CRC-12 G(X ) = X12+X11+ X3+X2+X+l
CRC-32 G(X ) = X32+X26+X23+ X22+X16+X12+ X11+X10+X8+X7+X5+X4 +X2+X+1
解答此类题目的一般思路是熟练掌握CRC校验的具体方法，同时要理解其含义，还要理解和掌握相关知识点。
针对这道题目，在局域网中广泛使用的校验方法是循环冗余码校验。CRC-16标准规定的生成多项式为G(X )=X16+X15+X2+l，它产生的校验码是16位，接收端发现错误后采取的措施是自动请求重发。如果CRC的生成多项式为G(X )=X4+X+1，信息码字为10110，则计算出的CRC校验码是1111。所以答案应该是（1）D，（2）C，（3）C，（4）D。
1.4 本章小结
关于计算机的数制表示（二进制、八进制、十进制和十六进制等）及其转换关系，作为基本技能，主要在程序员级别中考核，在软件设计师级别很少直接考核，而是融合在其他知识点中。
关于计算机中二进制数的运算方法，特别是补码的加减运算，能用双符号位法或进位判别法判断定点数运算结果是否溢出；掌握基本的逻辑运算，特别要熟练掌握异或运算。这部分内容在软件设计师级别也很少直接考核，而是放到程序员级别进行考核。
本章主要要求考生掌握带符号定点数据（纯整数和纯小数）的原码、反码、补码和移码表示，把握它们之间的相同点和不同点（符号位、数值位、0的表示方法），以及各自所表示的数的范围；掌握浮点数（实数）的表示，包括浮点数的组成和规格化，浮点数的加、减、乘、除运算规则；掌握奇偶校验编码的形成、校验原理和分类，掌握海明校验和循环冗余校验码的功能、形成及校验原理，校验码的计算。在软件设计师级别的考试中主要涉及这部分的内容。
1.5 全真模拟训练
1．对于R进制数，在每