2.8 无失真信源编码(1).ppt

《2.8 无失真信源编码(1).ppt》由会员分享，可在线阅读，更多相关《2.8 无失真信源编码(1).ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第二章 基本信息论2.8 无失真信源编码(一)2.8 无失真信源无失真信源编码编码(一一)一、一、引言引言四四、传输效率与编码效率传输效率与编码效率二二、基本概念基本概念三三、码树图码树图2第二章 基本信息论2.8 无失真信源编码(一)1.信源编码的主要任务信源编码的主要任务使信源消息符号与信道能够传输使信源消息符号与信道能够传输的的(数字数字)符号相符号相匹配。匹配。一、引言一、引言变换变换压缩压缩具体地说，通过变换使信源符号具体地说，通过变换使信源符号与与(数字数字)代码代码相对应。相对应。(汉字的区位码、四角号码汉字的区位码、四角号码)提高有效性或提高有效性或传输效率传输效率，信道传输

2、时，尽可能充分地利用信道容量。信道传输时，尽可能充分地利用信道容量。使编码后的使编码后的(数字数字)代码经过代码经过3第二章 基本信息论2.8 无失真信源编码(一)2.信源编码的分类信源编码的分类仅对信源的仅对信源的冗余度冗余度(或剩余度或剩余度)进行进行压缩。压缩。允许在一定的失真限制条件下允许在一定的失真限制条件下对信源进行压缩对信源进行压缩。一、引言一、引言必须是可逆的，即必须是可逆的，即信源符号可由代码完全恢复信源符号可由代码完全恢复。本节仅讨论本节仅讨论无失真编码无失真编码，重点介绍，重点介绍范诺码范诺码和和霍夫曼码霍夫曼码。无失真编码无失真编码限失真编码限失真编码不改变信源熵，即信

3、源的信息完全被保留不改变信源熵，即信源的信息完全被保留。将会降低信源熵，即信源的信息被部分丧失将会降低信源熵，即信源的信息被部分丧失。4第二章 基本信息论2.8 无失真信源编码(一)二二、基本概念基本概念1.编码器编码器消息符号集消息符号集基本符号集基本符号集(码码元，生成元，生成 m 元元代码代码)比如比如码元码元生成二元代码；生成二元代码；码元码元生成三元代码。生成三元代码。(已知概率分布已知概率分布 )消息符号集消息符号集 X基本符号集基本符号集 A编码器编码器(数字数字)代码集代码集 W5第二章 基本信息论2.8 无失真信源编码(一)二二、基本概念基本概念1.编码器编码器(数字数字)代

4、码集代码集(码字码字)编码编码1-1 对应对应其中，其中，称为称为码长码长；称为称为平均码长平均码长。注注(1)本教材仅考虑本教材仅考虑二元代码二元代码；(2)每个码元占用的时间相等每个码元占用的时间相等(称为称为同价码同价码)。(码字集合码字集合)消息符号消息符号6第二章 基本信息论2.8 无失真信源编码(一)0101101110码字码字40010110111码字码字3011011码字码字200011011码字码字10.40.30.20.1概率概率x1x2x3x4消息消息010110111码字码字5例如例如消息符号集消息符号集对应的几种码字集合。对应的几种码字集合。等长等长变长变长变长变长变

5、长变长变长变长单义单义非单义非单义单义单义单义单义单义单义即时即时非即时非即时即时即时即时即时非续长非续长非续长非续长 非续长非续长(最佳最佳?)?)描述及描述及评价指标评价指标7第二章 基本信息论2.8 无失真信源编码(一)等长码等长码码字集合中所有码字的长度都相同码字集合中所有码字的长度都相同。变变长长码码码码字集合字集合中的码字长中的码字长度度不不相同相同。2.等长码与变长码等长码与变长码如果码字的长度为如果码字的长度为N，则能够选择的不同码字的个数为则能够选择的不同码字的个数为 2N。二二、基本概念基本概念优点优点 编码与译码简单；编码与译码简单；缺点缺点 不能不能提高提高(编码或者传

6、输编码或者传输)效率效率。优点优点 能够提高能够提高(编码或者传输编码或者传输)效率；效率；缺点缺点 编码与译码复杂。编码与译码复杂。8第二章 基本信息论2.8 无失真信源编码(一)3.单义码单义码对于一个码字集合，若存在一种译码方法，对于一个码字集合，若存在一种译码方法，使得由任意使得由任意若干个若干个码字所组成的码字所组成的码元序列码元序列只能唯一地只能唯一地被分割成单个被分割成单个码字，码字，则称该码字集合为则称该码字集合为单义单义码码，又称为，又称为唯一可译唯一可译码码。二二、基本概念基本概念定义定义引例引例符号集符号集对应的码字集为对应的码字集为收到二元序列收到二元序列译出消息序列译

