无失真信源编码与香农第一定理

1、无失真信源编码(1)信源编码信源编码——n次扩展信源到码表的映射(2)码表及其模型码表——n次扩展信源发出消息的码字为不等长的码元序列，码元序列中任何一个码元都随机取值于同一个二进制集合码表的模型——不等长二进制离散型随机变量序列C1C2…Cl~P(C1C2…Cl)=P(X1X2…Xn)不等长二进制随机变量序列C1C2…Cl的取值为信源发出消息的码字i1,i2,…,in=1,2,…,Nk1,k2,…,kl=1,2l21kkkcccn21iiixxxnl21kkknn21iiiN,,2,1k2,1k,,k,kcccN,,2,1iN,,2,1i,,i,ixxxl21n21kic码字次扩展信源发出消息的nx次扩展信源发出的消息n记(3)平均码长与码率码长——n次扩展信源发出消息xi的码字ck的长度，用l(ck)表示，简记为lki,k=1,2,…,Nn（各码字的码长不一定相等）平均码长——对应于各消息码字的码长的数学期望，用L表示nnnN1kkkN1kkkN1kkkkl)x(P)c(l)x(P)c(l)c(P)]c(l[EL码率——对应于各消息中每一个符号码字的平均码长，用R表示，R=L/n编码及码率其二次扩展信源的信源：二进制信源的概率例1.09.0)1(P)0(P)X(P101.009.009.081.0)11(P)10(P)01(P)00(P)X(P2101c11x,100c10x,11c01x,0c00x44332211二次扩展信源的某种信源编码平均码长)bit(29.13)01.009.0(209.0181.0l)x(PL41kkk码率R=L/n=1.29/2=0.645(bit)的信源编码及码率其信源和二次扩展信源：三进制信源的概率例1.02.07.0)2(P)1(P)0(P)X(P2信源的某种信源编码11c2x,10c1x,0c0x332211平均码长)bit(3.12)1.02.0(17.0l)x(PL31kkk码率R=L/n=1.3(bit)01.002.007.002.004.014.007.014.049.0)22(P)21(P)20(P)12(P)11(P)10(P)02(P)01(P)00(P)X(P2二次扩展信源的某种信源编码011001c22x,011000c21x,01101c12x,0111c11x,0101c20x,0100c02x,001c10x,000c01x,1c00x998877665544332211平均码长)bit(33.26)01.002.0(502.04)04.007.02(314.02149.0l)x(PL91kkk码率R=L/n=2.33/2=1.165(bit)问题：n次扩展信源各消息码字的码率，n越大，码率越小——应该小到什么程度？2、香农第一定理离散信源的熵为H(X)，对n次扩展信源进行信源编码，对任意给定的ε0，只要码率R≥H(X)+ε，当n足够大，编码无失真反之，如果码率RH(X)-2ε，无论n多大，编码一定失真正定理的证明当n足够大，n次扩展信源产生接近等概率的典型序列，其数量不超过2n(H(X)+ε)设信源编码的码字数量为2L=2nR只要保证2nR≥2n(H(X)+ε)，即R≥H(X)+ε所有典型序列有对应的码字，其概率之和为译码正确（无失真）的概率1-Pe122222*)xxx(PP1))X(H(n))X(H(n))X(H(nnR)X(A*xxx))X(H(n)X(A*xxxiiienni2i1inni2i1in2100Pe译码错误概率逆定理的证明如果RH(X)-ε)X(A2)1(2)1(1222n))X(H(n))X(H(nn)2)X(H(nnR必然存在部分典型序列没有对应的码字有对应码字的这部分典型序列，其概率之和为译码正确的概率1-Pen))X(H(n)2)X(H(n))X(H(nnR)X(A*xxx))X(H(n)X(A*xxxiiie222222*)xxx(PP1nni2i1inni2i1in21121Pne译码错误概率香农第一定理表明熵H(X)是对应于n次扩展信源无失真信源编码码率R的下界——香农界例3：(1)利用香农第一定理验证例2中对应于信源和二次扩展信源的信源编码无失真(2)找例2中信源的另一种编码，利用香农第一定理验证其失真(1)信源的熵)bit(157.11.0log1.02.0log2.07.0log7.0)x(Plog)x(P)X(H31iii例2中信源的该种信源编码的码率R=1.3(bit)H(X)=1.157(bit)满足香农第一定理，例2中信源的该种信源编码无失真例2中二次扩展信源的该种信源编码的码率R=1.165(bit)H(X)=1.157(bit)满足香农第一定理，例2中二次扩展信源的该种信源编码无失真(2)例2中信源的另一种编码11c2x,1c1x,0c0x332211平均码长)bit(1.121.01)2.07.0(l)x(PL31kkk码率R=L/n=1.1(bit)例2中信源的另一种信源编码的码率R=1.1(bit)H(X)=1.157(bit)不满足香农第一定理，例2中信源的该种信源编码失真