离散信源的无失真编码

第2章 信源熵,2,本章主要内容,2.1单符号离散信源 2.2多符号离散平稳信源及熵 2.3连续信源及熵2.4离散无失真信源编码定理,3,2.4 离散无失真信源编码定理,信源涉及的重要问题：信源输出的信息量有多少：即信源信息量的计算问题。如何更有效地表示信源输出的消息：在尽量提高通信效率的前提下，对信源所发送的消息进行变换，即信源编码。,4,2.4离散无失真信源编码定理,信源编码的定义：把信源输出的原始消息变换成能够满足信道特性，适合信道传输的的符号序列（也叫码序列）的过程，称为信源编码。信源编码的分类无失真信源编码：把所有的信息丝毫不差地编码，然后传送到接收端。离散无失真信源编码：原始消息是多符号离散信源消息，按无失真编码的方法，编成对应的码序列。限失真信源编码：允许不对所有的信息进行编码，只对重要信息进行编码，对其它不影响视听的信息进行压缩、丢弃，但这种压缩失真必须在一定的限度以内，因此称为限失真信源编码。离散限失真信源编码连续限失真信源编码,5,离散信源无失真编码的基本原理原理图 说明：（1）信源发出的消息：是多符号离散信源消息，长度为L,可以用L次扩展信源表示为： XL=(X1X2XL) 其中，每一位Xi都取自同一个原始信源符号集合（n种符号）： X=x1，x2，xn 则最多可以对应nL条消息。,2.4离散无失真信源编码定理,6,（2） 信源编码后，编成的码序列长度为k,可以用k次扩展信宿符号表示为： Yk=(Y1Y2Yk) 称为码字/码组其中，每一位Yi都取自同一个原始信宿符号集合：Y=y1，y2，ym 又叫信道基本符号集合（称为码元，且是m进制的） 则最多可编成mk个码序列，对应mk条消息,7,定长无失真离散信源编码定理,要做到无失真编码，必须使信源消息和编成的码序列一一对应：即每条信源消息可以编成唯一的一个码字（码序列）；反过来，每个码字只能译成一条消息 。称为唯一可译码。定长编码：信源消息编成的码字长度k是固定的。对应的编码定理称为定长信源编码定理。变长编码：信源消息编成的码字长度k是可变的。,8,定长无失真离散信源编码定理,要做到唯一可译，需使编成的码序列数=待编码的消息数，即,其中：H(X)为原始信源的单符号熵,9,定长无失真离散信源编码定理,定长无失真离散信源编码定理：原始信源长为L的平稳无记忆离散序列信源XL=(X1X2XL) ，每个符号的熵为H(X),即平均符号熵为H(X),要想进行无失真的信源编码，需满足码字的最小长度为：,10,例:已知离散信源消息输出的八条消息分别用8个符号表示为：0，1，27，信道基本符号集合为：0，1 ，为了保证信源编码无失真，求输出码组的最小长度，并写出各代码组。解：由题意知：m=2，n=8，L=1 由码长公式,L=1,n=8,k=?,m=2,得,所以码组为：,11,例：有一个中文信源编码器如下图示:求每个汉字使用编码器1的话编成的定长码长至少为多少？求每个汉字对应的二进制码长又为多少？解： (1)设汉字集合中汉字数为10000个，则n=10000，单符号序列，所以L=1 编码器1：输出为十进制数，则m=10，码长为,12,即每个汉字至少要用4位十进制数表示,13,针对编码器2：每输入一个十进制数，编码后输出的二进制码组的码长为多少？,14,上例中，每个汉字编成长为4的十进制码组，每个十进制的码元又编成长为5的二进制等重码，因此上例属于两个信源编码器的级联，则每个汉字编成长为20的二进制码 若信源发“中国”，则,即,15,信源编码速率,由以上的离散无失真信源的定长编码定理得：显然，不等式的右边是编码前的平均符号熵。不等式的左边则是编码后的平均符号熵：表示编码后，传送一个信源符号所需的信息量，称为信源编码速率，记作R：,bit/符号,16,信源编码速率,bit/符号,17,信源编码速率,根据信源编码速率的定义：即编码后，传送一个信源符号所需的信息量，得到离散无失真信源的定长编码所对应的信源编码速率为：那么，若是离散无失真信源的变长编码，所对应的信源编码速率应该是？,bit/符号,18,信源编码效率,由以上的离散无失真信源的定长编码定理得：表示信源熵H(X)是个临界值：要进行无失真信源编码（译码），编码速率需=H(X);否则，当信源编码器的输出速率小于这个临界值后，就无法进行无失真的译码。因此把二者的比值称为信源的编码效率，记作：,bit/符号,19,信源编码效率,信源编码效率分析：,20,定长无失真离散信源编码定理,已知：定长无失真离散信源编码定理：原始信源长为L的平稳无记忆离散序列信源XL=(X1X2XL) ，每个符号的熵为H(X),即平均符号熵为H(X),要想进行无失真的信源编码，需满足码字的最小长度为：,21,离散无记忆信源的变长编码,因此：离散无记忆信源的变长编码定理为：信源为长L的扩展信源，发出的第i条消息出现的概率为pi，对信源符号进行m进制的变长编码，该消息无失真编码后对应的码字长度为ki，则无失真变长编码时的平均码长满足下式：其中，第i条消息对应的码长ki为证明：略（利用下式）,22,若为单符号离散信源的无失真变长编码，则L=1,因此编码定理化简为:,因为,23,注意：二进制编码时，有R= ,同时 。所以 信源无失真编码速率的上下限为编码码长K越长，编码速率R越大 ， 但编码效率 越小。信源编码速率：也就是信源编码以后在信道中传输的速率。（单位：bit/符号）,24,例：已知离散无记忆信源X=x1,x2,且p(x1)=1/4，p(x2)=3/4，求以下两种情况的编码效率：（1）信源发单符号离散消息：x1,x2，且编成x10， x21解：（1）,因为是单符号消息，一个符号表示一条消息，所以L=1,因为编成的码字是二进制的，所以m=2,因为编成的码字长度都是1，所以平均码长k=1,25,（2）信源发2重符号序列