计算机原理及系统结构 第六讲 主讲教师：赵宏伟 　　　　　　　　　　　　　　　　学时：64.

Presentation on theme: "计算机原理及系统结构 第六讲 主讲教师：赵宏伟 　　　　　　　　　　　　　　　　学时：64."— Presentation transcript:

1 计算机原理及系统结构 第六讲 主讲教师：赵宏伟 　　　　　　　　　　　　　　　　学时：64

2 第3章 数据表示、数据运算算法 和逻辑电路实现

3 本章主要内容 信息编码、码制转换与检错纠错码 数据表示——常用的信息编码 二进制数值数据的编码与运算算法

4 数字化编码二要素 数值 文字 符号 语音 图形 图像 等统称数据， 在计算机内部，都必须用数字化编码的形式 被 存储 加工 和 传送
被 存储 加工 和 传送 数字化编码二要素: 少量简单的基本符号 一定的组合规则 用以表示大量复杂多样的信息 P62

5 基二码（二进制码） 只使用两个基本点符号：１ ０ 符号个数最少，物理上容易实现 与二值逻辑的 真 假 两个值对应简单
只使用两个基本点符号：１ ０ 符号个数最少，物理上容易实现 与二值逻辑的 真 假 两个值对应简单 用二进制码表示数值数据运算规则简单 P63

6 N 进位记数法与进制转换 D = r 进位记数法 -k i * i i=m-1 N 代表一个数值 r 是这个数制的基(Radix)
表示m+k位的值求累加和 P64

7 从二进制数求其十进制的值，逐位码权累加求和
十进制转二进制 整数部分除2取余 小数部分乘2取整 2 1 1 1 低 0.625 * 2 2 5 高 1 * 2 1 * 2 2 2 1 1 1 2 高 0.0 低 除尽为止 求得位数满足要求为止 从二进制数求其十进制的值，逐位码权累加求和 P65

8 二到八或十六进制转换 小数部分不足位数要补零凑足,否则出错。 说明：整数部分不足位数对转换无影响， 二到八 从小数点向左右三位一分组
二到八 从小数点向左右三位一分组 （ )2 = ( )8 010 二到十六 从小数点向左右四位一分组 （ )2 = ( 9C . 4 )16 0100 说明：整数部分不足位数对转换无影响， 小数部分不足位数要补零凑足,否则出错。 P67

9 计算机原理及系统结构 第七讲 主讲教师：赵宏伟 　　　　　　　　　　　　　　　　学时：64

10 二进制数据算术运算规则 (1) 加法运算规则 0+0=0 例如： 0101 0+1=1 +) 0001 1+0=1 0110
(1) 加法运算规则 0+0= 例如： 0+1= ) 0001 1+0= 1+1=0 并产生进位 (2) 减法运算规则 0-0= 例如： 0-1=1 并产生借位 ) 1-0= 1-1=0

11 二进制数据算术运算规则 0X0=0 X) 0101 0X1=0 1101 1X0=0 1101 1X1=1 1000001 0000
乘法运算规则 例如： 0X0= X) 0101 0X1= 1X0= 1X1= 除法运算规则 例如： /1001 1001 1011 01001 0000 P68

12 二进制数据逻辑运算规则 0∨0=0 /0=1 0∨1=1 /1=0 1∨0=1 1∨1=1 0000 0∧0=0 0⊕0=0
（5）逻辑或运算规则 （7）逻辑非运算规则 0∨0= /0=1 0∨1= /1=0 1∨0=1 1∨1=1 （6）逻辑与运算规则 （8）逻辑异或运算规则 0∧0= ⊕0=0 0∧1= ⊕1=1 1∧0= ⊕0=1 1∧1= ⊕1=0 0000

13 计算机原理及系统结构 第八讲 主讲教师：赵宏伟 　　　　　　　　　　　　　　　　学时：64

14 检错纠错码 为了提高计算机的可靠性，除了采取选用更高可靠性的器件，更好的生产工艺等措施之外，还可以从数据编码上想一些办法，即采用一点冗余的线路，在原有数据位之外再增加一到几位校验位，使新得到的码字带上某种特性，之后则通过检查该码字是否仍保持有这一特性，来发现是否出现了错误，甚至于定位错误后，自动改正这一错误，这就是我们这里说的检错纠错编码技术。 P70

