信息论5.2-1信源编码

1、信源编码徐伟业电子信息工程教研室25.2无失真信源编码无失真信源编码的研究内容 若信源输出符号序列的长度L1，即变换成由KL个符号组成的码序列35.21无失真信源编码变换的要求能够无失真或无差错地从Y恢复X，也就是能正确地进行反变换或译码传送Y时所需要的信息率最小由于Yk可取m种可能值，即平均每个符号输出的最大信息量为logm，KL长码序列传输的最大信息量为KLlogm。用该码序列表示L长的信源序列,则送出一个信源符号所需要的信息率平均为45.2无失真信源编码无失真信源编码的研究内容就是就是找到一种编码方式使 最小那么：（1）最小信息率为多少时，才能得到无失真的译码？（2）若小于这个信息率是否

2、还能无失真地译码？55.2无失真信源编码一、定长编码若要实现无失真编码，所编码的码必须是唯一可译码定长码的每个码字长度相等，所以只要定长码是非奇异码，则必为唯一可译码研究定长编码时所需的码长65.2失真信源编码单符号信源X若对信源X进行定长编码，则必须满足n为信源符号数mK为用码符号集，可编出的码长为K的码字个数m为码元符号数K为定长码的码长例：4个信源符号的二元编码75.2无失真信源编码L次扩展信源XL如果将信源X的L次扩展信源进行定长编码，即将长度为L的信源序列变换为长度为KL的码符号序列。L长的信源序列数nLKL长的码符号序列数mKL85.2失真信源编码L次扩展信源XL满足 条件的定长编

3、码虽然可以保证无失真编码，但是平均码长较长，编码效率偏低例：第二章p38页，27个符号的定长二元编码即传输一个英文符号至少需要5个二元符号95.2失真信源编码L次扩展信源XL由第2章的计算结果可知，在考虑了符号出现的概率以及符号之间的相关性后，平均每个符号所提供的信息量约等于1.4bit，因此定长编码后，每个长度为5的码字只载荷约1.4bit的信息量由第3章可知，对于无噪无损的二元信道，信道容量为1bit/符号，即每个二元码最大能载荷1bit的信息量每个长度为5的二元码字最大能载荷5bit的信息量由此可以看出，上述的定长编码的效率很低能否缩短定长编码的码长来提高传输效率？105.2无失真信源编

4、码缩短码长的方法在前面的讨论中没有考虑符号出现的概率以及符号之间的相关性。如果考虑到以上两个因素，定长编码中每个符号所需的平均码长可以减少。例:考虑符号出现的概率设离散无记忆信源概率空间为115.2无失真信源编码若不考虑符号的概率分布，二元定长编码的码长若考虑符号的概率分布，对L长的无记忆信源序列进行编码，会出现小概率事件对小概率事件不进行编码，扩展信源序列数小于nL，平均每个信源符号所需的码长会减小。当然，这就会引入一定的误差。但是，当L足够长时，这种误差概率可以任意小，即可做到几乎无失真地编码。 125.2无失真信源编码:考虑符号之间的相关性设离散无记忆信源概率空间为符号间的依赖关系为其余

5、135.1无失真信源编码缩短码长的方法若不考虑符号之间的相关性，二元定长编码的码长若考虑符号之间的相关性，对此信源的二次扩展信源进行编码。根据已知条件，除 不等于0外，其余145.2无失真信源编码 因此，二次扩展信源X2的信源序列数由n2=16，缩减到4个此时对X2进行定长编码，所需码长KL=2,平均每个符号所需码长K=KL/2=1由此可见，当考虑符号之间的依赖关系后，有些信源符号序列不会出现，这样信源符号序列个数会减少，再进行编码时，所需平均码长就可以缩短 码长的极限是多少？155.2无失真信源编码定长编码定理 由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列 ，可用KL个

6、符号 （每个符号有m种可能值）进行定长编码。对任意 ，只要 则当L足够大时，必可使译码差错小于 ；反之，当 时，译码差错一定是有限值，而当L足够大时，译码几乎必定出错。 165.2无失真信源编码定长编码定理的说明(1)KL:信源L次扩展后，每个信源序列对应的码元数K= KL/L:平均每个信源符号对应的码元数 ，表示KL/L的码符号序列所能携带的最大信息量HL(X) ，表示信源序列中平均每个符号的熵，对于无记忆平稳信源HL(X)=H(X)175.1无失真信源编码定长编码定理的说明(2)信源经过定长编码后，每个码字携带的最大信息量大于信源序列中每个符号的熵， 则可以使传输几乎无失真，当然条件是L足

