《信息论》第四章.ppt

第四章 离散信源的无失真编码1§编码器 §等长编码及其定理 §不等长编码及其定理本章主要内容2编码器S =（s1，s2，…，sq） C =（W1，W2，…，Wk） X =（x1，x2，…，xr ）信源 符号码字码符号编码器 3§ § 码：特定的符号集合码：特定的符号集合 § § 编码：建立在源符号与码符号或码符号组之编码：建立在源符号与码符号或码符号组之 间的变换间的变换3 5 4 7——>0111011001113 5 4 7——>011101100111 § § 信源信源编码：编码：从信源输出符号序列到码符号序从信源输出符号序列到码符号序 列的一种映射，其逆映射称译码列的一种映射，其逆映射称译码 § § 信源信源编码的目的：编码的目的：适合于信道传输，提高输适合于信道传输，提高输 出效率出效率编码器4编码器同价码 非同价码非奇异码奇异码不等长码等长码信源 符号 si 出现 概率 pi 码 A码 B码Cs1p10000s2p20101s3p310100s4p41110115等长编码及其定理唯一可译码：一个码的任意一串有限长的码符号序列只唯一可译码：一个码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列。

能被唯一地译成所对应的信源符号序列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等长非奇异码一定是唯一可译码等长非奇异码一定是唯一可译码6对信源对信源S S的的N N次扩展信源次扩展信源S SN N进行等长编码进行等长编码若若S S = { = { s s1 1, , s s2 2,…,,…, s sq q} }，则，则N N次扩展信源次扩展信源S S N N= { = { a a1 1, , a a2 2,…,,…, a aqNqN} }，， 共有共有q qN N个符号序列个符号序列 设码符号集为设码符号集为X X = { = { x x1 1, , x x2 2,…,,…, x xr r} }，，长度为长度为l l 的码符号序列的码符号序列WWi i = (= (x xi i1 1 x xi i2 2 … … x xil il), ), x xi i1 1, , x xi i2 2,…,,…, x xil il∈∈X X。

若要求编得的等长码是唯一可译码则必须满足若要求编得的等长码是唯一可译码则必须满足q q N N≤ ≤r r l l 等长编码及其定理7对对 q q N N≤ ≤r r l l 两边取对数，则得两边取对数，则得 N N loglogq q ≤ ≤ l l loglogr r或或例如英文电报有例如英文电报有3232个符号个符号（（2626个英文字母加上个英文字母加上6 6个字符个字符）） ，，即即q q = = 3232若若r r = = 2 2，，N N =1=1( (即对信源的逐个符号进行二即对信源的逐个符号进行二 进制编码进制编码) )，则，则等长编码及其定理8定理定理4.14.1（等长信源编码定理）（等长信源编码定理）对于上述编码，对于任意对于上述编码，对于任意 ，只要，只要 N N 充充 分大，且满足不等式分大，且满足不等式则译码错误概率任意小（可以进行无失真编则译码错误概率任意小（可以进行无失真编 码）反之，若反之，若则不可能进行无失真编码，且则不可能进行无失真编码，且N N 充分大时，译充分大时，译 码错误概率近似等于码错误概率近似等于1 1。

9实现无失真编码实现无失真编码存在问题：存在问题：N N 充分大使存储和处理难度大充分大使存储和处理难度大解决办法：采用变长编码解决办法：采用变长编码 等长信源编码定理等长信源编码定理的意义：的意义：信源的信息熵信源的信息熵是（是（信源冗余度的可压缩性）信源冗余度的可压缩性）无失无失 真数据压缩的理论极限压缩到小于这个极限值，则真数据压缩的理论极限压缩到小于这个极限值，则 无失真做不到无失真做不到等长编码定理10不等长编码及其定理不等长编码的基本思想不等长编码的基本思想——“——“量体裁衣量体裁衣””出现概率出现概率大大的信源符号用的信源符号用较短码较短码字表示，出现概率字表示，出现概率小小 的信源符号用的信源符号用较长码较长码字表示这样平均每个信源符号所需字表示这样平均每个信源符号所需 的码符号数降低，提高编码效率的码符号数降低，提高编码效率 • • 唯一可译码：一个码的任意一串有限长的码符号序列唯一可译码：一个码的任意一串有限长的码符号序列 只能被唯一地译成所对应的信源符号序列只能被唯一地译成所对应的信源符号序列 • • 即时码：唯一可译码，译码时无需参考后续的码符号即时码：唯一可译码，译码时无需参考后续的码符号 就能立即作出译码判断。

