信息论课程设计报告(2)

挑选权值最小的两个节点

void select(HuffmanTree HT, int node_num, int &a1, int &a2) 建造霍夫曼树

void CreateTree(HuffmanTree &HT,HuffmanCode &HC,int count[],char word[]) 编码

void EncodeHuffman (HuffmanTree HT,HuffmanCode HC) 译码

void decode(HuffmanCode HC,char changed[],char output[]) 输出二进制编码

void Print(HuffmanCode HC,char input[],char after[]) 输入字符概率统计

int Sta(char * input,int count[], char word[]) 编码效率计算

double Ratio(char input[],int count[],HuffmanCode HC)

各模块的调用关系： 主程序 ↓

各功能模块

1.3测试情况

2、费诺编码 2.1算法思想

将信源消息符号按其出现的概率大小依次排列排列：p1?p2???pn。在程序中由sort()函数处理，此函数是一个冒泡排序法。若想改进，可用其它的排序算法。

将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并且对各组赋予一个二进制码元“0”和“1”。

将每一大组的信源符号再分成两组，使划分后的两个组的概率之和近似相同，并且对各组赋予一个二进制符号“0”和“1”。

如此重复，直到每个组只剩下一个信源符号为止。在程序中本部分采用递归思想。

2.2模块划分

（1）主程序模块：

Int main() {

初始化； 输入数据； 执行功能；

显示结果；

}

（2）各功能模块

输入字符的频数统计

int Sta(char*in,int count[],char w[]){} 为费诺结点分配具体数据值

void FanoNode(char in[],int count[],char w[]){} 将费诺结点数组按照概率降序排列 sort（begin，end，compare（））{} 编码

void EncodeFano(Fano F[],float pro,int begin,int end){} 译码

void decode(Fano F[],char after[],char out[]){} 计算编码效率

double Ratio(char in[],int count[],Fano F[]){}

2.3测试情况

3、游程编码

3.1算法思想

用一个符号值或串长代替具有相同值的连续符号(连续符号构成了一段连续的\行程\。行程编码因此而得名)，使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。

首先,将其按行分别进行读入和计数,其次,对灰度值进行编码,第三,对个数进行编码,

过程:首先,我们以<1,7>为例,对”1”我们用find函数(因为灰度级编码时按顺序存储所以其算法通过二分法查找来实现的)找到其在信源符号编码结果集中位置,然后将其码字拷贝到存储编码结果的存储结构中去.对于”7”则是在个数编码结果集中去用同样的方法进行查找,找到后也是用将其拷贝到编码结果存储结构中去.如此直到全部编码结束为止. 编码的效率：

计算方法:设图像的灰度级为M，一行的长度为N，则对每一行来说，游程数最少为1，最多为N。若将数对表示为（gk,lk）的序列， 用普通二进制码存放（gk,lk）序列，并设一行中的游程数为m，则描述一行像素的码字长度为：m?log2M?log2N?bit.而直接存储原图像一行所需的位数为Nlog2Mbit。

效率P=1-?m?log2M?log2N?bit/（Nlog2Mbit*C）.(c为行数)

0c3.2模块划分

（1）主程序模块：

Int main() {

初始化； 输入数据； 执行功能；

显示结果； }

（2）各功能模块 求出编码的长度 int get_gd(int n) 用于输出编码结果

void print( vectorvd)

输出码及其个数的组合

void print1( vector re) 输出编,解码结果

void print2(vector cd,int n) 读入要编码的灰度矩阵

bool read(vector &vr,int hd,int & cor,int &rows) 用于读取要解码的序列

bool read1(vector & vc,int num)

查找要编码的灰度值是否在灰度级范围内如果在返回相应码在编码序列中的位置

int find(vector vd,int x)

对灰度矩阵进行编码操作成功则通过cd将其值代回

void Encode(vector vr,vector vd,vector vh,vector &cd)

对输入要解码的序列进行解码操作

void coding(vector vc,vector &vi,int gd,int gds) 编码效率

void ratio(int cl,int ml,int col,int row)

3.3测试情况