第2章 数据的表示和运算

2.1 数值与编码

2.1.1 进位计数制及其相互转换

在计算机系统内部，所有的信息都是用二进制进行编码的，原因如下：

1）二进制只有两种状态，所以有两个稳定状态的物理器件就可以表示二进制数的每一位，如利用高低电平和电荷的正负极性都可以很方便的表示0和1

2）二进制位1和0正好与逻辑值“真”和“假”对应，为计算机实现逻辑运算和程序中的逻辑判断提供了便利条件

3）二进制的编码和运算规则很简单，通过逻辑门电路能方便的实现算术运算

1.进位计数法

进位计数法是一种计数方法。常用的进位计数法有十进制、二进制、八进制和十六进制等

在每种进位计数法中，所用到的不同数码的个数称为基数，如十进制的基数为10（0～9）

在每种进位计数法中，每个数码所表示的数值等于本身乘以一个与它所在数位有关的常数，这个常数称为位权，一个进位数的数值大小就是它的各位数码按权相加

2.不同进制之间的相互转化

（1）二进制转八进制和十六进制

对于一个混合二进制数（包含整数部分和小数部分），转换时以小数点为界

整数部分，从小数点开始往左数，将一串二进制数分为3位（八进制）一组或4位（十六进制）一组，不够则用0补齐

小数部分，从小数点开始往右数，将一串二进制数分为3位（八进制）一组或4位（十六进制）一组，不够也用0补齐

然后分别用对应的八进制数或十六进制数取代

以二进制数1111000010.01101为例,转换为八进制数为1702.32

分组	001	111	000	010	.	011	010
用八进制取代	1	7	0	2	.	3	2

八进制转16进制可以先转换为2进制再转换为16进制，八进制或十六进制转二进制时做上述流程相反操作即可

（2）任意进制数转换为十进制数

用各位数码与它们的权值相乘，再把乘积相加，就得到了一个十进制数（非常简单有没有？）这种方法称为按权展开相加法

（3）十进制数转换为任意进制数

对整数部分采用除基取余法，对小数部分采用乘基取整法

2.1.2 真值和机器数

带“+”或“-”符号的数称为真值。真值是机器数所代表的实际值

在计算机中，通常采用数的符号和数值一起编码的方法来表示数据。常用的有原码、补码和反码表示法。这几种表示法都将数据的符号数字化，通常“0”代表“正”，用“1”表示“负”。这种把符号“数字化”的数称为机器数

2.1.3 BCD码

用4位二进制数来表示一位十进制数0～9这10个数码

1）8421码（最常用）

它是一种有权码，设其各位的值位，b3,b2,b1,b0,权值从高到低依次为8，4，2，1，D=8b3+4b2+2b1+1b0,如8=1000

若两个8421码相加大于1001，即9，则需要加6修正，并向高位进位，可以在首次相加或修正时产生

如：（9+4=13）0100+1001=1101+0110=10011

2）余3码

它是一种无权码，是在8421码的基础上加上（0011）形成的，因每个数都多余“3”，因此称为余3码。如8->1011

3）2421码，它也是一种有权码，权值从高到低分别为2，4，2，1，特点是大于等于5的4位二进制数中最高位为1，小于5的最高位为0。如5->1011

2.1.4 字符和字符串

由于计算机智能识别和处理二进制代码，所以字符都必须按照一定的规则用一组二进制编码来表示

1.字符编码ASCII码

目前，国际上普遍采用一种字符系统是7位二进制编码的ASCII码（每个字节的最高位保持为0，可用于传输时的奇偶校验位）

ASCII码编码值	0-31	32-126	127	32
代表含义	控制字符（用于通信控制或设备的功能控制）	95个可印刷字符	DEL	空格SP

2.汉字的表示和编码

目前最新的汉字编码是2000年公布的国家标准GB 18030，收录了27484个汉字，编码标准采用1B、2B、4B

汉字的编码包括汉字的输入编码、汉字内码、汉字字形码三种，它们是计算机中用于输入、内部处理和输出三种用途的编码

区位码是国家标准局与1980年颁布、1981年实施的标准，它用两个字节表示一个汉字，每个字节用7位码，并将汉字和图形符号排在一个94*94的二维代码表中。区位码是四位十进制数，前两位是区码，后两位是位码，所以称为区位码

国际码将十进制的区位码转换为十六进制数后，再在每个字节上加上20H，国标码两字节的最高位都是0，ASCII码最高位也是0，为了方便计算机区分中文字符和英文字符，将国际码两字节的最高位都改为“1”，这就是汉字的内码

