Introduction to Computer Systems /18-243, spring st Lecture, Jan. 12th

Size: px

Start display at page:

Download "Introduction to Computer Systems /18-243, spring st Lecture, Jan. 12th"

鳜哄封
5 years ago
Views:

1 计算机组成原理第三讲第二章 : 运算方法和运算器数据与文字的表示方法 (2) 浮点数表示方法汉字表示方法及校验码授课老师 : 王浩宇 haoyuwang@bupt.edu.cn 1

2 关于课程网站的说明待爱课堂信息录入之后, 后期通过爱课堂布置和提交作业上周作业 : 整数表示方法的 C 语言实际测试本周四之前 (03.09) 提交到助教邮箱班级 - 姓名 - 学号.docx(pdf) 2

3 目录背景知识 : 二进制小数回顾 : 整数的表示方法浮点数的表示方法字符与字符串的表示方法汉字的表示方法校验码 3

4 Fractional binary numbers What is ? 4

$Representation 2 -j Bits to right of binary point represent fractional powers of 2 Represents$

5 Fractional Binary Numbers 2 i 2 i bi bi-1 b2 b1 b0 b-1 b-2 b-3 b-j 1/2 1/4 1/8 Representation 2 -j Bits to right of binary point represent fractional powers of 2 Represents rational number: 5

6 Fractional Binary Numbers: Examples Value Representation 5 3/ / / Observations Divide by 2 by shifting right (unsigned) Multiply by 2 by shifting left Numbers of form are just below 1.0 1/2 + 1/4 + 1/ /2 i Use notation 1.0 ε 6

7 Representable Numbers Limitation #1 Can only exactly represent numbers of the form x/2 k Other rational numbers have repeating bit representations Value 1/3 1/5 1/10 Representation [01] [0011] [0011] 2 Limitation #2 Just one setting of binary point within the w bits Limited range of numbers (very small values? very large?) 7

8 目录背景知识 : 二进制小数回顾 : 整数的表示方法浮点数的表示方法字符与字符串的表示方法汉字的表示方法校验码 8

9 数据的类型按数据的表示范围分 : 定点数 : 小数点位置固定, 数据表示范围小浮点数 : 小数点位置不固定, 数据表示范围较大按能否表示负数分 : 无符号数 : 所有均为表示数值, 直接用二进制数表示有符号数 : 有正负之分, 最高位为符号位, 其余表示数值按编码不同又可分为原码反码补码移码按数据格式分 : 真值 : 没有经过编码的直观数据表示方式, 其值可带正负号, 任何数制均可机器数 : 符号化后的数值 ( 包括正负号的表示 ), 一般位数固定 ( ), 不能随便忽略任何位置上的 0 或 1 9

10 数据格式定点数定点数 : 小数点固定在某一位置的数据 ; 纯小数 : 表示形式 The Principle of Computer Organization, BUPT, 2017 Spring 有符号数 x=x S x -1 x -2 x -n 0 x 1-2 -n ; x s 为符号位无符号数 x=x 0 x -1 x -2 x -n 0 x 1-2 -n ; 数据表示范围 0.0 0= 0 x 1-2 -n = 纯整数 : x 0 x -1 x -2 x -3 x -n x n x n-1 x n-2 x 1 x 0 设采用 n+1 位数据表示形式有符号数 x=x s x n-1 x 1 x 0 x 2 n -1; x s 为符号位无符号数 x=x n x n-1 x 1 x 0 0 x 2 n+1-1; x n 为数值位注意 : 小数点的位置是机器约定好的, 并没有实际的保存目前计算机中多采用定点纯整数表示, 因此将定点数表示的运算简称为整数运算 10

11 定点机的特点所能表示的数据范围小使用不方便, 运算精度较低存储单元利用率低 11

12 数的机器码表示重点 : 1 原码补码移码的表示形式 2 补码的定义 3 原码补码移码的表示范围 12

