香农编码--信息论大作业

信息论与编码课程大作业题目：香农编码学生姓名：******学号：&**********专业班级：*******************2013 年 5 月10 日香农编码1.香农编码的原理/步骤香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。

如何构造这种码？香农第一定理指出，选择每个码字的长度K i将满足式I(x i)≤K i＜I p(x i)+1就可以得到这种码。

这种编码方法就是香农编码。

香农编码步骤如下:(1)将信源消息符按从大到小的顺序排列。

(2)计算p[i]累加概率；(3)确定满足自身要求的整数码长；(4)将累加概率变为二进制数；(5)取P[i]二进制数的小数点后Ki位即为该消息符号的二进制码字。

2. 用C语言实现#include <stdio.h>#include <math.h>#include <stdlib.h>#define max_CL 10 /*maxsize of length of code*/#define max_PN 6 /*输入序列的个数*/typedef float datatype;typedef struct SHNODE {datatype pb; /*第i个消息符号出现的概率*/datatype p_sum; /*第i个消息符号累加概率*/int kl; /*第i个消息符号对应的码长*/int code[max_CL]; /*第i个消息符号的码字*/struct SHNODE *next;}shnolist;datatype sym_arry[max_PN]; /*序列的概率*/void pb_scan(); /*得到序列概率*/void pb_sort(); /*序列概率排序*/void valuelist(shnolist *L); /*计算累加概率，码长，码字*/void codedisp(shnolist *L);void pb_scan(){int i;datatype sum=0;printf("input %d possible!\n",max_PN);for(i=0;i<max_PN;i++){ printf(">>");scanf("%f",&sym_arry[i]);sum=sum+sym_arry[i];}/*判断序列的概率之和是否等于1，在实现这块模块时，scanf()对float数的缺陷，故只要满足0.99<sum<1.0001出现的误差是允许的*/if(sum>1.0001||sum<0.99){ printf("sum=%f,sum must (<0.999<sum<1.0001)",sum);pb_scan();}}/*选择法排序*/void pb_sort(){int i,j,pos;datatype max;for(i=0;i<max_PN-1;i++){max=sym_arry[i];pos=i;for(j=i+1;j<max_PN;j++)if(sym_arry[j]>max){max=sym_arry[j];pos=j;}sym_arry[pos]=sym_arry[i];sym_arry[i]=max;}}void codedisp(shnolist *L){int i,j;shnolist *p;datatype hx=0,KL=0; /*hx存放序列的熵的结果，KL存放序列编码后的平均码字的结果*/p=L->next;printf("num\tgailv\tsum\t-lb(p(ai))\tlenth\tcode\n");printf("\n");for(i=0;i<max_PN;i++){printf("a%d\t%1.3f\t%1.3f\t%f\t%d\t",i,p->pb,p->p_sum,-3.332*log10(p->pb),p ->kl);j=0;for(j=0;j<p->kl;j++)printf("%d",p->code[j]);printf("\n");hx=hx-p->pb*3.332*log10(p->pb); /*计算消息序列的熵*/KL=KL+p->kl*p->pb; /*计算平均码字*/p=p->next;}printf("H(x)=%f\tKL=%f\nR=%fbit/code",hx,KL,hx/KL); /*计算编码效率*/ }shnolist *setnull(){ shnolist *head;head=(shnolist *)malloc(sizeof(shnolist));head->next=NULL;return(head);}shnolist *my_creat(datatype a[],int n){shnolist *head,*p,*r;int i;head=setnull();r=head;for(i=0;i<n;i++){ p=(shnolist *)malloc(sizeof(shnolist));p->pb=a[i];p->next=NULL;r->next=p;r=p;}return(head);}void valuelist(shnolist *L){shnolist *head,*p;int j=0;int i;datatype temp,s;head=L;p=head->next;temp=0;while(j<max_PN){p->p_sum=temp;temp=temp+p->pb;p->kl=-3.322*log10(p->pb)+1;/*编码，*/{s=p->p_sum;for(i=0;i<p->kl;i++)p->code[i]=0;for(i=0;i<p->kl;i++){p->code[i]=2*s;if(2*s>=1)s=2*s-1;else if(2*s==0)break;else s=2*s;}}j++;p=p->next;}}int main(void){shnolist *head;pb_scan();pb_sort();head=my_creat(sym_arry,max_PN); valuelist(head);codedisp(head);}3.运行结果及分析（本程序先定义了码字长度的最大值和信源概率的个数，然后有设定了概率的和的范围。

