信息论与编码课程作业
——霍夫曼编码求信源熵和存储前后的信息量的变化
一：设计目的：
1、学习离散信源平均信息量的计算方法。
2、理解和掌握huffman 编码的基本原理，实现对信源符号的huffman 编码
3、熟悉 Matlab 编程； 二：设计原理和思路
1.信源熵的计算：
公式： 21()log a I a p = Matlab 实现：I=log2(1/p) 或I=-log2(p) 熵(平均自信息)的计算公式
22111()log log q
q i i i i i i H x p p p p ====-∑
∑
Matlab 实现：HX=sum(-x.*log2(x))；或者h=h-x(i)*log2(x(i));
2.霍夫曼编码原理;
分为两步，首先是码树形成过程：对信源概率进行合并形成编码码树。然后是码树回溯过程：在码树上分配编码码字并最终得到Huffman 编码。
1、码树形成过程：将信源概率按照从小到大顺序排序并建立相应的位置索引。然后按上述规则进行信源合并，再对信源进行排序并建立新的位置索引，直到合并结束。在这一过程中每一次都把排序后的信源概率存入矩阵p 中，位置索引存入矩阵m 中。这样，由排序之后的概率矩阵 p 以及索引矩阵m 就可以恢复原概率矩阵P 了，从而保证了回溯过程能够进行下去。
2、码树回溯过程：在码树上分配编码码字并最终得到Huffman 编码。从索引矩阵M 的末行开始回溯。
(1) 在p 的末行2元素位置填入0和1。
(2) 根据该行索引1位置指示，将索引1位置的编码(‘1’)填入上一行的第
一、第二元
素位置，并在它们之后分别添加‘0’和‘1’。
