信息论课件chap3[1]

1、第三章第三章 信源编码（一）信源编码（一）离散信源无失真编码离散信源无失真编码l1、信源及其分类l2、离散无记忆信源的等长编码l3、离散无记忆信源的不等长编码l4、最佳不等长编码l5、算术编码l6、LZ编码前前 言言一、通信中的两个问题：1. 信源的输出如何描述：计算信源信息量的问题2. 如何表示信源的输出：信源编码的问题二、信源编码的分类： 什么是编码？1. 无失真信源编码：2. 限定失真的信源编码：消息集到码字集的一种映射3.1 信源及其分类信源及其分类信源的概念 直观理解，信源就是信息的来源。但是必须要注意两点：l在一个固定的时刻，信源发出的是一个随机变量随机变量。l随着时间的延续，信源

2、发出的是一个随机过程。随机过程。因此，一般的信源种类太多，其统计性质太复杂。怎样做工程实用的简化？信源及其分类信源及其分类信源及其分类信源及其分类l离散信源l连续信源l无记忆信源l有记忆信源l简单信源独立同分布l平稳信源，各态历经源lM阶记忆源l时间离散连续源l随机波形源输出消息是否连续各符号是否统计独立离散信源离散信源 ： 信源每隔一个定长时间段就发出一个随机变量；随着时间的延续，信源发出的是随机变量序列U-2U-1U0U1U2，其中lUk为第k个时间段发出的随机变量；l每个Uk都是一个离散型的随机变量。离散无记忆信源离散无记忆信源 ：随机变量、U-2、U-1、U0、U1、U2、相互独立。离

3、散无记忆简单信源：离散无记忆简单信源： 随机变量、U-2、U-1、U0、U1、U2、具有相同的概率分布。 （总结：离散无记忆简单信源就是时间离散、事件离散、各随机变量独立同分布的信源。课程学习所面对的信源将主要是离散无记忆简单信源）信源及其分类信源及其分类3.2 离散无记忆源的等长离散无记忆源的等长编码编码一、一些基本的概念离散无记忆源： DMS1. 消息集A：字母表A=a1,aK,概率p1,pK,且各概率累加和为1。长为L的源输出序列uL=u1,uL，共有KL种序列。称集合UL为消息集消息集。2. 码字、D元码码符号字母表B=b1,bD,以码符号表示源输出序列，每个码符号序列称为码字码字。码

4、符号字母表B中的字符个数为D，对应的码字被称为D元码例例：离散无记忆简单信源发出的随机变量序列为：U-2U-1U0U1U2。其中U1的事件有3个：晴, 云, 阴。(U1U2)有9个事件（晴晴），（晴云），（晴阴），（云晴），（云云），（云阴），（阴晴），（阴云）， （阴阴）。用字母表0, 1对(U1U2)的事件进行2元编码如下：（晴晴）0000，（晴云）0001，（晴阴）0011，（云晴）0100，（云云）0101，（云阴）0111，（阴晴）1100，（阴云）1101，（阴阴）1111。一、一些基本的概念一、一些基本的概念一、一些基本的概念一、一些基本的概念3.等长码、不等长码4.等长D元码和

5、不等长D元码的最大码字数目等长D元码 DN不等长D元码D(DN-1)/(D-1)思考：对于不等长编码，可否完全使用满树？5.单义可译码与非单义可译码（等长码） 每个消息都至少有一个码字与之对应，且不同消息对应不同的码字。6.单义可译码存在的充要条件（等长码） DNKL NLlogK/logD编码速率：编码速率： R=NlogD/L。无错编码无错编码：编码速率 R=NlogD/LlogK非单义可译码非单义可译码：(U1U2UL)的有些不同事件用相同的码字来表示。l如何译码？l “译码错误”概率 ，定义为pe= P(U1U2UL)=(u1u2uL)| (u1u2uL)的码字在译码时并不译为(u1u

6、2uL)。一、一些基本的概念一、一些基本的概念（关于编码速率的说明：p编码速率本来是编码设备的性能指标。这就是说，首先有了编码设备的编码速率R0，然后选择N和L，使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0 ：R=NlogD/LR0。p当编码速率R比较高时，可以选择比较大的N，因此可供选择的码字比较多，因此更容易设计出能够快速识别的码，降低译码的难度。p当编码速率R比较低时，意味着使用低成本的编码设备。此时只能选择不大的N，因此更需要编码的技巧。 ） 一、一些基本的概念一、一些基本的概念单义可译的解读：单义可译的解读：l当R=NlogD/LlogK时，能够实现无错编码。l当R

