（精）6-第六讲 等长信源编码定理.ppt

* * 6－1 信源编码 6－2 典型序列和信源划分定理 6－3 等长信源编码定理 第六讲 等长信源编码定理 6－1 信源编码 信源编码就是把信源输出的源随机序列 1、基本概念 变换成码序列 信源 Si= （si1,si2,…,siN） si k?S={s1, s2,.. sq} 信源编码 Wi= （xi1,xi2,…,xi L） xi k?{x1, x2,.. xr } 信源符号集 码符号集 源序列 码字 编码就是从消息集到码字集的一种映射。 记住符号！ 变换的要求是能够无失真或无差错地从 Wi 恢复Si也就是能正确地进行反变换或译码。同时希望传送 Wi 时所需的信息率最小（即 Wi 的符号个数最少）。 由于xi可取 r 种可能值，其最大信息量是 log r。这就是说，送出一个信源符号所需的信息率平均为 M 是 x所能够编成的码字的个数。所谓信息率最小，就是找一种编码方式使 R’ 最小。 如何找到？如何实现有效性？ －－－－－－ 研究信源编码定理有定长编码和变长编码两种方法。 前者 L 是定值，相应的编码定理称为定长编码定理，我们寻找最小 L 值的编码方法； 后者 L 为变值，相应的编码定理为变长编码定理。此时 L 值最小意味着它的数学期望为最小。 （平均码长） 然而上述最小信息率为多少时，才能得到无失真的译码？若小于这个信息率是否还能够无失真译码？这是信源编码定理要研究的内容。 编码速率 ：送出一个信源符号所需的平均信息率； 码字 ：编码器输出的一个码符号的序列； 二元码 ：码符号集为（0，1），码字为二元序列； r－元码 ：码符号集为r个符号，码字为r元序列； 不等长码 ：码字长度不相等； 单义可译或唯一可译码： 每一个信源消息都至少有一个码字与之对应， 且不同的消息对应不同的码字。 等长码 ：码字长度都相等； 码 ：码字的全体。 编码效率 ： 称下式为编码效率： 码元：码符号。 定长编码定理概述 对于单义可译码，若 为待编码的消息的 个数，其中 q为信源符号的个数，N 为信源序列长度， 则单义可译码存在的充要条件为： 其中：r 为码符号个数，L为码长， L / N 是每个信源符号所需的平均码元数。 上边是独立等概的情况。当不等概时，我们注意到每个信源符号的信息量为H(S)，长为 N 的信源输出序列集的最大熵为NH(S)，译码时若 r 个符号独立等概，则其携带的信息量最大，码长最短，所以最小码长至少应满足： 才能实现无信息损失。但仅当 N 为无穷时，一个信源输出序列的平均每符号的信息量才等于H(S)，所以应选择N 足够大，使得 是与 N 有关的正数，且当 严格的证明需要利用序列的渐进等分特性： AEP：Asymptotic equipartition property 当独立等分布的随机序列趋于无限长时，一些序列 以近似相等的高概率出现。这些序列为典型序列， 编码只对它们编码即可。 AEP是大数定律的直接应用： 二项分布： （i.i.d. ：Independent identically distributed） （Bernoulli Scheme） i P(Ai) 车比雪夫不等式： 证明： （V－方差） （弱）大数定律： （Bernoulli 形式） 另一形式： 随着n增加，图形越展开和平坦，同时概率越集中到中央部分。这些序列就是典型序列 typical sequences k Pn(k) n np 设信源输出的 N 长序列： 信源是无记忆的，消息序列的概率和自信息量为： 6－2 典型序列和信源划分定理 消息序列中平均一个消息符号给出的信息量为: 而信源符号集的熵，就是 的均值： 根据弱大数定律，对任意 , 有： 上式说明，当N足够大时， 则将以概率 趋近于H(S)， 通过适当选择N，可令 由车比雪夫不等式： （D－方差） 上述的不等式是任意序列都可以吗？ 假如随机序列都取同一个字母， 不可能小于任意小的 ? 因此弱大数定律中不等式只对一些序列成立： 所以应当理解为：使