13 原码表示法 x n x n-1 x n-2 x 1 x 0 定义 : 定点小数 : [x] 原 = x 1> x 0 1- x=1+ x 0 x> -1 定点整数 : [x] 原 = 举例 : [ ] 原 = [-0.110] 原 = 1 - (-0.110) = [+110] 原 = 0110 [-110] 原 = (-110) = = 1110 x 2 n > x 0 2 n - x=2 n + x 0 x> -2 n 实际机器中保存时并不保存小数点 13

14 补码表示法 x n x n-1 x n-2 x 1 x 0 定义 : 定点小数 : [x] 补 = 定点整数 : [x] 补 = x 1> x 0 (mod 2) 2+x = 2 - x 0 x -1 x 2 n > x 0 (mod 2 n+1 ) 2 n+1 +x = 2 n+1 - x 0 x -2 n 举例 : [ ] 补 = [-0.110] 补 = 10 + (-0.110) = [+110] 补 = 0110 [-110] 补 = 2 4 +(-110 ) = = 1010 实际机器中保存时并不保存小数点 14

15 由原码求补码由原码求补码的简便原则 ( 负数 ) 除符号位以外, 其余各位按位取反, 末位加 1; 从最低位开始, 遇到的第一个 1 以前的各位保持不变, 之后各位取反例 :[X] 原 = [X] 补 =

16 求相反数的补码由 [X] 补求 [-X] 补连符号位一起各位求反, 末位加 1 例 :[X] 补 = 解 : [X] 补 = [-X] 补 = 由 [-X] 补求 [X] 补, 此规则同样适用 16

17 移码表示法 x n x n-1 x n-2 x 1 x 0 移码通常用于表示浮点数的阶码用定点整数形式的移码定义 : [x] 移 =2 n +x 2 n > x -2 n 与 [x] 补的区别 : 符号位相反优点 : 可以比较直观地判断两个数据的大小 ; 浮点数运算时, 容易进行对阶操作 ; 表示浮点数阶码时, 容易判断是否下溢 ; 当阶码为全 0 时, 浮点数下溢 4 位补码与移码真值补码移码

18 原补移码的编码形式正数 : 原补码的编码完全相同 ; 补码和移码的符号位相反, 数值位相同 ; 负数 : 原码 : 符号位为 1 数值部分与真值的绝对值相同补码 : 符号位为 1 数值部分与原码各位相反, 且末位加 1 移码 : 符号位与补码相反, 数值位与补码相同 18

19 以定点整数为例, 用数轴形式说明原码反码补码移码表示范围和可能的数码组合情况 19

20 将十进制真值 (-127,-1,0,+1,+127) 列表表示成二进制数及原码反码补码移码值十进制真值二进制真值原码表示反码表示补码表示移码表示负数时符号位 + 0;- 1 数值位各位取反数值位末位加 1 符号位 ( 正负数 ) 取反 20

21 设机器字长 16 位, 定点表示, 尾数 15 位, 数符 1 位, 问 : (1) 定点原码整数表示时, 最大正数是多少? 最小负数是多少? (2) 定点原码小数表示时, 最大正数是多少? 最小负数是多少? 定点原码整数最大正数 (2 15-1) = 最小负数 (2 15-1) = 定点原码小数最大正数最小负数 ( ) = +(1-1/32768) -( ) = -(1-1/32768) 21

22 2009 考研真题一个 C 语言程序在一台 32 位机器上运行程序中定义了三个变量 x,y 和 z, 其中 x 和 z 是 int 型,y 为 short 型当 x=127, y=-9 时, 执行赋值语句 z=x+y 后,x y 和 z 的值分别是 : A. x= fh, y=fff9h, z= h B. x= fh, y=fff9h, z=ffff0076h C. x= fh, y=fff7h, z=ffff0076h D. x= fh, y=fff7h, z= h 22

23 目录回顾 : 整数的表示方法浮点数的表示方法字符与字符串的表示方法汉字的表示方法校验码 23

