计算机组成与系统结构课件：计算机系统中的数据表示

计算机系统中的数据表示2.1概述2.2定点数2.3浮点数2.4BCD码2.5非数值数据2.6检错与纠错码

2.1概述

2.1.1数的进制及转换

常见的进位计数制有十进制、二进制、八进制和十六进制。十进制数中有0~9十个数码,其计数特点及进位原则为“逢十进一”。十进制的基数为10,位权为10i(i是整数)。十进制数的后面常用字母D标记或不加标记。计算机中常用的计数制还有二进制、八进制、十六进制。

任何一种进位计数制表示的数都可以写成按权展开的多项式之和,即任意一个r进制数N可表示为

其中,Di为该数制采用的基本数码,ri

是权,r是基数。数值数据是表示数量多少和数值大小的数据,即在数轴上能找到其对应点的数据。

各种数值数据在计算机中表示的形式称为机器数。机器数对应的实际数值称为数的真值。

2.1.2无符号数与有符号数的定义

1.无符号数

所谓无符号数,即没有符号的数,数中的每一位均用来表示数值。所以8位二进制无符号数所表示的数值范围是0~255,而16位无符号数的表示范围为0~65535。

2.有符号数

由于机器无法直接识别“+”(正)、“-”(负)符号,而“正”“负”恰好是两种截然不同的状态,因此若用“0”表示“正”,用“1”表示“负”,则符号可被数字化,再按规定将符号放在有效数字的前面就组成了有符号数。

2.1.3定点数与浮点数的定义

1.定点数

在机器数表示中,若约定小数点的位置固定不变,则称为定点数。有两种形式的定点数,即定点整数(纯整数,规定小数点在数据最低有效数位之后)和定点小数(纯小数,规定小数点在数据最高有效数位之前),如图2.1所示。图2.1有符号定点数的表示形式

2.浮点数

基数为2的数F的浮点表示为

其中,M称为尾数,E称为阶码。尾数为带符号的纯小数,阶码为带符号的纯整数。

按式(2.2)表示的数据既可以是纯整数,也可以是纯小数,还可以是同时含有整数和小数的数据,其小数点的位置是不固定的,故称为浮点数。计算机中常用的一种浮点数的编码格式如图2.2所示,其中数符(即数据的符号)就是尾符(即尾数的符号)。图2.2浮点数的编码格式之一

2.2定点数

2.2.1原码原码是机器数中最简单的一种表示形式,其符号位为0表示正数,符号位为1表示负数,数值位即真值的绝对值。

1.整数原码的定义

根据图2.1(a),若整数用二进制n位表示,则整数原码的定义为

式中,X为真值,n-1为整数数值位的位数。

原码可用定义表示,也可用符号位后面紧跟数的绝对值表示。

例2.1当X=+35或X=-35时,若采用8位二进制编码,其原码如何表示?

解当X=+35时,有

当X=-35时,有

从本例可以看到,符号位总是在最高位。原码又称作带符号的绝对值表示,即在符号的后面跟着的就是该数据的绝对值。

2.小数原码的定义

根据图2.1(b),若小数用二进制n位表示,则小数原码的定义为

根据式(2.4),纯小数的原码可以表示为

值得注意的是,在计算机中小数点是隐含的,是不用出现的,上面编码中出现小数点是为了强调小数点的位置。在本书各章节中,所有编码中若出现小数点,其作用与此处相同,都仅仅是为了提示。

例2.2若纯小数X=0.46875或X=-0.46875,试用包括符号位在内的8位定点原码表示。

解当X=0.46875时,有

当X=-0.46875时,有

3.原码的特点

(1)数值原码表示法简单直观,但加减运算很麻烦。

(2)对于数值0,用原码表示不是唯一的。以8位原码表示,有

(3)n位原码(包括一位符号位)纯整数可表示的数值范围为-(2n-1-1)~+(2n-1-1),纯小数可表示的数值范围为-(1-2-(n-1))~+(1-2-(n-1))。

2.2.2补码

1.补数的概念

