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

第二章 计算机的数据表示 计算机组成原理电子教案 陆 遥 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 字符数据的表示 n字符在计算机中的二进制编码称为字符代码。目 前，计算机中普遍使用的字符代码是长度为7位的 ASCII码（美国信息交换标准代码）。 nASCII码在存储器中存放时，需要占用存储器的 一个字节（8位），其中的最高位（b7）置为0或 用作奇偶校验位。 n字符串被看作是一种数据结构，它是若干字符组 成的一个序列，属于线性结构。字符串在计算机 中的存储一般采用顺序存储结构，串中每个字符 都用ASCII码表示，占用一个字节 。 设字符串“Very good!”存储在从主存地址i开始的 连续字节中，则其存储结果为 2.2 逻辑数据的表示 n逻辑数据用于描述某种关系是否成立、某种条件 是否满足、某种状态是否出现、某种控制是否有 效等。 n逻辑数据所描述的结果总是只有两种可能：成立 或不成立，满足或不满足，出现或未出现、有效 或无效等。 n逻辑数据的两种值被分别称为“真”和“假”。“真” 代表关系成立、条件满足、状态出现、控制有效 等，“假”则反之。计算机中只需用一位二进制数 字的0和1两种状态，就能满足逻辑数据表示的需 要：1表示“真”，0表示“假”。 2.3 校验码 n数据校验码是一类能够发现甚至自动纠正某些数 据错误的数据编码方法。 n通常，将正确的数据编码称为合法编码，而将错 误的数据编码称为非法编码。 n校验码的设计原则：当一个合法编码中的数据位 发生错误时，就变为一个非法编码，而不是变为 另一个合法编码。这样，只要检测到非法编码， 就能发现数据错误。 2.3.1 码距与校验位的概念 n一个二进制编码系统中，当两个不同的合法编码 进行对应位的比较时，会有一些位上的取值不同 ，这些取值不同的位的位数称为这两个编码的码 距，也称海明距离。 n一个编码系统中任意两个合法编码的码距的最小 值，称为这个编码系统的最小码距。 n一个编码系统不仅要编出全部合法编码，还应能 编出一定数量的非法编码。这样，在合法编码出 错时，才有可能变成非法编码而被检出。 n编码系统中包含的非法编码称为冗余码。 为了形成冗余码，需要在编码中增加冗余 位（校验位）。 一个n位的编码系统，如果不设校验位，则 无冗余码，全部2n个编码均为合法编码，最 小码距必然为1，编码系统无检错能力。 借助于校验位，可以使编码系统的最小码 距大于1，而与某个合法编码的码距小于最 小码距的编码一定是非法编码。 2.3.2 奇偶校验码 n奇偶校验码是在基本编码之上增加一个校验位 奇偶校验位而形成的。奇偶校验分为奇校验和 偶校验两种实现方案。 奇校验是通过校验位的调节，使整个编码中包含 的二进制1的位数为奇数。 偶校验是通过校验位的调节，使整个编码中包含 的二进制1的位数为偶数。 5位偶校验码表（最高位为校验位） 原始数据编码编码 （ 4位） 偶校验编码验编码 （5位） 原始数据编码编码 （ 4位） 偶校验编码验编码 （5位） 000000000100011000 000110001100101001 001010010101001010 001100011101111011 010010100110001100 010100101110111101 011000110111011110 011110111111101111 增加一个校验位后，最小码距从1变为2。 表中未列出的另16种5位编码就是本编码系 统的冗余码，也就是非法编码。任一非法 编码均与表中某个合法编码的码距为1，且 合法编码出错的位数为奇数（1、3或5）时 ，均会变成非法编码。 奇偶校验码能够发现奇数个编码位的错误 ，但无法确定出错位的位置，故不能实现 自动纠错。 n设奇偶校验码为PDn-1Dn-2D1D0，其中，P为校验 位，Dn-1Dn-2D1D0为n个数据编码位，按照奇偶 校验码的编码方法，校验位与数据编码位的逻辑 关系为： 奇校验： 偶校验： 奇偶校验的校验式为： 对偶校验，S=1时编码有错，S=0时编码无错，对 奇校验则正好相反。 2.3.3 海明校验码 n海明校验码具有发现2位错误并纠正1位错误的能 力，是一种广泛使用的校验码。 n海明校验码的设计原理：将几个校验位编入到数 据码的特定位置，全部数据位被分成几个奇偶校 验组，每个数据位被按一定的规则分配到其中几 个组中，各校验位分别作为各组的奇偶校验（一 般为偶校验）位。当某个数据位出错时，将会导 致含有该数据位的几个校验组的校验结果出错。 根据出错校验组的不同组合，就能确定是哪个数 据位发生错误，进而自动纠正这个错误。 海明码数据位数k与校验位数r的对应关系表 k值值最小的r值值 14 511 1226 2757 58120 4 5 6 7 8 设校验位的位数为r，数据位的位数为k，若要能够 发现2位错误并纠正1位错误，则需满足 n设m = k + r，则海明码是一个m位编码，设其一般 表示形式为HmHm-1H2H1，则此海明码的编码规 则是： 各校验位Pi（i =1，2，r）被安排在编码的 第2i-1位的位置，编码中的其余位为数据位。如校 验位P3在海明码中位于第4（23-1）位，即编码中 的H4。 海明码的每个位被分配到几个奇偶校验组中， 所以，每个位均由几个校验位来校验。各被校验 位与相关的校验位之间的关系是：被校验位的位 号是相关各校验位的位号之和（这里的位号是指 其在海明码中的位号）。 n例如，当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进行校验。 如选择偶校验，有 对应的三个校验式为 编码位出错与校验式结果之间的关系 当不同的编码位（包括数据位和校验位）发生错 误时，3个校验式的值组成的二进制序列S3S2S1就 会不同。 出错错的编码编码 位校验验式结结果 S3S2S1 海明码码位号 P1001 （1）H1 P2010 （2）H2 D1011 （3）H3 P3100 （4）H4 D2101 （5）H5 D3110 （6）H6 D4111 （7）H7 无出错错位000 （0）无 n按S3S2S1确认出错的编码位后，只需将该编码位 取反，即可纠正之。纠错时，需要针对S3S2S1的 每种取值（除000外）设计相应的纠错电路，来纠 正对应的出错编码位，硬件代价较大。 n海明码还能检出2位错误。因为任意两个编码位出 错，都将使S3S2S1000。但仅凭S3S2S1000，无法 区分是2位错误还是1位错误。为此，需要增加一 个总校验位P4，使得 并增设一个奇偶校验式 S4 =1，发生1位错误；S4 =0，发生2位错误。 2.3.4 循环冗余校验码 n循环冗余校验（CRC）码因其纠错能力强，且在 信息量较大的情况下，编码与解码所需的硬件代 价小等优点，被广泛用于串行传送过程中的检错 与纠错。 nCRC码也称为（n，k）码，它是在k位信息位之 后拼接r位校验位而形成的n位编码（n=k+r）。 1模2四则运算 nCRC码的编码及校验过程均需要用到模2四则运 算。模2运算是按位运算，位与位之间不产生进位 或借位。 模2加/减运算：模2加与模2减是两种等效的运 算，均等同于逻辑异或运算，即 模2乘运算：在对部分积求和时按模2加进行。 例如 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 模2除运算：上商时，如果上一次部分余数的最 高位为1，则本次上商为1，否则上商为0；求部分 余数时，按模2减进行；将每次求得的部分余数的 最高位（总是0）去掉，使部分余数每次减少一位 ，当部分余数的位数少于除数位数时，即为最终 的余数。例如 1 0 1 商 1 0 1 1 0 0 1 0 被除数也是最初的部分余数 1 0 1 部分余数最高位为1，上商为1 0 0 1 1 0 去掉部分余数最高位的0，部分余数减少一位 0 0 0 部分余数最高位为0，上商为0 0 1 1 0 去掉部分余数最高位的0，部分余数减少一位 1 0 1 部分余数最高位为1，上商为1 0 1 1 去掉部分余数最高位的0，得最终余数11 2CRC码的编码方法 n一个k位二进制信息码 可以用一 个多项式表示： M(x)称为信息码多项式。 n为了在信息位后拼接r位校验位，需将k位信息位 向左移动r位，得多项式M (x)xr。 nr位校验位可以表示为多项式R (x)，它是以下多项 式运算产生的余数（按模2运算） 上式中，G (x)被称为生成多项式，是一个r阶多项 式；Q (x)为商多项式；R (x)是余数多项式。 n将R (x)拼接在M (x)之后，即得到完整的CRC码， 其多项式表示形式为M (x)xrR (x)（模2加）。 nCRC码M (x)xrR (x)可被其生成多项式G (x)整 除（模2除），即余数为r位全0。因为 M (x)xrR (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) = x3x1。 解：由（7，4）码可知r = 74 = 3，即校验位有3位。根 据4位信息码1100得M (x) = x3x2；M (x)左移r位后得 M (x)xr = (x3x2)x3 = x6x5 = 1100000 G (x) = x3x1 = 1011。 下面按模2除求3位校验位 所以，R (x) = 010。由此可得CRC码为 M (x)xrR (x) = 1100000010 = 1100010 （模2加） 3CRC码的检错与纠错 nCRC码的检错原理：数据传送的接收方在接收到 CRC码后，使用与发送方约定的生成多项式去除 该CRC码，如果余数为r位全0，则收到的CRC码 无错误，否则有错误。 nCRC码的纠错原理：CRC码不同位上的错误将导 致产生不同的余数R (x)，可依据余数R (x)确定并 纠正出错的编码位。 例2.1的（7，4）CRC码出错位与余数R (x)之间的对应关系 （生成多项式G (x) = 1011） A7 A6 A5 A4 A3 A2 A1 余数R (x)出错错位 正确的编码编码 1 1 0 0 0 1 00 0 0无 发发生1位错错 误误的编码编码 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 2 3 4 5 6 7 可以证明，只要CRC码的码制（即（n，k）码的n、k取值） 和生成多项式G (x)不变，信息码M (x)的变化不改变出错位 与余数R (x)的对应关系。即上表所列，为所有以G (x)= 1011 为生成多项式的（7，4）CRC码的出错模式。 nCRC码还有一个重要特点：在一个不为0的余数 的最低位补1个0后再除以G (x)（模2除），所得的 余数就是出错模式表中的下一个余数；如此继续 下去，各次产生的余数将按出错模式表中的顺序 循环变化。 n对一个（n，k）码，在某位出错时，从对应的余 数开始，按上述方法产生余数的循环变化，同时 每次使整个CRC码循环左移1位，当余数变到对 应于An出错的余数时，出错位也被移到An的位置 ，此时将An取反实现纠错，然后继续做余数的循 环变化和CRC码的循环左移，直到做满一个循环 （n次），就得到了一个纠正后的CRC码。 n利用CRC码来纠错，不必针对每个不为0的余数 来设计对应编码位的纠错电路，能有效降低校验 电路的硬件代价。 4生成多项式简介 n生成多项式应能满足下列要求： CRC码的任何一位出错，均使余数不为0； CRC码的不同位出错时，余数也应不同； 对不为0的余数最低位补0后继续作模2除，应能 使余数循环。 若要求余数为r位，则生成多项式应为r阶。 n生成多项式的求取方法：对一个（n，k）码来说 ，可将（xn -1）按模2 运算规则分解为若干质因 子，根据编码所要求的码距选取其中的因式或若 干因式的乘积作为生成多项式。 【例2.2】设n = 7，则按模2 运算规则，有 选择G (x) = x1 = 11，可构成（7，6）码，只能判1位错 。 选择G (x) = x3x1 = 1011或G (x) = x3x21 = 1101， 可构成（7，4）码，能判2位错或纠1位错。 选择G (x) = (x1)(x3x1) = 11101，可构成（7，3）码 ，能判2位错并纠1位错。 部分（n，k）码的生成多项式G (x) nk码码距dG (x) 多项项式G (x)二进进制码码 743G1(x) = (x3+x+1) 或 (x3+x2+1)1011或1101 34G2(x) = G1(x) (x+1) = (x3+x+1) (x+1) 或 (x3+x2+1) (x+1) 11101或10111 15113G1(x) = (x4+x+1)10011 75G2(x) = (x4+x+1) (x4+ x3+x2+x+1) 111010001 31263G1(x) = (x5+x2+1)100101 215G2(x) = (x5+x2+1) (x5+x4+ x3+x2+x+1) 11101101001 63573G1(x) = (x6+x+1)1000011 515G2(x) = (x6+x+1) (x6+ x4+ x+1) 1010000110101 10411025G (x) = (x16+ x15+x2 +1)11000000000000101 2.4 数值数据的表示 n数值数据是计算机中用于各种算术运算的 数据。 n计算机中表示数值数据要解决有效数字、 小数点及符号的表示，还要便于数据的运 算。 2.4.1 数的二进制真值表示 n所谓数的“真值”表示，是相对于数在计算机中的 编码表示而言的，也就是人们平时所习惯的数的 书面表示形式。如+10000100 和-1111011.01。 n在计算机中，无论是“+”号、“-”号还是小数点“.” ，都属于字符，需要用ASCII码来表示。如果计 算机中也采用真值表示数据的话，就会大大增加 信息的存储量，同时也会给运算带来很大的麻烦 。 n计算机中的数值数据采用特殊的二进制编码形式 表示，称为机器数。 2.4.2 用BCD码表示十进制数 nBCD（binary coded decimal）码的完整意义是“ 用二进制编码的十进制码”，它采用4位二进制编 码表示1位十进制数。 nBCD码分有权码与无权码两类。有权码如8421码 、2421码等；无权码如余3码、格雷码等。 n采用8421码可以进行十进制算术运算，但运算结 果可能需要修正。 典型BCD码 十进进制数有权码权码无权码权码 8421码码2421码码余3码码格雷码码 00000000000110000 10001000101000001 20010001001010011 30011001101100010 40100010001110110 50101101110001110 60110110010011010 70111110110101000 81000111010111100 91001111111000100 2.4.3 定点数的表示 n计算机中实际用于数值计算的数据表示方法主要 有定点数表示法和浮点数表示法两种；定点数表 示法也是浮点数表示法的基础。 n所谓定点数表示，是指小数点被固定在数据中某 个特定位置上的数据表示方法。 定点整数： 定点小数： 其中，xs是数的符号。 n定点数中，小数点的位置可以看作是默认的，因 此，小数点不用表示出来。 n符号的表示是定点数表示必须要解决的问题。带 符号的定点数在计算机中有原码、补码、反码和 移码等四种编码表示方法。 1. 原码表示法 n原码以0表示正号，以1表示负号，直接置于数的 最左端（即最高位位置）；而数的数字部分与其 绝对值一致。 【例2.3】 若 x = +0.1011，则 x原 = 0.1011； 若 x = -0.1011，则 x原 = 1.1011； 若 x = +1011，则 x原 = 01011； 若 x = -1011，则 x原 = 11011。 n设符号位用xs表示，各数据位用xi（i = 0，1，2， ，n1）表示，则原码的一般表示形式为 x原 = xs xn1 xn2 x1 x0 n用原码表示时，+0原与-0原是不同的： +0原 = 00000 -0原 = 10000 n原码比较适合于乘除运算。 n原码不适合于加减运算。 2. 补码表示法 n计算机中，因为用来存储数据的存储单元或寄存 器有一定的位数限制，进行数据运算的运算器也 有一定的位数限制，所以，数据在计算机中表示 的位数也是受限制的。当数据超过规定位数时， 其处于高位的超出部分将被丢弃。 n以定点整数为例，设一个寄存器的位数为n，则超 出该寄存器存储能力的最小正整数是2n，它在该 寄存器中的存储结果与0的存储结果是一样的。 n一般地，设x为正整数，且0x2n，则x与2n x 在n位寄存器中的存储结果是一样的，均为x。这 种现象在数学中称为“同余”，即x除以2n与2n x 除以2n的余数相同，用数学公式表示为 x = 2n x (mod 2n) n在同余的概念下，设x0且|x|2n，则同样有 x = 2n x (mod 2n) 式中，x0而2n x0。它说明：在mod 2n的前 提下，一个负数x可以用一个正数2n x来表示； 也就是说，一个负数x与一个正数2n x在n位寄 存器中的存储结果是一样的。 n在mod 2n的前提下，设|x|2n，我们把x的同余数 2n x称为x的补码，即 x补 = 2n x (mod 2n) 在一个n位寄存器中存放补码时，要把最高位留作 符号位，数字部分为n1位。故x的实际取值范围 是 -2n1 x 2n1 -1 n对定点小数，由于符号位占据了n位寄存器的最高 位，相当于占据了20位，故模数应该是21。由此可 得定点小数x的补码为 x补 = 21 x (mod 21) x的实际取值范围是 -1 x 1-2-(n 1) 【例2.4】设寄存器位数为8位，可以存放一个8位 补码（1位符号，7位数值）。设 x = +1001011， 求x补 。 解： x补 = 28 + x (mod 28) = 28 + (+1001011) (mod 28) = 01001011 (mod 28) 其中，最高位上的0被看作符号位。由本例可知： 一个正数的补码与其原码是一致的。 【例2.5】设寄存器位数为8位，x = -1001011，求 x补 。 解： x补 = 28 + x (mod 28) = 28 + (-1001011) (mod 28) = 10110101 (mod 28) 其中，最高位上的1被看作符号位。由本例可知： 一个负数的补码，其符号位为1。显然，负数的补 码与其原码是不同的。 【例2.6】设寄存器位数为8位，x = +0.1001011， 求x补 。 解： x补 = 21 + x (mod 21) = 21 + (+0.1001011) (mod 21) = 0.1001011 (mod 21) 最高位上的0被看作符号位。 【例2.7】设寄存器位数为8位，x = -0.1001011， 求x补 。 解： x补 = 21 + x (mod 21) = 21 + (-0.1001011) (mod 21) = 1.0110101 (mod 21) 最高位上的1被看作符号位。 n与原码不同，补码的符号位（正为0，负为 1）不是人为规定的，而是在求补码的运算 中求出的，实际上就是运算结果的最高有 效数字位。因此，在用补码进行加减运算 时，符号位可以象数字位一样参加运算， 给计算机的加减运算带来很大方便。 3. 反码表示法 n一个数的反码可通过其原码求得，方法是：正数 的反码与其原码一致；负数的反码与其原码符号 位相同，数字位按位取反。 n反码一般不用于计算，但可用来作为原码转换为 补码时的中间代码。原码转换为补码的方法是： 正数的原码、补码及反码均相同，无需转换； 对负数，先从原码求其反码，再将反码加1，即 得其补码。 n补码到原码的转换也使用同样的方法。 【例2.8】设寄存器位数为8位，x = -1001011，则 x原 = 11001011， x反 = 10110100， x补 = x反 +1 = 10110100+1 = 10110101 【例2.9】在例2.8的基础上，将x补 转换为x原 的过程如下： x补 = 10110101符号位不变，数字位每位取反 ，得11001010加1，得11001011= x原 。 4. 移码表示法 n移码只用于表示带符号定点整数。设x是一个n位 二进制整数，则其移码定义为 x移 = 2n + x ， 2n x -2n x移 是一个n +1位的编码，最高位被看作符号。 【例2.10】设 x = +1001011，为7位数，则 x移 = 27 + x = 27 + (+1001011) = 11001011 【例2.11】设 x = -1001011，为7位数，则 x移 = 27 + x = 27 + (-1001011) = 00110101 n移码正数的符号为1，而负数的符号为0。移码的 符号能够直接参与加减运算。移码之间的大小关 系可以直接反映数据真值之间的大小关系。 2.4.4 浮点数的表示 n浮点数是指小数点位置未经人为约定的一般的数 ，其小数点可以出现在数中任意位置。 n一个浮点数N可以表示成 N = Re m n浮点数的三个构成要素：指数e；基数R；有效数 字m。 n浮点数表示的基本思想：将浮点数的三个要素分 别表示出来。 n在计算机中，指数是一个整数，可用定点整数表 示；基数默认为2，不用表示出来；有效数字部分 被规定为一个纯小数，可用定点小数表示。 n指数的机器数编码称为“阶码”，有效数字的机器 数编码称为“尾数”，尾数的符号就是浮点数的符 号。浮点数在计算机中的一般编码表示格式为： 尾数M一般用补码或原码表示；阶码E一般用移码 或补码表示；数符S是浮点数的符号，也就是尾数 的符号（故M不含符号位）。 n浮点数的表示范围取决于阶码的位数，而浮点数 的表示精度则取决于尾数的位数。 n在浮点数表示中，除了要求尾数为纯小数外，还 进一步规定：当尾数的绝对值不为0时，尾数绝对 值（或真值）的最高有效数字必须为1；这称为浮 点数的规格化表示。 如：+110.0101的规格化表示形式是 230.1100101 而不能是 240.01100101 n浮点数的规格化表示既消除了浮点数表示的不确 定性，又可以尽量减少其精度损失。 n浮点数表示中的一些特殊情况： 当尾数为0时，浮点数的值为零，称为机器零。 当阶码小于可表示的最小数（即绝对值最大的 负数）时，浮点数的值也被看作机器零。 当阶码大于可表示的最大数时，称为浮点数“溢 出”，通常要作为异常情况处理（报警或中止程序 执行等）。 nIEEE 754标准的32位（单精度）和64位（双精度 ）浮点数的标准格式： 其中，S为数符，0表示正数，1表示负数；E为阶 码，用移码表示；M是尾数，用原码表示。 nIEEE 754格式浮点数的真值x计算公式： 单精度：x = (-1)S (1. M)2E127 ，e = E127 双精度：x = (-1)S (1. M)2E1023 ，e = E1023 其中，S、E、M即为标准格式中的数符、阶码、 尾数，e是指数的真值。 nIEEE 754标准浮点数的规格化尾数实际为1. M， 其中的整数位1是默认的，没有表示出来，只在计 算时由运算电路自动提供。 n实际上，可将IEEE 754标准格式浮点数的规