24 数据格式浮点数浮点数 : 小数点位置可变, 形如科学计数法中的数据表示浮点数格式定义 : N= R e M M: 尾数 (mantissa), 是一个纯小数, 表示数据的全部有效数位, 决定着数值的精度 ; R: 基数 (radix), 可以取 , 表示当前的数制 ; 计算机中, 一般默认为 2, 隐含表示 e: 阶码 (exponent), 是一个整数, 用于指出小数点在该数中的位置, 决定着数据数值的大小机器数的一般表示形式阶符阶码数符尾数数符阶符阶码尾数 24

25 科学计数法的表示一个十进制数可以表示成不同的形式 : ( N) 同理, 一个二进制数也可以有多种表示 : ( N)

26 浮点数规格化浮点数的表示 = = 机器数的表示不同, 不利于运算规格化的目的保证浮点数表示的唯一性保留更多地有效数字, 提高运算的精度规格化要求 1/R 尾数 <1; 规格化处理 : 规格化尾数向左移 n 位 ( 小数点右移 ), 同时阶码减 n; 尾数向右移 n 位 ( 小数点左移 ), 同时阶码加 n 左规右规 26

27 浮点数的规格化尾数用原码表示时尾数最高数值位为 1; 尾数形如 0.1 ( 正 ); 或 1.1 ( 负 ); 例如, 要规格化则变为 ; 尾数用补码表示时要规格化则变为 ; 尾数最高数值位和尾数符号位相反 ; 尾数形如 0.1 ( 正 ); 或 1.0 ( 负 ) 例如, 要规格化, 则变为 ; 要规格化, 则变为 ; 27

28 浮点数的数据表示范围上溢区负数区下溢区正数区上溢区最小负数最大负数 0 最小正数最大正数尾数负的最小值负的最大值正的最小值正的最大值阶码正的最大值负的最小值负的最小值正的最大值浮点数的溢出 : 阶码溢出上溢 : 阶码大于所能表示的最大值 ; 下溢 : 阶码小于所能表示的最小值 ; 机器零 : 尾数为 0, 或阶码小于所能表示的最小值 ; 28

29 浮点数的最大小值 The Principle of Computer Organization, BUPT, 2017 Spring 移码表示 [-2 m,+(2 m -1)] 补码表示 [-1,+(1-2 -n )] 设浮点数格式为 1 位阶符 m 位阶码 1 位数符 n 位尾数最小负数最大负数最小正数最大正数非规格化数据规格化数据真值机器数机器数真值 ( 2m -1 ) -2 -n 2-2m +2 -n 2-2m +(1-2 -n ) 2 +(2m -1) ; 同左同左 ; ; ( n ) 2-2m ; ; ; 同左 m 同左 29

30 例 1 设浮点数的阶码 6 位 ( 含符号位 ), 尾数为 10 位 ( 含符号位 ), 阶码采用补码表示, 尾数采用原码表示, 分析其浮点数表示范围最大正数最大正数为即 ( ) 2 31 该浮点数即为规格化数形式 ;

31 例 1 设浮点数的阶码 6 位 ( 含符号位 ), 尾数为 10 位 ( 含符号位 ), 阶码采用补码表示, 尾数采用原码表示, 分析其浮点数表示范围最小正数 1 非规格化数形式最小正数为即 (25 ) = 规格化数形式最小正数为 (25 ) =

32 例 1 设浮点数的阶码 6 位 ( 含符号位 ), 尾数为 10 位 ( 含符号位 ), 阶码采用补码表示, 尾数采用原码表示, 分析其浮点数表示范围最小负数最小负数为 m 1 n 即 -( ) 2 (25-1) = -( ) 2 31 该浮点数即为规格化数形式 ; 32

33 例 1 设浮点数的阶码 6 位 ( 含符号位 ), 尾数为 10 位 ( 含符号位 ), 阶码采用补码表示, 尾数采用原码表示, 分析其浮点数表示范围最大负数 1 非规格化数形式 m 1 n 最大负数为即 (25 ) = 规格化数形式最大负数为即 (25 ) = m 1 n 33

34 例 2 设浮点数的阶码 6 位 ( 含符号位 ), 尾数为 10 位 ( 含符号位 ), 阶码和尾数均采用补码表示, 分析其规格化浮点数表示范围最大正数阶码最大尾数最大最大正数为 ( ) 2 31 最小正数最小正数为即 = 注意 : 不是因为不是规格化数

