解: (1)
1 1 H ( X ) 0.2 Lb 0.8Lb 0.72 bit / 字符 0.2 0.8 b 0.2 1 0.8 1 1 bit / 字符
=H ( X ) / b 100% 72%
(2)二重扩展. 最佳编码原则
1 x x 111 B1 3 1 1 25 4 x x 110 B2 3 1 2 25 4 xx 10 B3 2 2 1 25 16 x2 x2 0 B4 1 25 1 4 4 16 39 B 3 3 2 1 25 25 25 25 25 39 39 B/K /2 25 50 H ( X ) 0.72 92% B / K 39 50 由72% 92%
6
7
0.10
0.01
(0.11) 1
(0.10) 0
(0.01) 1
1110
1111
4
4
R
H ( x) 2.61 0.953(bit / 码元) 2.74 b
＝R C 95.3%
fano编码方法 > shannon编码方法
3．霍夫曼编码方法Huffman coding
1) 将信源消息的概率按大小顺序排队
3. 单义可译定理
信源消息集合 X {x , x ,..., x } 1 2 N 信道基本符号的种类为 D 码子集合为 码长集合为
S {s1 , s2 ,..., sN }
b {b 1, b 2 ,..., b N}
N i 1
即时码存在定理： D bi 1 Kraft不等式
即时码
2.即时码的构造(充分必要条件)
设 si (ai1ai 2 aik ) 是码 s 中的任一码字，
则 s 为即时码的充分必要条件为：
对于任意的 m < k， 任意的 s j (a j1a j 2 a jm ) 不是 si (ai1ai 2 aik ) 的前缀.
即 s 的任何一个码子不是另一个码子的前缀
第四章
消息集合
离散信源编码
编码器
X
代码集合
S
A 信道基本符号集合

第4.1节 信源编码的模型 ① X ：消息集合，Ｎ个元素 ②
③
X x1 , x2 ,
, xn
A ：信道基本符号集合， A a1 , a2 , , an
S
Ｄ种信道基本符号 ：代码集合，个数为Ｎ S S , S , 1 2
, SN
2.信源编码器的主要任务：完成输入消息集合与输 出代码的集合之间的映射。
信源编码的 3 个基本要求
①选择合适的信道基本符号 使输出代码能适应于信道。 （考虑信道的信源编码： 如信源信道联合编码）

②有效的编码方法
③编码方法应满足：消息集合与代码组集合一一对应。
使得信源发出消息 输出代码组

最佳 (1)若R C , 100%, (2) R C , 100%, 有改进余地 (3) R C , ? , 失真.(丢失)
R 100% C
编码效率η
H(X ) / b 100% H max ( X ) / b
或 k重扩展

