武汉理工信息理论与编码chapter4

1第4章离散无记忆信源无失真编码2主要内容1、信源编码概论2、码的唯一可译性3、定长编码4、变长编码5、变长编码方法34.1信源编码概论信道噪声YX信源编码信宿信源等效无噪信道信源译码信道编码信道译码YˆWWˆU传输之前的两次变换：信源编码、信道编码。传输之后的两次反变换：信道译码、信源译码。采取适当信道编码和译码措施后，可使信道传送的差错率降到允许的范围之内，因此，图中虚框部分可近似地视为一个等效的无损确定信道，简称为无噪信道，这一点是我们讨论信源编码的前提。信源编码的作用是压缩冗余度，提高传输效率。1、基本概念4信源编码分类：无失真编码、有失真编码。无失真编码：只对信源的冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码，它能保证码元序列经译码后能无失真地恢复成信源符号序列。有失真编码：又称熵压缩编码，将在第6章讨论。无失真信源编码的作用：（1）符号变换：使信源的输出符号与信道的输入符号相匹配；（2）冗余度压缩：使编码之后的新信源概率分布均匀化，信息含量效率等于或接近于100%。无损确定信道（等效）U信源编码信源W信宿信源译码WˆUf1f52、码长码长li：码字wi所含码元的个数。单位：码元/符号，r进制单位/符号。定长码(FLC)：中所有码字均有相同的码长l；否则称为变长码(VLC)。码或码字集W码字wi码元集X码元xi编码器f12{,,,}quuu12{,,,}rxxxWU12{,,,}q：一一对应的变换:,1,2,,iifuwiq符号ui信道能够传输611()()qqiiiiiilPwlPul码元/符号定长码：1()qiilPull码元/符号平均码长：平均码长是衡量码的性能的重要参数，“平均码长小”说明平均一个码元所携带的信息量大，信息的冗余就小。7例：编码设DMS的概率空间为123412141818UUuuuuP对其单个符号进行二进制编码。定长——21112222223332444()0,1()10,2:()110,3()111,3fuwlfuwlffuwlfuwl编码器f1234{,,,}uuuu{0,1}WU1224{,,,}()00,2()01,2:()10,2()11,2fuwlfuwlffuwlfuwl411111()222224882iiilPul码元/符号411111()123324881.75iiilPul码元/符号编码策略：出现概率大的符号采用较短的码字，出现概率小的符号采用较长的码字编码策略：采用等长的码字变长——83、编码器的输出编码器f12{,,,}quuu12{,,,}rxxxWU12{,,,}q{,,,}rxxxf是一一对应的映射()()1,2,,iiPwPuiq()()HWHUbit/码字或bit/符号()()()HWHUHXllbit/码元新信源X：编码后的信息率R(平均一个码元携带的信息量)：平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的信息。()()()HWHUHXllbit/码元R=94、编码效率为了衡量编码效果，定义编码效率：编码后的实际信息率与编码后最大信息率之比。maxmax()()()()loglogcRHXHUlHURHXrlr注：编码效率实际上也是新信源X的信息含量效率或熵的相对率。编码器f12{,,,}quuu12{,,,}rxxxWU12{,,,}q{,,,}rxxx新信源的冗余度也是码的冗余度：1cc104.2码的唯一可译性f为一一对应的变换只是无失真编码的必要条件，并不充分;要保证将码元序列无失真地恢复成信源符号序列，还要求编出的码自身具有独特的结构。—变长码有实用价值的码应该具有唯一可译性，即能从码字序列（也是码元序列）唯一地恢复成信源符号序列。无损确定信道（等效）U信源编码信源W信宿信源译码WˆUf1f111、唯一可译码(UDC，UniquelyDecodableCode）奇异码：不同符号有相同的码字。否则称为非奇异码。唯一可译码(UDC)：该码的码字组成的任意有限长码字序列都能恢复成唯一的信源序列。否则称为非唯一可译码。码是唯一可译码的充分必要条件是：由码中的码字组成的任意有限长的码字序列（码元序列），都能唯一划分成一个个的码字，且任一码字只与唯一一个信源符号对应。125种不同的码W1、W2：定长码。W3、W4、W5：变长码。W2:奇异码,奇异码肯定不是UDC。W1:定长非奇异码。是UDC。非续长码：码中任一码字都不是另一码字的续长（加长）。否则为续长码。非续长码是UDC。W3：变长码、非奇异码、续长码。12434321121211,00,10,01100100110,01,00,11,00,1,00,1uuuuuuuuuuuuuW3：不是UDC。W5：变长码、非奇异码、续长码。不是UDC。W4：变长码、非奇异码、非续长码。UP(ui)W1W2W3W4W5u11/20000100u21/40100001001u31/8101001110011u41/811111011111113唯一可译码定长非奇异码变长非续长码非奇异码非续长码肯定是UDC，并且是及时可译的，又称及时码或立即码。非续长码中任一码字既不是另一码字的续长，也不是另一码字的前缀。142、码树码树从树根开始向上长出树枝，树枝与树枝的交点叫做节点，树枝代表码元，码字在节点上。终端节点或端点：向上不长出树枝的节点。l阶节点：经过l根树枝才能到达的节点。00114w3w2w1w010001114w3w2w1w一阶节点01114111w10w113011w201w二阶节点三阶节点W1={00，01，10，11}W4={0，10，110，111}W5={0，01，011，111}15码字：与码树上的节点对应，组成该码字的码元就是从树根开始到该节点所经过的树枝（或码元）。非续长码：所有码字均处于终端节点，即端点上。整树：r进制码树各节点（包括树根）向上长出的树枝数均等于r。r进制码树：码元个数为r，各节点（含树根）向上长出的树枝数不大于r。163、Kraft不等式不满足Kraft不等式的码肯定不是非续长码；满足Kraft不等式的码也不一定是非续长码；根据满足Kraft不等式的码长集合可构造出一个非续长码；上述定理对唯一可译码仍然成立。非续长码存在性定理：对于任一r进制非续长码，各码字的码长为li(i=1,2,…q)，必须满足Kraft不等式：反过来，若上式成立，就一定能构造一个r进制非续长码。11iqlir174.3定长编码定理和定长编码方法1、对信源输出的符号序列进行编码DMS编码器f12{,,,}quuu12{,,,}rxxxWU12{,,,}q{,,,}rxxx对信源U的单个符号进行编码对信源U的N长符号串进行编码对扩展信源UN进行编码DMS编码器f12{,,,}Nq12{,,,}rxxxWNU12{,,,}Nq{,,,}rxxx182、定长编码定理DMS编码器f12{,,,}Nq12{,,,}rxxxWNU12{,,,}Nq{,,,}rxxxr进制定长编码，码长为lN，可用的码字数目：NlrNlNrq一一对应loglogNlqNrmaxmax()()logrHUHUr信源U的最大r进制熵一起编码的符号串长度19定长无失真编码定理：用r元符号表对离散无记忆信源U的N长符号序列进行定长编码，N长符号序列对应的码长为lN，若对于任意小的正数ε，有不等式就几乎能做到无失真编码，且随着序列长度N的增大，译码差错率趋于0。反过来，若就不可能做到无失真编码，且随着N的增大，译码差错率趋于1。()()logNrlHUHUNr()2()2logNrlHUHUNr203、定长编码方法（例）123456723456611111112222222UuuuuuuuUP对U的单个符号进行2进制编码。码元集：X={0，1}取l=31234567::001010011100101110111UuuuuuuuW7163()()log()32iiiHUPuPu6332()65.625%log3log2cHUlr3llbit/符号码元/符号提高编码效率的方法：对符号串进行编码，同时引入一定的失真。214、引入失真，提高编码效率限定定长编码码长的最小值，因此最佳的定长编码效率为：()()()()loglogcNHUHUHUlHUlrrN可以证明，差错率满足关系：22()eUPN2222()()()()log()()iiiUEIuHUPuPuHU对于任一个正整数δ，只要22()UN就可以使eP(4-3-9)(4-3-12)由上两式削去ε有2222()()(1)ccUNHU信源自信息量的方差误码率()logNlHUNr符号序列长度(1)()ccHU22例对前例所给的信源符号序列进行二进制编码，要求编码效率ηc=90%，允许的差错率为δ10-6解：前例已经求出信源的熵H(U)=63/32，自信息量的方差为2221()()log()()5.0625qiiiUPuPuHU所以，222822226()5.06250.910()(1)63/32(10.9)10ccUNHU由此可见，要达到要求的编码效率，必须取很长的信源序列(N108)，这在实际中难以实现。定长编码在引入失真的前提下，还需要很长的信源序列进行编码，才能达到较高的编码效率。即要不失真，同时又要很高的编码效率，只能采用变长编码无失真变长编码定理：用r元符号表对离散无记忆信源U的N长符号串进行变长编码，记N长符号串对应的平均码长为，要做到无失真编码，平均码长必须满足另一方面，一定存在唯一可译码，其平均码长满足234.4变长编码定理(香农第一定理)()NrlHUN1()NrlHUNNNl信源有效编码的基本界限：N趋于无穷时平均码长和编码效率的极限：limlim()NrNNllHUN()()limlimlim100%logrcNNNHUHUlrl随着信源序列长度的增大，单个信源符号所需的码元数愈接近信源的熵，编码效率提高，编码过程也愈复杂。244.5变长编码方法变长编码采用非续长码；力求平均码长最小，此时编码效率最高，信源的冗余得到最大程度的压缩；对给定的信源，使平均码长达到最小的编码方法称为最佳编码，编出的码称为最佳码；三种变长编码方法：霍夫曼编码、费诺编码以及香农编码；霍夫曼编码是真正意义下的最佳编码。251、霍夫曼编码二进制霍夫曼编码过程如下：（1）将信源符号按概率大小排序；（2）对概率最小的两个符号求其概率之和，同时给两符号分别赋予码元“0”和“1”；（3）将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，再重复上述步骤，直到“概率之和”为1为止；（4）按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。26符号ui概率P(ui)码字Wi码长liu11/2u21/22u31/23u41/24u51/25u61/26u71/2663326332()100%loglog2cHUlr10110001200130000016500001460000002345661111111631234566222222232l12345672345661111