15 纠错码分类 纠错码 线性码 非线性码 分组码 卷积码 非循环码 循环码 随机 错误 突发 错误 非系统码 系统码 校验位与信息位 的形成关系
信息位与校验位 的约束条件 卷积码 码字本身的 结构特点 非循环码 循环码 信息位与校验位排列位置关系 随机 错误 突发 错误 非系统码 系统码 P70

16 几种常用的检错纠错码 我们只介绍三种常用的检错纠错码： 原始数据 码 字 结果数据 传送 编码过程 译码过程
奇偶检错码， 用于并行数据传送中 海明检错与纠错码，用于并行数据传送中 循环冗余码， 用于串行数据传送中 原始数据 码 字 结果数据 传送 编码过程 译码过程 形成校验位的值，加进特征 检查接送的码字，发现 / 改正错误

17 奇偶校验码 用于并行码检错 原理：在 k 位数据码之外增加 1 位校验位， 使 K+1 位码字中取值为 1 的位数总保持 为 偶数（偶校验）或 奇数（奇校验）。 例如： 原有数字位 两个新的码字 偶校验 奇校验 校验位 P71

18 奇偶校验码的实现电路 p 编码电路 译码电路 + + 同左侧电路 + + + + + + 奇较验 偶校验 出错指示 八位数据位
奇较验 偶校验 出错指示 p 编码电路 译码电路 + + 同左侧电路 八位数据位 + + + + + + D7 D6 D5 D D3 D2 D1 D0 P (校验位)

19 海明校验码 用于多位并行数据检错纠错处理 实现：为 k 个数据位设立 r 个校验位， 使 k+r 位的码字同时具有这样两个特性：

20 海明码的编码方法 合理地用 k 位数据位形成 r 个校验位的值，即保证用 k 个数据位中不同的数据位组合来形成每个校验位的值，使任何一个数据位出错时，将影响 r 个校验位中不同的校验位组合起变化。换言之，通过检查是哪种校验位组合起了变化，就能确定是哪个数据位错，对该位求反则实现纠错。 有时两位错与某种情况的一位错对校验位组合的影响相同，必须加以区分与解决。

21 海明码的实现方案 例如： k =3, r =4 + ：异或 编码方案 译码方案 D3 D2 D1 P4 P3 P2 P1
+ ：异或 P1 = D2 + D1 P2 = D D1 P3 = D3 + D2 编码方案 P4 = P3 + P2 + P1 + D3 + D2 + D1 S1 = P D2 + D1 S2 = P2 + D D1 S3 = P3 + D3 + D2 S4 = P4 + P3 + P2 + P1 + D3 + D2 + D1 译码方案 P72

22 检错纠错码小结 (1) K位码有2K 个编码状态，全用于表示合法码，则任何一位出错, 均会变成另一个合法码，不具有检错能力。
(2) 从一个合法码变成另一个合法码，只少要改变几位码的值，称为最小码距(码距)。 (3) K+1 位码，只用其 2K 个状态，可使码距 为 2 , 如果一个合法码中的一位错了，就成为非法码，通过检查码字的合法性，就得到检错能力，这就是奇偶校验码。

23 检错纠错能力 (4) 对 k 位数据位，当给出 r 位校验位时， 要发现并改正一位错， 须满足如下关系：
2r > = k + r +1 ； 要发现并改正一位错，也能发现两位错,则应： 2r-1 >= k + r , 此时码距为 4。 (5) 若最小码距为 d (d>=2), 能发现 d-1 位错，或改正 (d-2)/2 (取整) 位错, 要发现 l 位错,并改正 t 位错，应满足如下条件: d >= l + t ( l >= t )

24 计算机原理及系统结构 第九讲 主讲教师：赵宏伟 　　　　　　　　　　　　　　　　学时：64

25 本章主要内容 信息编码、码制转换与检错纠错码 数据表示——常用的信息编码 二进制数值数据的编码与运算算法

26 基二码应用实例：数据表示 逻辑型数据 字符型数据 检错纠错码 奇偶校验 海明校验 循环冗余校验 数值型数据 定点小数 整数 浮点数
ASCII 码 EBCDIC 码 字符串 汉字 检错纠错码 奇偶校验 海明校验 循环冗余校验 数值型数据 定点小数 整数 浮点数 二—十进制数（BCD码）

27 逻辑型数据 逻辑型数据只有两个值：真 和 假， 对逻辑型数据可以执行逻辑的 与 或 非等基本逻辑运算。其规则如下：
逻辑型数据只有两个值：真 和 假， 正好可以用二进制码的两个符号分别表示， 例如 1 表示 真 则 表示 假 不必使用另外的编码规则。 对逻辑型数据可以执行逻辑的 与 或 非等基本逻辑运算。其规则如下：

