下载文档原格式
第5章无失真信源编码定理●通信的实质是信息的传输。
高效率、高质量地传送信息又是信息传输的基本问题。
●信源信息通过信道传送给信宿，需要解决两个问题：第一，在不失真或允许一定失真条件下，如何用尽可能少的符号来传送信源信息，以提高信息传输率。
第二，在信道受干扰的情况下，如何增强信号的抗干扰能力，提高信息传输的可靠性同时又使得信息传输率最大。
●为了解决以上两个问题，引入了信源编码和信道编码。
●提高抗干扰能力（降低失真或错误概率）往往是增加剩余度以降低信息传输率为代价的；反之，要提高信息传输率往往通过压缩信源的剩余度来实现，常常又会使抗干扰能力减弱。
●上面两者是有矛盾的，然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。
●第5章着重讨论对离散信源进行无失真信源编码的要求、方法及理论极限，得出极为重要的极限定理——香农第一定理。
5.1编码器●编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。
●图5.1就是一个编码器，它的输入是信源符号集S={s 1,s 2,…,s q }。
同时存在另一符号集X={x 1,x 2, …,x r }，一般元素x j 是适合信道传输的，称为码符号（或称为码元）。
编码器是将信源符号集中的符号s i （或者长为N 的信源符号序列a i ）变换成由x j（j=1,2, …,r ）组成的长度为l i的一一对应序列。
●这种码符号序列W i 称为码字。
长度l i称为码字长度或简称码长。
所有这些码字的集合C 称为码。
●编码就是从信源符号到码符号的一种映射，若要实现无失真编码，必须这种映射是一一对应的、可逆的。
编码器S ：{s 1,s 2,…s q }X ：{x 1,x 2,…x r }C ：{w 1,w 2,…w q }（w i 是由l i 个x j （x j 属于X ））组成的序列，并于s i 一一对应一些码的定义●二元码：若码符号集为X={0,1}，所得码字都是一些二元序列，则称为二元码。
第五章无失真信源编码定理与编码5．1．1 信源编码和码的类型1．信源编码2．码的类型若码符号集中符号数r=2称为二元码，r=3称为三元码，……，r元码。
若分组码中所有码字的码长都相同则称为等长码，否则称为变长码。
若分组码中所有码字都不相同则称为非奇异码，否则称为奇异码。
若每个码符号x i∈X的传输时间都相同则称为同价码，否则称为非同价码。
若分组码的任意一串有限长的码符号只能被唯一地译成所对应的信源符号序列则称为唯一可译码，否则称为非唯一可译码。
若分组码中,没有任何完整的码字是其他码字的前缀，则称为即时码（又称非延长码或前缀条件码），否则称为延长码。
本章主要研究的是同价唯一可译码.5．1．2 即时码及其树图构造法即时码（非延长码或前缀条件码)是唯一可译码的一类子码。
即时码可用树图法来构造。
构造的要点是:（1）最上端为树根A，从根出发向下伸出树枝，树枝总数等于r，树枝的尽头为节点。
（2）从每个节点再伸出r枝树枝，当某节点被安排为码字后,就不再伸枝，这节点为终端节点。
一直继续进行，直至都不能伸枝为止。
(3）每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。
即时码可用树图法来进行编码和译码。
从树图可知，即时码可以即时进行译码。
当码字长度给定，即时码不是唯一的。
可以认为等长唯一可译码是即时码的一类子码。
5．1．3 唯一可译码存在的充要条件（1)对含有q个信源符号的信源用含r个符号的码符号集进行编码,各码字的码长为l1，l2,…,l q的唯一可译码存在的充要条件是,满足Kraft不等式5．1．4 唯一可译码的判断法唯一可译码的判断步骤:首先，观察是否是非奇异码.若是奇异码则一定不是唯一可译码。
其次，计算是否满足Kraft不等式。
若不满足一定不是唯一可译码。
再次，将码画成一棵树图，观察是否满足即时码的树图的构造,若满足则是唯一可译码。
或用Sardinas和Patterson设计的判断方法：计算出分组码中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为唯一可译码;若有则一定不是唯一可译码.上述判断步骤中Sardinas和Patterson设计的判断方法是能确切地判断出是否是唯一可译码的方法,所以可以跳过前三个步骤直接采用该判断法。
