[信息与通信]信源编码ppt课件

1、 信源编码信源编码第二部分第三章第二部分第三章Efficiency vs. Reliability Efficiency Average code length as small as possible Reliability The ability to recover from errors in the transmissionCodingDecodingInformation sourceSourcecodingChannelcodingInformationchannelChanneldecodingSourcedecodingDestination 提要提要 1 根本概念根本概念

2、2 根本定理：变长编码定理根本定理：变长编码定理 3 即时码非续长码即时码非续长码 4 仙农仙农-费诺费诺Shannon-Fano法法 5 霍夫曼霍夫曼Huffman法法 * 6 数据压缩的分类与国际标准简介数据压缩的分类与国际标准简介 1 根本概念根本概念1编码：编码：利用编码符号集对消息符号集进展的某种变换。 例例 汉字电报 汉字符号标准电码五单元电码， 即汉字 0，1，2，9 0，15位0、1表示一个数字 0 01101，1 01011，2 11001，4 11010， 8 01110，9 10011 中0022 国0948 01101 01101 1101 1101 01101 100

3、11 11010 01110 2 信源编码：信源编码：又称数据语音、图象、文本压缩数据语音、图象、文本压缩，目的在于减少数字信息中的冗余度，进步通信或存储的有效性 连续信源编码： AA/D转换不讨论； B去冗余度。离散信源的统计特性： 离散消息-在有限符号集中选取假设干个符号组成的随机序列； 形成消息时，各符号出现的概率不同； 组成消息的符号之间有一定的相关性。信源的最正确编码：信源的最正确编码：在保证信息量不变或在允许一定的失真度条件下，使各码字的平均长度最短，即每个码元所含的平均信息量最大。 2 无干扰离散信道的信源编码定理无干扰离散信道的信源编码定理 仙农第一定理，仙农无失真信源编码定理

4、传输效率：传输效率：实际传信率R与信道容量之比，即信道容量 的利用率。 =R/C 对于无干扰无噪声信道， =实际信源熵实际信源熵/最大信源熵最大信源熵= H0X/max HX1 问：问： 能到达多大？2 仙农第一定理仙农第一定理：设离散无记忆：设离散无记忆信源熵为信源熵为HX，经容量，经容量为为Cbit/符号的无干扰信道传输，那么总可以找到某种编符号的无干扰信道传输，那么总可以找到某种编码方法对信源的输出进展编码，使其在信道中的传信率任意码方法对信源的输出进展编码，使其在信道中的传信率任意地接近于信道容量地接近于信道容量C正定理。正定理。证明略逆定理：不存在任何编码方法，使传信率逆定理：不存在

5、任何编码方法，使传信率R大于等于大于等于C。 3 信源编码器的作用：信源编码器的作用：改造信源，使HX最大化，从而使 1， 1的过程就是使信源最正确化的过程。 信源编码又称为使信源与信道匹配信源与信道匹配的最正确编码。类比： 信源信源又分为有记忆信源有记忆信源与无记忆信源无记忆信源：有记忆信源有记忆信源-信源发出的符号前后有关连，一个符号的出现会影响另一个符号的出现。无记忆信源无记忆信源-符号之间是独立的，一个符号出现的概率与前面出现的符号有关。 HX最大化包含两个步骤：1符号独立化，除符号之间的相关性；2各符号概率均匀化。 本章只考虑无记忆离散信源的编码，不考虑步骤1。 3 编码效率及变长编

