实验三 哈夫曼编码

实验一 离散信源及其信息测度

一、实验目的

1、理解信源编码的意义； 2、熟悉 MATLAB程序设计；

3、掌握哈夫曼编码的方法及计算机实现；

二、实验原理

通信的根本问题是如何将信源输出的信息在接收端的信宿精确或近似的复制出来。为了有效地复制信号，就通过对信源进行编码，使通信系统与信源的统计特性相匹配。

若接收端要求无失真地精确地复制信源输出的信息，这样的信源编码即为无失真编码。即使对于一个小的时间段内，连续信源输出的信息量也可以是无限大的，所以对其是无法实现无失真编码的；而离散信源输出的信息量却可以看成是有限的，所以只有离散信源才可能实现无失真编码。

凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可以称为最佳码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。

变字长编码的最佳编码定理：在变字长码中，对于概率大的信息符号编以短字长的码；对于概率小的信息符号编以长字长的码。如果码字长度严格按照符号概率的大小顺序排列，则平均码字长度一定小于俺任何顺序排列方式得到的码字长度。

哈夫曼编码就是利用了这个定理，讲等长分组的信源符号，根据其概率分布采用不等长编码。概率大的分组，使用短的码字编码；概率小的分组，使用长的码字编码。哈夫曼编码把信源按概率大小顺序排列，并设法按逆次序分配码字的长度。在分配码字的长度时，首先将出现概率最小的两个符号相加，合成一个概率；第二步把这个合成的概率看成是一个新组合符号的概率，重复上述做法，直到最后只剩下两个符号的概率为止。完成以上概率相加顺序排列后，再反过来逐步向前进行编码。每一步有两个分支，各赋予一个二进制码，可以对概率大的编为0码，概率小的编为1码。反之亦然。

哈夫曼编码的具体步骤归纳如下：

1. 统计n个信源消息符号，得到n个不同概率的信息符号。 2. 将这n个信源信息符号按其概率大小依次排序：

p(x1) ≥ p(x2)≥ …≥ p(xn)

3. 取两个概率最小的信息符号分别配以0和1两个码元，并将这两个概率

相加作为一个新的信息符号的概率，和未分配的信息符号构成新的信息

符号序列。

4. 将剩余的信息符号，按概率大小重新进行排序。

5. 重复步骤3，将排序后的最后两个小概论相加，相加和与其他概率再排

序。 6. 如此反复重复n-2次，最后只剩下两个概率。

7. 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相

应的码字，构成霍夫曼编码字。编码结束。

哈夫曼编码产生最佳整数前缀码，即没有一个码字是另一个码字的前缀，因此哈夫曼编码是唯一码。

编码之后，哈夫曼编码的平均码长为：

K?哈夫曼编码的效率为：

?p(x)Kii?1ni

??信源熵H(x)=

平均码长K三、实验内容

实验一、对信源进行哈夫曼编码，并计算编码效率。

1、按照实验一中的方法生成一10维离散无记忆信源X的概率分布。 2、对信源概率进行排序，（排序可用sort命令）。

3、取两个概率最小的信息符号分别配以0和1两个码元，并将这两个概率相加作为一个新的信息符号的概率，和未分配的信息符号构成新的信息符号序列，（分配的0,1可另建一个向量保存）。

4、将剩余的信息符号，按概率大小重新进行排序。

5、重复步骤3，将排序后的最后两个小概论相加，相加和与其他概率再排

序（利用for循环）。

6、如此反复重复n-2次，最后只剩下两个概率。

7、从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相

应的码字，构成霍夫曼编码字。编码结束。 8、计算平均码长与编码效率。

实验二、查看huffmandict函数，了解该函数的用途，调用格式，利用该函数

对实验一中的数据进行编码，并比较两者结果。

实 验 三

