信息论与编码第五章.ppt

第5章 无失真信源编码 5.1编码的定义 5.2定长编码定理 5.3编码器变长码定理 5.4最佳编码 将信源信息通过信道传送给信宿，怎样才 能做到尽可能不失真而又快速呢？这就需 要解决两个问题： 第一，在不失真或允许一定失真的条件下 ，如何用尽可能少的符号来传送信源信息 ； 第二，在信道受干扰的情况下，如何增加 信号的抗干扰能力，同时又使得信息传输 率最大。 为了解决这两个问题，就要引入信源编码 和信道编码。 信源编码：在不失真或允许一定失真条 件下,如何用尽可能少的符号来传送信源 信息,以便提高信息传输率。 在通信中要求精确的复现信源的输出， 就要保证信源产生的全部信息无损的传 送给信宿，这时的信源编码就是无失真 信源编码。 5.1编码的定义 5.1.1信源编码的定义 编码实质上是对信源的原始符号按一定的 数学规则进行的一种变换。 说明： （1）输出的码符号序列称为码字; （2)长度l称为码字长度或简称码长; (3)编码就是从信源符号到码符号的一种 映射; (4)若要实现无失真编码，则这种映射必 须是一一对应的，并且是可逆的。 二元信道的基本符号集为0,1,若将信源通 过一个二元信道传输，就必须把信源符号变 换成由0,1符号组成的码符号序列，即编码 。可用不同的码符号序列，如表 若把N次无记忆扩展信源的概念加以引申， 便可得到N次扩展码。 5.1.2信源变码的分类 等长码：码中所有码字的长度都相同 变长码：码中的码字长短不一 定义5.1 将信源符号集中的每个信源符号 映射成一个固定的码字 ，这样的码称为分组 码。 采用分组编码方法，需要分组码具有某些属性， 以保证在接受端能够迅速准确地将码译出。下面 首先讨论分组码的一些直观属性。 （1）奇异码和非奇异码：若信源符号和码 字是一一对应的，则该码为非奇异码。反之 为奇异码。 信源符号 信源符号 出现概率 码 表 码0码1码2码3码4 a1p(a1)=1/2000011 a2p(a2)=1/40111101001 a3p(a3)=1/8100000100001 a4p(a4)=1/811110110000001 （2）唯一可译码：若码的任意一串有限长的码 符号序列只能唯一地被译成所对应的信源符号 序列，则此码称为唯一可译码，否则就称为非 唯一可译码。 唯一可译码 码码 信源概率pi 编码编码编码编码编码 U11/211000 U21/4100111001 U31/810000100110011 U41/810000001111110111 即时码：无须考虑后续的码符号即可从码 符号序列中译出码字，这样的唯一可译码 称为即时码。 设 为一个码字，对于任意 的 ，码符号序列的前j个元素 为码字Wi的前缀。 一个唯一可译码成为即时码的充分必要条件是其 中任何一个码字都不是其他码字的前缀。 码树：表示各码字的构成 A 01 0 0 0 00 0 0 0 00 0 00 11 1 111 1 0 1 1 1 11 二进制码树 2 0 0 0 0 0 1 1 1 11 22 2 2 2 三进制码树 树根码字的起点 分成r个树枝码的进制数 终端节点码字1101 中间节点码字的一部分 节数码长 满树： 每个节点上都有r个分枝的树等长码 非满树： 变长码 用树的概念可导出唯一可译码存在的充分和必 要条件 综上所述，可将码作如下分类： 定理5.1 对于码符号为X=x1,x2,xr的任意唯 一可译码，其码字为W1,W2,Wq，所对应的码 长为l1,l2lq，则必定满足克拉夫特不等式 注意：克拉夫特不等式只是说明唯一可译 码是否存在，并不能作为唯一可译码的判 据。 【例5.1】设二进制码树中X=x1,x2,x3,x4， 对应的l1=1,l2=2,l3=2,l4=3，由上述定理，可 得 因此不存在满足这种码长的唯一可译码。 5.1.3唯一可译码的判断法（变长） （1）观察码C中最短的码字是否是其它码字的 前缀，若是，将其所有可能的尾随后缀排列出 。而这些尾随后缀又有可能是某些码字的前缀 ，再将这些尾随后缀产生的新的尾随后缀列出 。 （2）再观察这些新的尾随后缀是否是某些 码字的前缀，再将产生的尾随后缀列出， 依此下去，直到没有一个尾随后缀是码字 的前缀为止。 （3）这样，首先获得了由最短的码字能引起的 所有尾随后缀，接着，按照上述步骤将次短码 字、等等所有码字可能产生的尾随后缀全部 列出。 由此得到由码C的所有可能的尾随后缀的集合 F。当且仅当集合F中没有包含任一码字，则可 判断此码C为唯一可译码。 5.2 定长码编码定理 编码的目的，就是要是信源的信息率最小， 也就是说，要用最少的符号来代表信源。 在定长编码中，对每一个简单信源 ，码 字的长度 都是定值，要实现无失真的信源 编码要求: 信源符号s1 s2sq是一一对应码字W1 W2Wq, 能够无失真或无差错地从W恢复 , 也就是能正确地进行反变换或译码 ; 传送Y时所需要的信息率最小 如果对一个简单信源S进行定长编码，那么信 源S存在惟一可译码的条件是 q是信源S的符号个数，r是信道基本码符号 数,l是定长码的码长 如果对信源S的N次扩展信源SN进行定长编码， 若要编得的定长码是惟一可译码，则须满足 对上式两边取对数，有 表示SN中平均每个原始信源符号所需 要的码符号个数。 对于定长唯一可译码，平均每个原始信 源符号至少用 个码符号来变换。 例如英文电报有32个符号，即 ，采用 二元编码时，则 。对信源每个符号进 行二元编码，则 ，也就是说，每 个英文电报符号至少要用5位二元符号进行 编码才能得到唯一可译码。 定理5.2 设离散无记忆信源 的熵为H(S)，其N次扩展信源为 次扩展信源熵 现在用码符号集X=x1,x2,xr对N次扩展 信源SN进行长度为l的定长编码，对于 ，只要满足 则当N足够大时，必可使译码差错小于 。反之，若 则当N足够大时，译码错误概率趋于1。 定义5.2设熵为H(S)离散无记忆信源，若对信源的长 为N的符号序列进行定长编码，设码字是从r个码符 号集中选取l个码元构成，定义R为编码速率（单位 ：bit/符号），即 此时若 则可以实现无失真传输。 定义5.3.2称 为编码效率。 则有： 设差错概率为 当 和 均为定值时，只要N足够 大， 均为定值时，只要N足够大，即 【例5.1】设离散无记忆信源概率空间为 信源熵为 自信息方差为 对信源符号采用定长二元编码，要求编码效 率 ，无记忆信源有 ， 因此 可以得到 如果要求译码错误概率 因此，一般说来，当N有限时，高传输效率的定长码 往往要引入一定的失真和译码错误。解决的办法是可 以采用变长编码。 5.3 变长码定理 5.3.1码平均长度 定义5.4.1设有信源 编码后的码字为W1,W2,Wq，其码字相应的码长 分别为l1,l2,lq。因是惟一可译码，信源符号si 和码字Wi一一对应，则这个码的平均长度为 表示每个信源符号编码对平均需用的码符号个数 单位：码符号/信源符号 当信源S给定，信源的熵为H(S)，则每 个信道码元所携带的平均信息量可以 表示为: 传输一个码符号平均需要t秒时间，则编码后信道 每秒传输的信息量（单位：bit/s) 定义5.5 对应一给定的信源和一给定的 码符号集,若有一种惟一可译码,其平均 码长 小于所有其他唯一可译码，则 称这种码为紧致码，或最佳码。 定理5. 3设离散无记忆信源 若该离散无记忆离散信源的符号熵为H(S)，每个 信源符号的用具r进制码元进行定长编码，一定 存在一种无失真编码方法，其码字平均码长 满 足 5.3.2离散平稳无记忆序列变长编码定理 （香农第一定理） 定理5.4设离散无记忆信源 的熵为H(S)，其N次扩展信源为 现在用码符号集X=x1,x2,xr对N次扩展信源SN 进行编码，总可以找到一种编码方法，构成惟一 可译码，使信源S中的每个信源符号所需的码字平 均长度满足 或 且当N时，则： 号si所对应的平均码长。 定义5.7 编码效率定义为 表示离散无记忆信源S中的每个信源符 定义5.6变长编码的编码速率定义为 它表示编码后平均每个信源符号能载荷的 最大信息量。于是，定理5.4又可表述为， 其中，L为平均码长。此处 L= 故编码效率一定小于或等于1的数。 定义5.4.3对于变长码，定义码的剩余度为 【例5.4】设离散无记忆信源的概率空间为 其信源熵为 比特/符号 若用二元定长编码（0,1）来构造一个即时码： 这时平均码长 二元码符号/信源符号 编码效率为 输出的信息率为比特/二元码符号 再对长度为2的信源序列进行变长编码，其即时 码如下表所示 序列序列概念即时码序列序列概率即时码 9/1603/16110 3/16101/16111 这个码得码字平均长度 二元码符号/信源符号 每一单个符号的平均码长 二元码符号/信源符号 其编码效率 用同样的方法可进一步将信源序列的长度 增加，L=3或L=4，对这些信源序列X进行 编码，并求出其编码效率为 这时信息传输率分别为 如果对这一信源采用定长二元码编码，要求编 码效率达到96%时，允许译码错误概率 自信息的方差 10-5 2=0.4715 所需要的信源序列长度 4.13107 5.4 最佳编码 紧致码：香农、费诺、霍夫曼 香农码、费诺码、霍夫曼码都考虑了信 源的统计特性,使经常出现的信源符号对 应较短的码字,使信源的平均码长缩短, 从而实现了对信源的压缩； 香农码有系统的、惟一的编码方法,但 在很多情况下编码效率不是很高； 费诺码和霍夫曼码的编码方法都不惟一； 费诺码比较适合于对分组概率相等或接 近的信源编码,费诺码也可以编m进制码 ,但m越大,信源的符号数越多,可能的编 码方案就越多,编码过程就越复杂,有时 短码未必能得到充分利用； 霍夫曼码对信源的统计特性没有特殊要求 ,编码效率比较高,对编码设备的要求也比 较简单,因此综合性能优于香农码和费诺 码。 1. 香农（Shannon）编码 (1)将信源消息符号按其出现的概率大小依次 排列 (2)确定满足下列不等式的整数码长Ki。 (3)为了编成唯一可译码，计算第i个消息 的累加概率 (4)将累加概率Pi变换成二进制数。 (5)取Pi二进数的小数点后Ki位即为该消息 符号的二进制码字。 例5.4 设信源共7个符号消息，a1、a2 、 a3 、 a4 、 a5 、 a6 、 a7，概率分别为别为 0.20 、 0.19 、 0.18 、 0.17 、 0.15 、 0.10 、 0.01，求香 农编码。 信源消息符 号ai 符号概 率p(ai) 累加概率 Pi -log p(ai)码码字长长 度Ki 码码字 a10.2002.323000 a20.190.22.393001 a30.180.392.473011 a40.170.572.563100 a50.150.742.743101 a60.100.893.3241110 a70.010.996.6471111110 信源熵： 信源符号的平均码长为： 编码效率为： 香农编码方法特点： 由于ki总是进一取整，香农编码方法不一定 是最佳的； 码字集合是惟一的，且为即时码； 先有码字的长度再有码字； 对于一些信源，编码效率不高，多余度稍大 ，因此其实用性受到较大限制。 2. 费诺编码方法 费诺编码属于概率匹配编码 (1)将信源消息符号按其出现的概率大小依次 排列： (2)将依次排列的信源符号按概率值分为两大 组，使两个组的概率之和近于相同，并对各组 赋予一个二进制码元“0”和“1”。 (3)将每一大组的信源符号进一步再分成两组 ，使划分后的两个组的概率之和近于相同，并 又赋予两个组一个二进制符号“0”和“1”。 (4)如此重复，直至每个组只剩下一个信源符 号为止。 (5)信源符号所对应的码字即为费诺码。 例5.5 设信源共7个符号消息，a1、a2 、 a3 、 a4 、 a5 、 a6 、 a7，概率分别为别为 0.20 、 0.19 、 0.18 、 0.17 、 0.15 、 0.10 、 0.01，求费 诺编码。 消息符 号ai 各个消 息概率 p(ai) 第一次 分组组 第二次 分组组 第三次 分组组 第四次 分组组 二元 码码字 码长码长 Ki a10.200 0 002 a20.191 0 0103 a30.18 1 0113 a40.171 0 102 a50.151 0 1103 a60.101 0 11104 a70.01 1 11114 信源符号的平均码长为： 编码效率为： 例5.6 有一单符号离散无记忆信源 对该信源用费诺编码方法，求其二进制 代码组及其编码效率。 信源符号概率编码编码码码字码长码长 x10.2500002 x20.251012 x30.1251001003 x40.12511013 x50.062510011004 x60.0625111014 x70.06251011104 x80.0625111114 该信源熵为： 平均码长： 编码效率： 费诺编码特点： 概率大，则分解的次数小；概率小, 则分解的 次数多。这符合最佳编码原则。 码字集合是惟一可译码，且为即时码； 分解完了，同时可以得到码字和码长。 3. 哈夫曼编码方法 (1)将信源消息符号按其出现的概率大小依次排 列， (2)取两个概率最小的字母分别配以0和1两个码 元，并将这两个概率相加作为一个新字母的概率 ，与未分配的二进符号的字母重新排队。 (3)对重排后的两个概率最小符号重复步骤(2) 的过程。 (4)不断继续上述过程，直到最后两个符号配 以0和1为止。 (5)从最后一级开始，向前返回得到各个信源 符号所对应的码元序列，即相应的码字。 例5.7 设信源共7个符号消息，a1、a2 、 a3 、 a4 、 a5 、 a6 、 a7，概率分别为别为 0.20 、 0.19 、 0.18 、 0.17 、 0.15 、 0.10 、 0.01，求哈 夫曼编码。 5.2 无失真信源编码 0.20 0.19 0.18 0.17 0.15 0.10 0.01 0 1 0 1 0 1 0 1 0 1 0.20 0.19 0.18 0.17 0.15 0.11 0.26 0.20 0.19 0.18 0.17 0.35 0.26 0.20 0.19 0.39 0.35 0.26 0.61 0.39 1.00 1 信源符号ai概率p(ai)码码字Wi码长码长 Ki a10.20102 a20.19112 a30.180003 a40.170013 a50.150103 a60.1001104 a70.0101114 信源符号的平均码长为： 编码效率为： 哈夫曼编码方法得到的码并非唯一的。 每次对信源缩减时，赋予信源最后两个 概率最小的符号，用0和1是可以任意的， 所以可以得到不同的哈夫曼码，但不会影 响码字的长度。 对信源进行缩减时，两个概率最小的 符号合并后的概率与其它信源符号的概 率相同时，这两者在缩减信源中进行概 率排序，其位置放置次序是可以任意的 ，故会得到不同的哈夫曼码，此时将影 响码字的长度。 例5.8 设有离散无记忆信源 求哈夫曼编码。 0 1 0 1 0 1 0 1 解法一 1.00.4 0.2 0.2 0.2 0.4 0.4 0.2 0.6 0.4 0.4 0.2 0.2 0.1 0.1 信源符号 ai 概率p(ai)码码字Wi1 码长码长 Ki1 a10.411 a20.2012 a30.20003 a40.100104 a50.100114 解法二 0 1 0 1 0 1 0 1 1.00.4 0.2 0.2 0.2 0.4 0.4 0.2 0.6 0.4 0.4 0.2 0.2 0.1 0.1 信源符号 ai 概率p(ai)码码字Wi2码长码长 Ki2 a10.4002 a20.2102 a30.2112 a40.10103 a50.10113 信源符号的平均码长为： 编码效率为： 在实际应用中，选择那种编码方法？ 我们定义码字长度的方差为ki与平均码 长之差的平方的数学期望，记为2 ，即 计算上例中两种码的方差分别得 21= 1.36 22= 0.16 可见第二种编码方法的码长方差要小 许多。这意味着第二种编码方法的码长 变化较小，比较接近平均码长。 进行哈夫曼编码时，为得到码方差最 小的码，应使合并的信源符号位于缩减 信源序列尽可能高的位置上，以减少再 次合并的次数，充分利用短码。 哈夫曼码是用概率匹配方法进行信源编码。 哈夫曼码的编码方法保证了概率大的符号对 应于短码，概率小的符号对应于长码，充分利 用了短码； 缩减信源的最后二个码字总是最后一位不同 ，从而保证了哈夫曼码是即时码。 把二进制的编码方法推广到m进制哈夫 曼码。所不同的只是每次把m个概率最 小的符号分别用0,1,