《信息论与编码课件(第四章).》由会员分享，可在线阅读，更多相关《信息论与编码课件(第四章).（96页珍藏版）》请在金锄头文库上搜索。
1、第四章 无失真信源编码 电气信息工程学院 4.1 编码器及码的分类 4.2 等长码 4.4 等长信源编码定理 4.5变长码 4.6变长信源编码定理 4.7霍夫曼码和其它编码方法 4.8几种实用的无失真信源编码 小结 第四章 无失真信源编码 本章的重、难点内容 1、理解等长码和等长信源编码定理 2、理解和掌握变长码及变长码编码定理 3、理解Huffman编码、费诺码、香农码 4、了解几种实用的无失真信源编码方法，包括 （MH编码、算术编码、LZ码） 电气信息工程学院 第四章 无失真信源编码 编码的意义： 通信的基本问题：如何高速、高质地传送信息。 高速和高质鱼和熊掌。 编码讨论的问题： （1）质
2、量一定，如何提高信息传输速度（提高 编码效率或压缩比）- 信源编码（本章讨论 问题） （2）信道传输速度一定，如何提高信息传输质 量（抗干扰能力）-信道编码（下一章讨论） 电气信息工程学院 引言 信源编码：以提高通信有效性为目的的编 码。通常通过压缩信源的冗余度来实现。 采用的一般方法是压缩每个信源符号的平 均比特数或信源的码率。即同样多的信息 用较少的码率传送，使单位时间内传送的 平均信息量增加，从而提高通信的有效性 。 电气信息工程学院 引言 信道编码：是以提高信息传输的可靠性为 目的的编码。通常通过增加信源的冗余度 来实现。采用的一般方法是增大码率/带宽 。与信源编码正好相反。 密码：是
3、以提高通信系统的安全性为目的 的编码。通常通过加密和解密来实现。从 信息论的观点出发，“加密”可视为增熵 的过程，“解密”可视为减熵的过程。 电气信息工程学院 引言 信源编码理论是信息论的一个重要分支， 其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信 号编码的基础； 限失真信源编码定理：是连续信源/模拟信 号编码的基础。 电气信息工程学院 引言 信源编码的分类：离散信源编码、连续信 源编码和相关信源编码三类。 离散信源编码：独立信源编码，可做到无 失真编码； 连续信源编码：独立信源编码，只能做到 限失真信源编码； 相关信源编码：非独立信源编码。 电气信息工程学院 4.
4、1 编码器及码的分类 编码：信息的组织方式 编码的实质：对信源的原始符号按一定的 数学规则进行变换。 编码的目的： 信源编码：提高信息传输的有效性 信道编码：提高信息传输的可靠性 本章不考虑干扰问题 电气信息工程学院 4.1 编码器及码的分类 无失真编码器结构框图 几个术语： 信源符号： 信源输入码符号 (码元)： 电气信息工程学院 编码器信源码字 符号集 4.1 编码器及码的分类 码字Wi： 由xj (j=1,2,r)组成的长度为 li 的 序列，Wi与si一一对应。 码字长度 (码长)： Wi的长度li 编码器：将信源符号si变换成Wi的设备 信源编码 信源编码：把信源符号si映射为码字W
5、i的过程。 无失真编码：映射是一一对应、可逆的。 信源编码基本思想：尽可能缩短出现概率大的信 源符号的码字 电气信息工程学院 4.1 编码器及码的分类 码的分类 二元码：若码符号集X0，1，所得码字为一 些二元序列，则称二元码。在二元信道中传输 等长码（固定长度码）：若一组码中所有码字的 长度都相同(即li=l,i=1,q)，则称为等长码。 变长码：不满足等长码条件的码组称为变长码。 电气信息工程学院 4.1 编码器及码的分类 非奇异码：若一组码中所有码字都不相同(即所 有信源符号映射到不同的码符号序列，不同信源 符号可分辨)，则称为非奇异码。 奇异码：反之，若码组中含有相同的码字则为奇 异码
6、。 同价码：若码符号集X：x1,x2,xr中每个码 符号所占的传输时间都相同，则所得的码为同价 码。 电气信息工程学院 4.1 编码器及码的分类 码的N次扩展码： 电气信息工程学院 信源符号出现概率码1码2 s1 P(s1)000 s2P(s2)0101 s3 P(s3)10001 s4 P(s4)11111 信源码 字信源码 字信源码 字 a100W1W1=B1a5 . . . 010W2W1=B1 . . . . . . . a16 . . . . 111111=W4W4=B16 a2001W1W2=B2 a30001W1W3=B3 a40111W1W4=B4 4.1 编码器及码的分类 惟
7、一可译码：若码的任意一串有限长的码符号序 列只能被惟一地译成所对应的信源符号序列，则 此码称为惟一可译码（单义可译码）。否则就称 为非惟一可译码或非单义可译码。 表1中码1是惟一可译码，而码2是非惟一可译码 。因为对于码2，其有限长的码符号序列能译成 不同的信源符号序列。如码符号序列0010，可译 成s1s2s1或s3s1，就不惟一了。 问题：怎样才能做到无失真编码即惟一可译码？ 电气信息工程学院 4.2 等长码 若要实现无失真编码，不但要求信源符号si与码 字Wi是一一对应的，而且要求码符号序列的反变 换也是惟一的。即所编的码必须是惟一可译码。 对于等长码来说，若等长码是非奇异码，则它的 任
8、意有限长N次扩展码一定也是非奇异码。 等长非奇异码一定是惟一可译码。 电气信息工程学院 信源符号码1码2 s10000 s20111 s31010 s41111 非奇异码 唯一可译 码 奇异码 非惟一可 译码 4.2 等长码 等长编码惟一可译的必要条件： 其中： q为信源符号数,r为符号集中的码元数,l 为码长。 例如： 若信源符号数 q4，进行二元等长编码，则码 符号个数为 r 2。信源S存在惟一可译等长码 的条件是码长 l2。 若q8，r 2，l3。 电气信息工程学院 4.2 等长码 对 两边取对数得 平均每个信源符号所需的码符号个数 上式表明：对于等长惟一可译码而言，平均每个 信源符号至
9、少需要用 logqlogr个码符号来表 示。即：每个信源符号所需最短码长为 logq logr个。 电气信息工程学院 4.2 等长码 当r=2(二元码)时logr=1, 上式变成 上式表明：对于二元等长惟一可译码，平均每个 信源符号至少需要用logq个码符号来变换。 或：对信源进行二元等长不失真编码时，每个信 源符号所需的极限值为logq个。 电气信息工程学院 4.2 等长码 当考虑到符号之间的依赖关系或关联性时，可以 从N次扩展信源中去掉一些符号，使得总符号数 小于 ，这样使编码所需码字个数大大减少， 因此平均每个信源符号所需的码符号个数就可以 大大减少，从而提高传输效率。 当N足够长后，这
10、种误差概率可以任意小，做到 几乎无失真编码。 等长编码定理给出了信源进行等长编码所需码长 的理论极限值。 电气信息工程学院 4.4 等长信源编码定理 定理4.3 (等长信源编码定理): 一个熵为H(S)的离 散无记忆信源，若对信源长为N的符号序列进行 等长编码，设码字是从r个字母的码符号集中选 取l个码元组成。对于任意0，只要满足： 则当N足够大时，可实现几乎无失真编码，即译 码错误概率能为任意小。反之，若 当N足够大时，译码错误概率近 似为1,不可能实现无失真编码。 电气信息工程学院 4.4 等长信源编码定理 说明：定理4.3是在平稳无记忆离散信源的条件 下得出，但它同样适合于平稳有记忆信源
11、 。 当进行二元编码时，r2，则： 一般情况下，信源符号并非等概率分布，且符号 之间有很强的关联性，故信源的熵H(S)logq。 电气信息工程学院 等长编码时平均每个 信源符号所需的二元 码符号的理论极限 信源等 概分布 时 4.4 等长信源编码定理 从定理4.3可知，在等长编码中每个信源符号平 均所需的二元码符号可大大减少，从而使编码效 率提高。 定理4.3中的条件式可改写成： 电气信息工程学院 长为l的码符 号序列所能载 荷的最大信息 量 长为N的信源 序列平均携 带的信息量 4.4 等长信源编码定理 所以等长编码定理告诉我们：只要码字传输的信 息量大于信源序列携带的信息量，总可实现几乎
12、无失真编码。 令 它是编码后平均每个信源符号能 载荷的最大信息量，称为编码信息率。 可见，当编码信息率大于信源的熵时，才能实现 几乎无失真编码。 为衡量编码效果，引入编码效率。 电气信息工程学院 4.4 等长信源编码定理 称 为编码效率。 由定理4.3可得最佳等长编码的效率为： 如果自信息的方差 和均为定值时，只要 N足够大，编码错误就可以小于任一正数。也 即要求误差小于时， 电气信息工程学院 4.4 等长信源编码定理 信源序列长度N必须满足： 该式给出了在已知方差和信源熵的条件下，信源 序列长度N与最佳编码效率 和允许错误概率 的 关系。 允许错误概率越小，编码效率要求越高，则信源 序列长度
13、N就必须越长。 实际情况下，要实现几乎无失真的等长编码，N 需要非常大。 电气信息工程学院 4.4 等长信源编码定理 例 设离散无记忆信源 信源熵 自信息方差 若对信源S采用等长二元编码，要求编码效率 =0.96，允许错误概率 电气信息工程学院 4.4 等长信源编码定理 则得 即序列长度达4130万以上，这在实际中很难实现 。因此，一般来说，当N有限时，高传输效率的 等长码往往要引入一定的失真和错误，它不能像 变长码那样可以实现无失真编码。 下面介绍变长码，及其编码定理。 电气信息工程学院 4.5 变长码 4.5.1 惟一可译变长码与即时码 等长码仅当N很大才会有较高的编码效率； 变长码往往在
14、N不很大时就可编出效率很高而且 无失真的码。 等长码：非奇异 惟一可译 变长码：任意有限长N次扩展码是非奇异 惟一 可译 电气信息工程学院 4.5 变长码 即时码：在译码时无需参考后续的码符号就能立 即作出判断，译成对应的信源符号的惟一可译码 码4以“1”作为结束符号，起到逗号的作用，又 称为逗点码 。逗点码是一种即时码。 电气信息工程学院 信源符号出现概率码1码2码3码4 s1 s2 s3 s4 1/2 1/4 1/8 1/8 0 11 00 11 0 10 00 01 1 10 100 1000 1 01 001 0001 非惟一可译 奇异码 非惟一可译 非奇异码 惟一可译 非奇异码 惟一
15、可译 非奇异码 4.5 变长码 定义：如果一个码组中的任一个码字都不是另一 个码字的续长，或者说，任何一个码字都不是另 一个码字的前缀，则称为即时码也称非延长码或 前缀条件码。 电气信息工程学院 所有码 非奇异码 惟一可译码 即时码 4.5 变长码 4.5.2 即时码的树图构造法 构造即时码的一种简单方法是树图法。 电气信息工程学院 信源符号码4 s1 s2 s3 s4 1 01 001 0001 根：树的最上端 树枝的个数为r， r=2为二元码树 0 1 0 0 1 1 1 1 01 001 0001 码4的树图 A B C D 中间节点 （空心） 节点：树枝的终 端，从节点生出 树枝，每个节点 伸出r个枝 终端节点 （实心） 码字：从根到终 端节点对应的码 符号，又称树叶 4.5 变长码 按树图法构成的码一定满足即时码的充要条件， 因为从根到叶所走的路径各不相同，而且中间节 点不安排为码字，所以一定满足对前缀的限制。 该树的5个终端节点W1,W2,W3,W4,W5分别表示5个 二进制码字0，100，111，1010，1011 电气
