信息论与编码[第五章无失真信源编码定理与编码]山东大学期末考试知识点复习

5.1某离散无记忆信源的概率空间为采用香农码和费诺码对该信源进行二进制变长编码，写出编码输出码字，并且求出平均码长和编码效率。

解：计算相应的自信息量1)()(11=-=a lbp a I 比特 2)()(22=-=a lbp a I 比特 3)()(313=-=a lbp a I 比特 4)()(44=-=a lbp a I 比特 5)()(55=-=a lbp a I 比特 6)()(66=-=a lbp a I 比特 7)()(77=-=a lbp a I 比特 7)()(77=-=a lbp a I 比特根据香农码编码方法确定码长1)()(+<≤i i i a I l a I平均码长984375.164/6317128/17128/1664/1532/1416/138/124/112/1L 1=+=⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯=由于每个符号的码长等于自信息量，所以编码效率为1。

费罗马编码过程5.2某离散无记忆信源的概率空间为使用费罗码对该信源的扩展信源进行二进制变长编码，(1) 扩展信源长度，写出编码码字，计算平均码长和编码效率。

(2) 扩展信源长度，写出编码码字，计算平均码长和编码效率。

(3) 扩展信源长度，写出编码码字，计算平均码长和编码效率，并且与(1)的结果进行比较。

解：信息熵811.025.025.075.075.0)(=--=lb lb X H 比特/符号 （1）平均码长11=L 比特/符号编码效率为%1.81X)（H 11==L η（2）平均码长为84375.0）3161316321631169（212=⨯+⨯+⨯+⨯=L 比特/符号 编码效率%9684375.0811.0X)（H 22===L η（3）当N=4时，序列码长309.3725617256362563352569442569242562732562732256814=⨯+⨯+⨯⨯+⨯⨯+⨯⨯+⨯+⨯⨯+⨯=L平均码长827.04309.34==L %1.98827.0811.0X)（H 43===L η可见，随着信源扩展长度的增加，平均码长逐渐逼近熵，编码效率也逐渐提高。

第五章 信源编码（第十讲）（2课时）主要内容：（1）编码的定义（2）无失真信源编码 重点：定长编码定理、变长编码定理、最佳变长编码。

难点：定长编码定理、哈夫曼编码方法。

作业：5。

2，5。

4，5。

6；说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途。

另外，注意，解题方法。

多加一些内容丰富知识和理解。

通信的实质是信息的传输。

而高速度、高质量地传送信息是信息传输的基本问题。

将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。

为了解决这两个问题，就要引入信源编码和信道编码。

一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。

二者是有矛盾的。

然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。

这些结论对各种通信系统的设计和估价具有重大的理论指导意义。

§3.1 编码的定义编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。

讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。

