信息论与编码 (2)

1、一 设计目的 信息论与编码是我们电子信息工程的一门重要的专业课，通过对本次课程设计，学习将学到的理论知识用于实践，同时也学习了用软件编写程序，进一步对本课程知识的巩固和理解。学习分析问题，解决问题的方法和途径，提高对本专业的学习兴趣。二 设计任务与要求（1）统计信源熵要求：统计任意文本文件中各字符（不区分大小写）数量，计算字符概率，并计算信源熵。（2）哈夫曼编码要求：任意输入消息概率，利用哈夫曼编码方法进行编码，并计算信源熵和编码效率。三 理论简介3.1通信系统的模型 通信系统的模型通信系统的性能指标主要是有效性、可靠性、安全性和经济性，通信系统优化就是使这些指标达到最佳，除了经济性，这些指标

2、正是信息论的研究对象，可以通过各种编码处理来使通信系统的性能最优化。根据信息论的各种编码定理和上述通信系统的指标，编码问题可以分为3类：信源编码、信道编码和加密编码。3.1.1 信源编码由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余度，提高编码效率。信源编码的基础是信息论中的两个编码定理：无失真编码定理和限失真编码定理。前者适用于离散信源或数字信号；后者主要用于连续信源或模拟信号。本次课程设计就是利用的无失真信源编码。3.1.2 信道编码信源编码器的作用：把信源发出的消息变换成由二进制码元(或多进制码元)组成的代码组，这种代码组就是基带信号。同时通过

3、信源编码可以压缩信源的冗余度，以提高通信系统传输消息的效率。信源译码器的作用：把信道译码器输出的代码组变换成信宿所需要的消息形式，它的作用相当于信源编码器的逆过程。3.1.3 加密编码 加密编码是研究如何隐蔽消息中的信息内容，以便在传输过程中不被窃听，提高通信系统的安全性。3.2 信源熵3.2.1 信源的描述和分类& 按信源在时间和幅度上的分布情况 离散信源：文字、数据、电报 连续信源：语音、图像& 按发出符号的数量 单个符号信源：指信源每次只发出一个符号代表一个消息 符号序列信源：指信源每次发出一组含二个以上符号的符号序列代表一个消息& 按符号间的关系 无记忆信源 有

4、记忆信源3.2.2 离散信源熵& 自信息量：随机事件的自信息量定义为其概率对数的负值，即 在信息论中常用的对数底是2，信息量的单位为比特(bit)；& 联合自信息量两个消息xi，yj同时出现的联合自信息量： & 条件自信息量 在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi / yj) ，则它的条件自信息量定义为条件概率对数的负值： & 离散信源熵为信源中各个符号不确定度的数学期望，即 单位为：比特/符号 或者 比特/符号序列。 信息熵H(X)表示信源输出后，每个消息(或符号)所提供的平均信息量。四设计思路4.1 编码效率编码效率计算公式如下： 其中

5、H（X）为信源熵，K表示平均码长。4.2 变长码的编码方法 能获得最佳码的编码方法主要有： 香农（Shannon） 费诺（Fano） 霍夫曼（Huffman4.2.1 香农编码将信源消息符号按其概率从大到小排列确定满足下列不等式的整数码长Ki令P1=0，计算第i个消息的累加概率将累加概率Pi变换成二进制数，取小数点后Ki位为该消息的码字4.2.2 费诺编码 费诺编码属于概率匹配编码，不是最佳的编码方法。编码过程如下： （1）将信源消息符号按其出现的概率依次排列p(x1) p(x2) p(xn) （2）按编码进制数将概率分组，使每组概率尽可能接近或相等，并为每一组分配一位码元。如编二进制码就分成

6、两组，编m进制码就分成m组。 （3）将每一分组再按同样原则划分，重复步骤2，直至概率不再可分为止。 （4）信源符号所对应的码字即为费诺码。4.2.3 哈夫曼编码 （1）将信源消息符号按其出现的概率大小依次排列 p(x1)p(x2) p(xn) （2）取两个概率最小的符号分别配以0和1，并将这两个概率相加作为一个新符号的概率，与未分配码元的符号重新排队。 （3）对重排后的两个概率最小符号重复步骤2的过程。 （4）继续上述过程，直到最后两个符号配以0和1为止。 （5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。4.3 设计思路4.3.1 统计信源熵的设计思路在VC+环境

