《【2017年整理】霍夫曼编码的matlab实现》由会员分享，可在线阅读，更多相关《【2017年整理】霍夫曼编码的matlab实现（6页珍藏版）》请在金锄头文库上搜索。
1、霍夫曼编码的 matlab 实现一、实验内容：用 Matlab 语言编程实现霍夫曼（Huffman）编码。二、实验原理及编码思想：霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源符号集合中，首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。这样就得到了一张树图，从树根开始，将编码符号1 和0 分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树根到树叶途经支路上的编码最后就构成了一组异前
2、置码，就是霍夫曼编码输出。以本教材P36例题3-2信源为例：离散无记忆信源：U u1 u2 u3 u4 u5P(U) = 0.4 0.2 0.2 0.1 0.1 解：编码过程码字W i信符si概率P(si)第一次 第二次 第三次W1=0W2=10W3=111W4=1101W5=1100S1S2S3S4S50.40.20.20.10.10.40.20.21 0.200.40.410.200.61 0.401 A(1)0通过上表的对信源缩减合并过程，从而完成了对信源的霍夫曼编码。三、程序设计思路分为两步，首先是码树形成过程：对信源概率进行合并形成编码码树。然后是码树回溯过程：在码树上分配编码码字并
3、最终得到霍夫曼编码。1、码树形成过程：将信源概率按照从小到大顺序排序并建立相应的位置索引。然后按上述规则进行信源合并，再对信源进行排序并建立新的位置索引，直到合并结束。在这一过程中每一次都把排序后的信源概率存入矩阵G中，位置索引存入矩阵Index中。这样，由排序之后的概率矩阵 G以及索引矩阵Index就可以恢复原概率矩阵P了，从而保证了回溯过程能够进行下去。2、码树回溯过程：在码树上分配编码码字并最终得到Huffman 编码。从索引矩阵M 的末行开始回溯。(1) 在 Index 的末行2元素位置填入0和1。(2) 根据该行索引1 位置指示，将索引1 位置的编码（1）填入上一行的第一、第二元素位
4、置，并在它们之后分别添加0和1。(3) 将索引不为1的位置的编码值（0）填入上一行的相应位置（第3 列）。(4) 以 Index的倒数第二行开始向上，重复步骤(1) (3) ，直到计算至Index的首行为止。四、程序代码：%取得信源概率矩阵,并进行合法性判断clear;P=input(请输入信源概率向量P=);N=length(P);for component=1:1:Nif(P(component)0.0001)error(信源概率之和必须为1);end%建立各概率符号的位置索引矩阵Index,利于编码后从树根进行回溯,从而得出对应的编码Q=PIndex=zeros(N-1,N); %初始化
5、Index for i=1:N-1 Q,L=sort(Q); Index(i,:)=L(1:N-i+1),zeros(1,i-1);G(i,:)=Q;Q=Q(1)+Q(2),Q(3:N),1; %将Q中概率最小的两个元素合并，元素不足的地方补1end%根据以上建立的Index矩阵，进行回溯，获取信源编码for i=1:N-1Char(i,:)=blanks(N*N);%初始化一个由空格符组成的字符矩阵N*N,用于存放编码end%从码树的树根向树叶回溯，即从G矩阵的最后一行按与Index中的索引位置的对应关系向其第一行进行编码Char(N-1,N)=0;%G中的N-1行即最后一行第一个元素赋为0
6、，存到Char中N-1行的N列位置Char(N-1,2*N)=1;%G中的N-1行即最后一行第二个元素赋为1，存到Char中N-1行的2*N列位置%以下从G的倒数第二行开始向前编码for i=2:N-1 Char(N-i,1:N-1)=Char(N-i+1,N*(find(Index(N-i+1,:)=1) -(N-2):N*(find(Index(N-i+1,:)=1); %将Index后一行中索引为1的编码码字填入到当前行的第一个编码位置Char(N-i,N)=0; %然后在当前行的第一个编码位置末尾填入0 Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); %将G后
7、一行中索引为1的编码码字填入到当前行的第二个编码位置 Char(N-i,2*N)=1; %然后在当前行的第二个编码位置末尾填入1for j=1:i-1 %内循环作用：将Index后一行中索引不为1处的编码按照左右顺序填入当前行的第3个位置开始的地方,最后计算到Index的首行为止Char(N-i,(j+1)*N+1:(j+2)*N)=Char(N-i+1,N*(find(Index(N-i+1,:)=j+1)-1)+1:N*find(Index(N-i+1,:)=j+1); end end %Char中第一行的编码结果就是所需的Huffman 编码输出，通过Index中第一行索引将编码对应到相
8、应概率的信源符号上。for i=1:N Result(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N);end %打印编码结果String=信源概率及其对应的Huffman编码如下;disp(String);disp(P);disp(Result);五、运行结果：以例题3-2信源0.4 0.2 0.2 0.1 0.1为例：运行：HuffmanEncode结果：信源概率及其对应的Huffman编码如下0.4000 0.2000 0.2000 0.1000 0.10000 111 10 1100 1101可知，程序已完成了Huffman编码的功能，但与书中的结果不一致，验证了霍夫曼编码是不唯一的.因为：信源符号合并中遇到最小概率相同的情况时可任意选择来做合并；在码树分配编码码字的时候1 和0 的位置可以是任意的。
