根据能否在解码后完全准确的恢复出原始 消息(信息熵是否变换)，将信源编码分为无失 真信源编码和率失真信源编码.
能：无失真信源编码 能否完全恢复出原始信号？ 否：率失真信源编码
无失真编码：离散信源编码， 文字、数据，不能有差错 率失真编码：连续信源编码，语音、图像， 不可能没有差错，没必要没有差错
信源符号 码1 S1 S2 S3 S4
信息论基础 李富年 武汉科技大学
码2 00 01 00 11
码3 0 1 0 11
码4 1 10 100 1000
00 11 10 11
码的分类
根据码字的情况
非奇异码：所有码字都不相同，信源符号与码字之间唯一对应 奇异码：码字集合中有相同的码字，即存在Si S j但Wi W j
信息论基础 李富年 武汉科技大学

信源编码的概念
对于离散信源，如果信源的统计特性已知， 便可直接进行编码。
对于连续信源，应根据采样定理将连续 信号离散化。连续信号经过采样和量化就 变成了离散信号。将离散信号按一定规律 与一组代码相对应就是编码 。
信息论基础 李富年
武汉科技大学
无失真信源编码的基本概念
信息论基础 李富年 武汉科技大学
非续长码 -树图构造
例：给定编码符号表X={0，1}，码字W={W1， W2，W3，W4},字长分别是n1=1，n2=2 ， n3=n4=3，求非续长码。
信息论基础 李富年
武汉科技大学
非续长码 -树图构造
0 0 0 W4=000 1 1 W2=01 W3=001
W4=111 1
信息论基础 李富年 武汉科技大学
码的分类
信源符号 S1 S2 S3 S4 码4 0 01 011 111 码5 1 01 001 0001
0011101011
结论： 非续长码一定是单义码，而单义码却不 一定是非续长码。
信息论基础 李富年 武汉科技大学
码的分类
非奇异码、唯一可译码、非续长码的关系
非奇异码 唯一可译码 非续长码 非奇异码 唯一可译码 非续长码
信息论基础 李富年 武汉科技大学
树图法
1 对于码 1 01 001 0001 和 10 100 1000 用码树表示如下：
0 0 0 1 1 0 1 0 1 0 1
信息论基础 李富年
武汉科技大学
非续长码 -树图构造
编码：用树图法构造非续长码，只要将信源 符号全部对应于终端节点，而不是中间节 点即可。这样就可以保证任何一个码字都 不是其它码字的前缀 解码：按照码符号的顺序，从根节点依次查 询到终端节点，就得到对应的信源符号。 再从根节点对剩下的码符号序列做相同的 处理，直到处理完码符号序列中所有的码 符号。
例：电报： 1：母亲患癌症，情况危急，请速归。 2：母病危速归
信息论基础 李富年 武汉科技大学
信源编码的概念
具体来说，信源编码就是根据信源的统计 特性，对信源发出的消息进行编码。 一般而言，编码就是用数字形式表示消息 的过程。编码实质上是对要处理的源数据按 一定的规则进行变换。这些数学方法和变换 策略的目的都是力图用尽可能少的符号或位 来表示较多、较长的符号及消息。
武汉科技大学
单义码存在定理
码字不满足克拉夫特不等式，则肯定不是唯 一可译码。码字满足克拉夫特不等式，并不一 定是唯一可译码，只是说存在这样的码长条件 的唯一可译码。
信息论基础 李富年
武汉科技大学
等长编码
• 等长码：各个码字码长都相等的码 • 对于等长码，如果是非奇异码，那么一定 是唯一可译码
是
可以编码成 0 1 00 0 111 0 有效性： 1 更好 可靠性： 0 111 更好，提供纠错功能 00
否
信息论基础 李富年
武汉科技大学
等长编码
等长码码长不能无限制缩短。
信源符号集有2个符号，可以用 0 1 编 码，码长为1； 信源符号有4个，码长为1就不行了，必须 用码长为2的等长码 00 01 10 11 设信源符号集中有符号q个；用二元码进行 编码，码长为 l ，能够提供的最多码字为 l l 2 个，因此要满足 2 q l log q
r
i 1
q
ni
2
i 1
4
ni
1 1 1 1 1 2 4 8 8
如W改为为{0，01，110，011}， 即 n1=1，n2=2 ，n3=3 ，n4=3
r
i 1
信息论基础 李富年
q
ni
2
i 1
4
ni
1 1 1 1 1 2 4 8 8
r ni 1
i 1
其中，q是码字的个数，r是编码符号表的码元 个数，ni 是字长。若上式成立，就一定能构造一 个r进制的唯一可译码。
信息论基础 李富年
武汉科技大学
单义码存在定理
例：给定编码符号表X={0，1}，码字 W={W1，W2，W3，W4 }= {0，01，10，011}, 分别由1，2，2，3个码元构成的码字
信源编码模型
信源空间为：
s2 ...... s q s1 S p ( s1 ) p ( s 2 ) ...... p ( s q )
编码符号表为 X {x1 , x2 ,... xr } ，用 X 的符号对消息 s i 进行编码。
信息论基础 李富年
武汉科技大学
武汉科技大学
信源编码的概念
信源编码的作用 符号变换：用信道能传输的符号来代表信源 发出的消息，使信源适合于信道的传输。
例： 信源发送符号为{ 是，否} 信道中能够传输的符号为{0，1}
信息论基础 李富年
武汉科技大学
信源编码的概念
有效传输(冗余度压缩)——减少信源的剩余度 在不失真的条件下，用尽可能少的符号来传 送信源信息，提高信息传送率。 例： 信源发送符号为{ 是，否} 方案1： { 0，1} 方案2： {000，111}
非唯一可译码
信息论基础 李富年
武汉科技大学
码的分类
例：
X 0, 11, 10
0 1 0 1 0 1 0
例：
S1S3S3S3
01, 10
X 0,
0 1 0 1 0 1 0
S1S3S3S3
S2 S2 S2 S1
要保证无失真编码，必须采用唯一可译码。
信息论基础 李富年 武汉科技大学
码的分类
信息传输系统
第二章:信息量
消息
信源
信源编码器
信道编码器
第三章信道 与信道容量
等 效 信 道
第四章:无失 真信源编码
信宿
消息
信源解码器
信道解码器
信息论基础 李富年
武汉科技大学
第四章 无失真信源编码
信源编码的概念 信源编码的模型 等长编码 变长编码
香农－费诺－艾利斯编码
霍夫曼编码 费诺编码
1 W1=1
1 0
1 0
0 W1=0 W2=10 W3=110
①非续长码不是唯一的。 ②全部终端节点都代表码字，这种情况叫做 用尽的非续长码。
信息论基础 李富年 武汉科技大学
单义码存在定理
设信源S的符号集为 S : {s1 , s 2 ,...s q }，码符号 集 X :{x1, x2 ,... xr } ，又设码字为W1 ,W2 ,...Wq，其码长分 别为 n1 , n 2 ,...n q 。则存在单义码的必要条件是： q, r , ni (i 1 ,2 ,..., q) 满足Kraft不等式，即 q
变长码
信息论基础 李富年 武汉科技大学
等长码
树图法
• 树图法：所有码字用码树描述出来。码树是 一棵倒置的树，最上端是根节点，从根节点 出发不断向下伸出树枝，分支与码符号一一 对应。 • 一个节点继续分支，称为中间节点；一个节 点不再继续分支，称为终端节点。 • 将信源符号对应的节点用实心圆表示，从根 节点到这个节点经过的分支对应的码符号序 列就是码字；没有与信源符号对应的节点用 空心圆表示
按照不等式可知，q=4，r=2，n1=1，n2=2 ， n3=2 ，n4=3 ，代入Kraft不等式左边得
r
i 1
信息论基础 李富年
q
ni
2
i 1
4
ni
1 1 1 1 9 1 2 4 4 8 8
武汉科技大学
单义码存在定理
如W改为为{0，10，110，111}， 即 n1=1，n2=2 ，n3=3 ，n4=3
信息论基础 李富年
武汉科技大学
信源编码的概念
要把信源的信息高速度、高质量地通过信 道传送给信宿，一般要通过信源编码和信道编 码来完成。 研究信源编码：只考虑有效性，不考虑可靠性
等效无噪声信道
消息 信号S
信源
信源编码器
信道编码器
调制器
信 道
噪声
干 扰 源
消息
信宿
信源解码器
信道解码器
解调器
S＋ N
信息论基础 李富年
编码的定义
如果一种编码方案
s1 x1 00 s 2 x 2 01
s3 x 3 10
s4 x 4 11
如果信源连续发送S1S2S3三个符号，则该 信源编码的输出为 000110
信息论基础 李富年 武汉科技大学
编码的定义
如果一种编码方案
s1 x1 0
s3 x 3 110
信源符号 S1 S2 码1 00 01 码2 00 01
S3
S4
10
11
00
11
001110
等长非奇异码一定是唯一可译码。
信息论基础 李富年 武汉科技大学