实验报告课程名称：信息论与编码姓名：系：专业：年级：学号：指导教师：职称：年月日实验三 Shannon 编码一、实验目的1、熟悉离散信源的特点；2、学习仿真离散信源的方法3、学习离散信源平均信息量的计算方法4、熟悉 Matlab 编程二、实验原理给定某个信源符号的概率分布，通过以下的步骤进行香农编码 1、信源符号按概率从大到小排列；12.......n p p p ≥≥≥2、确定满足下列不等式的整数码长i K 为()()1i i i lb p K lb p -≤<-+3、为了编成唯一可译码，计算第i 个消息的累加概率：4、将累加概率i P 变换成二进制数；5、取i P 二进制数的小数点后i K 位即为该消息符号的二进制码字。

三、实验内容1、写出计算自信息量的Matlab 程序2、写出计算离散信源平均信息量的Matlab 程序。

3、将程序在计算机上仿真实现，验证程序的正确性并完成习题。

四、实验环境Microsoft Windows 7 Matlab 6.5五、编码程序计算如下信源进行香农编码，并计算编码效率：⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.06543210a a a a a a a P X MATLAB 程序：(1) a=[0.2 0.18 0.19 0.15 0.17 0.1 0.01]; k=length(a);y=0; for i=1:k-111()i i k k P p a -==∑for n=i+1:kif (a(i)<a(n))t=a(i);a(i)=a(n);a(n)=t;endendends=zeros(k,1);b=zeros(k,1);for m=1:ks(m)=y;y=y+a(m);b(m)=ceil(-log2(a(m)));z=zeros(b(m),1);x=s(m);p=b2d10(x);for r=1:b(m)z(r)=p(r);enddisp('Êä³ö½á¹ûΪ£º')disp('³öʸÅÂÊ'),disp(a(m))disp('ÇóºÍ½á¹û'),disp(s(m))disp('±àÂëλÊý'),disp(b(m))disp('×îÖÕ±àÂë'),disp(z')end(2) function y=b2d10(x)for i=1:8temp=x.*2;if(temp<1)y(i)=0;x=temp;elsex=temp-1;y(i)=1;endend(3) p=[0.2 0.19 0.18 0.17 0.15 0.1 0.01]; sum=0;sum1=0;for i=1:7a(i)=-log2(p(i));K(i)=ceil(a(i));R(i)=p(i)*K(i);sum=sum+R(i);c(i)=a(i)*p(i);sum1=sum1+c(i);endK1=sum;H=sum1;Y=H/K1;disp('ƽ¾ùÐÅÏ¢Á¿'),disp(H)disp('ƽ¾ùÂ볤'),disp(K1)disp('±àÂëЧÂÊ'),disp(Y)六、实验结果输出结果为：出事概率0.2000，求和结果0，编码位数3，最终编码000出事概率0.1900，求和结果0.2000，编码位数3，最终编码001出事概率0.1800，求和结果0.3900，编码位数3，最终编码011出事概率0.1700，求和结果0.5700，编码位数3，最终编码100出事概率0.1500，求和结果0.7400，编码位数3，最终编码101出事概率0.1000，求和结果0.8900，编码位数4，最终编码1110出事概率0.0100，求和结果0.9900，编码位数7，最终编码1111110编码效率：平均信息量2.6087平均码长3.1400编码效率0.8308七、实验总结通过本次的实验，掌握了Shannon编码的实验原理以及编码过程。

一、（11'）填空题（1）1948年，美国数学家香农发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。

（2）必然事件的自信息是0 。

（3）离散平稳无记忆信源X的N次扩展信源的熵等于离散信源X的熵的N倍。

（4）对于离散无记忆信源，当信源熵有最大值时，满足条件为__信源符号等概分布_。

（5）若一离散无记忆信源的信源熵H（X）等于2.5，对信源进行等长的无失真二进制编码，则编码长度至少为3 .（6）对于香农编码、费诺编码和霍夫曼编码，编码方法惟一的是香农编码. （7）已知某线性分组码的最小汉明距离为3,那么这组码最多能检测出_2_______个码元错误，最多能纠正___1__个码元错误。

（8）设有一离散无记忆平稳信道，其信道容量为C，只要待传送的信息传输率R__小于___C(大于、小于或者等于），则存在一种编码，当输入序列长度n足够大，使译码错误概率任意小. （9）平均错误概率不仅与信道本身的统计特性有关，还与___译码规则____________和___编码方法___有关三、（5'）居住在某地区的女孩中有25％是大学生,在女大学生中有75％是身高1.6米以上的,而女孩中身高1。

6米以上的占总数的一半。

假如我们得知“身高1.6米以上的某女孩是大学生”的消息，问获得多少信息量？解：设A表示“大学生”这一事件，B表示“身高1.60以上”这一事件，则P(A)=0。

25 p(B）=0.5 p(B｜A）=0.75 （2分)故 p（A｜B)=p（AB)/p(B)=p(A)p（B|A）/p(B)=0。

75＊0。

25/0。

5=0。

375 （2分）I（A|B)=—log0.375=1。

