4.4 等长信源编码定理

例 设离散无记忆信源


信源熵 自信息方差
1 3 4 H ( S ) log 4 log 0.811(bit symbol ) 4 4 3
2 2 2
s1 , s2 S 3 1 P( s) , 4 4
D I ( si ) pi (log pi ) H ( S )
引言

信源编码理论是信息论的一个重要分支， 其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信 号编码的基础； 限失真信源编码定理：是连续信源/模拟信 号编码的基础。
引言

信源编码的分类：离散信源编码、连续信 源编码和相关信源编码三类。 离散信源编码：独立信源编码，可做到无 失真编码； 连续信源编码：独立信源编码，只能做到 限失真信源编码； 相关信源编码：非独立信源编码。
第四章 无失真信源编码

4.1 编码器及码的分类


4.2 等长码
4.4 等长信源编码定理 4.5变长码 4.6变长信源编码定理
4.7霍夫曼码和其它编码方法 4.8几种实用的无失真信源编码 小结
第四章 无失真信源编码


本章的重、难点内容 1、理解等长码和等长信源编码定理 2、理解和掌握变长码及变长码编码定理 3、理解Huffman编码、费诺码、香农码 4、了解几种实用的无失真信源编码方法，包括 （MH编码、算术编码、LZ码）
4.4 等长信源编码定理

所以等长编码定理告诉我们：只要码字传输的信 息量大于信源序列携带的信息量，总可实现几乎 无失真编码。 l 令 它是编码后平均每个信源符号能 载荷的最大信息量，称为编码信息率。 可见，当编码信息率大于信源的熵时，才能实现 几乎无失真编码。 为衡量编码效果，引入编码效率。
l R log r N N log r H ( S )
4.4 等长信源编码定理

信源序列长度N必须满足：
N D I (si )
2
2 H 2 (S ) (1 2 )
D I (si )


该式给出了在已知方差和信源熵的条件下，信源 序列长度N与最佳编码效率和允许错误概率的 关系。 允许错误概率越小，编码效率要求越高，则信源 序列长度N就必须越长。 实际情况下，要实现几乎无失真的等长编码，N 需要非常大。
非惟一可译 奇异码
非惟一可译 非奇异码
惟一可译 非奇异码
惟一可译 非奇异码

码4以“1”作为结束符号，起到逗号的作用，又 称为逗点码 。逗点码是一种即时码。
4.5 变长码

定义：如果一个码组中的任一个码字都不是另一 个码字的续长，或者说，任何一个码字都不是另 一个码字的前缀，则称为即时码也称非延长码或 前缀条件码。
4.1 编码器及码的分类

码的分类 二元码：若码符号集X＝{0，1}，所得码字为一 些二元序列，则称二元码。[在二元信道中传输]

等长码（固定长度码）：若一组码中所有码字的
长度都相同(即li=l,i=1,„,q)，则称为等长码。

变长码：不满足等长码条件的码组称为变长码。
4.1 编码器及码的分类
s2
s3 s4 信源 a1 a2 a3 a4 码
00＝W1W1=B1 001＝W1W2=B2 0001＝W1W3=B3 0111＝W1W4=B4
4.1 编码器及码的分类



惟一可译码：若码的任意一串有限长的码符号序 列只能被惟一地译成所对应的信源符号序列，则 此码称为惟一可译码（单义可译码）。否则就称 为非惟一可译码或非单义可译码。 表1中码1是惟一可译码，而码2是非惟一可译码。 因为对于码2，其有限长的码符号序列能译成不 同的信源符号序列。如码符号序列0010，可译成 s1s2s1或s3s1，就不惟一了。 问题：怎样才能做到无失真编码即惟一可译码？

4.5 变长码

即时码：在译码时无需参考后续的码符号就能立 即作出判断，译成对应的信源符号的惟一可译码
信源符号 s1 s2 s3 s4 出现概率 1/2 1/4 1/8 1/8 码1 0 11 00 11 码2 0 10 00 01 码3 1 10 100 1000 码4 1 01 001 0001


即序列长度达4130万以上，这在实际中很难实现。 因此，一般来说，当N有限时，高传输效率的等 长码往往要引入一定的失真和错误，它不能像变 长码那样可以实现无失真编码。 下面介绍变长码，及其编码定理。
4.5 变长码


4.5.1 的编码效率； 变长码往往在N不很大时就可编出效率很高而且 无失真的码。 等长码：非奇异 惟一可译 变长码：任意有限长N次扩展码是非奇异 惟 一可译
非奇异码 唯一可译 码
s1
奇异码 非惟一可 译码
s2
s3 s4
01
10 11
11
10 11
4.2 等长码