7、够大当 时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零当 时，则为临界状态，可能无失真，也可能有失真185.2无失真信源编码定长编码定理的说明(3)适用范围定长编码定理是在离散平稳无记忆信源的条件下得到证明的，但它同样适用于平稳有记忆信源，只是要求平稳有记忆信源的极限熵 和极限方差 存在即可对于平稳有记忆信源，定理中应改为极限熵195.2无失真信源编码定长编码定理的说明(4)比较表达式 和 可知，当信源具有等概分布时，两式一致。一般情况下，信源符号并非等概分布，而且符号之间有很强的关联性，故信源熵 或 将远远小于logn这时，在定长编码中每个信源符号平均所需

8、的码符号数将大大减少，从而提高编码效率 205.2无失真信源编码差错概率与信源序列长度L的关系信源X的L次扩展信源XL，共有nL个样本序列对 中的样本不编码，此时差错概率为 中元素出现的概率215.2无失真信源编码差错概率与信源序列长度L的关系如果允许一定的差错概率， 。所以， 中的样本都应该是小概率事件。当L足够大时，小概率事件的出现概率会更小，即差错概率会更小式中 为自信息方差，为一正数。当 和 均为定值时，只要L足够大，Pe可以小于任一正数。 225.2无失真信源编码差错概率与信源序列长度L的关系当信源序列长度L满足 时，能达到差错率要求 235.2无失真信源编码相关概念编码信息率：平均

9、每个码字所能携带的最大信息量编码效率 为了衡量编码效果，定义编码效率为编码信息率大于信源的熵，才能实现无失真编码245.2无失真信源编码相关概念最佳编码效率 由定长编码定理可知最佳编码效率由上式可知，若要译码差错概率越小，编码效率越高，则信源序列长度L必须越长。在实际情况下，要几乎无失真的定长编码，L需要大到难以实现的程度255.2无失真信源编码例设离散无记忆信源概率空间为265.2无失真信源编码对信源符号采用定长二元编码，要求编码效率为 90若取L1，则可算出2.55/0.9=2.83码元/符号即每个符号用2.83个二元码进行定长编码，共有22.83=7.11种可能，按7种可能性计算，信源符

10、号中就有一种符号没有对应的码字，取概率最小的a8, 则Pe0.04 太大275.2无失真信源编码 L取多大时，由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要108个信源符号一起进行编码，这对存储和处理技术的要求太高，在实际应用中很难实现。285.2 无失真信源编码 如果用3比特来对上述信源的8个符号进行定长二元编码，L=1，此时可实现译码无差错，但编码效率只有2.55/3=85%。 因此，一般来说，当L有限时，高传输效率的定长码往往要引入一定的失真和译码错误。解决的办法是可以采用变长编码，真正实现无失真。295.2 无失真信源编码二、变长编码定理在变长编码中，码长KL是

11、变化的问题：对同一信源，其即时码或唯一可译码可以有许多种。究竟哪一种好呢？从高速传输信息的观点来考虑，当然 希望选择由短的码符号组成的码字，就是用码长来作为选择准则根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配）305.2 无失真信源编码变长编码定理平均码长设信源编码后的码字为：码长为：则这个码的平均码长为：315.2无失真信源编码变长编码定理码率：平均每个码元携带的信息量即编码后的信息传输率为最佳码：若有一个唯一可译码，它的平均码长小于其他唯一可译码的长度，则称此码为紧致码或最佳码，无失真信源编码的基本问题就是寻找最

12、佳码325.2无失真信源编码变长编码定理设离散无记忆信源为其信源熵为H(X)，它的L次扩展信源为XL335.2无失真信源编码变长编码定理现用码符号集Y=b1,b2, ,bm对XL进行编码，则总可以找到一种编码方法，构成唯一可译码，使信源X中平均每个符号所需的平均码长，满足其中，表示离散无记忆L扩展信源XL中每个信源序列i所对应的平均码长345.2无失真信源编码变长编码定理 表示离散无记忆信源X中平均每个信源符号所需的平均码长 是每个信源符号所需的平均码长，为了得到这个平均值，不是直接对单个信源符号进行编码，而是对L长的信源序列进行编码若从信道的角度看，当平均码长达到极限值 时，编码后信道的信息

13、传输率355.2无失真信源编码变长编码定理由此可见，这时信道的信息传输率等于无噪无损信道的信道容量C，信息传输效率最高。因此，无失真信源编码的实质是对信源进行适当的变换，使变换后新的码符号尽可能为等概分布，以使每个码符号携带的信息量达到最大，从而使信道的信息传输率R达到信道容量C，实现信源与信道理想的统计匹配365.1无失真信源编码相关概念编码信息率：编码效率码的剩余度：编码信息率大于信源的熵，才能实现无失真编码375.2无失真信源编码例设离散无记忆信源的概率空间为若用二元定长编码(0，1)来构造一个即时码： 平均码长 1二元码符号/信源符号385.2无失真信源编码编码效率为：输出的信息效率为

