计算机体系结构报告1.docx
- 文档编号:8941106
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:18
- 大小:38.39KB
计算机体系结构报告1.docx
《计算机体系结构报告1.docx》由会员分享,可在线阅读,更多相关《计算机体系结构报告1.docx(18页珍藏版)》请在冰点文库上搜索。
计算机体系结构报告1
中南大学
计算机体系结构
实验报告
学生姓名惠苗壮
指导教师余腊生
学院信息科学与工程学院
专业班级计科0904班
学号0909091627
完成时间2012年04月15日
霍夫曼编码及扩展编码
一、实验目的
了解和掌握对指令操作码进行霍夫曼编码的基本要求和基本原理,以及使用程序实现的方法。
了解和掌握对指令操作码进行扩展编码的基本要求和基本原理,以及使用程序实现的方法。
二、问题描述
使用编程工具编写一个程序,对一组指令进行霍夫曼编码,并输出最后的编码结果以及对指令码的长度进行评价。
与扩展操作码和等长编码进行比较。
问题描述以及问题分析:
我们举例说明此问题,例如:
有一组指令的操作码共分七类,它们出现概率如
P1
P2
P3
P4
P5
P6
P7
0.45
0.30
0.15
0.05
0.03
0.01
0.01
下表所示:
对此组指令进行HUFFMAN编码正如下图所示:
最后得到的HUFFMAN编码如下表所示:
P1
P2
P3
P4
P5
P6
P7
0
10
110
1110
11110
111110
111111
1
2
3
4
5
6
6
最短编码长度为:
H=0.45*1+0.30*2+0.15*3+0.05*4+0.03*5+0.01*6+0.01*6=-1.95.
要对指令的操作码进行HUFFMAN编码,只要根据指令的各类操作码的出现概率构造HUFFMAN树再进行HUFFAM编码。
此过程的难点构造HUFFMAN树,进行HUFFAM编码只要对你所生成的HUFFMAN树进行中序遍历即可完成编码工作。
再采用固定长操作码与霍夫曼编码相结合的方法得到扩展编码。
三.设计简要描述
本实验采用jav语言来完成实验。
具体实验方法如下:
对操作码单独建立一个类,属性有名称,是否被遍历,父节点,左右孩子,概率。
具体代码如下:
classCode{
privateStringname;//名称
publicbooleangood=true;
privateCodeparent=null;//父节点
publicCodegetParent(){
returnparent;
}
publicvoidsetParent(Codeparent){
this.parent=parent;
}
privateCodeLChrid;//左孩子
publicCodegetLChrid(){
returnLChrid;
}
publicvoidsetLChrid(CodelChrid){
LChrid=lChrid;
}
privateCodeRChild;//右孩子
publicCodegetRChild(){
returnRChild;
}
publicvoidsetRChild(CoderChild){
RChild=rChild;
}
privateStringHuffmancode;//概率
publicStringgetHuffmancode(){
returnHuffmancode;
}
publicvoidsetHuffmancode(Stringhuffmancode){
Huffmancode=huffmancode;
}
publicStringgetName(){
returnname;
}
publicvoidsetName(Stringname){
this.name=name;
}
privatedoubleprobability=0;
publicdoublegetProbability(){
returnprobability;
}
publicvoidsetProbability(doubleprobability){
this.probability=probability;
}
publicCode(Stringname,doubleprobability){
this.name=name;
this.probability=probability;
}
publicStringtoString(){
Strings=name+":
"+probability;
returns;
}
}
对每个节点根据概率排序,采用起泡排序的方法。
具体代码如下:
publicvoidSortCode(ArrayListcode){//起泡排序
inti=0;
intj=0;
for(i=0;i for(j=0;j if(code.get(j).getProbability()>code.get(j+1).getProbability()){ doubletemp=code.get(j).getProbability(); code.get(j).setProbability(code.get(j+1).getProbability()); code.get(j+1).setProbability(temp); } } } } 对排序后的序列进行霍夫曼编码 privatevoidEncoding_1(){//霍夫曼编码 this.SortCode(StartVaule); while(StartVaule.size()>1){ Codecode1=newCode("Node1",StartVaule.get(0).getProbability()+StartVaule.get (1).getProbability()); code1.good=false; StartVaule.get(0).setParent(code1); StartVaule.get (1).setParent(code1); StartVaule.get(0).setHuffmancode("0"); StartVaule.get (1).setHuffmancode("1"); MiddleVaule.add(StartVaule.get(0)); MiddleVaule.add(StartVaule.get (1)); this.InsertCode(code1,StartVaule); StartVaule.remove(StartVaule.get(0)); StartVaule.remove(StartVaule.get(0)); } StartVaule.get(0).setHuffmancode("1"); MiddleVaule.add(StartVaule.get(0)); StartVaule.remove(StartVaule.get(0)); Encoding_2(); } 中序遍历编码后的序列,得到霍夫曼编码 privatevoidEncoding_2(){ for(inti=0;i if(MiddleVaule.get(i).good){ Codeparent=MiddleVaule.get(i).getParent(); while(parent! =null){ MiddleVaule.get(i).setHuffmancode(parent.getHuffmancode()+MiddleVaule.get(i).getHuffmancode()); parent=parent.getParent(); } ResultVaule.add(MiddleVaule.get(i)); } } } 继续编码,得到扩展编码。 publicvoidcoding() { sortByProb(); intj=1; intbitnum; intnum; Stringcode=""; for(inti=Code.size()-1;i>=0;i--) { bitnum=((j-1)/3+1)*2;//编码位数 num=j%3; for(inth=0;h { code="1"+code; } if(i<=0&&num==1) { //code=code+"11"; } else { switch(num) { case1: code=code+"00";break; case2: code=code+"01";break; case0: code=code+"10";break; } } Code.get(i).setHuffmancode(code); code=""; j++; } } 四.源程序: 霍夫曼编码: importjava.util.*; publicclassHuffmanCode{ staticArrayList staticArrayList staticArrayList publicvoidStartCode(){ StartVaule.add(newCode("I1",0.45)); StartVaule.add(newCode("I2",0.30)); StartVaule.add(newCode("I3",0.15)); StartVaule.add(newCode("I4",0.05)); StartVaule.add(newCode("I5",0.03)); StartVaule.add(newCode("I6",0.01)); StartVaule.add(newCode("I7",0.01)); } publicvoidSortCode(ArrayList inti=0; intj=0; for(i=0;i for(j=0;j if(code.get(j).getProbability()>code.get(j+1).getProbability()){ doubletemp=code.get(j).getProbability(); code.get(j).setProbability(code.get(j+1).getProbability()); code.get(j+1).setProbability(temp); } } } } privatevoidEncoding_1(){ this.SortCode(StartVaule); while(StartVaule.size()>1){ Codecode1=newCode("Node1",StartVaule.get(0).getProbability()+StartVaule.get (1).getProbability()); code1.good=false; StartVaule.get(0).setParent(code1); StartVaule.get (1).setParent(code1); StartVaule.get(0).setHuffmancode("0"); StartVaule.get (1).setHuffmancode("1"); MiddleVaule.add(StartVaule.get(0)); MiddleVaule.add(StartVaule.get (1)); this.InsertCode(code1,StartVaule); StartVaule.remove(StartVaule.get(0)); StartVaule.remove(StartVaule.get(0)); } StartVaule.get(0).setHuffmancode("1"); MiddleVaule.add(StartVaule.get(0)); StartVaule.remove(StartVaule.get(0)); Encoding_2(); } privatevoidEncoding_2(){ for(inti=0;i if(MiddleVaule.get(i).good){ Codeparent=MiddleVaule.get(i).getParent(); while(parent! =null){ MiddleVaule.get(i).setHuffmancode(parent.getHuffmancode()+MiddleVaule.get(i).getHuffmancode()); parent=parent.getParent(); } ResultVaule.add(MiddleVaule.get(i)); } } } publicvoidprint(){ for(inti=0;i System.out.println(ResultVaule.get(i).getName()+"的编码为: "+ResultVaule.get(i).getHuffmancode()); } } publicvoidInsertCode(Codecode,ArrayList inti=0; for(i=0;i if(code.getProbability() break; } } array.add(i,code); } publicstaticvoidmain(Stringargs[]){ HuffmanCodetc=newHuffmanCode(); tc.StartCode(); /*tc.SortCode(StartVaule); tc.InsertCode(newCode("I123",0.16),StartVaule); for(inti=0;i System.out.println(StartVaule.get(i)); }*/ tc.Encoding_1(); tc.print(); } } classCode{ privateStringname; publicbooleangood=true; privateCodeparent=null; publicCodegetParent(){ returnparent; } publicvoidsetParent(Codeparent){ this.parent=parent; } privateCodeLChrid; publicCodegetLChrid(){ returnLChrid; } publicvoidsetLChrid(CodelChrid){ LChrid=lChrid; } privateCodeRChild; publicCodegetRChild(){ returnRChild; } publicvoidsetRChild(CoderChild){ RChild=rChild; } privateStringHuffmancode; publicStringgetHuffmancode(){ returnHuffmancode; } publicvoidsetHuffmancode(Stringhuffmancode){ Huffmancode=huffmancode; } publicStringgetName(){ returnname; } publicvoidsetName(Stringname){ this.name=name; } privatedoubleprobability=0; publicdoublegetProbability(){ returnprobability; } publicvoidsetProbability(doubleprobability){ this.probability=probability; } publicCode(Stringname,doubleprobability){ this.name=name; this.probability=probability; } publicStringtoString(){ Strings=name+": "+probability; returns; } } 扩展编码: importjava.util.ArrayList; importjava.util.List; publicclassExtendCoding{ privateList publicvoidinitCode() { Code.add(newCode("I1",0.45)); Code.add(newCode("I2",0.30)); Code.add(newCode("I3",0.15)); Code.add(newCode("I4",0.05)); Code.add(newCode("I5",0.03)); Code.add(newCode("I6",0.01)); Code.add(newCode("I7",0.01)); } //指令按概率从小到大排序 publicvoidsortByProb() { Codetemp; for(inti=0;i { for(intj=0;j { if(Code.get(j).getProbability()>Code.get(j+1).getProbability()) { temp=Code.get(j); Code.set(j,Code.get(j+1)); Code.set(j+1,temp); } } } } publicvoidcoding() { sortByProb(); intj=1; intbitnum; intnum; Stringcode=""; for(inti=Code.size()-1;i>=0;i--) { bitnum=((j-1)/3+1)*2;//编码位数 num=j%3; for(inth=0;h { code="1"+code; } if(i<=0&&num==1) { //code=code+"11"; } else { switch(num) { case1: code=code+"00";break; case2: code=code+"01";break; case0: code=code+"10";break; } } Code.get(i).setHuffmancode(code); code=""; j++; } } publicstaticvoidmain(String[]args){ ExtendCodingec=newExtendCoding(); ec.initCode(); ec.coding(); for(Codei: ec.getInstructions()) System.out.println(i.getName()+"的扩展编码为: "+i.getHuffmancode()); } publicvoidsetInstructions(List this.Code=instructions; } publicList returnCode; } } 五.结果分析: 由上面的输出结果界面可以看到程序输出霍夫曼编码及扩展编码的结果,输出的结StartVaule=newArrayList
();
MiddleVaule=newArrayList
();
ResultVaule=newArrayList
();
code){
array){
Code=newArrayList
();
instructions){
getInstructions(){
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机体系结构 报告