第五章信源编码(编码定义及定长编码)(课堂PPT).ppt

《第五章信源编码(编码定义及定长编码)(课堂PPT).ppt》由会员分享，可在线阅读，更多相关《第五章信源编码(编码定义及定长编码)(课堂PPT).ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章 信源编码信源编码5.1编码的定义编码的定义5.2无失真信源编码无失真信源编码 5.2.1定长编码定理定长编码定理31456002张安然张安然1回顾：为什么进行信源编码？回顾：为什么进行信源编码？理理论论上上，信信源源传传送送信信息息所所需需要要的的信信息息率率：极极限限熵熵H（X）或信息率失真函数或信息率失真函数R（D）.极极限限熵熵H（X）：多多符符号号离离散散平平稳稳信信源源实实际际上上就就是是原原始始信信源源在在不不断断地地发发出出符符号号，随随着着信信源源之之间间的的依依赖赖关关系系（即即信信源源的的相相关关性性）变变多多，信信源源的的实实际际熵熵越越小小（第第二二章章P

2、32-33证证明明），越越趋趋于于H（X）。所所以以H（X）是是离离散散平平稳稳有有记记忆忆信信源源平平均均每每发发一一个符号提供的信息量的个符号提供的信息量的最小值最小值。2信信息息率率失失真真函函数数R（D）：从从允允许许一一定定失失真真的的条条件件下下，我我们们去去寻寻找找可可以以用用较较小小的的信信息息率率来来传传送送信信息息，即即去去掉掉某某些些不不必必要要的的成成分分，这这时时得得到到的的信信息息率率的的最小值最小值是是R（D）。）。由由此此可可见见，极极限限熵熵H（X）或或信信息息率率失失真真函函数数R（D）是是理理论论上上传传送送信信息息的的最最小小值值。而而实实际际上上，信信

3、源源发发出出消消息息时时包包含含了了多多余余信信息息，即即存存在在冗冗余余度度，冗余度体现了信源输出信号的信息携带效率。冗余度体现了信源输出信号的信息携带效率。3冗余度冗余度定定义义：衡衡量量信信源源发发出出消消息息时时包包含含了了多多余余信信息息的的物物理量理量来源：来源：1.信信源源符符号号的的相相关关性性。相相关关程程度度越越大大，信信源源的的实实际上越小，越趋向于际上越小，越趋向于H（X）。2.信信源源符符号号分分布布的的不不均均匀匀性性。等等概概率率分分布布时时信信源源熵熵最最大大，不不均均匀匀分分布布时时，信信源源熵熵减减小小。当当各各符符号号之之间间不不存存在在依依赖赖关关系系且

4、且为为等等概概率率分分布布时时，信信源源实实际熵趋于最大熵际熵趋于最大熵H0（X）4下面，以英文为例，计算文字信源的冗余度：下面，以英文为例，计算文字信源的冗余度：首先给出英文字母（含空档）出现概率如下：首先给出英文字母（含空档）出现概率如下：5下面，首先求得独立等概率情况，即下面，首先求得独立等概率情况，即其次，计算独立不等概率情况，其次，计算独立不等概率情况，再次，若仅考虑字母有一维相关性，求再次，若仅考虑字母有一维相关性，求H2最最后后，利利用用统统计计推推断断方方法法求求出出，由由于于采采用用的的逼逼近近的的方方法法和和所所取取的的样样本本的的不不同同，推推算算值值也也有有不不同同，这

5、这里里采采用用Shannon的推断值。的推断值。6采用等概率下传送方式，计算得采用等概率下传送方式，计算得这这样样，可可以以计计算算出出R=0.71。这这一一结结论论说说明明，英英文文信信源源，从从理理论论上上看看71是是多多余余成成分分。直直观观地地说说100页页英英文文书书，理理论论上上看看仅仅有有29页页是是有有效效的的，其其余余71页页是是多多余余的的。正正是是由由于于这这一一多多余余量量的的存存在在，才才有有可能对英文信源进行压缩编码。可能对英文信源进行压缩编码。消消息息的的冗冗余余，特特别别是是大大量量的的冗冗余余，为为我我们们提提高高通通信信效效率率，压压缩缩信信号号容容量量提提

