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

1、2.8 无失真信源编码(一),1. 信源编码的主要任务,使信源消息符号与信道能够传输的(数字)符号相匹配。,一、引言,变换,压缩,具体地说，通过变换使信源符号与(数字)代码相对应。,(汉字的区位码、四角号码),提高有效性或传输效率，,信道传输时，尽可能充分地利用信道容量。,使编码后的(数字)代码经过,2. 信源编码的分类,仅对信源的冗余度(或剩余度)进行压缩。,允许在一定的失真限制条件下对信源进行压缩。,一、引言,必须是可逆的，即信源符号可由代码完全恢复。,本节仅讨论无失真编码，重点介绍范诺码和霍夫曼码。,无失真编码,限失真编码,不改变信源熵，即信源的信息完全被保留。,将会降低信源熵，即信源的

2、信息被部分丧失。,二、基本概念,1. 编码器,消息符号集,基本符号集,(码元，生成 m 元代码),(已知概率分布 ),二、基本概念,1. 编码器,(数字)代码集,(码字),编码,其中， 称为码长；,称为平均码长。,(2) 每个码元占用的时间相等(称为同价码)。,(码字集合),消息符号,(最佳?),2. 等长码与变长码,如果码字的长度为N，,则能够选择的不同码字的个数为 2N。,二、基本概念,3. 单义码,对于一个码字集合，若存在一种译码方法，使得由任意,若干个码字所组成的码元序列只能唯一地被分割成单个,码字，则称该码字集合为单义码，又称为唯一可译码 。,二、基本概念,定义,引例,收到二元序列,

3、译出消息序列,单义码存在的充要条件,其中，n 为信源符号数；,li 为各个码字的长度。,3. 单义码,二、基本概念,作为唯一可译码的判据。,因此不存在满足这种码长的单义码。,(1) 若码长分别为,则,因此一定存在满足这种码长的单义码。,(2) 若码长分别为,则,(等长码),因此一定存在满足这种码长的单义码。,(3) 若码长分别为,则,比如 0，10，110，1110 是单义码；,但是不能作为单义码的判据，,4. 非即时码和即时码,二、基本概念,引例,(单义码),首先收到 0，被译成 x1；,接着收到 1，被改译成 x2；,接着又收到 1，再被改译成 x3；,直到收到 0，才最后确定前面的码字应

4、译成 x3。,当对二元序列 0 1 1 0 1 进行接收并译码时，,4. 非即时码和即时码,二、基本概念,定义,如果接收到一个完整的码字后，不能立即(正确)译码，,还需等下一个码元收到后才能判断是否可以译码，,称这样的码集为非即时码；,如果只要收到的码字已完整，就可以立即(正确)译码，,则称这样的码集为即时码。,则,5. 非续长码和续长码,二、基本概念,的续长，则称这样的码字集合为非续长码；,为续长码。,非续长码：,否则称,5. 非续长码和续长码,二、基本概念,(2) 如何构造非续长码？,(3) 收到码元序列后，如何译码？,否则称为非整树。,三、码树图,1. 二叉树(二进制树),向下再至多长出

5、 2 个树枝，。,二叉树(整树),三、码树图,1. 二叉树(二进制树),二叉树(非整树),三、码树图,1. 二叉树(二进制树),三、码树图,2. 码树图,3. 由码字集合画出码树图,例如,反之，由端节点构成的码字集合一定是非续长码。,三、码树图,4. 利用码树图进行译码(非续长码),方法,(1) 接收到一串二元序列。,(2) 根据二元序列的顺序，依照码树图，从根节点出发，,若码元为“0”，就向左走；若码元为“1”，就向右走。,当走到某个端节点时，则译出相应的码字。,(3) 回到根节点，开始下一个码字的译码。,三、码树图,4. 利用码树图进行译码(非续长码),例如,接收到一串二元序列为,1 0

6、1 0 1 1 0 0 0 0 0 1 0 1 1 0 0,译出的码字序列为,四、传输效率与编码效率,1. 传输效率,传输效率,探讨如何评价编码的好坏。,其中，R 为熵速率(信息速率或信道传信率)，,C 为信道容量。,传输效率,即,四、传输效率与编码效率,2. 编码定理,总可以找到一种编码方法对信源的输出进行编码，使,得在信道上传输的平均速率为每秒 个符号。,其中， 为任意小的正数。,理解,由传输速率为,得传输效率为,传输效率,则,四、传输效率与编码效率,3. 编码效率,分析,仅考虑二元编码，且信道无噪，码元传输时间相同。,根据传输效率与编码效率的定义即得,编码效率,其中， 为二元代码的最大熵，即,为二元代码的码元熵，,即每一个码元的平均信息量。,四、传输效率与编码效率,3. 编码效率,如何求二元代码的码元熵 ?,信源熵,平均码长,四、传输效率与编码效率,3. 编码效率,如何求二元代码的码元熵 ?,消息序列,二元序列,设发送的总的消息个数为 M，,总的信息量为,总共使用的码元个数为,故每一个码元的平均信息量(码元熵),则,四、传输效率与编码效率,3. 编码效率,计算公式,编码效率,其中， 为信源熵，,为消息符号的平均码长。,(2) 当信源的消息之间有关联时，信源熵应为实际