游程编码是适用于相关信源的有效编码方法,尤其适用于二元相关信源。游程编码已在图文传真、图像传输等实际工程中得到应用。工程中,游程编码常与其他编码方法混合使用。

游程定义:指字符序列中各种字符连续地重复出现而形成的字符串的长度,又称游程长度或游长。

游程编码:将字符序列映射成串的字符、串的长度和串的位置的标志序列。游程编码适用于一维字符序列,也适用于二维字符序列。

二元相关信源,仅输出0游程和1游程。

二元相关信源的0游程和1游程总是交替出现。游程长度的取值:1,2,3,…,直至无穷值。可规定二元序列总是从0游程开始。游程长度常用自然数标记,所以,游程序列是自然数序列。且这种游程映射是可逆的,是无失真的。

【例7.10】某二元序列为:00001100011111100000001…,可以映射成游程序列:42367…;

规定从0游程开始,由上面的游程序列极易恢复二元序列,也包括序列最后一个1符号。因为L(0)=7的游程后面必定是符号1。

一般为二元数字信道,还需将游程序列变换成二元码字序列,即对游程长度进行二次编码。二次编码可以采用:等长编码或变长编码。本例用等长游程编码,因最大游程长度为7,三位码元编码。本例码字序列为:100,010,011,110,111,…。也可用变长游程编码,即对游程长度再进行其他变长编码,如Huffman编码,以进一步提高通信效率。需要测定0游程、1游程长度的概率分布,再设计变长码。一般,0游程和1游程长度分别编码,建立两种码表,且两码表中一般码字是不同的。0游程与1游程的两码表之间的码字不一定要满足非延长码的前缀条件。理论上,游程长度可以从1至无限大。但可采用一定技术,用有限码表实现编码。

给出一种编码方法(设l为游程长度):(www.daowen.com)

(1)选取适当n值,将l=1,2,…,2n长的2n个游程进行Huffman编码,其中2n长游程码为C。

(2)l＞2n的游程长度用2n长游程码C来处理。

方法:将2n＜l＜2n+1的2n个游程用C加n位的自然码A表示。A代表余数,用以区分2n～2n+1之间的不同长度。

(3)将2n+1＜l＜2n+2的2n个游程,就用两个CA为码字。

依次类推,可得到所有游程长度的一一对应的码字。0游程和1游程的码表中,为2n的码字C必须不同,且必须与码表中的其他码字,都满足非延长码的前缀条件,以保证译码。

η0,η1——0游程、1游程长度的Huffman码的编码效率。由编码效率定义,可得0和1游程的平均码长为

可推导出对应的二元序列的编码效率

假设η0＞η1可以证明　　　η0＞η＞η1