信息论基础教程 教学课件 作者焦瑞莉 第四章 离散信源的无失真编码.ppt

第四章 离散信源的无失真编码 本章主要内容 编码器 等长编码及其定理 不等长编码及其定理 编码器 编码器 码：特定的符号集合。 编码：建立在源符号与码符号或码符号组之间的变换。 3 5 4 7——011101100111 信源编码：从信源输出符号序列到码符号序列的一种映射，其逆映射称译码。 信源编码的目的：适合于信道传输，提高输出效率 编码器 等长编码及其定理 ak p(ak) 码A 码B a1 0.5 00 00 a2 0.25 01 01 a3 0.125 10 00 a4 0.125 11 10 等长编码及其定理 等长编码及其定理 定理4.1（等长信源编码定理） 对于上述编码，对于任意 ，只要 N 充 分大，且满足不等式 则译码错误概率任意小（可以进行无失真编 码）。 反之，若 则不可能进行无失真编码，且N 充分大时，译 码错误概率近似等于1。 等长编码定理 实现无失真编码 存在问题：N 充分大使存储和处理难度大。 解决办法：采用变长编码。 等长信源编码定理的意义： 信源的信息熵是（信源冗余度的可压缩性）无失 真数据压缩的理论极限。压缩到小于这个极限值，则 无失真做不到。 不等长编码及其定理 唯一可译码：一个码的任意一串有限长的码符号序列 只能被唯一地译成所对应的信源符号序列。 即时码：唯一可译码，译码时无需参考后续的码符号就能立即作出译码判断。 异前缀码：码中没有码字是任意其他码字的前缀。可以在无延时的情况下解码。 异前缀码等价于即时码 不等长编码及其定理 不等长编码及其定理 例： p(ak) 码A 码B 码C 码D a1 0.5 0 0 0 0 a2 0.25 0 10 01 10 a3 0.125 1 00 011 110 a4 0.125 10 01 0111 1110 码A：奇异，非唯一； 码B ：非奇异，非唯一； 码C：唯一，非异前缀； 码D：唯一，异前缀，即时码。 定理4.2 设信源S = { s1, s2,…, sq}，码符号集X = { x1, x2,…, xr}，又设码字为（W1，W2，…，Wq），其分别对应的码长为l1，l2，…，lq，则存在唯一可译码的充要条件为 例： p(ak) 码A 码B 码C 码D a1 0.5 0 0 1 1 a2 0.25 11 10 11 01 a3 0.125 00 00 100 001 a4 0.125 11 01 1010 0001 r＝2，码A，码B ：l1=1, l2=l3=l4=2, 这样码A，码B不可能是唯一可译码。 r＝2，码C，码D ：l1=1, l2=2, l3=3, l4=4, 码C不是唯一可译码，码D是唯一可译码。 信源编码有关概念 （1）平均码长 单位：码符号/信源符号 意义：每个源符号平均需要的码符号数。 编码后每个信源符号平均用 个码符号表示。 （2）信息传输率（平均每个码符号携带的信息量） 越短，信息传输率就越高。 （3）最佳码（紧致码） 最佳码：对于某一信源和某一码符号集，若有一唯一可 译码，其平均码长小于所有其他唯一可译码的