第二章习题18659

1、.第 二 章 习 题2.26 一个处理机有i1i10共10条指令，经统计，各指令在程序中出现的概率如下：i1：0.25 i2：0.20 i3：0.15 i4：0.10 i5：0.08i6：0.08 i7：0.05 i8：0.04 i9：0.03 i10：0.02（1）计算这10条指令的操作码最短平均长度。（2）写出这10条指令的huffman编码，并计算操作码编码的平均长度一信息冗余量。（3）采用3/7扩展编码法和2/8扩展编码法编写这10条指令的操作码。并分别计算编码的平均长度和信息冗余量。说明哪一种扩展编码较好的理由。解：（1）操作码编码的最短平均长度为：h=-log2pi h= (0.2

2、5log20.250.20log20.200.15log20.150.10log20.100.08log20.080.08log20.080.05log20.050.04log20.040.03log20.030.02log20.02) =2.96（位） （2）根据给出的使用频度，在构造huffman树的过程中，有两个结点可供合并，因此可生成不同的huffman树，其中给出一棵如图所示，相应的huffman编码如表所示。1.00 1 0 1 0 1 00.150.080.050.570.320.170.090.040.250.20 i2 i10.10 1 0 1 00.080.430.230.

3、130.05 1 0 i4 1 0 i30.030.02 1 0 i6 1 0 i5 i10 i9 i8 i7iipihuffman编码li2-5编码（3/7）li2-4编码（2/8）lii1025002002002i2020102012012i3015010310210004i4010110311000510014i50080110411001510104i60081110411010510114i700501110511011511004i800401111511100510014i900311110511101511104i1000211111511110511114精品. huffma

4、n编码的平均长度为：l=lil = 0.2520.2020.1530.1030.0840.0840.0550.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个，用一个作扩展标志；长码长取3位，有码点23=8个，有一个未被利用，即有一个 余码点。编码的平均长度为：l = (0.250.200.15)2(0.100.080.080.050.040.030.02)5 = 3

5、.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.1（位）2/8扩展编码的信息冗余量为：r=1h/l =（12.96/ 3.1）100% = 4.5% 可见，3/7扩展编码优于2/8扩展编码。2.28 用于文字处理的某专用机，每个文字符用4位十进制数字（09）编码表示

6、，空格用表示。在对传送的文字符和空格进行统计后，得出它们的使用频度如下：0.20 0:0.17 1:0.06 2:0.08 3:0.11 4:0.085: 0.05 6:0.08 7:0.13 8:0.03 9:0.01（1）若对数字09和空格采用二进制编码，试设计编码平均长度最短的编码。（2）若传送106个文字符号，且每个文字符号后均自动跟一个空格，按最短的编码，共需传送多少个二进制位？若传送波特率为9600bps，共需传送多少时间？（3）若对数字09和空格采用4位定长码编码，重新计算问题（2）。解：（1）操作码编码的平均长度最短为huffman编码：l=li。生成的huffman树，如图所

7、示，相应的huffman编码如表所示。 l= 3.23（位）（2）根据题意，每个字符的二进制码的平均长度为：3.23（41）=16.15（位）。若要传输106个字符，则要传输二进制位数为：10616.15 =1.615107（位）若波特率为56kb/s，则传输时间为：1.615107/（56103）=288（s）。（3）当采用四位定长编码时，则需要传输二进制位数为：1064（41）=2107（位），传输时间为：2107/（56103）=357（s）。精品.0.600.200.110.050.030.400.200.090.040.011.00 1 0 1 0 1 00.33 0.130.080

8、.270.140.06 1 0 1 0 1 00.170.16 3 7 00.080.08 5 1 6 4 2 9 8iipihuffman编码li020102001700037013010330111103200800104400800114600801104100601114500511104800311110590011111152.30 一台模型机共有7条指令，各指令的使用频度分别为：35%，25%，20%，10%，5%，3%，2%，有8个通用数据寄存器，2个变址寄存器。（1）要求操作码的平均长度最短，请设计操作码的编码，并计算操作码编码的平均长度。（2）设计8位字长的寄存器寄存器型指

9、令3条，16位字长的寄存器一存储器型变址寻址方式指令4条，变址范围不小于正、负127。请设计指令格式，并给出指令各字段的长度和操作码的编码。解：（1）操作码编码的平均长度最短为huffman编码：l=li。生成的huffman树如图所示，相应的huffman编码如表所示。 l= 2.35（位）精品.0.350.600.250.200.100.050.030.400.200.100.050.021.00iipihuffman编码li2-4编码（3/4）lii1035002002i2025012012i3020102102i4010110311004i50051110411014i60031111