7、出消息序列9第二章 基本信息论2.8 无失真信源编码(一)单义码单义码存在的充要条件存在的充要条件其中，其中，n 为信源符号数；为信源符号数；li 为各个码字的长度。为各个码字的长度。3.单义码单义码二二、基本概念基本概念对于对于 m 元代码，存在单义码的充要条件为元代码，存在单义码的充要条件为定理定理克劳夫特克劳夫特(Kraft)不等式不等式Kraft 不等式只是用来说明唯一可译码是否存在，不等式只是用来说明唯一可译码是否存在，并不能并不能注注作为唯一可译码的判据。作为唯一可译码的判据。10第二章 基本信息论2.8 无失真信源编码(一)因此不存在满足这种因此不存在满足这种码长码长的单义码。的

8、单义码。例如例如设二元码字集合设二元码字集合(1)若码长分别为若码长分别为则则因此一定存在满足这种因此一定存在满足这种码长码长的单义码。的单义码。(2)若码长分别为若码长分别为则则(等长码等长码)11第二章 基本信息论2.8 无失真信源编码(一)例如例如设二元码字集合设二元码字集合因此一定存在满足这种因此一定存在满足这种码长码长的单义码。的单义码。(3)若码长分别为若码长分别为则则比如比如 0，10，110，1110 是是单义码单义码；但是不能作为但是不能作为单义单义码的判据，码的判据，0，10，010，1110 不是不是单义码单义码。12第二章 基本信息论2.8 无失真信源编码(一)4.非即

9、时码和即时码非即时码和即时码二二、基本概念基本概念引例引例已知消息符号集已知消息符号集对应的码字集为对应的码字集为(单义码单义码)首先收到首先收到 0，被译成，被译成 x1；接着收到接着收到 1，被改译成，被改译成 x2；接着又收到接着又收到 1，再被改译成，再被改译成 x3；直到收到直到收到 0，才最后确定，才最后确定前面的码字前面的码字应译成应译成 x3。当对二元序列当对二元序列 0 1 1 0 1 进行接收并译码时，进行接收并译码时，而码字集而码字集不会出现这种情况。不会出现这种情况。13第二章 基本信息论2.8 无失真信源编码(一)4.非即时码和即时码非即时码和即时码二二、基本概念基本

10、概念定义定义如果接收到一个完整的码字后，不能如果接收到一个完整的码字后，不能立即立即(正确正确)译码译码，还需等下一个码元收到后才能判断是否可以译码，还需等下一个码元收到后才能判断是否可以译码，称这样的码集为称这样的码集为非即时码非即时码；如果只要收到的码字已完整，就可以立即如果只要收到的码字已完整，就可以立即(正确正确)译码，译码，则称这样的码集为则称这样的码集为即时码即时码。则则14第二章 基本信息论2.8 无失真信源编码(一)5.非续长码和续长码非续长码和续长码二二、基本概念基本概念定义定义如果码字集合中任何一个码字都不是另外一个码字如果码字集合中任何一个码字都不是另外一个码字的续长，则

11、称这样的码字集合为的续长，则称这样的码字集合为非续长码非续长码；为为续长码续长码。例如例如续长码：续长码：非续长码：非续长码：否则称否则称15第二章 基本信息论2.8 无失真信源编码(一)5.非续长码和续长码非续长码和续长码二二、基本概念基本概念结论结论非续长码非续长码单义码；单义码；非续长码非续长码即时码。即时码。目标目标构造构造非续长码非续长码。问题问题(1)如何判别如何判别非续长码？非续长码？(2)如何构造如何构造非续长码？非续长码？(3)收到码元序列后，如何译码收到码元序列后，如何译码？16第二章 基本信息论2.8 无失真信源编码(一)否则称为否则称为非整树非整树。三三、码树图码树图1

12、.二叉树二叉树(二进制树二进制树)从从“树根树根”开始向下至多长出开始向下至多长出 2 个树枝，个树枝，从树枝端点从树枝端点二叉树二叉树从根节点经过从根节点经过 r 个树枝才能到达的节点。个树枝才能到达的节点。r 阶节点阶节点向下不长出树枝的节点。向下不长出树枝的节点。端节点端节点各节点向下长出的树枝个数各节点向下长出的树枝个数等于等于 2，称为称为整树整树；整树整树/非整树非整树树枝与树枝的交点。树枝与树枝的交点。节点节点向下再至多长出向下再至多长出 2 个树枝，个树枝，。根节点根节点树根对应的节点。树根对应的节点。中间节点中间节点除除根节点与端节点以外的根节点与端节点以外的节点。节点。17

13、第二章 基本信息论2.8 无失真信源编码(一)二叉树二叉树(整树整树)三三、码树图码树图1.二叉树二叉树(二进制树二进制树)端节点端节点中间节点中间节点根节点根节点18第二章 基本信息论2.8 无失真信源编码(一)二叉树二叉树(非非整树整树)三三、码树图码树图1.二叉树二叉树(二进制树二进制树)端节点端节点中间节点中间节点根节点根节点0101010100110 1 01 0 10 1 0 019第二章 基本信息论2.8 无失真信源编码(一)三三、码树图码树图2.码树图码树图定义定义用一颗最小二叉树表示一个码字集合，称之为用一颗最小二叉树表示一个码字集合，称之为码树图码树图。3.由码字集合画出由

