《信息论与编码 第5章(1).》由会员分享，可在线阅读，更多相关《信息论与编码 第5章(1).（55页珍藏版）》请在金锄头文库上搜索。
1、*1 信源编码 第5章(第1讲） * 2 数字通信系统的一般模型 等效信道 干扰源 物理信道 解调器 编码器 译码器 信宿 信源 调制器 实际信道 编码信道 * 3 p信息通过信道传输到信宿的过程即为通信。要做到 既不失真又快速地通信，需要解决两个问题： n在不失真或允许一定失真条件下，如何提高信息 传输速度-这是本章要讨论的信源编码问题. n在信道受到干扰的情况下，如何增加信号的抗干 扰能力，同时又使得信息传输率最大-这是下 章要讨论的信道编码问题. * 4 * 5 u信源编码分为无失真和限失真。 u无失真编码，又名冗余度压缩编码：仅对信源的冗余度进 行压缩，不改变信源的熵；可逆编码的基础，
2、只适用于离 散信源，主要用于文字、数据信源的压缩。 u限失真编码，又名熵压缩编码：在失真受限的情况下进行 限失真编码。只适用于连续信源，主要用于图像、语音信 源的压缩。 p信源编码的基础是信息论中的两个编码定理 n无失真信源编码 第一极限定理 n限失真信源编码 第三极限定理 p信道编码定理（离散和连续信道） 第二极限定理 * 6 信源编码的主要任务 n减少冗余，提高编码效率。具体的说，就是针对信源输出 符号序列的统计特性，寻找一定的把信源输出符号序列变 换为最短码字序列的方法。 n符号变换：使信源输出符号与信道的输入符号相匹配。 p信源编码的基本途径有两个: n一是编码后使序列中的各个符号之间
3、尽可能地互相独立， 即解除相关性-方法包括预测编码和变换编码. n二是使编码后各个符号出现的概率尽可能相等，即均匀化 分布-方法主要是统计编码. * 7 p本章主要介绍信源编码的基本思路与主要方法，讨 论离散信源编码，首先从无失真编码定理出发，重 点讨论以香农码、费诺码和哈夫曼码为代表的最佳 无失真码。然后介绍了限失真编码定理。最后简单 介绍了一些其它常用的信源编码方法。期望通过本 章学习能建立起信源压缩编码的基本概念。 * 8 5.1 编码的定义 5.2 无失真信源编码 5.3 限失真信源编码 5.4 常用信源编码方法简介 主 要 内 容 * 9 5.1 编码的定义 * 10 编码的定义 p
4、编码定理证明: n必存在一种编码方法,使代码的平均长度可任意 接近但不能低于符号熵; n达到这目标的途径就是使概率与码长匹配。 p统计匹配编码： n根据信源的不同概率分布而选用与之匹配的编 码,以达到在系统中传信速率最小。 * 11 p编码器的作用： p 将信源符号集X中的符号 变换成由码符号集y中的码元 组成的长度为KL的一一对应的码字 。 p 码字集合叫做代码组Y；码字 所含码元的个数称为该码 字的码长，记为KL 。 编码器信源符号集X 代码组Y 基本符号y 编码的定义 * 12 如果信源输出符号序列长度L1，信源符号集 A(a1，a2，an)，信源概率空间为 若将信源X通过二元信道传输，
5、就必须把信源符 号ai变换成由0，1符号组成的码符号序列，这个 过程就是信源编码。 编码的定义 * 13 信源符号信源符号 概率 码 表 码1 码2 00 0 01 01 10 001 11 111 p若码集为0,1,所得码字为二元序列,称为二元码 p例如,信源符号Xa1,a2,a3,a4,对应不同码字如表 编码的定义 * 14 编码的定义 信源符号 信源符号 出现概率 码 表 码0码1码2码3码4 a1p(a1)=1/2000011 a2p(a2)=1/40111101001 a3p(a3)=1/8100000100001 a4p(a4)=1/811110110000001 p等长码：码中所
6、有码字的长度都相同 p可变长码：码中的码字长短不一 两种码：固定长度和可变长度的编码。 * 15 分组码的属性： (1)奇异码和非奇异码： p非奇异码：如果信源符号和码字是一一对应的，则称该 码为非奇异码。如码0,2,3,4 p奇异码：如果信源符号和码字不是一一对应的，则称该 码为奇异码。如码1 分组码/块码：将信源符号集X中的每个符号 映射成一个固定的码字 。这种码必须具有 某些属性，才能保证在接收端能够迅速可靠地译码。 编码的定义 * 16 编码的定义 (2)唯一可译码： n任意有限长的码元序列,只能被唯一地分割成一 个个的码字。 p例：0,10,11是一种唯一可译码。 p任意一串有限长码
7、序列,如100111000,只能被分 割成10,0,11,10,0,0。任何其他分割法都会产生 一些非定义的码字。 p奇异码不是唯一可译码 p非奇异码 n唯一可译码 码3 100,1,1,1000 n非唯一可译码 码2 10000100 * 17 (2)唯一可译码： 例如： 信源概率pi 编码编码编码编码编码 U11/2000111 U21/4010101001 U31/810100100001 U41/811100110000001 对于码元序列100111000110，分别用编码1， 编码3，编码4，试判断那种是唯一可译码？ * 18 编码的定义 (2)(2)唯一可译码唯一可译码 p非即时
8、码： n如果接收端收到一个完整的码字后不能立即译码,还 需等下一个码字开始接收后才能判断是否可以译码 p即时码（非延长码，异前缀码）： n在译码时无需参考后续的码符号就能立即作出判断, 译成对应的信源符号。 n任意一个码字都不是其它码字的前缀部分 p在延长码中,有的码是唯一可译的,取决于码的总体结构 ,如码3, “1,10,100,1000”. * 19 例如： 信源概率pi 编码编码编码编码编码 U11/2000000 U21/401011001 U31/810100110011 U41/81110111110111 试判断编码4和编码5是否为即时码？ * 20 编码的定义 码 非分组码 分
9、组码 奇异码 非奇异码 非唯一可译码 唯一可译码 非即时码 即时码 (非延长码 ) * 21 p码树从树根开始向下长出m个树枝，成为m进制码树 ，树枝代表码元，树枝与树枝的交点叫做节点。经过 r个树枝才能到达的节点称为r阶节点。向下不长出树 枝的节点称为终端节点或端点。m进制码树各节点（ 包括树根）向下长出的树枝不会超过m,若树码的各 个分支都延伸到最后一级端点称为满树（整树），否 则称为非满树非整树。 p码树上任一节点都对应一个码字，组成该码字的码元 就是从树根开始到该节点所经过的树枝（码元）。 p一个码，如果其所有的码字均处于终端节点，即端点 ，则该码就为非延长码。 编码的定义-用码树来构
10、造码字 * 22 p码树：表示各码字的构成（m进制） 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 三进制码树 树根码字的起点 分成m个树枝码的进制数 终端节点码字1101 中间节点码字的一部分 节数码长 * 23 码4 1 1 1 1 0 0 0 1 01 001 0001 码4 0 0 0 0 1 1 1 0 10 110 1110 p树码 n如果有n个信源符号,那么在码树上就要选择n个终 端节点,用相应的r元基本符号表示这些码字。 码0 0 1 0 0 111 1
11、 10 01 00 p任一即时码都可用树图 法来表示。 p当码字长度给定,即时 码不是唯一的。 * 24 1 10 1000 100 1 0 0 0 p码3对应的树如下图: 编码的定义 p该码树从根到终端节点所经路径上每一个中间节点 皆为码字,因此满足前缀条件。 p虽然码3不是即时码,但它是唯一可译码。 * 25 编码的定义 p满树： n每个节点上都有r个分枝的树等长码 p非满树： n变长码 p用树的概念可导出唯一可译码存在的充分和必要 条件,即各码字的长度Ki应符合Kraft不等式 式中: m是进制数 n是信源符号数 * 26 p例：设二进制码树中X=(a1 , a2 , a3 , a4),
12、 K1=1,K2=2,K3=2,K4=3,应用Kraft不等式,得： 不存在满足这种 Ki的唯一可译码 0 0 01 1 0 10 110 11 中间节点 p如果将各码字长度改成K1=1,K2=2,K3=3,K4=3,则 这样的码字就存 在唯一可译码 111 * 27 编码的定义 pp必须注意：必须注意： nKraft不等式只是用来说明唯一可译码是否存在 ,并不能作为唯一可译码的判据。 n如码字0，10，010，111虽然满足Kraft不等 式,但它不是唯一可译码。 * 28 唯一可译码的判断法 p方法一根据异前缀码是惟一可译码： n首先观察是否是非奇异码。若是奇异码，肯定不是唯一可 译码 n
13、其次，计算是否满足Kraft不等式。若不满足一定不是唯一 可译码； n然后将码画成一棵树图，观察是否满足异前缀码的树图的 构造，若满足则是唯一可译码。 n缺点：若是前缀码时，则无法判断是否是唯一可译码。 * 29 惟一可译码的判断准则 p方法二用A.A.Sardinas和G.W.Patterson设计的判断法： n算法思想：根据惟一可译码的定义可知，当且仅当有限长 的码符号序列能译成两种不同的码字序列，则此码是非惟 一的可译变长码。即如下图情况发生，其中Ai和Bi都是码 字。在下图中，B1一定是A1的前缀，而A1的尾随后缀一 定是另一码字B2的前缀；又B2的尾随后缀又是其他码字 的前缀。最后，
14、码符号序列的尾部一定是一个码字。 * 30 pA.A.Sardinas和G.W.Patterson算法步骤 n计算分组码中所有可能的尾随后缀集合A,观察A中有 没有包含任一码字，若无则为唯一可译码；若有则一 定不是唯一可译码。 n集合A的构造： p首先观察码C中最短的码字是否是其它码字的前缀。若 是，将其所有可能的尾随后缀排列出。而这些尾随后缀 又可能是某些码字的前缀，再将由这些尾随后缀产生的 新的尾随后缀列出。 p然后再观察这些新的尾随后缀是否是某些码字的前缀， 再将产生的尾随后缀列出。这样，首先获得由最短的码 字能引起的所有尾随后缀。 p接着，按照上述将次短的码字等等，所有码字可能产 生的
15、尾随后缀全部列出。由此得到码C的所有可能的尾 随后缀组成的集合A。 * 31 p例：现设C=0，10，1100，1110，1011，1101，来判断是否 是惟一可译码。 n解法一： p首先码字C是非奇异码，又由题知，信源符号数为q=6，输出信源 的码符号数为r=2，根据kraft不等式得， 满足kraft不等式。 p最后画出树图，如下图所示。又图知，该码是前缀码，所以还无 法判断是否是惟一可译码。 * 32 p解法二（根据A.A.Sardinas和G.W.Patterson算法）：因为 最短码字为“0”，不是其他码字的前缀，所以它没有尾随后 缀。观察码字“10”，它是码字“1011”的前缀，所
16、以有 尾随 后缀。根据下图可得，A=11，00，10，01，0，1，100， 110，011，101。可见，A集中“10”和“0”都是码字，故码C 不是惟一可译码。（对00，码字0是它的前缀，所以有尾随 后缀0） * 33 5.2 无失真信源编码 * 34 无失真信源编码 p信源编码器输入的消息序列: X=(X1 X2Xl XL), Xla1,an, 输入的消息总共有nL种可能的组合 p输出的码字为: Y=(Y1 Y2 Yk YKL ) , Ykb1,bm 输出的码字总共有mKL种可能的组合。 信源编码器 码表 信源信道 X Y L长序列 KL长码 字 * 35 无失真信源编码 p实现无失真无失真的信源编码,要求: n信源符号X1 X2Xl XL 是一一对应的 n 码字Y1 Y2Yk YKL p能够无失真或无差错地从Y恢复X,也就是能正确地 进行