6、供供了了基基础础。为为了了提提高高传传输效率，对大量冗余进行压缩，即信源编码。输效率，对大量冗余进行压缩，即信源编码。7信源编码信源编码信源编码是以提高通信的有效性为目的信源编码是以提高通信的有效性为目的编码。编码。采用的一般方法是压缩每个信源符号的采用的一般方法是压缩每个信源符号的平均比特数。同样多的信息用较少的信平均比特数。同样多的信息用较少的信息率来传送，使单位时间内传送的平均息率来传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。信息量增加，从而提高通信的有效性。信源编码的目的就是要减少冗余，提高编信源编码的目的就是要减少冗余，提高编码效率码效率。8信信源源编编码码的的基基

7、本本途途径径（即即消消除除冗冗余余度度来源的途径）有两个：来源的途径）有两个：使使序序列列中中的的各各个个符符号号尽尽可可能能地地互互相相独独立，即解除相关性；立，即解除相关性；使使编编码码中中各各个个符符号号出出现现的的概概率率尽尽可可能能地相等，即概率均匀化。地相等，即概率均匀化。9 根根据据能能否否在在解解码码后后完完全全准准确确的的恢恢复复出出原原始始消消息息（可逆）分为：（可逆）分为：无失真信源编码无失真信源编码 限失真信源编码限失真信源编码 无无失失真真编编码码只只适适用用于于离离散散信信源源；对对于于连连续续信信源源，只只能能在在失失真真受受限限制制的的情情况况下下进进行行限限失

8、失真真编编码码。前前者者主主要要用用于于文文字字、数数据据信信源源的的压压缩缩;后后者者主主要要用用于于图像、语音信源的压缩。图像、语音信源的压缩。10 一一般般地地：由由于于这这些些定定理理都都要要求求符符号号数数很很大大（参参考考极极限限熵熵H（X）序序列列长长趋趋向向于于）才才能能使使它它的的值值接接近所规定的值，因而这些定理被称为近所规定的值，因而这些定理被称为极限定理。极限定理。1.无失真信源编码定理称为无失真信源编码定理称为第一极限定理第一极限定理；2.信信道道编编码码定定理理(包包括括离离散散和和连连续续信信道道)称称为为第第二二极极限定理；限定理；3.限失真信源编码定理称为限失

9、真信源编码定理称为第三极限定理第三极限定理。这些定理的完善化，是这些定理的完善化，是香农信息论香农信息论的主要内容。的主要内容。11编编码码定定理理不不但但证证明明了了必必然然存存在在一一种种编编码码方方法法，使使代代码码的的平平均均长长度度可可任任意意接接近近但但不不能能低低于于符符号号熵熵，而而且且还还阐阐明明了了达达到到这这目目标标的的途途径径，就就是是使使概概率率与与码长匹配。码长匹配。例例如如之之后后学学习习的的变变长长编编码码，使使出出现现概概率率小小的的信信源源符符号号用用短短码码编编，出出现现概概率率大大的的用用长长的的码码编编，这这样样就就可可以以使使平平均均每每个个信信源源

10、符符号号的的输输出出符符号号降降低低。以以哈夫曼编码为例：哈夫曼编码为例：12哈哈夫夫曼曼编编码码的的编编码码结结果果可可以以看看出出，信信源源出出现现符符号号小小的的a7编编码码长长度度是是4位位，信信源源出出现现符符号号小小的的a1编编码码长长度度是是2位位，平平均均码长计算得码长计算得2.72码元码元/符号，输出符号码长减小。符号，输出符号码长减小。13信源编码（主要内容）信源编码定理信源编码定理v信源编码基本概念信源编码基本概念v定长信源编码定长信源编码v变长信源编码变长信源编码信源编码方法信源编码方法 离散信源编码离散信源编码 连续信源编码连续信源编码 相关信源编码相关信源编码 变换

11、编码变换编码145.1编码的定义编码的定义分分组组码码定定义义：将将信信源源消消息息分分成成若若干干组组，即即符符号号序序列列Xi=xi1,xi2,.,xiL,序序列列中中的的每每一一个个符符号号取取自自于于符符号号集集A，xil属属于于a1，a2，ai，an，而而每每个个符符号号序序列列Xi依依照照固固定定的的码码表表映映射射成成一一个个码码字字Yi，这样的码称为分组码，有时也叫块码。这样的码称为分组码，有时也叫块码。分分组组码码百百科科定定义义：它它把把信信源源待待发发的的信信息息序序列列按按固固定定的的位位一一组组划划分分成成消消息息组组,再再将将每每一一消消息息组组独独立立变变换换成成