在日常生活中,常会遇到补数的概念。例如,当前时钟指针指示在6点,欲使它指示3点,既可按顺时针方向将分针转9圈,也可按逆时针方向将分针转3圈,其结果是一致的。由于时钟的时针转一圈能指示12个小时,因此时钟指针两个方向转动产生的效果在数学上称为模12运算,写作mod12。

2.补码的定义

1)整数补码的定义根据图2.1(a),若整数用二进制n位表示,则整数补码的定义为

由式(2.5)可以看到,对正数来说,补码与原码的定义完全一样。

2)小数补码的定义

若小数用二进制n位表示,则小数补码的定义为

根据式(2.6),纯小数的补码同样可以表示为

同样地,小数点是隐含的。

例2.4若纯小数X=0.46875或X=-0.46875,试用包括符号位的8位定点补码表示。

解当X=0.46875时,有

对于负数纯小数,构成补码表示所采用的方法与整数一样。因此,当X=-0.46875时,[X]补=1.1000100。

3.补码的特点

(1)n位补码表示的整数数值范围为-2n-1~+(2n-1-1),n位补码表示的小数数值范围为-1~+(1-2-n+1)。

(2)0的表示是唯一的。以8位小数编码为例,有

(3)变形码。当模数为4时,可形成双符号位补码,如X=-0.1001B,对mod22而言,有

这种双符号位补码又叫作变形补码,它在阶码运算和溢出判断中有其特殊作用。

(4)求补运算。许多处理器中设置有求补指令,其功能是对操作数取负数(即正数变负数,负数变正数)。可以采用上述的负数补码的3种编码方法之一实现。

(5)简化加减法。利用补码实现两数相加是很方便的,补码加法的运算规则为

即两数和的补码就等于两数补码之和。

因此,减法运算就可以用加法运算来实现,即

这样在运算器中就可以不设置减法器,从而简化了运算器的结构。

(6)算术或逻辑左移。对补码表示的数值做算术或逻辑左移一位(即编码各位依次向左移动一位,最高位移出,最低位补0),如果移位结果没有超出所规定的数值范围,则相当于该数值乘2。

(7)算术右移。对补码表示的数值做算术右移一位(即编码各位依次向右移动一位,最低位移出,最高位保持原符号不变),相当于该数值除以2。

2.2.3反码

反码通常用来作为由原码求补码或者由补码求原码的中间过渡。

1.反码的定义

1)整数反码的定义

整数反码的定义为

2)小数反码的定义

小数反码的定义为

2.2.4移码

1.移码的由来

当真值用补码表示时,由于符号位和数值部分一起编码,与习惯上的表示法不同,因此人们很难从补码的形式上直接判断其真值的大小。例如:

十进制数X=+31,对应的二进制数为+11111,若用8位表示,则[X]补=00011111；

十进制数X=-31,对应的二进制数为-11111,若用8位表示,则[X]补=11100001。

上述补码表示中,从代码形式看,符号位也是一位二进制数。如果按这8位二进制代码比较其大小,会得出11100001>00011111,而实际情况恰恰相反。

2.移码的定义

由于移码多用于浮点数中表示阶码,均为整数,因此这里只介绍定点整数的移码表示。当用包括符号位在内的n位字长时,整数移码的定义为

要获得整数的移码表示,可以利用定义计算,也可以先求出该数的补码后将符号位取反。

3.移码的特点

(1)移码就是在其真值上加一个常数2n-1。移码在数轴上所表示的范围恰好对应其真值在数轴上的范围向轴的正方向移动2n-1个数据,如图2.3所示。图2.3移码在数轴上的表示

(2)移码与补码的关系。由图2.4可知,移码与补码间的关系十分密切,只要将补码的符号位取反,补码就转换成了相应的移码;同样,只要将移码的符号位取反,移码就转换成了相应的补码。进而可以想到,只要字长相同,补码与移码所能表示的数值范围是相同的。图2.4移码与补码的关系

(3)移码码值的大小反映了数值的大小,因此,正数移码的码值一定大于负数移码的码值。也就是说,大码值所表示的数值一定大于小码值所表示的数值。

由于具有上述突出优点,移码目前已被广泛采用。

2.2.5不同编码的比较

