资源描述：
《信息论与编码课件第四章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章离散信源的无失真编码编码器等长编码及其定理不等长编码及其定理第四章作业 教材第116页~117页4.2，4.8(1)(3)编码器S=（s1，s2，…，sq）C=（W1，W2，…，Wq）X=（x1，x2，…，xr）信源符号码字码符号编码器码：特定的符号集合。编码：建立在源符号与码符号或码符号组之间的变换。3547——>011101100111信源编码：从信源输出符号序列到码符号序列的一种映射，其逆映射称译码。信源编码的目的：适合于信道传输，提高输出效率编码器编码器同价码非同价码非奇异码奇异码不等长码等长码信源符号si出现概率pi码A码
2、B码Cs1p10000s2p20101s3p310100s4p4111011等长编码及其定理唯一可译码：一个码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列。akp(ak)码A码Ba10.50000a20.250101a30.1251000a40.1251110等长非奇异码一定是唯一可译码对信源S的N次扩展信源SN进行等长编码若S={s1,s2,…,sq}，则N次扩展信源SN={a1,a2,…,aqN}，共有qN个符号序列。设码符号集为X={x1,x2,…,xr}，长度为l的码符号序列Wi=(xi1xi2…xil),xi1
3、,xi2,…,xil∈X。若要求编得的等长码是唯一可译码则必须满足qN≤rl等长编码及其定理对qN≤rl两边取对数，则得Nlogq≤llogr或例如英文电报有32个符号（26个英文字母加上6个字符），即q=32。若r=2，N=1(即对信源的逐个符号进行二进制编码)，则等长编码及其定理定理4.1（等长信源编码定理）对于上述编码，对于任意，只要N充分大，且满足不等式则译码错误概率任意小（可以进行无失真编码）。反之，若则不可能进行无失真编码，且N充分大时，译码错误概率近似等于1。实现无失真编码存在问题：N充分大使存储和处理难度大。解决办法：采用变
4、长编码。等长信源编码定理的意义：信源的信息熵是（信源冗余度的可压缩性）无失真数据压缩的理论极限。压缩到小于这个极限值，则无失真做不到。等长编码定理不等长编码及其定理不等长编码的基本思想——“量体裁衣”出现概率大的信源符号用较短码字表示，出现概率小的信源符号用较长码字表示。这样平均每个信源符号所需的码符号数降低，提高编码效率。唯一可译码：一个码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列。即时码：唯一可译码，译码时无需参考后续的码符号就能立即作出译码判断。异前缀码：码中没有码字是任意其他码字的前缀。可以在无延时的情况下解码
5、。异前缀码等价于即时码不等长编码及其定理例：p(ak)码A码B码C码Da10.50000a20.250100110a30.125100011110a40.125100101111110码A：奇异，非唯一；码B：非奇异，非唯一；码C：唯一，非异前缀；码D：唯一，异前缀，即时码。不等长编码及其定理异前缀码是唯一可译码中的一类子码，易于构造。异前缀码等价于即时码。即任何一种唯一可译码都可找到相应、同样有效的异前缀码。不等长编码及其定理树图法是构造即时码（异前缀码）的一种简单方法。22022122210111220210一级节点二级节点三级节点12
6、0树根中间节点不能作为码字的终点定理4.2设信源S={s1,s2,…,sq}，码符号集X={x1,x2,…,xr}，又设码字为（W1，W2，…，Wq），其分别对应的码长为l1，l2，…，lq，则存在唯一可译码的充要条件为Kraft不等式定理给出了码字长度的下界的限制。例：p(ak)码A码B码C码Da10.50011a20.2511101101a30.1250000100001a40.125110110100001r＝2，码A，码B：l1=1,l2=l3=l4=2,这样码A，码B不可能是唯一可译码。r＝2，码C，码D：l1=1,l2=2,l3
7、=3,l4=4,码C不是唯一可译码，码D是唯一可译码。信源编码有关概念（1）平均码长单位：码符号/信源符号意义：每个源符号平均需要的码符号数。编码后每个信源符号平均用个码符号表示。（2）信息传输率（平均每个码符号携带的信息量）越短，信息传输率就越高。（3）最佳码（紧致码）最佳码：对于某一信源和某一码符号集，若有一唯一可译码，其平均码长小于等于所有其他唯一可译码的平均码长，则该码称为最佳码。（最短唯一可译码）无失真信源编码的基本问题就是找到最佳码，最佳码的平均码长为理论极限。理论极限是多少呢？定理4.3（单符号信源的变长编码定理）若有一离散无
8、记忆信源S具有熵H（S），并有r个码符号的符号集X={x1,x2,…,xr}，则总可以找到一种无失真编码方法，构成唯一可译码，使其平均码长满足证明：定理4.4（变长无失真信源编码