35 例 2 设浮点数的阶码 6 位 ( 含符号位 ), 尾数为 10 位 ( 含符号位 ), 阶码和尾数均采用补码表示, 分析其规格化浮点数表示范围最小的负数最小负数为即 2 31 (-1)= 最大的负数最大负数为即 -( ) 2-32 注意 : 因有规格化要求, 不是

36 浮点数的 IEEE754 标准表示 The Principle of Computer Organization, BUPT, 2017 Spring IEEE(Institute of Electrical and Electronics Engineers) 美国电气及电子工程师学会 IEEE 是一家总部在美国的工程技术和电子专家的组织 ; IEEE 致力于电气电子计算机工程和与科学有关的领域的开发和研究, 也是计算机网络标准的主要制定者为便于软件移植, 按照 IEEE754 标准, 实际机器内 32 位浮点数和 64 位浮点数的标准格式如下 : 32 位浮点数 S E M 0 64 位浮点数 1 位数符位阶码, 包括阶符位尾数, 仅为数值部分 51 S E M 0 36

37 32 位浮点数的 IEEE754 标准表示 The Principle of Computer Organization, BUPT, 2017 Spring 数符 S 阶码 E 尾数 M 数符 S: 表示浮点数的符号, 占 1 位,0 正数 1 负数 ; 尾数 M:23 位, 原码纯小数表示, 小数点在尾数域的最前面 ; 由于原码表示的规格化浮点数要求, 最高数值位始终为 1, 因此该标准中隐藏最高数值位 (1), 尾数的实际值为 1.M; 阶码 E:8 位, 采用有偏移值的移码表示 ; 移 127 码, 即 E=e+127,E 的 8 位二进制数即为移 127 码的编码 ; 浮点数的真值 :N=(-1) S (1.M) 2 E-127 为什么不是移 128 而是移 127? 37

38 IEEE754 标准格式 (64 位格式 ) 其真值表示为 : x=(-1) S (1.M) 2 E-1023 e=e

39 IEEE754 标准的数据表示 IEEE754 标准中的阶码 E 正零负零 E= ,M= E 与 M 均为零, 正负之分由数据符号确定 ; 正无穷负无穷 ~ E= ,M= E 为全 1,M 为全零, 正负之分由数据符号确定 ; 阶码 E 的其余值 ( ~ ) 为规格化数据 ; 真正的指数 e 的范围为 -126~

40 IEEE754 标准对特殊数据的表示符号位 S 阶码 E 尾数 M 数值 N 0/1 0 =0 0 0/1 0 0 (-1) S (0.M) /1 1~254 0 (-1) S (1.M) 2 E-127 0/ NaN( 非数值 ) 0/1 255 =0 (-1) S ( 无穷大 ) 40

41 非规范 (Denormalized) 浮点数 =? , 表达为规范浮点数则为指数小于允许的最小指数值! 当浮点数的指数为允许的最小指数值, 即 e min 时, 尾数不必是规范化的 , 其中指数 -126 等于 e min 41

42 [ 例 1] 若浮点数 x 的 754 标准存储格式为 ( ) 16, 求其浮点数的十进制数值解 : ( ) 16 = 数符 S 阶码 E 尾数 M 指数 e=e-127= = =3 尾数 1.M= = 浮点数 N =(-1) S (1.M) 2 e = (-1) 0 ( ) 2 3 = (11.375) 10 42

43 [ 例 2] 将 ( ) 10 转换成 754 标准的 32 位浮点数的二进制存储格式解 : ( ) 10 =( ) 2 将尾数规范为 1.M 的形式 : = 可得 : M = S = 0 E = 4+127=131= 故,32 位浮点数的 754 标准格式为 : = (41A4C000) 16 e=4 43