7、=NlogD/LH(U1)时，无论怎样编码都是有错编码。这是因为R0有P(U1U2UL)=(u1u2uL)| H(U1)-ILH(U1)+LllLVLI11)(111UHEVLEILllL1121111DVLDVLVLDDILllLllL211eLDV一、一些基本的概念一、一些基本的概念取L0使得则当LL0时总有因此当LL0时总有P(U1U2UL)=(u1u2uL)| H(U1)-ILH(U1)+1-。 ee201LDVee21LDV一、一些基本的概念一、一些基本的概念二、信源划分定理二、信源划分定理1、典型序列集的概念弱e典型序列集强e典型序列集)()(:),(eeeUHIUHuLTLLU)

8、()(:),(eeekkkLUapLLapLuLT二、信源划分定理二、信源划分定理)()()()(2| ),(|2)1 (2)(21),(eeeeeeeeUHLUUHLUHLLUHLULrLTuPLTuP2 2、非典型序列集的概念、非典型序列集的概念 称典型序列集的补集为非典型序列3 3、信源划分定理及两个推论、信源划分定理及两个推论三、离散无记忆源编码三、离散无记忆源编码定定理理1、编码速率：、编码速率：R=(1/L)logM=(N/L)logD, M为码字总数2、可达速率的定义：、可达速率的定义：对于给定信源和编码速率R以及任意e0e0，若有L0,以及编译码方法，使得LL0,错误概率小于小

9、于e e，R是可达的（或可采纳的），否则就称R是不可达的三、离散无记忆源编码三、离散无记忆源编码定定理理3、离散无记忆源编码定理离散无记忆源编码定理RH(U),R是可达的，是可达的，R1log)(DUHn因此三、几个定理三、几个定理定理3的推广:现在对信源随机向量UL=(U1U2UL)做唯一可译的D元不等长码。此时UL的事件的个数为KL。则任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足DULHDUHUnLLlog)(log)()(1log)(1log)()(DULHDUHUnLL三、几个定理三、几个定理重新定义平均码长：任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码

10、满足DUHnlog)(LDUHn1log)(LUnnL)(三、几个定理三、几个定理定义编码速率R和编码效率分别为 任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足DnLDUnRLloglog)()(UHR LDUHRlog)(注注: 不等长编码与等长编码具有相似的性质：当不等长编码与等长编码具有相似的性质：当L增大时，对增大时，对UL的编码可以的编码可以使用更短的平均码长，因而更加节省使用更短的平均码长，因而更加节省编码速率。但编码速率。但节省节省编码速率的下限编码速率的下限是是H(U)。RUH)(h三、几个定理三、几个定理例例3.3.1做2元编码。设 ；H(U)=0.811。4

11、14321aaUU概率码字平均码长编码速率编码效率a13/40(13/4+ 11/4)/1=110.811a21/41U2概率码字平均码长编码速率编码效率a1a19/160(19/16+ 23/16+ 33/16+ 31/16)/2=27/3227/320.961a1a23/1610a2a13/16110a2a21/161113.4最佳不等长编码最佳不等长编码3.4最佳不等长编码最佳不等长编码1、对信源的一般性描述：、对信源的一般性描述：信源消息集 A=a1,a2, aK 对应概率 p1 p2 pK二元码字集 C=c1, c2, cK码字长度 n1 , n2,nK2、定理定理3.4.1 对于给

12、定信源，存在最佳唯一二元可译码，最小概率的两个码字码长相等且最长，他们之间仅最后一位不同3.4最佳不等长编码最佳不等长编码3、Huffman编码编码1）整理信源（将消息集按照概率从大到小排列）2）构成新的辅助集（将最小的两个概率合并）3）将辅助集作为信源执行步骤1和步骤24）重复上述过程，知道新的辅助集中只有一个元素为止。5）从最后一个元素开始，依次到推到原始信源中的每个消息，同时记录下途径的分支编码6）结束Huffman编码编码例(0.19, 0.10, 0.01, 0.20,0.15, 0.18, 0.17)0.200.190.180.170.150.100.010.110.260.350

13、.351.00 01 10.200.190.180.170.15A AA A1 10 01 10.200.190.180.170.260.200.190.180.170 01 10.260.200.19A A2 2A A2 2A A3 30 01 10.260 01 1A A4 4A A5 50.39 0.390.610 01 1A A6 6000001010011001111011Shannon-Fano编码编码0 00 00 00 00 01 11 11 11 11 1a a1 1, 00, 00a a2 2, 010, 010a a3 3, 011, 011a a4 4, 10, 10a

14、 a5 5, 110, 110a a6 6, 1110, 1110a a7 7, 1111, 11110 01 13.4最佳不等长编码最佳不等长编码4、定理、定理3.4.2对辅助集U为最佳的码，对原始集U也是最佳的若若C1，C2，CK-1是对辅助集是对辅助集U 的最佳码，的最佳码，相应码长为相应码长为n1，n2，nK-1，则对则对U的码字的码字C1，C2, CK的码长为的码长为lnk= nk kK2lnk= nK-1+1 k=K, K1Kkkknpn12111) 1)(KkKKKkknppnp111)(KkKKkkppnp)(1KKppn3.43.4最佳不等长编码最佳不等长编码3.4最佳不等长

15、编码最佳不等长编码5、结论、结论二元Huffman码是最佳编码，同理可以推广到D元码。6、几个问题、几个问题lHuffman码是否唯一lHuffman码的缺点lcabcedeacacdeddaaabaababaaabbacdebaceadacabcedeacacdeddaaabaababaaabbacdebaceada 共共4040个字母个字母l频度频度la - 16a - 16，b - 7b - 7，c - 6c - 6，d - 6d - 6，e - 5 e - 5 1) 1) 将给定符号按照其频率从大到小排序。将给定符号按照其频率从大到小排序。la - 16 b - 7 c - 6 d -

