5.1 编码的定义
如果信源输出符号序列长度L＝1，信源符号集 A(a1， a2，…，an) 信源概率空间为
X P
a1 p(a1)
a2 p(a2)
an p(an )
若将信源X通过二元信道传输，就必须把信源符号ai 变换成由0,1符号组成的码符号序列，这个过程就是
信源编码
5.1 编码的定义
(3) 唯 一 可 译 码 中 又 分 为 非 即 时 码 和 即 时 码 (Instantaneous Codes)： 如果接收端收到一个完整的码字后，不能立即译码， 还需等下一个码字开始接收后才能判断是否可以译 码，这样的码叫做非即时码
5.1 编码的定义
即时码：只要收到符号就表示该码字已完整，可以立即 译码
通常可用码树来表示各码字的构成
节点 notes
树根root 0树枝 orde Nhomakorabeas 10
1
0
1
01
01
01
01
0 1 0 10 10 1 0 10 10 1 0 1
二进制码树
终端节点 terminal nodes
5.1 编码的定义
0
1
2
0 1 2 01 2 01 2 01 2
01 2
三进制码树
5.1 编码的定义
唯一可译码存在的充分和必要条件是各码字的长 度Ki （码元个数）应符合克劳夫特不等式(Kraft Inequality)： n
m－Ki 1
i 1
其中m为进制数，n为信源符号数，Ki为各码字的长度 （码元个数） 必要性——体现在如果是唯一可译码，则一定满足该不等式 充分性——体现在如果满足该不等式，则这种码长的唯一可 译码一定存在，但并不表示所有满足Kraft不等式的码一定是 唯一可译码
第5章 信源编码
信源编码的主要任务：由于信源符号之间存在分布不均 匀和相关性，使得信源存在冗余度，信源编码的主要任 务就是减少冗余，提高编码效率 信源编码的基本途径： 使序列中的各个符号尽可能地互相独立，即解除相关性； 使编码中各个符号出现的概率尽可能地相等，即概率均 匀化
第5章 信源编码
信源编码的理论基础是信息论中的两个编码定理： 无失真编码定理 限失真编码定理
表5-2中的码1是奇异码，码2是非奇异码
表5-2 码的不同属性
信源符号ai 符号出现概率p(ai) 码1 码2 码3
a1
1/2
0
0
1
a2
1/4
11 10
10
a3
1/8
00 00 100
a4
1/8
11 01 1000
码4 1
01 001 0001
5.1 编码的定义
(2) 唯一可译码 (Uniquely Decodable Codes) 任意有限长的码元序列，只能被唯一地分割成一个个 的码字，便称为唯一可译码
码可分为两类：
1、固定长度的码，码中所有码字的长度（码元个数）都 相同，如表5-1中的码1就是定长码(Fixed Length
Codes)
2、可变长度码，码中的码字长短不一，如表中码2就是
变长码(Variable Length Codes)
表5-1 变长码与定长码
信源符号ai 信源符号出现概率p(ai)
第5章 信源编码
编码(Coding)分为信源编码(Source Coding)和信道编码 (Channel Coding)，其中信源编码又分为无失真信源编码 和限失真信源编码 一般称
无失真信源编码定理为Shannon第一极限定理； 信道编码定理（包括离散和连续信道）称为Shannon第 二极限定理； 限失真信源编码定理称为Shannon第三极限定理
5.1 编码的定义
X
Y
信源
编码器
信道
码符号(元)
X——信源符号(Source Symbol)序列 Y——码字(Codeword)序列
图5-1 信源编码器示意图
信源编码是指信源输出的信源符号经信源编码器编码后 转换成另外的压缩符号(码字Codeword) 无失真信源编码：可精确无失真地复制信源输出的消息
5.1 编码的定义
将信源消息分成若干组，即符号序列 xi， xi＝(xi1xi2…xil…xiL)， xilA={a1，a2，…，ai，…，an}
每个符号序列xi依照固定码表映射成一个码字yi， yi＝(yi1yi2…yil…yiL)， yilB={b1，b2，…，bi，…，bm}
这样的码称为分组码(Block Codes)，也叫块码 只有分组码才有对应的码表，而非分组码中则不存在码表
∆无失真编码只适用于离散信源 ∆对于连续信源，只能在失真受限制的情况下进行限失真 编码
第5章 信源编码
本章主意讨论离散信源编码 首先从无失真编码定理出发，重点讨论以香农(Shannon) 码、费诺(Fano)码和霍夫曼(Huffman)码为代表的几种无 失真信源码 然后介绍限失真编码定理 最后简单介绍了一些常用的信源编码方法
即时码又称为非延长码(Undelayed Codes)，任意一个码 字都不是其它码字的前缀部分，有时叫做异前缀码(Prefix Codes)
非分组码
码
奇异码 非唯一可译码
分组码 非奇异码 唯一可译码
非即时码
即时码(非延长码)
5.1 编码的定义
码 分组码 非奇异码 唯一可译码
即时码
紧致码（最佳码）
5.1 编码的定义
码表
码1
码2
a1
p(a1)
00
0
a2
p(a2)
01
01
a3
p(a3)
10
001
a4
p(a4)
11
111
5.1 编码的定义
码的属性及分类
(1) 奇 异 码 (Singular Codes) 和 非 奇 异 码 (Nonsingular Codes) 若信源符号和码字是一一对应的，则该码为非 奇异码, 反之为奇异码
5.1 编码的定义
0
a4=000
{1，01，001，000}
惟一可译码；
0
1
{1，01，101，010}
0
1 a1=1
不是惟一可译码；
均满足克劳夫特不等式
1
a2=01
a3=011
4
2Ki 21 22 23 23 1
i 1
克劳夫特不等式只是用来说明唯一可译码是否存在， 并不能作为唯一可译码的判据。
所以说，该不等式是唯一可译码存在的充要条件
5.1 编码的定义
例5.1 (p.88) 设二进制码中ai (a1, a2 ,a3 , a4)，K1＝1，
K2＝2，K3＝2，K4＝3，应用Kraft定理判断是否可能
是唯一可译码
解： 4 2Ki 21 22 22 23 9 1
i 1
8
因此不存在满足这种Ki的唯一可译码。