离散信源无失真信源编码

《离散信源无失真信源编码》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、离散信源无失真信源编码目的：熟练掌握无失真信源编码的方法；熟练掌握Huffman编码的平均码长和编码效率的Huffman编码的基本原理及特点：Huffman编码是一种可变长编码算法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。Huffman编码一般利用二叉树结构实现，其基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。Huffman编码在信源符号表示平均所需要的比特数方面是最优的，而且也满足前缀条件（即唯一可译码）。在编码效率方面，Huffman编

2、码是基于二叉树算法的特点以及性质。从书本的例题看出Huffman编码方法得到的码是不唯一的。不同的排序准则以及不同的符号分配都会影响到最后的结果，虽然编码的效率相同，但是影响到了编码的质量。从课本上的例题可以看出，二叉树的层数较少的，编码质量较高（从码方差得出）。在编码的时候，要尽量避免二叉树的稀疏性给编码质量带来的影响。要减少二叉树的稀疏性就要提高二叉树的利用率，减少二叉树的层数。Huffman编码基本步骤，画出程序流程图：Huffman编码步骤：（1）将信源符号按概率递减的次序排序（2）将两个最小概率的分支分别标记为‘1’和‘

3、0’，他们的结合点为两分支概率之和（3）将上面的概率和看作一个新符号的概率。（4）重新排列后，重复上面的步骤。（5）从最后的节点开始读取，到要找的符号，路径的分支标号就是码字流程图：利用二叉树原理建一个数组，并加上相应的编码序号提取出Huffman树的编码信息并且输出数据输入并且判断是否符合要求数据排序Huffman树构建源程序：clearall;clc;p=1;place=1;total=0;require='youcaninputthemaxprobability:';disp('readme:whenprobabilityi

4、s-1endinput.');disp('inputprobabilitymustlessthan1,andthetotalprobabilityalsolessthan1');disp('wewillpointoutthemaxprobabilityyoucaninput');%%%inputdatawhile(1)q=num2str(p);r=strcat(require,q);disp(r);temp=input('probably=');if((temp-p)>5e-010)disp('inputprobablyisove

5、rflow,inputagain');endif(temp==-1)if(p==0)break;elsedisp('thetotalprobabilityisnotenough,doyouexit?');if(input('(y/n)','s')=='y')break;endendendif(temp<=(p+5e-010)&&temp>=5e-010)node(place).prob=temp;node(place).signal=input('signal=');p=p-temp;place=place+1;total=tot

6、al+1;if(p<5e-09)disp('enoughdata');break;endendend%%%p-pdatasort,smalltobigif(total==0)warning('youhavetoinputmorethanonedata!');elseif(total==1)disp('-__-

7、

8、

9、codeis1,soeasy.');elsefori=1:totalforj=i:totalif(node(i).prob>node(j).prob)tempn=node(i).prob;node(i).prob=nod

10、e(j).prob;node(j).prob=tempn;tempn=node(i).signal;node(i).signal=node(j).signal;node(j).signal=tempn;endendend%nodesortisright%%%huffmantree,probabilitybigis0,whenequal,deeplyis0temp2(1:total)=node(1:total);fori=1:totaltemp2(i).deep=1;temp2(i).pre=-1;end%createatreefo

11、ri=1:total*2-1tree(i).signal=-1;tree(i).prob=-1;tree(i).pre=-1;tree(i).deep=1;tree(i).code=-1;tree(i).next.right=-1;tree(i).