信息论与编码第5章.doc

第五章 信源编码第五章 信源编码（第十讲）（2课时）主要内容：（1）编码的定义（2）无失真信源编码重点：定长编码定理、变长编码定理、最佳变长编码难点：定长编码定理、哈夫曼编码方法作业：56；说明：本堂课推导内容较多，枯燥平淡，不易激发学生兴趣，要注意多讨论用途另外，注意，解题方法多加一些内容丰富知识和理解通信的实质是信息的传输而高速度、高质量地传送信息是信息传输的基本问题将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大为了解决这两个问题，就要引入信源编码和信道编码一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱二者是有矛盾的然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息这些结论对各种通信系统的设计和估价具有重大的理论指导意义§3.1 编码的定义编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。

讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单图3.1是一个信源编码器，它的输入是信源符号，同时存在另一符号，一般来说，元素xj是适合信道传输的，称为码符号（或者码元）编码器的功能就是将信源符号集中的符号si（或者长为N的信源符号序列）变换成由xj(j=1,2,3,…r)组成的长度为li的一一对应的序列输出的码符号序列称为码字，长度li称为码字长度或简称码长可见，编码就是从信源符号到码符号的一种映射若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的码符号的分类：下图是一个码分类图下面，我们给出这些码的定义1. 二元码若码符号集为X={0;1}，所有码字都是一些二元序列，则称为二元码二元码是数字通信和计算机系统中最常用的一种码2. 等长码：若一组码中所有码字的码长都相同，即li=l(i=1,2,…q)，则称为等长码3. 变长码：若一组码组中所有码字的码长各不相同，则称为变长码4. 非奇异码：若一组码中所有码字都不相同，则称为非奇异码5. 奇异码：若一组码中有相同的码字，则称为奇异码6. 唯一可译码：若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。

7. 非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码 如果收到一个完整的码字以后，就可以立即译码，则叫做即时码即时码要求任何一个码字都不是其他码字的前缀部分，也叫做异前缀码n 码树：即时码的一种简单构造方法是树图法对给定码字的全体集合C={W1,W2,…Wq}来说，可以用码树来描述它所谓树，就是既有根、枝，又有节点，如图5.2（80业）所示，图中，最上端A为根节点，A、B、C、D、E皆为节点，E为终端节点A、B、C、D为中间节点，中间节点不安排码字，而只在终端节点安排码字，每个终端节点所对应的码字就是从根节点出发到终端节点走过的路径上所对应的符号组成，如图5.2中的终端节点E，走过的路径为ABCDE，所对应的码符号分别为0、0、0、1，则E对应的码字为0001可以看出，按树图法构成的码一定满足即时码的定义（一一对应，非前缀码）从码树上可以得知，当第i阶的节点作为终端节点，且分配码字，则码字的码长为i任一即时码都可以用树图法来表示当码字长度给定后，用树图法安排的即时码不是唯一的如图3.2中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。

对一个给定的码，画出其对应的树，如果有中间节点安排了码字，则该码一定不是即时码每个节点上都有r个分支的树称为满树，否则为非满树即时码的码树图还可以用来译码当收到一串码符号序列后，首先从根节点出发，根据接收到的第一个码符号来选择应走的第一条路径，再根据收到的第二个符号来选择应走的第二条路径，直到走到终端节点为止，就可以根据终端节点，立即判断出所接收的码字然后从树根继续下一个码字的判断这样，就可以将接收到的一串码符号序列译成对应的信源符号序列n 克拉夫特（Kraft）不等式定理3.1 对于码符号为X={x1,x2,…xr}的任意唯一可译码，其码字为W1,W2,…Wq，所对应的码长为l1,l2…lq，则必定满足克拉夫特不等式反之，若码长满足上面的不等式，则一定存在具有这样码长的即时码注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据（可以排除，不能肯定）如{0，10，010，111}满足克拉夫特不等式，但却不是唯一可译码例题：设二进制码树中X={x1,x2,x3,x4}，对应的l1=1,l2=2,l3=2,l4=3，由上述定理，可得因此不存在满足这种码长的唯一可译码可以用树码进行检查。

