大学计算机组成原理--第2章、计算机数据表示方法

1、1 第二章、计算机数据表示方法 Outline 2 Data Representation o Qualitative o Quantitative n Integers o Signed o Unsigned n Non-integers (Real) o Signed o Unsigned 3 2.1 非数值数据表示法 o 字符表示法 characters o 汉字表示法 Chinese characters 4 2.1.1 Character representation o 如何使用数值表示字符数据 o Standards nASCII-American Standard Code f

2、or Information Interchange (ANSI 7bits) nEBCDIC-Extended Binary-Coded Decimal Interchange Code (IBM 8bits) nUnicode 5 128 Standard ASCII codes o 52 Letters na-z, A-Z o 10 Digits n0-9 o 34 Symbols n! # $ % int d; b=3.3; c=1.1; a=b/c; d=b/c; printf(%f,%d,a,d); if (3.0!=a) printf(nReally? 3.0!-a); 3.00

3、0000,2 ? Really?3.0!=a 二进制存储 浮点数不是精确数 52 一个奇怪的程序 main() float a,b,c; int d; b=3.3; c=1.1; a=b/c; d=b/c; printf(%f,%d,a,d); if (3.0!=a) printf(nYeah!); 3.000000,2 53 2.2 数值数据表示方法 o 计算机数值数据表示的特点 o 进位制数 o 数的定点、浮点表示 o 机器数 54 2.2.2 机器数/机器码 o 真值 (书写用) n将用+ -表示正负的二进制数称为符号数的真值 o 机器不能识别书写格式，计算机如何表示负数？ o 机器码

4、(机器内部使用) n将符号和数值一起编码表示的二进制数称为机器码 o 原码 Signed magnitude 反码 Ones complement o 补码 Twos complement 移码 Biased notation 55 原码表示法（Signed magnitude） o 计算机如何表示数的正负? o 增加符号位 Add a sign bit o 最高位为符号位，0为正，1为负，数值位不变 56 原码表示示例 o +0原=0.0000 o -0原=1. 0000 o -0.1111原 = 1.1111 o 0.1111原 = 0.1111 o 1110原 = 01110 o -11

5、10原 = 11110 57 求值方法 x = (-1)X0( x12n-1 + + xn-12 +Xn) 求值方法 x = (-1)X0( x12-1 + + xn-12-(n-1) +Xn2-n) 原码表示法 58 p -7+7 7个正数，7个负数，两个零 p -(2(n-1) -1) 2(n-1) -1 59 Signed Magnitude o Both positive and negative zero o Equal number of positives and negatives o Easy to interpret nFirst bit is the sign nRema

6、ining bits are number o Sounds ideal? But o 01011001+11001101=? 60 Signed Magnitude? 010110012 = 8910 + 110011012 = -7710 001001102 = 3210 61 Shortcomings of signed magnitude? o Arithmetic circuit complicated o Also, two zeros n 0 x00000000 = +0ten n 0 x80000000 = 0ten n What would two 0s mean for p

7、rogramming? o Therefore sign and magnitude abandoned 62 反码表示法 o 所谓反码,就是二进制的各位数码取反 o 符号位表示方法与原码相同 o Example: 710 = 001112 ； -710 =110002 o Called Ones Complement 63 反码0的表示 o +0反=0.0000 o -0反=1.1111 o 0.1111反=0.1111 o -0.1111反=1.0000 o 1110反=01110 o -1110反=10001 64 反码公式证明 o -1x=0时 n 假设 x=-0.x1x2xn n 假

8、x反= 1.x1x2xn n x反+|x|=1.111 =1.111+0.001-0.001 =10.000-0.001 =2-2-n o x反=2-2-n-|x|=2-2-n+x 65 反码公式证明 o -2nx=0时 n 假设 x= -x1x2xn n 假设 x反= 1x1x2xn n x反+|x|= 1111 = 1111+0001-0001 = 10000-0001 = 2n+1-1 o x反= 2n+1-1 -|x|= 2n+1-1 +x 66 求值方法(X反= x0 x1 xn-1 Xn) x = -x0（2n -1）+ x12n-1 + + xn-12 +Xn 反码表示法 67