16、 6 e a - 16 b - 7 c - 6 d - 6 e 5 52) 2) 将序列分成左右两部分，使得左部频率总和尽可能接将序列分成左右两部分，使得左部频率总和尽可能接近右部频率总和。有：近右部频率总和。有：l(a, b), (c, d, e)(a, b), (c, d, e)l3) 3) 我们把第二步中划分出的上部作为二叉树的左子树，记我们把第二步中划分出的上部作为二叉树的左子树，记 0 0，下，下部作为二叉树的右子树，记部作为二叉树的右子树，记 1 1。l4) 4) 分别对左右子树重复分别对左右子树重复 2 3 2 3 两步，直到所有的符号都成为二叉树两步，直到所有的符号都成为二叉树

17、的树叶为止。的树叶为止。bacde00101011a 00b 01c 10d 110e 111l编码结果编码结果lCabcedeacacdeddaaabaababaaabbacdebaceadal10 00 01 10 111 110 111 00 10 00 10 .l长长91bitl采用采用3bit等长编码需等长编码需120bitl采用采用ASCII码需要码需要320bit采用Huffman编码a 16b 7c 6d 6e 511132401010101a 0b 100c 101d 110e 111总比特数总比特数88，信源熵为，信源熵为86.601bitlShannon-FanoShan

18、non-Fano编码构造二叉树是自树根到树编码构造二叉树是自树根到树叶，很难保证最佳性。叶，很难保证最佳性。lHuffmanHuffman编码则是从树叶到树根，是最佳的编码则是从树叶到树根，是最佳的lHuffmanHuffman需要知道信源的概率分布，这在实际需要知道信源的概率分布，这在实际中有时是比较困难的。中有时是比较困难的。l采用半静态模型、自适应模型、采用半静态模型、自适应模型、markovmarkov模型，模型，部分匹配预测模型等等解决这一问题。部分匹配预测模型等等解决这一问题。3.4最佳不等长编码最佳不等长编码7、对、对Huffman码的进一步评价码的进一步评价S=（s1, s2

19、,s3 ,s3 ,s5）P=（0.4，0.2，0.2，0.1，0.1）0.40.20.20.10.1码长码字0.40.20.20.0.40.0.20.0.3.4最佳不等长编码最佳不等长编码0.40.20.20.10.1码长码字0.40.20.20.0.40.0.20.0.结论：平均码长相同时看方差，方差越小越好结论：平均码长相同时看方差，方差越小越好3.4最佳不等长编码最佳不等长编码、 D元元Huffman码码例子：三元例子：三元HuffmanU=（ a1, a2, a3, a4, a5, a6）P=（p1, p2, p3, p4, p5, p6）结论：结论：q = （D-1）m + D3.5