12、长长为为n(n)的的二二进进制制数数字字组组,称称为为码码字字。如如果果消消息息组组的的数数目目为为M(显显然然M2),由由此此所所获获得得的的M个个码码字字的的全全体体便便称称为为码码长长为为n、信信息息数数目目为为M的的分分组码组码,记为记为【n，M】。15只有分组码才有对应的码表，而非分组码中不存在码表。只有分组码才有对应的码表，而非分组码中不存在码表。编编码码定定义义：二二元元信信道道（基基本本符符号号0,1）中中，若若将将信信源源X通通过过这这样样的的二二元元信信道道传传输输，就就必必须须把把信信源源符符号号ai 变变换换成成有有1.0符符号组成的码符号序列，这个过程就是信源编码。号

13、组成的码符号序列，这个过程就是信源编码。编编码码的的广广泛泛定定义义：编编码码是是信信息息从从一一种种形形式式或或格格式式转转换换为为另另一一种种形形式式的的过过程程也也称称为为计计算算机机编编程程语语言言的的代代码码简简称称编编码码。用用预预先先规规定定的的方方法法将将文文字字、数数字字或或其其它它对对象象编编成成数数码码，或或将信息、数据转换成规定的电脉冲信号。将信息、数据转换成规定的电脉冲信号。我们之后介绍的是二元信道中的编码。我们之后介绍的是二元信道中的编码。16信源编码器示意图信源符号集信源符号集X Xaa1 1,a,a2 2,a an n：代表信源发出的消息，共有代表信源发出的消息

14、，共有n n个信源符号。个信源符号。码表（码符号集）码表（码符号集）码符号集中的元素称为码元或者码符号，适合信道传输。码符号集中的元素称为码元或者码符号，适合信道传输。码字集合码字集合Y=WY=W1 1,W,W2 2,W Wn n：与信源符号一一对应，码字由码符号序列组成。与信源符号一一对应，码字由码符号序列组成。17一个简单的编码实例一个简单的编码实例【例例】对学生的成绩等级进行编码，分为优、良、对学生的成绩等级进行编码，分为优、良、中、差中、差4 4个个 等级。等级。信源符号集信源符号集X Xaa1 1,a,a2 2,a an n=优、良、中、差优、良、中、差 用二元码，码符号集合为用二元

15、码，码符号集合为0,10,1码字集合为码字集合为 Y=WY=W1 1,W,W2 2,W Wn n=00,01,10,1100,01,10,11编码过程：编码过程：0000代表优，代表优，0101代表良，代表良，1010代表中，代表中，1111代代表差。每一个码字都是表差。每一个码字都是2 2个码符号组成的序列。个码符号组成的序列。18信源符号信源符号符符号号出出现现概概率率p(ai)码码1码码2码码3码码4a11/20011a21/411101001a31/80000100001a41/811011000000119(1)奇异码与非奇异码书书中中定定义义：若若信信源源符符号号和和码码字字是是一

16、一一一对对应应的的，则则该该码码是是非非奇奇异异码码；反反之之，是是奇奇异异码码。这这个个定定义义可可以以理理解解为为数数学学意意义义上上的的映映射射，每每一一个个符符号号均均可可以以在码字集合中找到唯一对应的码。在码字集合中找到唯一对应的码。华华中中科科技技大大学学书书中中定定义义：若若一一种种码码中中的的所所有有码码字字都都互互不不相相同同，则则称称此此分分组组码码为为非非奇奇异异码码，否否则则称称为奇异码。为奇异码。可可以以看看出出，表表中中码码1是是奇奇异异码码，有有两两个个11码码。其其他他是非奇异码是非奇异码20（2）唯一可译码书书中中定定义义：任任意意有有限限长长序序列列，只只能