原码表示很直观。若采用原码做乘除运算,可取其绝对值(原码的数值部分)直接运算,并按同号相乘除取正,异号相乘除取负的原则,单独处理符号位,比较方便。但原码加减运算时,其运算比较复杂。例如,当两个操作数符号不同且要作加法运算时,先要判断两个数的绝对值的大小,然后用绝对值大的数减去绝对值小的数,结果的符号以绝对值大的数为准,运算步骤既复杂又费时,且本来是加法运算却要用减法器实现。

而机器数采用补码,找到一个与负数等价的正数来代替该负数,即可用加法代替减法操作,这样在计算机中就可以只设加法器。但是根据补码的定义,在形成补码的过程中又出现了减法,因此引入了反码,作为由原码求补码或者由补码求原码的中间过渡,这样由真值通过原码求补码就可避免减法运算。

因此,原码、反码、补码、移码的特点可归纳如下:

(1)当真值为正时,原码、补码和反码的表示形式均相同,即符号位用“0”表示,数值部分与真值相同。

(2)当真值为负时,原码、补码和反码的表示形式不同,但其符号位都用“1”表示,而数值部分的关系为:反码是原码“每位取反”,补码是反码“加1”,补码是原码“求反加1”。

(3)移码较为特殊,当符号位为“0”时,表示真值为负数;当符号位为“1”时,表示真值为正数。移码与补码编码仅符号位相反。

表2.1列出了8位字长的二进制编码与无符号整数及定点整数的原码、补码、反码和移码所代表真值的对应关系。

2.3浮点数

2.3.1浮点数的表示方法由于计算机字长的限制,当需要表示的数据有很大的数值范围(如电子的质量为9×10-28克,太阳的质量为2×1033克)时,它们不能直接用定点小数或定点整数表示,而必须用浮点数表示。由于计算机采用二进制,所以浮点数的一般表示形式为式(2.2)。

例如,二进制数F=11.0101,用浮点数可表示为下列不同形态,即

其中,尾数与阶码均用二进制数表示,基数(为2)用十进制数表示。这里可以看到,一个包含整数与小数的数据用浮点数表示时有多种形态,那么计算机中采用哪种形态来表示这个浮点数呢?

1.浮点数的编码表示

根据浮点数的一般表示式(2.2),只要确定了尾数M和阶码E(基数是固定值),浮点数即被确定。但同一个浮点数又有多种表现形态,如上述例子,所以需要对M和E的形态做出合理选择,浮点数才能在计算机中有效编码。

浮点数编码的规则如下:

(1)尾数M必须为小数,用n+1位有符号定点小数表示,可以采用的编码有原码、补码。阶码E必须为整数,用k+1位有符号定点整数表示,可以采用的编码有原码、补码、移码。浮点数编码位数为m=(n+1)+(k+1)。

(2)浮点数编码格式有多种,使用较多的格式如图2.2和图2.5所示,格式的选择可由计算机设计人员决定。图2.5浮点数的编码格式之二

需要强调的是:

(1)阶码是整数,其位数k+1决定了浮点数表示的数值范围,也就是决定了数据的大小,或小数点在数据中的真实位置。阶符决定阶码的正负。

(2)尾数是小数,其位数n+1决定了浮点数的精度。如果尾数采用小数且位数n足够长,则当浮点数运算需要对尾数运算结果舍入时,造成的数据精度损失会比较小。

(3)尾数的符号表示浮点数的正负。

2.非规格化浮点数

当对尾数M只要求是小数而无其他限制时,此时的浮点数被称为非规格化浮点数。设浮点数为非规格化数,阶码数值位取k位,阶符为1位,且采用补码表示,尾数数值位取n位,尾符为1位,同样采用补码表示,则阶码和尾数可以表示的数值范围如表2.2所示。

此时,在数轴上表示的非规格化浮点数范围如图2.6所示。因为非规格化浮点数的尾数可以为0,也就是非规格化浮点数可以为0,因此非规格化浮点数范围为图2.6非规格化浮点数的数值范围

3.规格化浮点数