28 逻辑型数据基本运算规则 X Y X与Y X或Y X的非

29 字符型数据的表示 字符作为人—机联系的媒介，是最重要的数据类型之一，当前的西文字符集由 128 个符号组成，通常用 8 位二进制编码,即用一个字节来表示每一个符号，当前通用的两个标准字符集是： ASCII 码： 即 American Standard Code for Information Interchange EBCDIC码：即 Extended Binary Coded Decimal Interchage Code ASCII码字符集具体编码如下表所示：

30 ASCII字符编码集 b6 b5 b b3 b2 b1 b0 NUL DLE SP @ P , p SOH DC ! A Q a q STX DC “ B R b r ETX DC # C S c s EOT DC $ D T d t ENQ NAK % E U e u ACK SYN & F V f v BEL ETB ‘ G W g w BS CAN ( H X h x HT EM ) I Y i y LF SUB * : J Z j z VT ESC ; K [ k { FF FS , < L \ l | CR GS = M ] m } SO RS > N ^ n ~ SI US / ? O _ o P75

31 字符串的表示与存储 字符串是指连续的一串字符，它们占据主存中连续的多个字节，每个字节存放一个字符，对一个主存字的多个字节，有按从低位到高位字节次序存放的，也有按从高位到低位字节次序存放的。表示字符串数据要给出串存放的主存起始地址和串的长度。例如：IF A>B THEN READ(C)就可以有如下不同的存放方式： I F A A F I > B T T B > 假定每个字 H E N N E H 由 4 个字节 R E A D D A E R 组成 ( C ) ) C (

32 汉字的表示 通常用两个字节表示一个汉字 为了与西文字符编码相区别（西文的ASCII码的最高一位编码值为0），表示一个汉字时，把两个字节的最高一位的编码值设定为 1，则该编码集的最多编码数量为 128 X 128。 这种编码方案与西文传送中的把ASCII码的最高一位用作奇偶校验位有矛盾。

33 数值数据在计算机内的格式 定点小数: N = N N N ……...N 整 数 : N = N N N ... N N
s -1 -2 -n 整 数 : N = N N N N N s n n-1 1 浮点数: N = M E E E E M M ...M -n s s m-1 1 -1 -2 基为 2 IEEE 标准： 阶码用移码，尾数用原码 符号位 阶码位 尾数数码位 总位数 短浮点数: 长浮点数: 临时浮点数: P76

34 二 十进制编码（BCD编码） 用四位二进制表示一位十进制， 16个编码状态选用其中的10个编码 有多种方案，例如： 又可区分为：
8421码，余 3 码，循环码 又可区分为： 有权码：每位上的 1 代表确定的值 无权码：无法确定每位上的 1 代表的值

35 有权码 无权码 8421 余3码 循环码 84-2-1 P79

36 计算机原理及系统结构 第十讲 主讲教师：赵宏伟 　　　　　　　　　　　　　　　　学时：64

37 本章主要内容 信息编码、码制转换与检错纠错码 数据表示——常用的信息编码 二进制数值数据的编码与运算算法

38 定点小数表示: Ns N1 N2 … Nn （纯小数）原码，反码，补码的定义 [ X ] = (2 - 2 )+ X X
Mod ( ) 反 X 0 < X < 1 Mod 2 2 + X -1 < X < 0 补 P82

39 定点小数表示: Ns N1 N2 … Nn 原 码 定义： [ X ] 原 =
10000 结论：原码为符号位加数的绝对值，0正 1负 原码零有两个编码，+0 和 -0编码不同 原码难以用于加减运算，但乘除方便 X 0 < X < 1 1 - X -1 < X < 0 P83

40 定点小数表示: Ns N1 N2 … Nn 模 2 补码 定义： [ X ]补 =
结论：补码最高一位是符号位，0 正 1 负 补码表示为：2*符号位 + 数的真值 补码零只有一个编码，故能表示 -1 补码能很好地用于加减（乘除）运算 X 0 < X < 1 2 + X -1 < X < 0 MOD 2 P83

41 定点小数表示: Ns N1 N2 … Nn 反 码 定义：[ X ]反 = 实例： X1 = 0.10110 -0.10110 0.0000
11111 结论：反码负数为符号位跟每位的反, 0 正 1 负 反码零有二个编码，分+0 和 -0 反码难以用于加减运算，有循环进位问题 X 0 < X < 1 (2-2-n) + X -1 < X < 0 MOD (2-2-n) P86

42 计算机原理及系统结构 第十一讲 主讲教师：赵宏伟 　　　　　　　　　　　　　　　　学时：64

43 整数的编码表示 整数的 原码 反码 补码 表示 因此整数的模与整数位数有关， 例如：整数六位编码：
整数的 原码 反码 补码 表示 与小数的三种表示基本相同， 差别仅表现在小数点的位置， 可以认为整数的小数点在最低数值位的右侧 因此整数的模与整数位数有关， 讲课中不大用整数讲 原 反 补 码定义 例如：整数六位编码： X = [X]原= [X]补= X = [X]原= [X]补= P87

44 原 反 补码表示小结 正数的 原码、反码、补码表示均相同， 零的原码和反码均有 2个编码，补码只 1个码
符号位为 0，数值位同数的真值。 零的原码和反码均有 2个编码，补码只 1个码 负数的 原码，反码，补码表示均不同， 符号位为 1，数值位：原码为数的绝对值 反码为每一位均取反码 补码为反码再在最低位+1 由[X]补求[-X]补：每一位取反后,再在最低位+1 n 由 [X]补 求 X 的真值：X= Xi * 2-i i=1

45 数据的算术运算 补码 加 减 法 运算 原码一位乘法运算 原码一位除法运算 补码一位乘法运算 补码一位除法运算 原码二位乘法运算
原码一位乘法运算 原码一位除法运算 补码一位乘法运算 补码一位除法运算 原码二位乘法运算 补码二位乘法运算 其它快速乘除法运算方法简介

46 补码加减法的实现 [X + Y] = [X] + [Y] [X-Y] = [X] + [-Y]
[-Y] = 对 [Y] 逐位取反,再在最低位加 1 溢出判断： (1)正 + 正 得负 或 负 + 负 得正 (2)数字位有向符号位的进位，但符号位不产生向更高位的进位 (3)双符号位的值为 01 或 10 补 补 补 补 补 补 补 补

47 实现补码加减运算的逻辑电路 F 1 Fs F ALU Ｆ Ｘ Ｆ Ｙ Ｘ Ｆ 加 F X F /Y F Y 选通门 二选通门 X Y
OVR Z C F 1 Fs F ALU Ｆ　　　Ｘ Ｆ　　　Ｙ Ｘ　　　Ｆ 加 F X F /Y F Y 选通门 二选通门 X Y X X+Y X X-Y 1 0 1 目的 寄存器 源 寄存器 累加器 Ｆ　　　Ｘ Ｆ　　／Ｙ Ｆ　　　１ Ｘ　　　Ｆ 选通门 减 X F

48 补码加减法运算实例 X=0.1011 y= -0.0101 模 4 补码 [X] = 00 1011, [Y] = 11 1011
X+Y X-Y (溢出) 补 补 补

49 补码表示中的符号位扩展 由 [X]补 求 [X / 2]补 的方法 原符号位不变， 且符号位与数值位均右移一位，例如，
不同位数的整数补码相加减时， 位数少的补码数的符号位向左扩展， 一直扩展到与另一数的符号位对齐。

50 计算机原理及系统结构 第十二讲 主讲教师：赵宏伟 　　　　　　　　　　　　　　　　学时：64

51 原码一位乘运算 [X*Y]原 =( XＳ + YＳ ) ( X * Y ) 例如： X = 0.1101 Y = - 0.1011
* X 和 Y 符号异或为负 最终乘积原码表示为： 手工运算过程 计算机内运算的实现方法 部分积右移 部分积 乘数 P90 P92

52 原码一位乘运算 例如： X = Y = 问题： * 加法器只有两个数据输入端 加法器与乘运算数据位数相同 解决方案： 每次求出部分积，而不是一次总累加 变每次左移被乘数为右移部分积 　 判乘数每一位的值用固定的一位线路 手工运算过程

53 实现原码一位乘法的逻辑线路图 加 法 器 部 分 积 被 乘 数 乘 数 F 最低位 加运算 移位线路 每位1套 移位电路 第 i 位
加 法 器 部 分 积 被 乘 数 乘 数 F 最低位 加运算 移位线路 每位1套 第 i 位 第 i +1位 第 i 位 第 i -1位 F/2→X F→X F*2→X

54 原码一位乘法 1 加 法 器 部 分 积 被 乘 数 乘 数 F 最低位 加运算 移位线路 每位1套 1 0 1 1 1 1 1 低位积 1 0 1 1 1 1 1 1 1 0 1 1 1 1

55 原码一位乘运算 例如： X = 0.1101 Y = - 0.1011 0. 1 1 0 1 ００ ００００累加器初值取零值
００ ００００累加器初值取零值 * ００　１１０１ ００　１１０１　初值０加被乘数 ００　０１１０１ 　部分积右移 　　 　　 将移出的一位保存起来 求第一次部分积 手工运算过程

56 原码一位乘运算 例如： X = Y = ００　０１１０ * ００　１１０１ ０１　００１１ 前次部分积加被乘数 ００　１００１１１　 部分积右移 　　　　　　　　　　　 将移出的一位保存起来 求第二次部分积 手工运算过程

57 原码一位乘运算 例如： X = Y = ００　１００１ * ００　００００ ００　１００１　　前次部分积加０ ００　０１００１１１　部分积右移 　　　　　　　　　　 　将移出的一位保存起来 求第三次部分积 手工运算过程

58 原码一位乘运算 最后一步２数符号异或求积的符号 例如： X = 0.1101 Y = - 0.1011 0. 1 1 0 1 ００ ０１００
００　０１００ * ００　１１０１ ０１　０００１ 前次部分积加被乘数 ００　１０００１１１１　部分积右移 　　　　　　　　　　　　 将移出的一位保存起来 求第四次部分积 手工运算过程 最后一步２数符号异或求积的符号

59 若把乘数放在一个移位寄存器中，该寄存器又用来接受加法器的移位输出，则判乘数的某一位也更方便
原码一位乘运算 例如： X = Y = ００　０１００ * ００　１１０１ ０１　０００１　 ００　１０００１１１１　 　　　　　　　　　　　　　 求第四次部分积 手工运算过程 若把乘数放在一个移位寄存器中，该寄存器又用来接受加法器的移位输出，则判乘数的某一位也更方便

60 除法运算 在计算机内实现除运算时，存在与乘法运算类似的几个问题： 加法器与寄存器的配合， 被除数位数更长，商要一位一位地计算出来等。这可以用左移余数得到解决，且被除数的低位部分可以与最终的商合用同一个寄存器，余数与上商同时左移。

61 原码一位除运算 原码一位除是指用原码表示的数相除，求出原码表示的商。除操作的过程中，每次求出一位商。
[ Y / X ]原 =( XＳ + YＳ )（ Y X ) 　　　原码一位除是指用原码表示的数相除，求出原码表示的商。除操作的过程中，每次求出一位商。 　　　从理解原理考虑，用恢复余数除法讲解计算机内的实现方法更直观方便，即确定上商应为１还是为０时，必须用被除数或中间余数减去除数，通过检查本次求得的余数为正还是为负才能知道，而不象人计算时用眼睛直接看出来的。若求出一个为负的余数来，通常应首先恢复其值为正，再求下一位商才有道理。但计算机内从来不用这种办法，而是直接用求得的负余数求下一位商。 P93