14、：395.2无失真信源编码L=2的信源序列进行变长编码（编码方法后面介绍），其即时码如下表aip(ai)即时码a1a19/160a1a23/1610a2a13/16110a2a21/16111405.2无失真信源编码二元码符号/信源符号二元码符号/2个信源符号415.2无失真信源编码编码效率为：输出的信息效率为：425.2无失真信源编码L3： R30.985比特/二元码符号 L4： R40.991比特/二元码符号 变长编码，L不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码435.2无失真信源编码定长二元码编码，要求编码效率达到96时，允许译码错误概率 445.2无失真信源编码说明

15、：（）定长码需要的信源序列长，使码表很大，且总存在译码差错。而用变长码编码时，L不需要很大就可达到相当高的编码效率，而且可实现无失真编码。（）随着信源序列长度的增加，编码的效率越来越接近于1。编码后的传输率R也越来越接近于无噪无损二元对称信道的信道容量，达到信源与信道的匹配。455.2无失真信源编码最佳码的定义凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可称为最佳码最佳编码思想将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短最佳码的编码主要方法香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码465.2无失真信源编码

16、香农编码Shanon编码算法是一种简单的按概率编码的方法，对于一个离散无记忆信源，如果其某一符号ai的先验概率为p(ai)，则就取其码长为475.2无失真信源编码香农编码（1）将信源消息符号按其出现的概率大小依次排列（2）确定满足下列不等式的整数码长Ki485.2无失真信源编码香农编码（3）为了编成唯一可译码，计算第i个消息的累加概率（4）将累加概率Pi变换成二进制数（乘2取整，顺序排列）（5）取Pi二进数的小数点后Ki位即为该消息符号的二进制码字495.2无失真信源编码例 设信源共7个符号消息，其概率和累加概率如下表所示信源消息符号ai符号概率(ai)累加概率Pi-log p(ai)码字长度

17、Ki码字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.6471111110505.2无失真信源编码码元/符号比特/码元 515.2无失真信源编码费诺编码（1）将信源消息符号按其出现的概率大小依次排列（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”525.2无失真信源编码费诺编码（3）将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之

18、和近于相同，并又赋予两个组一个二进制符号“0”和“1”（4）如此重复，直至每个组只剩下一个信源符号为止（5）信源符号所对应的码字即为费诺码535.2无失真信源编码消息符号ai各个消息概率 p(ai)第一次分组第二次分组第三次分组第四次分组二元码字码长Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114545.2无失真信源编码 码元/符号 bit/符号 555.2无失真信源编码费诺编码的基本特点费诺编码在构造码树时，是从树根开始到终端节点结束由于赋码元时的任意性，因此编出的码字不是

19、唯一的费诺编码虽属于概率匹配范畴，但并未严格遵守匹配规则，有时出现概率小的码长反而小。因此平均码长一般不会最小费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率565.2无失真信源编码20110.25a24111110.0625a841110010.0625a741101010.0625a6411000.0625a5310110.125a43100000.125a3200010.25a1码长Ki二元码字第四次分组第三次分组第二次分组第一次分组各个消息概率 p(ai)消息符号ai001575.2无失真信源编码 码元/符号 bit/符号 b

20、it/符号 585.2无失真信源编码哈夫曼编码（1）将信源消息符号按其出现的概率大小依次排列（2）取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队595.2无失真信源编码哈夫曼编码（3）对重排后的两个概率最小符号重复步骤(2)的过程（4）不断继续上述过程，直到最后两个符号配以0和1为止（5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字605.2无失真信源编码哈夫曼编码信源符号ai概率p(ai)码字Wi码长Kia10.20102a20.19112a30.180003a40.170013a50.15010

21、3a60.1001104a70.0101114615.2无失真信源编码哈夫曼编码0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.01010101010101625.2无失真信源编码 码元/符号 bit/符号 哈夫曼编码效率最高，费诺编码效率次之，香农编码效率最低635.2无失真信源编码哈夫曼编码方法得到的码并非唯一每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，

22、所以可以得到不同的哈夫曼码，但不会影响码字的长度645.2无失真信源编码哈夫曼编码方法得到的码并非唯一对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差655.2无失真信源编码哈夫曼编码例 设有离散无记忆信源5.2无失真信源编码0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.20.10101010101010101675.2无失真信源编码685.2无失真信源编码信源符号ai概率p(ai)码字Wi1码长Ki1码字Wi2码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113695.2无失真信源编码705.2无失真信源编码哈夫曼编码的特点哈夫曼编码实际上构造了一个码树，码树从端点开始构造，直到树根结束，因此编出的码是非延长码哈