等长编码惟一可译的必要条件：q N r l 其中： q为信源符号数,r为符号集中的码元数,l为 码长。 例如： 若信源符号数 q＝4，进行二元等长编码，则码符 号个数为 r ＝2。信源S存在惟一可译等长码的条 件是码长 l≥2。 若q＝8，r ＝2，l≥3。
引言

信源编码：以提高通信有效性为目的的编 码。通常通过压缩信源的冗余度来实现。 采用的一般方法是压缩每个信源符号的平 均比特数或信源的码率。即同样多的信息 用较少的码率传送，使单位时间内传送的 平均信息量增加，从而提高通信的有效性。
引言

信道编码：是以提高信息传输的可靠性为 目的的编码。通常通过增加信源的冗余度 来实现。采用的一般方法是增大码率/带宽。 与信源编码正好相反。 密码：是以提高通信系统的安全性为目的 的编码。通常通过加密和解密来实现。从 信息论的观点出发，“加密”可视为增熵 的过程，“解密”可视为减熵的过程。
所有码 非奇异码 惟一可译码 即时码
4.5 变长码

4.5.2 即时码的树图构造法 构造即时码的一种简单方法是树图法。
码4 1 01 001 0001 s1 s2 s3 s4
4.1 编码器及码的分类

编码：信息的组织方式 编码的实质：对信源的原始符号按一定的 数学规则进行变换。 编码的目的： 信源编码：提高信息传输的有效性 信道编码：提高信息传输的可靠性

本章不考虑干扰问题
4.1 编码器及码的分类

无失真编码器结构框图
信源
S {S1, S2 ,..., Sq }
4.4 等长信源编码定理

定理4.3 (等长信源编码定理): 一个熵为H(S)的离 散无记忆信源，若对信源长为N的符号序列进行 等长编码，设码字是从r个字母的码符号集中选 取l个码元组成。对于任意ε＞0，只要满足：
l H (S ) N log r


则当N足够大时，可实现几乎无失真编码，即译 码错误概率能为任意小。反之，若 l H ( S ) 2 当N足够大时，译码错误概率近 N log r 似为1,不可能实现无失真编码。
4.2 等长码
N l q r 对 两边取对数得 N log q l log r

平均每个信源符号所需的码符号个数
l log q N log r

上式表明：对于等长惟一可译码而言，平均每个 信源符号至少需要用 logq／logr个码符号来表示。 即：每个信源符号所需最短码长为 logq／logr个。
码字Wi： 由xj (j=1,2,„,r)组成的长度为 li 的序列， Wi与si一一对应。 码字长度 (码长)： Wi的长度li 编码器：将信源符号si变换成Wi的设备 信源编码 信源编码：把信源符号si映射为码字Wi的过程。 无失真编码：映射是一一对应、可逆的。 信源编码基本思想：尽可能缩短出现概率大的信 源符号的码字
i 1

若对信源S采用等长二元编码，要求编码效率 η=0.96，允许错误概率 105
3 3 2 1 1 2 (log ) (log ) (0.811) 2 0.4715 4 4 4 4
4.4 等长信源编码定理
0.4715 (0.96)2 7 4.13 10 则得 N (0.811)2 0.042 105
4.2 等长码


若要实现无失真编码，不但要求信源符号si与码 字Wi是一一对应的，而且要求码符号序列的反变 换也是惟一的。即所编的码必须是惟一可译码。 对于等长码来说，若等长码是非奇异码，则它的 任意有限长N次扩展码一定也是非奇异码。 等长非奇异码一定是惟一可译码。
信源符号 码1 00 码2 00
4.4 等长信源编码定理

说明：定理4.3是在平稳无记忆离散信源的条件 下得出，但它同样适合于平稳有记忆信源 。

当进行二元编码时，r＝2，则：
等长编码时平均每个 信源符号所需的二元 码符号的理论极限
l H (S ) N
信源等 概分布 时
l log q N

一般情况下，信源符号并非等概率分布，且符号 之间有很强的关联性，故信源的熵H(S)<<logq。

非奇异码：若一组码中所有码字都不相同(即所 有信源符号映射到不同的码符号序列，不同信源 符号可分辨)，则称为非奇异码。

奇异码：反之，若码组中含有相同的码字则为奇 异码。

同价码：若码符号集X：{x1,x2,„,xr}中每个码符 号所占的传输时间都相同，则所得的码为同价码。
4.1 编码器及码的分类



4.4 等长信源编码定理
H (S ) H (S ) 称 l R log r N