香农编码
香农编码
概念：
香农编码是是采用信源符号的累计概率分布函数来分配字码的。香农编码是根据香农第一定理直接得出的，指出了平均码长与信息之间的关系，同时也指出了可以通过编码使平均码长达到极限值。香农第一定理是将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽量少的码符号传输信源信息。
香农编码属于不等长编码，通常将经常出现的消息变成短码，不经常出现的消息编成长码，从而提高通信效率。 香农编码严格意义上来说不是最佳码，它是采用信源符号的累计概率分布函数来分配码字。
编码步骤如下：
(1)将信源符号按概率从大到小顺序排列。
(2)计算第i个符号对应的码字的码长(取整)；
(3) 计算第i个符号的累加概率 ；
(4)将累加概率变换成二进制小数，取小数点后 位数作为第i个符号的码字。
可以看出，编码所得的码字，没有相同的，所以是非奇异码，也没有一个码字是其他码字的前缀，所以是即时码，也是唯一可译码。
特点：
香农编码的效率不高，实用性不大，但对其他编码方法有很好的理论指导意义。一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。
香农编码
1.根据步骤截取核心代码：
将信源符号按概率从大到小顺序排列
计算符号的累加概率，取小数点后特定位数作为第i个符号的码字
将累加概率变换成二进制小数
2.验证编码效率是100%的情况（0.5,0.25,0.125,0.125）
3.事例1（0.25,0.25,0.2,0.15,0.1,0.05）
4.事例2（0.20，0.19,0.18,0.17,0.15,0.10,0.01）做对比(平均码长，编码效率)
代码：
#include iostream
#include cstdlib
#include ctime
#include ctype.h
#include vector
#include math.h
#include iomanip
#include graphics.h
#include conio.h
#include windows.h
#include fstream
#include string
using namespace std;
struct Node
{
int num;
double p,pa;
int L;
int x[100];
};
Node box[20];
int M;
double H,L,K;
int exit1,exit2;
void draw()
{
int i,j,k,posx,posy;
cleardevice();
setlinecolor(BLACK);
settextcolor(BLACK);
for(i=1;i=M;i++){
posx=10;
posy=M*50;
k=50;
for(j=0;jbox[i].L;j++){
if(box[i].x[j]==1){
line(posx,posy,posx+k,posy-k);
outtextxy(posx+k/2,posy-k/2+2, _T(1));
posx+=k;
posy-=k;
}
else{
line(posx,posy,posx+k,posy);
outtextxy(posx+k/2-4,posy+1, _T(0));
posx+=k;
}
k/=1.05;
}
}
}
void initialization()
{
int i,j,k;
initgraph(501,550,SHOWCONSOLE);
setbkcolor(WHITE);
cleardevice();
M=6;
box[0].p=0;
box[1].p=0.25;
box[2].p=0.25;
box[3].p=0.20;
box[4].p=0.15;
box[5].p=0.1;
box[6].p=0.05;
}
void carry()
{
int i,j,k;
initialization();
exit1=0;
while(exit1==0){
for(i=0;i=M;i++){
box[i].pa=0;
}
for(i=1;i=M;i++){
box[i].pa=box[i-1].pa+box[i-1].p;
box[i].L=0;
while(box[i].L-(log(box[i].p)/log(2))){
box[i].L++;
}
}
H=0;
for(i=1;i=M;i++){
H-=box[i].p*log(box[i].p)/log(2);
}
L=0;
for(i=1;i=M;i++){
L+=box[i].p*box[i].L;
}
K=0;
for(i=1;i=M;i++){
K+=pow(0.5,box[i].L);
}
for(i=1;i=M;i++){
cout编号xi;
cout 概率box[i].p;
cout 码长box[i].L;
cout 码字;
for(j=0;jbox[i].L;j++){
box[i].pa*=2;
if(box[i].pa=1){
box[i].x[j]=1;
box[i].pa-=1;
}
else{
box[i].x[j]=0;
}
coutbox[i].x[j];
}
coutendl;
}
cout熵:Hendl;
cout平均码长Lendl;
cout编码效率H/L*100.0%endl;
cout克拉夫特值Kendl;
if(K=1)cout唯一可译码endl;
else cout非唯一可译码endl;
draw();
coutendl按任意键继续;
_getch();
system(cls);
cout请输入码数(3-10):endl;
M=0;
while(M3||M10){
cinM;
}
cout码数:Mendl;
for(i=1;i=M;i++){
cout请输入第i个码数的概率(0-1)(不必排序):endl;
box[i].p=0;
while(box[i].p=0||box[i].p=1){
cinbox[i].p;
}
}
for(i=0;iM;i++){
for(j=1;jM-i;j++){
if(box[j].pbox[j+1].p){
box[11].p=box[j+1].p;
box[j+1].p=box[j].p;
box[j].p=box[11].p;
}
}
}
system(cls);
}
}
int main()
{
carry();
}
演示视频：
接下来这些是信息论的大作业，三种无失真编码，只编了二元码，我要稍微详细说说过程，一般编之前肯定是找算法，概念，再在纸上像大纲一样从头到尾列出实现的或详或略的代码。
香农编码作为最简单的是可以根据老师ppt给的算法直接完成的，包括：概率排序，累加概率，由概率算码字长度，由累加概率编码即可，清晰明白。
如果编多（m）元码，我猜测，由概率算码字长度这一步要将log2为底改成logm为底，由累加概率编码这一步要将乘2取整再剪整数部分改为乘m取整再剪整数部分。
算术编码作为限失真编码，我感觉很像香农编码，如果符号序列因为各种原因未出现某符号，两者才会有区别。
ppt:
以上就是（香农编码）全部内容，收藏起来下次访问不迷路！