20、算术编码与算术编码与LZ编码编码一、一、Huffman码的本质与缺点码的本质与缺点1、Huffman码的本质码的本质Huffman从本质上说是一种分组码：即对待编码序列分割为长为L的段，然后生成长为N的输入。消息序列与码字一一对应保证唯一可译。一、一、Huffman码的本质与缺点码的本质与缺点、Huffman码的缺点码的缺点当已知信源分布，要求对长信源序列进行编码时需要知道后者的信源分布，编码工作量大。二、香农编码二、香农编码、香农第一定理、香农第一定理码字长度的选择应满足对任意的1)()(iiixIKxI、编码方法：、编码方法：l排列信源概率(x1)(x2) (xn) l确定满足香农第一定理

21、的正数码长Ki二、香农编码二、香农编码l保证唯一可译性：计算第i个消息的累加概率11)(ikkixppl将累加概率换算成二进制小数l取二进制小数点后Ki位为该消息符号的二进制码字二、香农编码二、香农编码例：x1 , x2 , x3 , x4 , x5 , x6 , x7 0.20, 0.19, 0.18, 0.17, 0.15, 0.10, 0.01 以x4 为例100.100100. 057. 018. 019. 020. 0356. 356. 2117. 0log17. 0log4431444242CxpPkkkii二、香农编码二、香农编码同理可得全部编码：源事件p(xi)Pi-log2p

22、(xi)码长码字x10.2002.343000 x20.190.202.413001x30.180.392.483011x40.170.572.563100 x50.150.742.743101x60.100.893.3441110 x70.010.996.6671111110三、算术编码三、算术编码1、与、与Huffman码的不同码的不同a) Huffman是分组码，算术编码不是。其是从全序列出发，需要考虑前后符号间的依赖关系来编码。b) 算术编码无需计算全序列的概率分布，其可以直接对信源符号序列进行编码，可以达到渐近最佳的性能。在这个过程中需要的仅仅是计算累加概率。三、算术编码三、算术编码

23、2、累加概率、累加概率a) 信源符号的累加概率：设信源符号集A=a1 , a2 , ak ，其对应的概率分布为p(ai)0(i=1,2,K) 定义信源符号的累加概率为：1111110)()(,.)()(iikikiikapaFAaaapaF三、算术编码三、算术编码b) 即时码即时码：累加概率函数将0到1的区间非成了不重叠的K个小区间，每个信源符号对应其中一个区间。取区间中一点小数后L位作为信源的码字可保证即时性。c) 信源序列的累加函数信源序列的累加函数：lU=u1 ,u2 , uL ul取值为0或1lF(0) = 0 , F(1) = p(0)F(0)F(1) p(0) p(1)1F(0)F

24、(1) p(0) p(1)1F(0)F(01) p(00) p(01)p(0)F(1)F(01)F(011) p(010) p(011)p(01)F(1)F(011)F(0111) p(0110) p(0111)p(011)F(1)三、算术编码三、算术编码l设当前序列为S，由上图可以归纳出 F(S0)=F(S) 对应区间宽度为A(S0)=A(S).p(0) F(S1)=F(S)+ A(S0)= F(S)+ A(S).p(0) 对应区间宽度为A(S1)=A(S).p(1)=A(S)-A(S0)l结论： F(Sr)=F(S)+ p(S).F(r) (r=0,1) A(Sr)= p(Sr)=p(S)

25、.p(r) (r=0,1)三、算术编码三、算术编码Eg:当S=“011”，接着输入1，得符号序列S1的累加概率为F(S1)=F(0111)=F(s=“011”)+p(011).p(0) =F(s=“01”)+ p(01).p(0)+ p(011).p(0) =F(s=“0”)+p(0).p(0)+ p(01).p(0)+ p(011).p(0) =0+p(00)+p(010)+p(0110)对应区间宽度为A(S1) = A(s=“011”).p(1)=p(011).p(1)=p(0111)F(S1)= 0+p(00)+p(010)+p(0110)0 00 00 00 01 11 11 11 1

26、1 1三、算术编码三、算术编码3、编码方法、编码方法a)码长的选取：设等待编码序列为u，则其码长为)(1logupN)编码步骤：针对u计算出对应的累积概率将该累积概率转换为二进制小数从小数后截取N位，如果后面还有尾数则进位Eg:F(S)=0.10110001 N=3 C=0.110三、算术编码三、算术编码4、码字唯一性讨论、码字唯一性讨论a）C中没有进位b）C中有进位5、例子、例子s=11111100，p(0)=1/4, p(1)=3/4, 所以有H(u)=0.81bit/符号； 6231( )( ) ( )44p s 21log7( )Lp s三、算术编码三、算术编码A：通过计算来编码， F

27、(s)=p(00000000)+p(00000001)+p(11111011) =1-p(11111111)-p(11111110)-p(11111101) -p(11111100)=1-p(1111111)-p(1111110) =1-p(111111) =1- =0.110100100111 所以C(s)=0.1101010 63()4()92.7%7/8H Uh三、算术编码三、算术编码B：用递推公式编码 输入符号P(s)=A(s)A(s)*P(0)F(s)L(s)C(s)10.0100空10.110.00110.0110.110.10010.0010010.011110.110.0110110.10010120.1110.010100010.1010011120.1110.00111100110.110000110130.11110.0010110110010.11010010011130.11100.000010110110010.110