42bit （1分)四、（5'）证明：平均互信息量同信息熵之间满足I(X;Y)=H(X）+H(Y)—H（XY)证明:（2分）同理（1分）则因为（1分）故即(1分）五、（18’）。

黑白气象传真图的消息只有黑色和白色两种,求:1）黑色出现的概率为0。

信息论霍夫曼、香农-费诺编码LT二、实验原理：1、香农-费诺编码首先,将信源符号以概率递减的次序排列进来，将排列好的信源符号划分为两大组，使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后，将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元码符号。

依次下去，直至每一个小组只剩下一个信源符号为止。

这样，信源符号所对应的码符号序列则为编得的码字。

译码原理，按照编码的二叉树从树根开始，按译码序列进行逐个的向其叶子结点走，直到找到相应的信源符号为止。

之后再把指示标记回调到树根，按照同样的方式进行下一序列的译码到序列结束。

如果整个译码序列能够完整的译出则返回成功，否则则返回译码失败。

2、霍夫曼编码霍夫曼编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。

同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。

生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。

算法步骤如下：（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。

（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。

（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。

（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。

三、实验环境matlab7.1四、实验内容1、对于给定的信源的概率分布，用香农-费诺编码实现图像压缩2、对于给定的信源的概率分布，用霍夫曼编码实现图像压缩五、实验过程1.香农-费诺编码编码1function c=shannon(p)%p=[0.2 0.15 0.15 0.1 0.1 0.1 0.1 0.1] %shannon(p)[p,index]=sort(p)p=fliplr(p)n=length(p)pa=0for i=2:npa(i)= pa(i-1)+p(i-1) endk=ceil(-log2(p))c=cell(1,n)for i=1:nc{i}=”tmp=pa(i)for j=1:k(i)tmp=tmp*2if tmp>=1tmp=tmp-1 c{i(j)='1'elsec{i}(j) = '0' endendendc = fliplr(c)c(index)=c编码2clc;clear;A=[0.4,0.3,0.1,0.09,0.07,0.04]; A=fliplr(sort(A));%降序排列[m,n]=size(A);for i=1:nB(i,1)=A(i);%生成B的第1列end%生成B第2列的元素a=sum(B(:,1))/2;for k=1:n-1ifabs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1, 1))-a)break;endendfor i=1:n%生成B第2列的元素if i<=kB(i,2)=0;elseB(i,2)=1;endend%生成第一次编码的结果END=B(:,2)';END=sym(END);%生成第3列及以后几列的各元素j=3;while (j~=0)p=1;while(p<=n)x=B(p,j-1);for q=p:nif x==-1break;elseif B(q,j-1)==xy=1;continue;elsey=0;break;endendif y==1q=q+1;endif q==p|q-p==1B(p,j)=-1;elseif q-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;for k=p:q-2abs(sum(B(p:k,1))-a)<=abs(sum(B(p:k+1, 1))-a);break;endendfor i=p:q-1if i<=kB(i,j)=0;END(i)=[char(END(i)),'0'];elseB(i,j)=1;END(i)=[char(END(i)),'1'];endendendendendC=B(:,j);D=find(C==-1);[e,f]=size(D);if e==nj=0;elsej=j+1;endendBAENDfor i=1:n[u,v]=size(char(END(i))); L(i)=v;avlen=sum(L.*A)2. 霍夫曼编码function c=huffman(p)n=size(p,2)if n==1c=cell(1,1)c{1}=''returnend[p1,i1]=min(p)index=[(1:i1-1),(i1+1:n)] p=p(index)n=n-1[p2,i2]=min(p)index2=[(1:i2-1),(i2+1:n)] p=p(index2);i2=index(i2)index=index(index2)p(n)=p1+p2c=huffman(p)c{n+1}=strcat(c{n},'1')c{n}=strcat(c{n},'0') index=[index,i1,i2]c(index)=c。

香农编码
香农编码（Shannon coding）是一种基于信息论的无失真压缩算法。

它由克劳德·香农于1948年提出，是一种前缀
编码方法，用于将一串符号串压缩成更短的编码串。

香农编码的基本思想是根据符号的出现概率分配不同长度
的编码。

出现概率高的符号分配较短的编码，出现概率低
的符号分配较长的编码。

这样，编码串的平均长度就可以
降低，实现了数据的无失真压缩。

具体的步骤如下：
1. 计算每个符号的出现概率。

2. 按照概率从高到低对符号进行排序。

3. 给较高概率的符号分配较短的编码，较低概率的符号分
配较长的编码。

