2.1.3自定义数据表示 目前在多数计算机中 数据存储单元(寄存器、主存储器、外存储器等)只存放纯数据 通过指令中的操作码来解释 数据的类型(定点数、浮点数、复数、字符、字符串、逻辑数、向量等) 进位制(2进制、10进制、16进制等) 数据字长(字、半字、双字、字节等) 寻址方式(直接寻址、间接寻址、相对寻址、寄存器寻址等) 数据的功能(地址、数值、控制字、标志等)等 同一种操作指令通常需要很多条 ·在高级语言和其它许多应用软件中 数据的属性必须由数据自己定义, 在高级语言与机器语言之间的语义差距,要靠编译器等填补 ·60年代开始, Burroughs公司在大型计算机中引入自定义数据表示方式 和带标志符的数据表示方式 1、带标志符的数据表示法 Burroughs公司的标志符数据表示方法 在B5000大型机中,每个数据有一位标志符 在B6500和B7500大型机中,每个数据有三位来标志符 在R-2巨型机中采用10位标志符 标志符 带有标志符的数据表示方式 2位2位1位4位 功能陷井 类型 10位标志符 在R-2巨型机中带标志符的数据表示方式 R-2巨型机中的标志符 功能位:操作数、指令、地址、控制字 陷井位:由软件定义四种捕捉方式 封写位:指定数据是只读的还是可读可写 类型位:对于操作数:二进制、十进制、定点数、浮点数、复数、 字符串、单精度、双精度等 对于地址:绝对地址、相对地址、变址地址、未连接的地址等 标志符由编译器或其它系统软件建立,对程序员透明 程序(包括指令和数据)的总存储量分析 数据存储量增加,指令存储量减少 例2.6:假设ⅹ处理机的数据不带标志符,其指令字长和数据字长均为32
2－1 2.1.3 自定义数据表示 • 目前在多数计算机中 数据存储单元（寄存器、主存储器、外存储器等）只存放纯数据 通过指令中的操作码来解释： 数据的类型（定点数、浮点数、复数、字符、字符串、逻辑数、向量等） 进位制（2 进制、10 进制、16 进制等） 数据字长（字、半字、双字、字节等） 寻址方式（直接寻址、间接寻址、相对寻址、寄存器寻址等） 数据的功能（地址、数值、控制字、标志等）等 同一种操作指令通常需要很多条 • 在高级语言和其它许多应用软件中 数据的属性必须由数据自己定义， • 在高级语言与机器语言之间的语义差距，要靠编译器等填补 • 60 年代开始，Burroughs 公司在大型计算机中引入自定义数据表示方式 和带标志符的数据表示方式 1、带标志符的数据表示法 • Burroughs 公司的标志符数据表示方法 在 B5000 大型机中，每个数据有一位标志符 在 B6500 和 B7500 大型机中，每个数据有三位来标志符 在 R-2 巨型机中采用 10 位标志符 标志符 数 值 带有标志符的数据表示方式 2 位 2 位 1 位 4 位 1 位 功能 陷井 封写 类型 校验 数 值 10 位标志符 在 R-2 巨型机中带标志符的数据表示方式 • R-2 巨型机中的标志符 功能位：操作数、指令、地址、控制字 陷井位：由软件定义四种捕捉方式 封写位：指定数据是只读的还是可读可写 类型位：对于操作数：二进制、十进制、定点数、浮点数、复数、 字符串、单精度、双精度等 对于地址：绝对地址、相对地址、变址地址、未连接的地址等 • 标志符由编译器或其它系统软件建立，对程序员透明 • 程序（包括指令和数据）的总存储量分析 数据存储量增加，指令存储量减少 例 2.6：假设 X 处理机的数据不带标志符，其指令字长和数据字长均为 32
位。Y处理机的数据带有标志符,每个数据的字长增加至35位,其中有3位是 标志符,其指令字长由32位减少至30位。并假设一条指令平均访问两个操作数 每个操作数平均被访问R次。现有一个程序,它的指令条数为I,分别计算在这 两种不同类型的处理机中程序所占用的存储空间。 2×32 解:X处理机程序占用的存储空间总和为:Bx=321+R Y处理机程序占用的存储空间总和为:B=301+2×351, Y处理机与Ⅹ处理机的程序占用存储空间的比值 2×35I B 30I 15R+35 Bx 32/42×3216R+32 R 当R>3时,有10, 即带标志符的处理机所占用的存储空间通常要小。 采用标志符数据表示方法的主要优点 采用标志符的 1、简化了指令系统。 一指令字 2、由硬件自动实现一致性检查和数据类 型的转换。 例如:在IBM370系列机中执行A=A+B 运算,若A、B都是十进制数,只需要一条指 令,共6个字节,在IBM370/145机上的执 指令字长缩短 指令 行时间是13微秒,若A与B中有一个是定点 进制数,由于要进行数据类型的一致性检 查和转换,在PL/I语言中的编译结果为13 条指令,共64个字节,在IBM370/145机上 的执行时间是408微秒,两者相比,存储空数据字长 间节省5倍,运算速度快30多倍。 加长 数据 3、简化程序设计,缩小了人与机器之间 的语义差距。 ↓标花长度香委厢蛟森 简化编译器,使高级语言与机器语言 之间的语义差距大大缩短。 采用标志符的数据长度 5、支持数据库系统,一个软件不加修改 就可适用于多种数据类型。 带标志符和不带标志符两种情 6、方便软件调试,在每个数据中都有陷况下程序所占存储空间比较 井位。 采用标志符数据表示方法的主要缺点: 1、数据和指令的长度可能不一致 2、指令的执行速度降低(程序的设计时间、编译时间和调试时间缩短) 3、硬件复杂度增加。 2、数据描述符表示法 ·数据描述符与标志符的区别: 标志符只作用于一个数据,而数据描述符要作用于一组数据。 2-2
2－2 位。Y 处理机的数据带有标志符，每个数据的字长增加至 35 位，其中有 3 位是 标志符，其指令字长由 32 位减少至 30 位。并假设一条指令平均访问两个操作数， 每个操作数平均被访问 R 次。现有一个程序，它的指令条数为 I，分别计算在这 两种不同类型的处理机中程序所占用的存储空间。 解：X 处理机程序占用的存储空间总和为： B I I R X = + 32 2 32 ， Y 处理机程序占用的存储空间总和为： B I I R Y = + 30 2 35 ， Y 处理机与 X 处理机的程序占用存储空间的比值： B B I I R I I R R R Y X = + + = + + 30 2 35 32 2 32 15 35 16 32 当 R＞3 时，有 B B Y X ＜1 ，在实际应用中经常是 R＞10， 即带标志符的处理机所占用的存储空间通常要小。 采用标志符数据表示方法的主要优点： 1、简化了指令系统。 2、由硬件自动实现一致性检查和数据类 型的转换。 例如：在 IBM 370 系列机中执行 A＝A＋B 运算，若 A、B 都是十进制数，只需要一条指 令，共 6 个字节，在 IBM 370/145 机上的执 行时间是 13 微秒，若 A 与 B 中有一个是定点 二进制数，由于要进行数据类型的一致性检 查和转换，在 PL/I 语言中的编译结果为 13 条指令，共 64 个字节，在 IBM 370/145 机上 的执行时间是 408 微秒，两者相比，存储空 间节省 5 倍，运算速度快 30 多倍。 3、简化程序设计，缩小了人与机器之间 的语义差距。 4、简化编译器，使高级语言与机器语言 之间的语义差距大大缩短。 5、支持数据库系统，一个软件不加修改 就可适用于多种数据类型。 6、方便软件调试，在每个数据中都有陷 井位。 采用标志符数据表示方法的主要缺点： 1、数据和指令的长度可能不一致。 2、指令的执行速度降低（程序的设计时间、编译时间和调试时间缩短） 3、硬件复杂度增加。 2、数据描述符表示法 • 数据描述符与标志符的区别： 标志符只作用于一个数据，而数据描述符要作用于一组数据。 采用标志符的数据长度 带标志符和不带标志符两种情 况下程序所占存储空间比较 指令 数据字长 加长 指 令 字 长 缩 短 数据 采用标志符的 指令字长 标志符长度 不采用标志符的 指令和数据字长
Burroughs公司生产的B-6700机中采用的数据描述符表示方法。 最高三位为101时表示数据描述符, 最高三位为000时表示数据 101 标志位 数据描述符 000 数 值 数据 例如:用数据描述符表示方法表示一个3×4矩阵A。 C112C13a14 A =a1a2a2a24 101标志3 3a2a33y4 101标志 101标志 2.2寻址技术 Ocx|y[o标志4 寻址技术研究的主要内容: 编址方式、寻址方式和定位方式 ·寻址技术研究的主要对象 000 12 寄存器、主存储器、堆栈和输入 输出设备 000 ·方法:分析各种寻址技术的 优缺点,如何选择和确定寻址技 术 2.2.1编址方式 000 2.2.2寻址方式 000 2.2.3定位方式 2.2.1编址方式 定义:编址方式是指对各种 000 存储设备进行编码的方法 主要内容:编址单位、零地 址空间个数、并行存储器的编址 技术、输入输出设备的编址技术 1、编址单位 用数据描述符表示方法表示一个3×4矩阵 常用的编址单位:字编址、字节编址、位编址、块编址等 编址单位与访问字长
2－3 • Burroughs 公司生产的 B-6700 机中采用的数据描述符表示方法。 最高三位为 101 时表示数据描述符， 最高三位为 000 时表示数据。 101 标志位 长 度 地 址 数据描述符 000 数 值 数据 例如：用数据描述符表示方法表示一个 3×4 矩阵 A。 A a a a a a a a a a a a a = 11 12 13 14 21 22 23 24 31 32 33 34 2.2 寻址技术 • 寻址技术研究的主要内容： 编址方式、寻址方式和定位方式 • 寻址技术研究的主要对象： 寄存器、主存储器、堆栈和输入 输出设备 • 方法：分析各种寻址技术的 优缺点，如何选择和确定寻址技 术 2.2.1 编址方式 2.2.2 寻址方式 2.2.3 定位方式 2.2.1 编址方式 • 定义：编址方式是指对各种 存储设备进行编码的方法。 • 主要内容：编址单位、零地 址空间个数、并行存储器的编址 技术、输入输出设备的编址技术 1、编址单位 • 常用的编址单位：字编址、字节编址、位编址、块编址等 • 编址单位与访问字长 用数据描述符表示方法表示一个 3×4 矩阵 …… 101 标志 位 3 101 标志 位 4 101 标志 位 4 101 标志 位 4 000 a11 000 a12 000 a13 000 a14 …… 000 a21 000 a22 000 a23 000 a24 …… 000 a31 000 a32 000 a33 000 a34 …… OPC X Y
一般:字节编址,字访问 部分机器:位编址,字访问 辅助存储器:块编址,位访问 ·字节编址字访问的优缺点 有利于信息处理 地址信息浪费 存储器空间浪费 读写逻辑稍复杂 0字节位置引起的问题 2、零地址空间个数 需要编址的设备主要有通用寄存器、主存储器和输入输出设备。 个零地址空间:通用寄存器、主存储器和输入输出设备均独立编址 两个零地址空间:主存储器与输入输出设备统一编址 个零地址空间:所有存储设备统一编址 最低端是通用寄存器,最高端是输入输出设备,中间为主存储器 ·隐含编址方式,实际上没有零地址空间 堆栈、 Cache等 3、输入输出设备的编址 台设备一个地址 台设备两个地址:数据寄存器、状态或控制寄存器 多个需要编址的寄存器共用同一个地址的方法: 依靠地址内部来区分,适用于被编址的接口寄存器的长度比较短 下跟法”隐含编址方式,必须按顺序读写寄存器 一台设备多个地址 4并行存储器的编址技术 高位交叉编址,主要目的是用来扩大存储器容量。 ·低位交叉编址,主要目的是提高存储器速度。 2.2.2寻址方式 定义:寻找操作数及数据存放单元的方法称为寻址方式 主要内容:设计思想和设计方法 1、寻址方式的设计思想 ·立即数寻址方式,用于数据比较短、源操作数 ·面向寄存器的寻址方式 R pCR. R OPCR. R. R OPC R, M 面向主存储器的寻址方式: M OPC M. M OPC M. M. M
2－4 一般：字节编址，字访问 部分机器：位编址，字访问 辅助存储器：块编址，位访问 • 字节编址字访问的优缺点 有利于信息处理 地址信息浪费 存储器空间浪费 读写逻辑稍复杂 0 字节位置引起的问题 2、零地址空间个数 需要编址的设备主要有通用寄存器、主存储器和输入输出设备。 • 三个零地址空间：通用寄存器、主存储器和输入输出设备均独立编址 • 两个零地址空间：主存储器与输入输出设备统一编址 • 一个零地址空间：所有存储设备统一编址 最低端是通用寄存器，最高端是输入输出设备，中间为主存储器 • 隐含编址方式，实际上没有零地址空间 堆栈、Cache 等 3、输入输出设备的编址 • 一台设备一个地址 • 一台设备两个地址：数据寄存器、状态或控制寄存器 多个需要编址的寄存器共用同一个地址的方法： 依靠地址内部来区分，适用于被编址的接口寄存器的长度比较短 “下跟法”隐含编址方式，必须按顺序读写寄存器。 • 一台设备多个地址。 4 并行存储器的编址技术 • 高位交叉编址，主要目的是用来扩大存储器容量。 • 低位交叉编址，主要目的是提高存储器速度。 2.2.2 寻址方式 • 定义：寻找操作数及数据存放单元的方法称为寻址方式。 • 主要内容：设计思想和设计方法 1、寻址方式的设计思想 • 立即数寻址方式，用于数据比较短、源操作数 • 面向寄存器的寻址方式 OPC R OPC R, R OPC R, R, R OPC R, M • 面向主存储器的寻址方式： OPC M OPC M, M OPC M, M, M
·面向堆栈的寻址方式: OPC 2、间接寻址方式与变址寻址方式的比较 ●目标相同:都是为了解决操作数地址的修改问题 都能做到不改变程序而修改操作数地址。 原则上,仅需设置间址寻址方式与变址寻址方式中的任何一种即可。 ●如何选取间址寻址方式与变址寻址方式? 例2.7:一个由N个元素组成的数组,已经存放在起始地址为AS的主存连 续单元中,现要把它搬到起始地址为AD的主存连续单元中。不必考虑可能出现 的存储单元的重叠问题。为了编程简单,采用一般的两地址指令编写程序 解:用间接寻址方式编写程序如下: ASR,ASI;保存源数组的起始地址 MOVE ADR 保存目标数组的起始地址 MOVE NUM,CNT;保存数据的个数 LOOP:MOVE@ASI,@ADI;用间址寻址方式传送数据 源数组的地址增量 INC ;目标数组的地址增量 个数减 BGT LOC ;测试N个数据是否传送完 HALT 停机 ASR 源数组的起始地址 目标数组的起始地址 ;需要传送的数据个数 ASI 当前正在传送的源数组地址 当前正在传送的源数组地址 剩余数据的个数 用变址寻址方式编写程序如下 START 把源数组的起始地址送入变址寄存器 MOVE NUM, CNT 保存数据个数,为了程序具有再入性 LOOP:MOVE(X),AD-AS(X);AD-AS为地址偏移量,在汇编时计算 INC 增量变址寄存器 DEC CNT 个数减1 BGT LOOP ;测试N个数据是否传送完成 HALT ;停机 NUM 需要传送的数据个数 CNT 剩余数据的个数 主要优缺点比较: 采用变址寻址方式编写的程序简单、易读 对于程序员,两种寻址方式的主要差别是 间址寻址方式:间接地址在主存储器中,没有偏移量 变址寻址方式:基地址在变址寄存器中,带有偏移量 实现的难易程度:间址寻址方式容易
2－5 • 面向堆栈的寻址方式： OPC OPC M 2、间接寻址方式与变址寻址方式的比较 • 目标相同：都是为了解决操作数地址的修改问题 都能做到不改变程序而修改操作数地址。 原则上，仅需设置间址寻址方式与变址寻址方式中的任何一种即可。 • 如何选取间址寻址方式与变址寻址方式？ 例 2．7：一个由 N 个元素组成的数组，已经存放在起始地址为 AS 的主存连 续单元中，现要把它搬到起始地址为 AD 的主存连续单元中。不必考虑可能出现 的存储单元的重叠问题。为了编程简单，采用一般的两地址指令编写程序。 解：用间接寻址方式编写程序如下： START: MOVE ASR, ASI ；保存源数组的起始地址 MOVE ADR, ADI ；保存目标数组的起始地址 MOVE NUM, CNT ；保存数据的个数 LOOP: MOVE @ASI, @ADI ；用间址寻址方式传送数据 INC ASI ；源数组的地址增量 INC ADI ；目标数组的地址增量 DEC CNT ；个数减 1 BGT LOOP ；测试 N 个数据是否传送完 HALT ；停机 ASR: AS ；源数组的起始地址 ADR: AD ；目标数组的起始地址 NUM: N ；需要传送的数据个数 ASI: 0 ；当前正在传送的源数组地址 ADI: 0 ；当前正在传送的源数组地址 CNT: 0 ；剩余数据的个数 用变址寻址方式编写程序如下： START: MOVE AS, X ；把源数组的起始地址送入变址寄存器 MOVE NUM, CNT ；保存数据个数，为了程序具有再入性 LOOP: MOVE (X), AD-AS(X)；AD-AS 为地址偏移量，在汇编时计算 INC X ；增量变址寄存器 DEC CNT ；个数减 1 BGT LOOP ；测试 N 个数据是否传送完成 HALT ；停机 NUM: N ；需要传送的数据个数 CNT: 0 ；剩余数据的个数 • 主要优缺点比较： 采用变址寻址方式编写的程序简单、易读。 对于程序员，两种寻址方式的主要差别是： 间址寻址方式：间接地址在主存储器中，没有偏移量 变址寻址方式：基地址在变址寄存器中，带有偏移量 实现的难易程度：间址寻址方式容易
指令的执行速度:间址寻址方式慢 对数组运算的支持:变址寻址方式比较好 自动变址:在访问间接地址过程中,地址自动增减 ●变址与间址混合时,有前变址与后变址两种方式 前变址寻址方式:EA=((X)+A) 后变址寻址方式:EA=(X)+(A) 3、寄存器寻址 主要优点: 指令字长短 指令执行速度快 支持向量、矩阵运算 主要缺点 不利于优化编译 现场切换困难 硬件复杂 4、堆站寻址方式 ●主要优点 支持高级语言,有利与编译程序 节省存储空间 支持程序的嵌套和递归调用,支持中断处理 主要缺点 运算速度比较低 栈顶部分设计成一个高速的寄存器堆 2.2.3定位方式 内容:程序的主存物理地址在什么时间确定?采用什么方式来实现? 程序需要定位的主要原因: 程序的独立性 程序的模块化设计 数据结构在程序运行过程中,其大小往往是变化的 有些程序本身很大,大于分配给它的主存物理空间 直接定位方式:在程序装入主存储器之前,程序中的指令和数据的主存物理 就已经确定了的称为直接定位方式。 静态定位:在程序装入主存储器的过程中随即进行地址变换,确定指令和数 据的主存物理地址的称为静态定位方式 动态定位:在程序执行过程中,当访问到相应的指令或数据时才进行地址变 换,确定指令和数据的主存物理地址的称为动态定位方式。 2.3指令格式的优化设计 主要目标 节省程序的存储空间 2-6
2－6 指令的执行速度：间址寻址方式慢 对数组运算的支持：变址寻址方式比较好 • 自动变址：在访问间接地址过程中，地址自动增减 • 变址与间址混合时，有前变址与后变址两种方式 前变址寻址方式：EA＝((X)＋A) 后变址寻址方式：EA＝(X)＋(A) 3、寄存器寻址 • 主要优点： 指令字长短 指令执行速度快 支持向量、矩阵运算 • 主要缺点： 不利于优化编译 现场切换困难 硬件复杂 4、堆站寻址方式 • 主要优点： 支持高级语言，有利与编译程序 节省存储空间 支持程序的嵌套和递归调用，支持中断处理 • 主要缺点： 运算速度比较低 栈顶部分设计成一个高速的寄存器堆 2.2.3 定位方式 • 内容：程序的主存物理地址在什么时间确定？采用什么方式来实现？ • 程序需要定位的主要原因： 程序的独立性 程序的模块化设计 数据结构在程序运行过程中，其大小往往是变化的 有些程序本身很大，大于分配给它的主存物理空间 • 直接定位方式：在程序装入主存储器之前，程序中的指令和数据的主存物理 就已经确定了的称为直接定位方式。 • 静态定位：在程序装入主存储器的过程中随即进行地址变换，确定指令和数 据的主存物理地址的称为静态定位方式。 • 动态定位：在程序执行过程中，当访问到相应的指令或数据时才进行地址变 换，确定指令和数据的主存物理地址的称为动态定位方式。 2.3 指令格式的优化设计 • 主要目标： 节省程序的存储空间
指令格式尽量规整 研究内容: 操作码优化表示 地址码优化表示 2.3.1指令的组成 2.3.2操作码的优化设计 2.3.3地址码的优化设计 2.3.4指令格式设计举例 2.3.1指令的组成 般的指令主要由两部分组成: 操作码(OPC) 址码(A) 操作码通常包括两部分内容: 操作种类:加、减、乘、除、数据传送、移位、转移、输入输出 操作数描述 数据的类型:定点数、浮点数、复数、字符、字符串、逻辑数、向量 进位制:2进制、10进制、16进制 数据字长:字、半字、双字、字节 地址码通常包括三部分内容 地址:还包括间接地址、立即数、寄存器编、变址寄存器 地址的附加信息:偏移量、块长度、跳距 寻址方式:直接寻址、间接寻址、立即数寻址、变址寻址、相对寻址、 寄存器寻址 2.3.2操作码的优化表示 ·操作码的三种编码方法:固定长度, Huffman编码、扩展编码 改进操作码编码方式节省程序存储空间( Burroughs公司的B-1700机) 操作码编码方式 整个操作系统所用 改进的百分比 指令的操作码总位数 8位定长编码 301,248 4-6-10扩展编码 184,966 39% Huffman编码 172,346 43% 1、固定长操作码 主要优点:规整,译码简单 ·主要缺点:浪费信息量(操作码的总长位数增加) 2、 Huffman编码法 1992年由 Huffman首先提出的一种编码方法
2－7 指令格式尽量规整 • 研究内容： 操作码优化表示 地址码优化表示 2．3．1 指令的组成 2．3．2 操作码的优化设计 2．3．3 地址码的优化设计 2．3．4 指令格式设计举例 2.3.1 指令的组成 • 一般的指令主要由两部分组成： 操作码（OPC） 地址码（A） • 操作码通常包括两部分内容： 操作种类：加、减、乘、除、数据传送、移位、转移、输入输出 操作数描述 数据的类型：定点数、浮点数、复数、字符、字符串、逻辑数、向量 进位制：2 进制、10 进制、16 进制 数据字长：字、半字、双字、字节 • 地址码通常包括三部分内容： 地址：还包括间接地址、立即数、寄存器编、变址寄存器 地址的附加信息：偏移量、块长度、跳距 寻址方式：直接寻址、间接寻址、立即数寻址、变址寻址、相对寻址、 寄存器寻址 2.3.2 操作码的优化表示 • 操作码的三种编码方法：固定长度，Huffman 编码、扩展编码 • 改进操作码编码方式节省程序存储空间(Burroughs 公司的 B-1700 机) 操作码编码方式 整个操作系统所用 指令的操作码总位数 改进的百分比 8 位定长编码 301,248 0 4-6-10 扩展编码 184,966 39％ Huffman 编码 172,346 43％ 1、固定长操作码 • 主要优点：规整，译码简单 • 主要缺点：浪费信息量（操作码的总长位数增加） 2、Huffman 编码法 1992 年由 Huffman 首先提出的一种编码方法
操作码的最短平均长度可以通过如下公式计算 H-∑plog2 其中:Pi表示第i种操作码在程序中出现的概率 固定长操作码相对于 Huffman操作码的信息冗余量为 pilog. pi R=1 例2.7:假设一台模型计算机共有7种不同的操作码,如果采用固定长操作 码需要3位。已知各种操作码在程序中出现的概率如下表,计算采用μ huffman编 码法的操作码平均长度,并计算固定长操作码和 Huffman操作码的信息冗余量。 指令序号1 I4 I5 出现的概率0.450.300.150.050.03 解:利用 Huffman树进行操作码编码的方法,又称为最小概率合并法 1、把所有指令按照操作码在程序中出现的概率,自左向右从排列好 、选取两个概率最小的结点合并成一个概率值是二者之和的新结点,并把 这个新结点插入到其它还没有合并的结点中间形成一个新结点集合。 3、在新的结点集合中选取两个概率最小的结点进行合并,如此继续进行下 去,直至全部结点都合并完毕 4、最后得到一个根结点,根结点的概率值为1。 5、每个结点都有两个分支,分别用一位代码“0”和“1”表示。 6、从根结点开始,沿尖头所指方向,到达属于该指令的概率结点,把沿线 所经过的代码组合起来得到这条指令的操作码编码 形成的操作码编码并不是唯一的,但操作码的平均长度是唯一的。 0.05
2－8 • 操作码的最短平均长度可以通过如下公式计算： H pi p i n = − i = 2 1 log 其中：Pi 表示第 i 种操作码在程序中出现的概率 • 固定长操作码相对于 Huffman 操作码的信息冗余量为： R p p n i i i n = − − = 1 2 1 2 log log 例 2.7：假设一台模型计算机共有 7 种不同的操作码，如果采用固定长操作 码需要 3 位。已知各种操作码在程序中出现的概率如下表，计算采用 Huffman 编 码法的操作码平均长度，并计算固定长操作码和 Huffman 操作码的信息冗余量。 指令序号 I1 I2 I3 I4 I5 I6 I7 出现的概率 0.45 0.30 0.15 0.05 0.03 0.01 0.01 解：利用 Huffman 树进行操作码编码的方法，又称为最小概率合并法。 1、把所有指令按照操作码在程序中出现的概率，自左向右从排列好。 2、选取两个概率最小的结点合并成一个概率值是二者之和的新结点，并把 这个新结点插入到其它还没有合并的结点中间形成一个新结点集合。 3、在新的结点集合中选取两个概率最小的结点进行合并，如此继续进行下 去，直至全部结点都合并完毕。 4、最后得到一个根结点，根结点的概率值为 1。 5、每个结点都有两个分支，分别用一位代码“0”和“1”表示。 6、从根结点开始，沿尖头所指方向，到达属于该指令的概率结点，把沿线 所经过的代码组合起来得到这条指令的操作码编码。 形成的操作码编码并不是唯一的，但操作码的平均长度是唯一的。 0 1 0 1 0 1 0 1 0 1 0 1 0.45 0.30 0.15 0.05 0.03 0.01 0.01 0.02 0.05 0.10 0.25 0.55 1.00
模型机的操作码 Huffman编码法 」指令序号出现的概率 Huffman编码法操作码长度 0.45 1位 1234567 0.30 2位 0.15 110 3位 0.05 1110 4位 0.03 11110 5位 0.01 111110 6位 0.01 1111111 6位 采用 Huffman编码法所得到的操作码的平均长度为: H=∑p:h=0.45×1+0.30×2+0.15×3+0.05×4 +0.03×5+0.01×6+0.01×6=1.97(位) 采用最优 Huffman编码法,操作码的平均长度为: H=∑p1g,pi=0.45×1.152+0.30×1.737+0.15×2.737 0.05×4.322+0.03×5.059+0.01×6.644+0.01×6.644 =1.95 采用3位固定长操作码的信息冗余量为:R= >):1-197 H 3359 Huffman编码法的信息冗余量仅为:R=1 197 与采用3位固定长操作码的信息冗余量35%相比要小得多。 3、扩展编码法 Huffman操作码的主要缺点: 操作码长度很不规整,硬件译码困难 与地址码共同组成固定长的指令比较困难 扩展编码法:由固定长操作码与 Huffman编码法相结合形成 7条指令的操作码扩展编码法 指令序号出现的概率1-2-3-5扩展编码|2-4等长扩展编码 0.45 III 0.30 10 01 0.15 110 10 0.05 11100 1100 4巧67 0.03 11101 1101 0.01 11110 1110 0.01 11111 1111 「平均长度 信息冗余量 2.5% 11.4% 2-9
2－9 模型机的操作码 Huffman 编码法 指令序号 出现的概率 Huffman 编码法 操作码长度 I1 0.45 0 1 位 I2 0.30 1 0 2 位 I3 0.15 1 1 0 3 位 I4 0.05 1 1 1 0 4 位 I5 0.03 1 1 1 1 0 5 位 I6 0.01 1 1 1 1 1 0 6 位 I7 0.01 1 1 1 1 1 1 1 6 位 采用 Huffman 编码法所得到的操作码的平均长度为： H pi li i = = 1 7 ＝0.45×1＋0.30×2＋0.15×3＋0.05×4 ＋0.03×5＋0.01×6＋0.01×6＝1.97（位） 采用最优 Huffman 编码法，操作码的平均长度为： H pi pi i = − = 2 1 7 log ＝0.45×1.152＋0.30×1.737＋0.15×2.737 ＋0.05×4.322＋0.03×5.059＋0.01×6.644＋0.01×6.644 ＝1.95 采用 3 位固定长操作码的信息冗余量为： R H = 1− = − 7 1 197 3 35% 2 log . Huffman 编码法的信息冗余量仅为： R = 1− 195 197 10% . . . 与采用 3 位固定长操作码的信息冗余量 35％相比要小得多。 3、扩展编码法 • Huffman 操作码的主要缺点： 操作码长度很不规整，硬件译码困难 与地址码共同组成固定长的指令比较困难 • 扩展编码法：由固定长操作码与 Huffman 编码法相结合形成 7 条指令的操作码扩展编码法 指令序号 出现的概率 1-2-3-5 扩展编码 2-4 等长扩展编码 I1 0.45 0 0 0 I2 0.30 1 0 0 1 I3 0.15 1 1 0 1 0 I4 0.05 1 1 1 0 0 1 1 0 0 I5 0.03 1 1 1 0 1 1 1 0 1 I6 0.01 1 1 1 1 0 1 1 1 0 I7 0.01 1 1 1 1 1 1 1 1 1 平均长度 2.0 2.2 信息冗余量 2.5％ 11.4％
例如:例27改为1-2-3-5扩展编码法,其操作码平均长度为 H=0.45×1+0.30×2+0.15×3+(0.05+0.03+0.01+0.01)×5 信息冗余量为:R=1 195 =25% 2.00 又例如:例27改为2-4等长扩展编码法,其操作码平均长度为: H=(0.45+0.30+0.15)×2+(0.05+0.03+0.01+0.01)×4 2.20 信息冗余量为:R=1 195 =114% 操作码等长扩展编码法 匚操作码编码 说明 操作码编码 0000 0000 0001 4位长度的 0001 4位长度的 操作码共15种 操作码共8种 1110 0111 11110000 10000000 l1110001 8位长度的 10000001 8位长度的 操作码共15种 操作码共64种 11111110 l1110111 ll1111110000 100010000000 1111101012位长度的 10001000001012位长度的操 操作码共16种 作码共512种 l11111111110 l11111110111 等长15/15/15……扩展法 等长8/64/512……扩展法 不等长操作码扩展编码法(4-6-10扩展编码法) 编码方法 各种不同长度操作码的指令 4位操作码6位操作码10位操作鸡/指令种类 15/3/16 15 16 34 8/31/16 31 16 8/30/32 8884 30 8/16/256 256 280 4/32/256 32 256 292 2.3.3地址码的优化表示 1、地址码个数的选择 地址码个数通常有三个、两个、一个及0个等四种情况 评价地址码个数应该取多少的标准主要有两个 是程序的存储容量,包括操作码和地址码 2-10
2－10 例如：例改为 1-2-3-5 扩展编码法，其操作码平均长度为： H＝0.45×1＋0.30×2＋0.15×3＋(0.05＋0.03＋0.01＋0.01)×5 ＝2.00 信息冗余量为： R = 1− = 195 2 00 2 5% . . . 又例如：例改为 2-4 等长扩展编码法，其操作码平均长度为： H＝（0.45＋0.30＋0.15）×2＋（0.05＋0.03＋0.01＋0.01）×4 ＝2.20 信息冗余量为： R = 1− = 195 2 20 114% . . . • 操作码等长扩展编码法 操作码编码 说 明 操作码编码 说 明 0000 0001 …… 1110 4 位长度的 操作码共 15 种 0000 0001 …… 0111 4 位长度的 操作码共 8 种 1111 0000 1111 0001 …… 1111 1110 8 位长度的 操作码共 15 种 1000 0000 1000 0001 …… 1111 0111 8 位长度的 操作码共 64 种 1111 1111 0000 1111 1111 0001 …… 1111 1111 1110 12 位长度的 操作码共 16 种 1000 1000 0000 1000 1000 0001 …… 1111 1111 0111 12 位长度的操 作码共 512 种 等长 15/15/15……扩展法 等长 8/64/512……扩展法 不等长操作码扩展编码法（4-6-10 扩展编码法） 编码方法 各种不同长度操作码的指令 指令种类 4 位操作码 6 位操作码 10 位操作码 15/3/16 15 3 16 34 8/31/16 8 31 16 55 8/30/32 8 30 32 70 8/16/256 8 16 256 280 4/32/256 4 32 256 292 2.3.3 地址码的优化表示 1、地址码个数的选择 • 地址码个数通常有三个、两个、一个及０个等四种情况 • 评价地址码个数应该取多少的标准主要有两个： 一是程序的存储容量，包括操作码和地址码