信息论与编码-第五章.ppt

信息论与编码-信源编码 所以等长编码定理告诉我们，只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真的编码。条件是所取得符号数L足够大。 信息论与编码-信源编码 例如，某信源有8种等概率符号，L＝1，信源序列熵达到最大值： H1(X)=log8=3bit/符号 即该信源符号肯定可以用3比特的信息率进行无失真的编码。这就是说，如果采用二进制符号作为码字输出符号，则用3个比特就可以表示一个符号。 信息论与编码-信源编码 当信源符号输出概率不相等时，如， p(xi)={.4,.18,.1,.1,.07,.06,.05,.04} 则此时，H1(X)=2.55bit/符号 因22.55=5.856，即若用2.55bit来表示，只有5.856种可能码字，还有部分符号没有对应的码字 这些符号一旦出现，被传输至接受端，就没有对应的码字译码，因而引起译码差错。所以定长编码一般都存在译码差错，只是差错大小不同。 当L足够大时，有些序列发生的概率很小，因此可使得译码差错达到足够小。 设 是信源序列的样本矢量， ，则共有 种样本 我们把它分成两个互补的集 和 集中的元素（样本矢量）有与之对应的不同码字 而集 中的元素没有对应的输出码字，因而会在译码时发生差错。 信息论与编码-信源编码 信息论与编码-信源编码 如果允许一定的差错 ，则编码时只需对属于 中的 个样本矢量赋予相应的不同字码，即输出码字的总个数 只要大于 就可以了。 在这种编码方式下，差错概率 即为集 中元素发生的概率 , 此时要求 ， 因而 集中的样本都应是小概率事件。 当L则增大时虽然样本数也随着增多，但小概率事件的概率将更小，有望使 更小。 设差错概率为 ，信源序列的自方差为 根据契比雪夫不等式，得： 当 和 均为定值时，只要L足够大， 可以 小于任一整数 ，即 信息论与编码-信源编码 信息论与编码-信源编码 此时要求： 只要 足够小，就可以几乎无差错地译码，当然代价是L变得更大。 信息论与编码-信源编码 令 为码字最大平均符号信息量。 定义编码效率为： 最佳编码效率为 信息论与编码-信源编码 无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1， 但要在实际中实现，则要求信源符号序列的L非常大进行统一编码才行，这往往是不现实的。 信息论与编码-信源编码 例题：设离散无记忆信源概率空间为 信源熵为 自信息方差为 信息论与编码-信源编码 信息论与编码-信源编码 对信源符号采用定长二元编码，要求编码效率 ，无记忆信源有 ，因此 可以得到 如果要求译码错误概率 ，则 信息论与编码-信源编码 由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要 个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。 如果用3比特来对上述信源的8个符号进行定长二元编码，L=1，此时可实现译码无差错，但编码效率只有2.55/3=85%。因此，一般说来，当L有限时，高传输效率的定长码往往要引入一定的失真和译码错误。解决的办法是可以采用变长编码。 信息论与编码-信源编码 变长编码定理 在变长编码中，码长是变化的。对同一信源，其即时码或唯一可译码可以有许多种。究竟哪一种好呢？从高速传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长来作为选择准则，为此我们引入码的平均长度。 设信源为 信息论与编码-信源编码 编码后的码字为 其码长分别为 因为对唯一可译码来说，信源符号与码字是一一对应的，所以有 则这个码的平均长度为 它是每个信源符号平均需用的码元数。 信息论与编码-信源编码 对某一信源来说，若有一个唯一可译码，其平均长度小于所有其它的唯一可译码的平均长度，则该码称为紧致码，或称最佳码。 无失真变长信源编码的基本问题就是要找最佳码。 信息论与编码-信源编码 单个符号变长编码定理： 若一离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度 满