17、能被被分分割割成成一一个个个个的的码码字字，便便可可以以称称为唯一可译码。为唯一可译码。例例如如给给定定一一个个信信源源,编编码码后后的的码码字字有有0,，10，11，就就是是说说信信源源只只能能变变出出这这三三种种码码字字。任任意意给给定定一一个个序序列列100111000，按按照照分分割割成成信信源源定定义义的的三三种种码码字字可可以以分分成成10,0,11,10,0,0唯唯一一一一种种方方式式。任任何何其其他他分分割割法法都都会产生信源不能发出的码字。这种码字就是唯一可译码会产生信源不能发出的码字。这种码字就是唯一可译码码码1是是奇奇异异码码，必必定定不不能能唯唯一一可可译译，因因为为如

18、如果果分分到到11码码，就就不不确确定定是是信源发的信源发的a2还是还是a4码码2也也不不是是唯唯一一可可译译码码，看看码码2的的码码字字特特点点，若若是是序序列列中中有有一一段段码码是是00，我们即可以分成，我们即可以分成00对应对应a3，也可以分成，也可以分成0,0对应发两次对应发两次a1.码码3是是唯唯一一可可译译码码。因因为为分分解解时时只只要要遇遇到到1就就看看后后面面有有几几个个0，确确定定唯唯一译码一译码21（3）非即时码和即时码）非即时码和即时码书书中中定定义义：如如果果接接受受端端收收到到一一个个完完整整的的码码字字后后，不不能能立立即即译译码码，还还需需要要等等下下一一个个

19、码码字字开开始始接接受受后后才能判断是否可以译码，这样的码叫做非即时码。才能判断是否可以译码，这样的码叫做非即时码。一一个个唯唯一一可可译译码码成成为为即即时时码码的的充充要要条条件件是是其其中中任任何一个码字都不是其它码字的前缀（前缀问题）何一个码字都不是其它码字的前缀（前缀问题）这这里里是是建建立立在在唯唯一一可可译译码码基基础础上上的的，表表中中码码3码码4是唯一可译码。是唯一可译码。码码3，接接到到0后后不不能能确确定定到到某某个个码码，码码4只只要要接接到到1就确认是哪个码了。就确认是哪个码了。2223消息消息概率概率C1C2C3C4C5C6u11/2000000101u21/400

20、1011010000001u31/160100111101101001100u41/16011011111101100010101u51/1610001111111101001110110u61/16101011111111110111111011124(1)哪些是唯一可译码（2）哪些是即时码（3）计算平均码长和编码效率25树图法树图法对于对于m进制树图，有树根、树枝和节点。进制树图，有树根、树枝和节点。p树图最顶部的节点称为树根；树图最顶部的节点称为树根；p每一个分支称为树枝；每一个分支称为树枝；p树树枝枝的的尽尽头头称称为为节节点点，每每个个节节点点生生出出的的树树枝枝数数目目等于码符号数

21、等于码符号数m；p从从树树根根到到终终端端节节点点各各树树枝枝代代表表的的码码符符号号顺顺次次连连接接，就得到了编码码字。就得到了编码码字。26m2的二进制树图27整树与非整树考虑一个树有r阶节点p整树：码树的各个分支都延伸到最后一级端点，此时，将共有mr个码字；p非整树：码树中存在分支，没有延伸到最后一级端点，此时，将少于mr个码字。28整树图例29非整树图例30即时码的构造树图法即时码的构造树图法编编码码：用用树树图图法法构构造造即即时时码码，只只要要将将信信源源符符号号全全部部对对应应于于终终端端节节点点，而而不不是中间节点即可。这样就可以保证任何一个码字都不是其它码字的前缀是中间节点即

22、可。这样就可以保证任何一个码字都不是其它码字的前缀解解码码：按按照照码码符符号号的的顺顺序序，从从根根节节点点依依次次查查询询到到终终端端节节点点，就就得得到到对对应应的的信信源源符符号号。再再从从根根节节点点对对剩剩下下的的码码符符号号序序列列做做相相同同的的处处理理，直直到到处处理理完完码码符号序列中所有的码符号符号序列中所有的码符号对应表中的码对应表中的码4 4分析分析31唯一可译码唯一可译码存在存在的充要条件的充要条件克劳夫特不等式：克劳夫特不等式：m是进制数，是进制数，n是信源符号数是信源符号数1.唯一可译码必定满足不等式唯一可译码必定满足不等式2.满满足足不不等等式式的的码码存存在

