第5(8)章无失真信源编码定理(OK)

第5(8)章无失真信源编码定理(OK)第一页，共54页。5.1信源编码概论--基本概念噪声信道信源编码信源信宿等效无噪信道信源译码信道编码信道译码传输之前的两次变换：信源编码、信道编码。传输之后的两次反变换，变换与反变换是成对出现的。讨论无失真信源编码可以先不考虑抗干扰问题，因此，图中虚框部分可近似地视为一个等效的无噪信道，这一点是我们讨论信源编码的前提。1、基本概念第二页，共54页。信源编码分类：无失真编码、有失真编码。无失真编码：只对信源的冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码，它能保证码元序列经译码后能无失真地恢复成信源符号序列。有失真编码：又称熵压缩编码，将在第7章讨论。无失真信源编码的作用：（1）符号变换：使信源的输出符号与信道的输入符号相匹配；（2）冗余度压缩：使编码之后的新信源概率分布均匀化，信息含量效率等于或接近于100%。5.1信源编码概论--基本概念第三页，共54页。5.1信源编码概论----编码器模型码C码字集C

码字wi

码元集

X码元xi

编码器f信源信源编码

：一一对应的变换:基本概念：码长li、等长码、变长码、平均码长第四页，共54页。码长li

：码字wi所含码元的个数。单位：码元/符号，r进制单位/符号。

等长码(FLC，FixedLengthcode)：码中所有码字均有相同的码长l；否则称为变长码(VLC，VariableLengthcode)。平均码长：码元/符号

定长码：

平均码长是衡量码的性能的重要参数，“平均码长小”说明平均一个码元所携带的信息量大，信息的冗余就小。5.1信源编码概论--编码器模型码元/符号

变长码：第五页，共54页。例：编码设一信源的概率空间为对其单个符号进行二进制编码。

码元/符号

码元/符号

编码策略：经常出现（概率大）的符号采用较短的码字，不经常出现（概率小）的符号采用较长的码字。编码策略：采用等长的码字。第六页，共54页。3、编码器的输出f是一一对应的映射

新信源X：编码后的信道的信息传输率R

：平均每个码元携带的信息量。平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的信息。5.1信源编码概论编码器f信源第七页，共54页。4、编码效率为了衡量编码效果，定义编码效率：编码后的实际信息率与编码后的最大信息率之比。

注：编码效率实际上也是新信源X的信息含量效率或熵的相对率。新信源的冗余度也是码的冗余度：5.1信源编码概论编码器f信源第八页，共54页。5.2码的唯一可译性f为一一对应的变换只是无失真编码的必要条件，并不充分;要保证将码元序列无失真地恢复成信源符号序列，还要求编出的码自身具有独特的结构。有实用价值的码应该具有唯一可译性，即能从码字序列（也是码元序列）唯一地恢复成信源符号序列。噪声信道信源编码信源信宿等效无噪信道信源译码信道编码信道译码f-1f第九页，共54页。1、唯一可译码（UDC，UniquelyDecodableCode）唯一可译码（UDC）：该码的码字组成的任意有限长码字序列都能恢复成唯一的信源序列。否则称为非唯一可译码。码是唯一可译码的充分必要条件是：由码中的码字组成的任意有限长的码字序列（也是码元序列），都能唯一划分成一个个的码字，且任一码字只与唯一一个信源符号对应。奇异码：含相同码字的码称奇异码。否则称为非奇异码。

5.2码的唯一可译性第十页，共54页。即时码：在惟一可译变长码中，有一类码，它在译码时无需参考后续的码符号就能立即做出判断，译成对应的信源符号，则这类码称为即时码。

前缀条件码：码中任一完整码字都不是另一码字的前缀。该码也称异前置码或非延长码。此码为即时码。

5种不同的码例题：5.2码的唯一可译性第十一页，共54页。W3：变长非奇异码，但不是UDC

。W5：变长码、非奇异码、延长码。是UDC。W4：变长码、非奇异码、是UDC

。5种不同的码例题：W1：等长非奇异码。是UDC。W2：等长奇异码，不是UDC。等长非奇异码一定是惟一可译码。5.2码的唯一可译性第十二页，共54页。唯一可译码等长非奇异码即时码非奇异码惟一可译码的判断方法：P182：将码中所有码字可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码为惟一可译码。5.2码的唯一可译性第十三页，共54页。2、码树

一阶节点二阶节点三阶节点W1={00，01，10，11}W4={0，10，110，111}W5={0，01，011，111}5.2码的唯一可译性第十四页，共54页。码树从树根开始向上长出树枝，树枝代表码元，树枝与树枝的交点叫做节点。r进制码树：码元个数为r，各节点（含树根）向上长出的树枝数不大于r。l阶节点：经过l根树枝才能到达的节点。终端节点或端点：向上不长出树枝的节点。码字：与码树上的节点对应，组成该码字的码元就是从树根开始到该节点所经过的树枝（或码元）。非延长码：所有码字均处于终端节点，即端点上。