实验离散信源及其信息测度 名称 课程信息论基础 名称 姓 学 姜圆香 专业、班级 信计11101班 名 号 班内实验地05 实验时间 2014.3.24 序号 点 实验一：对信源进行哈夫曼编码，并计算编码效率。 201106216 10教四楼 1、按照实验一中的方法生成一10维离散无记忆信源X的概率分布。 2、对信源概率进行排序，（排序可用sort命令）。 3、取两个概率最小的信息符号分别配以0和1两个码元，并将这两个概率相加作为一个新的信息符号的概率，和未分配的信息符号构成新的信息符号序列，（分配的0,1可另建一个向量保存）。 实 4、将剩余的信息符号，按概率大小重新进行排序。 验 5、重复步骤3，将排序后的最后两个小概论相加，相加和与其他概率再 。 内 排序（利用for循环） 6、如此反复重复n-2次，最后只剩下两个概率。 容 7、从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字，构成霍夫曼编码字。编码结束。 8、计算平均码长与编码效率。 实验二： 查看huffmandict函数，了解该函数的用途，调用格式，利用该函数对实验一中的数据进行编码，并比较两者结果。 实验一：编程实现哈夫曼编码 代码： m=rand(1,10) s=sum(m); p=m/s q=p; n=10; a=zeros(n-1,n); 生成一个n-1行n列的数组 for i=1:n-1 [q,l]=sort(q) ; a(i,:)=[l(1:n-i+1),zeros(1,i-1)] ; q=[q(1)+q(2),q(3:n),1]; end 实 验 过 程 及 结 果 分 析 for i=1:n-1 c(i,1:n*n)=blanks(n*n); end c(n-1,n)='1'; c(n-1,2*n)='0'; for i=2:n-1 c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)==1))-(n-2):n*(find(a(n-i+1,:)==1))) ; c(n-i,n)='1' ; 在分支的第一个元素后补1 c(n-i,n+1:2*n-1)=c(n-i,1:n-1) ; c(n-i,2*n)='0' ; 在分支的第一个元素后补0 for j=1:i-1 c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)==j+1)-1)+1:n*find(a(n-i+1,:)==j+1)); end end 完成Huffman编码 for i=1:n h(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n) ; ll(i)=length(find(abs(h(i,:))~=32)); 计算每一个Huffman码长 end l=sum(p.*ll); 计算平均码长 fprintf('\\n Huffman编码结果为:\\n'); h fprintf('\\n 编码的平均码长为:\\n'); l 实验结果： Huffman编码结果为: H= 1111 000 1010 110 1110 100 1011 011 010 001 编码的平均码长为: l = 3.1834 实验二：利用huffmandict函数实现编码 代码： y=p/sum(p) symbols = [1:10] [dict,avglen] = huffmandict(symbols,y) temp = dict; for i = 1:length(temp) temp{i,2} = num2str(temp{i,2}); end temp 实验结果： symbols = 1 2 3 4 5 6 7 8 9 10 dict = [ 1] [1x4 double] [ 2] [1x3 double] [ 3] [1x4 double] [ 4] [1x3 double] [ 5] [1x4 double] [ 6] [1x3 double] [ 7] [1x4 double] [ 8] [1x3 double] [ 9] [1x3 double] [10] [1x3 double] avglen = 3.1835 temp = [ 1] '1 1 1 1' [ 2] '0 0 0' [ 3] '1 0 1 0' [ 4] '1 1 0' [ 5] '1 1 1 0' [ 6] '1 0 0' [ 7] '1 0 1 1' [ 8] '0 1 1' [ 9] '0 1 0' [10] '0 0 1' 实验小结： 本次实验，在熟练掌握哈弗曼编码的理论知识后，还很大程度考验了我们的编程能力，将树结构的引入以及对树的各结点的赋值实现Huffman编码。虽然自己最后没有独立的把整个过程实现，而是查阅了相关资料，但是，如果遇到需要编码的地方，我完全可以在Matlab里面用Huffman函数来实现编码，同样达到目的。

temp = [ 1] '1 1 1 1' [ 2] '0 0 0' [ 3] '1 0 1 0' [ 4] '1 1 0' [ 5] '1 1 1 0' [ 6] '1 0 0' [ 7] '1 0 1 1' [ 8] '0 1 1' [ 9] '0 1 0' [10] '0 0 1' 实验小结： 本次实验，在熟练掌握哈弗曼编码的理论知识后，还很大程度考验了我们的编程能力，将树结构的引入以及对树的各结点的赋值实现Huffman编码。虽然自己最后没有独立的把整个过程实现，而是查阅了相关资料，但是，如果遇到需要编码的地方，我完全可以在Matlab里面用Huffman函数来实现编码，同样达到目的。

本文来源：https://www.bwwdw.com/article/ms7p.html