无失真信源编码定理1012下午上课

第2章信源熵本章主要内容2.1单符号离散信源2.2多符号离散平稳信源及熵2.3连续信源及熵2.4离散无失真信源编码定理22.4离散无失真信源编码定理信源涉及的重要问题：信源输出的信息量有多少：即信源信息量的计算问题。如何更有效地表示信源输出的消息：在尽量提高通信效率的前提下，对信源所发送的消息进行变换，即信源编码。3信源编码包括两个功能：（1）

将信源符号变换成适合信道传输的符号；（2）

压缩信源冗余度，提高传输效率。4{a1,a2,…,aK}为信源符号集，序列中每一个符号uml都取自信源符号集。{b1

，b2

，…，bD}是适合信道传输的D个符号，用作信源编码器的编码符号。编码输出码字cm=cm1cm2…cmn，

cmk∈{b1

，b2

，…，bD}k=1,2,

…,n

，n表示码字长度，简称码长

信源符号{a1,a2,…,aK}

信道符号（码符号）{b1,b2,…,bD}

图3-1信源编码器模型

信源

信源编码器

一般来说，信源编码可归纳为如图3-1所示的模型。

消息

ui

=ui1ui2…uiL

码字ci

=ci1ci2…cin

5

信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，编码方法是多种的。【例3.3】用{u1

，u2

，u3，u4}表示信源的四个消息，码符号集为{0,1}，表3-1列出了该信源的几种不同编码。表3-1同一信源的几种不同编码信源消息各消息概率码1码2码3码4u1q(u1)000001u2q(u2)1101110u3q(u3)101000100u4q(u4)1111111000码的分类63.变长码若码字集合C中的所有码字cm(m=1,2,…,M)，其码长不都相同，称码C为变长码，表3-1中列出的码3、码4就是变长码。2.等长码在一组码字集合C中的所有码字cm(m=1,2,…,M)，其码长都相同，则称这组码C为等长码，表3-1中列出的码1、码2就码长n=2等长码。一般，可以将码简单的分成如下几类：1.二元码若码符号集为{0，1}，则码字就是二元序列，称为二元码,二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，表3-1列出的4种码都是二元码。7离散信源无失真编码

内容提要用尽可能少的符号来传输信源消息，目的是提高传输效率，这是信源编码应考虑的问题，等长编码定理给出了等长编码条件下，其码长的下限值，变长编码定理（香农第一定理）给出了信源无失真变长编码时其码长的上、下限值。82.4离散无失真信源编码定理信源编码的定义：把信源输出的原始消息变换成能够满足信道特性，适合信道传输的的符号序列（也叫码序列）的过程，称为信源编码。信源编码的分类无失真信源编码：把所有的信息丝毫不差地编码，然后传送到接收端。离散无失真信源编码：原始消息是多符号离散信源消息，按无失真编码的方法，编成对应的码序列。限失真信源编码：允许不对所有的信息进行编码，只对重要信息进行编码，对其它不影响视听的信息进行压缩、丢弃，但这种压缩失真必须在一定的限度以内，因此称为限失真信源编码。离散限失真信源编码连续限失真信源编码9离散信源无失真编码的基本原理原理图

说明：（1）信源发出的消息：是多符号离散信源消息，长度为L,可以用L次扩展信源表示为：XL=(X1X2……XL)其中，每一位Xi都取自同一个原始信源符号集合（n种符号）：X={x1，x2，…xn}则最多可以对应nL条消息。2.4离散无失真信源编码定理10定长无失真离散信源编码定理要做到无失真编码，必须使信源消息和编成的码序列一一对应：即每条信源消息可以编成唯一的一个码字（码序列）；反过来，每个码字只能译成一条消息。——称为唯一可译码。定长编码：信源消息编成的码字长度k是固定的。对应的编码定理称为定长信源编码定理。变长编码：信源消息编成的码字长度k是可变的。Yk=(Y1Y2……Yk)XL=(X1X2……XL)11定长无失真离散信源编码定理要做到唯一可译，需使编成的码序列数>=待编码的消息数，即其中：H(X)为原始信源的单符号熵

Yk=(Y1Y2……Yk)XL=(X1X2……XL)12定长无失真离散信源编码定理定长无失真离散信源编码定理：原始信源长为L的平稳无记忆离散序列信源XL=(X1X2……XL)，每个符号的熵为H(X),即平均符号熵为H(X),要想进行无失真的信源编码，需满足码字的最小长度为：

13例:已知单符号离散信源消息输出的八条消息分别用8个符号表示为：{0，1，2…7}，信道基本符号集合为：{0，1}，为了保证信源编码无失真，求输出码组的最小长度，并写出各代码组。解：由题意知：m=2，n=8，L=1由码长公式

L=1,n=8k=?,m=2得

所以码组为：

14例：有一个中文信源编码器如下图示:求每个汉字使用编码器1的话编成的定长码长至少为多少？求每个汉字对应的二进制码长又为多少？解：(1)设汉字集合中汉字数为10000个，则n=10000，单符号序列，所以L=1

编码器1：输出为十进制数，则m=10，码长为

k1=?,m=10L=1,n=1000015即每个汉字至少要用4位十进制数表示