由于非规格化浮点数对小数形式的尾数没有进一步的限制,因此造成同一数据有不同的编码,使数据表示的通用性变差。为了使有限字长的二进制尾数能表示更多的有效数位,同时使浮点数有统一的表示形式,浮点数通常采用规格化形式来表示。

所谓规格化浮点数,就是将尾数的绝对值限定在规定的数值范围内,即1/2≤M<1。要使尾数的绝对值在此范围内,通过改变小数点的位置(相应地改变阶码)便可以做到。

若尾数M用补码表示,则当M≥0时,规格化尾数的形式必须为

其中,×为任意二进制值。

当M<0时,规格化尾数的形式必须为

其中,×为任意二进制值。

根据规格化浮点数的定义,可以得到规格化尾数的数值范围如表2.3所示。

对于规格化浮点数来说,其阶码所表示的数值范围与非规格化浮点数的是一样的。因此,可以确定规格化浮点数所能表示的数值范围如图2.7所示。图2.7规格化浮点数的数值范围

比较图2.6和图2.7可以发现,非规格化浮点数和规格化浮点数所能表示的数值范围的主要不同是绝对值最小的有效数值。由图2.7可知,规格化浮点数的数值范围如下:

当浮点数阶码大于最大阶码时,称为“上溢”,此时机器停止运算,进行溢出中断处理;当浮点数阶码小于最小阶码时,称为“下溢”,此时“溢出”的数的绝对值很小,通常将尾数各位强置为零,按机器零处理,机器可以继续运行。图2.7表示了浮点数所能表示的数值范围及溢出的情况。

一旦浮点数的位数确定后,不同的阶码和尾数位数划分将直接影响浮点数的表示范围和精度,所以需要合理分配阶码和尾数的位数。利用数值的浮点数表示,可实现用有限字长的二进制编码表示更大的数值范围。

4.规格化处理

浮点数在运算前和运算后,若其尾数不是规格化数,就要通过修改阶码并同时左右移动尾数使其变成规格化数。将非规格化数转换成规格化数的过程叫作规格化。

当尾数M用二进制补码编码时,规格化数应符合[M]补=0.1××…×和[M]补=1.0××…×的规定。规格化时,尾数左移1位,阶码减1,这种规格化叫作向左规格化,简称左规;尾数右移1位,阶码加1,这种规格化叫作向右规格化,简称右规。

5.定点数和浮点数的比较

(1)当浮点计算机和定点计算机中数据的位数相同时,浮点数的表示范围比定点数大得多。

例如,对于16位二进制编码,无符号数的范围为0~65535,补码定点整数的范围为-32768~+32767。对于浮点数,可有多种表示方案。假定阶码7位(含阶符1位),用移码表示,尾数9位(含数符1位),用补码表示,则该非规格化浮点数所能表示的数值范围是-263~+(1-2-8)×263。可见,同样字长的浮点数所能表示的数值范围要大得多。

(2)当浮点数为规格化数时,其精度比相同位数的定点数高。

(3)浮点数运算分为阶码部分和尾数部分,而且运算结果要求规格化,故浮点运算步骤比定点运算步骤多,运算速度比定点低,运算电路比定点复杂。

(4)在溢出的判断方法上,浮点数对规格化数的阶码进行判断,而定点数对数值本身进行判断。

总之,浮点数在数的表示范围、数的精度、溢出处理和程序编程方面(不取比例因子)均优于定点数。但在运算规则、运算速度及硬件成本方面又不如定点数。因此,究竟选用定点数还是浮点数,应根据具体应用综合考虑。一般来说,通用的大型计算机大多采用浮点数,或同时采用定点数和浮点数;小型、微型及某些专用机、控制机则大多采用定点数。当需要作浮点运算时,可通过软件实现,也可外加浮点扩展硬件(如协处理器)来实现。

例2.8将十进制数x=+13/128写成二进制定点数和浮点数(尾数数值部分取7位,阶码数值部分取7位,阶符和数符各取1位,阶码采用移码,尾数用补码表示),并分别写出该数的定点数和浮点数的编码(采用图2.2所示的编码格式)。图2.8例2.8中浮点数的表示形式