9、数值 -7 15 7 7 0 0 编码 p -7+7 正数7个，负数7个，零两个 p -(2n -1) 2n -1 68 原码&反码 数值 -7 15 7 7 0 0 编码 69 Shortcomings of Ones complement? o Arithmetic still a somewhat complicated. o Still two zeros n 0 x00000000 = +0ten n 0 xFFFFFFFF = -0ten o Although used for awhile on some computer products, ones complement wa

10、s eventually abandoned because another solution was better. 70 o3与15、-9 等效 有趣的时钟 12 3 6 9 12 3 6 9 12 3 6 9 71 同余的概念 o 假定有两个数a和b，若用某一个整数m去除， 所得的余数相同，就称a,b两个数对m同余, 记作： ab (mod m) o假设X,Y,Z三个数，满足下列关系：Z=nX+Y (n为 整数),则称Z和Y对模X是同余的，记作： ZY (mod X) YZ (mod X) 72 例子 o Z=nX+Y X为模数 o 以12为模 o 3=12+3=24+3=36+3 o

11、3，15，27，39 都是相等的 o -9=12-9=3 o -9与3是相等的 o 0=12 73 例子（减法变成加法） o 7+(-4) o =7+(12-4) o =7+8 o =15=3 74 3. 补码表示法 求值方法(X补= x0 x1 xn-1 Xn) x = -x02n + x12n-1 + + xn-12 +Xn 例如：10000100的真值为-128+4=-124 75 p -8+7 正数7个，负数8个，零1个 p -2n 2n -1 数值 0 0 -8 7 15 7 编码 76 反码、补码数轴表示比较 数值 0 0 -8 7 15 7 编码 数值 -7 15 7 7 0 0

12、 编码 77 o 正值直接取其原来的二进制码，对于负数是在对其逐位取反 之后再在最低位LSB加1。 o -10101010补 =1 01010101+1 =1 01010110 o -0.010101补=1.101011 78 证明 定点小数时 x反=2-2-n+x x补=2+x =(2-2-n+x)+2- n =x反+2-n 整数时 x反=2n+1-1+x x补=2n+1+x =(2n+1-1+x)+1 = x反+1 79 例子 o X=+0.11111111 X补 =? X补 =0.11111111 o X=-0.11111111 X补 =? X补 =1.00000000 +0.00000

13、001 =1.00000001 o X=-0.00000000 X补 =? X补 =1.11111111 +0.00000001 =10.00000000 =0.00000000 80 0000 0000 0000 0000 0000 0000 0000 0000two = 0ten 0000 0000 0000 0000 0000 0000 0000 0001two = + 1ten 0000 0000 0000 0000 0000 0000 0000 0010two = + 2ten . 0111 1111 1111 1111 1111 1111 1111 1110two = + 2,14

14、7,483,646ten 0111 1111 1111 1111 1111 1111 1111 1111two = + 2,147,483,647ten 1000 0000 0000 0000 0000 0000 0000 0000two = 2,147,483,648ten 1000 0000 0000 0000 0000 0000 0000 0001two = 2,147,483,647ten 1000 0000 0000 0000 0000 0000 0000 0010two = 2,147,483,646ten . 1111 1111 1111 1111 1111 1111 1111

15、1101two = 3ten 1111 1111 1111 1111 1111 1111 1111 1110two = 2ten 1111 1111 1111 1111 1111 1111 1111 1111two = 1ten maxint minint 32 bit MIPS signed numbers 81 例： 00.1010110 11.0101001 又称 双符号位补码，变形补码 82 补码的性质 o 零有唯一的表示方式 0.0000补= -0.0000补= 0.0000 o 负一的补码 1.0000补= 1.0000 83 补码加减法的实现 X + Y补= X补+ Y补 X-Y

16、补= X补+ -Y补 84 补码特点 o 唯一的零 o 符号位可以直接参与运算 o 减法可以变成加法 o 负数比整数多一个 85 4. 移码表示法 Biased/Excess Notation p 保持数据原有大小顺序，便于进行比较操作。 p 通常仅用于表示整数，表示浮点数的阶码。 p 与补码的符号位相异，数据位相同 定义 x移 = 2n+x -2n x 1 o 全部检错码为0表示数据正常 o 不为零时检错码的值表示编码中出错数据位 o 可检错，也可纠错 o 每一数据位至少参加2个校验组，一位出错，可引起多个检错码的变 化。 102 可检测一位错海明码 o 设海明码N位，其中数据位k位，校验位

