信息论第5章 无失真信源编码

第5章无失真信源编码1编码的意义通信的基本问题：如何高速、高质地传送信息。高速和高质＝鱼和熊掌。编码讨论的问题：（1）质量一定，如何提高信息传输速度（提高编码效率或压缩比）---信源编码（本章讨论问题）（2）信道传输速度一定，如何提高信息传输质量（抗干扰能力）----信道编码（下一章讨论）2信源输出的符号序列,需要变换成适合信道传输的符号序列,一般称为码序列.对信源输出的原始符号按照一定的数学规则进行的这种变换称为编码.完成编码功能的器件称为编码器.接收短有一个译码器完成相反的功能.5.1编码器3编码：信息的组织方式编码的实质：对信源的原始符号按一定的数学规则进行变换。编码的目的：提高信息传输的有效性（信源编码）；提高信息传输的可靠性。（信源或信道编码）

4几个术语：信源符号：信源输入S={s1,s2,…,sq}码符号(码元)：X={x1,x2,…,xr}码字Wi：由xj(j=1,2,…,r)组成的长度为li的序列，Wi与si一一对应。码字长度(码长)：Wi的长度li码(码书)：码字Wi的集合C={W1,W2,…,Wq}编码器：将信源符号si变换成Wi的设备5信源编码信源编码：把信源符号si映射为码字Wi的过程。无失真编码：映射是一一对应、可逆的。无失真信源编码：尽可能精确的再现信源的输出信源编码基本思想：尽可能缩短出现概率大的信源符号的码6通信的根本问题是将信源的输出，经信道传输在接收端精确的或近似地重现出来，因此要首先解决两个问题：

第三章中已经回答了第一个问题,这一章要讨论的是第二个问题.信源编码器如下图所示:7891011定长码和变长码12奇异码和非奇异码13N次扩展码141516说明:本章我们讨论的都是同价码,即每个码元符号所占的传输时间是相同的.显然,对同价码而言,定长码中每个码字的传输时间是相同的,而变长码中每个码字的传输时间不一定相等.175.2分组码

定义：18奇异性1920唯一可译性21即时性2223一个码，若其中所有码字均处于终端节点，即端点上，则该码为非续长码。2425不超过终端节点也叫端点。262728该树的5个终端节点W1,W2,W3,W4,W5分别表示5个二进制码字0，100，111，1010，1011

按树图法构成的码一定满足即时码的充要条件，因为从根到叶所走的路径各不相同，而且中间节点不安排为码字，所以一定满足对前缀的限制。29各节点（包括树根）长出的树枝树等于r30315.3定长码

（5－1）32若令N＝1，则有即（5－2）（5－3）与5－1式一致。式5－3表示平均每个原始信源符号所需要的码符号个数，对于定长码，平均每个原始信源符号至少需要用个码符号变换。333435定理5.3.136其中前一部分被视为正定理，后一部分被视为逆定理。373839编码效率4041425.4变长码变长码是在码符号序列长度N不大时就能编出效率很高而且无失真的信源码。要实现无失真的信源编码，变长码必须是唯一可译码。变长码要满足唯一可译码的条件，它必须是非奇异码，而且任意有限长N次扩展码也是非奇异的。为能即时进行译码，变长码还必须是即时码。435.4.1码的分类和主要编码方法44454647485.4.2Kraft不等式49注意：仅仅是存在！5.4.2克拉夫特不等式

与麦克米伦不等式

克拉夫特（kraft）不等式505152定理5.4.3若存在一个码长为l1，l2，…，lq的惟一可译码，则一定存在具有相同码长的即时码。若存在一个码长为l1，l2，…，lq的惟一可译码满足Kraft不等式（定理5.4.2）

存在具有相同码长的即时码（定理5.4.1）任何一个惟一可译码均可用一个即时码来代替，而不改变任一码字的长度。即时码可用树图法来构造。因此要构造惟一可译码，只需讨论构造即时码。535.4.3唯一可译码的判别准则若码长l1,l2,…,lq不满足Kraft不等式à不是惟一可译码；反之，l1,l2,…,lq满足Kraft不等式的码，不一定是惟一可译码。结论：不能用克拉夫特不等式，只能根据定义判断码C是否是惟一可译码。判别依据：非惟一可译变长码有限长的码符号序列能译成两种不同的码字序列。54例：如下图中情况发生，其中Ai，Bi都是码字(Ai,Bi

C)。

B1一定是A1的前缀，而A1的尾随后缀一定是另一码字B2的前缀，B2的尾随后缀又是其他码字的前缀。最后，码符号序列的尾部一定是一个码字。55判别准则：5657唯一可译码的判别方法唯一可译码的判断方法：方法一：（可确切判断）计算出分组码中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为唯一可译码，否则一定不是唯一可译码。方法二：步骤如下

1。观察是否是非奇异码。若是奇异码则一定不是唯一可译码。2。计算是否满足Kraft不等式。若不满足则一定不是唯一可译码。3。画出码树，观察是否满足即时码的树图的构造，若满足则是唯一可译码。585.4.4变长编码定理对于已知信源S可用码符号X进行变长编码，而且对同一信源可有多种即时码或惟一可译码。选择哪一种呢？从高速度传输信息的角度，希望用短的码符号组成码字，即用码长作为选择准则-----引进码的平均长度。59平均码长6061对于某一信源和某一码符号集来说，若有一个惟一可译码，其平均长度小于所有其他惟一可译码的平均长度，则该码称为紧致码，或称最佳码无失真信源编码的基本问题

找出紧致码。62636465定理4.8（香农信息论的主要定理之一）的结论：要做到无失真的信源编码，编码每个信源符号平均所需最少的r元码元数为信源的熵Hr(S)。即Hr(S)是无失真信源压缩的极限值。若编码的平均码长小于信源的熵值Hr(S)，则惟一可译码不存在，在译码或反变换时必然要带来失真或差错。通过对扩展信源进行变长编码，当N∞时，平均码长Hr(S)。66香农第一定理的物理意义无失真信源编码的实质：对离散信源进行变换

变换后信源符号(信道的输入信源)尽可能为等概率分布新信源符号平均所含的信息量达到最大à

使信道的信息传输率R达到信道容量C，实现信源与信道理想的统计匹配。无失真信源编码定理通常又称为无噪信道编码定理。表述为：若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使得在无噪无损信道上能无差错地以最大信息传输率C传输信息，但要使信道的信息传输率R大于C而无差错地