7、中进行编程 （1）打开一篇文章，将26个英文字母及空格作为信源。 （2）计算每个字母出现的次数（不区分大小写），再通过计算信源总大小来计算在本篇文章中每个字母出现的概率。 （3）通过信源熵计算公式来计算信源熵。4.3.2 哈弗曼编码的设计思路 在matlab中进行编码（1） 输入概率矩阵，并检验是否正确，即各概率不能小于零，总概率之和等于一。（2） 建立各概率符号的位置索引矩阵Index,利于编码后从树根进行回溯,从而得出对应的编码（3） 输出所需的哈弗曼编码。（4） 计算信源熵，并计算平均码长，算出编码效率。（5） 输出结果。五 设计流程图5.1统计信源熵的设计思路 5.2哈弗曼编码设计思路

8、 六 程序运行及结果6.1统计信源熵程序运行结果测试输入:text.txt There is no hate without fear. Hate is crystallized fear, fears dividend, fear objectivized. We hate what we fear and so where hate is, fear is lurking. Thus we hate what threatens our person, our vanity and our dreams and plans for ourselves. If we can isolate

9、this element in what we hate we may be able to cease from hating.测试目的：检验程序是否正确。检验方法：用验证法来检验；看中概率是否为一，并检测信源熵是否正确。检验结果：程序运行结果正确。如下截屏所示6.2哈弗曼编码程序运行结果测试输入：0.2 0.19 0.18 0.17 0.15 0.10 0.01测试目的：测试经常出现的信源符号是否对应较短的码长，检测程序运行结果是否正确。正确输出：01 00 111 110 101 1001 1000 信源熵为2.6087 bit/符号 平均码长为2.7 码元/符号 传送速率为0.9591

10、 bit/码元实际输出：与争取而输出一样检测结果：程序无错误以下为截屏八 心得体会 课程设计是非常锻炼我们能力的一种方法，在准备课程设计的过程中，各方面都有所提高。首先，再一次对课本知识进行学习，将所有设计到的知识重新温习一遍，并且针对设计，还要看些其它相关书籍，对知识进行升华，其次，针对课程设计，必须针对其要求进一步提取有效内容，锻炼分析问题，解决问题的能力，尽管本次课程设计相对简单些，我们还是需要从各方面进行准备，另外就是编写程序，这是本次课程设计的关键，编写程序，从不懂到会，这无疑又是一种极大的提高，还有在编程时遇见了不少问题，各种函数的应用都在考验着我们，然后便是我们小组的合作精神，随

11、着学习的深入和实践的锻炼，我们越来越觉得团队合作对于我们的重要性，在现在的社会，几乎没有人可以脱离团体单独工作，科技的发展，人类的进步，我们社会工作状态都呈现了一种个人分工，集体作战的策略，因此，在我们未正式进入社会之前，能够锻炼自己的团队精神，这是相当好的。 参考文献1 曹雪虹、张宗橙编著信息论与编码.清华大学出版社，2009年第2版2 贾宗璞、许合利编著C语言程序设计.人民邮电出版社，2010年第1版3 严蔚敏、吴伟民编著数据结构（C语言版）.清华大学出版社，1997年第1版附录源程序清单一统计信源熵 /要求：统计任意文本文件中各字符（不区分大小写）数量，计算字母及空格概率，并计算信源熵。

12、#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#define N 1000 /出错地方：字符总数不对，求字符串长度有问题。似乎跟N有关。int main(void) /没有输出字符个数。 char sN,MN; int i = 0,j=0,n=0,L=0; int len, num27 = 0; double result=0,p27= 0; FILE *f; char tempN; /*以下是打开一个指定文件的过程*/ if(!(f = fope

