信息预编码论文教材

PAGEPAGE14目录中文摘要（小4号宋体）…………1Abstract………………2引言（或绪论）………………………31准备工作…………41.1符号说明…………41.2理论准备及举例………………42香农编码…………………52.1编码说明…………………52.2编码步骤…………………52．3．1二元编码结果……………62.3.2matlab说明及验证…………63Fano编码……………………83.1编码说明…………………83.2编码步骤…………………83．3．1编码结果……………83.3.2matlab说明及验证…………94Huffman编码……………………104.1编码说明…………………104.2编码步骤…………………104．3．1编码结果……………………114.3.2matlab说明及验证…………114.4三进制编码………125总结比较…………13参考文献……………14附录1…………………15附录2………16附录2………18霍夫曼码的优化比较信息与计算科学1001李翠珍指导教师吴慧摘要信息通过信道传输到信宿的过程为通信。为了通信中快速，准确的传输信息，在允许一定失真的条件下，要提高信息传输速度，就要进行合适的编码，编码分为等长码和变长码。由于等长码存在冗余度较大，所以出现了变长编码，变长编码中以香农编码，费诺编码，霍夫曼编码最为典型，以下通过举例就对这3中编码通过编码效率进行比较。首先根据相应算法算出不同编码算法对应的二进制码字，码长和编码效率。然后用matlab进行计算验证。进行比较及查阅资料得出三种编码中huffman编码最优，然后判断是多进制的huffman编码效率是否提高，从而进行三种编码的总结性比较。关键字：Matlab效率编码Shannon,Fano,hoffmancodeoptimizationAbstract：Informationtransmittedthroughthechanneltothecommunicationprocessofthesink.Toensurecommunicationinfast,accuratetransmissionofinformationinallowingcertaindistortionconditions,toincreasethespeedofinformationtransmission,itisnecessaryforappropriateencoding,encodingisdividedintoequal-lengthcodeandthevariable-lengthcode.Becausethereissuchalongcoderedundancyislarge,sothereareavariable-lengthcoding,variablelengthencodingtoShannoncoding,Fennocoding,Huffmancodingismosttypical,thefollowingbywayofexampleinrespectofthesethreecodingefficiencybyencodingcomparison.First,accordingtotheappropriatealgorithmtocalculatedifferentencodingalgorithmscorrespondingbinarycodeword,codelengthandcodingefficiency.Thencalculatedusingmatlabverified.Compareandaccesstoinformationobtainedinthethreecodinghuffmancodingbest,andthenjudgearyhuffmancodingefficiencyisimproved,therebyperformingasummarycomparisonofthreecoding.Keywords:matlabefficiencycode前言香农编码，费诺编码，霍夫曼编码为变长编码的三个代表。由于定长编码存在冗余度，所以1951年香农证明，当信源输出有冗余的消息时可通过编码改变信源的输出，使信息传输速率接近信道容量。1948年香农就提出能使信源与信道匹配的香农编码，1949年美国麻省理工学院的R.M.费诺提出费诺编码1952年，霍夫曼提出了一种构造最佳吗的方法，这是一种最佳逐个符号的编码方法。三种编码在一定程度上降低了冗余度。但他们在同等条件下的编码效率如何就是下面要考证的问题。在通过方法计算得到结果，随后用matlab进行验证。1准备工作1.1符号说明表1第i个信源符号第i个信源符号的概率第i个信源符号的码长信源熵平均码长编码效率rr进制1.2理论准备与举例编码理论有三个分支信源编码，信道编码，保密编码以下研究的为编码论中的变长编码中的三个典型代表：香农编码，费诺编码和霍夫曼编码，为了更好的解释这三种编码所需要的公式：信源熵（1）平均码长（2）编码效率（3）信源冗余度（4）我们通过课本的一个例子5.14来比较三种编码的编码效率信源符号X有6中字母，概率为0.32,0.22,0.18,0.16,0.08,0.04。（1）求符号的熵（2）定长二进制码，计算其编码效率（3）用香农编码法编成二进制变长码，计算其编码效率（4）用费诺编码编成二进制变长码，计算其编码效率（5）用霍夫曼编码编成二进制变长码，计算其编码效率（6）用霍夫曼编码编成三进制变长码，计算其编码效率首先对定长编码求编码效率对于定长二进制码满足，本题中r=2，n=6，所以L=3码符号/信源符号编码效率为2.香农编码2.1编码说明1951年香农证明，当信源输出有冗余的消息时可通过编码改变信源的输出，使信息传输速率接近信道容量。1948年香农就提出能使信源与信道匹配的香农编码。一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，也既不是最佳码。只有当信源符号的概率分布使不等式（5）左边的符号成立时，编码效率才能达到最高香农第一定理指出，可以选择每个码字的长度满足关系式（5）或2.2编码步骤信源符号按概率从大到小排列对信源符号求累加概率，表达式：Gi=Gi-1+p(xi)求自信息量，确定码字长度。自信息量I(xi)=-log(p(xi));码字长度取大于等于自信息量的最小整数。将累加概率用二进制表示，并取小数点后码字的长度的码。2.3.1编码结果根据香农编码步骤得到表2表2信源符号概率累加概率二进制码长码字0.3200.00001.642000.220.320.01012.1830100.180.540.10002.4731000.160.720.10112.6431010.080.880.11103.64411100.040.960.111104.6451110平均码长编码效率2.3.2matlab说明及验证用matlab验证的到结果如下程序见附录1程序说明及结果分析程序中输入信源。首先利用sort语句进行从小到大排序，然后利用fliplr进行矩阵左右交换得到信源概率从大到小的排序结果即y下对应的结果在信源概率排序完成后对计算累加概率和，判断概率和是否等于1，等于1进行以下程序，否则跳出程序。然后利用公式（5）求得相应的自信息量即程序结果里的I下的结果即；利用ceil语句向无穷取整的到L所对应的的码长。利用香农编码的乘2理论及码长得到码字的相关矩阵，矩阵中大于码长的列为空，得到相应码字。，at为编码效率。验证算的的码字和编码效率与程序结果一致。y=0.32000.22000.18000.16000.08000.0400pa=00.3200pa=00.32000.5400pa=00.32000.54000.7200pa=00.32000.54000.72000.8800pa=00.32000.54000.72000.88000.9600I=1.64392.18442.47392.64393.64394.6439L=233345c=[0][0][][][][0][1][0][][][1][0][0][][][1][0][1][][][1][1][1][0][][1][1][1][1][0]avlen=2.8400hx=2.3522at=0.82823Fano编码3.1fano编码说明1949年美国麻省理工学院的R.M.费诺提出费诺编码。费诺编码属于概率匹配编码，他一般不是最佳的编码方法，只有当信源的概率分布呈现分布形式的条件下，才能达到最佳吗的性能。费诺编码实际上是一种构造码树的方法所以费诺码是即时码；费诺码考虑了信源的统计特性，使概率大的信源符号对应较短码长的码字，从而有效提高了编码效率；费诺码不一定是最佳码。因为不一定能使短码得到充分利用。当信源符号较多时，若有一些符号概率分布接近，分两大组的组合的方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加降低编码效率。3.2编码的步骤信源符号以概率递减的次序排序；将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组赋予一个二元码符号0和1。将每一个大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，在分别赋予一个二元码符号。依次下去，直至每个小组只剩下一个信源符号为止。信源符号所对应的码字即为费诺码3.3.1编码结果表3信源概率第一次组第二次第三次第四次码字码长0.3200000020.2210120.18101020.16111030.081111040.04111114信源熵平均码长编码效率本列费诺码的平均码长比香农编码的平均码长小，编码效率较高。但不是最佳码。3.3.2matlab说明及验证（程序见附录2）首先利用sort语句进行从小到大排序，然后利用fliplr进行矩阵左右交换得到信源概率从大到小的排序结果即A下对应的结果，构造矩阵B,a=sum(B(:,1))/2;B的第一列为A的转置。当满足B的第一列满足abs(sum(B(1:k,1))-a)>abs(sum(B(1:k+1,1))-a)，进行前K行赋值0，在前k行有一行结束本行其他列为—1，其它为1，然后重复此步骤。构造符号矩阵END，其中当B中第一行取0或1时END中第一个符号去相应0,1组合。码字为利用程序[u,v]=size(char(END(i)));L(i)=v求得码长，avlen=sum(L.*A)求得平均码长为2.4码符号/信源符号hx=-(A*log2(A'))求得信源熵为2.352bit/symbolat=hx/avlen求得编码效率B=0.320000-1.0000-1.0000-1.00000.220001.0000-1.0000-1.0000-1.00000.18001.00000-1.0000-1.0000-1.00000.16001.00001.00000-1.0000-1.00000.08001.00001.00001.00000-1.00000.04001.00001.00001.00001.0000-1.0000A=0.32000.22000.18000.16000.08000.0400END=[00,01,10,110,1110,1111]avlen=2.4000L=222344hx=2.3522at=0.98014Huffman编码4.1编码说明1952年，霍夫曼提出了一种构造最佳吗的方法，这是一种最佳逐个符号的编码方法，就是霍夫曼编码。它是一种分组码，一种唯一可行码一种即使码。4.2编码步骤将信源符号按概率大小由大到小排序从概率最小的两个信源进行编码，最小的赋值1，其次赋值0.将已编码的两个信源符号合并，重新排序，编码。重复步骤（3）直到合并概率1为止。从概率等于1端沿合并路线逆行至对应消息进行编码。4.3.1编码结果表4码长码字符号概率2000.320.320.320.40.601280.3200.412210.28130100.160.1600.180401100.0800.121401110.041信源熵平均码长编码效率4.4.2matlab说明及验证（程序见附录3）程序的编写借用了课本7.5.1的程序。输入信源个数n，输入对应概率。信源符号概率累加和等于一且概率非负，程序进行，否则终止程序。然后利用sort语句信源符号按概率从小到大排列，构造矩阵m记录每次排序后概率次序。然后利用q=[q(1)+q(2),q(3:n),1]语句合并概率最小的两项，循环排序得到q。对最小的符号符号赋值0，次小的赋值1，循环下去，直至概率和为1.得到码字h。利用lengthLL(i)=length(find(abs(h(i,:))~=32))的到码长LL利用avlen=sum(L.*A)求得平均码长为2.4码符号/信源符号hx=-(A*log2(A'))求得信源熵为2.352bit/symbolat=hx/avlen求得编码效率与计算得到结果一致4.4q=0.04000.08000.16000.18000.22000.3200q=0.12000.16000.18000.22000.32001.0000q=0.18000.22000.28000.32001.00001.0000q=0.28000.32000.40001.00001.00001.0000q=0.40000.60001.00001.00001.00001.0000xx=2.4000y=0.32000.22000.18000.16000.08000.0400h=00101101001100111LL=222344hx=2.3522at=0.98014.4三进制编码计算huffman编码的三进制编码验证是否平均码长越短，编码效率越高码长码字符号概率1000.320.320.68012010.220.2800.3212020.180.22130000.160.18230010.08130020.042信源熵平均码长编码效率5．总结性的比较香农编码操作比较简单，但只有满足概率分布不等式（5）时编码效率才能达到最高，一般情况为三种变长编码中编码效率较低的一种。费诺编码属于概率匹配编码，编码性能略优于香农编码，但他一般不是最佳的编码方法，只有当信源的概率分布呈现分布形式的条件下，才能达到最佳码的性能。霍夫曼吗这是一种最佳逐个符号的编码方法，编码效率在同等编码进制情况下编码效率较高。参考文献[1]柳丽华，潘庆杰，沈伟，等.野猪与杜洛克、长白及其杂交后代群体的多态性分析.青岛农业大学学报，2008，25（2）：101-104.（5号宋体）[2]封海胜，万书波，张建成.试论我国花生品质及改良提高策略.花生学报，2003，32：30-33.[3]张海楼.不同肥料配施对复种花生生长和产量的影响.杂粮作物，2005，25(2)：111-112.[4]YaoJP,LiangYY,YangXD.ResearchonthefittingdosageandcooperateproportionofN,PandKinhighyieldpeanutfield.PeanutScienceandTechnology,1989,6(2)：18-21.（五号TimesNewRomar）[1]岩垂好裕,信息传输与编码理论，北京，科学出版社，2002.[2]/wikdoc/sp/qr/history/version.do?ver=7&hisiden=oW1lBVUVHBQ,AIR,11WWkBXRg附录附录1香农编码n=6;p=[0.320.220.180.160.080.04];fori=1:nendifsum(p)<1||sum(p)>1error('wrong')endy=fliplr(sort(p))pa=0;fori=2:npa(i)=pa(i-1)+y(i-1)endI=-log2(p)L=ceil(I)Z=(sort(L))fori=1:nt=pa(i);forj=1:Z(i)ifj>Z(i)c{i,j}='';elset=t*2;ift>=1t=t-1;c{i,j}=1;elsec{i,j}=0;endendendendcavlen=sum(L.*p)Lhx=-(p*log2(p'))at=hx/avlen附录2费诺编码A=[0.32,0.22,0.18,0.16,0.08,0.04];A=fliplr(sort(A));[m,n]=size(A);fori=1:nB(i,1)=A(i);enda=sum(B(:,1))/2;fork=1:n-1ifabs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1,1))-a)break;endendfori=1:nifi<=kB(i,2)=0;elseB(i,2)=1;endendEND=B(:,2)';END=sym(END);j=3;while(j~=0)p=1;while(p<=n)x=B(p,j-1);forq=p:nifx==-1break;elseifB(q,j-1)==xy=1;continue;elsey=0;break;endendendify==1q=q+1;endifq==p|q-p==1B(p,j)=-1;elseifq-p==2B(p,j)=0;END(p)=[char(END(p)),'0'];B(q-1,j)=1;END(q-1)=[char(END(q-1)),'1'];elsea=sum(B(p:q-1,1))/2;fork=p:q-2ifabs(sum(B(p:k,1))-a)<=abs(sum(B(p:k+1,1))-a);break;endendfori=p:q-1ifi<=kB(i,j)=0;END(i)=[char(END(i)),'0'];elseB(i,j)=1;END(i)=[char(END(i)),'1'];endend