《[信息与通信]第三章无失真离散信源编码.ppt》由会员分享，可在线阅读，更多相关《[信息与通信]第三章无失真离散信源编码.ppt（32页珍藏版）》请在三一办公上搜索。
1、1,第3章 离散无记忆信源无失真编码,2,主要内容,3.1 信源编码概论3.2 码的唯一可译性3.3 定长编码定理和定长编码方法3.4 变长编码定理3.5 变长编码方法,3,3.1 信源编码概论,传输之前的两次变换：信源编码、信道编码。传输之后的两次反变换：信道译码、信源译码。变换与反变换是成对出现的。采取适当信道编码和译码措施后，可使信道传送的差错率降到允许的范围之内，因此，图中虚框部分可近似地视为一个等效的无损确定信道，简称为无噪信道，这一点是我们讨论信源编码的前提。,1、基本概念,4,信源编码分类：无失真编码、有失真编码。无失真编码：只对信源的冗余度进行压缩，不会改变信源的熵，又称冗余度
2、压缩编码，它能保证码元序列经译码后能无失真地恢复成信源符号序列。有失真编码：又称熵压缩编码，将在第6章讨论。,无失真信源编码的作用：,（1）符号变换：使信源的输出符号与信道的输入符号相匹配；,（2）冗余度压缩：使编码之后的新信源概率分布均匀化，信息含量效率等于或接近于100%。,5,2、编码器模型,码长li：码字wi 所含码元的个数。单位：码元/符号，r进制单位/符号。定长码(FLC，Fixed Length code)：码中所有码字均有相同的码长l；否则称为变长码(VLC，Variable Length code)。平均码长：,码W码字集W,码字wi,码元集 X,码元xi,信源编码f：一一对
3、应的变换。,码元/符号,定长码：,码元/符号,平均码长是衡量码的性能的重要参数，“平均码长小”说明平均一个码元所携带的信息量大，信息的冗余就小。,6,例：编码,设DMS的概率空间为,对其单个符号进行二进制编码。,码元/符号,码元/符号,编码策略：经常出现（概率大）的符号采用较短的码字，不经常出现（概率小）的符号采用较长的码字。,编码策略：采用等长的码字。,7,3、编码器的输出,f 是一一对应的映射,bit/码字或bit/符号,bit/码元,新信源X：,编码后的信息率R：平均一个码元携带的信息量。,bit/码元,平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的信息。,8,4、
4、编码效率,为了衡量编码效果，定义编码效率：编码后的实际信息率与编码后的最大信息率之比。,注：编码效率实际上也是新信源X的信息含量效率或熵的相对率。,新信源的冗余度也是码的冗余度：,9,3.2 码的唯一可译性,f为一一对应的变换只是无失真编码的必要条件，并不充分;要保证将码元序列无失真地恢复成信源符号序列，还要求编出的码自身具有独特的结构。有实用价值的码应该具有唯一可译性，即能从码字序列（也是码元序列）唯一地恢复成信源符号序列。,10,1、唯一可译码（UDC，Uniquely Decodable Code）,唯一可译码（UDC）：该码的码字组成的任意有限长码字序列都能恢复成唯一的信源序列。否则称
5、为非唯一可译码。码是唯一可译码的充分必要条件是：由码中的码字组成的任意有限长的码字序列（也是码元序列），都能唯一划分成一个个的码字，且任一码字只与唯一一个信源符号对应。奇异码：含相同码字的码。否则称为非奇异码。,11,W1、W2：定长码。,W3、W4、W5：变长码。,W2：奇异码。奇异码肯定不是UDC。,W1：定长非奇异码。不是UDC。,非续长码：码中任一码字都不是另一码字的续长（加长）。否则为续长码。,W3：变长码、非奇异码、续长码。,W3：不是UDC。,W5：变长码、非奇异码、续长码。是UDC。,W4：变长码、非奇异码、非续长码。,非续长码肯定是UDC，并且是及时可译的，又称及时码或立即码
6、。,12,13,2、码树,码树从树根开始向上长出树枝，树枝代表码元，树枝与树枝的交点叫做节点。r进制码树：码元个数为r，各节点（含树根）向上长出的树枝数不大于r。l阶节点：经过l 根树枝才能到达的节点。终端节点或端点：向上不长出树枝的节点。码字：与码树上的节点对应，组成该码字的码元就是从树根开始到该节点所经过的树枝（或码元）。非续长码：所有码字均处于终端节点，即端点上。整树：r进制码树各节点（包括树根）向上长出的树枝数均等于r。,W1=00，01，10，11,W4=0，10，110，111,W5=0，01，011，111,14,3、Kraft不等式,不满足Kraft不等式的码肯定不是非续长码；
7、满足Kraft不等式的码也不一定是非续长码；根据满足Kraft不等式的码长集合可构造出一个非续长码；上述定理对唯一可译码仍然成立。,非续长码存在性定理：对于任一 进制非续长码，各码字的码长为 必须满足Kraft不等式：反过来，若上式成立，就一定能构造一个 进制非续长码。,15,3.3 定长编码定理和定长编码方法,1、对信源输出的符号序列进行编码,对信源U的单个符号进行编码,对信源U的N长符号串进行编码,对扩展信源UN的单个符号进行编码,16,2、定长编码定理,r进制定长编码，码长为lN，可用的码字数目：,唯一可译,17,定长无失真编码定理：用r元符号表对离散无记忆信源U的N长符号序列进行定长编
8、码，N长符号序列对应的码长为lN，若对于任意小的正数，有不等式 就几乎能做到无失真编码，且随着序列长度N的增大，译码差错率趋于0。反过来，若 就不可能做到无失真编码，且随着N的增大，译码差错率趋于1。,18,3、定长编码方法（例）,对U的单个符号进行2进制编码。码元集：X=0，1,取l=3,bit/符号,码元/符号,提高编码效率的方法：对符号串进行编码，同时引入一定的失真。,19,3.4 变长编码定理(香农第一定理),无失真变长编码定理：用 元符号表对离散无记忆信源 的 长符号串进行变长编码，记 长符号串对应的平均码长为，那么，要做到无失真编码，平均码长 必须满足 另一方面，一定存在唯一可译码
9、，其平均码长 满足,信源有效编码的基本界限：,N趋于无穷时平均码长和编码效率的极限：,随着信源序列长度的增大，单个信源符号所需的码元数愈接近信源的熵，编码效率提高，当然编码过程也愈复杂。,20,3.5 变长编码方法,变长编码采用非续长码；力求平均码长最小，此时编码效率最高，信源的冗余得到最大程度的压缩；对给定的信源，使平均码长达到最小的编码方法称为最佳编码，编出的码称为最佳码；三种变长编码方法：霍夫曼编码、费诺编码以及香农编码；霍夫曼编码是真正意义下的最佳编码。,21,1、霍夫曼编码,二进制霍夫曼编码过程如下：（1）将信源符号按概率大小排序；（2）对概率最小的两个符号求其概率之和，同时给两符号
10、分别赋予码元“0”和“1”；（3）将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和”为1为止；（4）按上述步骤实际上构造了一个码树，从树根到端点经过的树技即为码字。,22,2进制霍夫曼编码。码元集：X=0，1,非续长码，平均码长最小，码字不唯一。,23,霍夫曼编码的基本特点,编出的码是非续长码：霍夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树。平均码长最小：霍夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码。码字不唯一：每次对概率最小的两个符号求概
11、率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元时是任意的，码字不唯一。,24,定长编码与变长编码冗余压缩效果比较,定长编码,变长编码,码元/符号,码元/符号,bit/符号,bit/符号,bit/符号,25,2进制霍夫曼编码。码元集：X=0，1,bit/符号,26,2进制霍夫曼编码。码元集：X=0，1,bit/符号,27,r进制霍夫曼编码,每次求缩减信源时，求r个最小概率之和，即将个概率最小的r符号缩减为一个新符号，直到概率之和为1终止。新问题：缩减到最后时剩下不到r个符号了。为保证平均码长最小，希望缩减到最后刚好还剩下r个符号。为达到此目的，可给信源添加几个无用的符号（概率为0的
12、符号），使得信源符号数q满足:q=(r-1)+r,信源缩减的次数,28,3进制霍夫曼编码。码元集：X=0，1，2,bit/符号,29,符号串的霍夫曼编码,例：对如下DMS进行2进制霍夫曼编码，分别对单个符号和二元符号串进行编码。,bit/符号,码元/符号,对单个符号进行编码,30,码元/符号,对二元符号串进行编码,31,2、费诺（Fano）编码,费诺（Fano）编码也是构造一个码树，因此，编出的码是非续长码，但不一定是最佳码。费诺编码步骤(以二进制编码为例)：（1）将信源符号按概率从大到小的排序；（2）将信源符号分成2组，使2组信源符号的概率之和近似相等，并给2组信源符号分别赋码元“0”和“1”；（3）接下来再把各小组的信源符号细分为2组并赋码元，方法与第一次分组相同；（4）如此一直进行下去，直到每一小组只含一个信源符号为止；（5）由此即可构造一个码树，所有终端节点上的码字组成费诺码。,32,2进制费诺编码。码元集：X=0，1,码元/符号,bit/符号,
