无失真信源编码讲义.ppt

（4） 时，则为临界状态，可能无失真，也可能有失真。 举例：某单符号信源有8种符号，分析各种情况下无失真编码的存在性 解：采用二进制符号作为码字输出符号，Yk∈{0,1}。 当8种符号等概率分布时，由题意可得 信源序列长度L＝1，X＝{a1,a2,…,a8} 各符号概率相同，即p(xi)＝1/8，i＝1,2,…,8 信源熵为H（X）＝－ 比特 1、码字携带的最大信息量KLlog22=LHL(X)=H(X)时 KL=H(X)＝3bit 此时，KL为3位二进制数，能提供mKL＝23＝8种码字，对应8种符号。该临界状态下可实现无失真编码 2、KL＞H(X)=3bit时无失真编码必然存在 3、KL＜H(X)=3bit时，码字个数mKL23,无法区别8个符号，编码误差必然存在 当信源符号输出概率不相等时：p(xi)={0.4,0,18,0.1,0.1,0.07,0.06,0.05,0.04} 验证 信源熵为H(X)=- 比特 码字携带的最大信息量KLlog22=LHL(X)=H(X)时 KL=H(X)＝2.55 比特 此时，KL小于3比特，能提供mKL＝22.55＝5.856种码字，不能区别8种符号。该临界状态下必然存在编码误差。 式中 为自信息方差， ?为一正数。当 和 均为定值时，只要L足够大，Pe可以小于任一正数?。 4.差错概率 即当信源序列长度L满足 时， 能达到差错率要求 。 5.编码效率： 满足一定错误概率的最佳编码效率为： (1) 信源的序列长度L满足: (2) 联立(1),(2)可得: 允许错误概率越小，编码效率又要高的话，信源序列的长度越长（L ∞），但实际不可能实现。 例 设离散无记忆信源概率空间为 比特/符号 若要求译码错误概率 码 { 非分组码 分组码 { 奇异码 非奇异码 { 非唯一可译码 唯一可译码 { 非即时码 即时码（非延长码） 码的分类如下： 唯一可译码存在的充要条件 用树的概念可导出唯一可译码存在的充分和必要条件，即各码字的长度Ki应符合克劳夫特不等式： (3-1-1) 式中，m是进制数，n是信源符号数。 注：克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。 唯一可译码的判断法计算分组码中所有可能的尾随后缀集合F,观察F中有没有包含任一码字,若无则为唯一可译码;若有则一定不是唯一可译码. 第二节 定长编码定理 由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2…Xl…XL，可用KL个符号Y1，Y2，…，Yk，…，（每个符号有m种可能值）进行定长编码。对任意?0，?0，只要 则当L足够大时，必可使译码差错小于?； 反之，当 时，译码差错一 定是有限值，而L足够大时，译码几乎必定出错。 变长编码定理 在变长编码中，码长是变化的。 根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配） 第三节 变长编码定理 单个符号变长编码定理： 若一离散无记忆信源的符号熵为H（X），每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式