信息论PPt(叶中行)

1、第3章 数据压缩和信源编码 3.1 3.2 3.3 3.4 信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。3.1 等长码 信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。

2、 信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类离散信源编码：独立信源编码，可做到无失真编码；连续信源编码：独立信源编码，只能做到限失真信源编码；相关信源编码：非独立信源编码。干扰源干扰源 信道信道信道译码器信道译码器信道编码器信道编码器信源译码器信源译码器信源编码器信源编码器信宿信宿信源信源等效信源等效信宿等效干扰信道信息传输系统模型信息传输系统模型 信源编码示意图信源编码示意图信源信源信源编码器信源编码器信源译码器信源译码器信信宿宿 编码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为 ；而信道所能传输的符号集为 编码器的功能是用符号集X中的元素，将原始信源的符号

3、变换为相应的码字符号 ，所以编码器输出端的符号集为 称为码字， 为码字 的码元个数，称为码字 的码字长度，简称码长。 12 ,.,qSS SS12 ,., rXx xx12 ,.,qSS SS12 ,.,rXx xx编码器编码器12:,.,qCW WW12:,.,qCWWWiSiwiwiLiwiw0,1,.1nkknnnnkuDDnkf :uuf xuukfR=fn设 为一信源字母集，为 进码字母集， ， 为正整数；映射称为等长编码，映射 ：称为相应的译码，对每个，（ ）=称为码字，码字全体构成之集合称由 编出的码。称为 的编码速率，简称码率。等长码有时定义3.也称1.1分组码。UUPX设离散

4、无记忆信源概率空间为1 2 3 例3.1.1 4 1/2 1/4 1/8 1/8对其单个符号进行二进制编码，即码元集合为= 0,11、二元码： 码符号集X=0,1，如果要将信源通过二元信道传输，必须将信源编成二元码，这也是最常用的一种码。2、等长码： 若一组码中所有码字的长度都相同，称为等长码。3、变长码： 若一组码中所有码字的长度各不相同，称为变长码。4、非奇异码： 若一组码中所有码字都不相同，称为非奇异码。3.2 变长编码信源符号出现概率码1码2码3码4s1s2s3s41/21/41/81/801100110100001110100100010100100015、奇异码： 若一组码中有相同

5、的码字，称为奇异码。6 、同价码: 每个码字占相同的传输时间 1212:,.7.:.,:(.)qiiiiNCWWWBBWWCNWBN若 码， 则码称 为 码码 的次 扩 展的次 扩 展 码8、唯一可译码： 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则称此码为唯一可译码。 9、即时码（瞬时编码）：没有一个码字是其他码字的前缀的唯一可译码称为。码非分组码分组码奇异码非奇异码非唯一可译码唯一可译码非即时码即时码10、码分类UUPX设 离 散 无 记 忆 信 源 概 率 空 间 为1 2 3 例 3.1.1 4 1/2 1/4 1/8 1/8对 其 单 个 符 号 进 行

6、二 进 制 编 码 ， 即 码 元 集 合为= 0,1 1 02 01 3 0114 111例3.2.2 信源字母 码字2、即时码的树图构造法树根码字的起点树枝数码的进制数结点码字或码字的一部分节数码长端点码字满树等长码非满树变长码1001A1100100001101001111010010001码4的树图221il1mi1mDlllDlll （克莱夫特不等式）码字字母取值于进字母集的即时码其码字长分别为：， ，.,时必须满足反之，对给定的满足上述不等式的一组( ， ，.,),必存在以它们为码字长定理3.的一2.1个即时码12341234( ,),1,2,2,3, Xa a a allll设二

7、进制码树中应用克莱夫特不等式判断是例否为唯一可译码126126126 1( ) iisssSpp sp pprlllr设离散信源将此信源编码成 元唯一可译码，其对应的码长为( , , )=(1,1,2,3,2,3),求例值的下限 3.2. () 2 iDliXDLLHXDp一个随机变量 的任何 进即时码的平均码长 应满足：其中等号成立当且仅当=定理 *() () () ()=11DLH XlHXHXH XLl 一个 进唯一可译码的冗余度定义为其平均长度与信源熵的差即 冗余度=或 相对冗余度或定义 通用信源编码本节将主要介绍 LZ算法， 改进的LZ-Welcn 算法 Kieffer-Yang