香农编码基于C++语言的实现

1/12香农编码基于C++语言的实现摘要：1948年，美国工程师香农在贝尔实验室杂志上发表了长文《通讯的数学原理》，他用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论，并由此奠定了现代信息论的基础。香农编码将信源编码后所得的二进制代码。编码是指为了达到某种目的而对信号进行的一种变换。根据编码的目的不同，编码理论有三个分支：①信源编码。对信源输出的信号进行变换，包括连续信号的离散化，即将模拟信号通过采样和量化变成数字信号,以及对数据进行压缩,提高数字信号传输的有效性而进行的编码。②信道编码。对信源编码器输出的信号进行再变换，包括区分通路、适应信道条件和提高通信可靠性而进行的编码。③保密编码。对信道编码器输出的信号进行再变换，即为了使信息在传输过程中不易被人窃取而进行的编码。本文介绍香农编码的编码过程和C++语言代码实现。Abstract:in1948,AmericanEngineerShannonintheBaerlabmagazinepublishedthearticlethemathematicaltheoryofcommunication,hismethodofprobabilityandmathematicalstatisticssystematicallydiscussedthebasicproblemsofthecommunication,obtainedseveralimportantanduniversalconclusions,andthuslaidthefoundationofmoderninformationtheory.TheShannoncodeintothebinarycodeobtainedaftersourcecoding.Codingreferstoatransformationinordertoachieveacertainpurposeandthesignal.Accordingtothecodefordifferentpurposes,thecodetheoryhasthreebranches:sourcecode.Thesignalsourcetotransformtheoutput,includingthecontinuoussignaldiscretization,theanalogsignalintodigitalsignalthroughthesamplingandquantization,andcompressingthedata,toimprovethevalidityofthedigitalsignaltransmissionandcoding.Thechannelcoding.Thesourcecoderoutputsignaltotransform,includingdistinguishingpathways,adaptingtothechannelconditionsandimprovethereliabilityofcommunicationandcoding.Thesecretcode.Signalontheoutputofthechannelencodertotransform,namely,inordertomaketheinformationinthetransmissionprocessisnoteasytobestolenandcoding.ThispaperintroducedtheShannoncodeencodingprocessandClanguagecodetoachieve.关键词：累加概率、排序、熵、码长、二元码2/121香农编码原理1.1信源编码器将信源符号序列按一定的数学规律映射成码符号的过程称为信源编码，完成编码功能的器件，称为编码器。接受端有一个译码器完成相反的功能。图1-1信源编码模型。}s,,s,{sSqs1},,{21q}x,x,{xXr2,1图1-1信源编码器的输入是信源符号集}s,,s,{sSqs1,共有q个信源符号。同时存在另一个符号集，称为码符号集}x,x,{xXr2,1，共有r个码符号，码符号集中的元素称为码元或者码符号。编辑器输出的符号序列},,{21q称为码。信源符号is对应iw，须用il个码符号来表示，il称为码字长度，简称码长。能够获得最佳编码的方法主要有：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。1.2码的分类1.分组码和非分组码将信源符号集中的每个信源符号is固定的映射成一个码字iw，这样的码成为分组码，又称为块码。与分组码对应的分类是非分组码，又称树码。2.奇异码和非奇异码若一种分组码种的所有码字都不相同，则称此分组码为非奇异码，否则称为奇异码。3.唯一可译码和非唯一可译码任意有限长的码元序列，只能够唯一地分割成一个个码字，便称为唯一可译码。4.即时码和非即时码无需考虑后续码符号就可以从码符号序列译出码字，这样的唯一可译码称为即时信源编码器3/12码。一个唯一可译码称为即时码的充分必要条件是其中任何一个码字都不是其他码字的前缀。综上所述，可将码作如下分类：图1-21.3香农第一定理设离散无记忆信源S的信源熵)(SH，它的N次扩展信源}s,s,{sSqN21N，其熵)(NSH。并用码符号}x,x,{xXr2,1对信源NS进行变长编码，那么总可以找到一种唯一的可译，使每个信源符号所需的平均码长NLN满足NrSHNLrSHN1log)(log)(公式1或者写成NSHNLSHrNr1)()(公式2式中，NqiiNispL1)(，其中i是扩展信源的信源符号is所对应的码字长度，因此NL是扩展信源的信源符号的平均码长。平均码长NL满足1)()(NrNNrSHLSH公式3即)(log-1)(log-22iiixpKxp公式4码非分组码分组码奇异码非奇异码非唯一可译码唯一可译码非即时码即时码4/121.4香农编码步骤香农第一定理指出了平均码长与信源熵之间的关系，同时也指出了可以通过编码使码长达到极限值。香农编码的方法是选择每个码长长度il，满足qisplii,2,1)(1log公式5香农编码的具体如下：（1）将所有q个信源符号按其概率的递减次序排列。)()()(21qspspsp（2）按下式依次计算每个信源符号的二元码码长il。qisplii,2,1)(1log公式6（3）计算每个信源符号的累加概率)(isF，并变换成二进制小数得到其码字。累加概率qispsFikki,,2,1)(）(11公式7（4）将累加概率)(isF变换成二进制小数，取小数点后il位数作为第i个信源符号的码字。1.5香农编码的不足通过对香农码的编码算法进行分析研究，可以发现在香农编码过程中，由于先限定每个码字的码长，以至于在码字的选取中是以每个码字的码长作为先决条件而没有考虑各个码字之间的相关性，因此编出的码字往往存在较大的冗余，比如其中某个码字原本可以编为1111，但由于根据香农编码规则该码字的先定码长为7，于是该码字的码长必须为7.很显然由于码长先决条件的限制，而使得整个码字的平均码长变大，无形中降低了编码效率，增加了通信过程中的冗余，使得通信系统的有效性这一重要指标的提高得到了很大限制。5/121.6香农编码的优化在编码过程中，忽略每个码字该有的码长限定，只需要根据最小概率计算出最小概率所对应的码长Z，将该码长作为参考值计算出所有累加概率所对应的二进制串，所有二进制串的长度均为Z，然后从每个长为Z的二进制串中选择最后的码字，其原则是任意一个码字一定不是前后备用码的前缀同时码字的选择必须要从二进制串的最左端开始，从左往右依次选取。根据该优化原理，具体过程可以描述如下:1)将信源发出的y符号按其概率递减顺序进行排列)()()(21qspspsp公式82)计算概率最小符号的对数值)(lognxpl，其中)}(,),(),(min{)(21qnxpxpxpxp公式93)计算出第i个符号的累加概率qixpxFikki,,2,1)(）(114)将每个符号所对应的累加概率变换成二进制小数，取小数后面的l位作为备用码。5)从概率最大的符号所对应的备用码开始，采用比较方法选取该符号所对应的码字，原则为:码字的选取从备用码的第一个二进制位开始从前往后依次选取，选取的码字不能是前后备用码的前缀，每个码字的选取尽可能短。2香农编码实例按照香农编码步骤，对一个有7个信源符号的信源编码。例如当i=4时，先求第4个信源符号的二元码的码长4l：3)(log44spl公式10因此码长取为3。表格2-1信源符号is概率)(isp累加概率)(isF)(log-isp码长il二元码S10.2002.343000S20.190.22.413001S30.180.392.4830116/12S40.170.572.563100S50.150.742.743101S60.100.593.3441110S70.010.996.6671111110再计算累加概率：57.0)()()()()(3314spspspspsFkk公式11将累加概率)(4sF变成二进制小数：432104212020212057.0)(sF公式12即2104）1001.0（）57.0（)(sF公式13根据码长3)(log44spl取小数点后三位作为第四个信源符号的二元码，即“100”。其他的信源符号编码可依次求得。由表2-1可以看出，一共5个三位的二元码，个码字至少有以为码符号不同。这个码就是唯一可译码，而且是即时码。平均码长：信源符号/码符号14.3)(71iiilspL公式14编码后的信息传输率：码符号/比特831.014.361.2)(LSHR公式153香农编码C++实现的算法介绍3.1算法介绍C++是一种使用非常广泛的计算机编程语言，是一种面向对象的程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、泛型程序设计等多种程序设计风格。利用C++语言的结构体知识可以对香农编码定义一个结构体（struckShannonCode），结构体种允许不同的数据类型成员。能够结构化，层次清晰的对香农的编码过程中的概率排序、概率累7/12加、求码长、求二元码等一系列的准确的代码呈现。并且根据概率累加公式、码长公式、二元码算法等计算并输出相应的数据。3.2程序功能介绍程序主要有三个函数完成，分别是主函数（voidmian（））、输入函数（voidinput（））、输出函数（voidDisplay（））。在程序开始定义：头文件以及可输入的最大的信源个数，并且给出了香农编码结构体（structShannonCode）以数组的方式存储信息。#includeiostream#includemath.husingnamespacestd;//定义可输入的最大的信源个数#defineMAX100//定义ShannonCode（香农编码）结构体structShannonCode{doublex;//字符概率doubley;//字符概率类加intk;//码字长度intcode;//第i个消息符号的码字}x[MAX];在输入信息概率是先确定输入的信源个数，然后再进行循环输入每个信源概率，在输入的过程中对所有信源累加求和，若和不等于1，将递归调用Input（）函数重新输入信源概率：for(i=0;im;i++)8/12{coutP(xi+1):;cina[i];sum=sum+a[i];}if(sum!=1){cout输入概率和是sum不为1，请重输;a[m]=NULL;//若不满足概率和为1，递归调用概率输入函数Input();}在VC中若输入的信源正确，那么程