14、码字集合画出码树图码树图例如例如结论结论非续长码的码字全部在端节点非续长码的码字全部在端节点；反之，由端节点构成的码字集合一定是非续长码。反之，由端节点构成的码字集合一定是非续长码。1001100020第二章 基本信息论2.8 无失真信源编码(一)三三、码树图码树图4.利用利用码树图进行码树图进行译码译码(非续长码非续长码)方法方法(1)接收到一串二元序列。接收到一串二元序列。(2)根据二元序列的顺序，依照码树图，从根节点出发，根据二元序列的顺序，依照码树图，从根节点出发，若码元为若码元为“0”，就向左走；若码元为，就向左走；若码元为“1”，就向右走。，就向右走。当走到某个端节点时，则译出相应

15、的码字。当走到某个端节点时，则译出相应的码字。(3)回到根节点，开始下一个码字的译码。回到根节点，开始下一个码字的译码。21第二章 基本信息论2.8 无失真信源编码(一)三三、码树图码树图4.利用利用码树图进行码树图进行译码译码(非续长码非续长码)例如例如00000111接收到一串二元序列为接收到一串二元序列为1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0译出的码字序列为译出的码字序列为22第二章 基本信息论2.8 无失真信源编码(一)四四、传输效率与编码效率传输效率与编码效率1.传输效率传输效率传输效率传输效率 探讨如何评价编码的好坏探讨如何评价编码的好坏。定义定义对于信

16、道容量的利用率称为对于信道容量的利用率称为传输效率传输效率，其中，其中，R 为熵速率为熵速率(信息速率或信道传信率信息速率或信道传信率)，C 为信道容量。为信道容量。特别特别对于离散无噪信道，且脉冲等宽，则有对于离散无噪信道，且脉冲等宽，则有传输效率传输效率即即23第二章 基本信息论2.8 无失真信源编码(一)四四、传输效率与编码效率传输效率与编码效率2.编码定理编码定理定理定理设信源的熵为设信源的熵为 H，离散无噪信道的信道容量为，离散无噪信道的信道容量为 C，总可以找到一种编码方法对信源的输出进行编码，使总可以找到一种编码方法对信源的输出进行编码，使得在信道上传输的平均速率为每秒得在信道上

17、传输的平均速率为每秒 个符号。个符号。其中，其中，为任意小的正数。为任意小的正数。理解理解由传输速率为由传输速率为得传输效率为得传输效率为表明表明对于离散无噪信道，可以找到一种编码方法，使得对于离散无噪信道，可以找到一种编码方法，使得传输效率传输效率则则24第二章 基本信息论2.8 无失真信源编码(一)四四、传输效率与编码效率传输效率与编码效率3.编码效率编码效率定义定义编码后的码元传输效率称为编码后的码元传输效率称为编码效率编码效率。分析分析仅考虑二元编码，且仅考虑二元编码，且信道无噪，信道无噪，码元传输时间相同码元传输时间相同。根据传输效率与编码效率的定义即得根据传输效率与编码效率的定义即

18、得编码效率编码效率其中，其中，为二元代码的最大熵，即为二元代码的最大熵，即为二元代码的码元熵，为二元代码的码元熵，即每一个码元的平均信息量。即每一个码元的平均信息量。25第二章 基本信息论2.8 无失真信源编码(一)四四、传输效率与编码效率传输效率与编码效率3.编码效率编码效率 如何求如何求二元代码的码元熵二元代码的码元熵?X 码字码字码长码长已知已知信源熵信源熵平均码长平均码长26第二章 基本信息论2.8 无失真信源编码(一)四四、传输效率与编码效率传输效率与编码效率3.编码效率编码效率编码编码 如何求如何求二元代码的码元熵二元代码的码元熵?信道信道消息序列消息序列二元序列二元序列设发送的总

19、的消息个数为设发送的总的消息个数为 M，总的信息量为总的信息量为总共使用的码元个数为总共使用的码元个数为故每一个码元的平均信息量故每一个码元的平均信息量(码元熵码元熵)则则27第二章 基本信息论2.8 无失真信源编码(一)四四、传输效率与编码效率传输效率与编码效率3.编码效率编码效率计算公式计算公式编码效率编码效率其中，其中，为信源熵，为信源熵，为消息符号的平均码长。为消息符号的平均码长。(1)信源熵的单位必须为信源熵的单位必须为 bi t。注注(2)当信源的消息之间有关联时，信源熵应为当信源的消息之间有关联时，信源熵应为实际熵实际熵。下面如无特别说明，均假定信源的消息之间独立。下面如无特别说明，均假定信源的消息之间独立。28第二章 基本信息论2.8 无失真信源编码(一)四四、传输效率与编码效率传输效率与编码效率3.编码效率编码效率小结小结(1)不编码不编码 等长编码等长编码 变长编码变长编码(减少平均码长减少平均码长)(N 元信道元信道)(2)编码编码(二二 元信道元信道)(等概化等概化)