信息论 基础理论与应用第三版(傅祖芸) 第5章 讲义

第5章无失真信源编码定理5.1编码器5.2等长码5.6变长信源编码定理5.4等长信源编码定理5.5变长码2021/6/271

信息通过信道传输到信宿的过程。要做到既不失真又快速地通信，需要解决两个问题：信源编码:

在不失真或允许一定失真条件下，提高信息传输率.信道编码:

在信道受到干扰的情况下，增加信号的抗干扰能力，同时又使得信息传输率最大.最佳编码：一般来说，抗干扰能与信息传输率二者相互矛盾。而编码定理理论上证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。信源编码：信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的就是要减少冗余，提高编码效率。

引言2021/6/272研究方法研究信源编码时，将信道编码与译码看成是信道的一部分，从而突出信源编码；研究信道编码时，将信源编码与译码看成是信源与信宿的一部分，从而突出信道编码。5.1编码器编码器：

对信源的符号按一定的数学规则进行的变换。它可以看作这样一个系统，它的输入端为原始信源S，其符号集为而信道所能传输的符号集为

2021/6/273

编码器功能：用符号集X中的元素，将原始信源的符号变换为相应的码字符号，编码器输出符号集为

(码或码书)

称为码字，li

为码字的码元个数（码字长度，码长）。码字集合C称为码或码书。2021/6/274

若要实现无失真编码，这种映射应是一一对应的可逆映射。编码的形式化描述：

从信源符号到码符号的一种映射或：2021/6/2751、二元码与r元码

2元码:码符号集X={0,1}.如果将信源通过二元信道传输，必须将信源编成二元码，这是最常用的一种码。

r元码:码符号集有r个符号的编码。2、等长码与变长码等长码:一组码中所有码字的长度都相同。变长码:一组码中所有码字的长度各不相同。

码的分类及定义2021/6/2763、非奇异码与奇异码非奇异码:一组码中所有码字都不相同。

奇异码:一组码中有相同的码字。2021/6/2774、同价码同价码:

码符号集中每个码符号所占的传输时间都相同(大多数情况)。变长码中每个码字的传输时间就不一定相同。（摩尔斯电报码，点-划所占传输时间不同）5、码的N次扩展

若某码C，它把信源S中的符号一一变换成码C中的码字，则码C的N次扩展码是所有N个码字组成的码字序列的集合B:S扩展2021/6/278码C码B扩展信源扩展码N次扩展N次扩展2021/6/279[例]

设信源S的概率空间为：