区位码和国际码都是输入码，它们和汉字内码的关系（十六进制）如下：

国标码 = （区位码）16进制 + 2020H

汉字内码 = （国标码）16进制 +8080H

2.1.5 校验码

校验码是指能够发现指能够发现或能够自动纠正错误的数据编码，也称检错纠错编码

校验码的原理是通过增加一些冗余码，来检验或纠错码

通常，编码是由许多码字构成，任意两个合法码字之间最少变化的二进制位数，称为数据校验码的码距，当码距大于等于2时开始具有检错能力，检错能力总是大于等于纠错能力

1.奇偶校验码

在原编码上加一个校验位，它的码距等于2，可以检测出一位错误（或奇数位错误），但是无法检测偶数位错误，无法确定出错位置，增加的冗余位称为奇偶校验位

奇偶校验实现的方法：

奇校验方法：整个校验码（有效信息位和校验位）“1”的个数为奇数：如1001101 的奇校验为11001101

偶校验方法：整个校验码（有效信息位和校验位）“1”的个数为偶数：如1001101 的偶校验为01001101

缺点在于奇偶校验只能发现数据代码只能够奇数位的出错情况，但不能纠正错误，常用于对存储器数据的检验或传输数据的检查

2.海明校验码

译作汉明码，是广泛采用的一种校验码，它实际上是一种多重奇偶校验码

实现原理：在有效信息中加入几个校验位形成海明码，并把海明码的每个二进制位分配到几个奇偶校验组中，当某一位出错时，就会引发有关的几个校验位的值发生变化，不但可以发现错位，还能指出错位的位置，为自动纠错提供依据

根据纠错理论得：L-1=D+C且D>=C,L为码距，D为检测错误的位数，C为纠正错误的位数

例子：在n=4、k=3时，求1010的海明码

（1）确定海明码的位数

n+k<=2的k方-1，即4+3<=8-1,n和k有效，设信息位为D4D3D2D1，校验位为P3P2P1，对应海明码为H7H6H5H4H3H2H1

（2）确定校验分布

规定校验Pi分布在海明位号位2的（i-1）次方的位置上，其余各位为信息位

H7	H6	H5	H4	H3	H2	H1
D4	D3	D2	P3	D1	P2	P1
1	0	1	0	0	1	0

（3）分组以形成校验关系

需满足的条件：校验数据位的海明位号等于校验该数据位的各校验位海明位号之和

	第一组	第二组	第三组
	P1（H1）	P2（H2）	P3（H4）
校验D1（H3）	P1	P2
校验D2（H5）	P1		P3
校验D3（H6）		P2	P3
校验D4（H7）	P1	P2	P3
Pi的值	0	1	0

（4）校验位取值

P1=D1异或D2异或D4=0

P2=D1异或D3异或D4=1

P3=D2异或D3异或D4=0

即对应的海明码为1010010

（5）海明码校验原理

每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查，构成k个校验方程

S1=P1异或D1异或D2异或D4

S2=P2异或D1异或D3异或D4

P3=P3异或D2异或D3异或D4

若S3S2S1的值为“000”，则说明无错：否则说明出错，且这个数就是错误位的位号，若S3S2S1=001，则说明第一位出错，即H1出错，取反可以达到纠错的目的

3.循环冗余校验（CRC）码

基本思想：在K位信息码后再拼接R为的校验码，整个编码的长度为N位，因此这种编码又称（N，K）码，CRC码基于线性编码理论，在发送端，将要传送的K位二进制信息码左移R位，将它与生成多项式G(x)做模2除法，生成一个R为的校验码，并附在信息码后构成一个新的二进制码（CRC码），共K+R位。在接收端，利用生成多项式是对接收到的编码做模2除法，以检测和确定出错的位置，若无错则整除，其中生成多项式是接收端和发送端的一个约定

任意一个二进制数码都可以用一个系数仅为1和0的多项式与其对应生成多项式G(x)的最高次幂为R，转换为对应的二进制数有R+1位。

例子：设生成的多项式为G(x)=x的三次方+x的平方+1，信息码为101001，求对应的CRC码

解：R=最高次幂=3，K=信息码长度=6，N=K+R，G(x)对应的二进制数：1101

（1）移位

101001000

（2）相除

一位之后除以二进制数，取余作为校验码：001

（3）检错和纠错

接收端收到的CRC码，用生成多项式G(x)做模2除法，若余数为0，则码字无错

若接收端收的CRC码为C9C8C7C6C5C4C3C2C1=101001011，将其与1101进行模2除法，得到的余数为010，则说明C2出错，将C2取反即可