香农编码基于C++语言的实现.doc
《香农编码基于C++语言的实现.doc》由会员分享，可在线阅读，更多相关《香农编码基于C++语言的实现.doc（12页珍藏版）》请在冰点文库上搜索。
香农编码基于C++语言的实现
摘要：
1948年，美国工程师香农在贝尔实验室杂志上发表了长文《通讯的数学原理》，他用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论，并由此奠定了现代信息论的基础。
香农编码将信源编码后所得的二进制代码。
编码是指为了达到某种目的而对信号进行的一种变换。
根据编码的目的不同，编码理论有三个分支：
①信源编码。
对信源输出的信号进行变换，包括连续信号的离散化，即将模拟信号通过采样和量化变成数字信号,以及对数据进行压缩,提高数字信号传输的有效性而进行的编码。
②信道编码。
对信源编码器输出的信号进行再变换，包括区分通路、适应信道条件和提高通信可靠性而进行的编码。
③保密编码。
对信道编码器输出的信号进行再变换，即为了使信息在传输过程中不易被人窃取而进行的编码。
本文介绍香农编码的编码过程和C++语言代码实现。
Abstract:
in1948,AmericanEngineerShannonintheBaerlabmagazinepublishedthearticle"themathematicaltheoryofcommunication",hismethodofprobabilityandmathematicalstatisticssystematicallydiscussedthebasicproblemsofthecommunication,obtainedseveralimportantanduniversalconclusions,andthuslaidthefoundationofmoderninformationtheory.TheShannoncodeintothebinarycodeobtainedaftersourcecoding.Codingreferstoatransformationinordertoachieveacertainpurposeandthesignal.Accordingtothecodefordifferentpurposes,thecodetheoryhasthreebranches:
sourcecode.Thesignalsourcetotransformtheoutput,includingthecontinuoussignaldiscretization,theanalogsignalintodigitalsignalthroughthesamplingandquantization,andcompressingthedata,toimprovethevalidityofthedigitalsignaltransmissionandcoding.Thechannelcoding.Thesourcecoderoutputsignaltotransform,includingdistinguishingpathways,adaptingtothechannelconditionsandimprovethereliabilityofcommunicationandcoding.Thesecretcode.Signalontheoutputofthechannelencodertotransform,namely,inordertomaketheinformationinthetransmissionprocessisnoteasytobestolenandcoding.ThispaperintroducedtheShannoncodeencodingprocessandClanguagecodetoachieve.
关键词：
累加概率、排序、熵、码长、二元码
1香农编码原理
1.1信源编码器
将信源符号序列按一定的数学规律映射成码符号的过程称为信源编码，完成编码功能的器件，称为编码器。
接受端有一个译码器完成相反的功能。
图1-1信源编码模型。
信源编码器
图1 1
信源编码器的输入是信源符号集,共有q个信源符号。
同时存在另一个符号集，称为码符号集，共有r个码符号，码符号集中的元素称为码元或者码符号。
编辑器输出的符号序列称为码。
信源符号对应，须用个码符号来表示，称为码字长度，简称码长。
能够获得最佳编码的方法主要有：
香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。
1.2码的分类
1.分组码和非分组码
将信源符号集中的每个信源符号固定的映射成一个码字，这样的码成为分组码，又称为块码。
与分组码对应的分类是非分组码，又称树码。
2.奇异码和非奇异码
若一种分组码种的所有码字都不相同，则称此分组码为非奇异码，否则称为奇异码。
3.唯一可译码和非唯一可译码
任意有限长的码元序列，只能够唯一地分割成一个个码字，便称为唯一可译码。
4.即时码和非即时码
无需考虑后续码符号就可以从码符号序列译出码字，这样的唯一可译码称为即时码。
一个唯一可译码称为即时码的充分必要条件是其中任何一个码字都不是其他码字的前缀。
综上所述，可将码作如下分类：
码
非分组码
分组码
奇异码
非奇异码
非唯一可译码
唯一可译码
非即时码
即时码
图1 2
1.3香农第一定理
设离散无记忆信源S的信源熵，它的N次扩展信源，其熵。
并用码符号对信源进行变长编码，那么总可以找到一种唯一的可译，使每个信源符号所需的平均码长满足
公式1
或者写成
公式2
式中，，其中是扩展信源的信源符号所对应的码字长度，因此是扩展信源的信源符号的平均码长。
平均码长满足
公式3
即公式4
1.4香农编码步骤
香农第一定理指出了平均码长与信源熵之间的关系，同时也指出了可以通过编码使码长达到极限值。
香农编码的方法是选择每个码长长度，满足
公式5
香农编码的具体如下：
（1）将所有q个信源符号按其概率的递减次序排列。
（2）按下式依次计算每个信源符号的二元码码长。
公式6
（3）计算每个信源符号的累加概率，并变换成二进制小数得到其码字。
累加概率
公式7
（4）将累加概率变换成二进制小数，取小数点后位数作为第i个信源符号的码字。
1.5香农编码的不足
通过对香农码的编码算法进行分析研究，可以发现在香农编码过程中，由于先限定每个码字的码长，以至于在码字的选取中是以每个码字的码长作为先决条件而没有考虑各个码字之间的相关性，因此编出的码字往往存在较大的冗余，比如其中某个码字原本可以编为1111，但由于根据香农编码规则该码字的先定码长为7，于是该码字的码长必须为7.很显然由于码长先决条件的限制，而使得整个码字的平均码长变大，无形中降低了编码效率，增加了通信过程中的冗余，使得通信系统的有效性这一重要指标的提高得到了很大限制。
1.6香农编码的优化
在编码过程中，忽略每个码字该有的码长限定，只需要根据最小概率计算出最小概率所对应的码长Z，将该码长作为参考值计算出所有累加概率所对应的二进制串，所有二进制串的长度均为Z，然后从每个长为Z的二进制串中选择最后的码字，其原则是任意一个码字一定不是前后备用码的前缀同时码字的选择必须要从二进制串的最左端开始，从左往右依次
选取。
根据该优化原理，具体过程可以描述如下:
1）将信源发出的y符号按其概率递减顺序进行排列
公式8
2）计算概率最小符号的对数值，其中
公式9
3）计算出第i个符号的累加概率
4）将每个符号所对应的累加概率变换成二进制小数，取小数后面的l位作为备用码。
5）从概率最大的符号所对应的备用码开始，采用比较方法选取该符号所对应的码字，原则为:
码字的选取从备用码的第一个二进制位开始从前往后依次选取，选取的码字不能是前后备用码的前缀，每个码字的选取尽可能短。
2香农编码实例
按照香农编码步骤，对一个有7个信源符号的信源编码。
例如当i=4时，先求第4个信源符号的二元码的码长：
公式10
因此码长取为3。
表格2-1
信源符号
概率
累加概率
码长
二元码
S1
0.20
0
2.34
3
000
S2
0.19
0.2
2.41
3
001
S3
0.18
0.39
2.48
3
011
S4
0.17
0.57
2.56
3
100
S5
0.15
0.74
2.74
3
101
S6
0.10
0.59
3.34
4
1110
S7
0.01
0.99
6.66
7
1111110
再计算累加概率：
公式11
将累加概率变成二进制小数：
公式12
即
公式13
根据码长取小数点后三位作为第四个信源符号的二元码，即“100”。
其他的信源符号编码可依次求得。
由表2-1可以看出，一共5个三位的二元码，个码字至少有以为码符号不同。
这个码就是唯一可译码，而且是即时码。
平均码长：
公式14
编码后的信息传输率：
公式15
3香农编码C++实现的算法介绍
3.1算法介绍
C++是一种使用非常广泛的计算机编程语言，是一种面向对象的程序设计语言。
它支持过程化程序设计、数据抽象、面向对象程序设计、泛型程序设计等多种程序设计风格。
利用C++语言的结构体知识可以对香农编码定义一个结构体（struckShannonCode），结构体种允许不同的数据类型成员。
能够结构化，层次清晰的对香农的编码过程中的概率排序、概率累加、求码长、求二元码等一系列的准确的代码呈现。
并且根据概率累加公式、码长公式、二元码算法等计算并输出相应的数据。
3.2程序功能介绍
程序主要有三个函数完成，分别是主函数（voidmian（））、输入函数（voidinput（））、输出函数（voidDisplay（））。
在程序开始定义：
头文件以及可输入的最大的信源个数，并且给出了香农编码结构体（structShannonCode）以数组的方式存储信息。
#include
#include
usingnamespacestd;
//定义可输入的最大的信源个数
#defineMAX100
//定义ShannonCode（香农编码）结构体
structShannonCode
{
doublex; //字符概率
doubley; //字符概率类加
intk; //码字长度
intcode; //第i个消息符号的码字
}x[MAX];
在输入信息概率是先确定输入的信源个数，然后再进行循环输入每个信源概率，在输入的过程中对所有信源累加求和，若和不等于1，将递归调用Input（）函数重新输入信源概率：
for（i=0;i {
cout<<"P（x"<";
cin>>a[i];
sum=sum+a[i];
}
if（sum!
=1）
{
cout<<"输入概率和是"< a[m]=NULL;
//若不满足概率和为1，递归调用概率输入函数
Input（）;
}
在VC中若输入的信源正确，那么程序将会在Display（）函数中执行相应的概率排序功能、概率累加功能、计算码长功能、计算二元码功能。
详细代码如表2。
表格2
//将概率由大到小排序
for（i=0;i {
max=i;
for（j=i+1;j {
if（x[i].x<=x[j].x）
max=j;
t=x[i].x;
x[i].x=x[max].x;
x[max].x=t;
}
}
//计算码长
for（i=0;i {
I=-log（x[i].x）/log
（2）;
if（I-（int）I==0）
{
x[i].k=（int）I;
}
else
x[i].k=（int）I+1;
}
//概率累加
for（i=0;i{
if（i!
=0）
{
p+=x[i-1].x;
x[i].y=p;
}
else
{
x[i].y=0;
}
}
//计算并输出二元码
floatt=x[i].y;
for（j=0;j {
t=t*2;
if（t>=1）
{
cout<<"1";
t=t-1;
}
else
{
cout<<"0";
}
}
3.3程序执行结果
4参考文献
[1]石峰，莫忠息.信息论基础.武汉：
武汉大学出版社，2006.
[2]李梅，李亦农.信息论基础教程.北京：
北京邮电大学出版社，2009.
[3]叶中行.信息论基础.北京：
高等教育出版社，2003.
[4]傅祖芸.信息论——基础理论与应用.北京：
点子工业出版社，2011.
[5]张燕红,刘瑜,孟海翠,刘晓娣.香农编码与香农-弗诺编码方法的研究及C#实现.电脑知识与技术,2013.
[6]邵军花,刘玉红,邸敬,周东梅.香农编码的优化算法研究[J].兰州交通大学学报,2010.
5附录
#include
#include
usingnamespacestd;
//定义可输入的最大的信源个数
#defineMAX100
//定义ShannonCode（香农编码）结构体
structShannonCode
{
doublex; //字符概率
doubley; //字符概率类加
intk; //码字长度
intcode; //第i个消息符号的码字
}x[MAX];
/*信源概率排序、概率累加、求码长、求二元
码、并且以表格的形式输出相关数据信息*/
voidDisplay（doublea[],intn）
{
inti,j,max;
doubleI=0,t,p=0;
for（i=0;i {
x[i].x=a[i];
}
//将概率由大到小排序
for（i=0;i {
max=i;
for（j=i+1;j {
if（x[i].x<=x[j].x）
max=j;
t=x[i].x;
x[i].x=x[max].x;
x[max].x=t;
}
}
//计算码长
for（i=0;i {
I=-log（x[i].x）/log
（2）;
if（I-（int）I==0）
{
x[i].k=（int）I;
}
else
x[i].k=（int）I+1;
}
cout< cout<<"信源符号xi"<<"\t概率p（xi）"<<"\t累加概率"<<"\t码字长度"<<"\t二元码"< for（i=0;i {
//概率累加
if（i!
=0）
{
p+=x[i-1].x;
x[i].y=p;
}
else
{
x[i].y=0;
}
cout<<""<<"S"<
//计算并输出二元码
floatt=x[i].y;
for（j=0;j {
t=t*2;
if（t>=1）
{
cout<<"1";
t=t-1;
}
else
{
cout<<"0";
}
}
cout< }
cout<}
//数据输入函数
voidInput（）
{
inti,m;
doublesum=0;
doublea[MAX];
cout<<"输入信源个数:
";
cin>>m;
cout<<"输入"<"< for（i=0;i {
cout<<"P（x"<";
cin>>a[i];
sum=sum+a[i];
}
if（sum!
=1）
{
cout<<"输入概率和是"< a[m]=NULL;
//若不满足概率和为1，递归调用概率输入函数
Input（）;
}
//输出相关信息
elseDisplay（a,m）;
}
//主函数
voidmain（）
{
Input（）;
}
12/12
升级会员 