信息，例如霍夫曼编码。

它相对简单，是 本章的重点。

信息有一定的差别，例如JPEG 、MPEG
■无失真信源编码：解码之后可以得到原始 jlll ■有失真信源编码：解码之后的信息与原始 jlll
■其中X 称为码符号集，X 中的元素“称为码元或者 码符号。

输岀符号叱•称为码字，植字的集合C 称 为代码组或者码。

码字比•的长度厶称为码字长度, 简称码长。

■要实现无失真编码，编码器的映射必须是一一对 应、可逆的。

码的分类
5.1编码器
编码器
C=(W1,W2,…,W 几
■信源编码器表示为: X=(QK2,…对
■例如:
S=(ACD) r A B C D C=(OOJOJl)r
00,01,10,11
r X=(o ，l)
S=(A ，CQ) AB C D C=(0,001,lip
* 0,01,001,111
X=(0J)
■根据码长
□固定长度码（定长码）：所有码字的长度相同。

□可变长度码（变长码）：码字长短不一。

■码字是否相同
□非奇异码：所有码字都不相同。

□奇异码：存在相同的码字。

5.2分组码
■象稱蛊轟凋11映射
■通常在接收端收到的码字之间并没有明显的间隔, 表现为皿叫…巴的形式，把这种形式称为g阶扩展码。

例如前面的两个例子，ACD编码成另 001011/0001111的形式，均为3阶扩展码。

■码字之间缺少间隔，给译码造成了一定的困难□定长码：不存在困难，001011必定译码成为ACD □变长码：存在困难，0001111可以译码成为ACD(0 001 111),也可以译码成为AABD(0 0 01 lll)o
唯一可译性
■定义524 —个分组码若对于任意有限的整 数N,其N 阶扩展码均为非奇异的，则称之 为唯一可译码。

■含义：无论码由多少个码字组成，总是能 够正确译码，不存在二义性。

10110 010 ^BACB 10110 0 Ol^ABAD
■无需知道下一个码字的码符号，即可译码, 这样的唯一可译码成为即时码。

■命题521 —个唯一可译码成为即时码的充 要条件是其中任何一个码字都不是其他码 字的前缀。

即时码
5.3定长码
■编码速率: ~1T，其中/是码字长度，厂是码符号的个数，N代表N次扩展信源。

■编码效率：rj=H(S)R其中H(S)是扩展之前信源的爛。

■例如：S={ABC},等概率出现，N=2，SN={AA,・・・,CC},对SN进行二元编码，则心2,编码方式如下，则上4。

■那么，S"的编码速率为R=(41og2)/2=2, S"的编码效率为
7=H(S)//?=log3/2=0.7925
5.4变长码
■匹配编码：根据概率进行编码，概率大的所给的代码短，概率小的所给的代码长。

例如哈夫曼编码。

■变换编码：将信号从一个空间变换到另一个空间，在新的空间里对信号进行编码。

例如JPEG
■识别编码：主要用于印刷或奢打字机等有标准形状的符号的编码。

0 2 4 6 8 10 12 14 16 18 20
5.4.2两个不等式
■定理5.4.1即时码爭在的充要条件是茁a
Z = 1
克拉夫特（Kraft）不等式。

■定理5.4.2唯一可译码存在的充要条件是
q
y
麦克米伦（McMillanS不等式。

5.4.3唯一可译码判别准则
■命题541 —种码是唯一可译码的充要条件是S], S”…中没有一个含有So中的码字。

5.4.4码平均长度 /八一…]…么 ....................
0 g 。

对唯一可译桐，则这个码的平 q 厶二£卩（训
i=l
■定义5.4.2对应一给定的信源和一给定的码符号
集，若有一种唯一可译码，其平均长度小于所有 其他
[;]
■定义5.4.1设信源
编码后的码字分别为W]W?…巴，各码字相应的码 长分别为仏••丿 均长度为
的唯一可译码，则称这种码为紧致码，或最佳码。

精品课件
V
1 •
•r
精品课件
V
1 •
•r
5.4.5变长码的编码方法：霍夫曼编码
■ {^5.4.4
$1$3$5
10 11 01 001 000
L = 2 x 0.4 + 2x 0.2 + 2x 0.2 + 3x0.1+3x0.! =
2.2
■定理5.4.6霍夫曼码是紧致码。