44 单精度浮点数与双精度浮点数高级语言的 float double 使用的即是 IEEE754 规定的格式 float :32 位浮点值, 也叫单精度浮点数 (4 字节保存 ) double:64 位浮点值, 也叫双精度浮点数 (8 字节保存 ) 单精度浮点数的例子 : 位 8 位 7 位 8 位 8 位 44

45 单精度浮点数与双精度浮点数除 0 之外,IEEE754 标准中单精度浮点数所能表示的绝对值最小的规格化浮点数的格式为 : S V=(-1) S (1.M)= (-1) S ( ) 除 ± 之外,IEEE754 标准中单精度浮点数所能表示的绝对值最大的规格化浮点数的格式为 : S V=(-1) S (1.M)= (-1) S ( ) 45

46 例如 : 将下列十进制数表示成 IEEE754 格式的 32 位浮点数二进制存储形式 27/32 11/512 解 : 27/32=27*(1/32) = ( ) 2 *2-5 尾数 : ; 阶码 :e=-5+4=-1,e=e+127=126 IEEE754 数据 : /512= ( ) 2 *2-9 尾数 :1.011 ; 阶码 :e=-9+3=-6,e=e+127=121 IEEE754 数据 :

47 例 : 将十进制数 -54 表示成二进制定点数 (16 位 ) 和浮点数 (16 位, 其中数值部分 10 位, 阶码部分 4 位, 阶符和数符各取 1 位 ), 并写出它在定点机和浮点机中的机器数形式令 x = -54, 则 x = 位定点数真值表示 : x = 定点机器数形式 [x] 原 : [x] 补 : 浮点数规格化表示 :x = -( ) 浮点机器数形式 [x] 原 : [x] 补 : ; ; 非 IEEE754 标准 47

48 假设一个 32 位非零规格化浮点数 x, 真值表示为 : 问 : 它所表示的规格化的最大正数最小正数最大负数最小负数是多少?( 尾数用原码表示 ) 最大正数 : 最小正数 : 最小负数 : 最大负数 : 数符阶码尾数 x=[1+( )] 数符阶码尾数 x= 数符阶码尾数 x=-[1+( )] 数符阶码尾数 x=

49 计算机储存程序的特点之一是把数据和指令都作为二进制信号看待今有一计算机字长 32bit, 数符位是第 31bit; 单精度浮点数格式如图所示位 23 位对于二进制数表示一个补码整数, 其十进制值是多少? 2 表示一个无符号整数, 其十进制值是多少? 3 表示一个 IEEE754 标准的单精度浮点数, 其值是多少? 49

50 二进制数表示一个补码整数, 其十进制值是多少? 作为补码整数, 其对应的原码是十进制值是 -( ) 2 表示一个无符号整数, 其十进制值是多少? 作为无符号整数, 其十进制值是

51 二进制数作为 IEEE754 标准的单精度浮点数阶码 E 是指数 e= 阶码 E-127= = B=-96D 尾数 M= 则 1.M = = 单精度浮点数值为 : X =(-1) s 1.M 2 e =-( ) 2-96 = -( ) 2-95 = -( ) 2-95 =

52 2010 考研真题假定变量 i,f,d 数据类型分别为 int, float, double(int 用补码表示,float 和 double 用 IEEE754 单精度和双精度浮点数据格式表示 ), 已知 i=785,f=1.5678e3,d=1.5e100, 若在 32 位机器中执行下列关系表达式, 则结果为真的是 () (I) i==(int)(float)i (II)f==(float)(int)f (III)f==(float)(double)f (IV)(d+f)-d==f A. 仅 I 和 II B. 仅 I 和 III C. 仅 II 和 III D. 仅 III 和 IV 关键是 == 两端的数据类型是否一致! 52

53 目录回顾 : 整数的表示方法浮点数的表示方法字符与字符串的表示方法汉字的表示方法校验码 53

54 数据格式十进制数串的表示方法字符串形式每个十进制数位占用一个字节 ; 除保存各数位, 还需要指明该数存放的起始地址和总位数 ; 主要用于非数值计算的应用领域压缩的十进制数串形式采用 BCD 码表示, 一个字节可存放两个十进制数位 ; 节省存储空间, 便于直接完成十进制数的算术运算 ; 用特殊的二进制编码表示数据正负, 如 1100 正 1101 负 54

