费诺编码实验报告

1 / 15 费诺编码实验报告 中南大学 信息论与编码实验报告 选 题：费诺编码 学生姓名： 学 号： 专业班级： 通信工程指导老师： 学 院： 信息科学与工程学院 时 间： 2016 目录 一、实验目的 二、实验原理 费诺编码思想 费诺编码流程图 三、实验内容 四、实验要求 五、代码调试结果 六、心得体会 七、程序源代码 一实验目的 1. 掌握费诺编码的原理和过程。 2. 熟悉 C/C+语言，练习使用 C/C+实现香农码和Huffman 编码。 二、实验原理 2 .1 费诺编码思想 设有离散无记忆信源 ?x1?p?1x2.xn?n ,?p?1?p.p?i?1 2 / 15 1.按信源符号的概率从大到小的顺序排队 不妨设 p?p?.?p 2.将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“ 0”和“ 1”。 3.将 每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“ 0”和“ 1”。 4.如此重复，直至每个组只剩下一个信源符号为止。 5.信源符号所对应的码字即为费诺码。 例：有一单符号离散无记忆信源 x2x3x4x5x6?X?x1 ?P? 对该信源编二进制费诺码 H? R? log2mL H ?%R 6 ? ?pki? i?1 费诺编码流程图 3 / 15 三、实验内容 使用 CC+实现费诺编码，并自己设计测试案例。 四、实验要求 1.提前预习实验，认真阅读实验原理以及相应的参考书。 2.认真高效的完成实验，实验中服从实验室管理人员以及实验指导老师的管理。 3.认真撰写实验报告，内容可以自己编排，可以考虑包括以下一些方面：原理概述、程序设计与算法描述、源程序及注释、运行输出结果实例、调试和运行程序过程中产生的问题及采取的措施、对实验的讨论分析、总结。 五、代 码调试结果 吉林建筑大学 电气与电子信息工程学院 设计题目： 费诺编码的分析与实现 专业班级： 电子信息工程 111 学生姓名： 马 超 学 号：指导教师： 设计时间： 第 1章 概述 设计的作用、目的 信息论与编码是一门理论与实践密切结合的课程 ,通过理论课程学习如何计算信道容4 / 15 量，包括对信道的认识，以及传输速率的计算，计算最佳编码，编码效率等等。再通过课程设计加深对知识的认识，课程设 计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。 通过完成具体编码算法的程序设计和调试工作，提高对 MATLAB 等类似软件的认识程度，掌握 MATLAB等类似软件的各种操作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践 的程序和方法。 设计任务及要求 1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2. 掌握费诺编码方法的基本步骤及优缺点； 3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码 过程； 4. 能够使用 MATLAB 或其他语言进行编程，编写的函数要有通用性。 设计内容 5 / 15 一个有 8个符号的信源 X，各个符号出现的概率分别为： x7x8?X?x1x2x3x4x5x6? ?P? 运用 MATLAB 软件，编写适当的程序，对以上 8个信源符号进行费诺编码， 得出二进制码字，计算平均码长、编码效率、冗余度，并总结费诺编码方法 的特点和应用。 第 2 章 费诺编码的分析与实现 设计原理 1.编码原理 早期的数据压缩来自于人们对概率的了解。当对文字信息进行编码时，如果出现概率较高的字幕赋予较短的编码，为出现概率较低的字母赋予较长的编码，平均编码长度就能缩短不少。著名的 Morse电码就是一个范例。信息论之父 曾指出，任何 信息都存在冗余，冗余大小与信息中每个符号出现概率有关。他所提出的无失真信源编码定理奠定了数据压缩的理论基础。数据压缩的目的就是要消除冗余，信息论是运用概率论与数理统计的方法研究信息、信源熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科。 从 DVD 到个人电脑，从卫星通信到文件，在我们今天的生活中，信息几乎在每个领域都扮演者重要角色。工程6 / 15 师克劳德香农于 1948 年奠定了信息论的基础，他指出了通信的极限。基于这一理论产生了数据压缩技术、纠错技术等各个应用技术，这些技术提高了数据传输和存储的 效率。信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。这两个方面又由信息传输定理、信源 信道隔离定理相互联系。当然，信息论的重大应用远不止于此。 DNA是一种信息存储物质，正事信息论帮助人们解开了生物基因组密码之谜。简单地说信息论包含了生命、宇宙乃至一切。 信息论对现代社会的影响是多方面的。首先，在理论研究方面，信息论所处的地位已远远超出了香农当年所界定的“通信的数学理论”的范畴，得到了不断的扩充和发展，出现了语义信息、语法信息与 语用信息等研究与信息的意义有关的学科，以及面向智能研究的全信息理论。如今，信息已成为与物质、能量并列的宇宙中的三个基本要素，世间万物的发展变化可归结为物质、能量和信息的传递和转化过程。另一方面，在科学和技术高度发展的今天，信息的概念也被渗透到许多不同的学科和领域，深入到了社会生活的各个方面，成为可与相对论和量子力学并驾齐驱的新一代边缘交叉学科的重要组成部分。特别是以信息论、控制论、和系统论为代表的“老三论”以及以普利高津的耗散结构理论，哈肯的协同学和托姆的突变论或艾根的超循环理论为代表7 / 15 的“新三论”的出现，标 志着一代新的边缘交叉学科的兴起。它们的形成和发展对现代科学的研究具有重要的方法论上的指导意义。 编码是信息从一种形式或格式转换为另一种形式的过程也称为计算机编程语言的代码简称编码。用预先规定的方法将文字、数字或其它对象编成数码，或将信息、数据转换成规定的电脉冲信号。编码在电子计算机、电视、遥控和通讯等方面广泛使用。在计算机硬件中，编码是指用代码来表示各组数据资料，使其成为可利用计算机进行处理和分析的信息。代码是用来表示事物的记号，它可以用数字、字母、特殊的符号或它们之间的组合来表示，将数据转换为 代码或编码字符，并能译为原数据形式。是计算机书写指令的过程，程序设计中的一部分。在地图自动制图中，按一定规则用数字与字母表示地图内容的过程，通过编码，使计算机能识别地图的各地理要素。 编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真。由于这些定力都要求符号数很大，以便其值接近所规定的值，因而这些定力被称为极限定理。一般称无失真信源编码定力为第一极限定理；信道编码称为第二极限定理；限失真信源编码定力称为第三极限定理。 2.信源编码原理 由于信源符号之间存在分布不 均匀和相关性，是的8 / 15 信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体说，就是针对仙缘输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。信源编码的基本途径有两个：使序列中的各个符号尽可能的相互独立，及解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。 信源编码的基础是信息论中的两个编码定理：无失真编码定理和限失真编码定理，前者是可逆编码的基础。可逆是指当信源符号转换成代码后，可从代码无失真的恢复原信源符号。当已知信源符号的概率特性时，可计算它的 符号熵，这边是每个信源符号所载有的信息量。编码定理不但证明了必定存在一种编码方法，可使代码的平均长度可任意接近但不低于符号熵，而且还阐明达到这木匾的途径，就是使概率与码长匹配。无失真编码或可逆编码只适用与离散信源。对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为后者的取值可有无限多个。此时只能根据率失真编码定理在失真受限制的情况下进行限失真编码。信源编码定理出现后，编码定理趋于合理化。关于离散信源编码，从无失真编码定理出发。 若要所编的码是惟一可译码，不但要求编码时不同的信源符号变换成不同的码字，而且必须要求任意有限长的信源序列所对应的码符号序列各不相同，即要求码的任意有9 / 15 限长 N次扩展码都是非奇异码。因为只有任意有限长的信源序列 所对应的码符号序列各不相同，才能把该码符号序列惟一地分割成一个个对应的信源符号，从而实现惟一的译码。 3.费诺编码原理 费诺编码就是 通过使编码中各个句号出现的概率大致相等，实现概率均匀化，从而减少冗余度，提高编码效率。凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。在编 N 进制码时首先将信源消息符号按其出现的额概率一次又小到大排列开来，并将排列好的心愿符号按概率值分 N 大组，使 N组的概率之和近似相同，并对各组赋予一个 N 进制码元 0、 1.N-1。之后再针对每一个大组内的心愿符号做如上处理，即再分为概率相同的 N组，赋予 N进制码元。如此重复，直到每组只剩下一个心愿符号为止。此时每个信源符号所对应的码字即为费 诺码。针对同一个心愿，费诺码比香农码平均码长小，消息出书速率大，编码效率高。费诺编码是一种信源编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高。但它属于概率匹配编码它不是最佳的编码方法。 4.费诺编码特点 10 / 15 费诺编码是一种信源编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高。但它属于概率匹配编码它不是最佳的编码方法。 费诺编码属于概率匹配编码，具有如下特点： 概率大，则分解次数少；概率小则分解次数多，这符合最佳编 码原则。 码字集合是唯一的。 分解之后先得码字后得码长。 设计步骤 1.费诺码编码步骤 将信源消息符号按其出现的概率大小依次排列： p1 p2 pn 。 将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似 相同，并对各组赋予一个二进制码元“ 0”和“ 1”。 将每一大组的信源符号再分成两组，使划分后的两个组的概率之和近似 相同，并对各组赋予一个二进制符号“ 0”和“ 1”。 如此重复，直至每个组只剩下一个 信源符号为止。 信源符号所对应的码子即为费诺码。 本科生实验报告 实验课程 信息论与编码 学院名称 信息科学11 / 15 与技术学院专业名称通信工程 学生姓名学生学号 指导教师谢振东 实验地点 6C601 实验成绩 二 一五 年 十一 月二 一五 年 十一月 实验一：香农编码 一、实验目的 掌握通过计算机实现香农编码的方法。 二、实验要求 对于给定的信源的概率分布，按照香农编码的方法进行计算机实现 。 三、实验基本原理 给定某个信源符号的概率分布，通过以下的步骤进行香农编码 1、将信源消息符号按其出现的概率大小排列 p?p?p 2、确定满足下列不等式的整数码长 Ki ； ?log2p?Ki?log2p?1 i?13、为了编成唯一可译码，计算第 i 个消息的累加概率 pi?k?1p 4、将累加概率 Pi变换成二进制数。 5、取 Pi 二进制数的小数点后 K i 位即为该消息符号的二进制码。 12 / 15 四、源程序： #include #include #include #include #include using namespace std; int main int N; coutN; cout double *X=new doubleN; /离散无记忆信源 int i,j; for coutXi; for for if double temp=Xi;Xi=Xj;Xj=temp; int *K=new intN; 13 / 15 for Ki=int/log)+1; if/log)+1) double *Pa=new doubleN; Pa0=; for Pai=Pai-1+Xi-1; string *code=new stringN; for for double temp=Pai*2; if codei+=1; Pai=Pai*2-1; else codei+=0; Pai*= 2; 14 / 15 for codei= codei.substr; cout for cout delete X; delete Pa; delete K; delete code; getchar; return 0; 六、调试过程中出现的错误： 1、在源代码的基础上添加： #include #include #include #include #include using