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，1（5位0、1表示一个数字）0 01101，1 01011，2 11001，4 11010，8 01110，9 10011 中（0022）国（0948）01101 01101 1101 1101 01101 10011 11010 01110
3、 2 信源编码：信源编码：又称数据（语音、图象、文本）压缩数据（语音、图象、文本）压缩，目的在于减少数字信息中的冗余度，提高通信或存储的有效性 连续信源编码：（A）A/D转换（不讨论）；（B）去冗余度。离散信源的统计特性：离散消息-在有限符号集中选取若干个符号组成的随机序列；形成消息时，各符号出现的概率不同；组成消息的符号之间有一定的相关性。3信源的最佳编码：信源的最佳编码：在保证信息量不变（或在允许一定的失真度）条件下，使各码字的平均长度最短，即每个码元所含的平均信息量最大。2 无干扰离散信道的信源编码定理无干扰离散信道的信源编码定理 （仙农第一定理，仙农无失真信源编码定理）1 传输效率：传
4、输效率：实际传信率（R）与信道容量之比，即信道容量 的利用率。=R/C 对于无干扰（无噪声）信道，=实际信源熵实际信源熵/最大信源熵最大信源熵=H0(X)/max H(X)问：问：能达到多大？2 仙农第一定理仙农第一定理：设离散无记忆：设离散无记忆信源熵为信源熵为H(X)，经容量为，经容量为C（bit/符号）的无干扰信道传输，则总可以找到某种编码方符号）的无干扰信道传输，则总可以找到某种编码方法对信源的输出进行编码，使其在信道中的传信率任意地接法对信源的输出进行编码，使其在信道中的传信率任意地接近于信道容量近于信道容量C（正定理）。（正定理）。（证明略）逆定理：不存在任何编码方法，使传信率逆定
5、理：不存在任何编码方法，使传信率R大于等于大于等于C。3 信源编码器的作用：信源编码器的作用：改造信源，使H（X）最大化，从而使 1，1的过程就是使信源最佳化的过程。信源编码又称为使信源与信道匹配信源与信道匹配的最佳编码。类比：信源信源又分为有记忆信源有记忆信源与无记忆信源无记忆信源：有记忆信源有记忆信源-信源发出的符号前后有关连，一个符号的出现会影响另一个符号的出现。无记忆信源无记忆信源-符号之间是独立的，一个符号出现的概率与前面出现的符号有关。H(X)最大化包含两个步骤：(1)符号独立化，除符号之间的相关性；(2)各符号概率均匀化。本章只考虑无记忆离散信源的编码，不考虑步骤（1）。3 编码
6、效率及变长编码定理编码效率及变长编码定理1最小平均码长与编码效率最小平均码长与编码效率平均码长平均码长:iimiinxpn)(1可以证明，码字的平均长度DXHn2log)(（1）最小平均码长）最小平均码长DXHn2minlog)(若D=2，则)(minXHn（2）编码效率：）编码效率：DnXHnn2minlog)(（3）编码剩余度：）编码剩余度：1yR例例 一个离散信源输出为4个长度均为1的符号，每个符号出现的概率分别为1/2，1/4，1/8。1/8，求平均码长与编码效率。81,81,41,21,432,1xxxxX解解:)(bit/75.1log)(41符号iiippXH1)(1iimiin
7、xpn875.04log75.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 码字母ip3 编码方法编码方法例例 一个离散信源由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）：）：立即可译。编码的一般原则编码的一般原则:(1)须唯一可译;(2)概率大的用短码,概率小的用长码;(3)码字之间不用空格符就能区分;(4)须立即可译.4变长编码定理变长编码定理:(1)若离散信源的熵为若离散信源的熵为H(X),每个信源符号用每个信源符号用D进制符号进行编进制符号进行编码码,则存在某种编码方法则存在某种编码方法,其码字平均长度满足其码字平均长度满足DXHDXHn22log)(log)(1对于二进制编码二进制编码(D=2),则有)()(1XHXHn(2)对于对于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.021n 1627)
11、(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）即时码（非续长码）：）即时码（非续长码）：收到一个码字就能译出，不必等待与观察后面接收的是什么符号。例例 （1）C1=S1，S2，S3，S4=0，01，011，111 接收序列：0111101101 若边收边译：0，111，1 译不下去了 若收完后再译（从后往前）：01，111，011，01 唯一可译，但需要等待 （2）C2=S1，S2，S3，
13、S4，S5=00，01，10，110，111 接收序列：110101110100 110，10，111，01，00（唯一可译码）（3）即时码与唯一可译码（单义码）之间的关系：）即时码与唯一可译码（单义码）之间的关系：即时码一定是唯一可译码（单义码），但唯一可译码（单义码）不一定是即时码。2 即时码存在的充要条件即时码存在的充要条件（1）即时码存在的充要条件（从结构上）：）即时码存在的充要条件（从结构上）：即时码中任何一任何一个码字都不能是另一个码字的开头（前缀）个码字都不能是另一个码字的开头（前缀），或者说任何任何一个码字都不能是另一个码字的延续（延长）一个码字都不能是另一个码字的延续（延长）
14、，因而这种码又称为非续长码非续长码。（2）即时码存在的充要条件（从码长上）：）即时码存在的充要条件（从码长上）：存在N个码长为ni（i=1,2,n）的即时码的充要条件是 111NinDi(D是编码符号集中符号的数目，即编码采用的进制）例例 已知：信源已知：信源X=x1,x2,x7，采用，采用2进编码，编出的码长分进编码，编出的码长分 别为，别为，ni=2,2,3,3,3,4,5,试判断是否存在这样的即时码。试判断是否存在这样的即时码。解：解：存在即时码196875.02121232221543271ini例例 设设wi表示码长为表示码长为i的码字数目的码字数目,且且w1=0,w2=3,w3=0
15、,w4=5,求：能编成即时码的求：能编成即时码的D的最小值。的最小值。解：解：.3D ,05.2 192872.4 ,102093 ,0135 ,15322242时可编成即时码故取即即得令DDxxxDxDD3 即时码的编译码即时码的编译码 编码器的描述编码器的描述（1）即时码的编码（码树法）即时码的编码（码树法）例例 设A=0，1，将X=x1,x2,x3,x4编成码长分别为1，2，3，3的即时码。解：解：D=2存在这样的即时码 122212132原则：任何一个码字不能作为另一个码字的开头用码树图编码的步骤：用码树图编码的步骤：从顶点（树根）出发，画出两条（D=2）分枝，一条代表“0”，另一条代
16、表“1”。选取其中的一个终点作为码字，如w1=0;从未被选用的终点再画出两枝，选其中的一个终点作为码字w2;继续下去，直至W中所有的码字都有一个终点来表示为止；从树根出发到各个终点，依次读出各枝代表的符号（0，1），便得到相应的码字。w1=0W2=10W3=110W4=111(2)即时码的译码即时码的译码例例 在上例中，若收到一串码字100110010，试用码树进行译码。解：解：译码方法：译码方法：顺着码树走，遇到一个终点便得到一个码字，然后再回到树根，从头开始走，直至全部码序列都译完为止。译码结果：W2 W1 W3 W1 W2，即10，0，110，0，104 紧致即时码：紧致即时码：平均码长
17、刚好等于信源熵的即时码，其编码效率为100%。1963年Abramson 发现，若符号出现的概率为，取码字长度为ni,便能编出紧致即时码。例例 设信源源不断个符号出现的概率分别为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）编码法）编码法 最佳编码最佳编码-按概率匹配的原则，概率大的编短码，概
18、率小的编长码，使在给定信息量的条件下，平均码长最短。两种最佳编码法：两种最佳编码法：仙农费诺法，霍夫曼（Huffman）法.1 仙农仙农-费诺编码法费诺编码法符号解编码制试对下列信源进行二进按照概率匹配的原则例/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)nxpniii2 仙农仙农-费诺法的编码步骤：费诺法的编码步骤：（1）将信源符号按概率由大到小排列；（2）将全部信源符号分成概率和大致
19、相等的两个（D=2）组，分别赋予“0”，“1”；（3）再按（2）的方法对各组进行处理，直至每个符号被分割出来为止；（4）按编码过程顺序读出各符号相应的码元，便得到对应的码字。例例 用仙农-费诺法将下述消息编成三进制码，D=0，1，261,81,81,83,121,81)(,654321MpmmmmmmM%94log388.2 ,625.1)(81DnH(X)H(X)nxpniii 6 霍夫曼（霍夫曼（Huffman）编码法）编码法问题：问题：仙农-费诺法的优缺点是什么？如何改进？1 Huffman编码法编码法例例 对下列信源进行二进制编码：16.0,18.0,08.0,04.0,32.0,22
20、.0)(,654321MpmmmmmmM解：解：符号/352.2)(log)()(61bitmpmpMHiii 先将符号按概率由大到小排列，再从概率最小的符号开始编码%984.2352.2log ,4.2)(81DnH(M)nmpniiiHufman编码法步骤：编码法步骤：（1）将信源符号按概率由大到小顺序排列；（2）将概率最小的两个（对于D=2）符号分成一组，分别赋予“0”、“1”，并计算出其概率和；（3）将编过码的组作为一个单一符号看待，继续按（1）（2）步骤编码，直至每个符号被分割出来为止；（4）按逆序读出相应符号的码元，便得到所须的码字。作业作业 p.127#3-6,#3-7,#3-8
21、,#3-9补充题：补充题：大桥收费站将过往车辆的类型和数目自动记录在一磁带记录器上，每类车辆分配一个二进制代码，每小时各种车辆的平均数为小汽车：500辆 摩托车：50辆公共汽车：25辆 重型车：200辆出租车：50辆 自行车：25辆有蓬卡车：100辆 其它：50辆 试编成高效即时码，求其编码效率，并与简单等长码作一比较，评价这两种码的可行性与合理性。本章小结本章小结1 基本概念：基本概念：编码 信源编码及其作用 H(X)最大化 平均码长与编码效率 如何编才能使平均码长最短？最佳编码 唯一可译码（单义码）与即时码（非续长码）2 基本定理：基本定理：（1）仙农第一定理；（2）变长编码定理：DXHDXHn22log)(log)(1DXHLDXHn22log)(1log)(L次扩展：3 即时码：即时码：（1）即时码存在的充要条件 从结构上：一个码字不能是另一个码字的开头；从码长上：111NinDi （2）紧致即时码：（3）即时码的码树表示法。4 两种最佳编码：两种最佳编码：（1）仙农-费诺法 （2）Hufman法