可以使用二叉树进行编码，每个符号对应
树上的一个叶子节点，编码为从根节点到叶子节点的路径。

4. 根据编码生成压缩后的编码串。

由于香农编码是一种无失真压缩算法，可以保证压缩后的数据能够完全恢复成原始数据。

然而，香农编码会导致编码长度不固定，需要附加一些额外的信息来标识编码的边界，这会增加一定的开销。

为了解决这个问题，后续发展出了其他压缩算法，如哈夫曼编码。

香农编码例题香农编码是一种将符号转化为二进制代码的编码方式，它是由美国数学家克劳德·香农在1948年提出的。

这种编码方式最初被应用于通信领域，但现在已经广泛应用于数据压缩、图像处理和音频处理等领域。

香农编码的基本思想是根据符号出现的概率来确定其对应的二进制代码。

出现概率较高的符号使用较短的二进制代码表示，而出现概率较低的符号使用较长的二进制代码表示。

这样可以有效地减少使用的二进制位数，从而达到数据压缩的目的。

下面我们来看一个例题：假设有5个符号A、B、C、D、E，它们出现的概率分别为0.4、0.2、0.15、0.15和0.1，请使用香农编码将它们转化为二进制代码。

首先需要按照概率大小对这些符号进行排序，从大到小依次为A、B、C、D和E。

接下来需要计算每个符号对应的编码长度。

根据香农编码原理可知，每个符号对应的编码长度等于其出现概率取对数后向上取整得到的值。

因此，A的编码长度为ceil(log2(1/0.4))=ceil(1.3219)=2，B的编码长度为ceil(log2(1/0.2))=ceil(2.3219)=3，C和D的编码长度均为4，E的编码长度为5。

然后可以根据每个符号对应的编码长度来确定它们对应的二进制代码。

具体地，A对应的二进制代码为00，B对应的二进制代码为010，C和D均对应的二进制代码为0110，E对应的二进制代码为01110。

最后将这些二进制代码按照符号出现概率大小从小到大排列起来就可以得到它们对应的香农编码：E=01110、D=0110、C=0110、B=010、A=00。

通过这个例题我们可以看出，在使用香农编码进行数据压缩时，出现概率较高的符号所对应的二进制代码较短，而出现概率较低的符号所对应的二进制代码较长。

这样可以有效地减少使用的二进制位数，并且在解压缩时也能够快速地还原原始数据。

因此，在实际应用中香农编码是一种非常有效和常用的数据压缩方式。

2.1 同时掷出两个正常的骰子，也就是各面呈现的概率都为1/6，求： (1) “3和5同时出现”这事件的自信息； (2) “两个1同时出现”这事件的自信息； (3) 两个点数中至少有一个是1的自信息量。

2.2 居住某地区的女孩子有25%是大学生，在女大学生中有75%是身高160厘米以上的，而女孩子中身高160厘米以上的占总数的一半。

假如我们得知“身高160厘米以上的某女孩是大学生”的消息，问获得多少信息量？2.3 掷两颗骰子，当其向上的面的小圆点之和是3时，该消息包含的信息量是多少？当小圆点之和是7时，该消息所包含的信息量又是多少？2.4 从大量统计资料知道，男性中红绿色盲的发病率为7%，女性发病率为0.5%，如果你问一位男士：“你是否是色盲？”他的回答可能是“是”，可能是“否”，问这两个回答中各含多少信息量，平均每个回答中含有多少信息量？如果问一位女士，则答案中含有的平均自信息量是多少？2.5黑白气象传真图的消息只有黑色和白色两种，即信源X ={黑，白}。

设黑色出现的概率为P(黑) = 0.3，白色出现的概率为P(白) = 0.7。

假设图上黑白消息出现前后没有关联，求熵H(X)；2.6 有两个随机变量X 和Y ，其和为Z = X + Y （一般加法），若X 和Y 相互独立，求证：H(X) ≤ H(Z), H(Y) ≤ H(Z)。

2.7 消息源以概率123451/2,1/4,1/8,1/16,1/16,P P P P P =====发送5种消息符号12345,,,,m m m m m 。

（1） 若每个消息符号出现是独立的，求每个消息符号的信息量。

（2） 求该符号集的平均信息量。

2.8 设离散无记忆信源⎭⎬⎫⎩⎨⎧=====⎥⎦⎤⎢⎣⎡8/14/1324/18/310)(4321x x x x X P X ，其发出的信息为(202120130213001203210110321010021032011223210)，求 (1) 此消息的自信息量是多少？(2) 此消息中平均每符号携带的信息量是多少？2.9 汉字电报中每位十进制数字代码的出现概率如题9表所示，求该离散信源的熵。