第三章 无失真信源编码

二、变长编码方法
霍夫曼编码 ①把信源发出的N个消息按其概率递减次序排列 把信源发出的N ②把概率最小的两个消息分别编成“1”和“0”码元(即把概 把概率最小的两个消息分别编成“1”和 0”码元( 码元 率较大的消息编为“1”，概率较小的消息编为“0”； 率较大的消息编为“1”，概率较小的消息编为“0”；或反之 也可),并对这两个消息求概率之和 也可),并对这两个消息求概率之和 ), ③把上述的概率和作为一个新消息的概率，再与原来的其他消 把上述的概率和作为一个新消息的概率， 息按概率递减的次序排列 ④重复上述编码步骤②与③，直到概率和是1为止 重复上述编码步骤② 直到概率和是1 ⑤从最终的编码步骤，在各个消息编码方向线的逆行程顺序地 从最终的编码步骤， 取下所编出的码元， 取下所编出的码元，构成相对的代码组
i =1 7
= 0.2 × 2 + 0.19 × 2 + 0.18 × 3 + 0.17 × 3 + 0.15 × 3 + 0.1 × 4 + 0.01 × 4 码元/符号 码元 符号] = 2.72 [码元 符号
H( X ) = −∑ P( xi ) log P( xi ) = 2.16
b =
N
∑Pb
i =1 i
i
[码元/符号]
所以，信息传输速率R 所以，信息传输速率R为：
H( X) R= b
bit/码元时间 bit/码元时间
对于K重符号序列消息，设有N 对于K重符号序列消息，设有N个K重符号序列X1，X2，…， 重符号序列 ， XN输入，它们的出现概率分别为P1， P2，…，PN，各自对应 输入，它们的出现概率分别为P 的代码组长度又分别为B 则平均长度为： 的代码组长度又分别为B1，B2，…，BN，则平均长度为：
X ={x , x2,… xN} ， 1
信源编码器 N个 符 号 序 列 集 合 N个 代 码 组 集 合
S={S ,S2,… SN} , 1
A={a ,a2， ， D} … a 1
信道基本符号集合
信源发出K重序列消息时，信源编码器的模型如下图，设信源X 信源发出K重序列消息时，信源编码器的模型如下图，设信源X 中有M种不同的符号，即X＝{X1，X2，…，Xm }，那么K重符号序 中有M种不同的符号， ， 那么K 列消息的的数目N 此为K 列消息的的数目N＝MK，此为K维矢量
R= H( X) b
bit/码元时间 bit/码元时间
对于K重符号序列消息(包含有记忆序列和无记忆序列) 对于K重符号序列消息(包含有记忆序列和无记忆序列)，设 代码组包含B个码元，则信息传输速率R 代码组包含B个码元，则信息传输速率R为：
H( X K ) R= B
bit/码元时间 bit=1/4，P(x2)=3/4。 例：已知信源X包含 1和x2两种符号，且有 已知信源 包含 ， 。 现信源编码方案为x 现信源编码方案为
1
0 x2
1， 求其编码效率 1。再设信 ， 求其编码效率η 110， x2x1 ， 10， x2x2 ，
源改发出四种符号序列消息x 源改发出四种符号序列消息 1x1, x1x2, x2x1, x2x2，采用最佳 编码方案为x 编码方案为 1x1 111， 111， x1x2
B =
N
∑P B
i =1 i
i
[码元/符号序列] 码元/符号序列]
所以，信息传输速率R 所以，信息传输速率R为：
H( X K ) R= B
对于无记忆信源， 对于无记忆信源，有：
bit/码元时间 bit/码元时间
H( X K ) KH( X) H( X) R= = = B B B K
bit/码元时间 bit/码元时间
等长代码组 信源编码器输 出的代码组 不等长代码组
下面我们的讨论，假设信源编码器为正规编码器， 下面我们的讨论，假设信源编码器为正规编码器，等效信源的 熵等于原信源熵 ①等长代码组的信息传输速率 对于发出单符号消息，若信源编码器输出的代码组含b 对于发出单符号消息，若信源编码器输出的代码组含b个码 则代码组消息在编码信道上的信息传输速率R 元，则代码组消息在编码信道上的信息传输速率R为:
对于单符号消息有： 对于单符号消息有：
H( X)
η=
b = H( X) log 2 D b log 2 D
对于K重符号序列消息有： 对于K重符号序列消息有：
H( X K )
η=
H( X K ) B = log 2 D B log 2 D
对于二进制均匀编码信道，又对于离散无记忆信源有： 对于二进制均匀编码信道，又对于离散无记忆信源有：
2
0，并计算编码效率η2 ，并计算编码效率 解：①
H( X) = −∑ P( xi ) log P( xi )
i =1
1 1 3 3 = − log 2 − log 2 4 4 4 4 bit/符号 = 0.811 bit/符号
b =1
码元/符号 码元/
C = log2 D = 1
bit/码元时间 bit/码元时间
例：
1 1 0 0.20 1 0 0.19 0 0.39 00 2 0.61 1.0 01 2
0.18
1 0.35
111
3
0.17
0
110 1
3
0.15 1
101
3
0.10
0 0 0.11
0.26
1001
4
0.01
1000
4
由上可得代码组得平均长度为： 由上可得代码组得平均长度为：
b = ∑ Pi bi
三位二进 代码组制 信源 0， 1， 2， …， 7 信源编码器 二进制编码信道
信 道 基 本 符 号 0， 1
凡是能把信源发出的所以消息都一一对应地变换成相应代码组 的信源编码器称为正规编码器。这种编码器不会损失信息量， 的信源编码器称为正规编码器。这种编码器不会损失信息量，故 可以把信源和正规编码器合并在一起，看作一个等效信源， 可以把信源和正规编码器合并在一起，看作一个等效信源，等效 信源的熵与原信源熵相等 2.消息在编码信道上的信息传输速率 2.消息在编码信道上的信息传输速率
3.信源编码的编码效率 3.信源编码的编码效率 信源编码器的作用—— ——使各个代码组的长度分布与信源中各 信源编码器的作用——使各个代码组的长度分布与信源中各 个消息的概率分布达到统计匹配 信源编码器的实质——通过合适的信源编码方法可使消息在 信源编码器的实质——通过合适的信源编码方法可使消息在 —— 信道上信息传输速率尽量接近信道容 量，这样使编码效率尽量接近于1 这样使编码效率尽量接近于1 编码效率η定义为信息传输速率与信道容量C的比值，即 定义为信息传输速率与信道容量C的比值， η＝ R/C ＝ 信道容量是在传输消息不产生失真条件下， 信道容量是在传输消息不产生失真条件下，信道允许的最大 信息传输速率 信道容量C定义为： 信道容量C定义为： C ＝ log2 D bit/码元时间 对于二进制均匀编码信道， 对于二进制均匀编码信道，D＝2，则 C＝1 bit/码元时间
第三章 无失真信源编码
一、信源编码概述
1.离散信源信源编码的目的和模型 1.离散信源信源编码的目的和模型 目的： 目的： ①把信源发出的消息(单个符号消息和符号序列消息)变换成 把信源发出的消息(单个符号消息和符号序列消息) 由信道基本符号构成的代码组(称为码字) 由信道基本符号构成的代码组(称为码字)，以使得消息能在编 码信道上传输 ②尽量减小代码组的平均长度，以提高信道传输消息的有效 尽量减小代码组的平均长度， 性
X ={x , x2,… xN} ， 1
信源编码器 N个 符 号 序 列 集 合 N个 代 码 组 集 合
S={S ,S2,… SN} , 1
A={a ,a2， ， D} … a 1
信道基本符号集合
二进制信道是一种常用的信道，它的信道基本符号为0 二进制信道是一种常用的信道，它的信道基本符号为0和1两 种。下图为二进制信源编码器
H( X) 0.811 η1 = = = 81.1% b log 2 D 1
② K＝2时 P(x 1/4×1/4＝ P(x 1/4×3/4＝ P1＝P( 1x1)＝1/4×1/4＝1/16 P2＝P( 1x2)＝1/4×3/4＝3/16 P(x 3/4×1/4＝ P(x 3/4×3/4＝ P3＝P( 2x1)＝3/4×1/4＝3/16 P4＝P( 2x2)＝3/4×3/4＝9/16 B1＝ B2＝ B3＝ B4＝ B1＝3码元 B2＝3码元 B3＝2码元 B4＝1码元
②不等长代码组的信息传输速率 此时需先求代码组的平均长度 对于单符号消息，设有N个符号消息 对于单符号消息，设有N个符号消息X1，X2，…，XN输入， ， 输入， 它们的出现概率分别为P 它们的出现概率分别为P1， P2，…，PN，各自对应的代码组长 度又分别为b 则平均长度为： 度又分别为b1，b2，…，bN，则平均长度为：
qN
∑r
j =1
−l j
≤1
10， 110， 0 ， X2 10，X3 110，X4 例：四个非延长码组，X1 四个非延长码组， 1110 观察这四个代码组可知 最后一个码元为0 起逗号作用， 代码组可知， 观察这四个代码组可知，最后一个码元为0，起逗号作用， 见到码元0 见到码元0，表明代码组结束 若有二进制序列 (1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0) 它所对应原消息序列( 它所对应原消息序列(X3，X2，X4，X1，X4，X1，X3，X2，X4) 例：设有延长码组， X1 设有延长码组， 01， 0 ， X2 01，X3 0111 若收到序列 (0 0 1 1 0 1 0 0 1 1 1 0 1 1) 011， 011，X4
B = ∑ Pj Bj