55 字符与字符串的表示方法 ASCII 码 ( 美国国家信息交换标准字符码 ) 包括 128 个字符, 共需 7 位编码 ; ASCII 码规定 : 最高位为 0, 余下 7 位作为 128 个字符的编码最高位的作用 : 奇偶校验 ; 扩展编码字符串指连续的一串字符, 每个字节存一个字符当存储字长为 2 或 4 个字节时, 在同一个存储单元中 ; 可按从低位字节向高位字节的顺序存放字符串的内容 ; 或按从高位字节向低位字节的次序顺序存放字符串的内容 55

56 目录回顾 : 整数的表示方法浮点数的表示方法字符与字符串的表示方法汉字的表示方法校验码 56

57 汉字的表示方法汉字的输入编码目的 : 直接使用西文标准键盘把汉字输入到计算机分类 : 主要有数字编码拼音码字形编码三类汉字内码用于汉字信息的存储交换检索等操作的机内代码一般用两个字节表示, 两个字节的最高位均规定为 1 汉字字模码用点阵表示的汉字字形代码, 用于汉字的输出 57

58 中文编码字符代码化 ( 输入 ) 数字码拼音码输入码向机内码转换字形码机内码机内码向字形码转换显示输出打印输出 58

59 汉字字模码汉字点阵类型点阵占用字节数简易型普及型提高型精密型

60 目录回顾 : 整数的表示方法浮点数的表示方法字符与字符串的表示方法汉字的表示方法校验码 60

61 校验码 ( 数据校验 ) 数据校验原因为减少和避免数据在计算机系统运行或传送过程中发生错误, 在数据的编码上提供了检错和纠错的支持数据校验码的定义能够发现某些错误或具有自动纠错能力的数据编码 ; 也称检错码 ; 数据校验的基本原理是扩大码距 ; 码距 : 任意两个合法码之间不同的二进制位的最少位数 ; 仅有一位不同时, 称其码距为 1 整个编码系统中任意两个码字的的最小距离就是该编码系统的码距 61

62 码距及作用设用 3 位二进制表示 8 种状态 8 种编码都用到了, 此时码距为 1 任何一种状态的三位码中的一位或几位出错, 就变成另一个合法码无查错能力若用四位二进制表示 8 个状态只用其中的 8 种编码, 而把另 8 种编码作为非法编码可使码距扩大为 2 注意 : 并不是任选 8 种编码都可扩大码距 62

63 码距及作用码距为 1 码距为 2 63

64 校验码的类型 The Principle of Computer Organization, BUPT, 2017 Spring 奇偶校验码判断数据中 1 的个数设置 1 位校验位 ; 分奇校验和偶校验两种, 只能检错, 无纠错能力 ; 海明校验码在奇偶校验的基础上增加校验位而得 ; 具有检错和纠错的能力 ; 循环冗余校验码 (CRC) 通过模 2 的除法运算建立数据信息和校验位之间的约定关系 ; 具有很强的检错纠错能力 64

65 奇偶校验码概念奇偶校验原理在数据中增加 1 个冗余位, 使码距由 1 增加到 2; 如果合法编码中有奇数个位发生了错误, 就将成为非法代码增加的冗余位称为奇偶校验位校验的类型偶校验 : 每个码字 ( 包括校验位 ) 中 1 的数目为偶数奇校验 : 每个码字 ( 包括校验位 ) 中 1 的数目为奇数校验过程发送端 : 按照校验类型, 在发送数据后添加校验位 P; 接收端 : 对接收到的数据 ( 包括校验位 ) 进行同样类型的校验, 决定数据传输中是否存在错误 ; 65

66 奇偶校验码校验原理偶校验 : 在接收端求校验位 P =D 7 D 6 D 5 D 4 D 3 D 2 D 1 D 0 P 若 P =0, 则无错 ; 若 P =1, 则有错奇校验 : 在接收端求校验位 P =D 7 D 6 D 5 D 4 D 3 D 2 D 1 D 0 P 若 P =1, 则无错 ; 若 P =0, 则有错电路实现 : 一般采用异或电路得到校验位求校验码偶校验码奇校验码

