信息论实验报告
游程编码实现有效性提高的原理及通用编码的思想
康乐 [1**********]0
摘要：信源编码的目的是提高信息传输效率，其思想是去除消息中的冗余成分。在无失真的信源编码中，根据信源的统计特性进行编码称为统计编码，而在信源统计特性未知的情况下，就需要一种新的编码方法，称之为通用编码。本文对统计编码中的游程编码进行了分析， 说明其有效性，给出其具有有效性的原理论述，对游程编码的截断效应进行了仿真；同时分析了通用编码的存在性与构造方法，还以字典码为例进行了仿真。
关键词：信源编码 游程编码 通用编码 字典码
一、 信源编码概述
通信的根本问题是将信源的输出在接收端精确的或近似的重现出来。为此需要解决两个问题。其一是信源的输出应如何描述，及如何计算它产生的信息量；其二是如何表示信源的输出，即信源编码问题。 由于信源可以根据信息输出的形式分为离散信源和连续信源，因此信源编码也就可以分为离散信源和连续信源。
根据通信的要求，可以将信源编码分为无失真信源编码和限定失真的信源编码。若要求精确的重现信源的输出，就要保证信源产生的
全部信息无损的传递给信宿，这时的信源编码就是无失真信源编码。许多实际情况下，并不要求完全精确地复制出信源的输出，而且在有干扰的情况下，这也是不可能的。一般对信源-信宿要定出可接收准则或保真度准则，这就是限定失真的信源编码。 离散信源的输出可以用如下符号序列表示：
U2,U1,U0,U1,U2,
其中Ul表示在第l时刻产生的符号，l为整数。Ul为一随机变量，它在有限字母集Aa1,ak中选取。如果使用D字母的集合
Bb1,bd作为码表，那么如果组成码字的码符号数目相等，我们就称之为等长编码，否则称之为非等长编码。
非等长编码则可以根据编码是否依赖信源的统计特性分为统计编码与通用编码。
二、 游程编码 2.1 游程编码概念
游程编码（RLC, Run Length Coding），又称“运行长度编码”或“行程编码”，是一种统计编码，该编码属于无损压缩编码，是栅格数据压缩的重要编码方法。
游程编码中的游程是指字符序列中各个字符连续重复出现而形成的字符串长度，编码方法是将字符序列映射成字符串长度和位置的标志序列，那么对于M元序列：
{u0,u1,,uM1}
输入的消息序列U{ui,,ur,ur,ur,uk}中的符号Ur的游程长度L(r)就是其游程长度。
例如：[***********]1111111
行程编码为：（5，6）（7，5）（3，3）（2，4）（1，7）。可见，行程编码的位数远远少于原始字符串的位数。
2.2 游程编码有效性
行程编码是连续精确的编码，在传输过程中，如果其中一位符号发生错误，即可影响整个编码序列，使行程编码无法还原回原始数据。
游程长度在栅格加密时，数据量没有明显增加，压缩效率较高，且易于检索、叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码和解码运算，增加处理和操作时间的情况。
举例来说，一组输入序列"AAAABBBCCDEEEE"，由4个A、3个B、2个C、1个D、4个E组成，经过游程编码可将序列压缩为4A3B2C1D4E，即由14个单位转成10个单位长度。
简言之，其优点在于将重复性高的数据量压缩成小单位；然而，其缺点在于─若该字符出现频率不高，可能导致压缩结果数据量比原始序列大，例如：原始序列"ABCDE"，压缩结果为"1A1B1C1D1E"即由5个单位转成10个单位长度。
2.3 游程编码有效性原理
由于游程编码并没有一个完备的数学公理体系作为支撑，因此想要分析它的有效性就要分类进行，本文只讨论了二元游程编码以及多元游程编码中的冗余位编码的有效性原理。 冗余位编码 对于M元序列：
{u0,u1,,uM1}
当M≥3时，只凭借游程长度L无法实现可逆的编码，需要添加其他
符号。当M很大时，附加标志可能抵消压缩编码的好处。但是有一种特殊情况,当输入序列为：
Ux1x2x3xm1yyyyyyxm11xm2yyyy 经过游程编码可以分解为以下两个序列：
L1111000000110000
U'x1 x2 x3 xm1 xm11xm2
即将一个多元序列分解为一个二元序列和一个缩减多元序列，从而提高了编码效率。 二元游程编码
对于二元相关信源来说，对其N次扩展信源编码才能提高编码效率。这将产生符号数剧增，码字多，译码复杂，符号间相关性没有利用等等一系列问题。
而对于二元相关信源，游程编码可以只凭借游程长度L实现可逆的编码，下面给出有效性的证明：
假设游程编码将二元相关信源编码为黑游程与白游程，分别对应 1与0的长度。那么可以得到白游程熵：
lw为白游程长度，L为白游程最大长度
由信源编码定理：
Lw为白游程平均码长。
所以白游程长的平均值为：
联立上述几式可得：
白像素熵值为：
白像素平均码长为：
带入（4）式中可得：
同理对黑游程也可以得到：
每个像素的熵值：
……..………..…….(8)
每个像素平均码长：
将（5）乘以Pw加上（7）乘以PB：
可以看出二元相关信源编码后的平均码长仍以信源熵为极限，所以压缩效率较高。
三、 通用编码 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的码字，然后结束编码。
图 1 字典码编码流程图
译码
LZ的译码过程与之相反，将当前码字W对应的前缀输出，再输出当前编码对应符号C。从空集开始更新字典，不断添加新的缀-符串。是边生成字典，边译码的过程。 译码算法
步骤1： 步骤2： 步骤3： 步骤4：C。
步骤5： 步骤6： 在开始时词典是空的。
当前码字W ：=码字流中的下一个码字。 当前字符C ：= 紧随码字之后的字符。 输出当前码字的缀-符串到字符流，然后输出字符把W+C添加到词典中。
判断码字流中是否还有码字要译码 (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.