10、0511104i700211111511114（2）由于通用寄存器有8个，则指令中通用寄存器字段应为3位；操作码字段2位可有4个码点，用三个码点表示三条指令，另一个码点则作为扩展标志。所以3条8位长的寄存器寄存器型指令格式如下：操作码（2位）寄存器1（3位）寄存器2（3位）由于变址寄存器有2个，则指令中变址寄存器字段应为1位；变址范围-127+127，则指令中相对位移字段应为8位；操作码字段前2位可有4个码点，用三个码点表示三条指令，另一个码点则作为扩展标志。扩展2位正好可表示四条指令，操作码字段则为4位。所以4条16位长的寄存器存储器型指令格式如下：操作码（4位）寄存器（3位）变址寄存器（1

11、位）相对位移（8位）特别地，当采用3/4扩展编码时，使用频度高的用短码表示，使用频度低的用长码表示，其相应的编码如表所示。2.31 某处理机的指令字长为16位，有二地址指令、一地址指令和零地址指令3类，每个地址字段的长度均为6位。（1）如果二地址指令有15条，一地址指令和零地址指令的条数基本相等。问一地址指令和零地址指令各有多少条？并为这3类指令分配操作码。（2）如果指令系统要求这3类指令条数的比例大致为1：9：9，问这3类指令各有多少条？并为这3类指令分配操作码。解：（1）操作码字段取4位可有24=16个码点，用15个码点（00001110）表示15条二地址指令，另一个码点（1111）则作为

12、扩展标志。所以15条二地址指令格式如下：精品.操作码（4位）地址码1（6位）地址码2（6位）由于要求一地址指令和零地址指令的条数基本相等。所以地址码1字段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条二

13、地址指令，另二个码点（1110与1111）则作为扩展标志。扩展标志（1110）扩展地址码1字段6位的64个码点（11100000001110111111）全部用来表示一地址指令，有64条。扩展标志（1111）扩展地址码1字段6位的64个码点，用62个码点（11110000001111111101）表示62条一地址指令，另二个码点（1111111110与1111111111）则作为扩展标志。这样一地址指令，共有126条。扩展标志（1111111110与1111111111）扩展地址码2字段6位，各有64个码点全部用来表示零地址指令，则有128条零地址指令。2.32 某模型机9条指令使用频度为：a

14、dd（加） 30% sub（减） 24% jom（按负转移） 6% sto（存） 7%jmp（转移） 7% shr（右移） 2% cil（循环左移） 3% cla（清除） 20% stp（停机） 1%要求有两种指令字长，都按双操作数指令格式编排，采用扩展操作码，并限制只能有两种操作码码长。设该机有若干通用寄存器，主存为16位宽，按字节编址，采用按整数边界存储，任何指令都在一个主存周期中取得，短指令为寄存器-寄存器型，长指令为寄存器-主存型，主存地址应能变址寻址。（1）仅根据使用频度，不考虑其它要求，设计出全huffman操作码，计算其平均码长；（2）考虑题目全部要求，设计优化实用的操作码形式，

15、并计算其操作码的平均码长；（3）该机允许使用多少可编址的通用寄存器？（4）画出该机两种指令字格式，标出各字段之位数；（5）指出访存操作数地址寻址的最大相对位移量为多少个字节？解：（1）根据给出的使用频度，在构造huffman树的过程中，有两个结点可供合并，因此可生成不同的huffman树，其中给出一棵如图所示，相应的huffman编码如表所示。 huffman编码的平均长度为：l=lil=0.320.2420.220.0740.0740.0640.0350.0260.016=2.61（位）（2）任何指令都在一个主存周期中取得，那么短指令字长为8位，长指令字长为16位。又指令都是二地址指令，所以

16、短指令寄存器-寄存器型的格式为：操作码（2位）寄存器1（3位）寄存器2（3位）长指令为寄存器-主存型的格式为：操作码（5位）寄存器（3位）变址寄存器（3位）相对位移（5位）由题意可知：指令操作码采用扩展编码，且只能有两种码长。从指令使用频度来看，add、sub和cla三条指令的使用频度与其它指令的使用频度相差较大，所以用两位操作码的三个码点来表示三条指令，一个码点作为扩展码点，且扩展三位来表示六条指令，即采用2-4扩展编码构成3/6编码，2-4扩展精品.编码如表所示。 2-4扩展编码（3/6）的平均长度为：l=li=2.781.000.560.060.030.020.260.120.060.030.01 0.440.240.200.30 add cla sub 0.070.140.07 j0m jmp sto cil stp shr 指令iipihuffman编码li2-5编码（3/6）liaddi1030012002subi2024112012clai3020102102stoi400700114110015jmpi500700104110105j