计算机组成原理电子教案第2章

第二章计算机的数据表示计算机组成原理电子教案陆遥2.1字符数据的表示2.2逻辑数据的表示2.3校验码2.3.1码距与校验位的概念2.3.2奇偶校验码2.3.3海明校验码2.3.4循环冗余校验码2.4数值数据的表示2.4.1数的二进制真值表示2.4.2用BCD码表示十进制数2.4.3定点数的表示2.4.4浮点数的表示2.1字符数据的表示字符在计算机中的二进制编码称为字符代码。目前，计算机中普遍使用的字符代码是长度为7位的ASCII码（美国信息交换标准代码）。ASCII码在存储器中存放时，需要占用存储器的一个字节（8位），其中的最高位（b7）置为0或用作奇偶校验位。字符串被看作是一种数据结构，它是若干字符组成的一个序列，属于线性结构。字符串在计算机中的存储一般采用顺序存储结构，串中每个字符都用ASCII码表示，占用一个字节。设字符串“Verygood!”存储在从主存地址i开始的连续字节中，则其存储结果为……Very空格good!……存储器地址ii+1i+2i+3i+4i+5i+6i+7i+8i+9图2.1字符串在主存中的顺序存储2.2逻辑数据的表示逻辑数据用于描述某种关系是否成立、某种条件是否满足、某种状态是否出现、某种控制是否有效等。逻辑数据所描述的结果总是只有两种可能：成立或不成立，满足或不满足，出现或未出现、有效或无效等。逻辑数据的两种值被分别称为“真”和“假”。“真”代表关系成立、条件满足、状态出现、控制有效等，“假”则反之。计算机中只需用一位二进制数字的0和1两种状态，就能满足逻辑数据表示的需要：1表示“真”，0表示“假”。2.3校验码数据校验码是一类能够发现甚至自动纠正某些数据错误的数据编码方法。通常，将正确的数据编码称为合法编码，而将错误的数据编码称为非法编码。校验码的设计原则：当一个合法编码中的数据位发生错误时，就变为一个非法编码，而不是变为另一个合法编码。这样，只要检测到非法编码，就能发现数据错误。2.3.1码距与校验位的概念一个二进制编码系统中，当两个不同的合法编码进行对应位的比较时，会有一些位上的取值不同，这些取值不同的位的位数称为这两个编码的码距，也称海明距离。一个编码系统中任意两个合法编码的码距的最小值，称为这个编码系统的最小码距。一个编码系统不仅要编出全部合法编码，还应能编出一定数量的非法编码。这样，在合法编码出错时，才有可能变成非法编码而被检出。编码系统中包含的非法编码称为冗余码。为了形成冗余码，需要在编码中增加冗余位（校验位）。一个n位的编码系统，如果不设校验位，则无冗余码，全部2n个编码均为合法编码，最小码距必然为1，编码系统无检错能力。借助于校验位，可以使编码系统的最小码距大于1，而与某个合法编码的码距小于最小码距的编码一定是非法编码。2.3.2奇偶校验码奇偶校验码是在基本编码之上增加一个校验位——奇偶校验位而形成的。奇偶校验分为奇校验和偶校验两种实现方案。奇校验是通过校验位的调节，使整个编码中包含的二进制1的位数为奇数。偶校验是通过校验位的调节，使整个编码中包含的二进制1的位数为偶数。5位偶校验码表（最高位为校验位）原始数据编码（4位）偶校验编码（5位）原始数据编码（4位）偶校验编码（5位）000000000100011000000110001100101001001010010101001010001100011101111011010010100110001100010100101110111101011000110111011110011110111111101111增加一个校验位后，最小码距从1变为2。表中未列出的另16种5位编码就是本编码系统的冗余码，也就是非法编码。任一非法编码均与表中某个合法编码的码距为1，且合法编码出错的位数为奇数（1、3或5）时，均会变成非法编码。奇偶校验码能够发现奇数个编码位的错误，但无法确定出错位的位置，故不能实现自动纠错。设奇偶校验码为PDn-1Dn-2…D1D0，其中，P为校验位，Dn-1Dn-2…D1D0为n个数据编码位，按照奇偶校验码的编码方法，校验位与数据编码位的逻辑关系为：奇校验：偶校验：奇偶校验的校验式为：对偶校验，S=1时编码有错，S=0时编码无错，对奇校验则正好相反。0121DDDDPnn0121DDDDPnn0121DDDDPSnn2.3.3海明校验码海明校验码具有发现2位错误并纠正1位错误的能力，是一种广泛使用的校验码。海明校验码的设计原理：将几个校验位编入到数据码的特定位置，全部数据位被分成几个奇偶校验组，每个数据位被按一定的规则分配到其中几个组中，各校验位分别作为各组的奇偶校验（一般为偶校验）位。当某个数据位出错时，将会导致含有该数据位的几个校验组的校验结果出错。根据出错校验组的不同组合，就能确定是哪个数据位发生错误，进而自动纠正这个错误。海明码数据位数k与校验位数r的对应关系表k值最小的r值1～45～1112～2627～5758～12045678设校验位的位数为r，数据位的位数为k，若要能够发现2位错误并纠正1位错误，则需满足rkr12设m=k+r，则海明码是一个m位编码，设其一般表示形式为HmHm-1…H2H1，则此海明码的编码规则是：⑴各校验位Pi（i=1，2，…，r）被安排在编码的第2i-1位的位置，编码中的其余位为数据位。如校验位P3在海明码中位于第4（23-1）位，即编码中的H4。⑵海明码的每个位被分配到几个奇偶校验组中，所以，每个位均由几个校验位来校验。各被校验位与相关的校验位之间的关系是：被校验位的位号是相关各校验位的位号之和（这里的位号是指其在海明码中的位号）。例如，当k=4时，有r=4，则海明码总位数为8，可表示为H8H7H6H5H4H3H2H1。按编码规则，4个校验位P1、P2、P3、P4被分别安排在H1、H2、H4和H8。如以Di和Pi（i=1，2，3，4）分别表示数据位和校验位，则海明码的编码结果为P4D4D3D2P3D1P2P1其中的各个编码位与相关的校验位之间的关系如下表所示：海明码的编码位与相关校验位之间的关系海明码位号数据位/校验位相关的校验位位号H1P11（1=1）H2P22（2=2）H3D11，2（3=1+2）H4P34（4=4）H5D21，4（5=1+4）H6D32，4（6=2+4）H7D41，2，4（7=1+2+4）H8P48（8=8）可见，P1要对数据位D1、D2、D4进行校验，P2要对数据位D1、D3、D4进行校验，P3要对数据位D2、D3、D4进行校验。如选择偶校验，有对应的三个校验式为432343124211DDDPDDDPDDDP432334312242111DDDPSDDDPSDDDPS编码位出错与校验式结果之间的关系当不同的编码位（包括数据位和校验位）发生错误时，3个校验式的值组成的二进制序列S3S2S1就会不同。出错的编码位校验式结果S3S2S1海明码位号P1001（1）H1P2010（2）H2D1011（3）H3P3100（4）H4D2101（5）H5D3110（6）H6D4111（7）H7无出错位000（0）无按S3S2S1确认出错的编码位后，只需将该编码位取反，即可纠正之。纠错时，需要针对S3S2S1的每种取值（除000外）设计相应的纠错电路，来纠正对应的出错编码位，硬件代价较大。海明码还能检出2位错误。因为任意两个编码位出错，都将使S3S2S1≠000。但仅凭S3S2S1≠000，无法区分是2位错误还是1位错误。为此，需要增加一个总校验位P4，使得并增设一个奇偶校验式S4=1，发生1位错误；S4=0，发生2位错误。32143214PPPDDDDP321432144PPPDDDDPS2.3.4循环冗余校验码循环冗余校验（CRC）码因其纠错能力强，且在信息量较大的情况下，编码与解码所需的硬件代价小等优点，被广泛用于串行传送过程中的检错与纠错。CRC码也称为（n，k）码，它是在k位信息位之后拼接r位校验位而形成的n位编码（n=k+r）。1．模2四则运算CRC码的编码及校验过程均需要用到模2四则运算。模2运算是按位运算，位与位之间不产生进位或借位。⑴模2加/减运算：模2加与模2减是两种等效的运算，均等同于逻辑异或运算，即⑵模2乘运算：在对部分积求和时按模2加进行。例如1010×110110100000101010101110010baba⑶模2除运算：上商时，如果上一次部分余数的最高位为1，则本次上商为1，否则上商为0；求部分余数时，按模2减进行；将每次求得的部分余数的最高位（总是0）去掉，使部分余数每次减少一位，当部分余数的位数少于除数位数时，即为最终的余数。例如101商10110010被除数也是最初的部分余数101部分余数最高位为1，上商为100110去掉部分余数最高位的0，部分余数减少一位000部分余数最高位为0，上商为00110去掉部分余数最高位的0，部分余数减少一位101部分余数最高位为1，上商为1011去掉部分余数最高位的0，得最终余数112．CRC码的编码方法一个k位二进制信息码可以用一个多项式表示：M(x)称为信息码多项式。为了在信息位后拼接r位校验位，需将k位信息位向左移动r位，得多项式M(x)×xr。r位校验位可以表示为多项式R(x)，它是以下多项式运算产生的余数（按模2运算）0121DDDDkk012211DxDxDxDxMkkkkxGxRxQxGxxMr上式中，G(x)被称为生成多项式，是一个r阶多项式；Q(x)为商多项式；R(x)是余数多项式。将R(x)拼接在M(x)之后，即得到完整的CRC码，其多项式表示形式为M(x)×xr＋R(x)（模2加）。CRC码M(x)×xr＋R(x)可被其生成多项式G(x)整除（模2除），即余数为r位全0。因为M(x)×xr＋R(x)=[Q(x)×G(x)＋R(x)]＋R(x)=Q(x)×G(x)＋[R(x)＋R(x)]=Q(x)×G(x)（模2运算）【例2.1】按（7，4）CRC码的编码规则，求4位信息码1100的CRC码，生成多项式选择G(x)=x3＋x＋1。解：由（7，4）码可知r=7－4=3，即校验位有3位。根据4位信息码1100得M(x)=x3＋x2；M(x)左移r位后得M(x)×xr=(x3＋x2)×x3=x6＋x5=1100000G(x)=x3＋x＋1=1011。下面按模2除求3位校验位所以，R(x)=010。由此可得CRC码为M(x)×xr＋R(x)=1100000＋010=1100010（模2加）1011010111010111100000xGxxMr3．CRC码的检错与纠错CRC码的检错原理：数据传送的接收方在接收到CRC码后，使用与发送方约定的生成多项式去除该CRC码，如果余数为r位全0，则收到的CRC码无错误，否则有错误。CRC码的纠错原理：CRC码不同位上的错误将导致产生不同的余数R(x)，可依据余数R(x)确定并纠正出错的编码位。例2.1的（7，4）CRC码出错位与余数R(x)之间的对应关系（生成多项式G(x)=1011）A7A6A5A4A3A2A1余数R(x)出错位正确的编码1100010000无发生1位错误的编码11000111100000110011011010101110010100001001000100010101000111101111011234567可以证明，只要CRC码的码制（即（n，k）码的n、k取值）和生成多项式G(x)不变，信息码M(x)的变化不改变出错位与余数R(x)的对应关系。即上表所列，为所有以G(x)=1011为生成多项式的（7，4）CRC码的出错模式。CRC码还有一个重要特点：在一个不为0的余数的最低位补1个0后再除以G(x)（模2除），所得的余数就是出错模式表中的下一个余