例2.9设浮点数字长为16位,其中阶码为6位(含1位阶符),尾数为10位(含1位数符),阶码用移码,尾数用补码,写出十进制数x=-(53/512)对应的规格化浮点数编码(采用图2.5所示的编码格式)。图2.9例2.9中浮点数的表示形式

例2.10已知规格化浮点数字长16位,其中7位阶码(含一位阶符),用移码表示,9位尾数(含一位数符),用补码表示,其格式及编码值如图2.10所示,请写出该数的真值。图2.10例2.10中浮点数的编码

解该浮点数尾数为1.01011001,真值为-0.10100111。阶码为1000111,真值为7,因此浮点数的真值为

2.3.2IEEE754标准

1985年,IEEE发表了一份关于单精度和双精度浮点数的表示标准,这个标准官方称为IEEE7541985。以后又不断加以发展,SUN公司于2005年推出《数值计算指南》(中译本名),对该标准进行了更加详细和深入的讨论,给出了多种格式及程序。因此,《数值计算指南》更加全面、实用。目前IEEE754标准已获得了广泛的认可,并已用于当前所有处理器和浮点协处理器中。

IEEE754规定了单精度和双精度两种基本的浮点格式以及双精度扩展等多种浮点格式。常用的IEEE754格式参数如表2.4所示。

1.单精度浮点数

1)编码IEEE754标准规定,单精度浮点数的真值一般表示为

IEEE754单精度浮点数的编码格式如图2.11所示。其编码格式由三个字段构成:数符s为1位,尾数编码f为23位,阶码编码e为8位(含1位阶符),每字段的位模式如表2.5所示。图2.11IEEE754单精度浮点数的编码格式

由表2.5可以看到,正规数尾数有效数字的前导位(小数点左侧的位)为1,与23位尾数一起提供了24位的精度。次正规数有效数字的前导位为0,在IEEE754标准中,单精度格式次正规数也称为单精度格式非规格化数。表中符号u为任意值。

2)说明

根据上述描述,可以得到关于IEEE754标准单精度浮点数的如下结论:

(1)由于规定阶码真值E=e-127,并且0<e<255(即规定编码e在+1~+254内为正规数),因此阶码真值E的取值范围为-126~+127。

(2)所能表示的正规数范围:正数为+2+127×(1+1-2-23)~+2-126×(1+0),负数为-2+127×(1+1-2-23)~-2-126×(1+0)。

(3)当e=0或e=255时,在IEEE754标准中表示特殊的数。

例2.11利用IEEE754标准将十进制数176.0625表示为单精度浮点数。．

解首先将该十进制数转换成二进制数,有

对二进制数规格化,有

(1)单精度浮点数的23位尾数f为01100000001000000000000;

(2)单精度浮点数阶码真值E=e-127=7,即e=(7+127)10=(134)10=(10000110)2,则e就是阶码编码;

(3)将(176.0625)10表示为IEEE754标准的单精度浮点数,有

例2.12若浮点数x的IEEE754编码为(41360000)16,求其浮点数的十进制值。解将十六进制数展开为二进制数,有

2.对双精度浮点数的说明

下面简要说明一下IEEE754标准双精度浮点数。

(1)阶码真值E的取值范围为-1022~+1023,将其偏移+1023即得编码e,e编码值为+1~+2046。

(2)双精度浮点规格化数表示N为

(3)所能表示的规格化数范围:正数为+2+1023×(1+1-2-52)~+2-1022×(1+0),负数为-2+1023×(1+1-2-52)~-2-1022×(1+0)。

(4)当e=0或e=2047时,在IEEE754标准中表示特殊的数。

2.4BCD码

在计算机中,采用4位二进制编码来表示1位十进制数,这种编码称为BCD码(Binary-CodedDecimal,二十进制数)。4位二进制有16种编码,从中取出10种表示十进制数的0~9十个数字,有多种方案。因此有多种BCD码,其中使用最多的是8421码。

在8421码中,表示1位十进制数的4位二进制编码,从最高位到最低位的权值依次为8、4、2、1。因此可用0000、0001、0010、…、1001这十个编码分别表示十进制数0、1、2、…、9,剩余的6个编码对8421码而言是非法的,是不允许出现的。