整树：r进制码树各节点（包括树根）向上长出的树枝数均等于r。5.2码的唯一可译性第十五页，共54页。不满足Kraft不等式的码肯定不是非延长码；满足Kraft不等式的码也不一定是非延长码；根据满足Kraft不等式的码长集合可构造出一个非延长码；上述定理对唯一可译码仍然成立。

即时码存在性定理：对于任一进制即时码，各码字的码长为则必定满足Kraft不等式：

反过来，若上式成立，就一定能构造一个进制即时码。5.2码的唯一可译性（--Kraft不等式）第十六页，共54页。5.3等长编码定理和等长编码方法1、对信源输出的符号序列进行编码

信源编码器f信源编码器f对信源U的单个符号进行编码

对信源U的N长符号串进行编码

对扩展信源UN的单个符号进行编码

第十七页，共54页。2、等长编码定理

信源编码器fr进制定长编码，码长为lN，可用的码字数目：唯一可译5.3等长编码定理和等长编码方法第十八页，共54页。

等长无失真编码定理：用r元符号对离散无记忆信源U的N长符号序列进行定长编码，N长符号序列对应的码长为lN，若对于任意小的正数，有不等式

就几乎能做到无失真编码，且随着序列长度N的增大，译码差错率趋于0。反过来，若

就不可能做到无失真编码，且随着N的增大，译码差错率趋于1。5.3等长编码定理和等长编码方法第十九页，共54页。3、等长编码方法（例）对U的单个符号进行2进制编码。码元集：X={0，1}

取l=3bit/符号码元/符号提高编码效率的方法：对符号串进行编码，同时引入一定的失真。第二十页，共54页。5.4变长编码定理(香农第一定理

)定理5.8：无失真变长信源编码定理：离散无记忆信源的N次扩展信源，其熵为，并有码符号对信源进行编码，总可以找到一种编码方法，构成惟一可译码，使信源S中的每个信源符号所需的平均码长满足：第二十一页，共54页。5.5变长编码方法变长编码采用非延长码；力求平均码长最小，此时编码效率最高，信源的冗余得到最大程度的压缩；对给定的信源，使平均码长达到最小的编码方法称为最佳编码，编出的码称为最佳码；三种变长编码方法：霍夫曼编码、费诺编码以及香农编码；霍夫曼编码是真正意义下的最佳编码。第二十二页，共54页。1、霍夫曼编码

二进制霍夫曼编码过程如下：（1）将信源符号按概率大小排序；（2）对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元“0”和“1”；（3）将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和”为1为止；（4）按上述步骤实际上构造了一个码树，从树根到端点经过的树技即为码字。5.5变长编码方法第二十三页，共54页。符号概率码字Wi码长li11012001300014000015000001600000062进制霍夫曼编码。码元集：X={0，1}

非延长码，平均码长最小，码字不唯一。第二十四页，共54页。霍夫曼编码的基本特点编出的码是非延长码：霍夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树。平均码长最小：霍夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码。码字不唯一：每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元时是任意的，码字不唯一。第二十五页，共54页。等长编码与变长编码冗余压缩效果比较等长编码变长编码码元/符号码元/符号bit/符号bit/符号bit/符号第二十六页，共54页。符号概率码字Wi码长li0.35110.300120.2000130.10000140.040000150.00500000160.00500000062进制霍夫曼编码。码元集：X={0，1}

bit/符号第二十七页，共54页。r进制霍夫曼编码每次求缩减信源时，求r个最小概率之和，即将个概率最小的r符号缩减为一个新符号，直到概率之和为1终止。新问题：缩减到最后时剩下不到r个符号了。为保证平均码长最小，希望缩减到最后刚好还剩下r个符号。为达到此目的，可给信源添加几个无用的符号（概率为0的符号），使得信源符号数q满足:q=(r-1)θ+r

信源缩减的次数第二十八页，共54页。符号概率码字Wi码长li0.32210.22120.180220.160120.0800230.0400130.003进制霍夫曼编码。码元集：X={0，1，2}

bit/符号第二十九页，共54页。符号串的霍夫曼编码例：对如下DMS进行2进制霍夫曼编码，分别对单个符号和二元符号串进行编码。bit/符号符号概率码字码长u10.4511u20.35012u30.20002码元/符号对单个符号进行编码第三十页，共54页。符号概率码字码长u1u10.2025112u1u20.15750113u2u10.15750013u2u20.12250003u1u30.091013u3u10.0901014u2u30.0701004u3u20.0710014u3u30.0410004码元/符号对二元符号串进行编码第三十一页，共54页。2、费诺（Fano）编码

