第3章通信信導与信源编码 了的概率。于是，这个一阶马尔可夫信源的嫡为： H(X)=H(XX) (3-2-10) (④)连续信源的差熵 连续随机变量不能像离散随机变量那样定义自信息，因而也不能相应地定义熵，但可类 似地定义一种嫡，称为差嫡 p)Logn( (3-2-11) (⑤)连续信源的平均互信息 设连续随机变量X和Y的联合PDF为p(x,y),它们的边沿PDF分别为p(x,py),那么X和 Y之间的平均互信息定义为： x:)=[p)p(yLoddy p(x)p(y) (3-2-12) Y己知时X的平均条件熵定义为： H(XIY)=-[[p(x.y)Logp(xly)dxdy (3-2-13) 于是有 I(X:Y)=H(X)-H(X Y)=H(Y)-H(YX) (3-2-14) 3.3离散信源信息的编码 3.3.1定长编码 一个字符集大小为L的无记忆离散信源X,当各字符的概率相等时其熵的值最大，即： H(X)≤LogL (3-3-1) 采用固定长度码字，对于字符集大小为L的无记忆离散信源所发出的字符序列逐个地进行 无失真编码，则每个码字的长度需要比特： r=mlog2(L-l]+】 (3-3-2) 这里表示舍尾取整，因此应取r比特才能确保L种字符都有对应的码字，即2≥L。 【离散信源定长编码定理】对于一个信源熵等于H(X)比特的无记忆离散平稳信源X,可以 将信源发出的字符序列每J个字符分为一组，用N比特长的码字进行编码，对于任意小的正数 8,只要J选择的足够大，并使码率R满足 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 6 j 的概率。于是，这个一阶马尔可夫信源的熵为： 2 1 HX HX X () ( | ) = (3-2-10) (4) 连续信源的差熵 连续随机变量不能像离散随机变量那样定义自信息，因而也不能相应地定义熵，但可类 似地定义一种熵，称为差熵： H X p x Logp x dx ( ) () () ∞ −∞ = − ∫ (3-2-11) (5) 连续信源的平均互信息 设连续随机变量 X 和Y的联合PDF为 p(, ) x y ,它们的边沿PDF分别为 p( ), ( ) x py ,那么 X 和 Y 之间的平均互信息定义为： () ( | ) ( ; ) () ( | ) () () pxpy x I X Y p x p y x Log dxdy pxpy ∞ ∞ −∞ −∞ = ∫ ∫ (3-2-12) Y 已知时 X 的平均条件熵定义为: H X Y p x y Logp x y dxdy ( | ) (, ) ( | ) ∞ ∞ −∞ −∞ = −∫ ∫ (3-2-13) 于是有 IXY HX HX Y (;) ( ) ( |) = − = HY HY X () ( | ) − (3-2-14) 3.3 离散信源信息的编码 3.3.1 定长编码 一个字符集大小为 L 的无记忆离散信源 X ，当各字符的概率相等时其熵的值最大,即： H X LogL ( ) ≤ (3-3-1) 采用固定长度码字，对于字符集大小为 L 的无记忆离散信源所发出的字符序列逐个地进行 无失真编码，则每个码字的长度需要 r 比特： 2 r Int L = −+ [log ( 1)] 1 (3-3-2) 这里 Int 表示舍尾取整，因此应取r 比特才能确保 L 种字符都有对应的码字，即2r ≥ L 。 【离散信源定长编码定理】对于一个信源熵等于 H X( ) 比特的无记忆离散平稳信源 X ,可以 将信源发出的字符序列每 J 个字符分为一组，用 N 比特长的码字进行编码，对于任意小的正数 ε，只要 J 选择的足够大，并使码率 R 满足
第3章通信信源与信源编码 7 R=N≥HX)+E (3-3-3) 就可以保证编码失败的码组出现的概率P。可以任意小：反之，若码率 R=NSH(X)-6 (3-3-4) 则编码失败码组出现的概率P。将随J的增大而趋于100%. 此定理的含义是：对一个信源发出的符号序列进行定长分组编码，只要码率大于信源熵， 码组又足够长，则无失真编码失败的概率可以无穷小：而若码率小于信源嫡，无失真编码失败 的可能性非常大。 【例】将一本中文书看作一个信源，如果所用汉字都包含在国标一级字表的3763个汉字之中，则国标 一级字表就是信源字符集。将书中的汉字用代码表示，本来需要用12比特长的代码才能表示一个汉字。但 是，假如根据该书中各种汉字出现的概率求得的信源熵H(X)=7.9比特/字符，而将书中每J个汉字看作 个码组用一个N比特的代码表示，那么只要N/J>7.9,即平均每个汉字8比特以上，就有可能成功表示各 种可能的码组，但要使表示失败的概率任意小，则要求J足够大。 3.3.2变长编码 对于非等概率分布的无记忆离散信源的编码，采用可变长度的码字进行编码可获得更高 的编码效率，但其码字必须满足前缀条件，即任意一个码字不能是任何其它码字的前缀。 。Kraft不等式 一个包括有L个码字且都满足前缀条件的码字集是否存在，其充分和必要条件是： 22.s1 (3-3-5) 其中m,m2,n,分别为各个码字的长度 ·离散信源变长编码定理 【定理1】若一离散无记忆信源的熵为H(X),每个信源字符用m进制码字进行变长编码， 则一定存在一种无失真编码方法其码字平均长度下满足不等式： H≤R<W+1 logm logm (3-3-6) 【定理2】对于一个字符熵为H(X)的离散无记忆信源进行变长编码，必定存在一种无失 真编码方法，其平均信息率R满足不等式： 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 7 ( ) N R HX J ≡≥ + ε (3-3-3) 就可以保证编码失败的码组出现的概率 Pe可以任意小；反之，若码率 ( ) N R HX J ≡≤ − ε (3-3-4) 则编码失败码组出现的概率 Pe将随 J 的增大而趋于 100%。 此定理的含义是：对一个信源发出的符号序列进行定长分组编码，只要码率大于信源熵， 码组又足够长，则无失真编码失败的概率可以无穷小；而若码率小于信源熵，无失真编码失败 的可能性非常大。 【例】将一本中文书看作一个信源，如果所用汉字都包含在国标一级字表的 3763 个汉字之中，则国标 一级字表就是信源字符集。将书中的汉字用代码表示，本来需要用 12 比特长的代码才能表示一个汉字。但 是，假如根据该书中各种汉字出现的概率求得的信源熵 H X( ) =7.9 比特/字符，而将书中每 J 个汉字看作一 个码组用一个 N 比特的代码表示，那么只要 N / J >7.9，即平均每个汉字 8 比特以上，就有可能成功表示各 种可能的码组，但要使表示失败的概率任意小，则要求 J 足够大。 3.3.2 变长编码 对于非等概率分布的无记忆离散信源的编码，采用可变长度的码字进行编码可获得更高 的编码效率，但其码字必须满足前缀条件，即任意一个码字不能是任何其它码字的前缀。 z Kraft 不等式 一个包括有 L 个码字且都满足前缀条件的码字集是否存在，其充分和必要条件是： ∑= − ≤ L k nk 1 2 1 (3-3-5) 其中 L n ,n ,.,n 1 2 分别为各个码字的长度。 z 离散信源变长编码定理 【定理 1】若一离散无记忆信源的熵为 H X( )，每个信源字符用m 进制码字进行变长编码， 则一定存在一种无失真编码方法其码字平均长度 K 满足不等式： () () 1 log log HX HX K m m ≤< + (3-3-6) 【定理 2】对于一个字符熵为 H X( )的离散无记忆信源进行变长编码，必定存在一种无失 真编码方法，其平均信息率 R 满足不等式：
第3查通信信源与信源缩码 H(X)≤R<H(X)+EH(X) (3-3-7) 其中ε为任意小的正数。 此两个定理的含义是：采用不定长的m种码字对于每J个字符构成的一个码组进行编码， 只要平均信息率（即平均每个字符的比特数）R>H(X),就可以确保编码成功。 【例】仍以一本中文书中汉字编码为例，因为信源痛是H(X)=7.9比特序符：但因包含J个汉字的各 种可能码组出现的概率不同，我们采用m种比特数不同的码字表示各个码组，概率高的用短码，概率低的 用长码：那么只要码率（平均每个汉字编码的比特数）大于H(X),就可以确保编码成功。 3.3.3 Huffman编码算法 设一个离散信源共有n个信源字符{x,x2,x。}，字符的概率分布为： P(X=x)=p,i=l,2,n,并且B,+P,+.+p.=l:则采用Huffiman树形结构算法可以生成 个非等长的二进制码字集{G,92,C,},即码书，使码字集中各码字分别与信源字符集相对 应，即对应于x。该码书生成的步骤如下： ①比较n个概率值{P,P,P}的大小，将概率最小的两个字符，例如x和x,所对应码 字c和c,的最后一个比特分别指定为0和1； ②将这两个最小概率值合并，即P,=p+P,并用P取代P和P,得到树中第1个节点。 ③将P,与其它n-2个概率值进行比较，重新找出两个概率最小的，如果这两个概率值所 对应的信源字符，例如是x,和x,而不是前述的，和x,则将这两个信源字符所对应的码字c 和c的最后1比特分别指定为0和1：如果x与前述两个字符中的一个相同，例如x,=x,即 曾经分配过1比特，则将c,的倒数第2比特指定为0或1。 ④再次将两个新的最小概率值合并，得到树中一个新的节点，将此概率值与其它的-3 个（也可能还有n-2)概率值进行比较，重新找出两个概率最小的，如果这两个概率值所对应的 信源字符不包括在前面己分配过比特的码字，则将这两个码字的最后1比特分别指定为0和1： 如果这两个码字中有一个（或两个）曾经分配过比特，则将它所涉及的码字的前一比特指定为 0或1。 如此重复进行，直到所有的概率值合并为1，由此得到长短不一的n个码字，即构成一个 uffman树形码书。 【例】由7个字符构成的信源字符集，各字符出现概率分别为0.005,0.005,0.04,0.1,0.2,0.3， 0.35:那么按照上述编码方法设计Huffman码书的7个码字分别为：11111,11110,1110,110， 10,01,00。 西安电子科技大学
第 3 章 通信信源与信源编码 西安电子科技大学 8 HX R HX () () ≤< + ε H X( ) (3-3-7) 其中 ε 为任意小的正数。 此两个定理的含义是：采用不定长的 m 种码字对于每 J 个字符构成的一个码组进行编码， 只要平均信息率（即平均每个字符的比特数） R > H X( ) ，就可以确保编码成功。 【例】仍以一本中文书中汉字编码为例，因为信源熵是 H X( ) =7.9 比特/字符；但因包含 J 个汉字的各 种可能码组出现的概率不同，我们采用 m 种比特数不同的码字表示各个码组，概率高的用短码，概率低的 用长码；那么只要码率（平均每个汉字编码的比特数）大于 H X( ) ，就可以确保编码成功。 3.3.3 Huffman 编码算法 设一个离散信源共有 n 个信源字符 { n x , x ,., x 1 2 } ，字符的概率分布为： ( ) 1, 2,., i i PX x p i n == = ，并且 1 2 . 1 n pp p + ++ = ；则采用 Huffman 树形结构算法可以生成 一个非等长的二进制码字集{ 1 2 , ,., n cc c }，即码书，使码字集中各码字分别与信源字符集相对 应，即 i c 对应于 i x 。该码书生成的步骤如下： ① 比较n 个概率值{ 1 2 , ,., n p p p }的大小，将概率最小的两个字符，例如 i x 和 j x 所对应码 字 i c 和 j c 的最后一个比特分别指定为 0 和 1； ② 将这两个最小概率值合并，即 ij p = i p + j p ，并用 ij p 取代 i p 和 j p ，得到树中第 1 个节点。 ③ 将 ij p 与其它n -2 个概率值进行比较，重新找出两个概率最小的，如果这两个概率值所 对应的信源字符，例如是 i' x 和 j' x ，而不是前述的 i x 和 j x ，则将这两个信源字符所对应的码字 i' c 和 j' c 的最后 1 比特分别指定为 0 和 1；如果 i' x 与前述两个字符中的一个相同，例如 i' x = i x ，即 曾经分配过 1 比特，则将 i c 的倒数第 2 比特指定为 0 或 1。 ④ 再次将两个新的最小概率值合并，得到树中一个新的节点，将此概率值与其它的n -3 个（也可能还有n -2）概率值进行比较,重新找出两个概率最小的,如果这两个概率值所对应的 信源字符不包括在前面已分配过比特的码字,则将这两个码字的最后 1 比特分别指定为 0 和 1； 如果这两个码字中有一个（或两个）曾经分配过比特，则将它所涉及的码字的前一比特指定为 0 或 1。 如此重复进行，直到所有的概率值合并为 1，由此得到长短不一的n 个码字，即构成一个 Huffman 树形码书。 【例】由7个字符构成的信源字符集，各字符出现概率分别为0.005, 0.005, 0.04, 0.1, 0.2, 0.3, 0.35;那么按照上述编码方法设计 Huffman 码书的 7 个码字分别为：11111，11110，1110，110， 10，01，00