游程编码：适用于相关信源的高效方法

游程编码是一种适用于相关信源的有效编码方法，尤其适用于二元相关信源。游程编码已在图文传真、图像传输等实际通信工程中得到应用。有时工程中常常将游程编码和其他编码方法混合使用，能获得更好的压缩效果。

游程（Run-Length，RL）指的是信源输出的字符序列中各种字符连续地重复出现而形成的字符串的长度，又称游程长度或游长。游程编码就是将这种字符序列映射成串的字符、串的长度和串的位置的标志序列。知道了串的字符、串的长度和串的位置的标志序列，就可以完全恢复出原来的字符序列。所以，游程编码不但适用于一维字符序列，也适用于二维字符序列。

对于二元相关信源，其输出只有两个符号，即0和1。在信源输出的一维二元序列中，连续出现0符号的这一段称为0游程，连续出现1符号的这一段称为1游程。对应段中的符号个数就是0游程长度和1游程长度，记为l（0）和l（1）。

因为信源输出是随机的，所以游程长度是随机变量，其取值可以是1，2，3，…，直至无穷值。又在输出的二元序列中，0游程和1游程总是交替出现。若规定二元序列总是从0游程开始，这样，就只需对串的长度（即游程长度）进行标记，然后就可以将信源输出的任意二元序列一一对应地映射成交替出现的游程长度的标志序列。

游程长度通常用自然数标记，所以就映射成交替出现的表示游程长度的自然数序列，简称游程序列。这种映射是可逆的、无失真的。

【例4.18】

某二元序列为00001100011111100000001…，可以映射成游程序列42367…；

由于已规定二元序列从0游程开始，则当已知上面的游程序列后极易恢复出原来的二元序列，也包括序列最后一个1符号。因为L（0）=7的游程后面必定是符号1。

一般传输信道为二元数字信道，所以还需要将自然数标记的游程序列变换成二元码字序列，即对游程长度进行二次编码。二次编码可以采用等长编码或变长编码。

若采用等长游程编码，就是将游程长度编成二进制自然数。假设例4.18中最大游程长度为7，则用三位码元来编码，例4.18的码字序列为100，010，011，110，111，…。可见，信源序列得到压缩。当然，游程长度越长及长游程频繁出现时压缩效率就会越高。

也可以采用变长游程编码，将游程长度这种多元序列再进行其他变长编码，如Huffman编码，就能进一步压缩信源，提高通信效率。当然，首先要测定0游程长度和1游程长度的概率分布，即以游程长度为元素，构造一个新的多元信源，然后对这个新多元信源进行编码，得到不同游程长度映射的码字，就可以将游程序列变换成码字序列，使信源得到压缩。

一般0游程长度和1游程长度应分别编码，建立各自的码字和码表，而且两码表中一般码字是不同的。但0游程码表与1游程码表两表之间的码字不一定要满足非延长码的前缀条件（见下面的MH码表）。

从理论上来讲，游程长度可以从1至无限大。由此要建立的码表将很大、很困难。通常游程越长，出现的概率就越小；游程长度趋向于无穷时，其出现的概率也趋向于零。按照Huffman编码规则，概率越小，码长越长，但小概率的码字对平均码长的影响较小。所以常常在实际应用时，对长游程就不严格按照Huffman编码的步骤进行，而采用截断处理的方法，将大于一定长度的长游程统一用等长编码。(www.xing528.com)

下面给出一种编码方法：

1）选取适当n值，将1，2，…，2ⁿ长的2ⁿ个游程进行Huffman编码，其中2ⁿ长游程码为C。

2）大于2ⁿ的游程用2ⁿ长游程码C来处理。将大于2ⁿ、小于2ⁿ⁺¹的2ⁿ个游程用码字C之后加一个n位的自然码A构成对应的码字。A代表余数，用以区分2ⁿ～2ⁿ⁺¹之间的不同长度。如当游程长度恰好等于2ⁿ时就用为码字。游程长度等于2ⁿ+1时，其码字为，直至游程长度等于2ⁿ⁺¹-1时，其码字为。

3）当游程长度大于2ⁿ⁺¹、小于2ⁿ⁺²时，就用两个CA为码字。如当游程长度为2ⁿ⁺¹时，码字是，游程长度为2ⁿ⁺¹+1时，码字是，……，游程长度为2ⁿ⁺²-1时，码字是。依次类推，可以得到所有游程长度的一一对应的、各不相同的码字。

因为进行了截断处理，在码字序列中有可能出现两个或两个以上的连续码字CA，所以0游程和1游程的码表中为2ⁿ的码字C必须不同，而且这两个码字必须与码表中的其他码字都满足非延长码的前缀条件。设C₀和C₁分别是0游程和1游程中游长为2ⁿ的码字。当译码器接到时，需要根据后面的码字才能判断这个0游程的长度。若后面的码字是C₁，则该0游程长度为2ⁿ；若后面的码字是C₀，则该0游程长度大于2ⁿ。若当C₀和C₁相同时，就无法作出正确判断。同样，若不满足非延长码的前缀条件，也会发生错误的判断，造成译码错误，就不可能实现无失真信源编码。

假设0游程长度的Huffman码效率为η₀，1游程长度Huffman码效率为η₁，由编码效率定义，可得0和1游程的平均码长为

则两个游程的信息熵之和除以平均码长之和，就得到对应的二元序列的编码效率

假设η₀＞η₁，则有

η₀＞η＞η₁ （4.43）

当0游程和1游程的编码效率都很高时，采用游程编码的编码效率也很高，至少不会低于较小的那个效率。由式（4.42）还可以看出，要想编码效率尽可能高，应使式（4.42）的分母尽可能小，这就要求尽可能提高熵值较大的游程的编码效率。

对于多元相关信源，也可以将其输出的一维多元序列映射成一一对应的标志序列。这时就需要选用表示串的字符、串的长度的两个标志参量来表示游程。如果信源符号集中符号数较多，且平均游程长度不是很长时，所增加的串字符的标志参量可能会抵消游程编码压缩得到的好处。所以，一般对多元相关信源采用其他的直接编码方法为好。