游程编码及MH编码

1、游程编码及MH编码游程编码内容游程编码的概念二元相关信源的游程编码二元游程序列的概率特性多元相关信源的游程编码 又称“游程长度编码”、“行程编码” 是将这种字符串序列映射成串的字符串的长度和串的位置的标志序列。游程编码的概念游程编码RLC游程（Run-Length，缩写RL） 又称游程长度或游长，指的是字符序列中各个字符连续重复出现而形成字符串的长度二元相关信源的游程编码“0”游程： 连续出现“0”符号的段“1”游程： 连续出现“1”符号的段“0”游程长度L(0)“1”游程长度L(1)游程序列： 用自然数标记的游程长度，映射成交替出现的游程长度序列例如某二元序列：二元相关信源的游程编码1000

2、0000137621游程序列：011001010110111等长游程编码：二元相关信源的游程编码游程越长，出现的概率越小；游程长度趋于无穷时，其出现的概率也趋向于零。按照霍夫曼编码的规则，概率越小，码长越长，但小概率的码字对平均码长的影响较小。 所以在实际应用时，对长游程一般采用截断处理的方法，将大于一定长度的长游程统一用等长码编码。二元相关信源的游程编码截断处理：选取适当的n值，游程长度定为1,2, , ,大于 的都用游程为 的码字来处理。按概率大小进行霍夫曼编码，得到相应的码字，游程为 的码字为C。 L ,需用两个或者两个以上的CA为码字。二元相关信源的游程编码L= C0000截断处理：n

3、个L= L= L=/ C0001 C11 11C0000C0000n个n个n个n个L= C0000C1111n个n个二元游程序列的概率特性和编码效率设二元无记忆信源“0”和“1”的概率分别为 和 ，可求得L(0)和L(1)的概率 若下一个符号是1，则L(0)=1，若下一个符号是“0”，再下一个符号是“1”，则L(0)=2，二元游程序列的概率特性和编码效率以此类推：易验证：二元游程序列的概率特性和编码效率熵：二元游程序列的概率特性和编码效率熵：同理：二元游程序列的概率特性和编码效率平均游程长度：同理：二元游程序列的概率特性和编码效率 原信源的二元序列是由“0”游程和“1”游程交替出现而组成的，所

4、以二元序列的熵应等于两个游程长度信源熵之和除以它们的平均游程长度之和。二元游程序列的概率特性和编码效率对于有记忆的二元信源，假设“0”游程长度的霍夫曼编码效率为 ，“1”游程长度的霍夫曼编码效率为 ，则平均码长为 则两个游程的信息熵之和除以平均码长之和得到对应的二元序列的编码效率 假设 ，则有 多元相关信源的游程编码多元序列也存在相应的游程序列 多元序列变换成游程序列再进行压缩编码没有多大意义 游程编码只适用于二元序列，对于多元信源，一般不能直接利用游程编码 MH编码MH编码内容MH编码的概念MH编码的方法MH编码的特点MH编码MH编码是用于黑白二值文件传真的数据压缩。文件传真是指一般文件、图

5、纸、手写稿、表格、报纸等文件的传真。它们是黑白二值的，即信源是二元信源q=2。MH码分别对“黑”、“白”的不同游程长度进行霍夫曼编码，形成黑、白两张霍夫曼码表。编译码通过查表进行。规定每行标准像素为1728个，根据统计结果可知，黑白游程长度在063的情况居多，因此MH码的码字分为结尾码（或称终端码）和组合码（或称形成码）两种MH编码MH编码方法： 1.黑白游程分别对应不同的编码表； 2.游程长度在063时，码字直接用相应的终端码（结尾码）表示； 例：一行中连续19个白，接着连续30个黑， 即白游程长度为19，黑游程长度为30.查表 得码字为0001100 0MH编码MH编码方法： 3.游程长度

6、在641728，用一个组合码加上一个结尾码为相应码字； 例：白游程长度为65（=64+1）,查表得码字， 11011000111 黑游程长度为856（=832+24），查表得码字， 01MH编码MH编码MH码表（二),组合基干码RL长度白游程码字黑游程码字RL长度白游程码字黑游程码字64110110000001111960011010100112810010010240110101010019201011111088011010110012561115201101011110320112160110110001138401280011011001104481134401101101011512

7、00140801101101100576011472010011000016401015360100110011070401100110011160001001101011768011001101001664011000008320110100100117280100110110189601101001110EOL11MH编码MH编码方法： 4.规定每行都从白游程开始，若实际出现黑游程开始的话，则在行首加上零长度白游程码字，每行结束用一个结束码（EOL）； 5.每行恢复成1728个像素，否则有错； 6.每页文件开始第一个数据前加一个结束码。每页尾连续使用6个结束码表示结尾；MH编码MH编码方法

8、：7.为了传输时实现同步操作，规定T为每编码行的最小传输时间。一般规定T最小为20ms，最大为5s。若编码行传输时间小于T，则在结束码之前填以足够的“0”码元（称填充码）。MH编码例题：设某页传真文件中某一扫描行的像素点如下图所示，求，(1）该扫描行的MH编码； （2）编码后的比特总数； （3）本编码行的数据压缩比。17个（白）5黑55白10黑1641白解：（1）10101100111010011010（2）将码字数一下，答案就是 54 bit（3）压缩前数据总比特： 数据压缩比：1600白+ 41白+EOL17+5+55+10+1641=1728 bit1728:54=32MH编码传真信息传输格式MH编码平均码长 设 为白游程长度为i的概率， 为黑游程长度为i的概率，可计算白游程长度信源的熵为MH编码令白游程信源中平均白游程长度为令每个黑像素的熵值为 ，每个黑像素所需的平均码长为 ，同理可得 MH编码设 为白像素出现的概率， 为黑像素出现的概率。经过对黑、白的统计平均，得每个像素的熵值 每个像素所需的平均码长 为 则MH编码