就能立即作出译码判断 • • 异前缀码异前缀码：码中没有码字是任意其他码字的前缀可：码中没有码字是任意其他码字的前缀可 以在无延时的情况下解码以在无延时的情况下解码 异前缀码等价于异前缀码等价于即时码即时码11不等长编码及其定理12例：例：p(ap(ak k) ) 码码A A 码码B B 码码C C 码码D Da a1 1 0.5 0 0 0 00.5 0 0 0 0a a2 2 0.25 0 10 01 100.25 0 10 01 10a a3 3 0.125 1 00 011 1100.125 1 00 011 110a a4 4 0.125 10 01 0111 11100.125 10 01 0111 1110码码A A：：奇异，非唯一；奇异，非唯一； 码码B B ：：非奇异，非唯一；非奇异，非唯一； 码码C C：：唯一，非异前缀；唯一，非异前缀； 码码D D：：唯一，异前缀，即时码。

唯一，异前缀，即时码不等长编码及其定理13• •异前缀码是唯一可译码中的一类子码，易于构造异前缀码是唯一可译码中的一类子码，易于构造 • •异前缀码等价于即时码异前缀码等价于即时码 • •即任何一种唯一可译码都可找到相应、同样有效的异即任何一种唯一可译码都可找到相应、同样有效的异 前缀码不等长编码及其定理树图法是构造树图法是构造 即时码（异前即时码（异前 缀码）的一种缀码）的一种 简单方法简单方法220 221 22210 11 12 20 210一级节点二级节点三级节点 120树根14定理定理4.2 4.2 设信源设信源S S = { = { s s1 1, , s s2 2,…,,…, s sq q} }，，码符号集码符号集X X = { = { x x1 1, , x x2 2,…,,…, x xr r} }，，又设码字为（又设码字为（WW1 1，，WW2 2，，… …，，WWq q），），其分其分 别对应的码长为别对应的码长为l l1 1，，l l2 2，，… …，，l lq q，，则存在唯一可译码则存在唯一可译码 的充要条件为的充要条件为Kraft不等式 定理给出了码字长度的下界的限制。

定理给出了码字长度的下界的限制15例：例： p(ap(ak k) ) 码码A A 码码B B 码码C C 码码D Da a1 1 0.5 0 0 1 10.5 0 0 1 1a a2 2 0.25 11 10 11 01 0.25 11 10 11 01 a a3 3 0.125 00 00 100 0010.125 00 00 100 001a a4 4 0.125 11 01 1010 00010.125 11 01 1010 0001 r r＝＝2 2，码，码A A，码，码B B ：：l l1 1=1, =1, l l2 2= =l l3 3= =l l4 4=2,=2,这样码这样码A A，码，码B B不可能是不可能是唯一可译码唯一可译码。

r r＝＝2 2，码，码C C，码，码D D ：：l l1 1=1, =1, l l2 2=2, =2, l l3 3=3, =3, l l4 4=4,=4,码码C C不是不是唯一可译码，唯一可译码，码码D D是是唯一可译码唯一可译码16信源编码有关概念信源编码有关概念 （（1 1）平均码长）平均码长单位：码符号单位：码符号/ /信源符号信源符号意义：每个源符号平均需要的码符号数意义：每个源符号平均需要的码符号数编码后每个信源符号平均用编码后每个信源符号平均用 个码符号表示个码符号表示 （（2 2）信息传输率（平均每个码符号携带的信息量））信息传输率（平均每个码符号携带的信息量）越短，信息传输率就越高越短，信息传输率就越高 17（（3 3）最佳码（紧致码））最佳码（紧致码）最佳码：对于某一信源和某一码符号集，若有一唯一可最佳码：对于某一信源和某一码符号集，若有一唯一可译码，其平均码长小于所有其他唯一可译码的译码，其平均码长小于所有其他唯一可译码的平均码长，则该码称为最佳码最短唯一可平均码长，则该码称为最佳码最短唯一可译码）译码）无失真信源编码的基本问题就是找到无失真信源编码的基本问题就是找到最佳码最佳码，最，最佳码的平均码长为理论极限。

佳码的平均码长为理论极限理论极限是多少呢？理论极限是多少呢？18定理定理4.34.3（单符号信源的变长编码定理）（单符号信源的变长编码定理） 若有一离散无记忆信源若有一离散无记忆信源S S 具有熵具有熵H H（（S S）），，并。