67 奇偶校验码例题校验码字校验位例 1: 数据奇校验码偶校验码例 2: 数据 : 发送端 ( 门电路 ) 偶校验码出错! 接收端 67

68 奇偶校验码例题例 3: 数据 : 发送端 ( 门电路 ) 奇校验码正确奇偶校验只能发现接收端奇数个错误, 且不能纠正错误! 68

69 海明码海明码是 1950 年提出的 ; 只要增加少数的几位校验码, 即可检测出多位出错, 并能自动恢复一或几位出错信息 ; 实现原理 : 在一个数据中加入几个校验位, 每个校验位和某几个特定的信息位构成偶校验的关系 ; 接收端对每个偶关系进行校验, 产生校验因子 ; 通过校正因子区分无错和码字中的 n 个不同位置的错误 ; 不同代码位上的错误会得出不同的校验结果 ; 69

70 海明码确定校验位的位数设 K 为有效信息的位数,r 为校验位的位数, 则整个码字的位数 N 应满足不等式 : N=K+r 2 r -1 为什么? 通常称为 (N,K) 海明码设某 (7,4) 海明码表示的码字长度为 7 位, 校验位数为 3位例如 : 数据 D 3 D 2 D 1 D 0 =1001 K=4,r+5 2 r ; 可知, 需要校验位 3 位 P 3 P 2 P 1 ; 70

71 海明码确定校验位的位置数据表示数据位 D(D i D i-1 D 1 D 0 ) 校验位 P(P j P j-1 P 2 P 1 ) 海明码 H ( 包括数据位和校验位 ):H m H m-1 H 2 H 1 ; 分组原则每个校验位 P i 从低到高被分在海明码中位号 2 i-1 的位置 ; 例如 : 数据 D 3 D 2 D 1 D 0 =1001, 校验位 P 3 P 2 P 1 海明码共 7 位 H 7 H 6 H 2 H 1, 各位分配如下 : H 7 H 6 H 5 H 4 H 3 H 2 H 1 D 3 D 2 D 1 P 3 D 0 P 2 P 1 71

72 海明码校验分组校验原则海明码的每一位 H i 有多个校验位校验, 其关系是被校验的每一位位号等于校验它的各校验位的位号之和 ; 每个信息位的位置写成用 2 的幂次之和的形式 ; 例如 H 7 参与 H 1 H 2 H 4 的校验 ; H 6 参与 H 2 H 4 的校验 ; H 5 参与 H 1 H 4 的校验 ; H 3 参与 H 1 H 2 的校验 ; 分组情况第一组 (P 1 D 3 D 1 D 0 ) 第二组 (P 2 D 3 D 2 D 0 ) 第三组 (P 3 D 3 D 2 D 1 ) 第一组 P 1 第二组 P 2 第三组 P 3 H 7 H 6 H 5 H 4 H 3 H 2 H 1 D 3 D 2 D 1 P 3 D 0 P 2 P 1 72

73 海明码校验位的形成校验位形成公式 P 1 = 第一组中所有位 ( 除 P 1 ) 求异或 P j = 第 j 组中所有位 ( 除 P j ) 求异或为了能检测两个错误, 增加一位校验 P j+1, 放在最高位 P j +1 = 所有位 ( 包括 P 1,P 2,, P j ) 求异或第一组 (P 1 D 3 D 1 D 0 ) 第二组 (P 2 D 3 D 2 D 0 ) 第三组 (P 3 D 3 D 2 D 1 ) 例如 : P 1 =D 3 D 1 D 0 =1 0 1=0 P 2 =D 3 D 2 D 0 =1 0 1=0 P 3 =D 3 D 2 D 1 =1 0 0=1 P 4 =D 3 D 2 D 1 D 0 P 3 P 2 P 1 = =1 但不能纠错! 73