例如十进制数49,用8421码表示为01001001。

8421码为有权码,即4个二进制位上有确定的权值。其他的有权码还有5421码、2421码、5211码、4311码、8421码等。另外还有无权码,即二进制各位上没有确定的权值,如余3码、格雷码等。

2.5非数值数据

2.5.1ASCII码现代计算机不仅处理数值领域的问题,而且处理大量非数值领域的问题。这样,必然要引入文字、字母以及某些专用符号,以便表示文字语言、逻辑语言等信息。例如,人机交互信息时使用英文字母、标点符号、十进制数以及诸如$、%、+等符号。然而,计算机只能处理二进制数据,上述信息应用到计算机时,都必须表示成二进制数据,即字符信息也要用数据表示,称为符号数据。

ASCII码编码格式如图2.12所示,低4位组d3d2d1d0用作行编码,高3位组d6d5d4用作列编码,可表示128个符号。ASCII编码表见表2.6。图2.12ASCII码的编码格式

字符串是指连续的一串字符。通常方式下,它们占用主存中连续的多个字节单元,每个字节单元存储一个字符。当主存字由2个或4个字节组成时,在同一个主存字中,既可按从低位字节向高位字节的顺序存放字符串内容,也可按从高位字节向低位字节的顺序存放字符串内容。这两种存放方式都是常用方式。

2.5.2汉字编码

英文是一种拼音文字,只需要配备26个字母键,并规定26个字母的编码(比如通用的ASCII码)就能方便地输入英文信息了。汉字字形结构复杂,仅部首就有数百种,汉字的字数也很多,因此汉字的计算机处理技术远比拼音文字复杂。

从ASCII、GB2312—80、GBK到GB18030—2005,这些字符集是向下兼容的,即同一个字符在这些方案中总是有相同的编码,后面的标准支持更多的字符。中英文被统一处理,区分中文、英文的方法是看最高字节的最高位,为0即是ASCII码,为1则为中文(双字节或四字节)。

2.5.3Unicode与UTF-8

为了统一表示世界各国的文字,1993年国际标准化组织公布了国际标准ISO/IEC10646,简称UCS。这一标准为包括汉字在内的各种正在使用的文字规定了统一的编码方案,因此又称为Unicode。Unicode已获得了一些程序设计语言(如Java)和操作系统(如Windows)的支持。

Unicode的基本思路是给每一个字符和符号分配一个永久的、唯一的16位值,称为码点(CodePoint)。例如,汉字“计”的码点为0x8BA1,记为U+8BA1。Unicode系统最多有65536个码点,而全世界的语言大概有20万个符号,因此码点就成为一种稀缺资源,不能随意分配。Unicode的编码空间大概分为六部分,如表2.7所示。其中,ASCII字符的码点定义为0~127,因此ASCII码与Unicode之间的转换规则十分简单。

为此又设计出了Unicode字符集的编码方案,如UTF-8、UCS-2、UTF-16、UCS-4和UTF-32,其中最常用的是UTF-8。UTF-8以8位一个字节为单位,是一种可变长度的编码。它将Unicode的码点编码为1~4个字节,具体编码方案如表2.8所示

例如,汉字“计”的码点为U+8BA1,属于表2.8的第三行范围,编码为三个字节,“计”的UTF-8的编码为E8AEA1,其编码方法如图2.13所示。图2.13汉字“计”的UTF-8编码方法

UTF-8的优点在于:编码0~127分配给了ASCII码,并且用一个字节表示,因此纯ASCII码的字符串也是UTF-8的合法字符串,两者一致,这样原先以ASCII码存储的文件或处理ASCII码的程序,不用改动即可兼容UTF-8;UTF-8编码中的第一个字节指明了这个字符一共有几个字节,若第一个字节最高位是“0”,则该字符只有一个字节,若第一个字节最高位是“1”,则有几个连续“1”就表明该字符有几个字节。后面的字节都以“10”开头,这样在传输或存储中出错时,很容易跳过出错字节,直接找到下一个字符的起始字节,即拥有自同步能力。当前UTF-8在互联网上被广泛使用。