图 3.1是一个信源编码器，它的输入是信源符号},,,{21q s s s S ，同时存在另一符号},,,{21r x x x X ，一般来说，元素xj 是适合信道传输的，称为码符号（或者码元）。

编码器的功能就是将信源符号集中的符号s i （或者长为N 的信源符号序列）变换成由x j (j=1,2,3,…r)组成的长度为l i 的一一对应的序列。

输出的码符号序列称为码字，长度l i 称为码字长度或简称码长。

可见，编码就是从信源符号到码符号的一种映射。

若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。

1第1章 概论1. 信号(适合信道传输的物理量）、信息（抽象的意识/知识，是系统传输、转换、处理的对象）和消息(信息的载体)定义；相互关系：(1信号携带消息，是消息的运载工具(2信号携带信息但不是信息本身(3同一信息可用不同的信号来表示(4同一信号也可表示不同的信息。

2. 通信的系统模型及目的:提高信息系统可靠性、有效性和安全性，以达到系统最优化.第2章 信源及信息量1. 单符号离散信源数学模型2. 自信息量定义：一随机事件发生某一结果时带来的信息量I(xi)=-log2P(xi)、单位：bit 、物理意义：确定事件信息量为0；0概率事件发生信息量巨大、性质：I(xi)非负；P(xi)=1时I(xi)=0；P(xi)=0时I(xi)无穷；I(xi)单调递减；I(xi)是随机变量。

3. 联合自信息量：I(xiyi)=- log2P(xiyj) 物理意义：两独立事件同时发生的信息量=各自发生的信息量的和、条件自信息量：I(xi/yi)=- log2P(xi/yj)；物理意义：特定条件下(yj 已定)随机事件xi 所带来的信息量。

三者关系：I(xi/yi)= I(xi)+ I(yi/xi)= I(yi)+ I(xi/yi)4. 熵：定义(信源中离散消息自信息量的数学期望)、单位(比特/符号)、物理意义(输出消息后每个离散消息提供的平均信息量；输出消息前信源的平均不确定度；变量的随机性)、计算:(H(X)=-∑P(xi)log2 P(xi)) 1)连续熵和离散的区别：离散熵是非负的2)离散信源当且仅当各消息P相等时信息熵最大H (X )=log 2 n 。

3)连续信源的最大熵:定义域内的极值. 5.条件熵H(Y/X) = -∑∑P(xiyj) log2P(yj/xi)，H (X /Y )= -∑∑P(xiyj) log2P(xi/yj) 、物理意义：信道疑义度H(X/Y)：信宿收到Y 后，信源X 仍存在的不确定度，有噪信道传输引起信息量的损失，也称损失熵。

第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}，所得码字都是一些二元序列，则称为二元码。

信息论与编码复习总结题型：填空、解答、计算1、编码：无失真与限失真信源编码定理编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真三大定理:无失真信源编码定理（第一极限定理）（可逆）信道编码定理（第二极限定理）限失真信源编码定理（第三极限定理）（不可逆）Shannon(香农)信息论：在噪声环境下，可靠地、安全地、有效地传送信息理论。

通信系统模型方框图:信道的种类很多，如电信中常用的架空明线、同轴电缆、波导、光纤、传输电磁波的空间等都是信道。

也可以从信道的性质或其传送的信号情况来分类，例如：无干扰信道和有干扰信道、恒参信道和变参信道、离散信道（Discrete Channel）和连续信道（Continuous Channel）、单用户信道和多用户信道等。

信源的描述：通过概率空间描述平稳包含齐次，而齐次不包含平稳（重要，第二章计算题）定义：若齐次马尔可夫链对一切i,j存在不依赖于i的极限，则称其具有遍历性，p j称为平稳分布（如下）设有一齐次马尔可夫链，其状态转移矩阵为P，其稳态分布为w j=p(s j)自信息量的特性：p(x i)=1,I(x i)=0; p(x i)=0,I(x i)=∞;非负性；单调递减性；可加性；定义：联合概率空间中任一联合事件的联合（自）信息量为：定义：对于给定离散概率空间表示的信源，在出现y事件后所提供有关事件x的信息量定义互信息，单位为比特信道模型：二进制离散信道BSC；离散无记忆信道DMC；波形信道信源编码器的目的：是使编码后所需的信息传输率R尽量小。

信源编码：主要任务就是减少冗余，提高编码效率。

唯一可译码：（任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码）{0,10,11}为唯一可译码，任意有限长码序列：100111000。

（分类）即时码和非即时码变长编码定理：（解答，重要）???1、平均码长：2、根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。

第五章无失真信源编码定理与编码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设计的判断方法是能确切地判断出是否是唯一可译码的方法,所以可以跳过前三个步骤直接采用该判断法。

信息论基础与编码(第五章)5-1 有一信源，它有六种可能的输出，其概率分布如下表所示，表中给出了对应的六种编码12345C C C C C 、、、、和6C 。

（1） 求这些码中哪些是唯一可译码； （2） 求哪些是非延长码（即时码）； （3） 对所有唯一可译码求出其平均码长。

001111解：（1）1,2,3,6是唯一可译码； (2)1,3,6是即时码。

5-2证明若存在一个码长为12,,,ql l l ⋅⋅⋅的唯一可译码，则一定存在具有相同码长的即时码。

证明：由定理可知若存在一个码长为的唯一可译码，则必定满足kraft 不等式1。

由定理4可知若码长满足kraft 不等式，则一定存在这样码长的即时码。

所以若存在码长的唯一可译码，则一定存在具有相同码长P （y=0）的即时码。

5-3设信源126126()s s s S p p p P s ⋅⋅⋅⎡⎤⎡⎤=⎢⎥⎢⎥⋅⋅⋅⎣⎦⎣⎦，611i i p ==∑。

将此信源编码成为r 元唯一可译变长码（即码符号集12{,,,}r X x x x =⋅⋅⋅），其对应的码长为（126,,,l l l ⋅⋅⋅）=（1，1，2，3，2，3），求r 值的最小下限。

解：要将此信源编码成为 r 元唯一可译变长码，其码字对应的码长（l 1 ,l 2 ,l 3, l 4,l 5, l 6）=(1,1,2,3,2,3) 必须满足克拉夫特不等式，即LqL L ,,2,1 ∑=-qi l ir1≤4⋅LqL L ,,2,1132321161≤+++++=------=-∑r r r r r r ri li所以要满足 122232≤++rr r ，其中 r 是大于或等于1的正整数。

可见，当r=1时，不能满足Kraft 不等式。

当r=2, 1824222>++，不能满足Kraft 。

当r=3, 127262729232<=++，满足Kraft 。

所以，求得r 的最大值下限值等于3。