17、r位 o 校验位r位表示共r个校验组 o N=k+r2r1 o (4,3)编码 nD4D3D2D1P3P2P1 nH7H6H5H4H3H2H1 n包含G3G2G1个校验组，P3P2P1分属其中一组 103 H7参与G3 G2 G1三校验组 H6参与G3 G2两校验组 H5参与G3 G1两校验组 H3参与G2 G1两校验组 G2G1=0 表示仅仅 P3位出错 G3G1=0 表示仅仅 P2位出错 G3G2=0 表示仅仅P1位出错 备注 H7出错111 H6出错110 H5出错101 H3出错011 P3存放在H4位置H4出错100 P2存放在H2位置H2出错010 P1存放在H1位置H1出错001

18、 数据正常000 出错位G3G2G1 可检测一位错海明码 104 P1P2D1P3D2D3D4 H1H2H3H4H5H6H7 o G1(P1,H3,H5,H7) o G2(P2,H3,H6,H7) o G3(P3,H5,H6,H7) oP1=D1 D2 D4 oP2=D1 D3 D4 oP3=D2 D3 D4 可检测一位错海明码 H7参与G3 G2 G1校验组 H6参与G3 G2校验组 H5参与G3 G1校验组 H3参与G2 G1校验组 H7出错111 H6出错110 H5出错101 H3出错011 备注出错位G3G2G1 105 指错、纠错原理 o G1=P1 D1 D2 D4 o G2=P

19、2 D1 D3 D4 o G3=P3 D2 D3 D4 o 检错码G3G2G1 !=000表示出错，具体值表示出错位置 o 将对应位置上的数位取反即可纠错 o 假设D1D2同时出错，则G3G2G1=110 ？ o引入总校验位 P4=H1 H2 H3 H4 H5 H6 H7 oG4=P4 H1 H2 H3 H4 H5 H6 H7 判断一位错两位错 106 CRC循环冗余校验码 o 检错，纠错码 o 数据位k位，校验位r位 o N=k+r2r1 107 模2运算规则 o 加法：按位加不考虑进位 o 减法：按位减不考虑借位 n 异或运算，不考虑进位 o 乘法：部分积之和按模2加法计算 o 除法：余数

20、首位为1，商上1 ,否则上0 n 10000101 n =101*101+01 108 多项式 o 将待编码的k位有效信息位组表达为多项式M(x) o M(x)=bk-1Xk-1 + bk-2Xk-2 + b1X1 + b0 o 将数据左移r位，以便空出r位校验位，多项式变成M(x)X r o 将M(x)X r除以生成多项式G(x) n商为Q(x) 余数R(x) M(x)X r=Q(X)G(x)+R(X) o 将余数拼接在空出的校验位上 o M(x)X r+R(X)=(Q(X)G(x)+R(X)+R(x) Q(X)G(x) CRC编码可被G(x)表示的编码整除 109 (7,4)循环码出错模式

21、G(x)=1011 11010100010 21111000010 31101110010 40111101010 51001100110 60101100000 70011100011 无0001100010 出错位余数A1A7 1101- 0101 100 1101- 0111 1101- 0011 0110 1101- 0001 0 0100 0110100 010 110 生成多项式 o 任何一位发生错误都应使余数不为0 o 不同位发生错误应当使得余数不同 o 对余数继续作模2除，应使余数循环 o (n,k)码，将Xn-1分解为若干质因子 o 根据编码要求的码距选择其中的因式或若干因式

22、的乘积为生成多项式 111 生成多项式 o x7-1=(x+1)(x3+x+1)(x3+x2+1) o G(x)=x+1=11 n (7,6)码，判一位错 o G(x)= x3+x+1 G(x)(x3+x2+1) n (7,4)码，判两位错或纠一位错 o G(x)=(x+1)(x3+x+1)=11101 n (7,3)码，判两位错并纠一位错 112 Example o 现有一个(7,3)循环冗余校验码，其中3位为信息位，求信息 位M(x)=110的CRC码，其中生成多项式为G(x)=11101。 113 (7,3)循环码出错模式G(x)=11101 111100101001 201111001001 311011111001 410001100001 501001101101 600101101011 700011101000 无00001101001 出错位余数A1A7 1+2+301000010001 5+6+701111101110 1+611000101011 2+310101011001 3+4010111100