《2021年整理第二章习题.pptx》由会员分享，可在线阅读，更多相关《2021年整理第二章习题.pptx（6页珍藏版）》请在金锄头文库上搜索。
1、第二章习题,2.26 一个处理机有 I1I10 共 10 条指令，经统计，各指令在程序中出现的概率如下： I1：0.25I2：0.20I3：0.15I4：0.10I5：0.08 I6：0.08I7：0.05I8：0.04I9：0.03I10：0.02 计算这 10 条指令的操作码最短平均长度。 写出这 10 条指令的 Huffman 编码，并计算操作码编码的平均长度一信息冗余量。 采用 3/7 扩展编码法和 2/8 扩展编码法编写这 10 条指令的操作码。并分别计算编码的平均长 度和信息冗余量。说明哪一种扩展编码较好的理由。,n,解：（1）操作码编码的最短平均长度为：H=- pi log2pi
2、 i1,H=(0.25log20.250.20log20.200.15log20.150.10log20.100.08log20.08 0.08log20.080.05log20.050.04log20.040.03log20.030.02log20.02) =2.96（位） （2）根据给出的使用频度，在构造 Huffman 树的过程中，有两个结点可供合并，因此可生成不同的 Huffman 树，其中给出一棵如图所示，相应的 Huffman 编码如表所示。,10 1010 I2I1 1010 10I410I3 10I610I5,I10I9I8I7,1.00,0.02,0.05,0.13,0.23
3、,0.43,0.03,0.08,0.10,0.20,0.04,0.09,0.17,0.32,0.57,0.05,0.08,0.15,0.25,1,2,n,Huffman 编码的平均长度为：l= pi li i1,l=0.2520.2020.1530.1030.0840.0840.055 0.0450.0350.025=2.99（位） Huffman 编码的信息冗余量为：R=1-H/l =（12.96/2.99）100%=1.0% （3）3/7 扩展编码和 2/8 扩展编码如表所示。 3/7 扩展编码要求短码码点数为 3，长码码点数为 7。所以短码长取 2 位，有码点 22=4 个，用一个作 扩
4、展标志；长码长取 3 位，有码点 23=8 个，有一个未被利用，即有一个余码点。编码的平均长度为： l=(0.250.200.15)2(0.100.080.080.050.040.030.02)5=3.2（位） 3/7 扩展编码的信息冗余量为：R=1H/l =（12.96/3.2）100%=7.5% 2/8 扩展编码要求短码码点数为 2，长码码点数为 8。所以短码长取 2 位，有码点 22=4 个，用二个作 扩展标志；长码长取 2 位，有码点 222=8 个，码点全部被利用，即没有多余码点。 l=(0.250.20)2(0.150.100.080.080.050.040.030.02)4=3.
5、1（位） 2/8 扩展编码的信息冗余量为：R=1H/l =（12.96/3.1）100%=4.5% 可见，3/7 扩展编码优于 2/8 扩展编码。 2.28 用于文字处理的某专用机，每个文字符用 4 位十进制数字（09）编码表示，空格用表示。在 对传送的文字符和空格进行统计后，得出它们的使用频度如下： ：0.200:0.171:0.062:0.083:0.114:0.08 5:0.056:0.087:0.138:0.039:0.01 若对数字 09 和空格采用二进制编码，试设计编码平均长度最短的编码。 若传送 106 个文字符号，且每个文字符号后均自动跟一个空格，按最短的编码，共需传送多少 个
6、二进制位？若传送波特率为 9600bPS，共需传送多少时间？ 若对数字 09 和空格采用 4 位定长码编码，重新计算问题（2）。,n,解：（1）操作码编码的平均长度最短为 Huffman 编码：l= pi li。生成的 Huffman 树，如图所 i1,示，相应的 Huffman 编码如表所示。 l=3.23（位） 根据题意，每个字符的二进制码的平均长度为：3.23（41）=16.15（位）。若要传输 106 个 字符，则要传输二进制位数为：10616.15=1.615107（位） 若波特率为 56Kb/s，则传输时间为：1.615107/（56103）=288（s）。 当采用四位定长编码时，
7、则需要传输二进制位数为：1064（41）=2107（位），传输时间为： 2107/（56103）=357（s）。,10 1010 101010 370 51642 98,2.30 一台模型机共有 7 条指令，各指令的使用频度分别为：35，25，20，10，5，3，2， 有 8 个通用数据寄存器，2 个变址寄存器。 要求操作码的平均长度最短，请设计操作码的编码，并计算操作码编码的平均长度。 设计 8 位字长的寄存器寄存器型指令 3 条，16 位字长的寄存器一存储器型变址寻址方式指 令 4 条，变址范围不小于正、负 127。请设计指令格式，并给出指令各字段的长度和操作码的编码。,n,解：（1）操作
8、码编码的平均长度最短为 Huffman 编码：l= pi li。生成的 Huffman 树如图所示， i1,相应的 Huffman 编码如表所示。l=2.35（位）,1.00,0.01,0.04,0.09,0.20,0.40,0.03,0.05,0.11,0.20,0.08,0.06,0.14,0.27,0.60,0.16,0.08,0.13,0.33,0.17,0.08,3,（2）由于通用寄存器有 8 个，则指令中通用寄存器字段应为 3 位；操作码字段 2 位可有 4 个码点， 用三个码点表示三条指令，另一个码点则作为扩展标志。所以 3 条 8 位长的寄存器寄存器型指令格式 如下： 由于变址
9、寄存器有 2 个，则指令中变址寄存器字段应为 1 位；变址范围-127+127，则指令中相对位 移字段应为 8 位；操作码字段前 2 位可有 4 个码点，用三个码点表示三条指令，另一个码点则作为扩展标 志。扩展 2 位正好可表示四条指令，操作码字段则为 4 位。所以 4 条 16 位长的寄存器存储器型指令 格式如下： 特别地，当采用 3/4 扩展编码时，使用频度高的用短码表示，使用频度低的用长码表示，其相应的编 码如表所示。 2.31 某处理机的指令字长为 16 位，有二地址指令、一地址指令和零地址指令 3 类，每个地址字段的 长度均为 6 位。 如果二地址指令有 15 条，一地址指令和零地址
10、指令的条数基本相等。问一地址指令和零地址指 令各有多少条？并为这 3 类指令分配操作码。 如果指令系统要求这 3 类指令条数的比例大致为 1：9：9，问这 3 类指令各有多少条？并为这 3 类指令分配操作码。 解：（1）操作码字段取 4 位可有 24=16 个码点，用 15 个码点（00001110）表示 15 条二地址指令，,1.00,0.02,0.05,0.10,0.20,0.40,0.03,0.05,0.10,0.20,0.25,0.60,0.35,4,另一个码点（1111）则作为扩展标志。所以 15 条二地址指令格式如下： 由于要求一地址指令和零地址指令的条数基本相等。所以地址码 1
11、字段 6 位扩展有 26=64 个码点，用 63 个码点（11110000001111111110）表示 63 条一地址指令，另一个码点（1111111111）则作为扩展标 志。而用地址码 2 字段 6 位扩展有 26=64 个码点，64 个码点都用来表示零地址指令，共有 64 条。 （2）在一中指令条数的比例大约 1：4.2：4.2，因此若使一地址指令和零地址指令加大一倍，则三类 指令条数的比例大约 1：9：9。 操作码字段取 4 位时的 16 个码点，用 14 个码点（00001101）表示 14 条二地址指令，另二个码点 （1110 与 1111）则作为扩展标志。 扩展标志（1110）扩
12、展地址码 1 字段 6 位的 64 个码点（11100000001110111111）全部用来表示一 地址指令，有 64 条。扩展标志（1111）扩展地址码 1 字段 6 位的 64 个码点，用 62 个码点（1111000000 1111111101）表示 62 条一地址指令，另二个码点（1111111110 与 1111111111）则作为扩展标志。这样一 地址指令，共有 126 条。 扩展标志（1111111110 与 1111111111）扩展地址码 2 字段 6 位，各有 64 个码点全部用来表示零地址 指令，则有 128 条零地址指令。 2.32 某模型机 9 条指令使用频度为：
13、ADD（加）30 SUB（减）24JOM（按负转移）6STO（存）7 JMP（转移）7SHR（右移）2CIL（循环左移）3CLA（清除）20 STP（停机）1 要求有两种指令字长，都按双操作数指令格式编排，采用扩展操作码，并限制只能有两种操作码码长。设 该机有若干通用寄存器，主存为 16 位宽，按字节编址，采用按整数边界存储，任何指令都在一个主存周 期中取得，短指令为寄存器-寄存器型，长指令为寄存器-主存型，主存地址应能变址寻址。 仅根据使用频度，不考虑其它要求，设计出全 Huffman 操作码，计算其平均码长； 考虑题目全部要求，设计优化实用的操作码形式，并计算其操作码的平均码长； 该机允许
14、使用多少可编址的通用寄存器？ 画出该机两种指令字格式，标出各字段之位数； 指出访存操作数地址寻址的最大相对位移量为多少个字节？ 解：（1）根据给出的使用频度，在构造 Huffman 树的过程中，有两个结点可供合并，因此可生成不同 的 Huffman 树，其中给出一棵如图所示，相应的 Huffman 编码如表所示。,5,n,Huffman 编码的平均长度为：l= pi li i1,l=0.320.2420.220.0740.0740.0640.0350.0260.016=2.61（位） （2）任何指令都在一个主存周期中取得，那么短指令字长为 8 位，长指令字长为 16 位。又指令都是 二地址指令
15、，所以短指令寄存器-寄存器型的格式为： 长指令为寄存器-主存型的格式为： 由题意可知：指令操作码采用扩展编码，且只能有两种码长。从指令使用频度来看，ADD、SUB 和 CLA 三条指令的使用频度与其它指令的使用频度相差较大，所以用两位操作码的三个码点来表示三条指令，一,个码点作为扩展码点，且扩展三位来表示六条指令，即采用 2-4 扩展编码构成 3/6 编码，2-4 扩展编码 如表所示。,n,2-4 扩展编码（3/6）的平均长度为：l= pi li=2.78 i1,ADDCLASUB J0MJMPSTO CIL STPSHR,（3）（4）由短指令寄存器-寄存器型的格式可知，寄存器号字段长度为 3 位，寄存器个数为 8 个。 则各字段长度如图格式所标识。 而对于长指令寄存器-主存型，一般变址寄存器是某通用寄存器，则变址寄存器号的字段长度为 3 位， 则各字段长度如图格式所标识。 （5）由于相对位移字段长度为 5 位，因此访存地址寻址的最大相对位移量为 25=32 字节。,0.56,0.01,0.03,0.06,0.12,0.26,0.02,0.03,0.06,0.07,0.14,1.00,0.20,0.07,0.44,0.24,0.30,6,
