第4章_离散信源的信源编码

东南大学移动通信国家重点实验室“信息论与编码”课件1第四章离散信源的信源编码东南大学移动通信国家重点实验室“信息论与编码”课件2本章内容提要信源编码的模型信息传输速率和编码效率单义可译定理无失真信源编码定理几种典型的信源编码方法汉字编码方法及其讨论图像的信源编码误码对信源译码的影响东南大学移动通信国家重点实验室“信息论与编码”课件3信源编码的含义:将信源产生的消息变换为数字序列的过程。信源编码的主要任务:把消息信号数字化和压缩其冗余度，提高编码效率。由于信源消息之间可能具有相关性，使得其输出符号序列中存在着冗余度。信源编码就是要把信源发出的消息变换成由信道基本符号构成的代码组（亦称码字）以使其能在编码信道上传输，并且尽量减少码字的平均长度以提高通信的有效性。第4章离散信源的信源编码东南大学移动通信国家重点实验室“信息论与编码”课件4从编码结果使信源消息的信息量有无损失角度，可分为无失真信源编码和限失真信源编码两种。无失真信源编码和限失真信源编码的理论基础分别为香农第一定理和香农第三定理。本章仅讨论无失真信源编码并仅限于离散信源引出信源编码的一般模型，讨论离散信源的无失真编码，导出香农第一定理，给出最佳编码的概念，几种最佳编码的实例，介绍和分析几种文本、图像的编码方法，并对译码中可能出现的错误扩展问题提出了讨论。第4章离散信源的信源编码东南大学移动通信国家重点实验室“信息论与编码”课件5ASCII（AmericaStandardCodeII）码ASCII码是人们最为熟悉一种信源编码结果，它是由两位16进制数00~FF构成的码字集合，与一些控制字符（回车，换行等）、可打印字符（0~9，A~Z，a~z，+，–，*，/等）以及图形符号一一对应。通常称这些字符、图符为ASCII字符。4.1信源编码的模型东南大学移动通信国家重点实验室“信息论与编码”课件6编码器字符集合代码集合信道基本符号集合4.1信源编码的模型ASCII码编码器的模型图4.1ASCII码编码器的模型东南大学移动通信国家重点实验室“信息论与编码”课件7字符集合：ASCII字符代码集合：16进制数信道基本符号集合：ASCII码编码器：产生它们之间相互关系的装置4.1信源编码的模型ASCII码编码器的模型东南大学移动通信国家重点实验室“信息论与编码”课件8如果将编码器看作是一个网络，则它有2个输入和1个输出，分别是消息集合X、信道基本符号集合A和代码集合S。设消息集合共有n个元素，信道基本符号共有D种，代码组集合的元素个数为N，则X={x1，x2，…，xn}A={a1，a2，…，aD}S={s1，s2，…，sN}4.1信源编码的模型信源编码的一般模型东南大学移动通信国家重点实验室“信息论与编码”课件9信源编码器的主要任务:完成输入消息集合与输出代码集合之间的映射。（1）选择合适的信道基本符号，使映射后的代码适应信道。例如ASCII码选用了16进制数。（2）寻求一种方法，把信源发出的消息变换成相应的代码组。这种方法就是编码，变换成的代码就是字。（3）编码应使消息集合与代码组集合中的元素一一对应。上述三点也是对信源编码的基本要求。4.1信源编码的模型信源编码的一般模型东南大学移动通信国家重点实验室“信息论与编码”课件10通常称具有上述映射规则的信源编码器为正规编码器，编出来的码称为非奇异码。在有些应用中可以只关心编码器的输出而不追究其初始消息和编码过程，这时可以把信源和正规编码器合在一起而称之为等效信源或简称信源，而把编码器的输入称为初始信源。由于正规编码器一一对应的规则确保了编码过程不会造成信息量的损失，故等效信源的熵必定与初始信源的熵相等。4.1信源编码的模型信源编码的一般模型东南大学移动通信国家重点实验室“信息论与编码”课件11码字的平均长度最短和易于实现是最被人们注重的。前者追求用尽可能少的信道基本符号来表示尽可能多的信源消息，即提高编码效率，后者则需综合考虑其实现方法的性能价格比。4.1信源编码的模型衡量编码方法的优劣指标东南大学移动通信国家重点实验室“信息论与编码”课件12中文电报的基本编码方法是将每一个汉字或字符用4位十进制数来表示，每一个十进制数再用5位二进制数来表示。例如，“信息论”三个字的电码分别是(0207)，(1873)，(6158)。以“信”为例，首先将它编成4位十进制的码0207，再将它们变换成20位二进制的码:01101110010110111100，由此可见，其编码过程为汉字电码二进制码字组查“标准电报电码”二变换十~4.1信源编码的模型中文电报的编码方法东南大学移动通信国家重点实验室“信息论与编码”课件13从汉字的电报码可以看出如下问题：（1）若每个汉字都用4位十进制数来表示，则汉字电报电码最多只能有1万个（0000~9999），将汉字字符分为常用和非常用两大类，将常用汉字字符直接用4位十进制数表示；对非常用汉字字符则根据汉字的结构，用多个常用汉字字符的组合来表示，这就是“电码作字办法”。就汉字总体而言，中文电报是非等长编码，而其中的常用字是等长编码。4.1信源编码的模型中文电报的编码方法东南大学移动通信国家重点实验室“信息论与编码”课件14（2）1个常用汉字用20-bit的二进制数来表示，但20-bit的二进制数可表示的汉字字符数为220=1048576个，因此尽管汉字到电码再到二进制码的变换是一一对应的，但反过来就不是一一对应了。这样做是不是浪费了很多二进制码？这种编码是不是最好？能不能找一个判定编码优劣的判据？电报编码具体的变换关系为0→01101，1→01011，2→11001，3→10110，4→11010，5→00111，6→10101，7→11100，8→01110，9→10011。这种编码只能检测错误但不能纠正错误，称为检错码。中文电报的编码方法4.1信源编码的模型东南大学移动通信国家重点实验室“信息论与编码”课件15（1）把信源发出的消息一一对应地变换成由信道基本符号构成的代码组，以使得消息能在编码信道上传输；（2）尽量减小代码组的平均长度，提高编码效率。可以从不同的角度来定义编码效率。从利用信道传输能力的角度来看，能够充分利用之的编码，其效率较高。若信源编码后的信息传输速率达到了信道的极限传输能力，则其效率最高。也就是说，信源编码效率可以用信道参量以及信息传输速率来定义。4.1信源编码的模型信源编码的主要目的东南大学移动通信国家重点实验室“信息论与编码”课件16定义4.1对于信源编码器的输出序列，其单位时间内所包含的信息量称为信源编码器的信息传输速率，简称信息率，通常用R表示。4.2信息传输速率和编码效率4.2.1信息传输速率东南大学移动通信国家重点实验室“信息论与编码”课件171.等长码的信息传输速率对单符号离散信源，设其信源熵为H(X)，对其进行等长编码，每码字b个码元，故其信息传输速率为R=H(X)/b(4.1)对于K重扩展信源，设其信源熵为H(XK)，对其进行等长编码，每码字B个码元，故其信息传输速率为R=H(XK)/B(4.2)4.2信息传输速率和编码效率4.2.1信息传输速率东南大学移动通信国家重点实验室“信息论与编码”课件182.变长码的信息传输速率假设信源编码的结果使得代码组的长度不是等长的，则该编码为变长码，求其信息传输速率需先求其代码组的平均长度。先考虑单符号消息的情况。4.2信息传输速率和编码效率4.2.1信息传输速率东南大学移动通信国家重点实验室“信息论与编码”课件19设信源有N个单符号消息x1，x2，…，xN，变长码编码器输出的代码组长度对应为b1,b2,…,bN，其出现概率分别为P(b1),P(b2),…,P(bN)，则该变长码的平均长度为(4.3)其信息传输速率为(4.4)1()NiiibPbbbHR/)(X4.2信息传输速率和编码效率4.2.1信息传输速率东南大学移动通信国家重点实验室“信息论与编码”课件20对于符号序列，设信源有N个K重扩展的符号序列消息x1，x2，…，xN，变长码编码器输出的代码组长度对应为B1,B2,…,BN，其出现概率分别为P(B1),P(B2),…,P(BN)，则该变长码的平均长度为这时信息传输速率为1()NiiiBPBBBHRK/)(X)5.4()6.4(4.2信息传输速率和编码效率4.2.1信息传输速率东南大学移动通信国家重点实验室“信息论与编码”课件21信道的极限传输能力也称为信道容量。定义4.2消息在不失真传输的条件下，信道所允许的最大信息传输速率称为信道容量。即C=Rmax(4.7)定义4.3信源编码器输出代码组的信息传输速率与信道容量之比，称为信源编码器的编码效率。即%100CR)8.4(4.2.2编码效率4.2信息传输速率和编码效率东南大学移动通信国家重点实验室“信息论与编码”课件22当R=C时，=100%这是信源编码的最理想特性，这样的信源编码能最充分地利用信道。当RC时，100%说明这样的信源编码还没有最充分地利用信道，具有进一步改进的潜力。当RC时，100%说明信源编码输出的信息速率超过了信道的传输能力，这样必然会产生失真。4.2信息传输速率和编码效率4.2.2编码效率东南大学移动通信国家重点实验室“信息论与编码”课件23信源的最大熵对应着信道容量，故信源编码器的编码效率又可表示为或%100/)(/)(maxbHbHXX%100/)(/)(maxBHBHKKXX4.2信息传输速率和编码效率4.2.2编码效率由于信源的最大熵必然对应着信源消息的等概率分布，因此对于给定的信源，b和B都是常数。(4.9)(4.10)东南大学移动通信国家重点实验室“信息论与编码”课件24由式(4.9)和(4.10)可以清楚地看出，在给定信源的情况下，若要提高信源编码的编码效率，方法之一就是使代码组的平均长度尽可能地小。通常称具有最短的代码组平均长度或编码效率接近于1的信源编码为最佳信源编码，亦简称为最佳编码。4.2信息传输速率和编码效率4.2.2编码效率bB、东南大学移动通信国家重点实验室“信息论与编码”课件254.2信息传输速率和编码效率4.2.3最佳编码•最佳编码是无失真信源编码的理想模式。•为了达到这个目的，通常需要遵循下面两个原则：（1）对信源中出现概率大的消息（或符号），尽可能用短的代码组（码字）来表示，简称短码；反之用长码。（2）不使用间隔即可区分码字。东南大学移动通信国家重点实验室“信息论与编码”课件26对于（1），还可以用定理的形式描述。定理4.1设信源有N个消息分别为x1,x2,…,xN，出现概率分别为P(x1),P(x2),…,P(xN)，信源编码器输出的N个代码组分别为s1,s2,…,sN，对应长度分别为b1,b2,…,bN，若信源消息的概率分布满足P(x1)P(x2)…P(xN)，而信源编码器输出的代码组长度满足b1b2…bN，则该代码组的平均长度为最短。4.2信息传输速率和编码效率4.2.3最佳编码东南大学移动通信国家重点实验室“信息论与编码”课件27定理4.1的证明：用反证法。设有小于N的正整数m和n，且mn，存在着P(xm)P(xn)和bmbn，而其余所有信源符号的概率与其对应的代码组长度都符合最佳编码的第一条原则，假定这样计算出的代码组平均长度为最短。计算代码组平均长度时，必有P(xm)bm+P(xn)bn这两项；但是若这两项也符合最佳编码的第一条原则，则在计算代码组平均长度时应将其替换为P(xm)bn+P(xn)bm。4.2信息传输速率和编码效率4.2.3最佳编码东南大学移动通信国家重点实验室“信息论与编码”课件28现在比较它们的大小，为此求它们的差值：[P(xm)bn+P(xn)bm]–[P(xm)bm+P(xn)bn]=P(xm)(bn–bm)+P(xn)(bm–bn)=[P(xm)–P(xn)]