2.6检错与纠错码

元件故障、噪声干扰等各种因素常常导致计算机在传输、存储或处理信息的过程中出现错误。例如,将一位1从部件A传送到部件B,可能由于传送信道中的噪声干扰而受到破坏,以至于接收部件B收到的是0而不是1。为了防止这种错误,可采用专门的逻辑电路对信号进行编码以便于检测错误,甚至校正错误。

2.6.1码距与校验位位数

假设数据有n位,为了具备检错或纠错能力,必须增添k位校验位,则数据加校验位一共有m=n+k位,称为m位码字。

任意两个m位的码字,其对应位不同的数目称为这两个码字的海明码距。设码字x=xm-1xm-2…x0和y=ym-1ym-2…y0,则x与y的海明码距d定义为

例如,两个8位码字为01001000与11001011,其码距为3。求海明码距只需将两个码字异或后看有多少位是1即可。

对于n位数据,所有的2n个编码都是合法编码。而增加k位校验位变成m=n+k位的码字后,在2m个码字中,仍然只有2n个码字是合法的。在这2n个合法码字之间,两两码字之间海明码距的最小值dmin,称为这种编码的海明码距。

编码的检错与纠错能力取决于其海明码距dmin。如果要检测r位错,则编码的码距dmin至少应为r+1,使得一个合法码字的r位出错时不会成为另一个合法码字。而要纠正r位错,则编码的码距dmin至少应为2r+1,使得一个合法码字r位出错时,得到的码字与原合法码字的码距(为r)一定比它与其他合法码字间的码距(大于等于r+1)要小,因此,只要选取与该错误码字码距最小的合法码字作为正确的码字,就实现了纠错。

例如,一种只有4个合法码字的编码为000000、000111、111000、111111,其海明码距为3,则可以纠1位错误。对于非法码字010111来说,码距最近的合法码字为000111,所以000111就是010111的纠错结果。这是假定只出现1位错误的前提下做出的纠错结果。如果允许出现两位错误,比如码字111111变成了010111,则无法纠错,因为没办法判断到底是一位出错还是两位出错,所以无法确定应该纠错为000111还是111111。

对于n位数据,为使其具有纠一位错的能力,增添k位校验位组成m=n+k位编码。在2n个合法的码字中,其m个二进制位中任何一位出错都会得到一个非法码字,从而可以发现错误。为了能纠正这个一位错误,这些非法码字彼此必须是不同的(反之,如果一个非法码字可能从两个合法码字分别错一位得到,则无法纠错)。因此,每个合法码字对应了m个与之码距为1的非法码字,再加上其自身,每个合法码字对应了m+1个码字,则总的码字数目至少为2n×(m+1)个。而m位编码至多有2m种码字组合,因此要满足2m≥2n×(m+1),将m=n+k代入,可得

在确保具有一位纠错能力时,由式(2.16)可求得数据长度n所需的校验位位数k,如表2.9所示。

2.6.2奇偶校验码

例2.13试确定二进制数X=01010100和Y=01010101的奇校验编码。

解当X=01010100时,奇校验位c必须为0,则加了奇校验的数据X'=001010100。

当Y=01010101时,奇校验位c必须为1,则加了奇校验的数据Y'=101010101。

2.偶校验

偶校验的概念与奇校验是一样的,就是加上偶校验后,必须保证数据(包括偶校验位在内)的n+1位中1的个数为偶数,即必须保证:

当数据X=x0x1…xn-1加上偶校验时,可利用下式求出偶校验位c:

也就是说,偶校验位等于数据各位的模2加。

同样,当数据加上偶校验后,便可以存储或传输。在从存储器读出或通信对方收到该数据后,可利用式(2.19)进行计算。若式(2.19)成立,则认为在存储或传输过程中未发生1位出错。

例2.14试确定二进制数X=01010100和Y=01010101的偶校验编码。

解当X=01010100时,偶校验位c必须为1,则加了偶校验的数据X'=101010100。

当Y=01010101时,偶校验位c必须为0,则加了偶校验的数据Y'=001010101。