H(X k ) / B H max ( X ) / B
• 书上举例 X : x1 , x2 , x3 , x4 62页 例4.4 1 1 1 1 P( X ) : , , , {0,1}集 2 4 8 8 1 1 1 1 N bi 8 8 D 2 2 2 4 2 2 1 i 1
存在即时码. 简单地说
编码过程：是建立码地址和将编码消息序列分段的过程。
第4.7节 图像的信源编码
1. 图象消息的信息特征 信息量大： 352×288×3×25 VCD 768×576×3×25 DVD STV 1280×1024×3×60 HDTV 1920×1280×3×60 2. 一些编码压缩方法 • 压缩比： P Ls Ld 100%
k
100%
η
1：最佳编码
3.最佳编码的两原则
(1)对信源中出现概率大的消息(或符号)，尽可能用短的代
码组来表示，即短码; 反之，用长码。
(2)不使用间隔, 采用可区分码字 信源： x 1 ,..., xN P( x 1 ),..., P( xN ) 输出代码组： s1 , ..., sN b 1 , ..., b N 若
③ 每一组再进一步分裂 => 赋 0，1 ④ 重复，到每组只剩下一个信源符号为止。 其特点：
1）最佳编码： 概率大的 => 分解的次数少
概率小的 => 分解的次数多 2）码字集合是唯一的
举例：书上P71页 表4.3
I 1 2 3 4 5 pi 0.20 0.19 0.18 0.17 0.15 1 (0.43) (0.26) 1 (0.57) (0.37) 1 0(0.17) (0.15) 0 1分解 0 2分解 (0.20) 0 (0.19) 0 (0.18) 1 3分解 4分解 编码 00 010 011 10 110 码长 2 3 3 2 3
对应的编码得到的
逗点码(comma code) （书上59页，例4.2） 即时码(instantaneous code) 译码时不需要考察 后续码元 单义可译码
• 逗点码： (例4.2) 1
s1
0 1 0 1 0
s2
s3
1
s4
0
1 0 1
s5
s6
•延长码(extended code)
•非延长码：
书上 P73 举例4.10 P74 4.11
Huffman coding 小结
① Huffman coding 总是以最小概率相加的方法来 “缩减”参与排队的概率个数： 概率越小→对缩减的贡献越大，码字也越大 ② 最小概率相加的方法 → 编码结果不具有唯一性。 ③ 尽管对同一信源存在着多种Huffman编码结果， 但其平均码长几乎都是相同的
k 对于 k 重扩展信源 . 熵 H ( X ).每个码字为B个码元 k R H ( X )/ B (bit / 码元)
(2)变长码的信息传输速率
x1 , x2 ,..., xN N 个单符号消息: b1 , b2 ,..., bN 变长码编码的代码组长度: 对应的概率为 : P(b ), P(b ),..., P(b ) 1 2 N
P( x1 ) P( x2 ) ... P( xN ) b 1 b 2 ... bN
则 b P ( xi )b i 最短！
第4.3节 单义可译定理
1.单义可译码: 对于一个有限长度的信源消息序列，若编码得 到的码字序列不与其他任何信源序列所对应的 码字相同
当信源消息序列不同 码字序列必然不同
2) 将两个最小的概率相加，形成新的概率，将和的 概率重新排队 3) 再重复 2），直到最后概率为1
4) 再次概率相加，将0，1按同一规律赋予相加的两 个概率（大概率赋1，小概率赋0）
• 举例：
b 2.5码元/ 符号 H ( x) P( xi )lbP( xi ) 2.471bit / 码元 R H ( x ) b 2.471/ 2.5 0.988bit / 码元
Ls
• 无失真编码 ： Huffman、算法编码、VLC、轮廓编码法
若b bmin b bmin
不存在单义可译码 存在单义可译码
4.平均码长界定
H(X ) H(X ) b 1 LbD LbD
无失真信源编码. 单一可译码
bmin
H(X ) 下界 LbD
• 若 D 给定，给定信源 ( H ( X ))，则 bmin 也确定
第4.4节 无失真信源编码定理
④
⑤
是最佳编码
先统计再编码
⑥
建立在编码器与译码器码树结构上的基础上
3. Lempel-ziv编码
概率分布未知
码树结构未知
① 独立于信源的统计特性，变长到定长的编码 ② 形成字典 code dictionary ③ 码字：（1）字典地址 （2）本码段需要源加的消息
④ 利用已编码信息进行当前的编码
4. 信源编码的目的
(1) 把信源发出的信息一一对应地变换维信道
基本符合构成的代码组 (2) 尽可能减小代码组的平均长度. 编码效率
第4.2节 信息传输速率和编码效率
1.信源编码的信息传输速率(信息率)R：
单位时间内所包含的信息量
(1) 等长码的信息传输速率 R
对于单符号信源. 熵H( X ).每个码字为b个码元 R H ( X ) / b (bit / 码元)
码元 / 字符
第4.5节
典型的信源方法
1． 香农编码 1 ① log D bi log D
P( xi )
1 1 P( xi )
b1 b2 ... bN
② ③
p( x1 ) p( x2 ) ... p( xN )
Pi pk
k 1
i 1
(前(i-1)个概率的累加)
香农编码方法
xi
pi
Pi
―lbpi
1 2 …
bi
1 2 …
代码组
0 10 …
x1 ½ 0 x2 ¼ ½+¼ … … …
xi 1 2 … …
i
1
2i 1
…
i …
i …
111…110 …
2．费诺编码（Fano coding）
①
p( x1 ) p( x2 ) ... p( xN )
② 将依次排列的信源符号按概率值分为“概率和接 近相同”的 2 组 => 赋 0，1