Ch2例题与证明五.doc

u 定长编码定理 由L个符号组成的，每个符号的熵为H(X)的平稳无记忆符号序列 ，可用K个符号（每个符号有m种可能取值）进行定长编码，对任意，只要则当L足够大时，必可使译码差错小于。反之当时，译码差错一定是有限值，当L足够大时，译码必定出错。不等式（1）中，m代表码序列中每个符号的可能取值数，假定m个取值是等概率的,则单个符号的信息量为。对于定长编码，每个码字的长度都是K，故码字的总数为。若信源是平稳无记忆的，长度为K的码序列的总信息量为：代表的是消息（长为L的信源符号序列）的信息量。平均每个符号的信息量即平均符号熵为。显然传送一个信源符号所需的信息率就是。定长编码定理中的正定理说明，信息率略大于单符号熵时，可做到几乎无失真译码，条件是L必须足够大。可以证明，只要 (3)译码差错率一定小于任意正数。逆定理说明，信息率比信源熵略小一点（小一个）时，译码差错未必超过限定值，但若比H(X)小，则译码失真一定大于，时，必定失真。 信源熵H(X)其实就是一个界限，或者说是一个临界值，当编码器输出的信息率超过这个临界值时，就能无失真译码，否则就不行。信源编码定理从理论上阐明了编码效率接近于1，即的理想编码器的存在性，代价是在实际编码时取无限长的信源符号（）进行统一编码。具体来说，就是给定和，用式（3）规定的L计算所有可能信源消息的概率，按由大到小的次序排列，选用概率较大的消息进行编码，于是有编码的消息构成一个集合，直到该集合的概率，意味着译码差错率必定小于，即完成了编码过程。只要足够小，就可实现几乎无失真译码，所需的信息率也不会超过；若足够小，编码效率就接近于1。理想编码器实际上是很难实现的。例2.4.1设某单符号信源模型为计算得 若要求编码效率为90%,即 则 =0.28 设译码差错率为，由式（3）可得 由此可见，在差错率和效率的要求都不苛刻的情况下，就必须有1600多万个信源符号一起编码，技术实现非常困难。不仅如此，它的编码效率也不高。对8种可能的取值编定长码，要无差错地译码，每种取值需用3个比特，其编码效率为了解决这一问题，就出现了不等长编码，也称变长编码。不等长编码允许把等长的消息变换成不等长的码序列。通常把经常出现的消息编成短码，不常出现的消息编成长码。这样可使平均码长最短，从而提高通信效率，代价是增加了编译码设备的复杂度。例如在不等长码字组成的序列中要正确识别每个长度不同的码字的起点就比等长码复杂得多。另外，接收到一个不等长码序列后，有时不能马上断定码字是否真正结束，因而不能立即译出该码，要等到后面的符号收到后才能正确译出。这就是所谓的译码同步和译码延时问题。例2.4.2 显然码A与信源消息不是一一对应，因而它不是唯一可译码。码B虽然能完成消息的唯一编码，但它仍然不是唯一可译的。因为若收到00，可译为，也可译为；同样11也不是唯一可译的。码C虽是唯一可译的，但它要等到下一个“0”收到后才能确定码字的结束，于是有译码延时。只有码D既是唯一可译的，又没有延时。 如果一个码的任何一个码字都不是其它码字的前缀，则称该码为前缀码、异前置码、异字头码、逗点码，也称即时码。 码D是即时码，可用树图法来构造。对于m元或m进制树图，在最顶部画一个起始点，成为树根。从根部引出m条线段，每条线段都称为树枝。通过树枝到达另一个节点，从这个节点往下，有可以分出m个树枝。如此下去，就可以构造出一个树形图，称为m元或m进制码树图。自根部起，通过一条树枝到达的接点为一级节点，一级节点最多有m个；通过两条树枝到达的节点称为二级节点，二级节点最多有个；如此则通过n条树枝到达的节点称为n级节点，n级节点最多有个。下面不再有树枝的节点称为终端节点或终节点。除了树根和终结点以外，其余的节点都称为中间节点。串联的树枝称为联枝。从树根开始到每一个终结点的联枝代表一个码字。3元码树图如下：在码树图中，当每一个码字的串联枝数都相同时，就是定长码。此时的码树称为满树，如上图(a)。码长为N的满树的终节点个数为，即可表示个码字。当有些树枝未用时，称为非满树，如上图(b)所示。非满树构造的就是变长码。如果每一个码字都被安排在终节点上，这种码就是异前置码。M元长度为的异前置码存在的充要条件是 （4）式（4）称为克拉夫特不等式。现在来证明这个不等式。设异前置码第i个码字的长度为，我们构造了一个码树图，在第级，总共有个节点。第i个码字占据了第级的。根据异前置码的定义，其后的树枝不能再用。对于N级满而言，其后不能用的枝数为，那么总共不用的枝数为。N级满树第N级上的总枝数已知为，所以必有 （5）两边除以，就得这就是异前置码存在的必要条件。反之，如果式(4)成立，则式(5)必成立，总可以把第N级上的树枝分成n组，各组中从第N级开始删除个枝。相对于N级满树而言，等于删除了所有可能的级节点的。在该组中以第级节点作为终节点，就构造好了第i个码字。对所有的n个码字均如法炮制，则总共删除了所有个节点中的。由于于是构造了一个异前置码。这是异前置码存在的充分条件。根据克拉夫特不等式，证明变长编码定理。变长编码定理 若一离散无记忆信源的符号熵为，对信源符号进行m元变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式 (6) 其平均信息率满足不等式 （7）式中， 为任意正数。 证明 设信源符号，概率为，若对用一个长度为的码字，使 （8）只要我们规定为整数时，式（8）取等号，非整数时，取比它大一些的最接近的整数，则满足上式的整数必存在。将式（8）分别乘以再对i求和。得对取数学期望就是平均值，故由式(8) 码字长度满足克拉夫特不等式，因而是异前置码。对于平稳无记忆信源来说，当信源输出的是长度为L的消息序列时，易证式