n 唯一可译码的判断法（变长）：将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码集合F的构成方法：首先，观察码C中最短的码字是否是其它码字的前缀，若是，将其所有可能的尾随后缀排列出而这些尾随后缀又有可能是某些码字的前缀，再将这些尾随后缀产生的新的尾随后缀列出，然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为止这样，首先获得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码字、…等等所有码字可能产生的尾随后缀全部列出由此得到由码C的所有可能的尾随后缀的集合F例题：设码C={0,10,1100,1110,1011,1101}，根据上述测试方法，判断是否是唯一可译码解：1. 先看最短的码字：“0”，它不是其他码字前缀，所以没有尾随后缀 2. 再观察码字“10”，它是码字“1011”的前缀，因此有尾随后缀所以，集合F={11，00，10，01}，其中“10”为码字，故码C不是唯一可译码§3.2 定长编码定理前面已经说过，所谓信源编码，就是将信源符号序列变换成另一个序列（码字）。

设信源输出符号序列长度为L，码字的长度为KL，编码的目的，就是要是信源的信息率最小，也就是说，要用最少的符号来代表信源在定长编码中，对每一个信源序列，KL都是定值，设等于K，我们的目的是寻找最小K值要实现无失真的信源编码，要求信源符号Xi(i=1,2,…q)与码字是一一对应的，并求由码字组成的符号序列的逆变换也是唯一的（唯一可译码）定长编码定理：由L个符号组成的、每个符号熵为HL(X)的无记忆平稳信源符号序列X1X2X3…XL用KL个符号Y1Y2…YKL（每个符号有m种可能值）进行定长变码对任意，只要则当L足够大时，必可使译码差错小于；反之，当时，译码差错一定是有限值，当L足够大时，译码几乎必定出错式中，左边是输出码字每符号所能载荷的最大信息量所以等长编码定理告诉我们，只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真的编码条件时所取得符号数L足够大设差错概率为，信源序列的自方差为则有：当和均为定值时，只要L足够大，可以小于任一整数，即此时要求：只要足够小，就可以几乎无差错地译码，当然代价是L变得更大令为码字最大平均符号信息量定义编码效率为：最佳编码效率为无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，但要在实际中实现，则要求信源符号序列的L非常大进行统一编码才行，这往往是不现实的。

例如：例题：设离散无记忆信源概率空间为信源熵为自信息方差为对信源符号采用定长二元编码，要求编码效率，无记忆信源有，因此可以得到如果要求译码错误概率，则由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现如果用3比特来对上述信源的8个符号进行定长二元编码，L=1，此时可实现译码无差错，但编码效率只有2.55/3=85%因此，一般说来，当L有限时，高传输效率的定长码往往要引入一定的失真和译码错误解决的办法是可以采用变长编码§3.3 最佳编码最佳码：对于某一信源和某一码符号集来说，若有一唯一可译码，其平均码长小于所有其他唯一可译码的平均长度为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短能获得最佳码的编码方法：香农（Shannon）费诺（Fano）哈夫曼（Huffman）1、香农编码方法香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理香农第一定理指出，选择每个码字的长度Ki满足下式： Ki= []——取整即： －log2pi ≤Ki≤1－log2pi 就可以得到这种码。

这种编码方法称为香农编码例：设无记忆信源的概率空间为：计算各符号的码字长度：K1= log2=1K2= log4=2K3= K4 =log8=3用图示码树，可得各自的码字： u1:（0），u2:（10），u3:（110），u4:（111）信息熵H(U):信源符号的平均码长:编码效率对于这种信源，香农编码是最佳编码码树达到满树l 香农编码法多余度稍大，实用性不大，但有重要的理论意义编码方法如下：⑴ 将信源消息符号按其出现的概率大小依次排列 p(u1)≥p(u2)≥…≥ p(un)⑵ 确定码长Ki (整数) ： Ki= []——取整⑶ 为了编成唯一可译码，计算第i个消息的累加概率 ⑷ 将累加概率Pi变换成二进制数⑸ 取pi二进制数的小数点后Ki位即为该消息符号的二进制数例： 信源符号ui符号概率p(ui) 累加概率Pi-log p(ui)码字长度Ki码字u10.401.32200u20.30.41.73201u30.20.72.323101u40.050.94.3511100u50.050.954.3511101以i = 3为例，计算各符号的码字长度：K3 = [－log0.2] = 3 累加概率P4 = 0.7 —— 0.10110… —— 101 由图，这些码字没有占满所有树叶，所以是非最佳码。

平均码长：编码效率： 为了提高编码效率，首先应达到满树；例如把u4u5换成A、B这些前面的节点，就可减小平均码长所以不应先规定码长，而是由码树来规定码字，可得更好的结果 2、费诺编码。