计算机体系结构实验 huffman编码

中南大学

计算机体系结构

实验报告

学院：_信息科学与工程学院____

专业班级：计算机科学与技术09**班

学号： 090909****

姓名： ***

指导教师：陈丽萍

2012年4月

一、实验目的

了解和掌握指令编码的基本要求和基本原理，对编码方式和它的优缺点有个更深入的了解。

二、实验内容

使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。

三、实验过程

我们举例说明此问题，例如：

有一组指令的操作码共分七类，它们出现概率如下表所示：

对此组指令进行HUFFMAN 编码正如下图所示：

最后得到的HUFFMAN 编码如下表所示：

最短编码长度为：

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 树进行中序遍历即可完成编码工作。

四、具体实现

总体函数的截图

固定长度编码

Huffman_Code_Show.Clear();

int length = Stady_Coding_Line.Count;

int Code_Length=Convert.ToInt16(Math.Log(length))+1;

for (int i = 0; i < length;i++ )

{

Stady_Coding_Line[i].code_flag = i;

}

for (int i = 0; i < length;i++ )

{

string dcod = Convert.ToString(Stady_Coding_Line[i].code_flag, 2);

if (dcod.Length

{

string dcod_end=dcod;

int mul = Code_Length - dcod.Length;

for (int s = 0; s < mul;s++ )

{

dcod_end = "0" + dcod_end;

}

Stady_Coding_Line[i].Scode = dcod_end;

}

else

{

Stady_Coding_Line[i].Scode = dcod;

}

}

for (int i = 0; i < Stady_Coding_Line.Count;i++ )

{

Huffman_Code_Show.Text += "指?令?【?"+ Stady_Coding_Line[i].myself.ToString() + "】? 固?定¨长¤编括?码?为a：阰"+ Stady_Coding_Line[i].Scode.ToString() + "\n";

}

Huffman编码

private void bt_Coding_Click(object sender, RoutedEventArgs e)

{

for (int i = 0; i < Before_Coding_Line.Count;i++ )

{

for (int j = 0; j < Before_Coding_Line.Count - 1;j++ )

{

if (Before_Coding_Line[i].weight

{

Node stmp = Before_Coding_Line[i];

Before_Coding_Line[i] = Before_Coding_Line[j];

Before_Coding_Line[j] = stmp;

}

}

}

Huffman_Code_Show.Clear();

while (true)

{

if (Before_Coding_Line.Count>=2)

{

int count = 0;//生Θ?成é节ú点?计?数簓器÷

newnode.weight = Before_Coding_Line[0].weight + Before_Coding_Line[1].weight;

newnode.myself = count.ToString();

if

(Before_Coding_Line[0].myself!="1"&&Before_Coding_Line[0].myself!="2"&&Before_Coding_Li ne[0].myself!="3"&&Before_Coding_Line[0].myself!="4"&&Before_Coding_Line[0].myself!="5" &&Before_Coding_Line[0].myself!="6"&&Before_Coding_Line[0].myself!="0")

{

Huffman_Tree.Add(Before_Coding_Line[0]);

}

if(Before_Coding_Line[1].myself != "1"&& Before_Coding_Line[1].myself != "2"&& Before_Coding_Line[1].myself != "3"&& Before_Coding_Line[1].myself != "4"&& Before_Coding_Line[1].myself != "5"&& Before_Coding_Line[1].myself != "6" && Before_Coding_Line[1].myself != "0")

{

Huffman_Tree.Add(Before_Coding_Line[1]);

}

Before_Coding_Line.Remove(Before_Coding_Line[0]);

Before_Coding_Line.Remove(Before_Coding_Line[0]);

Before_Coding_Line.Add(newnode);

for (int i = 0; i < Before_Coding_Line.Count; i++)

{

for (int j = 0; j < Before_Coding_Line.Count - 1; j++)

{

if(Before_Coding_Line[i].weight < Before_Coding_Line[j].weight)

{

Node stmp = Before_Coding_Line[i];

Before_Coding_Line[i] = Before_Coding_Line[j];

Before_Coding_Line[j] = stmp;

}

}

}

count++;

}

else

{

break;

}

}

for (int i = 0; i < Huffman_Tree.Count; i++)

{

Huffman_Code_Show.Text += "指?令?【?"+ Huffman_Tree[i].myself.ToString() + "】?" + "\n" + "出?现?概?率ê：阰" + Huffman_Tree[i].weight.ToString()+"\n";

}

cou = 1;

for (int i = Huffman_Tree.Count; i >= 1;i-- )

{

string hcode=null;

for (int j = 0; j < cou-1;j++ )

{

hcode += "1";

}

hcode += "0";

Huffman_Tree[i-1].Hcode = hcode;

cou++;

}

string hcod=null;

for (int i = 0; i < cou - 2;i++ )

{

hcod += "1";

}

Huffman_Tree[0].Hcode = hcod;

for (int i = Huffman_Tree.Count-1; i >= 0;i-- )

{

Huffman_Code_Show.Text += "指?令?【?"+ Huffman_Tree[i].myself + "】? 哈t夫え?曼ü编括?码?为a：阰" + Huffman_Tree[i].Hcode.ToString() + "\n";

}

}