第五章信源编码(编码定义及定长编码)

第1章概述第2章信源熵第3章信道容量第4章信息率失真函数第5章信源编码第6章信道编码第7章密码体制的安全性测度信源编码¾信源编码是以提高通信的有效性为目的编码。

¾通常通过压缩信源的冗余度来实现。

¾采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。

同样多的信息用较少的码率来传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。

信源编码的基本途径有两个：¾使序列中的各个符号尽可能地互相独立，即解除相关性；¾使编码中各个符号出现的概率尽可能地相等，即概率均匀化。

信源编码的基础是信息论中的两个编码定理：¾无失真编码定理¾限失真编码定理无失真编码只适用于离散信源；对于连续信源，只能在失真受限制的情况下进行限失真编码。

本章首先介绍信源编码的相关概念以及信源编码定理，然后描述编码方法。

本章内容安排 信源编码定理 信源编码概念香农第一定理香农第三定理 信源编码方法 离散信源编码连续信源编码相关信源编码变换编码信源编码概念及信源编码定理信源编码及有关概念无失真信源编码定理衡量编码效果的公式定长信源编码定理变长信源编码定理限失真信源编码定理无失真信源编码－概念无失真信源编码要求精确地复现信源的输出保证信源的全部信息无损的送给信宿研究方法只考虑有效性，不考虑可靠性将信道及信道编解码整体看成一个无噪无损信道无失真信源编码器信源X={x1,x2 ,...,x q}码W=｛W1,W2,...,W q｝码符号集C=｛c1,c2,...,c m｝无失真信源编码器－示意图无失真信源编码器－输入输出描述信源符号集X＝[x1,x2,…x n]，共有n个信源符号。

码符号集C＝[c1,c2,…c m]，共有m个码符号。

码符号集中的元素称为码元或者码符号。

码字集合W=[W1,W2,…W n]，与信源符号一一对应码字Wi ＝（ci1ci2…ciki）其中，长度ki称为码字长度，简称码长。

可以看出，编码效率并不是很高。
4、费诺编码

将概率按从大到小的顺序排列，令：
p(x1)≥ p(x2)≥…≥ p(xn)

按编码进制数将概率分组，使每组概率尽可能接近或相
等。如编二进制码就分成两组，编 m 进制码就分成 m
组。

给每一组分配一位码元。 将每一分组再按同样原则划分，重复步骤 2 和 3，直 至概率不再可分为止。
麦克米伦不等式：设信源为 U u1 , u2 ,, un ，对其进行r 元信源编码，相应码字长度为 l1 , l2 ,, ln ，则唯一可译码 存在的充要条件是：
r
i 1
n
li
1

不同编码方式的衡量标准
平均码长：对离散无记忆信源进行信源编码，设编码后各个 码字的码长分别为

信源熵为：H(X)=2.75(比特/符号) 平均码长为：
K (0.25 0.25) 2 0.12 2 3 0.0625 4 4 2.75 （比特／符号）

编码效率为η=1。之所以如此，因为每次所分两组的 概率恰好相等。
5、哈弗曼编码 哈夫曼(Huffman) 编码是一种效率比较高的变长无失 真信源编码方法。
0 1
即时
s2
任何一个码字不是其它码字的延长或前缀
即 时 码

即时码的判决准则
克拉夫特不等式：设信源为 U u1 , u2 ,, un ，对其进行r 元信源编码，相应码字长度为 l1 , l2 ,, ln ，则即时码存在 的充要条件是：
r
i 1
n
li
1

唯一可译码的判决准则
2、编码的分类 信源编码可看成是从信源符号集到码符号集的一种映射，即将 信源符号集中的每个元素（可以是单符号，也可以是符号序列）映 射成一个长度为n的码字。对于同一个信源，编码方法是多种的。 【例5.1】 用{u1 ，u2 ，u3，u4， } 表示信源的四个消息，码符号集 为{0,1}，表1列出了该信源的几种不同编码。 表1 同一信源的几种不同编码 信 源 消息 u1 u2 u3 各消息 概率 q(u1) q(u2) q(u3)

所以送一个信源符号x需要的平均信息率为：
K KL logm L
信息率最小就是找到一种编码方式使
KL logm L
最小。
5.2.1定长编码定理
定义：各个码字码长都相等的码 定长码中每个码字长度相等，所以只要定长码是非奇异
码，则必为唯一可译码
非奇异码 唯一可译码
即时码
非奇异码 唯一可译码
即时码
变长码
等长码
消息
概率
C1
C2
C3
C4
C5
C6
u1
1/2
000
0
0
0
1
01
u2
1/4
001
01
10
10
000
001
u3
1/16
010
011
110
1101 001
100
u4
1/16
011
0111 1110 1100 010
101
u5
1/16
100
01111 11110 1001 110
110
u6
1/16
101
解码：按照码符号的顺序，从根节点依次查询到终端节点，就得到对应的 信源符号。再从根节点对剩下的码符号序列做相同的处理，直到处理完码 符号序列中所有的码符号
对应表中的码4分析
A01Fra bibliotek01
1
0
0
1
0
10 1
0
1
000
001 010
011 100 101 110
111
一阶节点 二阶节点 三阶节点
唯一可译码存在的充要条件
我们之后介绍的是二元信道中的编码。

第五章信源编码信息论基础第五章信源编码 本章主要讨论的问题：5.1 离散信源编码5.1.1 编码器5.1.2分组码5.1.3定长码5.1.4 变长码5.2 连续信源编码5.3 相关信源编码简介信源编码：以提高通信有效性为目的的编码。

通常通过压缩信源的冗余度来实现。

采用的方法是压缩每个信源符号的平均比特数或信源的码率。

即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。

信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。

–无失真信源编码定理：是离散信源/数字信号编码的基础；–限失真信源编码定理：是连续信源/模拟信号编码的基础，如语音、图像等信号。

信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。

–离散信源编码：独立信源编码，可做到无失真编码；–连续信源编码：独立信源编码，只能做到限失真信源编码；–相关信源编码：非独立信源编码。

编码器编码器可以看作这样一个系统，它的输入端为原始信源S ，其符号集为；而信道所能传输的符号集为。

编码器的功能是用符号集X 中的元素，将原始信源的符号变换为相应的码字符号，所以编码器输出端的符号集为称为码字，为码字的码元个数，称为码字的码字长度，简称码长。

码字的集合C 称为码书。

称为码元。

12{,,...,}q S S S S =12{,,...,}r X x x x =12{,,...,}q S s s s =12{,,...,}r X x x x =编码器12:{,,...,}q C W W W 12:{,,...,}q C w w w i S i w i w i L i w i w i x例：二元信道的信源编码器：码符号集X={0,1}，如果要将信源通过二元信道传输，必须将信源编成二元码，这也是最常用的一种码。

等长码非等长码非奇异码非奇异码 等长码与变长码码中各个码字都是由同样多个码元构成的，称为等长码，反之，称为变长码。