13、n("C:test2.txt","rb") printf("文件打开失败！n");return 0; while(!feof(f) /feof输入输出函数，检查文件是否结束，如结束，则返回非零值，否则返回0 .函数原型为：int feof(FILE *fp) len = fread(temp,1,486,f); /fread返回读取的字符个数 temp为内存区域首地址 1为每次读入字节数 486读入次数 f指针 fclose(f); /关闭文件 templen = '0' /方便统计字符总数 memcpy(s, tem

14、p, sizeof(temp); /从temp中拷贝sizeof个字节到目标s中 /*统计26个字母及空格出现次数*/ for(i=0; i<strlen(s); i+) if(si=' ') num26+; else if(si>='a'&&si<='z') numsi-97+; else if(si>='A'&&si<='Z') numsi-65+; printf("文档中各个字母出现的次数:n"); for(j=0; j<

15、26; j+)Mj=numj; printf("%3c:%dt",j+65,Mj);L+; if(L=3) printf("n"); L=0; printf("空格:%dt",num26); /*统计26个字母或者空格出现概率*/ printf("n文档中各个字母出现的概率:n"); for(i=0; i<26; i+) pi=(double)numi/strlen(s); printf("%3c:%ft",i+65,pi); n+; if(n=3) printf("n"

16、;); n=0; p26=(double)num26/strlen(s); printf("空格:%ft",p26); printf("n");/*计算信源熵*/ for(i=0; i<27; i+) if (pi!=0) result=result+pi*log(pi)*1.433; result=-result; printf("信源熵为:%f",result); printf(" n文章总字符长度:%d",strlen(temp); printf("n"); return 0;二哈夫

17、曼编码%要求：任意输入消息概率，利用上述编码方法进行编码，并计算信源熵和编码效率。>> clear;P=input('请输入信源概率向量P=');N=length(P);for component=1:1:N if(P(component)<0) error('信源概率不能小于0'); endendif(sum(P)-1)>0.0001) error('信源概率之和必须为1');end%建立各概率符号的位置索引矩阵Index,利于编码后从树根进行回溯,从而得出对应的编码Q=PIndex=zeros(N-1,N); %初始化

18、Index for i=1:N-1 Q,L=sort(Q); Index(i,:)=L(1:N-i+1),zeros(1,i-1); G(i,:)=Q; Q=Q(1)+Q(2),Q(3:N),1; %将Q中概率最小的两个元素合并，元素不足的地方补1end %根据以上建立的Index矩阵，进行回溯，获取信源编码for i=1:N-1Char(i,:)=blanks(N*N);%初始化一个由空格符组成的字符矩阵N*N,用于存放编码end %从码树的树根向树叶回溯，即从G矩阵的最后一行按与Index中的索引位置的对应关系向其第一行进行编码Char(N-1,N)='0' %G中的N-1

19、行即最后一行第一个元素赋为0，存到Char中N-1行的N列位置Char(N-1,2*N)='1'%G中的N-1行即最后一行第二个元素赋为1，存到Char中N-1行的2*N列位置 %以下从G的倒数第二行开始向前编码for i=2:N-1 Char(N-i,1:N-1)=Char(N-i+1,N*(find(Index(N-i+1,:)=1) -(N-2):N*(find(Index(N-i+1,:)=1); %将Index后一行中索引为1的编码码字填入到当前行的第一个编码位置 Char(N-i,N)='0' %然后在当前行的第一个编码位置末尾填入'0

20、9; Char(N-i,N+1:2*N-1)=Char(N-i,1:N-1); %将G后一行中索引为1的编码码字填入到当前行的第二个编码位置 Char(N-i,2*N)='1' %然后在当前行的第二个编码位置末尾填入'1' for j=1:i-1 %内循环作用：将Index后一行中索引不为1处的编码按照左右顺序填入当前行的第3个位置开始的地方,最后计算到Index的首行为止. Char(N-i,(j+1)*N+1:(j+2)*N)=Char(N-i+1,N*(find(Index(N-i+1,:)=j+1)-1)+1:N*find(Index(N-i+1,:)=j+1); end end %Char中第一行的编码结果就是所需的Huffman 编码输出，通过Index中第一行索引将编码对应到相应概率的信源符号上。 for i=1:N Result(i,1:N)=Char(1,N*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*N); h(i)=length(find(abs(Result(i,:)=32)