1、1第一章无损信源编码 块码，序列码，通用码。1.信息熵和信源编码定理 2.赫夫曼编码 3.游程编码 4.冗余位编码 2信息熵和信源编码定理（1）1.信息熵计算公式 x0,x1.xr xA=a1,a2am H0=log2 m bit H1=-p(x)log p(x)H2=-p(x0)P(x1|x0)log P(x1|x0).Hk+1=-p(x0,x1.xk-1)P(xk|x0,x1.xk-1)log P(xk|x0,x1.xk-1)3信息熵和信源编码定理（2）H0H1.Hk.H(x0,x1.xk-1)=-p(x0,x1.xk-1)logp(x0,x1.xk-1)极限熵 H=Lim Hk=Lim
2、H(x0,x1.xk-1)/k k 无限2.等长码的编码定理 码字同样长有利于传输 典型序列ar出现Spr次.4信息熵和信源编码定理(3)当S趋于无限，非典型序列出现的概率趋 于零。可只编这些序列，差错接近零。典型序列个数是 N=S!/(Spr)！用斯斗林公式 S!=(S/e)S(2S)每个信源符号所需码长是(S)lim l=lim(logN)/S=-pr log pr 5熵和信信息源编码定理(4)S有限时有失真，可容忍时S已很大。很难实现。3.变长码的编码定理 可分离的必要条件是异前置性。码树结构(根，叶，节，枝）R 0 0 0 1 1 16信息熵和信源编码定理(5)一个长为li的码字占2L
3、-li个长为L的码字。Kraft不等式：2L-li2L，2-li1 可分离的充要条件。可推广到k进码。若 li=-log pi -log pil1-log pi,7信息熵和信源编码定理(6)2-lipi=1,可以编码,平均码长l，有 -pi log pil=li pi1-pi log pi,SH1S lk,m=2时，能用并元来扩大m，S个符号并成一个 使m=2S。例：独立二元序列 p0=0.7,H=0.881,S=3 17赫夫曼编码(10)符号 概率 码字 码长 符号 概率 码字 码长 000 0.343 00 2 011 0.063 1000 4 001 0.147 11 2 101 0.0
4、63 1001 4 010 0.147 010 3 011 0.063 1010 4 100 0.147 011 3 111 0.027 1.011 4 l=2.726/3=0.909,=0.881/0.909=96.9%增大S尚可进一步提高效率。18赫夫曼编码(11)并元还可部分解除相关性。若 P(0|0)=0.97,P(0|1)=0.07,利用平稳性，可得：p0=0.7,p1=0.3 000 0.659 0 011 0.0195 1111 111 0.259 10 110 0.0195 11010 001 0.0204 1100 010 0.00147 110110 100 0.0204
5、1110 101 0.00147 11011119赫夫曼编码(12)l=1.53/3=0.51A)=p(y2),可逼近H(l0)和H(l1)从而得到很高的编码效率，比并元更易于实现，且能更好地解除相关性（一阶和二阶可全解除，更高阶可减弱。这可说明如下：25游程编码（4）1游程以下列形式开始:x01y,x与前一个0游程长度有关，y是与当前1游程长度有关，对于一阶或二阶马氏链，当01一定时，y的概率已与x的取值无关，也就是当前1游程的长度与前一个0游程的长度相互独立，游程序列是独立序列。它对应于原序列的符号熵等于原序列的条件熵。计算这熵值也可得这一结果。26游程编码（5）二元高阶马氏链通过游程变换
6、虽不能完全解除相关性，但至少可降阶，并减弱相关性。x010101y中间个1相间个符号。对于阶马氏链，的概率与取值无关，当前的游程只与前面-2个游程有关,游程序列降至k-2阶。不是1相间时还要降得多。降阶后的序列相关性也较弱。27游程编码（6）3.实现问题：两种游程分别编赫夫曼码，两个码表。符号集中有无限个元，必须截止。令=2n,l=1,22n-1 各给一个码字。l2n-1,用一个码字C，2n00.0 (n个0),2n+1C00.1 28游程编码（7）2n+1-1C11.1,2n+1C00.0C00.0 2n+1+1C00.0C00.1 0游程的n可与1游程的n不同，0游程的C不但要与本码表的码
7、字异前置，还要与1游程的码表异前置。才能分辨C00.0C是 0游程长度为2n，后面的C是1游程，还是0游程长度大于2n+1-1。29冗余位编码（1）1.概述：冗余位-间隙 固定码位 分成两个序列传送 例 x1,x2xnyyyyyyxn+1,xn+2xn+myyyy 分成 x1,x2xn,xn+1xn+m和 11.1000000111.10000 可逆变换30冗余位编码（2）后一序列通常是一阶马氏链，若 P(0|0)=a,P(0|1)=b,则 p0=a/(1-a+b),p1=/(1-b+a)H(y)=pH(a)+pH(b),H=H(y)+p1H(x)当p1小时，可极大地压缩码率。但同时传送两个序
8、列有困难，通常只好 分段来编码。31冗余位编码（3）2.L-D码 帧长N,信息位数Q,nj是第j个信息位的位置0n1nON 传送Q和T两个值，就可正确译码。若 ,则 nQ=k+1 QjjjnT11QkTQk132冗余位编码（4）若 ,则 nQ-1=l+1 直至求得n1，就可恢复这一帧。由 .QkTT kQkQkQ 11lQTlQ 11133冗余位编码（5）这样就可唯一地判定nQ,以后的T相当于Q-1个信息位的情况。从而判 定nQ-1.编一帧需 比特 )1log(logNQNA1QQnnTQQ12.110QQQQQnnnnQnQTQQQ34冗余位编码（6）例：001000000010000 N=
9、15，Q=2，n1=3,n2=11,需要4比特编Q,0010.需要 7比特编T,0101111 得码字 00100101111a3a11。若Q=0或N,可只用4位码：0000或1111 T 1 1123114 735冗余位编码（7）Q 0 1 2 3 4 5 6 7 T 0 4 7 9 11 12 13 13 总码长 4 8 11 13 15 16 17 17 压缩率0.27 0.53 0.73 0.87 1.0 1.07 1.13 1.13 Q小时才有效。平均编码效率。3.信息位标志码 上例可编为：0011a31011a110000 36冗余位编码（8）最后四个0是分帧号，所需比特数是 A=
10、(Q+1)log(N+1)也只适用于Q小时。平均编码效率不如 L-D码 4.非连1码 不分帧时表示冗余位长度可用非1连码。L 1 2 3 4 5 6 7 8 9 10 码字 0 1 00 01 10 000 001 010 100 101 37冗余位编码（9）例：011111110a1a2a310011110a4a5 表示 4个冗余位（01），三个信息位 （6个 1，1个0），9个冗余位（100），两个信息位 (4个1，1个0）译码是唯一的。非连1码的个数问题。38冗余位编码（10）设长度为k的码字数N(K），以0开始的有N(K-1)个，以1开始的有N(K-2)个，则 N(K)=N(K-1)+N(K-2)N(1)=2,N(2)=3 N(k)=(1/2+5/2)k+2-(1/2-5/2)k+2/5 N(kL)3(1.62)L.冗余位编码的方法尚很多，以上仅举例。
