信息论与编码教案.doc

2.3连续信源熵上一章我们讨论的为离散信源，实际应用中还有一类信源称为连续信源，这种信源的时间和取值都是连续的，例如语音信号，电视信号都是连续信号。 时间离散状态连续的信源熵可以用连续信源熵表示，相当于一个连续随机变量。而时间连续的信源，为一个随机过程，只要信号频谱有限，则可以根据采样定理，将其变为时间离散信源。 信息论中只讨论单变量连续信源，即时间离散状态连续的连续信源。1连续信源的熵1-1连续信源熵的定义 连续信源的状态概率用概率密度来表示。如果连续随机变量X，取值为实数域R，其概率密度函数为p(x)，则如果取值为有限实数域a,b，则这是X的概率分布函数为： 连续信源的数学模型X: R(或a,b) P(X): p(x) 连续信源熵的表达式利用离散信源熵的概念来定义连续信源熵，首先看一个再a,b取间的连续随机变量，如图： p(x) p(xi) a 0 xi b x首先把X的取值区间a,b分割为n个小区间，小区间宽度为： =(b-a)/n根据概率分布为概率密度函数曲线的区间面积的关系，X取值为xi的概率为：Pi=p(xi).这样可以得到离散信源Xn的信源空间为：Xn,P:Xn:x1x2xnP(Xn):p(x1)p(x2)p(xn)且有：当n趋无穷时，按离散信源熵的定义：可得离散信源Xn的熵：当趋于0，n趋于无穷时，离散随机变量Xn将接近于连续随机变量X，这时可以得到连续信源的熵为：其中：连续信源的熵定义为： 连续信源熵为一个相对熵，其值为绝对熵减去一个无穷大量。 连续信源有无穷多个状态，因此根据SHANNON熵的定义必然为无穷大。 连续信源的熵不等于一个消息状态具有的平均信息量。其熵是有限的，而信息量是无限的。 连续信源熵不具有非负性，可以为负值。尽管连续信源的绝对熵为一个无穷大量，但信息论的主要问题是信息传输问题，连续信道的输入输出都是连续变量，当分析其交互信息量时是求两个熵的差，当采用相同的量化过程时，两个无穷大量将被抵消，不影响分析。连续信源的疑义度：则平均交互信息量为： I(X,Y)=H(X)-H(X/Y)1-2 几种连续信源的熵(1) 均匀分布的连续信源熵设一维连续随机变量X的取值区间是a,b，在a,b中的概率密度函数是这种连续信源称为均匀分布的连续信源。其熵为：这时可以看到：当(b-a)1时，H(X)0，即H(X)不具有熵函数的非负性，因为H(X)是相对熵，相对熵可以为负值，但绝对熵仍然为正值。(2) 高斯分布的连续信源熵设一维随机变量X的取值范围是整个实数R，概率密度函数为：其中，m是随机变量X的均值2是随机变量X的方差当均值m=0时，方差2就是随机变量的平均功率，这个信源称为高斯分布的连续信源，其数学模型为：这时可以得到高斯连续信源的熵为：这里的对数是以e为底。当均值为0时，高斯信源的熵为(3) 指数分布的连续信源熵设一随机变量X的取值取间为0，其概率密度函数为则称为指数分布的连续信源。其中常数a为随机变量X的均值。即指数分布的连续信源的熵为2 连续信源的最大熵2-1 连续信源的最大熵为了求出连续信源的最大熵，将利用数学中的变分法的方法来求解。连续信源的熵为：其基本约束条件为：其它约束条件为：建立辅助函数：其中有：根据极值的条件有：及m个约束方程，可以确定最大熵和所对应的信源概率密度分布p(x)。下面讨论两种基本信源。（1） 输出幅度受限时的最大熵（瞬时功率受限）其基本条件为：|x|v，x2S，这时对应只有一个约束方程，并且：可以得到：这里的对数为以e为底，由约束方程可得：结论：对于瞬时功率受限的连续信源，在假定信源状态为独立时，当概率密度分布为常数时，信源具有最大熵。其最大熵为：（2） 输出平均功率受限时的最大熵推导：这时的约束条件为：可知：由极值条件：可得：logp(x)=1+2x2-1 p(x)=e1-1e2x2将其代入约束条件1，可得：利用积分公式：可得：由：利用积分关系：可得：代入前面的结果：得到：得到连续信源获得最大熵时的概率密度函数：这是一个均值为0的高斯分布。其最大熵为其中利用两个积分关系：如果平均功率为N=2; 则有结论：（最大熵定理）对于输出平均功率受限的连续信源，在假设状态相互独立时，当其概率密度函数为高斯分布时，具有最大熵。其最大熵值随功率N的增加而增加。2-2连续信源的熵功率 对于平均功率受限的连续信源，当信源为高斯分布时有最大熵，如果概率分布不是高斯分布，则信源熵将小于最大熵。熵功率则用来描述连续信源熵的剩余度。 一个平均功率为N的非高斯分布的连续信源的熵功率等于与其有同样熵的高斯信源的平均功率。 当非高斯连续信源与高斯信源具有相同熵时，那非高斯信源的平均功率一定大于高斯信源的功率。 当非高斯连续信源与高斯信源具有相同平均功率时，那非高斯信源的熵一定小于高斯信源的熵。平均功率为N的非高斯信源的熵功率为2-3 连续信源的共熵和条件熵同离散信源相似，连续信源也可定义其共熵和条件熵，其基本关系为： H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X/Y) H(X,Y)H(X)+H(Y) H(X/Y)H(X) H(Y/X)H(Y)2.4 平稳随机序列信源熵前面讨论的是单符号离散信源和单符号离散信道的信息特性。这一节开始讨论随机矢量或随机序列信源的情况。通常这种信源是很复杂的，通常要进行简化分析。X=X1，X2，X3， 为平稳随机序列，即统计特性不随时间改变； 随机序列为有限等长度，每个信源消息由N个符号序列组成，1 离散无记忆信源的扩展信源A.假设条件这里对离散平稳随机序列信源做进一步假设。(1) 我们假设多符号离散平稳信源X=X1，X2，XN中，符号的随机变量Xi都取值于同一个信源空间，Xi,P=x1x2x3xnp(x1)p(x2)p(x3)p(xn)(2) 我们假设多符号离散平稳信源X=X1，X2，XN中，各变量Xi(i=1,2,N)之间统计独立，即P(X)=P(X1,X2,XN)=P(X1)P(X2)P(X3)P(N)到目前为止，我们介绍的离散无记忆信源包括两层意思： 单符号离散无记忆信源，p(x1,x2,xn)=p(x1)p(x2)p(xn) 多符号离散无记忆信源，P(X1,X2,XN)= P(X1)P(X2)P(X3)P(N)在这种假设前提下，可以把多符号离散平稳信源看作单符号离散平稳信源的N次扩展信源。通常N次扩展信源，记为XN。B. N次扩展信源的信源空间因为信源XN的每一个消息Xi=Xi1,Xi2,XiN均由信源X的符号集X:x1,x2,xn中的N个符号组成，所以，XN 的某一个具体符号Xi可以表示为Xi=(xi1,xi2,xiN)xijX:x1,x2,xn，这个关系表明扩展信源的每个符号取值于同一个单符号信源空间，X: x1,x2,xn。因此扩展信源XN 就有rN 种不同的符号，可以表示为XN : X1,X2,Xi,XnN; (i=1,2, nN) 例如n=2, N=2, X=X1,X2 XN : X1,X2,X3,X4 X:x1=0,x2=1 X1=00; X2=01; X3=10; X4=11;所以平稳离散无记忆信源X，P的N次扩展信源的信源空间为：XN,P:XNX1X2XnNP(XN)p(X1)p(X2)p(XnN)并且有： 表明该信源概率空间也是一个完备空间。C. N次扩展信源的熵根据熵函数的定义：利用p(Xi)=p(xi1,xi2,xiN)的关系和p(xi1,xi2,xiN)=p(xi1)p(xi2)p(xiN)无记忆信源，可以得到： 再考虑到无记忆信源，H(X1)=H(X2)=H(XN)，可以得到：H(XN)=N.H(X)多符号平稳离散无记忆信源的N次扩展信源是一种最简单的多符号信源。如果多符号平稳离散无记忆信源X=X1,X2,XN中的各变量Xi取值于不同的单符号离散无记忆信源Xi,P。Xi,P:Xixi1xi2xinP(Xi)p(xi1)p(xi2)p(xin)(i=1,2, N)这种信源称为多符号离散无记忆信源，可以证明这种信源的熵为：其中H(Xi)为单符号离散信源Xi,P的熵。2 二维离散平稳有记忆信源的信源熵这里介绍最简单的离散平稳有记忆信源，即二维信源。X=X1，X2所谓有记忆信源就是一种相关信源，每个消息由两个符号组成，后一个符号与前一个符号有一个概率表明相关性，（这是一种近似处理方法，只考虑消息组内的相关性）。设离散平稳信源的信源空间为：X,P=x1x2x3xnp(x1)p(x2)p(x3)p(xn)且有p(xi)=1，同时有一维条件概率为“PX2=xj/X1=xi=PX2+T=xj/X1+T=xi=p(xj/xi) ，表明为平稳序列。(i=1,2,n; j=1,2,n)X=X1，X2 的符号集中的一个Xi=(xi1,xi2) xi1,xi2X:x1,x2,xn; i1,i2=1,2,ni=1,2,3,n2且有：p(Xi)=p(xi1,xi2)=p(xi1)p(xi2/xi1)这时可得二维信源X=X1,X2的信源空间： X,P=X1X2X3Xn2p(X1)p(X2)p(X3)p(Xn2)即信源空间为完备空间。可得二维信源的一个消息（两个符号）所提供的平均信息量为： 其中：H(X1)表示信源发出第一个符号所能提供的平均信息量，H(X2/X1)表示在第一个符号已知的前提下，第二个符号所提供的平均信息量。 二维离散平稳有记忆信源每发一个消息所能提供的平均信息量是一种联合熵，这种信源的熵等于第一个随机变量的熵加上第一变量已知的条件下第二个变量的条件熵。其中： 当随机变量X1X2相互独立时，有H(X)=H(X1,X2)=H(X1)+H(X2)。可以证明：二维离散平稳有记忆信源的熵满足：H(X1,X2)H(X1)+H(X2)，（作业）例2-15 设某二维离散信源的原始信源的信源空间X=x1,x2,x3; P(X)=1/4, 1/4, 1/2, 一维条件概率PX2=xi/X1=xj为：p(x1/x1)=1/2; p(x2/x1)=1/2; p(x3/x1)=0;p(x1/x2)=1/8; p(x2/x2)=3/4; p(x3/x2)=1/8;p(x1/x3)=0; p(x2/x3)=1/4; p(x3/x3)=3/4;原始信源的熵为：H(X)=1.5 bit/符号条件熵：H(X2/X1)=1.4 bit/符号可见：H(X2/X1)1 ，对于一切ij=1,2,n 都有pij(n0)0 （矩阵P中的所有元素）对于每个 j=1,2,.,n都存在不依赖i的极限（每个状态都以一定的概率出现）则称这个马氏链是各态历经的。其中的极限概率pj=p1,p2,pn是方程组 满足条件 的唯一解。为：Pj=P1,P2,Pn; PjT=P(1)T.PjT马氏链的各态历经定理说明： 只有在转移了一定步数后各状态之间可相通的条件下，当转移步数足够大时，处于某一状态的概率才能稳定在某一极限值； 各状态相通，均可经历； 每个由各状态经历过程产生的序列都有同样的统计特性，即统计均匀性；例2: 设一个马氏链有三个状态，X:0,1,2,其一步转移概率为：P(1)=ij012=0120p00p01p020qp01p10p11p121q0p2p20p21p2220qp这时pij0不满足，不能判断是否具有各态历经性，看二步转移矩阵。P(2)=P(1)P(1)=0120q2+pqqpp21q22qpp22q2qpqp+p2这时pij0满足，可以判断具有各态历经性，其状态极限概率（稳态概率）可以由方程得到：p0qq0p0p0=qp0+qp1 由这四个方程求解p1=pp0+qp2p2=pp1+pp2; p0+p1+p2=1p1=p0qp1p20ppp2由一步状态转移矩阵求极限概率的基本关系为：PT=P(1)T.PT T表示矩阵的转置。(3) 状态转移图有限齐次马氏链除了用转移矩阵描述外还可以用状态转移图来表示。例如上面的例题对应的状态图为： q p q 0 1 2 p p q 齐次马氏链为一个不可约闭集，即对马氏链中的任意两个状态，总可以从一个状态经过有限步数转移到另一个状态； 齐次马氏链具有非周期性，从一个状态到另一个状态的步数不能具有周期性；(4) 马尔柯夫信源 m阶马尔可夫信源：如果一个离散平稳有记忆信源X=X1，X2，,Xm,Xm+1,Xm+2,中，任一时刻(m+1)的随机变量Xm+1只依赖于它前面的m个随机变量，与更前面的变量无关，称为记忆长度为m的离散平稳有记忆信源，也称为m 阶马尔柯夫信源。这时把(X1,X2,Xm)某一个取值Si=(xk1,xk2,xkm) 称为一个状态。xkjX:x1,x2,xn为原始信源状态空间; kj=1,2,n j=1,2,.mi=1,2,nm 马尔柯夫信源状态：同时把随机变量(X2,X3,Xm+1)的某一取值Sj称为另一个状态，Si为Sj的前一状态。m 阶马尔柯夫信源的状态空间为S:S1,S2,Srm，马尔柯夫信源的一个状态由m个符号组成，当信源再输出一个符号时，信源变为另一个状态，所以从Si到Sj的一步转移概率为：p(Sj/Si)=p(xkm+1/xk1xk2xkm) 为一个条件概率；其中：(k1,k2,km=1,2,n; km+1=1,2,n)(i,j=1,2,.nm) m 阶马尔柯夫信源空间：X: x1 x2 xnP: p(xkm+1/xk1 xk2 xkm)且有： m 阶马尔柯夫信源的极限熵：根据 m 阶马尔柯夫信源的定义，及平稳性，有： p(xkN/xk1 xk2 xkm xkm+1,xkN-1)=p(xkN/xkN-m xkN-m+1,xkN-1) =p(xkm+1/xk1 xk2 .xkm), 这样，可以得到m 阶马尔柯夫信源的极限熵： =H(Xm+1/X1X2Xm)这表明，m 阶马尔柯夫信源的极限熵就等于m阶条件熵，记为：Hm+1。 用状态转移概率表示极限熵：p(Sj/Si)=p(xk/Si)=p(xkm+1/xk1xk2xkm) 或p(xk+1/Si)这时极限熵可以表示为：从以上分析可以看到，m 阶马尔柯夫信源的分析是实际信源的一种简化，把一个无限的问题转化为有限量的计算问题。已知m 阶马尔柯夫信源的状态一步转移概率后，求极限熵的问题就在于得到概率p(Si)，(i=1,2, nm)，而p(Si)就是马尔柯夫信源在稳定状态时的各状态的极限概率。所以，首先要判断信源是否具有各态历经性，如果有，则可以有一步转移概率求出极限概率。例3: 一个二进制二阶马尔柯夫信源的原始信源为X：0，1，m=2，这时的状态空间为：S: S1=00, S2=01, S3=10, S4=11，共有nm=22=4个不同的状态。已知其一步转移概率为：0/0000p(0/00)p(0/S1)p(S1/S1)=0.81/0001p(1/00)p(1/S1)p(S2/S1)=0.20/0110p(0/01)p(0/S2)p(S3/S2)=0.51/0111p(1/01)p(1/S2)p(S4/S2)=0.50/1000p(0/10)p(0/S3)p(S1/S3)=0.51/1001p(1/10)p(1/S3)p(S2/S3)=0.50/1110p(0/11)p(0/S4)p(S3/S4)=0.21/1111p(1/11)p(1/S4)p(S4/S4)=0.8信源空间S:S1,S2,S3,S4 p(Sj/Si) (i=1,2,3,4)可得到信源状态转移图为： 0.8 S1 0.2 0.5 0.5 S2 S3 0.5 0.5 0.2 S4 0.8由状态图可以判断，这是一个非周期不可闭集，具有各态历经性，存在状态极限概率。有：p(S1)=0.800.50p(S1)p(S2)0.200.50p(S2)p(S3)00.500.5p(S3)p(S4)00.500.5p(S4)其约束条件为：p(S1)+p(S2)+p(S3)+p(S4)=1p(Si)1 (i=1,2,3,4) 解得其极限概率分别为：p(S1)=p(S4)=5/14; p(S2)=p(S3)=2/14由极限概率和状态转移概率就可以计算马尔柯夫信源的极限熵： = 0.8 bit/符号另外，还有的离散有记忆信源即马尔柯夫信源是已知极限概率和转移概率，求信源熵的。注意：马尔柯夫信源的熵就是其极限熵，也就是一个条件熵。例4: 一个一阶马尔柯夫信源的原始信源为X:x1,x2,x3，已知其先验概率和一步转移概率，求其极限熵。p(x1)=11/36; p(x2)=4/9; p(x3)=1/4;P(1)=9/112/1101/83/41/802/97/9其状态图如图示：可得原始信源熵和极限熵为：H(X)=1.542 bit/符号 H1+1=H(j/i)=H(Xj/Xi)=0.89 bit/符号。也可以用各态历经的验证方法：P(2)=9/112/1109/112/1101/83/41/81/83/41/802/97/902/97/9可知：P(2)中pij0，其极限概率存在。p(x1)9/111/80p(x1)p(x2)=2/113/42/9p(x2)p(x3)01/87/9p(x3)可得：p(x1)=(9/11)p(x1)+(1/8)p(x2) p(x2)=(2/11)p(x1)+(3/4)p(x2)+(2/9)p(x3) p(x3)=(1/8)p(x2)+(7/9)p(x3)在考虑:p(x1)+p(x2)+p(x3)=1可以得出：p(x1)=11/36; p(x2)=4/9; p(x3)=1/4;2.5信源的冗余度(1) 关于离散信源熵的总结： 实际信源非平稳的有记忆随机序列信源；其极限熵是不存在的； 解决的方法是假设其为离散平稳随机序列信源，极限熵存在，但求解困难； 进一步假设其为m阶Markov信源，用其极限熵Hm+1近似； 再进一步假设为一阶Markov信源，用其极限熵H1+1(X2/X1) 来近似； 最简化的信源是离散无记忆信源，其熵为H(x)=H1+1(X); 最后可以假定为等概的离散无记忆信源，其熵为H0(X)=logn；它们之间的关系可以表示为：logn=H0(X)H1(X)H1+1(X)H2+1(X)Hm+1(X)H可见离散有记忆信源的记忆长度越长，信源熵越小，而独立且等概的信源，熵最大。(2) 冗余度：用来衡量由于信源内部的消息状态的相关性和分布性，使其熵减少的程度称为冗余度。 相对熵：= H/H0=(实际信源熵)/(离散信源最大熵) =H(X)/Hmax(X) 内熵(信息熵差)：= H0- H（最大熵）-（实际信源熵） =H(X)-Hmax(X) 冗余度：例上面的例题中其冗余度为：E=1-(0.89/log3)=43.8% 说明信源X有43%的剩余，只有57%是纯信息。例英文字母信源：H0=log27=4.76 bit (等概)H1=4.02 bit （不等概）H1+1=3.32 bit （一阶M-信源）H2+1=3.1 bit （二阶M-信源）H=1.4 bit 6、 本章小结1) 信息是可以定量描述的，可以比较大小。由概率决定；2) 对应特定信源，可以求出所含不确定度，也就是消除不确定度所需的信息量；3) 可通过对信源的观察、测量获得信息，以减少对信源的不确定度；4) 考虑信源符号概率分布和符号之间的相关性，信源不确定度会下降； 5) H(X)就是信源无失真时必需输出的最小信息量；6) 通过传输，信宿可以得到信息I(X;Y)，从而减小对信源的不确定度：H(X/Y)=H(X)-I(X;Y)7) 信息通过系统传输，只会丢失信息，不会增加。丢失部分H(X/Y)是由噪声引起的；8) 弄清自信息量、信源熵、相对熵；互信息、条件熵、联合熵，序列熵、平均符号熵、极限熵冗余度的定义、计算公式、相互关系。7、 教学反思第3章 无失真信源编码1、 教学目标：1、 理解信源编码的意义和分类，了解信源编码基础知识。2、 掌握定长编码和变长编码的特点。3、 掌握香农编码、费诺编码、哈夫曼编码的编码思想和编码方法。2、 教学重点与难点：重点：变长编码定理结论的应用难点：变长编码定理的证明3、 计划课时：4、 教学方法：5、 教学内容：通信的根本目的就是有效而可靠地传输信息。Shannon信息论中的一个重要内容就是它给出了信息传输的有效性和可靠性的极限能力。具体表现为两个编码定理；一般称为Shannon第一编码定理（信源编码定理，有效性编码定理）和Shannon第二编码定理（信道编码定理，抗干扰编码定理）。3-1-1 编码器(Encoder)我们前面考虑的信源都是离散化的信源，实际上没有考虑到编码的问题。编码的作用可以分为以下编两点： 一些原始信源的符号不适应信道的传输； 原始信源符号的传输效率很低；码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为S:s1,s2,sn；si(i=1,2,n)；而信道所能传输的符号集为A:a1,a2,aq；编码器的功能是用符号集A中的元素，将原始信源的符号si变换为相应的码字符号Wi，(i=1,2,n)，所以编码器输出端的符号集为W:W1,W2,Wn。S=原始信源符号集；A=码元符号集；W=码字符号集；（码组）编码器 S:s1,s2,sn W:W1,W2,Wn A:a1,a2,aqWi=w1,w2,wLi wia1,a2,aqLi为码字Wi的码元个数，称为码字Wi的码字长度，简称码长。q=2时，称为二元编码，否则称为q元编码。3-1-2 单义可译码(Uniquely decodable code)(1) 单义可译码定义：如果一个码组的任一有限长的码字序列（一串码字），只能唯一地被译成一个一个码字，则称为单义可译码，也称为异前置码。例如：S: s1,s2,s3; A:0,1; W: w1=0, w2=10, w3=11, 为单义可译码。当接收码字序列为：10011001111 时，可以唯一地译为：w2,w1,w3,w1,w1,w3,w3;如果码字集合为：W:0,01,11 则为非单义可译码。当接收码字序列为：10011001111 时，可以译为：x,w1,w1(w2)(2) 瞬时可译码（非续长码）定义：如果一个码组中的任一个码字都不是另一个码字的续长，或者说，任何一个码字后加上若干码元后都不是码组中另一个码字。则称为瞬时可译码，也称为非续长码。例如：W：0，10，100，111不是瞬时可译码，100为10的续长。 瞬时可译码一定是单义的，单义可译码却不一定是瞬时可译码。例如：W：0，01是单义的，但不是瞬时可译码。(3) 单义可译码定理：设原始信源符号集为S:s1,s2,sn，码元符号集为A:a1,a2,aq，码字集合为W:W1,W2,Wn，其码长分别为L1,L2,Ln；则单义可译码存在的充要条件为码长组合满足Kraft不等式，即 Kraft不等式不仅是单义可译码的充要条件，也是瞬时可译码的充要条件； 这里所说的充要条件是对于码长组合而言，而不是对于码字本身而言，就是说：满足Kraft不等式的码长组合一定能构成单义码，单义码的码长组合一定满足Kraft不等式。 有些码字的码长组合满足Kraft不等式，但不是单义码。（编码方法不对）下面看一个例子：n=4, q=2 A:0,1信源符号W1W2W3W4W5W6s10000000s2011011101001s30111101001101110s40111111011011111011 W1:满足Kraft不等式，但只是单义的，不是瞬时可译码；码长组合为1,2,3,4； W2:满足Kraft不等式，是单义的，也是瞬时可译码；码长组合为1,2,3,4； W3:满足Kraft不等式，不是单义的，也不是瞬时可译码；码长组合为1,2,3,3； W4:满足Kraft不等式，是单义的，也是瞬时可译码；码长组合为1,2,3,3； W5:不满足Kraft不等式，不可能为单义的；码长组合为1,2,2,3； W6:满足Kraft不等式，是单义的，也是瞬时可译码；为等长码；(4) 用码树图构成瞬时可译码 从根开始，画出q条分支，任选一个分支作为W1； 在另一个分支上再分出q条分支，任选一个分支作为W2； 继续进行，直至结束； 从根到各端点，所经过的状态即为码字；例如：A:0,1, q=2, W:W1,W2,W3,W4 根 根 0 1 1 0 W1 0 1 W1 1 0 W2 W2 0 1 1 0 W3 W4 W3 W4 这种方法构成的瞬时可译码是不唯一的； 码树图可以用于译码，有根，枝，节点等概念； 同样可以用于q元编码；例：S:s1,s2,s9,A=0,1,2, q=3 0 2 W1 1 2 2 W9 0 0 1 0 1 W2 1 2 W5 W6 W8 W3 W4 W7W1=0; W5=20; W9=222;W2=10; W6=21;W3=11; W7=220;W4=12; W8=221;3-1-3 平均码子长度如果一个码组的参数满足Kraft不等式，就一定可以构成无噪声信道下的无失真传输，然而，在一个通信系统中，信源编码的主要目的是提高编码效率，即每个码元符号要携带更多的信息量。因此要定义平均码长的概念。设原始信源的信源空间为S,P=s1s2snp(s1)p(s2)p(sn)其中：对此信源用码元符号集A;a1,a2,aq进行编码，得单义可译码W：W1，W2，Wn。相应得码字长度分别为：Li,(i=1,2,n)。则这个信源编码的平均码长为：这时看一下信息传输效率：每个信道码元所携带的平均信息量。当信源S给定，信源的熵为H(S)，则每个信道码元所携带的平均信息量可以表示为可见，当原始信源一定时，编码后的平均码长越小，信道传信率越高，编码效率越高。 编码效率可以用平均码长来描述； 每个码字的长度应当与对应的信源符号的先验概率有关。为了提高编码效率，总希望平均码长越小越好，但平均码长能否无限小呢？定理: 平均码长极限定理若一个离散无记忆信源S的熵为H(S)，对其进行q元编码，A:a1,a2,aq，则总可以找到一种无失真的编码方法，构成单义可译码，使其平均码长满足：对于常用的二元编码来说： H(S)LH(S)+1 下界证明根据平均码长和熵的定义有 由单义可译码的存在定理可知，当满足q-Li1时，取对数后为小于等于0。则有： H(S)-Llogq0 LH(S)/logq下界证毕。 平均码长最小不能小于极限值，H(S)/logq，若小于，则不存在单义可译码； 当下界等号成立时，效率最高时，为p(si)=q-Li可得：当然这要求信源符号的先验概率满足其是以q为底的对数为整数，这就要求信源符号的先验概率为p(si)=q-Li形式，如果满足这一条件，编出的码字称为最佳码。例如：S:s1,s2,s3,s4; P(S):1/2,1/4,1/8,1/8时，编码后码长为1,2,3,3，这时平均码长将为L=H(S)=1.74 码元/符号。上界证明我们考察在满足Kraft不等式的条件下，平均码长满足下界。设每个码字的平均码长在以下区间取正整数。考虑到对数为单调递增函数，则有：进而有： 对上式的i连续取和：即：这表明这样选择每个码元的码长可以满足Kraft不等式，然后对所有的i相加，得:即上界证毕。 平均码长大于这个上界当然也可以构成单义可译码，但实际上总希望码长小； 当一个离散无记忆信源得统计特性确定后，信源熵就确定了，平均编码长度下界也就确定了，编码效率也就确定了，如果进一步提高效率，就要想其它方法。下面得编码定理给出了方法。3.2编码定理以下是Shannon编码定理的三种形式。它们是进一步提高编码效率的极限定理。 定理一：离散无记忆信源S的N次扩展信源SN，其熵为H(SN)，并且编码器的码元符号集为A:a1,a2,aq，对信源SN进行编码，总可以找到一种编码方法，构成单义可译码，使信源S中每个符号si所需要的平均码长满足：说明： H(SN)=NH(S)，根据平均码长的界限定理有：LN为N次扩展信源每个符号的平均码长，原始信源的每符号的平均码长则为则上式可以变为：即得： 当离散无记忆信源S的扩展次数N足够大时，有 定理一表明当将离散无记忆信源进行N次扩展后再进行编码，就可以使原始信源每个符号的平均码长接近信源熵H(S)，即达到下限值。 这时就不要求原始信源的先验概率满足特殊条件了，但却要求扩展次数N趋于无穷。因此，这也是一个极限定理，（给出一种不现实的方法）。 定理二：离散平稳各态历经有记忆信源S的N次扩展信源S=S1,S2,SN，其熵为H(S)= H(S1,S2,SN)，并且编码器的码元符号集为A:a1,a2,aq，对信源S进行编码，总可以找到一种编码方法，构成单义可译码，使信源S中每个符号所需要的平均码长满足：已知N次扩展信源的熵为H(S)=H(S1,S2,SN)，根据平均的界限定理，将上式除以N得：可以注意到：对于平稳各态历经有记忆信源来说，当信源稳定后，即当N趋于无穷时，每发一个符号携带的平均信息量等于其极限熵。又考虑到lim(1/N)=0，可知： 比较定理一和定理二，由于H(S)H，所以，有记忆信源的平均码长的下界将小于无记忆信源的平均码长的下界； 对于m阶马尔柯夫信源来说；H=Hm+1(S)，则有：即，记忆长度越长，平均码长的下界就越小。 定理一和定理二说明：可以用信源扩展的方法，达到数据压缩的目的，扩展程度越高，编码效率越高。定理三：设信源S的熵为H(S)，无噪声离散信道的信道容量为C。则总可以找到一种编码方法，使信道上的信源符号平均传输速率为C/H(S)-。其中可以是任意小的正数。要使符号平均传输速率大于C/H(S)是不可能的。关于编码定理的说明： 在编码前，离散无噪声信道的信道容量为C，C=r0Hmax(S)，Hmax(S)为信源的最大熵，r为符号传输速率，C=Hmax(S)，相当于r0=1。 在编码前，离散无噪声信道的实际熵速率为R=r0H(S)，这时的符号传输速率就等于r0，单位是原始信源符号数/每秒。 这时的传输效率（编码效率）：实际传输能力/最大传输能力，为： =R/C=H(S)/Hmax(S)对于n个符号的原始信源，如果不进行编码就相当于n元编码，其最大熵为Hmax(S)=logn; 传输效率（编码效率）=R/C=H(S)/Hmax(S)=H(S)/logn。 编码后，每个原始信源符号si编成了Li个信道码元组成的码字Wi。编码器的输出可以看成一个新的信源，它有q个信源符号（信道码元），每个信道码元所携带的信息量为H(S)/L。如果将这个新信源记为A，则H(A)=H(S)/L，如果信道码元的符号速率为n1，则信道的实际熵速率为R=r1H(A)=r1H(S)/L。 编码器输出的码元符号集共有q个元素，这个新信源的最大熵为当q个信道码元符号为等概率时，即Hmax(A)=logq，信道容量为C=r1Hmax(A)。 这时编码器输出端的传输效率（编码效率）为： =R/C=H(A)/Hmax(A)=H(S)/LHmax(A)=H(S)/Llogq 当q=2时，为二元编码，logq=1; 传输效率就为：=R/C=H(S)/L。 这时从另一个角度，我们看一下编码定理中定义的符号传输速率，它是指原始信源符号的传输速率：即每秒传输的原始信源符号的个数。 实际符号传输速率为：为r0=R/H(S) (比特/秒)/(比特/符号)=(信源符号/秒) 有：r0=R/H(S)C/H(S);编码定理指出：总可以有方法使R趋进于C，并构成单义可译码，实际上等效于：L趋于H(S)/logq 。或者说：编码后的编码效率趋于1。 由平均码长界限定理可知，要构成单义可以码，平均码长有一个下界： 结合这两个关系，可以得到：单义可译码的信道码元符号在离散无噪声信道上的熵速率（传信率）就相应有一个上界； 我们知道logq是信道码元符号集A:a1,a2,aq的最大熵，也就是将A看作信源时，在离散无噪声信道上的信道容量C，所以有： RC 这就是说，要编成单义可译码，就不可能使信道传信率（熵速率）大于信道容量。关于Shannon编码第一定理：定理一、定理二和定理三实际上是同一个定理，定理一和定理二是针对一个具体的信源形式，而定理三是一个概括性的。这个定理称为无失真信源编码定理，也称为无噪声信道编码定理。例4-1：有一个离散无记忆信源，S:s1,s2, P(S):0.2, 0.8, 其原始信源熵为：H(S)=1/5log5+4/5log(5/4)=0.72193 bit/信源符号(s