信息论与编码基础一、香农第一定理香农三大定理简介二、香农第二定理三、香农第三定理信息论与编码基础一、香农第一定理二、香农第二定理三、香农第三定理香农三大定理简介信息论与编码基础1、信源编码器、a、模型S:s∈{a1,...,aq}香农三大定理简介编码器C:c∈{W1,...,Wq}Wi={xi1,xi2...,xili}码字码长X:x∈{x1,...,xr}码符号单符号信源无失真编码器信息论与编码基础1、信源编码器、a、模型SN=(S1,...,SN)香农三大定理简介Wi={xi1,xi2...,xili}编码器Si∈{a1,...,aq}i=1,2,...,NX:x∈{x1,...,xr}i=1,2,...,qNN次扩展信源无失真编码器信息论与编码基础1、信源编码器、b、举例1）ASCII信源编码器香农三大定理简介{英文字母/符号/命令}二进代码ASCII编码器编码器码符号集{0，1}信息论与编码基础1、信源编码器、符号点划b、举例b、举例二进代码字母间隔―――000香农三大定理简介单词间隔――――――00000022）摩尔斯信源编码器101110+―+++电平2）摩尔斯电码―{A,B,…,Z}二进符号信源编码器I信源编码器码符号集{点/划/字母间隔/单词间隔}信源编码器II信源编码器码符号集{0，1}信息论与编码基础1、信源编码器、b、举例33）中文电报信源编码器“中”“0022”香农三大定理简介“01101011011100111001”信息论与编码基础1、信源编码器、c、分类等长码中文电报变长码莫尔斯电码惟一可译码有失真编码无失真编码香农三大定理简介I(S;C)<H(S)I(S;C)=H(S)若某一种码的任意一串有限长的符号序列只能被惟一地译成所对应的信源符号。非惟一可译码被惟一地译成所对应的信源符号。非惟一可译码信息论与编码基础1、信源编码器、d、指标1)平均码长香农三大定理简介L=∑P(si)lii=1qcode/signrLN=∑P(si)λii=1qNcode/N-sign信息论与编码基础1、信源编码器、d、指标2)编码后的信息传输率香农三大定理简介R=H(S)/Lbit/codebit/codeH(S)RN=LN/N信息论与编码基础1、信源编码器、d、指标3)编码效率实际编码的信息传输率η=最大编码的信息传输率香农三大定理简介H(S)=LNlogrN信息论与编码基础例：二元DMS进行无失真编码二元进行无失真编码?s1?S???P(s)?=?3???4s2??1?4?香农三大定理简介H(S)=H(3/4,1/4)=0.811(bit/sign)N=1L1=1(code/sign)H(S)R1==0.811(bit/code)L1H(S)η1==0.811L1?log2信息论与编码基础例：二元DMS进行无失真编码二元进行无失真编码?s1?S???P(s)?=?3???4s2??1?4?香农三大定理简介H(S)=H(3/4,1/4)=0.811(bit/sign){0,10,110,111}N=2L2=1.688(code/2-sign)H(S)R2==0.961(bit/code)L2/2H(S)η2==0.961L2/2?log2信息论与编码基础例：二元DMS进行无失真编码二元进行无失真编码香农三大定理简介?s1s2??S??=31??P(s)??????44?随着N的增加平均码长减小，有效性逐步提高；的增加，随着的增加，平均码长减小，有效性逐步提高；H(S)=H(3/4,1/4)趋于无穷时，=0.811(bit/sign)当N趋于无穷时，平均码长可以无限制地减小吗？趋于无穷时平均码长可以无限制地减小吗？N=3N=4H(S)R3==0.985(bit/code)R4=0.991(bit/code)L3/3H(S)η3==0.985η4=0.991L3/3?log2信息论与编码基础香农三大定理简介2、香农第一定理（可变长无失真信源编码定理）、香农第一定理（）设SN={α1,α2,...,αqN}定理4.1定理为q元离散无记忆信源S的N次扩展信源，若对SN进行编码，码符号集{x1,x2,...,xr}=X，则总可以找到一种编码方法构成惟一可译码，使信源S中每个符号所需的平均编码长度满足：H(S)1LNH(S)+>≥logrNNlogr