第5章无失真信源编码 通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题： (1) 在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息； (2) 在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。 为了解决这两个问题，就要引入信源编码和信道编码。 一般来说，提高抗干扰能力(降低失真或错误概率)往往是以降低信息传输率为代价的； 反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法能够解决上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和评价具有重大的理论指导意义。 第4章讨论了满足一定失真限度的限失真信源编码。那么在无失真的条件下如何让信源消息尽可能快地传递到接收端呢？这个问题引出了无失真信源编码。本章将在第2章信源统计特性和信源熵概念的基础上，研究离散信源的无失真编码问题，重点讨论无失真信源编码定理，并给出以香农编码、费诺编码和哈夫曼编码为代表的最佳无失真信源编码方法。 5.1编码的基本概念 无失真信源编码是一种可逆编码，是指当信源符号转换成码字后，可从接收码字无失真地恢复原信源符号。本节主要讨论对离散信源进行无失真编码的要求和方法，涉及的基本概念有编码器的定义、码字的类型划分、即时码的构造及唯一可译码的判断等。 5.1.1编码器的定义 编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。 图5.1.1所示是一个信源编码器，它的输入是信源符号序列XN=(X1X2…XN)，序列中的每个符号Xi∈{a1,a2,…,an}； 而每个符号序列依照固定的码表映射成一个码符号序列YKN=(Y1Y2…YKN)，码符号序列中的每个符号Yk∈{b1,b2,…,bm}，一般来说，元素bj是适合信道传输的，称为码符号(或者码元)。输出的码符号序列称为码字，长度KN称为码字长度或简称码长。可见，编码就是从信源符号到码符号的一种映射。若要实现无失真编码，则这种映射必须是一一对应，并且是可逆的。 图5.1.1无失真信源编码器 例5.1.1如果信源输出的符号序列长度为1，即信源输出符号集 X∈{x1,x2,…,xn} 信源概率空间 X P=x1x2…xn p(x1)p(x2)…p(xn) 假设该信道为二元信道，即信道的符号集为{0,1}。若将信源X通过该二元信道传输，就必须把信源符号xi变换成由0、1符号组成的码符号序列，即要进行编码。n=2,4,8时，信源符号与码字的一种可能的一一对应关系为 n=2x1→0,x2→1 n=4x1→00,x2→01,x3→10,x4→11 n=8x1→000,x2→001,x3→010,x4→011 x5→100,x6→101,x7→110,x4→111 例5.1.2为了传输一个由字母A、B、C、D组成的符号集，把每个字母编码成二元码脉冲序列，以“00”代表A，“01”代表B，“10”代表C，“11”代表D，每个二元码脉冲宽度为5ms。 (1) 不同字母等概率出现时，计算信息的传输速率； (2) 若每个字母出现的概率分别为pA=15，pB=14，pC=14，pD=310，试计算信息的传输速率。 解： (1) 不同字母等概率出现时，符号集的概率空间为 X P=ABCD 14141414 每个符号含有的平均信息量即熵为 H(X)=log24=2(bit/符号) 现在用两个二元码脉冲代表一个字母，每个二元码脉冲宽度为τ=5ms，则每个字母占用t=2τ=10ms。1s内可以传输的字母个数为 n=1t=100(字母/s) 则信息传输速率 Rt=nH(X)=200(b/s) (2) 字母出现概率不同时，据题意其概率空间为 X P=ABCD 151414310 则此时每个字母含有的平均信息量为 H(X)=－∑4i=1p(ai)logp(ai)=1.985(bit/符号) 同(1)，计算得信息传输速率为 Rt=nH(X)=198.5(b/s) 可见，编码后信源的信息传输速率与信源的统计特性有关。 对于固定的信源，信源编码的方式对信源的信息传输速率有什么影响呢？ 上例中，将字母A、B、C、D编码为由两个码符号组成的等长码。当然，也可以把每个字母编为长度不同的码字。如 码1： A→111； B→10； C→01； D→0 码2： A→0； B→01； C→001； D→111 码1和码2的性能怎么评价呢？哪个最适合给定的信源，使编码后的信息传输速率最大呢？它们是否满足无失真编码的要求呢？这些问题，将在后续内容中讲到。 无失真码字的性能除了与信源的统计特性相关外，主要由码符号的类型、码长决定。图5.1.2是一个码分类图。 码非分组码 分组码奇异码 非奇异码非唯一可译码 唯一可译码非即时码 即时码(非延长码) 图5.1.2码的分类 这些码的定义如下： 分组码与非分组码——将信源消息分成若干组(符号序列)，对每一组按照固定的码表映射成一个码字，这样的码称为分组码，也叫块码。只有分组码有固定的码表，而非分组码中不存在码表。 二元码——若码符号集为Y={0,1}，所有码字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。 等长码与变长码——若一组码中所有码字的长度都相同，则称为等长码或定长码。若码字的长短不一，则称为变长码。 奇异码与非奇异码——若一组码中所有码字都不相同，则称为非奇异码。非奇异码中，信源符号和码字是一一对应的； 反之，若一组码中有相同的码字，则该码为奇异码。奇异码不可能是无失真的码字。 唯一可译码与非唯一可译码——若任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码； 否则，就称为非唯一可译码。 即时码与非即时码——唯一可译码可分为即时码和非即时码。如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码称为非即时码。如果收到一个完整的码字以后，就可以立即译码，则称为即时码。即时码要求任何一个码字都不是其他码字的前缀部分，也称为异前缀码，又称为非延长码。即时码一定是唯一可译码，但是非即时码并非一定不是唯一可译码，这取决于码字的总体结构，可采用前缀后缀法进行判断。 例5.1.3给定信源 X P=x1x2x3x4 12141818 对该信源进行二元编码，如表5.1.1所示。 表5.1.1二元信源编码示例 信源码字 码1码2码3码4码5码6 x10000110 x2011011100101 x3100010100001001 x411111110000001111 码1中，每个码字的长度相同，为等长码。每个码字各不相同，为非奇异码。若等长码为非奇异码，则一定是唯一可译码，且为即时码。 码2、码3、码4、码5和码6均为变长码。码2中的每个码字都不相同，为非奇异码。码字“00”有两种译码方法，既可以译成信源符号x3，又可以译成x1x1，因此码2是非唯一可译码。 码3中有相同的码字，为奇异码，一定不是唯一可译码。 码4为唯一可译码，也为前缀码，短码是长码的前缀，除去前缀“1”，码字“10”的后缀“0”、码字“100”的后缀“00”及码字“1000”的后缀都不是码组中的码字，因此该非即时码为唯一可译码，这就是前缀后缀判断法。 码5为即时码，一定是唯一可译码。 码6为前缀码，短码“0”是长码“01”“001”的前缀，对应的后缀分别为“1”“01”，其中后缀“01”是码组中单独的码字，因此码6不是唯一可译码。码符号序列001既可以译成信源符号x3，又可以译成x1x2。 5.1.2即时码的码树构造法 即时码一定是唯一可译码。无失真信源编码要求所编的码字必须是唯一可译码，包含两层含义，一是要求信源符号与码字一一对应； 二是要求码字的反变换也对应唯一的信源符号，否则就会引起译码带来的错误和失真。 即时码作为唯一可译码以其较快的译码速度得到广泛应用。那么，如何构造即时码呢？ 即时码的一种简单构造方法是码树法。 对于给定码字的全体集合 C={W1,W2,…,Wq} 图5.1.3码树结构图 可以用码树来描述它。所谓树，就是既有根、枝，又有节点，如图5.1.3所示。图中，最上端A为根节点，A、B、C、D、E皆为节点，E为终端节点。A、B、C、D为中间节点，中间节点不安排码字，而只在终端节点安排码字，每个终端节点所对应的码字就是从根节点出发到终端节点走过的路径上所对应的符号组成。终端节点E，走过的路径为ABCDE，所对应的码符号分别为0、0、0、1，则E对应的码字为0001。可以看出，按码树法构成的码一定是即时码，是非前缀的唯一可译码。 从码树上可以得知，当第i阶的节点作为终端节点，且分配码字，则码字的码长为i。任一即时码都可以用码树来表示。当码字长度给定后，用码树法安排的即时码不是唯一的。如图5.1.3中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。 对一个给定的码，画出其对应的码树，如果有中间节点安排了码字，则该码一定不是即时码。这是最简单的即时码判断方法。 每个中间节点上都有r(r为进制数，如为二进制码树，则r=2)个分支的树称为满树，否则为非满树。 即时码的码树还可以用来译码。当收到一串码符号序列后，首先从根节点出发，根据接收到的第一个码符号来选择应走的第一条路径，再根据接收到的第二个符号来选择应走的第二条路径，直到走到终端节点为止，就可以根据终端节点，立即判断出所接收的码字。然后从树根继续下一个码字的判断。这样，就可以将接收到的一串码符号序列译成对应的信源符号序列。 在表5.1.1给出的码组中，码1、码2和码5对应的码树图分别如图5.1.4(a)、(b)、(c)所示。 图5.1.4码1、码2和码5对应的码树 可见，码1和码5的各码字位于树的终端节点，满足即时码的条件。 5.1.3唯一可译码与克拉夫特不等式 用码树的概念可以判断、构造即时码，还可以导出唯一可译码存在的充分和必要条件，即各码字的长度Ki应符合克拉夫特(Kraft)不等式。 定理对于码符号为Y={b1,b2,…,bm}的任意唯一可译码，其码字为W1,W2,…,Wq，所对应的码长为k1,k2,…,kq，则必定满足克拉夫特不等式 ∑qi=1m－ki≤1(5.1.1) 反之，若码长满足上面的不等式，则一定存在具有这样码长的唯一可译码。式中，m为码符号进制数。 克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据，但可以作为某码组不是唯一可译码的判据。如{0,10,11,110}不满足克拉夫特不等式，则肯定不是唯一可译码； {0，10，010，111}满足克拉夫特不等式，但却不是唯一可译码。因为，如果收到码字“010”，则存在两种可能的译码方法： 既可译为“010”对应的信源符号，又可译为“0”“10”对应的信源符号； 而{0，10，110，111}是满足克拉夫特不等式的唯一可译码。 例5.1.4设二进制码树中X={x1,x2,x3,x4}，对应的k1=1，k2=2，k3=2,k4=3，由上述定理，可得 ∑4i=12－ki=2－1+2－2+2－2+2－3=98>1 因此不存在满足这种码长的唯一可译码。{0,10,11,110}的码长分布如题，肯定不是唯一可译码。 根据克拉夫特不等式，结合前缀后缀法即可以判断某码组是否是唯一可译码。 (1) 等长码为唯一可译码的判断法。等长码若为非奇异码，一定是唯一可译码。 (2) 变长码为唯一可译码的判断法。首先，该变长码的各码字长度若不满足克拉夫特不等式，则一定不是唯一可译码； 如果变长码的各码字长度满足克拉夫特不等式，则进一步按照前缀后缀法判断。将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。 集合F的构成方法： 首先，观察码C中最短的码字是否是其他码字的前缀，若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀，再将这些尾随后缀产生的新的尾随后缀列出，然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为止。这样，首先获得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码字等所有码字可能产生的尾随后缀全部列出。由此得到由码C的所有可能的尾随后缀的集合F。 例5.1.5设码C={0,10,1100,1110,1011,1101}，根据唯一可译码前缀后缀判断法，判断其是否是唯一可译码。 解： 首先，计算克拉夫特不等式 ∑6i=12－ki=2－1+2－2+2－4+2－4+2－4+2－4=1 因此，该码组满足克拉夫特不等式。存在该码长分布的唯一可译码。下面结合前缀后缀法判断具体码字。 (1) 先看最短的码字“0”，它不是其他码字的前缀，所以没有尾随后缀。 (2) 再观察次短码字“10”，它是码字“1011”的前缀，因此有尾随后缀 尾随后缀集合F={11，00，10，01,0，11，1，100，110，011，101}，其中“10”“0”为码字，故码C不是唯一可译码。 5.1.4码性能评价参数 无失真码字的性能除了与信源的统计特性相关外，主要由所编码字的特性决定。无失真编码要求所编的码字是唯一可译码，码组中的各码字的码长要满足克拉夫特不等式。无失真编码器的整体性能需要用平均码长、编码信息率、压缩比、编码效率和信道剩余度评价。 1. 平均码长 如果单符号信源概率空间为 X P=x1x2…xn p(x1)p(x2)…p(xn) 对每个信源符号进行无失真信源编码，对应码字为C={W1,W2,…,Wn}，所对应的码长为k1,k2,…,kn。根据无失真信源编码的要求中信源符号与码字的一一映射关系，码字概率空间和码长概率空间为 C P=W1W2…Wn p(x1)p(x2)…p(xn) 和 K P=k1k2…kn p(x1)p(x2)…p(xn)(5.1.2) 各码字长度的数学期望，即平均码长为 =E［ki］=∑ni=1kip(xi)(5.1.3) 上述信源编码的对象是单符号信源，因此式(5.1.3)的平均码长又称为单符号码长。当然，大多数的情况下，可以对单符号信源的N次扩展信源进行编码，所编的码字称为N次扩展码。假设N次扩展信源的概率空间为 XN P=α1α2…αq p(α1)p(α2)…p(αq)(5.1.4) 对每个信源序列进行无失真信源编码，对应码字为C={W1,W2,…,Wq}，所对应的码长为k1,k2,…,kq。 各码字长度的数学期望，即平均码长为 N=∑qi=1kip(αi)(5.1.5) 称N为序列码长，对应的单符号码长为 =NN(5.1.6) 单符号码长的物理意义就是平均一个信源符号对应个码符号。那么，单符号信源的熵也将平均分配给个码符号。 2. 编码信息率 单符号信源X的信源熵就是信源的信息传输速率。若所编码字的单符号码长为，则单符号信源的熵等于个码符号的熵。当信源给定时，信源的熵确定，而编码后每个信源符号平均用个码符号来替换。那么，每个码符号的平均信息量，即编码信息率为 R=H(X)(5.1.7) 若传输一个码符号平均需要t秒，则编码后信源每秒钟传输的信息量，即编码后信源的信息传输速率为 Rt=H(X)t(5.1.8) 式(5.1.7)和式(5.1.8)给出了单符号信源的编码信息率和信息传输速率； 对于如图5.1.1所示的信源序列编码器，只需要把式中的单符号信源熵H(X)替换为信源序列的符号熵HN(X)即可。 R=HN(X)(5.1.9) Rt=HN(X)t(5.1.10) 式中，=NN，代入式(5.1.9)，可得 R=NHN(X)N=H(XN)N(5.1.11) 式中，H(XN)为无记忆信源序列的序列熵。 编码信息率既可以表示为单符号熵与单符号码长之比，也可以表示为序列熵与序列码长之比。而且，平均码长越短，编码信息率就越大，编码的信息传输速率就越高。为此，信源编码研究中感兴趣的是使平均码长为最短的码。 3. 压缩比 压缩比是衡量数据压缩程度的指标之一。目前常用的压缩比定义为 Pr=LB－LdLB×100%(5.1.12) 式中，LB为源代码长度； Ld为压缩后的代码长度。 压缩比的物理意义是被压缩掉的数据占据源数据的百分比。当压缩比Pr接近100%时，压缩效果最理想。 4. 编码效率 与信源信息传输速率的定义相类似，编码后信道中传输的是码符号，因为不能完全获得码符号的概率分布，只能按照每个码符号的等概率分布进行估算。也就是说，所设计的信道要具有传输码符号等概率分布时的最大熵的传输能力或手段。 图5.1.1给出的编码器中，码符号序列YKN=(Y1Y2…YKN)，码符号序列中的每个符号Yk∈{b1,b2,…,bm}，根据最大熵定理，当码符号等概率分布时，即p(bi)=1m，每个码符号携带的平均信息量最大，等于logmbit，长度为N的码字的最大信息量为Nlogmbit。用该码字表示长为N的信源序列，则送出一个信源符号所需要的信息率最大值为 Rmax=NNlogm=logm(5.1.13) 定义编码效率 η=HN(X)logm(5.1.14) 对二元码，m=2，代入式(5.1.14)，可得 η=HN(X)(5.1.15) 或 η=H(XN)N 从工程观点来看，总希望通信设备经济、简单，并且单位时间内传输的信息量越大越好。 5. 信道剩余度(冗余度) 信道剩余度表示信道未被利用的程度，所以是冗余的。信道冗余度定义为 γ=1-η=1-HN(X)(5.1.16) 可见，对于二元信源编码，编码效率与编码信息率大小相同，只是单位不同。平均码长越短，编码效率和编码信息率越高。当平均码长等于信源熵时，编码效率达到上限100%，编码信息率达到二元对称信道的信道容量1，消除信源冗余度实现了信源与信道的匹配。由上述分析可见，最短的平均码长与信源的统计特性有关，如果某种信源编码方法的平均码长最短，可称之为最佳无失真信源编码。一般情况下，如何使无失真信源编码的平均码长尽可能接近信源熵并可实现是被关心的问题，在解决该问题的过程中需要遵循的是无失真信源编码定理。 5.2无失真信源编码定理 由5.1节可知，无失真信源编码要求所编码字必须是唯一可译码，这样才能保证无失真或无差错地从Y恢复X，也就是能正确地进行译码； 如果进一步考虑编码前后的信息传输率变化，无失真信源编码的编码信息率的最大值必定不能小于信源的信息率，同时希望传送Y时所需要的信息率最小。 无失真信源编码的编码信息率的最大值必定不能小于信源的信息率的数学描述为 NNlogm≥HN(X)(5.2.1) 可写成 logm≥HN(X)(5.2.2) 即 ≥HN(X)logm(5.2.3) 上式给出了无失真信源编码平均码长的下界，对于二元编码，≥HN(X)。 5.2.1定长编码定理 前面已经讲过，所谓信源编码，就是将信源符号序列变换成另一个序列(码字)。设信源输出符号序列长度为N，码字的长度为KN，编码的目的就是要使信源的信息率最小，也就是说，要用最少的符号来代表信源。 在定长编码中，对每一个信源序列，KN都是定值，编码的目的是寻找最小KN值。 定长编码定理由N个符号组成的、每个符号熵为HN(X)的无记忆平稳信源符号序列X1X2…XN，可用KN个符号Y1Y2…YKN(每个符号有m种可能值)进行定长编码。对任意ε>0,δ>0，只要 NNlogm≥HN(X)+ε(5.2.4) 则当N足够大时，必可使译码差错小于δ，即可实现几乎无失真编码； 反之，当 KNNlogmHN(X)HN(X)+logmN(5.2.20) 或者 η=H(XN)N 例5.2.2设离散无记忆信源的概率空间为 X P=x1 34x2 14 其信源熵为 H(X)=14log24+34log243=0.811(bit/符号) 若用二元定长编码(0,1)来构造一个即时码： x1→0,x2→1，这时平均码长为 =1(二元码符号/信源符号) 编码效率为 η=H(X)=0.811 输出的编码信息率为 R=0.811(bit/符号) 再对长度为2的信源序列进行变长编码，其即时码如表5.2.1所示。 表5.2.1长度为2的信源序列对应的即时码 序列序 列 概 率即时码序列序 列 概 率即时码 x1x19/160x2x13/16110 x1x23/1610x2x21/16111 这个码的平均长度为 K2=916×1+316×2+316×3+116×3=2716(二元码符号/信源序列) 单个信源符号所编码字的平均码长为 =22=2732(二元码符号/信源符号) 其编码效率和编码信息率分别为 η2=32×0.81127=0.961 R2=0.961(bit/码符号) 这说明，虽然编码复杂了，但信息传输率和效率有了提高。同样，可以求得信源序列长度增加到3和4时，进行变长编码所得的编码效率和信息传输速率分别为 η3=0.985，R3=0.985(bit/码符号) η4=0.991，R4=0.991(bit/码符号) 如果对这一信源采用定长二元码编码，要求编码效率达到96%，允许译码错误概率δ≤10－5，则可以算出自信息方差为 σ2(X)=∑2i=1pi(logpi)2－［H(X)］2=0.4715 ε为 ε=H(X)η－H(X)=0.8110.96－0.811=0.811×0.040.96 需要的信源序列长度为 L≥σ2(X)ε2δ=4.13×107 可以看出，使用定长编码时，为了使编码效率较高(96%)，需要对非常长的信源序列进行编码，且总存在译码差错。而使用变长编码，使编码效率达到96%，只要L=2就行了，且可以实现无失真编码。当然，变长编码的译码相对来说要复杂一些。 5.2.3最佳变长编码及MATLAB实现 香农第一定理给出了信源熵与编码后的平均码长之间的关系，同时也指出可以通过编码使平均码长达到极限值，因此，香农第一定理是一个极限定理。但定理中并没有告知如何来构造这种码。 根据最佳码的编码思想： 选择每个码字长度ki满足 ki=log1p(xi)(5.2.21) 式中，·」表示向上取整。 由单符号变长编码定理可知，这样选择的码长一定满足克拉夫特不等式，所以一定存在唯一可译码。然后，按照这个码长ki，用树图法就可以编出相应的一组码(即时码)。 式(5.2.21)证明： 根据单符号变长编码定理，≥H(X)logm，即 H(X)-logm≤0 展开式为 H(X)-logm=-∑ni=1p(xi)logp(xi)－logm∑ni=1p(xi)ki =-∑ni=1p(xi)logp(xi)+∑ni=1p(xi)logm－ki 詹姆斯不等式∑ni=1p(xi)logm－kip(xi)≤log∑ni=1p(xi)m－kip(xi)=log∑ni=1m－ki 因为总可以找到一种唯一可译码，其码长满足克拉夫特不等式，所以 H(X)－logm≤log∑ni=1m－ki≤0 得 ≥H(X)logm 上式成立的充要条件是 m－kip(xi)=1，对所有i 即 p(xi)=m－ki 两边取对数，得 ki=－logp(xi)logm==－logmp(xi) 证明完毕。 下面将介绍三种无失真信源编码方法： 香农编码、费诺编码以及哈夫曼编码。这三种码的平均码长都比较短。 1. 香农编码方法 因为平均码长是各个码字长度的概率平均，可以想象，应该使出现概率大的信源符号编码后码长尽量短一些，出现概率小的信源符号编码后码长长一些，保证平均码长较短。三种编码方法的出发点都是如此，这也是变长编码的思想。 香农编码严格意义上来说不是最佳编码。 香农编码是采用信源符号的累计概率分布函数来分配码字的。 设信源符号集X={x1,x2,…,xn}，并设所有的P(x)>0，则香农编码方法如下： (1) 将信源消息符号按其出现的概率大小依次排列： p(x1)≥p(x2)≥…≥p(xn)； (2) 确定满足下列不等式的整数码长ki： －logp(xi)≤ki<－logp(xi)+1 (3) 为了编成唯一可译码，计算第i个消息的累加概率： Pi=∑i－1k=1p(xk) (4) 将累加概率Pi变换成二进制数； (5) 取Pi二进制数的小数点后ki位即为该消息符号的二进制码字。 可以证明，这样得到的编码一定是唯一可译码，且码长比较短，接近于最佳编码。也可以不对信源消息符号按概率大小排列，这时香农编码方法如下： (1) 求出修正累计概率分布函数为 Pi=∑i－1k=1p(xk)+12p(xi)xk,xi∈X (2) 确定满足下式的码长： ki=log1p(xi)+1 (3) 将修正累加概率Pi变换成二进制数。 (4) 取Pi二进制小数点后ki位即为该消息符号的二进制编码。 例5.2.3设信源共由7个符号组成，其概率和香农编码过程如表5.2.2所示。 表5.2.2香农编码过程 信源符号xi符号概率p(xi)累加概率Pi-logp(xi)码字长度ki码字 x10.2002.343000 x20.190.22.413001 x30.180.392.483011 x40.170.572.563100 x50.150.742.743101 x60.100.893.3441110 x70.010.996.6671111110 以i=4为例，第4个信源符号所编码的码长为 -log0.17≤k4<－log20.17+1 即 2.56≤k4<3.56 取 k4=3 第4个信源符号累加概率Pi=0.57，变成二进制数，为0.1001…，取3位，得第4个信源符号所编码字为： 100。 小数变二进制数的方法： 用Pi乘以2，如果整数部分有进位，则小数点后第一位为1，否则为0，将其小数部分再做同样的处理，得到小数点后的第二位，依此类推，直到得到满足要求的位数，或者没有小数部分为止。 例如，现在Pi=0.57，乘以2为1.14，整数部分有进位，所以小数点后第一位为1，将小数部分即0.14再乘以2，得0.28，没有整数进位，所以小数点后第二位为0，依此类推，可得到其对应的二进制数为0.1001…。 由表5.2.2可以看出，编码所得的码字没有相同的，所以是非奇异码，也没有一个码字是其他码字的前缀，所以是即时码、唯一可译码。 香农编码的MATLAB程序： 主程序shanoncode.m，子程序deczbin.m。 %%%主程序shanoncode.m clc clear all n=input('输入信源符号个数n='); p=zeros(1,n); while(1) for i=1:n fprintf('请输入第%个符号的概率:',i); p(1,i)=input('p='); end if sum(p)~=1 disp('输入概率不符合概率分布') continue else y=fliplr(sort(p)); d=zeros(n,4); D(:,1)=y; for i=2:n D(1,2)=0;%令第一行第二行的元素为0 D(i,2)=D(i-1,1)+D(i-1,2);%第二行其余的元素用此式求得，即为累加概率 end for i=1:n D(i,3)=-log2(D(i,1));%求第三列的元素 D(i,4)=ceil(D(i,3));%求第四列的元素,对D(i,3)向无穷方向取最小正整数 end D A=D(:,2)';%取出D中第二列元素 B=D(:,4)'; for j=1:n C=deczbin(A(j),B(j))%生成码字 end end break end function ［C］=deczbin(A,B)%对累加概率求二进制的函数 C=zeros(1,B);%生成零矩阵用于存储生成的二进制数，对二进制的每一位进行操作temp=A; %temp赋值 for i=1:B%累加概率转化为二进制，循环求二进制的每一位，B控制生成二进制的位数 temp=temp*2; if temp>1 temp=temp-1; C(1,i)=1; else C(1,i)=0; end end 程序运行结果： 输入信源符号个数n=7 请输入第1个符号的概率:p=0.2 请输入第2个符号的概率:p=0.19 请输入第3个符号的概率:p=0.18 请输入第4个符号的概率:p=0.17 请输入第5个符号的概率:p=0.15 请输入第6个符号的概率:p=0.1 请输入第7个符号的概率:p=0.01 D = 0.200002.32193.0000 0.19000.20002.39593.0000 0.18000.39002.47393.0000 0.17000.57002.55643.0000 0.15000.74002.73703.0000 0.10000.89003.32194.0000 0.01000.99006.64397.0000 C =000 C =001 C =011 C =100 C =101 C =1110 C =1111110 例5.2.3中香农编码的性能可以用平均码长和平均信息传输率、编码效率评价。 平均码长为 =∑7i=1p(xi)ki=3.14(二元码符号/信源符号) 平均信息传输率为 R=H(X)=2.613.14=0.831(bit/码符号) 编码效率为 η=H(X)=83.1% 压缩之前7个符号，平均每个符号需要3bit表示，经香农编码压缩之后的平均码字长度为3.14，因此压缩比为 Pr=3－3.143×100%=－4.67% 香农编码的效率不高，本例中压缩比为负值，并没有对信源进行压缩，实用意义不大，但对其他编码方法有很好的理论指导意义。 2. 费诺编码方法 费诺编码也不是最佳编码方法，但有时可以得到最佳编码。 费诺编码方法如下： 首先，将信源符号以概率递减的次序排列起来，将排列好的信源符号分成两组，使每一组的概率之和相接近，并各赋予一个二元码符号“0”或者“1”； 然后，将每一组的信源符号再分成两组，使每一小组的符号概率之和也接近相等，并又分别赋予一个二元码符号。依此下去，直到每一个小组只剩下一个信源符号为止。这样，信源符号所对应的码符号序列则为编得的码字。 例5.2.4给定信源的费诺编码过程如表5.2.3所示。 表5.2.3费诺编码过程 消 息 符 号符 号 概 率第一次分组第二次分组第三次分组第四次分组码字码长 x10.20 x20.19 x30.18001 002 00103 10113 x40.17 x50.15 x60.10 x70.011 0 1 01 102 1103 011104 111114 费诺编码的MATLAB程序： %fanocode.m clc; clear all; fprintf('......................费诺编码程序......................＼n'); fprintf('请输入信源符号的个数:'); N=input('N=');%输入信源符号的个数 s=0;l=0;H=0; for i=1:N fprintf('请输入第%d个符号的概率:',i); p(i)=input('p=');%输入信源符号概率分布向量,0=1 error('请注意P的范围是01 & B(i,j)==B(i-1,j) d=d+1; else d=1; end B(B(n,j+1),j+1)=-1; temp=B(:,j+1); x=find(temp==B(i,j)); END(i)=END1(x(d)); end y=B(n,j+1); END(t-1)=［char(END1(y)),'0'］; END(t)=［char(END1(y)),'1'］; t=t+1; END1=END; end A%排序后的原概率序列 END%编码结果 for i=1:n ［a,b］=size(char(END(i))); L(i)=b; end avlen=sum(L.*A)%平均码长 H1=log2(A); H=-A*(H1')%熵 P=H/avlen%编码效率 end 程序运行结果为 Enter the number of source symbols:7 input source symbol probability:0.2 input source symbol probability:0.19 input source symbol probability:0.18 input source symbol probability:0.17 input source symbol probability:0.15 input source symbol probability:0.1 input source symbol probability:0.01 m = 1 n = 7 A = 0.2000 0.1900 0.1800 0.1700 0.1500 0.1000 0.0100 END = ［10, 11, 000, 001, 010, 0110, 0111］ avlen = 2.7200 H = 2.6087 P = 0.9591 哈夫曼编码还可以调用huffmanenco和huffmandeco函数实现编码和译码： ENCO = HUFFMANENCO(SIG, DICT)——HUFFMANENCO Encode an input signal using Huffman coding algorithm. DECO = HUFFMANDECO(COMP, DICT)——HUFFMANDECO Huffman decoder. 上例的MATLAB程序如下： Clear all; clc; symbols=［1:7］; p=［0.2 0.19 0.18 0.17 0.15 0.1 0.01］; entropy=-p*log2(p'); ［dict,avg_len］=huffmandict(symbols,p) eta=entropy/avg_len; source_len=1000; seq=randsrc(1,source_len,［1 2 3 4 5 6 7;0.2 0.19 0.18 0.17 0.15 0.1 0.01］); comp=huffmanenco(seq,dict); ［s,codeseq_len］=size(comp) actual_avg_len=codeseq_len/source_len actual_eta=entropy/actual_avg_len dcomp=huffmandeco(comp,dict); 输出： dict = %编码映射表，第1列为信源序号，第1列对应码字长度 ［1］［1x2 double］［1,0］ ［2］［1x2 double］ ［1,1］ ［3］［1x3 double］［0,0,0］ ［4］［1x3 double］［0,0,1］ ［5］［1x3 double］［0,1,0］ ［6］［1x4 double］ ［0,1,1,0］ ［7］［1x4 double］［0,1,1,1］ avg_len = 2.7200%平均码长 codeseq_len = 2750%码序列长度 actual_avg_len = 2.7500%实际平均码长 actual_eta = 0.9486%实际平均码长 平均码长为 =∑7i=1p(xi)ki=2.72(二元码符号/信源符号) 信息传输率为 R=H(X)=2.612.72=0.9596(bit/码符号) 压缩之前7个符号，平均每个符号需要3bit表示，经哈夫曼编码压缩之后的平均码字长度为2.72，因此压缩比为 Pr=3－2.723×100%=9.33% 与香农编码、费诺编码相比，哈夫曼编码的平均码长较短，编码效率和压缩比较高。 从表5.2.4可以看出，哈夫曼编码方法得到的码一定是即时码。因为这种编码方法不会使任一码字的前缀为码字。这一点在用码树形式表示时看得更清楚。图5.2.1是用码树形式进行哈夫曼编码的过程，由于代表信源符号的节点都是终端节点，因此其编码不可能是其他终端节点对应的码字的前缀。 另外，由于哈夫曼编码总是把概率大的符号安排在离根节点近的终端节点，所以其码长比较小，因此得到的编码整体平均码长就比较小。 哈夫曼编码得到的码不是唯一的，因为每次对缩减信源中两个概率最小的符号编码时，“0”和“1”的安排是任意的。另外，当两个符号的概率相同时，排列的次序也是随意的，所以可能导致不同的编码结果，但最后的平均码长一定是一样的。在这种情况下，怎么样来判断一个码的好坏呢？可以引进码字长度ki偏离平均长度的方差，即码方差σ2： σ2=E［(ki－)2］=∑ni=1p(xi)(ki－)2 哈夫曼编码时，一般将合并的概率放在上面，这样可获得较小的码方差。 例5.2.6对信源{0.4 0.2 0.2 0.1 0.1}进行哈夫曼编码的过程如表5.2.5和表5.2.6所示。两个表中合并符号概率与原信源符号概率相同时，表5.2.5将合并信源符号概率排在上面，表5.2.6将合并信源符号概率放在下面。 表5.2.5哈夫曼编码过程1 表5.2.6哈夫曼编码过程2 表5.2.5所编哈夫曼编码字的平均码长和码方差分别为 =0.4×2+0.2×2+0.2×2+0.1×3+0.1×3=2.2(二元码符号/信源符号) σ2k=0.4×0.22+0.2×0.22+0.2×0.22+0.1×0.82+0.1×0.82=0.16 表5.2.6所编哈夫曼编码字的平均码长和码方差分别为 =0.4×1+0.2×2+0.2×3+0.1×4+0.1×4=2.2(二元码符号/信源符号) σ2k=0.4×1.22+0.2×0.22+0.2×0.82+0.1×1.82+0.1×1.82=1.36 可见，将合并概率放在同概率信源符号的上面能提供较小的码方差。因此哈夫曼编码中应将合并概率放在同概率信源符号的上面，以保证较好的编码性能。 从以上的编码实例中可以看出，哈夫曼编码具有以下三个特点： (1) 哈夫曼编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，且短码得到充分利用。 (2) 每次缩减信源的最后两个码字总是最后一位码元不同，前面各位码元相同。 (3) 每次缩减信源的最长两个码字有相同的码长。 这三个特点保证了所得的哈夫曼编码一定是最佳编码。 5.3实用的无失真信源编码方法 无失真信源编码主要用于离散信源或数字信号，如文字、数字、数据等。它们要求无失真地数据压缩，且无失真地可逆恢复。目的是增加单位时间内传送的信息量，即提高信息传输的效率。香农第一定理给出了无失真信源压缩的理论极限，由定理可知，信源的熵是信源进行无失真编码的理论极限值，存在最佳的无失真信源编码方法使编码后信源的信息传输率任意接近信源的熵。香农第一定理并没有告知如何找到最佳的无失真信源编码方法，但是，从降低信源冗余度的途径考虑，只要寻找到去除信源符号相关性或者改变信源符号概率分布不均匀性的方法和手段，就能找到最佳无失真信源编码的具体方法和实用码型。 5.2.3节已经从香农第一定理内容中信源熵与平均码长的关系推导出码长与信源各符号自信息量的关系，讨论了香农编码、费诺编码和哈夫曼编码的原理和方法。它们都是当信源的统计特性一定时，能达到或接近无失真信源压缩极限的典型编码方法。上述编码主要适用于多元信源和无记忆信源。当信源给定时，哈夫曼编码是最佳编码，它在实际中已有所应用,但它仍存在一些分组码所具备的缺点。例如，概率特性必须得到精确的测定，若略有变化，还需要更新码表； 对于二元信源，必须对其N次扩展信源进行编码，才能取得好的效果，但当合并的符号数不大时编码效率提高不多，特别是二元相关信源； 采用哈夫曼编码等分组编码方法会使编译码设备变得复杂，而且没有充分利用扩展信源符号间的相关性，导致这些编码方法的编码效率提高不多。 游程编码、算术编码和字典码是针对相关信源的有效无失真信源编码方法，属于非分组码，尤其适用于二元相关信源。 5.3.1游程编码及其MATLAB实现 对于二元相关信源，输出的信源符号序列中往往会出现多个“0”或“1”符号，游程编码尤其适合对这类信源的编码。游程编码已在图文传真、图像传输等实际通信工程技术中得到应用，实际工程技术中也常与其他变长编码方法进行联合编码，如哈夫曼编码、MH编码等，能进一步压缩信源，提高传输效率。 游程编码是无失真信源编码，它能够把二元序列编成多元码。 在二元序列中，只有“0”和“1”两种码元，把连续出现的“0”称为“0”游程，连续出现的“1”称为“1”游程。连续出现“0”或者“1”码元的个数称为游程长度(RunLength，RL)，“0”游程长度记为L(0)，“1”游程长度记为L(1)。这样，一个二元序列可以转换成游程序列，游程序列中游程长度一般都用自然数标记。 例如，二元序列00011111000000011110001000000可以变换成多元序列3574316。 若规定游程必须从“0”游程开始，第一个游程是“0”游程，则第二个游程必为“1”游程，第三个又是“0”游程……。上述变换是可逆、无失真的。如果连“0”或连“1”非常多，则可以达到信源压缩的目的。 一般传输信道为二元离散信道，游程序列中的各游程长度必须变换成二元码序列。等长游程编码就是将游程长度编成二进制的自然数。上例中，max［L(0),L(1)］=7，则用三位二进制码来编码，上例的游程序列对应的码序列为 011101111100011001110 可见，信源序列由原来的29个二元符号，编成21个二元码符号，信源序列得到压缩，游程长度越长及长游程较多时压缩效果越好。 为提高压缩比，变长游程编码游程映射变换后常和哈夫曼编码或MH编码结合。联合编码过程如下： 首先对游程映射的各多元序列，测定L(0)和L(1)的概率分布，以游程长度为元素，构造一个新的多元信源，一般L(0)和L(1)应建立各自的信源； 然后对L(0)构成的多元信源进行哈夫曼编码，得到不同游程长度映射的码字，从而将游程序列变换成码字序列； 同样，对L(1)构成的多元信源进行哈夫曼编码，这样就可以得到L(0)信源与L(1)信源的码字和码表，而且两码表中的码字一般是不同的。在上述编码过程中，考虑到编码的复杂度以及长游程概率随游程长度减小的特点，对较大的游程长度，采用截断处理的方法，将大于一定长度的长游程统一用等长码编码。 游程编码一般不直接应用于多灰度值的图像，因其压缩比很低，但比较适合于黑白图文、图片等二值图像的编码。游程编码与其他一些编码方法的混合使用，能达到较好的压缩效果。如在彩色静止图像压缩的国际标准化算法JPEG中，采用了游程编码和离散余弦变换(Discrete Cosine Transform，DCT)及哈夫曼编码的联合编码方法。 例5.3.1二值图像游程编码算法的MATLAB实现。 clc clear all image1=imread('C:＼Program Files＼MATLAB71＼work＼1＼girl.jpg');%读入图像 figure(1); imshow(image1);%显示原图像 %以下程序是将原图像转换为二值图像 image2=image1(:);%将原始图像写成一维的数据并设为 image2 image2length=length(image2); %计算image2的长度 for i=1:1:image2length%for 循环，目的在于转换为二值图像 Ifimage2(i)>=127 image2(i)=255; else image2(i)=0; end end image3=reshape(image2,146,122); %重建二维数组图像，并设为image3 figure(2); imshow(image3);%以下程序为对原图像进行游程编码，压缩 X=image3(:);%令X为新建的二值图像的一维数据组 x=1:1:length(X);%显示游程编码之前的图像数据 figure(3); plot(x,X(x)); j=1; image4(1)=1; for z=1:1:(length(X)-1)%游程编码程序段 ifX(z)==X(z+1) image4(j)=image4(j)+1; else data(j)=X(z);%data(j)代表相应的像素数据 j=j+1; image4(j)=1; end end data(j)=X(length(X));%最后一个像素数据赋给data image4length=length(image4); y=1:1:image4length; figure(4); plot(y,image4(y)); PR=(image2length-image4length)/ (image2length; %压缩比 l=1; for m=1:image4length for n=1:1:image4(m); rec_image(1)=data(m); l=l+1; end end u=1:1:length(rec_image); figure(5) plot(u,rec_image(u)); 二值图像游程编码算法的MATLAB实现所涉及的原图像、原图像转换的二值图像、二值图像灰度数据以及游程编码结果如图5.3.1~图5.3.4所示。 图5.3.1原图像 图5.3.2原图像转换为二值图像 图5.3.3二值图像灰度数据 图5.3.4游程编码结果 仿真结果显示，压缩比PR=93.58%。 5.3.2算术编码及其MATLAB实现 算术编码也是一种无失真信源编码方法。 前面讨论的无失真信源编码方法，都是针对单个信源符号的编码，当信源符号之间有相关性时，这些编码方法由于没有考虑到符号之间的相关性，因此编码效率就不可能很高。解决的办法是对信源序列进行编码，编码效率随序列长度增大而提高。但序列中符号之间的相关性以及序列之间的相关性无法考虑，无法真正满足信源编码的匹配原则。比如，某个符号的概率为0.8，该符号只需要-log0.8=0.322位二元码符号编码，但香农编码等最佳变长编码会为其分配一位0或一位1的码字。是否存在与该符号概率相匹配的编码呢？ 为了解决这个问题，需要跳出分组码的局限，研究非分组码。算术编码就是一种非分组编码方法。其基本思路： 从全序列出发，将不同的信源序列的概率映射到［0，1］区间上，使每个序列对应区间上的一点，即把区间［0，1］分成许多互不重叠的小区间，不同的信源序列对应不同的小区间，每个小区间的长度等于某一序列的概率。在每个小区间内取一个二进制小数用作码字，其长度可与该序列的概率匹配，达到高效率编码的目的。可以证明，只要这些小区间互不重叠，就可以编得即时码。 可见，算术编码的主要编码方法就是计算信源符号序列所对应的小区间。下面将讨论如何找出信源符号序列所对应的区间。 设信源符号集A={a1,a2,…,aq}，其相应的概率分布为p(ai)，p(ai)>0(i=1,2,…,q)。定义信源符号的累积分布函数为 F(ak)=∑k－1i=1p(ai) 则 F(a1)=0,F(a2)=p(a1),F(a3)=p(a1)+p(a2),… 对二元序列，有 F(0)=0,F(1)=p(0) 现在，来计算二元信源序列s的累积分布函数。只讨论二元无记忆信源，结果可推广到一般情况。 (1) 初始时，在［0，1)区间内由F(1)划分成二个子区间［0，F(1))和［F(1)，1)，F(1)=p(0)。子区间［0，F(1)］的宽度为A(0)=p(0)，子区间［F(1)，1)的宽度为A(1)=p(1)。子区间［0，F(1)］对应于信源符号“0”，子区间［F(1)，1)对应于信源符号“1”。若输入符号序列的第一个符号为s=“0”，即落入相应的区间为［0，F(1))，得F(s=“0”)=F(0)=0。即某序列累积概率分布函数为该序列所对应区间的下界值。 (2) 当输入的第二个符号为“1”时，s=“01”，s=“01”所对应的区间是在［0，F(1))中进行分割。符号序列“00”对应的区间宽度为A(00)=A(0)p(0)=p(0)p(0)； 符号序列“01”对应的区间宽度为A(01)=A(0)p(1)=p(0)p(1)=p(01)，也等于A(01)=A(0)-A(00)。“00”对应的区间为［0，F(s=“01”))； “01”对应的区间为［F(s=“01”)，F(1))。其中，F(s=“01”)是符号序列“01”区间的下界值。可见，F(s=“01”)=p(0)p(0)正是符号序列s=“01”的累积分布函数。 (3) 当输入符号序列中第三个符号为“1”时，因前面已输入序列为s=“01”，所以可记做输入序列为s1=“011”(若第三个符号输入为“0”，可记作s0=“010”)。现在，输入序列s1=“011”所对应的区间是对区间［F(s)，F(1))进行分割。序列s0=“010”对应的区间宽度为A(s0=“010”)=A(s=“01”)p(0)=A(s)p(0)，其对应的区间为［F(s)，F(s)+A(s)p(0))，而序列s1=“011”对应的区间宽度为 A(s1=“011”)=A(s)p(1)=A(s=“01”)-A(s0=“010”) 即A(s1=“011”)=A(s)-A(s0)，其对应的区间为［F(s)+A(s)p(0),F(1))。可得，符号序列s1=“011”的累积概率分布函数为F(s1)=F(s)+A(s)p(0)。 (4) 若第三个符号输入为“0”，由上述分析可得，符号序列s0=“010”的区间下界值仍为F(s)，所以符号s0=“010”的累积概率分布函数为F(s0)=F(s)。 现已输入三个符号串，将这个符号序列标为s，接着输入第四个符号为“0”或“1”，又可计算出s0=“0110”或s1=“0111”对应的子区间及其累积概率分布函数，如图5.3.5所示。 图5.3.5信源符号序列的累积概率分布函数F(s)及对应的区间A 根据前面的分析，可归纳出： 当已知前面输入符号序列s，若接着输入一个符号“r”，则二元信源符号序列的累积概率分布函数的递推公式为 F(sr)=F(s)+p(s)F(r)(r=0,1)(5.3.1) 同样，可得信源符号序列所对应区间宽度的递推公式为 A(sr)=p(sr)=p(s)p(r)(5.3.2) 由此可得，信源符号序列对应的区间宽度等于该符号序列的概率。 例5.3.2设二元无记忆信源X∈{0,1}，其p(0)=1/4，p(1)=3/4。对二元序列s=11111100做算术编码。 解： 根据式(5.3.1)和式(5.3.2)，二元序列s=11111100的累积概率分布函数为 F(11111100)=F(1111110)+p(1111110)F(0) =F(111111)+p(111111)F(0)+p(1111110)F(0) =F(11111)+p(11111)F(1) =F(1111)+p(1111)F(1) =F(111)+p(111)F(1) =F(11)+p(11)F(1) =F(1)+p(1)F(1)+p(11)F(1)+p(111)F(1)+p(1111)F(1)+ p(11111)F(1)+p(111111)F(0)+p(1111110)F(0) =p(0)+p(10)+p(110)+p(1110)+p(11110)+p(111110) 其对应的区间宽度为 A(11111100)=p(11111100) 由于累积概率分布函数和子区间宽度都是递推公式，因此在实际应用中，只需要两个存储器，把p(s)和F(s)存储下来，然后随着符号的输入，不断地更新两个存储器中的数值。因为在编码过程中，每输入一个符号就要进行乘法和加法运算，所以称这种编码方法为算术编码。 很容易将其推广到多元信源序列。可以得到一般信源序列的累积概率分布函数和区间宽度的递推公式为 F(sak)=F(s)+p(s)F(ak) A(sak)=p(sak)=p(s)p(ak)(5.3.3) 通过关于信源符号序列的累积概率分布函数计算，F(s)可以把区间［0，1)分割成许多小区间，每个小区间的长度等于各信源序列的概率F(s)，不同的信源符号序列对应于不同的区间［F(s),F(s)+p(s))。可取小区间内的一点来代表这个序列。下面讨论如何选择这个点。 将符号序列的累积概率分布函数写成二进制小数，取小数点后l位，若后面有尾数，则进位到第l位，这样得到的一个数C，并使l满足 l=log1p(s)(5.3.4) 设C=0.z1z2…zl，zi取0或者1，得符号s的码字为z1z2…zl。这样选取的数值C，根据二进制小数截去位数的影响，得 C－F(s)<12l 当F(s)在l位以后没有尾数时，C=F(s)。另外，由l=log1p(s)可知，p(s)≥12l，则信源符号序列s对应区间的上界为 F(s)+p(s)=F(s)+12l>C 可见，数值C在区间［F(s)，F(s)+p(s))内。不同的信源序列对应的不同区间(左封右开的区间)是不重叠的，所以编得的码是即时码。符号序列s的平均码长满足 －∑sp(s)logp(s)≤=∑sp(s)l(s)<－∑sp(s)logp(s)+1 平均每个信源符号的码长为 H(s)n≤n