16针对编码器2：每输入一个十进制数，编码后输出的二进制码组的码长为多少？

L=1,n=10k2=?,m=2k1=4,m=10L=1,n=1000017上例中，每个汉字编成长为4的十进制码组，每个十进制的码元又编成长为5的二进制等重码，因此上例属于两个信源编码器的级联，则每个汉字编成长为20的二进制码

若信源发“中国”，则

即

k1=4,m=10L=1,n=10000k2=5,m=218信源编码速率由以上的离散无失真信源的定长编码定理得：显然，不等式的右边是编码前的平均符号熵。不等式的左边则是编码后的平均符号熵：表示编码后，传送一个信源符号所需的信息量，称为信源编码速率，记作R：bit/符号19信源编码速率bit/符号信源编码器20信源编码速率根据信源编码速率的定义：即编码后，传送一个信源符号所需的信息量，得到离散无失真信源的定长编码所对应的信源编码速率为：那么，若是离散无失真信源的变长编码，所对应的信源编码速率应该是？bit/符号21信源编码效率由以上的离散无失真信源的定长编码定理得：表示信源熵H(X)是个临界值：要进行无失真信源编码（译码），编码速率需>=H(X);否则，当信源编码器的输出速率小于这个临界值后，就无法进行无失真的译码。因此把二者的比值称为信源的编码效率，记作η：bit/符号22信源编码效率信源编码效率分析：23注意：二进制编码时，有R=,同时。所以信源无失真编码速率的上下限为编码码长K越长，编码速率R越大，但编码效率越小。信源编码速率：也就是信源编码以后在信道中传输的速率。（单位：bit/符号）24例：已知离散无记忆信源X={x1,x2},且p(x1)=1/4，p(x2)=3/4，求以下两种情况的编码效率：（1）信源发单符号离散消息：x1,x2，且编成x1—>0，x2—>1解：（1）因为是单符号消息，一个符号表示一条消息，所以L=1因为编成的码字是二进制的，所以m=2因为编成的码字长度都是1，所以平均码长k=125（2）信源发2重符号序列消息，无记忆：x1x1，x1x2，x2x1，x2x2，且编成x1x1—>111，x1x2—>110，x2x1—>10，x2x2—>0解：说明：发L重符号序列的信源编码器效率要高于单符号离散无记忆信源，但同时也增加了编码和解码的复杂度。26定长无失真离散信源编码定理已知：定长无失真离散信源编码定理：原始信源长为L的平稳无记忆离散序列信源XL=(X1X2……XL)，每个符号的熵为H(X),即平均符号熵为H(X),要想进行无失真的信源编码，需满足码字的最小长度为：

27离散无记忆信源的变长编码因此：离散无记忆信源的变长编码定理为：信源为长L的扩展信源，发出的第i条消息出现的概率为pi，对信源符号进行m进制的变长编码，该消息无失真编码后对应的码字长度为ki，则无失真变长编码时的平均码长满足下式：其中，第i条消息对应的码长ki为证明：略（利用下式）信源每条消息包含的信息量信源第i条消息包含的信息量28若为单符号离散信源的无失真变长编码，则L=1,因此编码定理化简为:因为29总结无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，但要在实际中实现，则要求信源符号序列的L非常大进行统一编码才行，这往往是不现实的。302、编码效率：最佳编码效率为1、编码信息率：对于定长编码，定义：等长编码可表述为，若平均每个码符号所能携带的最大信息量设U=X31结论：①当n=m时，K≥L不有效。②当K=L时，m≥n，亦不满足有效性。

由

解决办法：引入信源统计特性。例：英文电报：32字符（26个字母及6个字符）即n=32，m=2，L=1得：H(S)=1.4bit每5bit码字只载荷1.4bit信息量---效率低这时，我们可以修改①式为：

K/L≥H(U)/logm----②

即考虑信源不等概率，而码字为等概率，----①这样即使n=m,只要满足就有可能实现K<L32例题：设离散无记忆信源概率空间为信源熵为自信息方差为33对信源符号采用定长二元编码，要求编码效率无记忆信源有因此可以得到如果要求译码错误概率则由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。等长编码时34一般说来，当L有限时，高传输效率的定长码往往要引入一定的失真和译码错误。解决的办法是可以采用变长编码。35变长编码定理在变长编码中，码长是变化的。对同一信源，究竟哪一种好呢？从高速传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长来作为选择准则，为此我们引入码的平均长度。设信源为编码后的码字为其码长分别为因为对唯一可译码来说，信源符号与码字是一一对应的，所以有一变长编码的基本参数1、码的平均长度36则这个码的平均长度为它是每个信源符号平均需用的码元数。对某一信源来说，若有一个唯一可译码，其平均长度小于所有其它的唯一可译码的平均长度，则该码称为紧致码，或称最佳码。无失真变长信源编码的基本问题就是要找最佳码。2.平均每个码元携带的信息量---即编码后信道的信息传输速率为3.编码后每秒钟信道的信息传输速率为37二、单个符号变长编码定理（平均码长界定定理）：1.定理:若一离散无记忆信源的符号熵为H(X)，