23、在唯唯一一可可译译码码，但但不不一一定定是是唯一可译码唯一可译码此定理只证明存在性此定理只证明存在性32例题p8833无失真信源编码概念无失真信源编码无失真信源编码：o要求精确地复现信源的输出o保证信源的全部信息无损的送给信宿研究方法研究方法：o只考虑有效性，不考虑可靠性o将信道编解码看成一个无噪无损信道34输输入入序序列列X长长度度L，每每一一位位n种种可可能能。编编码码后后Y的的长长度度是是KL，每每一一位位m种种可能。可能。北京邮电大学周炯槃的书北京邮电大学周炯槃的书中解释无失真条件：中解释无失真条件：无失真：无失真：nL mK(每个消息序列有对应的编码码组每个消息序列有对应的编码码组)

24、信信源源输输出出有有效效：nL 大大于于等等于于mK（编编码码输输出出的的码码组组数数小小于于信信源源消消息息序序列总数）列总数）信源编码输入输出XX1,X2,XLYY1,Y2,YKL35由无失真条件可得：36编编码码的的目目的的：希希望望传传送送Y时时所所需需的的信信息息率率（信信息息率率是是通通过过接接收收到到的的信信息息可可获获得得的的发发送送信信息息的的信信息息量量,即即互互信信息息。单单位位:bit/符号）最小。符号）最小。序序列列Y的的最最大大信信息息量量是是Klogm(序序列列长长乘乘以以每每个个符符号号的的最最大信息熵大信息熵)所以送一个信源符号所以送一个信源符号x需要的平均信

25、息率为：需要的平均信息率为：信息率最小就是找到一种编码方式使信息率最小就是找到一种编码方式使 最小。最小。375.2.1定长编码定理定长编码定理n定义：各个码字码长都相等的码定义：各个码字码长都相等的码 n定长码中每个码字长度相等，所以只要定长码是非奇异定长码中每个码字长度相等，所以只要定长码是非奇异码，则必为唯一可译码码，则必为唯一可译码38消息消息概率概率C1C2C3C4C5C6u11/2000000101u21/4001011010000001u31/160100111101101001100u41/16011011111101100010101u51/16100011111111010

26、01110110u61/16101011111111110111111011139唯一可译定长码的存在条件唯一可译定长码的存在条件o对一个简单信源X进行定长编码，信源X存在唯一可译定长码的条件是：nmKn其中，n是信源X的符号个数，m是信道基本码符号数，K 是定长码的码长。n此为华中科技大学书中给出的定理。40o英文电报有32个符号，即n32，n26个英文字母加上6个标点符号o采用二元码时，则m2。o对信源X的逐个符号xi,i1,2,32进行二元编码，则 322Ko这就是说，每个英文电报符号至少要用5位二元符号进行编码才能得到唯一可译码41定长信源编码定理（香农第一等长编码公式）定长信源编码定

27、理（香农第一等长编码公式）o定理内容：由L个符号组成的，每个符号的熵为HL（X）的无记忆平稳信源符号XX1,X2,XL，编码K个符号YY1,Y2,YKL（每个符号m种可能）对任意0,0，只要满足n则当L足够大时，必可使译码差错小于。o反之，若n则当L足够大时，可以实现几乎无失真编码，译码错误概率趋于1，几乎必定出错。42定长信源编码定理的意义：o信源经过定长编码后，所能携带的信息量，一定要大于信源所携带的平均信息量(熵)。o若是小于，肯定不能无失真o若是等于，是临界状态。可能失真，也可能不失真。43例例如如某某信信源源有有8种种符符号号，L=1，信信源源序序列列熵熵=log8=3bit/符符号

28、。说明可以用号。说明可以用3bit的信息屡进行无失真编码。的信息屡进行无失真编码。采采用用二二进进制制，0,1，等等概概时时lb8=3 bit/符符号号（这这是是等等概概信信源的）源的）若信源非等概，若信源非等概，p(ai)=0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04,则则 H(X)=2.55 bit/符符 号号 的的 信信 息息 率率 在在 二二 进进 制制 中中 可可 以以 表表 示示22.55=5.856种种码码字字，还还有有部部分分符符号号没没有有编编码码，当当出出现现没没编编码码的的符符号号只只能能用用其其他他符符号号代代替替，这这就就是是失失真真。当当