6、码定理编码效率及变长编码定理最小平均码长与编码效率最小平均码长与编码效率1平均码长平均码长: iimiinxpn)(1可以证明，码字的平均长度DXHn2log)(1最小平均码长最小平均码长DXHn2minlog)(假设D=2，那么)(minXHn2编码效率：编码效率：DnXHnn2minlog)(3编码剩余度：编码剩余度： 1yR例例 一个离散信源输出为4个长度均为1的符号，每个符号出现的概率分别为1/2，1/4，1/8。1/8，求平均码长与编码效率。81,81,41,21,432,1xxxxX解解:)(bit/ 75. 1log)(41符号iiippXH1)(1iimiinxpn875. 0

7、4log75. 1log)(22minDnXHnn125.01yR 信源编码的必要性信源编码的必要性: 实际信源往往含有大量冗余, 比方,英文字母表含空格符共27个符号, 假设等概出现,那么每个符号的信息量为4.76bit, 而在无记忆情况下实际信源熵只有4.076bit/符号, 假设考虑两个字母之间的相关性，那么实际熵只有3.32bit/符号;假设考虑100个字母之间的相关性,那么实际信源熵只有1bit/符号,此时编码剩余度为79%!如何编码才能使平均码长最短？如何编码才能使平均码长最短？ 一般离散信源各符号出现的概率并不相等, 由可知, 概率大的符号编短码概率大的符号编短码,概率小的编长码

8、概率小的编长码, 就可以使平均码长最短. Morse电报就采用这种方法.iimiinxpn)(1 - - 0.00063 Z- - 0.00099 Q- - - 0.00108 J .- 0.0668 A- 0.0856 T 0.1073 EMorse 码字母ip编码方法编码方法例例 一个离散信源由4个符号S1, S2, S3, S4组成,其出现的概率分别为0.6, 0.2, 0.2, 0.1和0.1, 试用不同的方法编码,并加以比较.码码1：假设发S4S1=110，接收时既可译成11，0=S4S1， 也可译成110=S3， 不唯一可译；码码2：等长码，唯一可译，效率较低；码码3：每码字均以0

9、结尾，称为逗点码，唯一可译，且可随收随译；码码4：以0开头，须等待下一个0到来时才能开场译；码码5：立即可译。编码的一般原那么编码的一般原那么:须唯一可译;2 概率大的用短码, 概率小的用长码;3 码字之间不用空格符就能区分;4 须立即可译.变长编码定理变长编码定理:假设离散信源的熵为假设离散信源的熵为HX,每个信源符号用每个信源符号用D进制符号进制符号进展编码进展编码,那么存在某种编码方法那么存在某种编码方法, 其码字平均长度满足其码字平均长度满足DXHDXHn22log)(log)(1对于二进制编码二进制编码D=2, 那么有)()(1XHXHn2 对于对于L次扩展信源次扩展信源, 那么有以

10、下关系那么有以下关系DXHLDXHLDXHnn2L22log)(lim , ,log)(1log)(时当可见注注:1 该定理只是一个极限定理，必须在L为无穷时才能到达理论情况； 2某些信源如语音、图象等在实际应用中往往允许一定的失真不研究。21ii21212 1,)/( 1pn 1S 0,S:) 1 (bit/ 811. 034log434log41log)( :.1 0, 1/4,3/4 ,SSS iiiinppSH信源符号二进符号令单符号编码符号解进行编码试用和其概率分别为组成由两个符号已知信源例)( 98.5% :)3()3(%1 .96842.0811.0lognH(S)842.021

11、n 1627)( 111 110 10 0 16141 163 1634143 SS :2)(L(2)18.9%-1 R%,1 .81lognH(S) 222 224123 2121112y)()43( 2过程略三次扩展编码的一个符号展信源的两个符号构成二次扩由二次扩展LDnpnnSSaSSaSSaSSaDii 4 即时码非续长码、非延长码即时码非续长码、非延长码 1 唯一可译码单义码与即时码唯一可译码单义码与即时码 编码编码-等长码，变长码 等长码：效率低，简单、方便 变长码：效率高，但码字区分困难 要求：要求： 唯一可译； 即时性-可边收边译，不必等待。1唯一可译码单义码：唯一可译码单义码

12、：只能译出一种结果例例 C1=1，01，00 接收序列10001101唯一译成1，00，01，10，1 唯一可译码，单义码C2=0，10，01接收序列01001既可译成01，0，01 也可译成0，10，01 不唯一可译，非单义码2即时码非续长码：即时码非续长码：收到一个码字就能译出，不必等待与观察后面接收的是什么符号。例例 1C1=S1，S2，S3，S4=0，01，011，111 接收序列：0111101101 假设边收边译：0，111，1 译不下去了 假设收完后再译从后往前：01，111，011，01 唯一可译，但需要等待 2C2=S1，S2，S3， S4，S5=00，01，10，110，1

13、11 接收序列：110101110100 110，10，111，01，00 唯一可译码3即时码与唯一可译码单义码之间的关系：即时码与唯一可译码单义码之间的关系： 即时码一定是唯一可译码单义码，但唯一可译码单义码不一定是即时码。即时码存在的充要条件即时码存在的充要条件1即时码存在的充要条件从构造上：即时码存在的充要条件从构造上：即时码中任何任何一个码字都不能是另一个码字的开头前缀一个码字都不能是另一个码字的开头前缀，或者说任任何一个码字都不能是另一个码字的延续延长何一个码字都不能是另一个码字的延续延长，因此这种码又称为非续长码非续长码。2即时码存在的充要条件从码长上：即时码存在的充要条件从码长上

14、：存在N个码长为nii=1,2,n的即时码的充要条件是2 111NinDiD是编码符号集中符号的数目，即编码采用的进制例例 ：信源：信源X=x1,x2,x7，采用，采用2进编码，编出的码长分进编码，编出的码长分 别为，别为， ni=2,2,3,3,3,4,5, 试判断是否存在这样的即时码。试判断是否存在这样的即时码。解：解：存在即时码196875.02121232221543271ini例例 设设wi表示码长为表示码长为i的码字数目的码字数目, 且且w1=0, w2=3, w3=0, w4=5, 求：能编成即时码的求：能编成即时码的D的最小值。的最小值。解：解：.3D ,05.2 192872

15、.4 ,102093 ,0135 ,15322242时可编成即时码故取即即得令DDxxxDxDD即时码的编译码即时码的编译码 编码器的描绘编码器的描绘1即时码的编码码树法即时码的编码码树法例例 设A=0，1，将X=x1,x2,x3,x4编成码长分别为1，2，3，3的即时码。解：解：D=2存在这样的即时码 122212132原那么：任何一个码字不能作为另一个码字的开头用码树图编码的步骤：用码树图编码的步骤： 从顶点树根出发，画出两条D=2分枝，一条代表“0，另一条代表“1。选取其中的一个终点作为码字，如w1=0; 从未被选用的终点再画出两枝，选其中的一个终点作为码字w2; 继续下去，直至W中所有

16、的码字都有一个终点来表示为止； 从树根出发到各个终点，依次读出各枝代表的符号0，1，便得到相应的码字。w1=0W2=10W3=110W4=1112即时码的译码即时码的译码例例 在上例中，假设收到一串码字100110010，试用码树进展译码。解：解：译码方法：译码方法：顺着码树走，遇到一个终点便得到一个码字，然后再回到树根，从头开场走，直至全部码序列都译完为止。译码结果：W2 W1 W3 W1 W2，即10，0，110，0，10紧致即时码：紧致即时码：平均码长刚好等于信源熵的即时码，其编码效率为100%。 1963年Abramson 发现，假设符号出现的概率为，取码字长度为ni, 便能编出紧致即

17、时码。例例 设信源源不断个符号出现的概率分别为1/2，1/4，1/8，1/8，试编成紧致即时码，并将其平均码长与信源熵进展比较。解：解：由)(21inip )(21inip 知，4个码字的长度分别选为1，2，3，3，编码后得到的码字分别为0，10，110，111。. )(n 431n431log)(4141因而是即时码XHpnppXHiiiiii 5 仙农仙农-费诺费诺Shannon-Fano编码法编码法 最正确编码最正确编码-按概率匹配的原那么，概率大的编短码，概率小的编长码，使在给定信息量的条件下，平均码长最短。 两种最正确编码法：两种最正确编码法：仙农费诺法，霍夫曼Huffman法.仙农

18、仙农-费诺编码法费诺编码法符号解编码制试对下列信源进行二进按照概率匹配的原则例/ 75. 2)(log)()( 1 , 0 0625. 0 ,0625. 0 ,125. 0 ,25. 0 ,0625. 0 ,0625. 0 ,25. 0 ,125. 0)( , , , , , , ,X : , 8187654321bitxpxpXHDxpxxxxxxxxiii%100log75.2)( 81DnH(X)nxpniii仙农仙农-费诺法的编码步骤：费诺法的编码步骤： 1将信源符号按概率由大到小排列； 2将全部信源符号分成概率和大致相等的两个D=2组，分别赋予“0，“1； 3再按2的方法对各组进展处

19、理，直至每个符号被分割出来为止； 4 按编码过程顺序读出各符号相应的码元，便得到对应的码字。例例 用仙农-费诺法将下述消息编成三进制码，D=0，1，261,81,81,83,121,81)( , , , , , 654321MpmmmmmmM%94log388.2 ,625.1)( 81DnH(X)H(X)nxpniii 6 霍夫曼霍夫曼Huffman编码法编码法问题：问题：仙农-费诺法的优缺点是什么？如何改进？Huffman编码法编码法例例 对以下信源进展二进制编码：16. 0 ,18. 0 ,08. 0 ,04. 0 ,32. 0 ,22. 0)( , , , , , 654321MpmmmmmmM解：解：符号/ 352. 2)(log)()(61bitmpmpMHiii 先将符号按概率由大到小排列，再从概率最小的符号开场编码%984.2352.2