游程编码实现有效性提高的原理及通用编码的思想
康乐203201505020
摘要：信源编码的目的是提高信息传输效率，其思想是去除消息中的冗余成分。在无失真的信源编码中，根据信源的统计特性进行编码称为统计编码，而在信源统计特性未知的情况下，就需要一种新的编码方法，称之为通用编码。本文对统计编码中的游程编码进行了分析，说明其有效性，给出其具有有效性的原理论述，对游程编码的截断效应进行了仿真；同时分析了通用编码的存在性与构造方法，还以字典码为例进行了仿真。
关键词：信源编码游程编码通用编码字典码
一、信源编码概述
通信的根本问题是将信源的输出在接收端精确的或近似的重现出来。为此需要解决两个问题。其一是信源的输出应如何描述，及如何计算它产生的信息量；其二是如何表示信源的输出，即信源编码问题。由于信源可以根据信息输出的形式分为离散信源和连续信源，因此信源编码也就可以分为离散信源和连续信源。
根据通信的要求，可以将信源编码分为无失真信源编码和限定失真的信源编码。若要求精确的重现信源的输出，就要保证信源产生的
全部信息无损的传递给信宿，这时的信源编码就是无失真信源编码。许多实际情况下，并不要求完全精确地复制出信源的输出，而且在有干扰的情况下，这也是不可能的。一般对信源-信宿要定出可接收准则或保真度准则，这就是限定失真的信源编码。
离散信源的输出可以用如下符号序列表示：
21012,,,,,U U U U U --
其中l U 表示在第l 时刻产生的符号，l 为整数。l U 为一随机变量，它
在有限字母集{}1,k A a a =中选取。如果使用D 字母的集合
{}1,d B b b =作为码表，那么如果组成码字的码符号数目相等，我们就称之为等长编码，否则称之为非等长编码。
非等长编码则可以根据编码是否依赖信源的统计特性分为统计编码与通用编码。
二、 游程编码
2.1 游程编码概念
游程编码（RLC, Run Length Coding ），又称“运行长度编码”或“行程编码”，是一种统计编码，该编码属于无损压缩编码，是栅格数据压缩的重要编码方法。
游程编码中的游程是指字符序列中各个字符连续重复出现而形成的字符串长度，编码方法是将字符序列映射成字符串长度和位置的标志序列，那么对于M 元序列：
011{,,,}M u u u -
输入的消息序列{,,,,,}i r r r k U u u u u u 中的符号r U 的游程长度()L r 就是其游程长度。 例如：5555557777733322221111111
行程编码为：（5，6）（7，5）（3，3）（2，4）（1，7）。可见，行程编码的位数远远少于原始字符串的位数。
2.2 游程编码有效性 在对图像数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，用字串代替这些连续符号，可大幅度减少数据量。
游程编码记录方式有两种：①逐行的记录每个游程的终点列号：②逐行的记录每个游程的长度
第一种方式：
A A A
B B
A C C C A
这个图形就记为：
A,3，B,5
A,1，C,4，A,5
第二种就记作：
A,3，B,2
A,1，C,3，A,1
行程编码是连续精确的编码，在传输过程中，如果其中一位符号发生错误，即可影响整个编码序列，使行程编码无法还原回原始数据。
游程长度在栅格加密时，数据量没有明显增加，压缩效率较高，且易于检索、叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码和解码运算，增加处理和操作时间的情况。
举例来说，一组输入序列"AAAABBBCCDEEEE"，由4个A 、3个B 、2个C 、1个D 、4个E 组成，经过游程编码可将序列压缩为4A3B2C1D4E ，即由14个单位转成10个单位长度。
简言之，其优点在于将重复性高的数据量压缩成小单位；然而，其缺点在于─若该字符出现频率不高，可能导致压缩结果数据量比原始序列大，例如：原始序列"ABCDE"，压缩结果为"1A1B1C1D1E"即由5个单位转成10个单位长度。
2.3 游程编码有效性原理
由于游程编码并没有一个完备的数学公理体系作为支撑，因此想要分析它的有效性就要分类进行，本文只讨论了二元游程编码以及多元游程编码中的冗余位编码的有效性原理。
冗余位编码
对于M 元序列：
011{,,,}M u u u
当M≥3时，只凭借游程长度L 无法实现可逆的编码，需要添加其他
符号。当M 很大时，附加标志可能抵消压缩编码的好处。但是有一种特殊情况,当输入序列为：
1231112m m m U x x x x yy yyyyx x y yyy +=?????
经过游程编码可以分解为以下两个序列：
1111000000110000L =?????
'1231112 m m m U x x x x x x +=???
即将一个多元序列分解为一个二元序列和一个缩减多元序列，从而提高了编码效率。
二元游程编码
对于二元相关信源来说，对其N 次扩展信源编码才能提高编码效率。这将产生符号数剧增，码字多，译码复杂，符号间相关性没有利用等等一系列问题。
而对于二元相关信源，游程编码可以只凭借游程长度L 实现可逆的编码，下面给出有效性的证明：
假设游程编码将二元相关信源编码为黑游程与白游程，分别对应 1与0的长度。那么可以得到白游程熵：
w l 为白游程长度，L 为白游程最大长度
由信源编码定理：
w L 为白游程平均码长。
所以白游程长的平均值为：
联立上述几式可得：
白像素熵值为：
白像素平均码长为：
带入（4）式中可得：
同理对黑游程也可以得到：
每个像素的熵值：
(8)
每个像素平均码长：
(9)
将（5）乘以w P 加上（7）乘以B P ：
可以看出二元相关信源编码后的平均码长仍以信源熵为极限，所以压缩效率较高。
三、通用编码
3.1通用编码的存在性
统计分布需要精确的知道信源的概率分布，或者对信源的实际分布和假设分布之间的偏差很敏感时。一旦实际分布与假设分布有差异时，通用编码的性能会急剧下降。但在实际应用中，想要确切的获得信源的统计特性是十分困难的，这时就需要寻找一种与信源统计特性无关的编码方案。
由香农第三定理，只要码长足够长，总可以找到一种信源编码，使得编码后的信息传输率略大于率湿疹函数，而编码的平均失真度不大于给定的允许失真度。这就说明了至少存在有限失真的通用编码方法，使得编码长度足够大时，错误概率任意小。
3.2通用编码的构造方法
由于统计特性不确知是通用编码的困难之处，因此可以考虑对信源的概率统计特性进行估计，并用估计的统计特性为基础，将类似于统计编码的设计思路应用到通用编码上。这种构造方法一般的特点是
边统计，边编码，以使得完成的编码与心愿的概率统计特性近似的匹配。
另外一种构造方法是考虑到通用编码存在的依据：只要编码速率R＞H(x)，H(x)是信源熵，那么当编码长度充分的大时，可以使得译码错误概率任意小。那么只要对平均码长做出约束，就可以大致确定通用编码的方式。这种构造方法是以序列复杂度的理论为基础，以求出平均码长极限，从而获得编码方案。
3.3字典码
字典码是使用估计信源的统计特性来构造通用编码方法的典型应用。
编码
LZ编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的缀-符串用字符C进行扩展生成新的缀-符串，然后添加到词典中。是边生成字典，边编码的过程。
编码算法
步骤1：在开始时，词典和当前前缀P都是空的。
步骤2：当前字符C ：=字符流中的下一个字符。
步骤3：判断P+C是否在词典中：
(1) 如果“是”：用C扩展P，让P ：= P+C ；
(2) 如果“否”：
①输出与当前前缀P相对应的码字和当前字符C；
② 把字符串P+C 添加到词典中。
③ 令P ：=空值。
(3) 判断字符流中是否还有字符需要编码
① 如果“是”：返回到步骤2。
② 如果“否”：若当前前缀P 不是空的，输出相应于当
前前缀P 的码字，然后结束编码。
N 开始 获得信源序列
初始化字典 初始化待处理字 符串 能否在字典中找到短语得到短语号 更新最后一个字符 已到输入序列中最后一结束 输出：字典中最后一个字符 更新字典，将最新的字符加更新最后一个字符 Y N Y 图 1 字典码编码流程图
●译码
LZ的译码过程与之相反，将当前码字W对应的前缀输出，再输出当前编码对应符号C。从空集开始更新字典，不断添加新的缀-符串。是边生成字典，边译码的过程。
译码算法
?步骤1：在开始时词典是空的。
?步骤2：当前码字W ：=码字流中的下一个码字。
?步骤3：当前字符C ：= 紧随码字之后的字符。
?步骤4：输出当前码字的缀-符串到字符流，然后输出字符C。
?步骤5：把W+C添加到词典中。
?步骤6：判断码字流中是否还有码字要译码
(1) 如果“是”，就返回到步骤2。
(2) 如果“否”，则结束。
四、 总结
本文对统计编码中的游程编码进行了分析，说明其有效性，给出其具有有效性的原理论述，对游程编码的截断效应进行了仿真；同时分析了通用编码的存在性与构造方法，还以字典码为例进行了仿真。 其中遇到的难点有以下几点：
? 游程编码理论分析
? 游程编码截断效应仿真
? 通用编码构造方法总结 图 2 字典码译码流程图
?字典码编程实现
解决问题的方法主要有：
?将游程编码视为黑白二种游程，先分别计算其平均码长，再将两种游程看成一种编码，计算其平均码长，从而说明游程编
码是一种熵编码。
?游程编码的仿真中存在寻找不同游程变化点的过程，是整体算法计算复杂度最集中的部分，后来在改进中使用求导的方法
来获得游程变化点，大大减少了复杂度，是的截断效应的仿
真点数增多，效果能够更加明显。
?通用编码的构造方法在一般的教参中很少提及，大多含混而过，此处综合了许多文献的观点。
?字典码的编程实现还是较为复杂的，主要是编译码过程中对字典的构造需要大量的计算，但是通过改进，可以动态的建立
字典，只需传递字典的大小而不必传输字典本身，并且可以
将每一步的输出都输出出来，从而验证了代码的正确性。
参考文献：
[1].徐利华, 陈早生. 二值图像中的游程编码区域标记[J]. 光电工程,
2004, 31(6):63-65. 最得力的参考文献[2].魏佳圆, 温媛媛, 周诠. 二值图像游程-Huffman编码方法研究及
Matlab实现[J]. 空间电子技术, 2015(1):93-96.
[3]. 谭兆信. 散列高阶字典编码及其实现[J]. 软件学报,
1998(8):632-636.
[4].李畅. 无损图像压缩算法与有损图像压缩算法分析[J]. 现代计算
机：普及版, 2015(12):61-64.
[5].
实验课程：信息论与编码理论专业：信息与计算科学班级：09070241 学号：0907024101 姓名：孙秋月 中北大学理学院
实验二 哈夫曼编码 一、实验目的 1. 掌握哈夫曼编码的原理及编码步骤 2. 练习matlab 中哈夫曼编码函数的调用及通信工具箱的使用 二、实验原理 哈夫曼编码的具体步骤归纳如下： 1. 统计n 个信源消息符号，得到n 个不同概率的信息符号。 2. 将这n 个信源信息符号按其概率大小依次排序： p (x 1) ≥ p (x 2)≥ …≥ p (x n ) 3. 取两个概率最小的信息符号分别配以0和1两个码元，并将这两个概率相加作为一个新的信息符号的概率，和未分配的信息符号构成新的信息符号序列。 4. 将剩余的信息符号，按概率大小重新进行排序。 5. 重复步骤3，将排序后的最后两个小概论相加，相加和与其他概率再排序。 6. 如此反复重复n-2次，最后只剩下两个概率。 7. 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字，构成霍夫曼编码字。编码结束。 三、实验内容 为某一信源进行哈夫曼编码。该信源的字符集为X={x 1, x 2, … x 6 }，相应的概率矢量为：P =(0.30,0.25,0.21,0.10,0.09,0.05)，即X ，P 的概率空间为： 123456 0.300.250.210.100.090.05X x x x x x x P ????=???????? 根据哈夫曼编码算法对该信源进行哈夫曼编码。并计算其平均码长和编码效率。 调用matlab 哈夫曼编码函数进行哈夫曼编码，与人工编码结果做比较。 1. huffmandict 函数： 为已知概率分布的信源模型生成哈夫曼编解码索引表。
本科生实验报告 实验课程信息论与编码 学院名称信息科学与技术学院 专业名称通信工程 学生姓名 学生学号 指导教师谢振东 实验地点6C601 实验成绩 二〇一五年十一月二〇一五年十一月
实验一：香农（Shannon ）编码 一、实验目的 掌握通过计算机实现香农编码的方法。 二、实验要求 对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。 三、实验基本原理 给定某个信源符号的概率分布，通过以下的步骤进行香农编码 1、将信源消息符号按其出现的概率大小排列 )()()(21n x p x p x p ≥≥≥ 2、确定满足下列不等式的整数码长K i ； 1)(l o g )(l o g 22+-<≤-i i i x p K x p 3、为了编成唯一可译码，计算第i 个消息的累加概率 ∑ -== 1 1 )(i k k i x p p 4、将累加概率P i 变换成二进制数。 5、取P i 二进制数的小数点后K i 位即为该消息符号的二进制码。 四、源程序： #include int i,j; for(i=0;i 信息论实验报告 学生： 班级： 学号： 实验一香农编码一、程序设计的流程图 二、程序清单 #include #include aa=tem-1; } else { MM[i]+='0'; aa=tem; } } } string BB[N]; for(int i=0;i 实验报告 课程名称：信息论与编码姓名： 系：专 业：年 级：学 号：指导教 师：职 称： 年月日 目录 实验一信源熵值的计算 (1) 实验二Huffman 信源编码. (5) 实验三Shannon 编码 (9) 实验四信道容量的迭代算法 (12) 实验五率失真函数 (15) 实验六差错控制方法 (20) 实验七汉明编码 (22) 实验一信源熵值的计算 、实验目的 1 进一步熟悉信源熵值的计算 2 熟悉Matlab 编程 、实验原理 熵(平均自信息)的计算公式 q q 1 H(x) p i log2 p i log2 p i i 1 p i i 1 MATLAB实现：HX sum( x.* log2( x))；或者h h x(i)* log 2 (x(i )) 流程：第一步：打开一个名为“ nan311”的TXT文档，读入一篇英文文章存入一个数组temp，为了程序准确性将所读内容转存到另一个数组S，计算该数组中每个字母与空格的出现次数( 遇到小写字母都将其转化为大写字母进行计数) ，每出现一次该字符的计数器+1；第二步：计算信源总大小计算出每个字母和空格出现的概率；最后，通过统计数据和信息熵公式计算出所求信源熵值(本程序中单位为奈特nat )。 程序流程图： 三、实验内容 1、写出计算自信息量的Matlab 程序 2、已知：信源符号为英文字母(不区分大小写)和空格输入：一篇英文的信源文档。输出：给出该信源文档的中各个字母与空格的概率分布，以及该信源的熵。 四、实验环境 Microsoft Windows 7 五、编码程序 #include"stdio.h" #include 《信息论与信源编码》实验报告 1、实验目的 (1) 理解信源编码的基本原理； (2) 熟练掌握Huffman编码的方法； (3) 理解无失真信源编码和限失真编码方法在实际图像信源编码应用中的差异。 2、实验设备与软件 (1) PC计算机系统 (2) VC++6.0语言编程环境 (3) 基于VC++6.0的图像处理实验基本程序框架imageprocessing_S (4) 常用图像浏览编辑软件Acdsee和数据压缩软件winrar。 (5) 实验所需要的bmp格式图像（灰度图象若干幅） 3、实验内容与步骤 (1) 针对“图像1.bmp”、“图像2.bmp”和“图像3.bmp”进行灰度频率统计（即计算图像灰度直方图），在此基础上添加函数代码构造Huffman码表，针对图像数据进行Huffman编码，观察和分析不同图像信源的编码效率和压缩比。 (2) 利用图像处理软件Acdsee将“图像1.bmp”、“图像2.bmp”和“图像 3.bmp”转换为质量因子为10、50、90的JPG格式图像（共生成9幅JPG图像），比较图像格式转换前后数据量的差异，比较不同品质因素对图像质量的影响； (3) 数据压缩软件winrar将“图像1.bmp”、“图像2.bmp”和“图像3.bmp”分别生成压缩包文件，观察和分析压缩前后数据量的差异； (4) 针对任意一幅图像，比较原始BMP图像数据量、Huffman编码后的数据量（不含码表）、品质因素分别为10、50、90时的JPG文件数据量和rar压缩包的数据量，分析不同编码方案下图像数据量变化的原因。 4、实验结果及分析 (1)在VC环境下，添加代码构造Huffman编码表，对比试验结果如下： a.图像1.bmp： 实验一 绘制二进熵函数曲线（2个学时） 一、实验目的： 1. 掌握Excel 的数据填充、公式运算和图表制作 2. 掌握Matlab 绘图函数 3. 掌握、理解熵函数表达式及其性质 二、实验要求： 1. 提前预习实验，认真阅读实验原理以及相应的参考书。 2. 在实验报告中给出二进制熵函数曲线图 三、实验原理： 1. Excel 的图表功能 2. 信源熵的概念及性质 ()()[] ()[]())(1)(1 .log )( .) ( 1log 1log ) (log )()(10 , 110)(21Q H P H Q P H b n X H a p H p p p p x p x p X H p p p x x X P X i i i λλλλ-+≥-+≤=--+-=-=≤≤? ?????-===??????∑ 单位为 比特/符号 或 比特/符号序列。 当某一符号xi 的概率p(xi)为零时，p(xi)log p(xi) 在熵公式中无意义，为此规定这时的 p(xi)log p(xi) 也为零。当信源X 中只含有一个符号x 时，必有p(x)=1，此时信源熵H （X ）为零。 四、实验内容： 用Excel 和Matlab 软件制作二进熵函数曲线。根据曲线说明信源熵的物理意义。 （一） Excel 具体步骤如下： 1、启动Excel 应用程序。 2、准备一组数据p 。在Excel 的一个工作表的A 列（或其它列）输入一组p ，取步长为0.01，从0至100产生101个p （利用Excel 填充功能）。 3、取定对数底c，在B列计算H(x) ,注意对p=0与p=1两处，在B列对应位置直接输入0。Excel中提供了三种对数函数LN(x),LOG10(x)和LOG(x,c)，其中LN(x)是求自然对数，LOG10(x)是求以10为底的对数，LOG(x,c)表示求对数。选用c=2,则应用函数LOG(x,2)。 在单元格B2中输入公式：=-A2*LOG(A2,2)-(1-A2)*LOG(1-A2,2) 双击B2的填充柄，即可完成H(p)的计算。 4、使用Excel的图表向导，图表类型选“XY散点图”，子图表类型选“无数据点平滑散点图”，数据区域用计算出的H(p)数据所在列范围，即$B$1:$B$101。在“系列”中输入X值(即p值)范围，即$A$1:$A$101。在X轴输入标题概率，在Y轴输入标题信源熵。 （二）用matlab软件绘制二源信源熵函数曲线 p = 0.0001:0.0001:0.9999; h = -p.*log2(p)-(1-p).*log2(1-p); plot(p,h) 五、实验结果 信息论与编码实验一实验报告 学生姓名周群创 指导教师张祖平 学号0909110814 专业班级电子信息1101 实验一关于信源熵的实验 一、实验目的 1. 掌握离散信源熵的原理和计算方法。 2. 熟悉matlab 软件的基本操作，练习使用matlab 求解信源的信息熵。 3. 自学图像熵的相关概念，并应用所学知识，使用matlab 或其他开发工具求解图像熵。 4. 掌握Excel 的绘图功能，使用Excel 绘制散点图、直方图。 二、实验原理 1. 离散信源相关的基本概念、原理和计算公式 产生离散信息的信源称为离散信源。离散信源只能产生有限种符号。 随机事件的自信息量I（x i）为其对应的随机变量x i 出现概率对数的负值。即： I（x i）= -log2 p(x i) 随机事件X 的平均不确定度（信源熵）H（X）为离散随机变量x i 出现概 率的数学期望，即： H(X )=-∑p(x )I (x ) =-∑p(x ) log p(x ) 2. 二元信源的信息熵 设信源符号集X={0，1}，每个符号发生的概率分别为p(0)=p，p(1)=q， p+ q=1，即信源的概率空间为 则该二元信源的信源熵为： H(X) = - p log p –q log q = - p log p – (1- p) log (1- p) 即：H (p) = - p log p – (1- p) log (1- p) 其中0 ≤p ≤1 3. MATLAB 二维绘图 用matlab 中的命令plot(x, y)就可以自动绘制出二维图来。 例1-2，在matlab 上绘制余弦曲线图，y = cos x，其中0 ≤x ≤2。>>x=0:0.1:2*pi；%生成横坐标向量，使其为0，0.1，0.2，…，6.2 >>y=cos(x)；%计算余弦向量 >>plot(x,y) %绘制图形 4. MATLAB 求解离散信源熵 求解信息熵过程： 1) 输入一个离散信源，并检查该信源是否是完备集。 2) 去除信源中符号分布概率为零的元素。 3) 根据平均信息量公式，求出离散信源的熵。 5. 图像熵的相关知识 图像熵是一种特征的统计形式，它反映了图像中平均信息量的多少。图像的 实验报告 学院：专业：班级： 姓名：学号：实验日期： 实验名称： 实验一：唯一可译码判别准则的代码实现 实验二：霍夫曼编码的代码实现 实验目的： 实验一： 1.进一步熟悉唯一可译码判别准则； 2.掌握C 语言字符串处理程序的设计和调试技术。 实验二： 1.进一步熟悉Huffman 编码过程； 2.掌握C 语言递归程序的设计和调试技术。 实验仪器： 装有visual studio 2010 的电脑一台 实验原理： 实验一： 根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据类型并利用指针进行编程来实现算法。 算法：1、考察 C 中所有的码字，若Wi 是Wj 的前缀，则将对应的后缀作为一个尾随后缀码放入集合Fi+1 中； 2、考察C 和Fi 俩个集合，若Wi ∈C 是Wj∈F 的前缀或Wi ∈F 是Wj∈C 的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1 中； 3、F=∪Fi 即为码C 的尾随后缀集合； 4、若F 中出现了C 中的元素，算法终止，返回假（C 不是唯一可译码）；否 则若F 中没有出现新的元素，则返回真。 实验二： 1.将q 个信源符合按概率大小递减排列; 2.用“0,1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1 个符号的新信源，称为缩减信源s 1； 3.把缩减信源s1的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了q-2 个信源符号的缩减信源s 2； 4.依次继续下去，直至信源符号最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“0”和“1”表示； 5.然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即对应的码字。 实验内容与步骤： 实验一： 1.已知：信源符号数和码字集合C； 2.输入：任意的一个码，码字的个数和每个具体的码字在运行时从键盘输入； 3.输出：判决（是唯一可译码/不是唯一可译码）；循环（若继续判决则输入1 循环判决，否则输入0 结束运行）。 实验二： 1. 输入：信源符号个数r、信源的概率分布P； 2. 输出：每个信源符号对应的Huffman 编码的码字。 实验数据： 实验一源代码： #include 信息论与编码实验报告-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII 实验一关于硬币称重问题的探讨 一、问题描述： 假设有N 个硬币，这N 个硬币中或许存在一个特殊的硬币，这个硬币或轻 或重，而且在外观上和其他的硬币没什么区别。现在有一个标准天平，但是无刻度。现在要找出这个硬币，并且知道它到底是比真的硬币重还是轻，或者所有硬币都是真的。请问： 1）至少要称多少次才能达到目的； 2）如果N=12，是否能在3 次之内将特殊的硬币找到；如果可以，要怎么称？ 二、问题分析： 对于这个命题，有几处需要注意的地方： 1）特殊的硬币可能存在，但也可能不存在，即使存在，其或轻或重未知； 2）在目的上，不光要找到这只硬币，还要确定它是重还是轻； 3）天平没有刻度，不能记录每次的读数，只能判断是左边重还是右边重，亦或者是两边平衡； 4）最多只能称3 次。 三、解决方案： 1.关于可行性的分析 在这里，我们把称量的过程看成一种信息的获取过程。对于N 个硬币，他们 可能的情况为2N+1 种，即重（N 种），轻（N 种）或者无假币（1 种）。由于 这2N+1 种情况是等概率的，这个事件的不确定度为： Y=Log(2N+1) 对于称量的过程，其实也是信息的获取过程，一是不确定度逐步消除的过程。 每一次称量只有3 种情况：左边重，右边重，平衡。这3 种情况也是等概率 的，所以他所提供的信息量为： y=Log3 在K 次测量中，要将事件的不确定度完全消除，所以 K= Log(2N+1)/ Log3 根据上式，当N=12 时，K= 2.92< 3 所以13 只硬币是可以在3 次称量中达到 信息理论与编码实验指导书 电子与电气工程学院 罗晓琴编 实验要求 1、实验前认真阅读实验指导书的内容，并完成预习任务。 2、复习Matlab的相关知识，完成仿真。 3、要熟悉本次实验的任务。 4、实验过程中要认真记录实验结果，仿真结果需经指导教师审阅。 5、实验后每位同学要独立完成实验报告的内容。 目录 实验一离散信源的自信息量和熵 (3) 实验二最大离散熵定理 (6) 实验三费诺编码 (9) 实验四霍夫曼编码 (13) 实验五香农编码 (16) 实验一：计算离散信源的自信息量和熵 一、实验目的 1、熟悉离散信源的特点。 2、学习Matlab 仿真离散信源的方法。 3、学习离散信源自信息量和信源熵的计算方法。 4、熟悉 Matlab 编程。 二、实验设备 1、计算机 2、软件：Matlab 三、实验原理 本实验主要完成信源概率分布的自信息量以及信源熵的计算。 计算公式如下： 一个字符它所携带的信息量是和该字符出现的概率有关，概率可以表征自信息量的大小自信息的计算公式为： 2 1()log a I a p = 自信息量有两个含义： 第一、当事件发生前，表示该事件发生的不确定性； 第二、当事件发生后，标是该事件所提供的信息量． 自信息量的单位取决于对数所取的底，若以2为底，单位为比特，以e 为底，单位为奈特，以10为底，单位为哈特。 在通信系统中，通常取比特为单位，底数2略去不写。 由于自信息I(a)是一个随机变量，不能用来表征整个信源的不确定度。所以我们用平均自信息量来表征整个信源的不确定度。平均自信息量就是信源输出所有消息的自信息的数学期望，又称为信息熵、信源熵，简称熵。 熵（平均自信息）的计算公式为： 22111 ()log log q q i i i i i i H x p p p p ====-∑∑ 信息熵H （x ）是对信源的平均不确定性的描述。它从平均意义上来表征信 源的总体信息测度。对于某特定的信源，其信息熵是一个确定的数值。 信息熵具有如下三种物理意义。 第一，信息熵H （x ）是表示信源输出后，每个消息或符号所提供的平均信息量。 第二，信息熵H （x ）是表示信源输出前，信源的平均不确定性。 第三，信息熵H （x ）可表征变量X 的随机性。 由此可以看出，自信息量与信息熵的含义是不同的： （1）信息熵是表征信源本身统计特性的一个物理量，它表示信源的平均不确定性，是信源输出的每一个消息所能提供的平均信息量；自信息量表示的是每一个消息的信息量度。 信息论与编码实验指导书 1 课程实验目的 本课程是一门实践性很强的专业课和核心课程，根据课程理论教学的需要安排了6学时的配套实验教学，主要内容涉及信息度量的计算方法、典型信源编码方法、典型信道容量计算方法和数据压缩方法四个实验，这四个实验的开设一方面有助于学生消化、巩固课程理论教学的知识，另一方面又可培养学生实践动手能力，同时为后续课程做好准备。 2 课程实验要求 课程实验准备要求 （1）课程实验主要为设计性实验，要求学生熟悉掌握在VC环境下编写和调试C++程序的方法。 （2）要求学生在实验前复习实验所用到的预备知识。可以查阅教材或者相关的参考资料，这需要学生有自主的学习意识和整理知识的能力。 （3）根据实验项目，设计相关的数据结构和算法，再转换为对应的书面程序，并进行静态检查，尽量减少语法错误和逻辑错误。上机前的充分准备能高效利用机时，在有限的时间内完成更多的实验内容。 课程实验过程要求 （1）生成源代码。将课前编写好的书面代码，利用VC自带的编辑器尽快输入为转换为源代码； （2）程序调试和软件测试。要求学生熟练掌握调试工具，调试正确后，认真整理源程序和注释，给出带有完整注释且格式良好的源程序清单和结果。 （3）完成实验报告。根据实验内容和完成情况，按照附件1给定的格式完成课程实验报告的编写。 课程实验报告要求 在每次课程实验后要及时进行总结和整理，并编写课程实验报告。报告格式按江西蓝天学院实验报告纸格式填写。 实验一二维随机变量信息熵的计算 [实验目的] 掌握二变量多种信息量的计算方法。 [实验学时] 2学时 [实验准备] 1．熟悉二变量多种信息量的计算方法，设计实验的数据结构和算法； 2．编写计算二维随机变量信息量的书面程序代码。 [实验内容及步骤] 离散二维随机变换熵的计算 说明： （1）利用random函数和归一化方法构造一个二维离散随机变量（X，Y）； （2）分别计算X与Y的熵、联合熵、条件熵：H（X）、H（Y）、H（X,Y）H（X|Y）、I（X|Y）； （3）对测试通过的程序进行规范和优化； （4）编写本次实验的实验报告。 桂林理工大学 实验报告班级：通信09-2班学号：3090731219 姓名：崔泽 实验名称：计算离散信源的熵日期：2011年5月10日 一、实验目的 1、熟悉离散信源的特点 2、熟悉离散信源平均信息量的计算方法 二、实验内容 1、写出计算自信息量的Matlab程序 2、写出计算离散信源平均信息量的Matlab程序 3、掌握二元离散信源的最大信息量与概率的关系 4、完成习题 三、习题 1、程序： x=[0.5 0.25 0.125 0.125 ]; y=[0.875 0.125]; b=-x.*log2(x) H1=sum(b) c=-y.*log2(y) H1=sum(c) X=-log2(x) Y=-log2(y) 程序运行结果： b = 0.5000 0.5000 0.3750 0.3750 H1 = 1.7500 c = 0.1686 0.3750 H1 = 0.5436 X = 1 2 3 3 Y =0.1926 3.0000 由上面结果可以看出，甲信源的熵为： 1.7500 已信源的熵为：0.5436 甲地各种天气的信息量晴，云，大雨，小雨分别为1 2 3 3 已地各种天气的信息量晴，小雨分别为0.1926 3.0000 2、Matlab程序： x=[1/4 1/8 1/8 3/16 5/16]; a=-x.*log2(x); H=sum(a) 程序运行结果： H = 2.2272 3、Matlab程序： X=[1/4 1/8 1/8 1/2]; a=-x.*log2(x); H=sum(a) 程序运行结果： H = 1.7500 3、Matlab程序： p=0.00011:0.1:0.99999; x=[p,1-p]; a=-x.*log2(x); H=sum(a) plot(x,a) p H H = 7.0879 当p呈等概率分布时，平均信息量达到最大值7.0879 信息论与编码实验报告 课程名称：信息论与编码 实验名称：霍夫曼编码 班级： 学号： 姓名： 实验目的 1、熟练掌握Huffman编码的原理及过程，并熟练运用； 2、熟练运用MATLAB应用软件，并实现Huffman编码过程。 一、实验设备 装有MATLAB应用软件的PC计算机。 二、实验原理及过程 原理： 1、将信源符号按概率从大到小的排列，令P （X1）>=P(X2)>=P(X3)......P(Xn) 2、给两个概率最小的信源符号P（Xn-1）和P（Xn）各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。 3、将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含（n-2）个符号的缩减信源S2. 4、重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。 过程： 用MATLAB编写代码实现Huffman编码其程序为： %哈夫曼编码的MA TLAB实现（基于0、1编码）： clc; clear; A=[0.3,0.2,0.1,0.2,0.2];信源消息的概率序列 A=fliplr(sort(A));%按降序排列 T=A; [m,n]=size(A); B=zeros(n,n-1);%空的编码表（矩阵） for i=1:n B(i,1)=T(i);%生成编码表的第一列 end r=B(i,1)+B(i-1,1);%最后两个元素相加 T(n-1)=r; T(n)=0; T=fliplr(sort(T)); t=n-1; for j=2:n-1%生成编码表的其他各列 for i=1:t B(i,j)=T(i); end K=find(T==r); B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在 游程编码实现有效性提高的原理及通用编码的思想 康乐203201505020 摘要：信源编码的目的是提高信息传输效率，其思想是去除消息中的冗余成分。在无失真的信源编码中，根据信源的统计特性进行编码称为统计编码，而在信源统计特性未知的情况下，就需要一种新的编码方法，称之为通用编码。本文对统计编码中的游程编码进行了分析，说明其有效性，给出其具有有效性的原理论述，对游程编码的截断效应进行了仿真；同时分析了通用编码的存在性与构造方法，还以字典码为例进行了仿真。 关键词：信源编码游程编码通用编码字典码 一、信源编码概述 通信的根本问题是将信源的输出在接收端精确的或近似的重现出来。为此需要解决两个问题。其一是信源的输出应如何描述，及如何计算它产生的信息量；其二是如何表示信源的输出，即信源编码问题。由于信源可以根据信息输出的形式分为离散信源和连续信源，因此信源编码也就可以分为离散信源和连续信源。 根据通信的要求，可以将信源编码分为无失真信源编码和限定失真的信源编码。若要求精确的重现信源的输出，就要保证信源产生的 全部信息无损的传递给信宿，这时的信源编码就是无失真信源编码。许多实际情况下，并不要求完全精确地复制出信源的输出，而且在有干扰的情况下，这也是不可能的。一般对信源-信宿要定出可接收准则或保真度准则，这就是限定失真的信源编码。 离散信源的输出可以用如下符号序列表示： 21012,,,,,U U U U U -- 其中l U 表示在第l 时刻产生的符号，l 为整数。l U 为一随机变量，它 在有限字母集{}1,k A a a =中选取。如果使用D 字母的集合 {}1,d B b b =作为码表，那么如果组成码字的码符号数目相等，我们就称之为等长编码，否则称之为非等长编码。 非等长编码则可以根据编码是否依赖信源的统计特性分为统计编码与通用编码。 二、 游程编码 2.1 游程编码概念 游程编码（RLC, Run Length Coding ），又称“运行长度编码”或“行程编码”，是一种统计编码，该编码属于无损压缩编码，是栅格数据压缩的重要编码方法。 游程编码中的游程是指字符序列中各个字符连续重复出现而形成的字符串长度，编码方法是将字符序列映射成字符串长度和位置的标志序列，那么对于M 元序列： 011{,,,}M u u u - 中南大学 信息论与编码实验报告 选题：费诺编码 学生姓名： 学号： 专业班级：通信工程 指导老师： 学院：信息科学与工程学院 时间： 2015 目录 一、实验目的 二、实验原理 费诺编码思想 费诺编码流程图 三、实验内容 四、实验要求 五、代码调试结果 六、心得体会 七、程序源代码 一实验目的 1. 掌握费诺编码的原理和过程。 2. 熟悉 C/C++语言，练习使用C/C++实现香农码和Huffman 编码。 二、实验原理 费诺编码思想 设有离散无记忆信源 ∑==??????n i i n n x p x p x p x p x x x 1 21211)(,)(.....)()(..... 1.按信源符号的概率从大到小的顺序排队 不妨设 ) (......)()(21n x p x p x p ≥≥≥ 2.将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。 3.将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。 4.如此重复，直至每个组只剩下一个信源符号为止。 5.信源符号所对应的码字即为费诺码。 例：有一单符号离散无记忆信源 ??????=??????04.008.016.018.022.032.0)(654321 x x x x x x X P X 对该信源编二进制费诺码 )i /(35.2)(gn s bit X H = m L K R 2log = %92.97) (== R x H η ∑===61 ) /(4.2)(i i i k x p K 符号比特 费诺编码流程图 本科生实验报告 实验课程信息理论与编码 学院名称信息科学与技术学院 专业名称 学生姓名 学生学号 指导教师 实验地点 实验成绩 二〇一六年九月----二〇一六年十一月 填写说明 1、适用于本科生所有的实验报告（印制实验报告册除外）； 2、专业填写为专业全称，有专业方向的用小括号标明； 3、格式要求： ①用A4纸双面打印（封面双面打印）或在A4大小纸上用蓝黑色水笔书写。 ②打印排版：正文用宋体小四号，1.5倍行距，页边距采取默认形式（上下2.54cm， 左右2.54cm，页眉1.5cm，页脚1.75cm）。字符间距为默认值（缩放100%，间距：标准）；页码用小五号字底端居中。 ③具体要求： 题目（二号黑体居中）； 摘要（“摘要”二字用小二号黑体居中，隔行书写摘要的文字部分，小4号宋体）； 关键词（隔行顶格书写“关键词”三字，提炼3-5个关键词，用分号隔开，小4号黑体)； 正文部分采用三级标题； 第1章××(小二号黑体居中，段前0.5行) 1.1 ×××××小三号黑体×××××（段前、段后0.5行） 1.1.1小四号黑体（段前、段后0.5行） 参考文献（黑体小二号居中，段前0.5行），参考文献用五号宋体，参照《参考文献著录规则（GB/T 7714－2005）》。 实验一：香农（Shannon ）编码 一、实验目的 掌握通过计算机实现香农编码的方法。 二、实验要求 对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。 三、实验基本原理 给定某个信源符号的概率分布，通过以下的步骤进行香农编码 1.将信源消息符号按其出现的概率大小排列 )()()(21n x p x p x p ≥≥≥ 2．确定满足下列不等式的整数码长K i ； 1)(lo g )(lo g 22+-<≤-i i i x p K x p 3．为了编成唯一可译码，计算第i 个消息的累加概率 ∑-==1 1 )(i k k i x p p 4．将累加概率P i 变换成二进制数。 5．取P i 二进制数的小数点后K i 位即为该消息符号的二进制码。 四、实验内容 1.对给定信源? ?????=????? ?01.01.015.017.018.019.02.0)(7654321 x x x x x x x X q X 进行二进制香农编码。 2.对给定信源??????=????? ?05.010.015.020.025.025.0)(654321x x x x x x X q X 进行二进制香农编码。 3.自已选择一个例子进行香农编码。 五、实验设备 PC 计算机 ，C++ 信息论基础 实验报告 专业：电子信息工程 姓名： 班级/学号：电信1002/ 指导老师：李红莲 实验一：信息熵、信道容量的计算 一、实验目的 掌握使用计算机计算信息熵、信道容量的方法。 二、实验原理 1．参照教材（焦瑞莉等编著《信息论基础教程》）第14页式（2-16）理解信息熵的定义 2．参照教材（焦瑞莉等编著《信息论基础教程》）第68页式（3-15）理解信道容量的定义 三、实验方法与实验步骤 （一）参照教材第215页信源熵程序建立文件entropy.m （二）建立文件exercise2_3_1.m通过调用entropy.m计算教材第69页练习2.3（1）（参考答案：0.81比特） （三）参照教材第215页离散无记忆信道容量的迭代计算程序建立文件channelcap.m （四）建立文件exercise3_2_b.m通过调用channelcap.m计算教材第92页练习3.2（b）（参考答案：0.0817比特） 四．源程序代码 1）function H=entropy(P,r) if(~isempty(find(P<=0))) error('Not a prob.Vector,negative component'); end if(abs(sum(P)-1)>10e-10) error('Not aprob vetor,component do not add up to 1'); end H=(sum(-P.*log2(P)))/(log2(r)+eps); clc; H=entropy([1/4,3/4],2 2）function [CC,Paa]=channelcap(P,k) 信息论与编码基础实验报告 汉明码编译码 信 息 论 与 编 码 实 验 报 告 班级： 姓名： 学号： 实验一 绘制二进熵函数曲线（2个学时） 一、实验目的： 1. 掌握Excel 的数据填充、公式运算和图表制作 2. 掌握Matlab 绘图函数 3. 掌握、理解熵函数表达式及其性质 二、实验要求： 1. 提前预习实验，认真阅读实验原理以及相应的参考书。 2. 在实验报告中给出二进制熵函数曲线图 三、实验原理： 1. Excel 的图表功能 2. 信源熵的概念及性质 ()()[]()[]()) (1)(1 .log )( .) ( 1log 1log ) (log )()(10 , 110)(21Q H P H Q P H b n X H a p H p p p p x p x p X H p p p x x X P X i i i λλλλ-+≥-+≤=--+-=-=≤≤???? ?? -===???? ??∑ 四、实验内容： 用Excel 或Matlab 软件制作二进熵函数曲线。 具体步骤如下： 1、启动Excel 应用程序。 2、准备一组数据p 。在Excel 的一个工作表的A 列（或其它列）输入一组p ，取步长为0.01，从0至100产生101个p （利用Excel 填充功能）。 3、取定对数底c ，在B 列计算H(x) ,注意对p=0与p=1两处，在B 列对应位置直接输入0。Excel 中提供了三种对数函数LN(x),LOG10(x)和LOG(x,c)，其中LN(x)是求自然对数，LOG10(x)是求以10为底的对数，LOG(x,c)表示求对数。选用c=2,则应用函数LOG(x,2)。 在单元格B2中输入公式：=-A2*LOG(A2,2)-(1-A2)*LOG(1-A2,2) 双击B2的填充柄，即可完成H(p)的计算。 4、使用Excel 的图表向导，图表类型选“XY 散点图”，子图表类型选“无 《信息与编码理论》上机实验指导书———————应用MATLAB软件实现 UPC通信工程系 前言 本实验系列是采用MATLAB软件，主要针对《信息论基础》课程中的相关内容进行的实验。 MATLAB是一完整的并可扩展的计算机环境，是一种进行科学和工程计算的交互式程序语言。它的基本数据单元是不需要制定维数的矩阵，它可直接用于表达数学的算式和技术概念，解决同样的数值计算问题，使用MATLAB要比使用Basic、Fortran和C语言等提高效率许多倍。MATLAB还是一种有利的教学工具，在大学的线性代数课程以及其它领域的高一级课程的教学中，已称为标准的教学工具。 该指导书共安排了4个实验，现就一些情况作简要说明： 各实验要求学生在MATLAB系统上尽量独立完成，弄懂。实验内容紧扣课程教学内容的各主要基本概念，希望同学们在完成每个实验后，对所学的内容起到巩固和加深理解的作用。 每个实验做完后必须交一份实验报告。 恳请各位实验老师和同学在实验中提出宝贵意见，以利于以后改进提高。 目录 实验一离散信源及其信息测度 (3) 实验二离散信道及其容量 (6) 实验三无失真信源编码 (8) 实验四有噪信道编码 (10) 附录部分常用MATLAB命令 (12) 实验一 离散信源及其信息测度 一、[实验目的] 离散无记忆信源是一种最简单且最重要的信源，可以用完备的离散型概率空间来描述。本实验通过计算给定的信源的熵，加深对信源及其扩展信源的熵的概念的理解。 二、[实验环境] windows XP,MATLAB 三、[实验原理] 信源输出的各消息的自信息量的数学期望为信源的信息熵，表达式如下 1()[()]()log ()q i i i H X E I xi p x p x ===-∑ 信源熵是信源的统计平均不确定性的描述，是概率函数()p x 的函数。 四、[实验内容] 1、有条100字符英文信息，假定其中每字符从26个英文字母和1个空格中等概选取，那么每条信息提供的信息量为多少？若将27个字符分为三类，9个出现概率占2/7,13个出现概率占4/7，5个出现占1/7，而每类中符号出现等概，求该字符信源的信息熵。 2、二进制通信系统使用0、1,由于存在失真，传输会产生误码，用符号表示下列事件：u0:一个0发出；u1:一个1发出；v0:一个0收到；v1:一个1收到；给定下列概率：p(u0)=1/2,p(v0|u0)=3/4,p(v0|u1)=1/2。求：(a)已知发出一个0，求收到符号后得到的信息量；(b)已知发出的符号，求收到符号后得到的信息量； 3、给定离散无记忆信源X ，其概率空间为 010.70.3X P ????=???? ???? 求该信源的熵和其二次、三次扩展信源的熵。(编写一M 函数文件： function [H_X1,H_X2,H_X3]=t03(X1,P1) %t03 求信源和其二次、三次扩展信源的熵 %输入为X1,P1,分别为信源符号和概率阵 %输出为原离散信源的熵H_X1和二次、三次扩展信源的熵H_X2、H_X3信息论实验报告-
信息论与编码实验报告材料
《信息论与信源编码》实验报告
信息论与编码实验报告
实验1_信息论相关实验实验报告
信息论实验报告
信息论与编码实验报告
信息论实验指导书
信息论与编码实验指导书
信息论实验报告
信息论霍夫曼编码
信息论实验报告
信息论编码实验报告-费诺编码附源代码
信息论与编码实验报告材料
信息论实验报告李红莲实验一
信息论与编码实验报告
学院： 队别： 专业： 姓名： 学号：
电子科学与工程学院 二队 06 级 通信工程专业 曹务绅 200604015014
国防科学技术大学电子科学与工程学院
1
一、 实验目的
通过本次实验的练习， 进一步巩固了信道编码的基本原理， 掌握了Hamming 码编译码方法，提高了软硬件操作能力，培养了实验人员理论结合实践的能力。
二、 实验原理
（一）汉明码： 汉明码是在原编码的基础上附加一部分代码，使其满足纠错码的条件。它属 于线性分组码， 由于汉明码的抗干扰能力较强， 至今仍是应用比较广泛的一类码。 它具有以下特征： 码 长： n = 2m ? 1
信息位数： k = 2 m ? m ? 1 监督码位： r = n ? k = m 最小码距： d = 3 纠错能力： t = 1 （二）汉明码的编码： 在(n，k)汉明码中， (n-k)个附加的监督码元是由信息码元的线性运算产生 的。码长为 n,信息码元长度为 k，2k 个码组构成 n 维线性空间中的一个 k 维子 空间，编码的实质就是要在 n 维空间中，找出一组长为 n 的 k 个线性无关的矢 量 g0 g1 g k ?1 ，使得每个码组 c 都可以表示为 k 个矢量的线性组合，即 c0 ] = mk ?1 g 0 + mk ? 2 g1 + m0 g k ?1 其中， m i∈{0，1}， i=0，
c = [cn ?1 cn ? 2
1，……，k-1。将上式写成矩阵形式得
2 信息论与编码实验书
《信息论》实验指导书— 应用MATLAB软件实现
相关主题
文本预览