62 加减交替除法原理证明 1. 若第 i - 1次求商余数为 + R ,商1 余数 2. 则第 i 次求商 R =2R - Y
3. 则第 i+ 1次求商 R = 2( R + Y ) - Y = 2R + Y 实质是: 对上次负差直接左移, 本次用 +Y 求商即可。 i-1 i-1 若 R > 0 则 i i i-1 若 R < 0 商 0 i 恢复余数为正且左移得 2(R + Y ) i i+1 i i

63 实现原码一位除法运算的原理逻辑图 1→F F 加法器 C 乘商寄存器 上商 与或门 A 被除数(余数) 2C→C 与或门 B→F /B→F
2F→A F→A 计数器 Cd

64 原码一位除运算 [ Y / X ]原 =( Xs + Ys ) ( Y / X ) 例如： X = - 0.1101 Y = 0.1011
　　初态 　第１次 　第２次 　第３次 　第４次 　　　　　　 　第５次 1101 0111 X 和 Y 符号异或为负 最终商原码表示为： 　　　1 1101 余数为： * 2-4

65 被除数(余数) 商 开始情形 -Y <0, 商0 左移1位 +Y >0, 商1 左移1位 >0, 商1 左移1位 <0, 商0 左移1位 >0, 商1 +) X=0.1011 Y=0.1101 +) X / Y = ? [Y]补 = +) [-Y]补= +) +)