由上述分析可见,当数据位中有1位变化时,校验位也会跟着变化,因此奇偶校验码的码距为2,可以检测出1位错误(或奇数位错误,但多于1位错误的概率很小),无法检测出2位或偶数位错,也无法定位错误位置,从而无法纠错。由于奇偶校验原理简单,实现容易,因此这种方法得到了广泛应用。

2.6.3海明校验码

RichardHamming于1950年提出的海明码可以达到满足式(2.16)的最少的校验位数。

1.海明码的编码

设有效信息为16位数据,用D15~D0表示由高到低的各位。根据式(2.16)计算或查表2.7可知,若要纠正1位错误,需要在有效信息中添加5个校验位H4~H0。此时海明码的码长为m=n+k=16+5=21。表2.10所示为21位海明码的生成及校验方程的构建。

(1)构建海明码编码格式。先将21位码的位置编号列于表2.10第1行中,编号从1开始,在表中按顺序排列。在十进制位置编号为2i之处放置各校验位Hi,i从0开始,见表2.10中第2行。在除Hi之外的剩余位置编号之处,将数据D15~D0的各位从低位到高位在表2.10中第3行从右到左按顺序填入,然后合并第2、3行得到海明码编码格式,如图2.14所示。图2.14海明码编码格式

(2)对表2.10第4~8行进行打“√”操作。第4行从位置1(即20,对应H0)开始,从右到左每打1个“√”空1个位置,直到最高位置。第5行从位置2(即21,对应H1)开始,从右到左每打2个“√”空2个位置,直到最高位置。第6行从位置4(即22,对应H2)开始,从右到左每打4个“√”空4个位置,直到最高位置。第7行从位置8(即23,对应H3)开始,从右到左每打8个“√”空8个位置,直到最高位置。第8行从位置16(即24,对应H4)开始,从右到左每打16个“√”空16个位置,直到最高位置。

2.海明码的校验

(1)构建生成方程。在该编码方案中,每个校验位对所有二进制位置编号对应位为1的那些数据位进行校验。

(2)构成海明码。利用生成方程产生海明码校验位后,将数据与校验位按照图2.14编码格式组织就构成了该数据的海明码,之后可以对海明码进行存储或传输。

(3)构建校验方程。当获得一个海明码时,使用校验方程来判断该编码的正确性。

3.海明码的纠错

根据校验方程即可直接确定海明码是否有错或者出错位置编号。知道出错位置,对该位求反,就实现了纠错。所以海明码也被称作纠错码,具有纠正一位错误的能力。

图2.15是针对12位海明码(8位数据+4位校验)纠错的电路。将4-16译码器74LS154输入端接P3P2P1P0,选择16个译码输出(低有效)中对应8位数据的输出端加反相器,再与相应的数据位做异或运算,这样就可以实现海明码无错时8位数据直接输出,有错时对出错数据位求反纠正。图2.15纠错电路原理图

4.单纠错双检错码

观察表2.10中n=8、k=4时海明码的生成方程可以发现,每一个数据位至少出现在两个生成方程中,即被两个校验位校验。因此当一个数据位变化时,至少有两个校验位也随之变化,这意味着两个合法码字之间的码距至少为3。实际上,n=8、k=4时海明码的码距就是3。根据2.6.1节中的分析,它可以纠正1位错误,或者发现2位错误而不纠正。那么,能否同时纠正1位错误及发现2位错误呢?这就需要进一步扩大码距。

方案是:增加一个所有数据位异或得到的校验位(即偶校验)。若该校验位校验错误,表示可能有1位错误(实际上说明有奇数位错误),进一步根据P3~P0具体确定错误位的位置,并纠错;反之,若该校验位校验正确,而P3~P0不是全零,则表示有2位错误(实际上为偶数位错误),只给出校验错误信息,不纠错,这就是半导体存储器中常用的单纠错双检错(Single-Error-Correcting,Double-Error-Detecting,SEC-DED)码。

海明码不仅用于主存储器的校验,在通信传输、磁盘记录中同样可以使用。

2.6.4循环冗余校验码

循环冗余校验(CyclicRedundancyCheck,CRC)码可以发现并纠正信息在存储或传送过程中出现的错误。因