若通过—个二元信道进行传输，须把信源符号变换成0，1符号组成的码符号序列(二元序列)。采用如下二元码，如下表所示（q=4）：试求码的二次扩展码。2021/6/2710信源S的二次扩展信源：则码的二次扩展码为：2021/6/27116、唯一可译码(单义可译码）由码构成的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列。否则,就为非惟一可译码或非单义可译码。

例：对于二元码，当任意给定一串码字序列，例如…10001101…只可唯一地划分为1,00,01,1,01，因此是惟一可译码；而对另一个二元码，当码字序列为…01001…可划分为0,10,01或01,0,01，所以是非惟一可译的。2021/6/2712唯一可译码的条件

1）不同的信源符号变换成不同的码字(非奇异码)；

2）任意有限长的信源序列所对应的码元序列各不相同.

即:码的任意有限长N次扩展码都是非奇异码。Or:

码符号序列的反变换也唯一的（扩展码非奇异）

原因：若要使某一码为惟一可译码，则对于任意有限长的码符号序列，必须只能被惟一地分割成一个个的码字，才能实现唯一的译码。2021/6/2713无失真的编码的一般条件

1）码字与信源符号之间一一对应（非奇异码）；

2）码符号序列的反变换也唯一的（扩展码非奇异）。即：编码必须是唯一可译码。否则，就会引起译码的错误与失真。等长码是唯一可译码的条件

若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。因此，等长非奇异码字一定是唯一可译码,因为采用固定长度划分码字序列.5.2等长码2021/6/27141）若对每个信源符号进行等长编码，则必须满足:

其中:l是码长，r是码符号集的码元数，q信源符号数。2）若对信源的N次扩展信源进行编码，必须满足:表示平均每个信源符号所需的码符号个数。即

为了使等长码为非奇异码（唯一可译码），那么:2021/6/2715例证：根据依赖关系，信源符号平均所需码符号数可减少。例设信源而其依赖关系为：1）若不考虑符号间的依赖关系，可得每符号码长l＝2；2）若考虑符号间的二元依赖关系，可作二次扩展信源进行分析。根据条件概率仅有4项的概率不为零，可得扩展信源的码长l’=2，而每个信源符号的平均码长为l’/N=1

。2021/6/27165.4等长信源编码定理给出了等长信源编码所需码长的极限值。定理等长信源编码定理

一熵为H(S)的离散无记忆信源，若对其N次扩展信源进行等长r元编码，码长为l，对于任意大于0，只要满足当N足够大时，则可以实现几乎无失真编码，反之，若：则不可能实现无失真编码，当N趋向于无穷大时，译码错误率接近于1。2021/6/2717分析：定理中的条件式可写成

左边:长为l

的码符号（码字）所能载荷的最大信息量；

右边:长为N的信源符号序列平均携带的信息量。因此，定理说明了：只要码字传输的最大信息量大于信源序列携带的信息量，则可以实现无失真编码。编码后信源的信息传输率

令：可见，只有编码后信息传输率

，才能实现无失真编码。(编码后，平均每个信源符号承载的信息量)2021/6/2718最佳编码效率：

由定理知，编码效率移项后，2021/6/2719当信源符号自信息量的方差和确定时，只要N足够大，就可以实现允许错误概率：这时要求序列长度满足：（任意一正数）信源序列长度N

一般情况下，在已知信源熵的情况下，信源序列长度N的选择，与最佳编码效率和允许错误概率有关。可以证明：2021/6/2720若采用等长二元编码，要求编码效率，允许错误率则：例：设离散无记忆信源：2021/6/27211、唯一可译变长码5.5变长码优势：容易实现效率很高的编码。变长码也必须是唯一可译码，才能实现无失真编码。码1是一个奇异码，故不是唯一可译码；码2也不是唯一可译码，因为收到一串序列，无法唯一译出对应的原符号序列，如01000，即可译作s4s3s1,也可译作s4s1s3,s1s2s3或s1s2s1s1；2021/6/2722码2本身不是奇异码，但从有限长的码符号序列是奇异码。如果把码2的2次扩展码写出，则会发现：

S1S3的扩展码字为：000；

S3S1的扩展码字也为：000

所以，当出现000序列时候，不能唯一地确定信源符号。码3和码4都是唯一可译的，但码3和码4也不太一样。码4称作逗点码，只要收到1，就可以立即作出译码；而码3不同，当收到一个或几个码时，必须参考后面的码才能作出判断。

100010010…2021/6/2723即时码接收端收到一个完整的码字后，就能立即进行译码，无须参考后面的码字就可以作出唯一判断（译码）。对于非即时码，接收端收到一个完整的码字后，还需等后续码元接收后才能判断是否可以唯一译码。非延长码（前缀条件码）

若码C中，没有任何完整的码字是其他码字的前缀，即设是码C中的任意码字，而它不是其他码字（j>m）的前缀，则此码为非延长码（或前缀条件码）。！！显然：即时码等价于前缀条件码（非延长码）。2021/6/2724码3：s1的码字是s2,s3,s4的码字的前缀（词头）；s2的码字是s3,s4的码字的前缀；s3的码字是s4的码字的前缀；当译码时，接受到一个完整码字后，不能马上译码，还需考察后续码元的情况才能进行正确译码；如：100010010…可译码为：s4s3？…因此，码3不是即时码；但确是唯一可译码。码4：码本中的任何一个码字都不是其他码字的前缀。当译码时，接受到一个完整码字后，不需要等待后续码元的情况即可正确译码；如：100010010…可译码为：s1s4s3…因此，码4是即时码，也是唯一可译码。2021/6/2725因此，对于码C：若其为唯一可译码，则必为非奇异码；若其为即时码，则必是唯一可译码；反之，作为唯一可译码，则不一定是即时码。所有的码非奇异码唯一可译码即时码（非延长码）2021/6/27262、即时码（非延时码）的树图构造法

对于给定码字集合C，可用码树来描述。同时，树图法可构造即时码。01001111010010001码4的树图描述2021/6/2727

在每个节点上都有r个分枝的树称为整树（满树），否则称为非整（满）树。

01

01

01

01010101

0101010101010101等长码二元码树（整树）树根——码字的起点树枝数—码符号数终端节点—码字阶数—码长中间节点2021/6/2728012012012012012012三元码树（整树）满树——变长码01001111010010001非满树2021/6/2729非即时码的树图中间节点安排为码字1.树图中间节点不作为码字；2.一旦某节点作为码字，则不再继续进行分枝。这样可保证每个码字不同，且满足前缀条件码的条件。一般编码方法选择相应节点作为码字：不同的路径上的分支，对应了相应的码元符号，则可得到所编码字。10001101001000构造即时码2021/6/2730编码举例（即时码，编码方式不同）都为即时码，但编码方式不唯一2021/6/2731编码举例（多元即时码）2021/6/2732译码方法

因为每一码元对应于一个的树图分枝路径，则即时码的树图可以用来译码。译码器系统对一串符号序列译码过程：1）首先从树根出发，根据接收的第一个码元符号来选择应走的第一条路径；2）若沿着所选路径走到某中间节点，再根据接收的第二个码元符号来选择第二条路经；3）若又走到中间节点，再依次继续选择路径，直到终端节点为止。这时，可根据所经历的枝路，判断出所接收的码字。4）重新返回树根，再作下一个接收码字的判断。

这样，便可将接收到的一串码符号序列译成信源符号序列。2021/6/27333、克拉夫特（Kraft）不等式定理对于码符号为的任意r元即时码

，若所对应的码长，则必定满足：反之，若码长满足上式，则一定存在这样的即时码。*可以证明，对于唯一可译码也须满足Kraft不等式。

这说明，其他唯一可译码并不比即时码占优。而即时码很容易用树图法构造，所以在讨论唯一可译码时，只需要讨论即时码就可以了。定理若存在一个码长为的唯一可译码，则一定存在一个同样长度的即时码。2021/6/2734例：设二进制码树中S=(s1,s2,s3,s4),L1=1,L2=2,L3=2,L4=3,应用Kraft不等式,得：不存在满足这种Li的唯一可译码如果将各码字长度改成L1=1,L2=2,L3=3,L4=3,则存在满足这种Li唯一可译码0001101011011码树111000110101102021/6/2735设信源编码后的码字为：码长为：码的平均长度（平均码长）为：5.6变长信源编码定理（码符号/信源符号）码的平均长度信息传输率（码率）：平均每个码元携带的信息量，即编码后信道的信息传输率：（比特/码符号）2021/6/2736

若信道传输一个码符号平均需要t秒钟，则编码后信道的每秒传输的信息量为：（比特/秒）由此可见：

平均码长越短，信息传输效率越高。紧致码（最佳码）对于某一信源和某一个码符号集合，若有一个唯一可译码，它的平均码长小于其他唯一可译码的长度。无失真信源编码的基本问题就是寻找紧致码。2021/6/2737定理

若对一熵为H(S)的离散无记忆信源S进行r元编码，则总是可以找到一种无失真编码方法构成唯一可译码，使其平均码长满足：

说明：下界：平均码长不能小于极限H(s)/logr,否则唯一可译码不存在。上界：给出了平均码长的上界。但并不是说大于这个上界就不能构成唯一可译码。而是说在上界范围内，可找到唯一可译码。2021/6/2738证明：1.下界证明：詹森不等式2021/6/2739因总可找到一种唯一可译码，其码长满足Craft不等式，所以则证得：由Craft不等式，此等式成立的充要条件：即：可见，只有当能够选择每个码长满足上述等式时候，平均码长才能够达到这个下界值。2021/6/2740

由于li

必须为正整数，所以也必须为正整数。那么，当该等式成立时，每个信源符号的概率分布必须呈现如下形式：如果这个条件满足，则只要选择：根据这些码长，按照树图法构造出一种唯一可译码，所得的码一定是紧致码。2021/6/27412.上界证明：只需证明存在一种唯一可译码满足即可。令则，选取每个码字的长度的原则是：显然知2021/6/2742即为Craft不等式；因此，用这样选择的码长满足Craft不等式，故可构造唯一可译码。但不一定是紧致码。两边对i求和，则有：由于2021/6/2743右边的不等式两边进行如下处理：平均码长因此，平均码长小于上界的唯一可译码存在。两边乘以P(si)后，求和。另外由于2021/6/2744无失真变长信源编码定理（香农第一定理）离散无记忆信源S的N次扩展信源，其熵为，且编码器码元符号集为.对信源进行编码，总可以找到一种编码方法，构成唯一可译码，使信源S中每个信源符号si所需要的平均码长满足当则得：2021/6/2745证明：设离散无记忆信源X的数学模型N次扩展由于无记忆性，有：2021/6/2746由前述定理，有：2021/6/2747定理含义：

要做到无失真信源编码，变换每个信源符号平均所需最少的r元码元数是信源的熵值。

若编码的平均码长小于信源的熵，则唯一可译码不存在，在译码时必然带来失真或差错。

同时，通过对扩展信源进行变长编码，当扩展长度N足够大时，平均码长可达到此极限值。

信源的熵是无失真信源压缩的极限值。

2021/6/2748定理推广：

可以推广到平稳有记忆信源和马尔科夫信源：2021/6/2749

如果将定理中的下式改写：为编码后平均每个信源符号所能承载的最大信息量，即变长编码后信源的信息传输率（编码信息率）。这样，香农第一定理也可表述为：

若R’>=H(S),就存在唯一可译变长编码；若R’<H(S),唯一可译边长码不存在，不能实现无失真德信源编码。则定义：等长编码2021/6/2750

从信道角度看，编码后信道的信息传输率：

由此可见，此时信道的信息传输率等于无噪无损信道的信道容量C，信息传输率最高。

因此，无失真信源编码的实质是：对离散信源进行适当编码，使变换后新的码符号信源（信道的输入信源）尽可能等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率R达到信道容量C，实