1、计算机体系结构报告1中南大学计算机体系结构实验报告学生姓名 惠苗壮 指导教师 余腊生 学 院 信息科学与工程学院 专业班级 计科0904班 学 号 0909091627 完成时间 2012年04月15日 霍夫曼编码及扩展编码一、 实验目的 了解和掌握对指令操作码进行霍夫曼编码的基本要求和基本原理，以及使用程序实现的方法。了解和掌握对指令操作码进行扩展编码的基本要求和基本原理，以及使用程序实现的方法。二、问题描述 使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。 问题描述以及问题分析： 我们举例说明此问题，例如：
2、 有一组指令的操作码共分七类，它们出现概率如 P1P2P3P4P5P6P70.450.300.150.050.030.010.01下表所示： 对此组指令进行HUFFMAN编码正如下图所示： 最后得到的HUFFMAN编码如下表所示： P1 P2 P3 P4 P5 P6 P7 0 10 110 1110 11110 111110111111 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树再进
3、行HUFFAM编码。此过程的难点构造HUFFMAN树，进行HUFFAM编码只要对你所生成的HUFFMAN树进行中序遍历即可完成编码工作。 再采用固定长操作码与霍夫曼编码相结合的方法得到扩展编码。三 . 设计简要描述 本实验采用jav语言来完成实验。具体实验方法如下： 对操作码单独建立一个类，属性有名称，是否被遍历，父节点，左右孩子，概率。具体代码如下： class Code private String name;/名称 public boolean good = true; private Code parent = null;/父节点 public Code getParent() ret
4、urn parent; public void setParent(Code parent) this.parent = parent; private Code LChrid;/左孩子 public Code getLChrid() return LChrid; public void setLChrid(Code lChrid) LChrid = lChrid; private Code RChild;/右孩子 public Code getRChild() return RChild; public void setRChild(Code rChild) RChild = rChild;
5、 private String Huffmancode;/概率 public String getHuffmancode() return Huffmancode; public void setHuffmancode(String huffmancode) Huffmancode = huffmancode; public String getName() return name; public void setName(String name) this.name = name; private double probability = 0; public double getProbab
6、ility() return probability; public void setProbability(double probability) this.probability = probability; public Code(String name,double probability) this.name = name; this.probability = probability; public String toString() String s = name+:+probability; return s; 对每个节点根据概率排序，采用起泡排序的方法。具体代码如下：publ
7、ic void SortCode(ArrayList code)/起泡排序 int i = 0; int j = 0; for(i = 0;icode.size();i+) for(j=0;jcode.get(j+1).getProbability() double temp = code.get(j).getProbability(); code.get(j).setProbability(code.get(j+1).getProbability(); code.get(j+1).setProbability(temp); 对排序后的序列进行霍夫曼编码private void Encodin
8、g_1()/霍夫曼编码 this.SortCode(StartVaule); while(StartVaule.size()1) Code code1 = new Code(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); StartVa
9、ule.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(
10、StartVaule.get(0); Encoding_2(); 中序遍历编码后的序列，得到霍夫曼编码private void Encoding_2() for(int i = 0;i=0; i-) bitnum=(j-1)/3+1)*2;/编码位数 num=j%3; for(int h=0;hbitnum-2;h+) code=1+code; if(i=0&num=1) /code=code+11; else switch(num) case 1: code=code+00;break; case 2: code=code+01;break; case 0: code=code+10;bre
11、ak; Code.get(i).setHuffmancode(code); code=; j+; 四源程序：霍夫曼编码：import java.util.*;public class HuffmanCode static ArrayList StartVaule = new ArrayList(); static ArrayList MiddleVaule = new ArrayList(); static ArrayList ResultVaule = new ArrayList(); public void StartCode() StartVaule.add(new Code(I1,0.
12、45); StartVaule.add(new Code(I2,0.30); StartVaule.add(new Code(I3,0.15); StartVaule.add(new Code(I4,0.05); StartVaule.add(new Code(I5,0.03); StartVaule.add(new Code(I6,0.01); StartVaule.add(new Code(I7,0.01); public void SortCode(ArrayList code) int i = 0; int j = 0; for(i = 0;icode.size();i+) for(j
13、=0;jcode.get(j+1).getProbability() double temp = code.get(j).getProbability(); code.get(j).setProbability(code.get(j+1).getProbability(); code.get(j+1).setProbability(temp); private void Encoding_1() this.SortCode(StartVaule); while(StartVaule.size()1) Code code1 = new Code(Node1,StartVaule.get(0).g
14、etProbability()+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.InsertC
15、ode(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(); private void Encoding_2() for(int i = 0;iMiddleVaule.size();i+) if(MiddleVaule.
16、get(i).good) Code parent = 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); public void print() for(int i = 0; iResultVaule.size();i+)
17、System.out.println(ResultVaule.get(i).getName()+ 的编码为： +ResultVaule.get(i).getHuffmancode(); public void InsertCode(Code code,ArrayList array) int i = 0; for(i= 0;iarray.size();i+) if(code.getProbability()array.get(i).getProbability() break; array.add(i,code); public static void main(String args) Hu
18、ffmanCode tc = new HuffmanCode(); tc.StartCode(); /*tc.SortCode(StartVaule); tc.InsertCode(new Code(I123,0.16), StartVaule); for(int i = 0;iStartVaule.size();i+) System.out.println(StartVaule.get(i); */ tc.Encoding_1(); tc.print(); class Code private String name; public boolean good = true; private
19、Code parent = null; public Code getParent() return parent; public void setParent(Code parent) this.parent = parent; private Code LChrid; public Code getLChrid() return LChrid; public void setLChrid(Code lChrid) LChrid = lChrid; private Code RChild; public Code getRChild() return RChild; public void
20、setRChild(Code rChild) RChild = rChild; private String Huffmancode; public String getHuffmancode() return Huffmancode; public void setHuffmancode(String huffmancode) Huffmancode = huffmancode; public String getName() return name; public void setName(String name) this.name = name; private double prob
21、ability = 0; public double getProbability() return probability; public void setProbability(double probability) this.probability = probability; public Code(String name,double probability) this.name = name; this.probability = probability; public String toString() String s = name+:+probability; return
22、s; 扩展编码：import java.util.ArrayList;import java.util.List;public class ExtendCoding private List Code = new ArrayList(); public void initCode() Code.add(new Code(I1,0.45); Code.add(new Code(I2,0.30); Code.add(new Code(I3,0.15); Code.add(new Code(I4,0.05); Code.add(new Code(I5,0.03); Code.add(new Code
23、(I6,0.01); Code.add(new Code(I7,0.01); /指令按概率从小到大排序 public void sortByProb() Code temp; for(int i=0; iCode.size(); i+) for(int j=0; jCode.get(j+1).getProbability() temp = Code.get(j); Code.set(j, Code.get(j+1); Code.set(j+1, temp); public void coding() sortByProb(); int j=1; int bitnum; int num; Str
24、ing code=; for(int i=Code.size()-1; i=0; i-) bitnum=(j-1)/3+1)*2;/编码位数 num=j%3; for(int h=0;hbitnum-2;h+) code=1+code; if(i=0&num=1) /code=code+11; else switch(num) case 1: code=code+00;break; case 2: code=code+01;break; case 0: code=code+10;break; Code.get(i).setHuffmancode(code); code=; j+; public
25、 static void main(String args) ExtendCoding ec = new ExtendCoding(); ec.initCode(); ec.coding(); for(Code i:ec.getInstructions() System.out.println(i.getName()+ 的扩展编码为： +i.getHuffmancode(); public void setInstructions(List instructions) this.Code = instructions; public List getInstructions() return Code; 五.结果分析:由上面的输出结果界面可以看到程序输出霍夫曼编码及扩展编码的结果，输出的结
