信息论与编码 第5章(1)

1、2022-1-21信源编码信源编码 第第5 5章章(第第1讲）讲）2022-1-22数字通信系统的一般模型数字通信系统的一般模型 等效信道等效信道 干扰源干扰源 物理信道物理信道 解调器解调器 编码器编码器 译码器译码器 信宿信宿 信源信源 调制器调制器 实际信道实际信道 编码信道编码信道 2022-1-23p信息通过信道传输到信宿的过程即为信息通过信道传输到信宿的过程即为通信通信。要做到。要做到既不失真又快速地通信，需要解决两个问题：既不失真又快速地通信，需要解决两个问题：n在不失真或允许一定失真条件下，在不失真或允许一定失真条件下，如何提高信息如何提高信息传输速度传输速度-这是本章要讨论的

2、这是本章要讨论的信源编码信源编码问题问题.n在信道受到干扰的情况下，在信道受到干扰的情况下，如何增加信号的抗干如何增加信号的抗干扰能力，同时又使得信息传输率最大扰能力，同时又使得信息传输率最大-这是下这是下章要讨论的章要讨论的信道编码信道编码问题问题.2022-1-242022-1-25u信源编码分为信源编码分为无失真和限失真无失真和限失真。u无失真编码无失真编码，又名，又名冗余度压缩冗余度压缩编码：仅对信源的冗余度进编码：仅对信源的冗余度进行压缩，行压缩，不改变信源的熵不改变信源的熵；可逆编码的基础，只适用于离；可逆编码的基础，只适用于离散信源，主要用于文字、数据信源的压缩。散信源，主要用于

3、文字、数据信源的压缩。u限失真编码限失真编码，又名，又名熵压缩熵压缩编码：在失真受限的情况下进行编码：在失真受限的情况下进行限失真编码。只适用于连续信源，主要用于图像、语音信限失真编码。只适用于连续信源，主要用于图像、语音信源的压缩。源的压缩。p信源编码的基础是信息论中的两个编码定理信源编码的基础是信息论中的两个编码定理n无失真信源编码无失真信源编码 第一极限定理第一极限定理 n限失真信源编码限失真信源编码 第三极限定理第三极限定理p信道编码定理（离散和连续信道）信道编码定理（离散和连续信道） 第二极限定理第二极限定理2022-1-26信源编码的主要任务信源编码的主要任务n减少冗余，提高编码效

4、率减少冗余，提高编码效率。具体的说，就是针对信源输。具体的说，就是针对信源输出符号序列的统计特性，寻找一定的把信源输出符号序出符号序列的统计特性，寻找一定的把信源输出符号序列变换为最短码字序列的方法。列变换为最短码字序列的方法。n符号变换：使信源输出符号与信道的输入符号相匹配。符号变换：使信源输出符号与信道的输入符号相匹配。p信源编码的信源编码的基本途径基本途径有两个有两个: :n一是编码后使序列中的各个符号之间尽可能地互相独立，一是编码后使序列中的各个符号之间尽可能地互相独立，即即解除相关性解除相关性-方法包括预测编码和变换编码方法包括预测编码和变换编码. .n二是使编码后各个符号出现的概率

5、尽可能相等，即二是使编码后各个符号出现的概率尽可能相等，即均匀均匀化分布化分布-方法主要是统计编码方法主要是统计编码. .2022-1-27p本章主要介绍信源编码的基本思路与主要方法，讨本章主要介绍信源编码的基本思路与主要方法，讨论论离散信源编码离散信源编码，首先从，首先从无失真编码定理无失真编码定理出发，重出发，重点讨论以点讨论以香农码香农码、费诺码费诺码和和哈夫曼码哈夫曼码为代表的最佳为代表的最佳无失真码。然后介绍了无失真码。然后介绍了限失真编码定理限失真编码定理。最后简单。最后简单介绍了一些其它常用的信源编码方法。期望通过本介绍了一些其它常用的信源编码方法。期望通过本章学习能建立起信源压

6、缩编码的基本概念。章学习能建立起信源压缩编码的基本概念。2022-1-285.1 编码的定义编码的定义5.2 无失真信源编码无失真信源编码5.3 限失真信源编码限失真信源编码5.4 常用信源编码方法简介常用信源编码方法简介主主 要要 内内 容容2022-1-295.1 5.1 编码的定义编码的定义2022-1-210编码的定义编码的定义p编码定理证明编码定理证明: :n必存在一种编码方法必存在一种编码方法, ,使使代码的平均长度代码的平均长度可任意可任意接近但接近但不能低于符号熵不能低于符号熵; ;n达到这目标的途径就是使达到这目标的途径就是使概率与码长匹配概率与码长匹配。p统计匹配编码统计匹

7、配编码：n根据信源的根据信源的不同概率分布不同概率分布而选用与之匹配的编而选用与之匹配的编码码, ,以达到在系统中以达到在系统中传信速率最小传信速率最小。2022-1-211p编码器的作用：编码器的作用：p 将信源符号集将信源符号集X中的符号中的符号 变换成由码符号集变换成由码符号集y中的中的码元码元 组成的长度为组成的长度为KL的一一对应的的一一对应的码字码字 。p 码字集合叫做代码组码字集合叫做代码组Y；码字；码字 所含码元的个数称为该码字所含码元的个数称为该码字的的码长码长，记为，记为KL 。1,2,iXiq1,2,iy imiYiY12,qXXXX12, ,qYY YY 编码器编码器信

8、源符号集信源符号集X代码组代码组Y基本符号基本符号y12, ,myy yy编码的定义编码的定义2022-1-212如果信源输出符号序列长度如果信源输出符号序列长度L1，信源符号集，信源符号集A(a1，a2，an)，信源概率空间为，信源概率空间为 )()()(2121nnapapapaaaPX若将信源若将信源X通过二元信道传输，就必须把信源符通过二元信道传输，就必须把信源符号号ai变换成由变换成由0，1符号组成的码符号序列，这个符号组成的码符号序列，这个过程就是信源编码。过程就是信源编码。 编码的定义编码的定义2022-1-213信源符号信源符号信源符号信源符号概率概率 码码 表表 码码1 码码

9、2 00 0 01 01 10 001 11 111 ia1a2a3a4a)(iap)(1ap)(2ap)(3ap)(4app若码集为若码集为0,1,所得码字为所得码字为二元序列二元序列,称为称为二元码二元码p例如例如,信源符号信源符号Xa1,a2,a3,a4,对应不同码字如表对应不同码字如表编码的定义编码的定义2022-1-214编码的定义编码的定义信源符号信源符号 信源符号信源符号出现概率出现概率 码码 表表 码码0码码1码码2码码3码码4a1p(a1)=1/2000011a2p(a2)=1/40111101001a3p(a3)=1/8100000100001a4p(a4)=1/81111

10、0110000001p等长码等长码：码中所有码字的长度都相同：码中所有码字的长度都相同p可变长码可变长码：码中的码字长短不一：码中的码字长短不一两种码：固定长度和可变长度的编码。两种码：固定长度和可变长度的编码。2022-1-215分组码的属性：分组码的属性：(1)奇异码和非奇异码：奇异码和非奇异码：p非奇异码非奇异码：如果信源符号和码字是一一对应的，则称该：如果信源符号和码字是一一对应的，则称该码为非奇异码。如码码为非奇异码。如码0,2,3,40,2,3,4p奇异码奇异码：如果信源符号和码字不是一一对应的，则称该：如果信源符号和码字不是一一对应的，则称该码为奇异码。如码码为奇异码。如码1 1

11、分组码分组码/块码块码：将信源符号集：将信源符号集X中的每个符号中的每个符号 映射成一个映射成一个固定固定的码字的码字 。这种码必须具有。这种码必须具有某些属性，才能保证在接收端能够迅速可靠地译码。某些属性，才能保证在接收端能够迅速可靠地译码。1,2,iXiq1,2,iYiq编码的定义编码的定义2022-1-216编码的定义编码的定义(2)(2)唯一可译码唯一可译码：n任意有限长的码元序列任意有限长的码元序列,只能被唯一地分割成一只能被唯一地分割成一个个的码字。个个的码字。p例：例：0,10,11是一种唯一可译码。是一种唯一可译码。p任意一串有限长码序列任意一串有限长码序列,如如1001110

12、00,只能被分只能被分割成割成10,0,11,10,0,0。任何其他分割法都会产生。任何其他分割法都会产生一些非定义的码字。一些非定义的码字。p奇异码不是唯一可译码奇异码不是唯一可译码p非奇异码非奇异码 n唯一可译码唯一可译码 码码3 100,1,1,1000n非唯一可译码非唯一可译码 码码2 100001002022-1-217(2)唯一可译码：唯一可译码：例如：例如：信源信源概率概率pi 编码编码编码编码编码编码编码编码编码编码U11/2000111U21/4010101001U31/810100100001U41/811100110000001对于码元序列对于码元序列1001110001

13、10，分别用编码，分别用编码1，编码编码3，编码，编码4，试判断那种是唯一可译码？，试判断那种是唯一可译码？2022-1-218编码的定义编码的定义 p非即时码非即时码：n如果接收端收到一个完整的码字后不能立即译码如果接收端收到一个完整的码字后不能立即译码,还还需等下一个码字开始接收后才能判断是否可以译码需等下一个码字开始接收后才能判断是否可以译码p即时码（非延长码，异前缀码）即时码（非延长码，异前缀码）：n在译码时无需参考后续的码符号就能在译码时无需参考后续的码符号就能立即立即作出判断作出判断,译成对应的信源符号。译成对应的信源符号。n任意一个码字都任意一个码字都不是不是其它码字的其它码字的

14、前缀前缀部分部分p在在延长码延长码中中,有的码是唯一可译的有的码是唯一可译的,取决于码的总体结取决于码的总体结构构,如码如码3, “1,10,100,1000”.2022-1-219例如：例如：信源信源概率概率pi 编码编码编码编码编码编码编码编码编码编码U11/2000000U21/401011001U31/810100110011U41/81110111110111试判断编码试判断编码4和编码和编码5是否为即时码？是否为即时码？2022-1-220编码的定义编码的定义码码非分组码非分组码 分组码分组码奇异码奇异码 非奇异码非奇异码 非唯一可译码非唯一可译码 唯一可译码唯一可译码非即时码非即

15、时码 即时码即时码 (非延长码非延长码) 2022-1-221p码树从树根开始向下长出码树从树根开始向下长出m个树枝，成为个树枝，成为m进制码树，进制码树，树枝代表码元，树枝与树枝的交点叫做树枝代表码元，树枝与树枝的交点叫做节点节点。经过。经过r个树枝才能到达的节点称为个树枝才能到达的节点称为r阶节点阶节点。向下不长出树。向下不长出树枝的节点称为枝的节点称为终端节点终端节点或或端点端点。m进制码树各节点进制码树各节点（包括树根）向下长出的树枝不会超过（包括树根）向下长出的树枝不会超过m,若树码的若树码的各个分支都延伸到最后一级端点称为各个分支都延伸到最后一级端点称为满树满树（整树），（整树），

16、否则称为非满树非整树。否则称为非满树非整树。p码树上任一节点都对应一个码字，组成该码字的码码树上任一节点都对应一个码字，组成该码字的码元就是从树根开始到该节点所经过的树枝（码元）。元就是从树根开始到该节点所经过的树枝（码元）。p一个码，如果其所有的码字均处于终端节点，即端一个码，如果其所有的码字均处于终端节点，即端点，则该码就为非延长码。点，则该码就为非延长码。编码的定义编码的定义-用码树来构造码字用码树来构造码字2022-1-222p码树：表示各码字的构成（码树：表示各码字的构成（m进制）进制） A0100000000000001111111011111二进制码树20000011111222

17、22三进制码树树根码字的起点 分成m个树枝码的进制数终端节点码字1101中间节点码字的一部分节数码长2022-1-223码411110001010010001码400001110101101110p树码树码n如果有如果有n个信源符号个信源符号,那么在码树上就要选择那么在码树上就要选择n个个终终端节点端节点,用相应的用相应的r元基本符号表示这些码字。元基本符号表示这些码字。码001001111100100p任一任一即时码即时码都可用树图都可用树图法来表示。法来表示。p当码字长度给定当码字长度给定,即时即时码不是唯一的。码不是唯一的。 2022-1-22411010001001000p码码3对应的

18、树如下图对应的树如下图:编码的定义编码的定义p该码树从根到终端节点所经路径上每一个该码树从根到终端节点所经路径上每一个中间节中间节点皆为码字点皆为码字,因此满足前缀条件。因此满足前缀条件。p虽然码虽然码3不是即时码不是即时码,但它是唯一可译码。但它是唯一可译码。 2022-1-225编码的定义编码的定义p满树：满树：n每个节点上都有每个节点上都有r个分枝的树个分枝的树等长码等长码p非满树：非满树：n变长码变长码p用树的概念可导出用树的概念可导出唯一可译码唯一可译码存在存在的的充分和必要充分和必要条件条件,即各码字的长度即各码字的长度Ki应符合应符合Kraft不等式不等式式中:m是进制数n是信源

19、符号数11niKim2022-1-226p例例：设二进制码树中：设二进制码树中X=(a1 , a2 , a3 , a4), K1=1,K2=2,K3=2,K4=3,应用应用Kraft不等式不等式,得：得： 不存在满足这种不存在满足这种Ki的唯一可译码的唯一可译码 0001101011011中间中间节节点点p如果将各码字长度改成如果将各码字长度改成K1=1,K2=2,K3=3,K4=3,则则18922222322141iKi122222332141iKi这样的码字就存这样的码字就存在唯一可译码在唯一可译码 1112022-1-227编码的定义编码的定义nKraft不等式只是用来说明唯一可译码是否

20、存在不等式只是用来说明唯一可译码是否存在,并不能作为唯一可译码的判据。并不能作为唯一可译码的判据。n如码字如码字0，10，010，111虽然满足虽然满足Kraft不等不等式式,但它不是唯一可译码。但它不是唯一可译码。2022-1-228唯一可译码的判断法唯一可译码的判断法p方法一根据异前缀码是惟一可译码：方法一根据异前缀码是惟一可译码：n首先观察是否是非奇异码。若是奇异码，肯定不是唯一可首先观察是否是非奇异码。若是奇异码，肯定不是唯一可译码译码n其次，计算是否满足其次，计算是否满足Kraft不等式。若不满足一定不是唯不等式。若不满足一定不是唯一可译码；一可译码；n然后将码画成一棵树图，观察是否

21、满足异前缀码的树图的然后将码画成一棵树图，观察是否满足异前缀码的树图的构造，若满足则是唯一可译码。构造，若满足则是唯一可译码。n缺点：若是前缀码时，则无法判断是否是唯一可译码。缺点：若是前缀码时，则无法判断是否是唯一可译码。2022-1-229惟一可译码的判断准则惟一可译码的判断准则p方法二用方法二用A.A.Sardinas和和G.W.Patterson设计的判断法：设计的判断法：n算法思想：根据惟一可译码的定义可知，当且仅当有限长算法思想：根据惟一可译码的定义可知，当且仅当有限长的码符号序列能译成两种不同的码字序列，则此码是非惟的码符号序列能译成两种不同的码字序列，则此码是非惟一的可译变长码

22、。即如下图情况发生，其中一的可译变长码。即如下图情况发生，其中Ai和和Bi都是码都是码字。在下图中，字。在下图中，B1一定是一定是A1的前缀，而的前缀，而A1的尾随后缀一的尾随后缀一定是另一码字定是另一码字B2的前缀；又的前缀；又B2的尾随后缀又是其他码字的尾随后缀又是其他码字的前缀。最后，码符号序列的尾部一定是一个码字。的前缀。最后，码符号序列的尾部一定是一个码字。A1A2A3AmB1B2B3Bm有限长码符号序列译成两种不同的码字序列2022-1-230pA.A.Sardinas和和G.W.Patterson算法步骤算法步骤n计算分组码中所有可能的尾随后缀集合计算分组码中所有可能的尾随后缀集

23、合A,观察观察A中有中有没有包含任一码字，若无则为唯一可译码；若有则一没有包含任一码字，若无则为唯一可译码；若有则一定不是唯一可译码。定不是唯一可译码。n集合集合A的构造：的构造：p首先观察码首先观察码C中最短的码字是否是其它码字的前缀。若中最短的码字是否是其它码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀是，将其所有可能的尾随后缀排列出。而这些尾随后缀又可能是某些码字的前缀，再将由这些尾随后缀产生的又可能是某些码字的前缀，再将由这些尾随后缀产生的新的尾随后缀列出。新的尾随后缀列出。p然后再观察这些新的尾随后缀是否是某些码字的前缀，然后再观察这些新的尾随后缀是否是某些码字的前缀

24、，再将产生的尾随后缀列出。这样，首先获得由最短的码再将产生的尾随后缀列出。这样，首先获得由最短的码字能引起的所有尾随后缀。字能引起的所有尾随后缀。p接着，按照上述将次短的码字接着，按照上述将次短的码字等等，所有码字可能产等等，所有码字可能产生的尾随后缀全部列出。由此得到码生的尾随后缀全部列出。由此得到码C的所有可能的尾的所有可能的尾随后缀组成的集合随后缀组成的集合A。2022-1-231p例：现设例：现设C=0，10，1100，1110，1011，1101，来判断是否，来判断是否是惟一可译码。是惟一可译码。n解法一：解法一：p首先码字首先码字C是非奇异码，又由题知，信源符号数为是非奇异码，又由

25、题知，信源符号数为q=6，输出信源，输出信源的码符号数为的码符号数为r=2，根据，根据kraft不等式得，不等式得， 满足满足kraft不等式。不等式。p最后画出树图，如下图所示。又图知，该码是前缀码，所以还无最后画出树图，如下图所示。又图知，该码是前缀码，所以还无法判断是否是惟一可译码。法判断是否是惟一可译码。110101010010101010101010010101码字0码字1 0码字1 0 1 1码字1 1 0 0码字1 1 0 1码字1 1 1 012444412222221qliir2022-1-232p解法二（根据解法二（根据A.A.Sardinas和和G.W.Patterson

26、算法）：因为算法）：因为最短码字为最短码字为“0”，不是其他码字的前缀，所以它没有尾随，不是其他码字的前缀，所以它没有尾随后缀。观察码字后缀。观察码字“10”，它是码字，它是码字“1011”的前缀，所以有的前缀，所以有 尾随后缀。根据下图可得，尾随后缀。根据下图可得，A=11，00，10，01，0，1，100，110，011，101。可见，。可见，A集中集中“10”和和“0”都是码字，都是码字，故码故码C不是惟一可译码。（对不是惟一可译码。（对00，码字，码字0是它的前缀，所以是它的前缀，所以有尾随后缀有尾随后缀0）101100100101110100110011101011码字尾随后缀202

27、2-1-2335.2 5.2 无失真信源编码无失真信源编码2022-1-234无失真信源编码无失真信源编码p信源编码器输入的消息序列信源编码器输入的消息序列: X=(X1 X2Xl XL), Xla1,an, 输入的消息总共有输入的消息总共有nL种可能的组合种可能的组合p输出的输出的码字码字为为: Y=(Y1 Y2 Yk YKL ) , Ykb1,bm 输出的码字总共有输出的码字总共有mKL种可能的组合。种可能的组合。信源编码器码表码表信源信源信道信道XYL长序列KL长码字2022-1-235无失真信源编码无失真信源编码p实现实现的信源编码的信源编码,要求要求:n信源符号信源符号X1 X2Xl

28、 XL 是一一对应的是一一对应的n 码字码字Y1 Y2Yk YKLp能够无失真或能够无失真或无差错地从无差错地从Y恢复恢复X,也就是能正确地也就是能正确地进行反变换或译码进行反变换或译码 ;p传送传送Y时所需要的时所需要的信息率最小信息率最小 MLmLKKLlog1log_信息率最小信息率最小就是找到一种编码方式使就是找到一种编码方式使最小最小2022-1-2365.2.1 5.2.1 定长编码定理定长编码定理p在在定长定长编码中编码中,K（KL）是是定值定值。目的是寻找。目的是寻找最小最小K值值。p编码器输入编码器输入X=(X1 X2Xl XL), Xla1,an, 输入的输入的消息总共有消

29、息总共有nL种可能的组合种可能的组合p输出的码字输出的码字Y=(Y1 Y2 Yk YK ) , Ykb1,bm,输出输出的码字总共有的码字总共有mK种可能的组合种可能的组合p若对信源进行若对信源进行定长定长编码编码,必须满足必须满足: nLmK 信源编码器码表码表信源信源信道信道XYL长序列K长码字2022-1-237定长编码定长编码p若对信源进行若对信源进行定长定长编码编码,必须满足必须满足: mnLKmnKLloglog或p只有当只有当K长的码符号序列数长的码符号序列数 mK大于或等于信源的符大于或等于信源的符号数号数nL时时,才可能存在才可能存在定长定长非奇异码。非奇异码。 p例如英文电

30、报有例如英文电报有27个符号个符号,n=27,L=1,m=2(二元编码二元编码)527logloglog222mnLK每个英文电报符号至少要用5位二元符号编码2022-1-238定长编码定长编码p实际英文电报符号信源实际英文电报符号信源,在考虑了符号出现的概率在考虑了符号出现的概率以及符号之间的依赖性后以及符号之间的依赖性后,平均每个英文电报符号平均每个英文电报符号所提供的信息量约等于所提供的信息量约等于1.4比特比特,大大小于大大小于5比特。比特。p编码后编码后5个二元符号只携带约个二元符号只携带约1.4比特信息量。比特信息量。p定长编码的信息传输效率极低。定长编码的信息传输效率极低。202

31、2-1-239定长编码定理定长编码定理p定长编码定理定长编码定理：p由由L个符号组成的、每个符号的熵为个符号组成的、每个符号的熵为HL(X)的无记忆的无记忆平稳信源符号序列平稳信源符号序列X1XlXL,可用可用 K个符号个符号Y1YkYK(每个符号有每个符号有m种可能值种可能值)进行定长编码。进行定长编码。对任意对任意0,0,只要只要 则当则当L足够大时足够大时,必可使译码差错小于必可使译码差错小于;反之反之,当当 时时,译码差错一定是有限值译码差错一定是有限值,而当而当L足够大时足够大时,译码几乎译码几乎必定出错必定出错 )(logXLHmLK2)(logXLHmLK2022-1-240定长

32、编码定理定长编码定理当编码器容许的输出信息率当编码器容许的输出信息率,也就是当每个信源符也就是当每个信源符号所必须输出的码长是号所必须输出的码长是 时时,只要只要 ,这种编码器一定可以做到这种编码器一定可以做到几乎几乎无失真无失真,也就是收端的译码差错概率接近于零也就是收端的译码差错概率接近于零,条件是所取的符号数条件是所取的符号数L足够大足够大。MLmLKKLlog1log_)(_XHKL2022-1-241p将定理的条件改写成将定理的条件改写成其中：其中：左边：左边：KL长码字所能携带的最大信息，长码字所能携带的最大信息， 右边：右边：L长信源序列携带的信息量。长信源序列携带的信息量。lo

33、g()()LLKmLHXH Xp上述定理表明上述定理表明: :n只要码字所能携带的信息量大于信源序列输出的只要码字所能携带的信息量大于信源序列输出的信息量信息量, ,则可以使传输几乎无失真则可以使传输几乎无失真, ,当然条件是当然条件是L足够大。足够大。n反之反之, ,当当 时时, ,不可能构成无失真的编不可能构成无失真的编码码, ,也就是不可能做一种编码器也就是不可能做一种编码器, ,能使收端译码时能使收端译码时差错概率趋于零。差错概率趋于零。n 时时, ,则为临界状态则为临界状态, ,可能无失真可能无失真, ,也可也可能有失真。能有失真。 )(_XHKL)(_XHKL2022-1-242_

34、111234567881,()3/()3/33 000,001,010,011 100,101,110,111LH XbitKH Xbitbitbitxxxxxxxx例如某信源有 种等概率符号，现假设则信源熵达到最大值符号, 设符号（临界状态）所以，该信源肯定可以用的信息速率进行无失真的编码（相当于每一个符号对应一个的码字）。例如定长编码定理的应用例子：定长编码定理的应用例子：2022-1-243定长编码定理的应用例子：定长编码定理的应用例子：概率比较小。小，这时使差错号序列出现的概率特别取值比较大，有一些符如果而会引起差错。但是其它的码字来代替，从现这些符号，也只能用果出有对应的码字，信源如

35、则会有部分信源符号没如果取个码字，所以种信源符号共需要的要求，前面的无失真信源编码种可能的码字，而根据符号共可以表示由于符号此时符号。则有率不相等时，如果信源输出的符号概LKbitbitXHKbitXHapi,55. 2886856. 52/55. 2/55. 2)(/55. 2)(04. 0 ,05. 0 ,06. 0,07. 0 , 1 . 0 , 1 . 0 ,18. 0 , 4 . 0)(_55. 21_12022-1-244定长编码定理定长编码定理p为了衡量编码效果为了衡量编码效果,定义定义编码效率编码效率：0,)()(XHXHLLp对定长编码对定长编码,若要实现几乎无失真编码若要实

36、现几乎无失真编码,则信源长度则信源长度必须满足（必须满足（为差错率为差错率）:22)(XL 22() ( )() iXE I xH Xn信源单符号的自信息方信源单符号的自信息方差差 （离散无记忆）（离散无记忆）KXHL)(p最佳编码效率最佳编码效率：p阐明了编码效率接近阐明了编码效率接近1的理想编码器的存在性，使的理想编码器的存在性，使输出符号信息率与信源熵之比接近于输出符号信息率与信源熵之比接近于12022-1-245例例5-212345678_2.83( )0.40.180.10.10.070.060.050.04()2.55/90%,1() 2.83/27.11,7.118LXaaaaa

37、aaap xH XbitLHXKbit设离散无记忆信源概率空间为：根据信源熵的计算公式可以得到： 符号如果用二元编码，要求编码效率为并且取符号同时由于种来表示 个符号8,0.04a显然不够，如果去掉概率最小的则误码率为。2022-1-246p方差：方差：p若取差错率若取差错率106,编码效率为编码效率为90%(则则=0.28=0.28),则则L应满足应满足22281282. 7)()(log)(bitXHppXiii76222108 . 91028. 082. 7)(XLp在差错率和编码效率要求并不十分苛刻的条件下在差错率和编码效率要求并不十分苛刻的条件下,需需要要L=108个信源符号进行联合

38、编码个信源符号进行联合编码,这显然很难实现这显然很难实现2022-1-2475.2.2 5.2.2 变长编码定理变长编码定理p在在变长变长编码中码长编码中码长K是变化是变化的。的。p我们可根据信源各个符号的我们可根据信源各个符号的统计特性统计特性,如概率大的符如概率大的符号用短码号用短码,概率小的用较长的码概率小的用较长的码,这样在大量信源符这样在大量信源符号编成码后平均每个信源符号所需的输出符号数就号编成码后平均每个信源符号所需的输出符号数就可以降低可以降低,从而提高编码效率从而提高编码效率2022-1-248变长编码定理变长编码定理p单个符号变长编码定理单个符号变长编码定理：n若一离散无记

39、忆信源的符号熵为若一离散无记忆信源的符号熵为H(X),每个信源每个信源符号用符号用m进制码元进行变长编码进制码元进行变长编码,一定存在一种无一定存在一种无失真编码方法失真编码方法,其其码字平均长度码字平均长度满足下列不等式满足下列不等式:()()1 loglogLH XH XKmm2022-1-249变长编码定理变长编码定理p离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理n对于平均符号熵为对于平均符号熵为HL(X)的离散平稳无记忆信源的离散平稳无记忆信源,必存在一种无失真编码方法必存在一种无失真编码方法,使使平均信息率平均信息率 满满足不等式足不等式 ( )( )( ) LLHKHXXKn其中其中为任意小正数为任意小正数logLKKmL2022-1-250变长编码定理变长编码定理p用变长编码来达到相当高的编码效率用变长编码来达到相当高的编码效率,一般所要求的