费诺（Fano）编码也是构造一个码树，因此，编出的码是非续长码，但不一定是最佳码。费诺编码步骤(以二进制编码为例)：（1）将信源符号按概率从大到小的排序；（2）将信源符号分成2组，使2组信源符号的概率之和近似相等，并给2组信源符号分别赋码元“0”和“1”；（3）接下来再把各小组的信源符号细分为2组并赋码元，方法与第一次分组相同；（4）如此一直进行下去，直到每一小组只含一个信源符号为止；（5）由此即可构造一个码树，所有终端节点上的码字组成费诺码。第三十二页，共54页。符号ui概率P(u1)码字Wi码长liu10.20002u20.190103u30.180113u40.17102u50.151103u60.1011104u70.01111142进制费诺编码。码元集：X={0，1}

码元/符号bit/符号第三十三页，共54页。概率大，则分解的次数少；概率小,则分解的次数多。这符合最佳编码原则。码字集合是唯一的。分解完了，码字出来了，码长也有了。因此，费诺编码方法又称为子集分解法。费诺编码方法比较适合于每次分组概率都很接近的信源，特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。费诺编码特点第三十四页，共54页。3、香农编码设离散无记忆信源二进制香农码的编码步骤如下：将信源符号按概率从大到小的顺序排列，为方便起见，令p(x1)≥p(x2)≥…≥p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率，则第三十五页，共54页。3、香农编码确定满足下列不等式的整数ki，并令ki为第i个码字的长度－log2

p(xi)≤ki<1－log2

p(xi)将pa(xj)用二进制表示，并取小数点后ki位作为符号xi的编码。第三十六页，共54页。1.某信源具有7个消息符号，其概率分别为：0.20,0.19,0.18,0.17,0.15,0.10,0.01。欲对其进行香农方法的二进制编码，求其二进制代码组及其编码效率。

解：先计算每一个码字的码长，分别为：3,3,3,3,3,4,7；再计算累加概率。例如：P4=p1+p2+p3=0.20+0.19=0.18=0.57，变换成二进制数为：0.1001···，因为b4=3，故对于概率为0.17的消息符号x4，其编码为100。依此类推，与本题有关的数据和编码结果列于下表。例题第三十七页，共54页。例题第三十八页，共54页。可以求出其平均码长和信源熵分别为3.14码元/符号和2.16比特/符号，故其信息传输速率为同样，本题也是二进制信道，信道容量C=1比特/码元时间，故其编码效率在数值上等于信息传输速率，即=83.1%。上述两个例子可见，香农编码方法对有的信源能够达到最佳编码而有的则不能，因此还不能说它是最佳编码。例题第三十九页，共54页。香农编码方法特点：由于bi总是进一取整，香农编码方法不一定是最佳的；由于第一个消息符号的累加概率总是为0，故它对应的码字总是0、00、000、0…0的式样；码字集合是唯一的，且为即时码；先有码长再有码字；对于一些信源，编码效率不高，冗余度稍大，因此其实用性受到较大限制。3、香农编码第四十页，共54页。游程：指的是字符序列中各个字符连续重复出现而形成字符串的长度，又称游程长度或游长。编码方法：首先测定“0”游程长度和“1”游程长度的概率分布，即以游程长度为元素，构造一个新的信源；对新的信源（游程序列）进行哈夫曼编码。4、二元游程编码第四十一页，共54页。其中为“0”游程长度的霍夫曼编码效率，为“1”游程长度的霍夫曼编码效率。4、二元游程编码游程长度概率：二元序列的编码效率：第四十二页，共54页。游程变换减弱了原序列符号间的相关性。游程变换将二元序列变换成了多元序列；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。多元序列也可以变换成游程序列，如m元序列可有m种游程。但是变换成游程序列时，需要增加标志位才能区分游程序列中的“长度”是m种游程中的哪一个的长度，否则，变换就不可逆。这样，增加的标志位可能会抵消压缩编码得到的好处。所以，对多元序列进行游程变换的意义不大。4、二元游程编码第四十三页，共54页。1.一个信源包含6个符号消息，它们的出现概率分别为0.3,0.2,0.15,0.15,0.1,0.1，信道基本符号为二进制码元，试用哈夫曼编码方法对该信源的6个符号进行信源编码，并求出代码组的平均长度和信息传输速率。解根据哈夫曼编码的步骤，可得其编码过程和编码结果，如下图所示。习题1第四十四页，共54页。习题1第四十五页，共54页。由编码结果，求得平均码长为=2.5码元/符号信源熵为信息传输速率为由此可得其编码效率为98.8%，接近于最佳编码。习题1第四十六页，共54页。习题22.信源符号X有8种消息，概率为(1/2,1/4,1/8,1/16,1/3