Chap 8
无失真信源编码
香农编码、费诺编码、霍夫曼编码
限失真信源编码
游程编码
- 对相关信源编码更有效
例如：二元序列 000101110010001…
可变换成如下游程序列 31132131
减弱原序列符号间的相关性
将二元序列变换成了多元序列
[适合于用其他方法，如霍夫曼编码，进一步压缩信源，提高通信效率]
- 游程变换是一一对应的可逆变换，变换后熵值不变
游程编码的熵
eg. 二元独立序列游程长度的熵
“0”游程长度L(0)的概率为
$p[L(0)]=p_0^{L(0)－1} p_1$
“1”游程长度L(1)的概率为
$P[L(1)]=p_1^{L(1)-1} p_0$
游程变换后符号熵没有变。
因为游程变换是一一对应的可逆变换，所以变换后熵值不变，这也说明变换后的游程序列是独立序列(for 二元独立序列 )
$H(p_0)= H(p_1)$
$0: H[L(0)] = H(p_0)/p_1; l_0 = 1/p_1$
$1: H[L(1)] = H(p_1)/p_0 l_1 = 1/p_0$
$H(X) = {H[L(0)] + H[L(1)]}/(l_0+l_1) = H(p_0) = H(p_1)$
游程长度可从1到无穷，要建立游程长度和码字之间的一一对应的码表是困难的 ==> 长码的截断处理
例子
- 首先测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源；
- 对新的信源（游程序列）进行霍夫曼编码