29、L足足够够大大时，有些符号的发生概率变得很小，差错率就变得很小。时，有些符号的发生概率变得很小，差错率就变得很小。44典型序列及非典型序列的说明典型序列及非典型序列的说明引入信源的不等概统计特性后，无需将信源所有符号序列编码，仅对大概率典型序列编码，小的不编码（会失真），下面介绍北北京京邮邮电电大大学学周周炯炯槃槃书中的对典型序列及非典型序列的说明：当L足够大时，根据大数定理，其中一些序列的集合会以趋向概率1出现，如果每一个序列等概率出现，这个概率为2-LH（X）（这个计算是先确定等概率的信息上是 log 2-LH（X）这个计算=LH(X),就是是平均每个序列的信息量，L长序列，序列中每个符号

30、信息量是H(X)。）所以证明这个集合就是典型序列集合，共有2 LH（X）个典型序列，只需要对这些序列编码即可。这这一一概概念念对对应应本本书书中中的的互互补补集合。集合。45L增大时，典型序列数目增多，小概率事件概率更小。根据切比雪夫不等式式中，为信源序列的自信息方差，为一正数。当 和 均为定值时，P可以小于任一正数 。信源序列长度L必满足可以看出，L无穷大时，误码概率趋向于0.46信源编码效率信源编码效率对于等长编码，编码效率一定是小于或等于1的数。对同一信源来说，若码的平均码长越短，信息传输率就越高，这时也越接近1。所以编码效率可以用来衡量各种编码方法在有效性方面的优劣。47上面介绍到了，

31、L无限长时，实际编码长变小，越接近最小可能码长。看下面的例子：设离散无记忆信源概率空间为信源熵为对信源符号采用定长二元编码，要求编码效率为若取L=1，则可以算出：即每个符号用2.83bit进行定长二元编码，共有7.11种可能性，按7种算，有一个符号没有对应的码字，取概率最小的a8，差错仍0.04，太大。48试想信源发送的L很大时，可以用编码效率的公式计算：信源序列的自信息方差为若要求译码错误概率则可见，一定错误概率下，要对L=108个信源符号一起编码，对存储和处理要求太高，无法实现。49如果不限制编码效率，用3bit信息率（即H(X)+=3）来对8个符号编码，L=1，有8种可能性，正好实现无差

32、错译码，。这种情况，L足够大关于差错概率的公式不适用了。但此时编码效率 为2.55/3=85%。因此一般来说，当L有限时，高传输效率的定长码往往引入一定的失真和错误，它不像变长码那样可以实现无失真编码。定长编码在理论上可以达到很高的编码效率，但是从上例中可以看到，在编码效率、错误概率要求较严格的情况下，扩展次数L需要非常大，这在实际工程中是无法实现的。在实际过程中，普遍使用变长编码。50定长编码与变长编码比较定长编码与变长编码比较定长编码要实现无失真定长编码要实现无失真,需要的编码长度大需要的编码长度大,效率不高。效率不高。变变长长编编码码的的编编码码长长度度不不需需要要很很大大就就可可以以达

33、达到到相相当当高高的的编编码码效效率率,而而且且可可以以实实现现无无失失真真编编码码.香香农农编编码码、费费诺诺编编码码和和哈哈夫曼编码是常见的离散无记忆信源编码方法夫曼编码是常见的离散无记忆信源编码方法.采采用用变变长长编编码码L不不需需要要很很大大就就可可以以达达到到相相当当高高的的编编码码效效率率，而而且且可可以以实实现现元元失失真真编编码码。且且随随着着L的的增增大大编编码码效效率率越越来来越越接接近近于于1。（张张晓晓梅梅 常常见见离离散散信信源源编编码码方方法法的的比比较较【J】.福建电脑，福建电脑，2009,5,48-52）51参考文献参考文献1曹雪虹。信息论与编码（第二版）。北京。清华大学出版社2周炯槃。通信原理（第3版）。北京;人民邮电出版社3陈运。信息论与编码（第二版）。北京：电子工业出版社4张晓梅 常见离散信源编码方法的比较【J】.福建电脑，2009,5,48-525253