离散信源的无失真编码

第2章信源熵本章主要内容2.1单符号离散信源2.2多符号离散平稳信源及熵2.3连续信源及熵2.4离散无失真信源编码定理

学会忘记痛苦，为阳光记忆腾出空间。

——耶鲁大学励志语录

22.4离散无失真信源编码定理信源涉及的重要问题：信源输出的信息量有多少：即信源信息量的计算问题。如何更有效地表示信源输出的消息：在尽量提高通信效率的前提下，对信源所发送的消息进行变换，即信源编码。32.4离散无失真信源编码定理信源编码的定义：把信源输出的原始消息变换成能够满足信道特性，适合信道传输的的符号序列（也叫码序列）的过程，称为信源编码。信源编码的分类无失真信源编码：把所有的信息丝毫不差地编码，然后传送到接收端。离散无失真信源编码：原始消息是多符号离散信源消息，按无失真编码的方法，编成对应的码序列。限失真信源编码：允许不对所有的信息进行编码，只对重要信息进行编码，对其它不影响视听的信息进行压缩、丢弃，但这种压缩失真必须在一定的限度以内，因此称为限失真信源编码。4离散信源无失真编码的基本原理原理图

说明：（1）信源发出的消息：是多符号离散信源消息，长度为L,可以用L次扩展信源表示为：XL=(X1X2……XL)其中，每一位Xi都取自同一个原始信源符号集合（n种符号）：X={x1，x2，…xn}则L次扩展信源最多可以对应nL条消息。2.4离散无失真信源编码定理5（2）信源编码后，编成的码序列长度为k,称为k次扩展信宿，表示为：

Yk=(Y1Y2……Yk)称为码字/码组其中，每一位Yi都取自同一个原始信宿符号集合Y：Y={y1，y2，…ym}又叫信道基本符号集合（其中的每个符号称为码元，易看出，信宿是m进制的）

则最多可编成mk个码序列，它应该和mk条信源消息一一对应。6定长无失真离散信源编码定理要做到无失真编码，必须使信源消息和编成的码序列一一对应：即每条信源消息编成唯一的一个码字（码序列）；反过来，每个码字只能译成一条消息。——称为唯一可译码。定长编码：信源消息编成的码字长度k是固定的。对应的编码定理称为定长信源编码定理。变长编码：信源消息编成的码字长度k是可变的。Yk=(Y1Y2……Yk)XL=(X1X2……XL)7定长无失真离散信源编码定理要做到唯一可译，需使编成的码序列数>=待编码的消息数，即其中：H(X)为原始信源的单符号熵

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

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

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

所以码组为：

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

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

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

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

L=1,n=10k2=?,m=2k1=4,m=10L=1,n=10000实际为了抗干扰，k2

取513上例中，每个汉字编成长为4的十进制码组，每个十进制的码元又编成长为5的二进制等重码，因此上例属于两个信源编码器的级联，则每个汉字编成长为20的二进制码

若信源发“中国”，则

即

k1=4,m=10L=1,n=10000k2=5,m=214信源编码速率由以上的离散无失真信源的定长编码定理得：显然，不等式的右边是编码前的平均符号熵。不等式的左边则是编码后的平均符号熵：表示编码后，传送一个信源符号所需的信息量，称为信源编码速率，记作R：bit/符号15信源编码速率bit/符号信源编码器16信源编码速率根据信源编码速率的定义：即编码后，传送一个信源符号所需的信息量，得到离散无失真信源的定长编码所对应的信源编码速率为：那么，若是离散无失真信源的变长编码，所对应的信源编码速率应该是？bit/符号17信源编码效率由以上的离散无失真信源的定长编码定理得：表示信源熵H(X)是个临界值：要进行无失真信源编码（译码），编码速率需>=H(X);否则，当信源编码器的输出速率小于这个临界值后，就无法进行无失真的译码。因此把二者的比值称为信源的编码效率，记作η：bit/符号18信源编码效率信源编码效率分析：19定长无失真离散信源编码定理

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

20离散无记忆信源的变长编码因此：离散无记忆信源的变长编码定理为：信源为长L的扩展信源，发出的第i条消息出现的概率为pi，对信源符号进行m进制的变长编码，该消息无失真编码后对应的码字长度为ki，则无失真变长编码时的平均码长满足下式：其中，第i条消息对应的码长ki为信源每条消息包含的信息量信源第i条消息包含的信息量21若为单符号离散信源的无失真变长编码，则L=1,因此编码定理化简为:因为22注意：二进制编码时，有R=。因为R>=H(X),同时为了满足信道编码定理的无失真传输，需使。所以信源无失真编码速率的上下限为编码码长K越短，编码速率R越小，但编码效率越大。信源编码速率：也就是信源编码以后在信道中传输的速率。（单位：bit/符号）23例：已知离散无记忆信源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=124（2）信源发2重符号序列消息，无记忆：x