74 海明码接收端校验 (1/2) 接收端接收到数据后, 分别求 S 1,S 2,S 3,,S j S 1 = 第一组中所有位 ( 包括 P 1 ) 求异或 S j = 第 j 组中所有位 ( 包括 P j ) 求异或 S j +1 = P j +1 所有位 ( 包括 P 1,P 2,, P j ) 求异或当 S j +1 =1 时, 有一位出错 ; 由 S j S 3 S 2 S 1 的编码指出出错位号, 将其取反, 即可纠错当 S j +1 =0 时, 无错或有偶数个错 ( 两个错的可能性比较大 ); 当 S j S 3 S 2 S 1 = 时, 接收的数无错, 否则有两个错 74

75 海明码接收端校验 (2/2) 同上例, 接收端接收的数据为接收端求 S S 1 = =0 S 2 = =0 S 3 = =0 S 4 = =0 若接收端接收到错误的数据 S 1 = =0 S 2 = =1 S 3 = =1 S 4 = =1 H 8 H 7 H 6 H 5 H 4 H 3 H 2 H 1 P 4 D 3 D 2 D 1 P 3 D 0 P 2 P 第一组 (P 1 D 3 D 1 D 0 ) 第二组 (P 2 D 3 D 2 D 0 ) 第三组 (P 3 D 3 D 2 D 1 ) 无错误! S 4 =1, 有错误! S 3 S 2 S 1 =110,H 6 位有错, 应取反! 75

76 练习设待校验的数据为 D7~D0= , 写出其海明校验码 The Principle of Computer Organization, BUPT, 2017 Spring 解 1 确定海明校验位的位数因为 K=8, 由 N=K+r 2 r -1, 得 9+r 2 r, 校验位的位数为 r=4 2 确定校验位的位置 i: D 7 D 6 D 5 D 4 P 4 D 3 D 2 D 1 P 3 D 0 P 2 P 1 3 分组 (N 位分 r 组 ) 位号 i D 7 D 6 D 5 D 4 P 4 D 3 D 2 D 1 P 3 D 0 P 2 P 第一组 (P 1 ) 第二组 (P 2 ) 第三组 (P 3 ) 第四组 (P 4 ) 76

77 练习设待校验的数据为 D7~D0= , 写出其海明校验码 4 校验位的形成 P1=D6 D4 D3 D1 D0 = 1; P2=D6 D5 D3 D2 D0 = 1 P3=D7 D3 D2 D1 =1 ; P4=D7 D6 D5 D4 =0 所以, 信息码的海明校验码为 :

78 海明码的纠错与检错能力一个系统能纠正一位差错时, 码距最小是 3; 码距为 3 时, 或能纠正一位错, 或能检测二位错 ; 但不能同时纠正一位错并检测二位错码距为 1 至 7 时, 海明码的纠错和检错能力如右表 : 码距越大, 纠错能力越强, 但数据冗余也越大, 即编码效率低了码距码能力检错纠错或并并并并 3 78

79 CRC 校验 CRC 的工作方法在发送端产生一个循环冗余码, 附加在信息位后面一起发送到接收端 ; 接收端收到的信息按发送端形成循环冗余码同样的算法进行校验 ; 若无错, 则接收 ; 若有错, 需重发 CRC 的特点可检测出所有奇数位错 ; 可检测出所有双比特的错 ; 可检测出所有小于等于校验位长度的突发错 CRC 码的信息字段和校验字段的长度可以任意选定 79

Introduction to Computer Systems /18-243, spring st Lecture, Jan. 12th

Introduction to Computer Systems /18-243, spring st Lecture, Jan. 12th 计算机组成原理习题课 1 授课老师 : 王浩宇 haoyuwang@bupt.edu.cn 1 练习 : 机器数的表示和相互转化练习 1: 当十六进制数 9B 和 FF 分别表示为原码补码反码移码和无符号数时, 所对应的十进制数各为多少 ( 设机器数采用一位符号位 )? 16 进制真值无符号数原码 ( 真值 ) 反码 ( 真值 ) 补码 ( 真值 ) 移码 ( 真值 ) 9BH 二进制十进制