西北大学信息科学与技术学院：《信息与编码》课程教学课件（PPT讲稿）第四章 无失真信源编码

第四章无失真信源编码 第一节引言 第二节码的分类 第三节等长信源编码定理 第四节变长信源编码定理 第五节香农编码 第六节费诺编码 第七节霍夫曼编码 第八节游程编码、算术编码、冗长编码

第四章 无失真信源编码 第一节 引言 第二节 码的分类 第三节 等长信源编码定理 第四节 变长信源编码定理 第八节 游程编码、算术编码、冗长编码 第六节 费诺编码 第七节 霍夫曼编码 第五节 香农编码

第一节引言 信源编码:以提髙通信有效性为目的的编码。通常通过压缩信 源的冗余度来实现。采用的一般方法是压缩每个信源符号的平 均比特数或信源的码率。即同样多的信息用较少的码率传送, 使单位时间内传送的平均信息量增加,从而提高通信的有效性 信道编码:是以提髙信息传输的可靠性为目的的编码。通常通 过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。 与信源编码正好相反 ■密码:是以提高通信系统的安全性为目的的编码。通常通过加 密和解密来实现。从信息论的观点出发,“加密”可视为增熵 的过程,“解密”可视为减熵的过程

n 信源编码：以提高通信有效性为目的的编码。通常通过压缩信 源的冗余度来实现。采用的一般方法是压缩每个信源符号的平 均比特数或信源的码率。即同样多的信息用较少的码率传送， 使单位时间内传送的平均信息量增加，从而提高通信的有效性。 n 信道编码：是以提高信息传输的可靠性为目的的编码。通常通 过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。 与信源编码正好相反。 n 密码：是以提高通信系统的安全性为目的的编码。通常通过加 密和解密来实现。从信息论的观点出发， “加密”可视为增熵 的过程， “解密”可视为减熵的过程。 第一节 引言

第一节引言 信源编码理论是信息论的一个重要分支,其理论基础是信源编 码的两个定理。 ■无失真信源编码定理:是离散信源/数字信号编码的基础; ■限失真信源编码定理:是连续信源/模拟信号编码的基础 信源编码的分类:离散信源编码、连续信源编码和相关信源编 码三类。 ■离散信源编码:独立信源编码,可做到无失真编码 连续信源编码:独立信源编码,只能做到限失真信源编码; ■相关信源编码:非独立信源编码

n 信源编码理论是信息论的一个重要分支，其理论基础是信源编 码的两个定理。 n 无失真信源编码定理：是离散信源/数字信号编码的基础； n 限失真信源编码定理：是连续信源/模拟信号编码的基础。 n 信源编码的分类：离散信源编码、连续信源编码和相关信源编 码三类。 n 离散信源编码：独立信源编码，可做到无失真编码； n 连续信源编码：独立信源编码，只能做到限失真信源编码； n 相关信源编码：非独立信源编码。 第一节 引言

第二节码的分类 编码器可以看作这样一个系统,它的输入端为原始信 源S,其符号集为S={S,S,…S};而信道所能传输的符号集 为x={x1x2…x}编码器的功能是用符号集X中的元素,将 原始信源的符号S变换为相应的码字符号W,所以编码器 输出端的符号集为C:W,H2,,H} s=sS2S编码器c{,m, X={x1 x 称为码字,L为码字W的码元个数,称为码字v的码字 长度,简称码长

第二节 码的分类 编码器可以看作这样一个系统，它的输入端为原始信 源S，其符号集为 ；而信道所能传输的符号集 为 编码器的功能是用符号集X中的元素，将 原始信源的符号 变换为相应的码字符号 ，所以编码器 输出端的符号集为 称为码字， 为码字 的码元个数，称为码字 的码字 长度，简称码长。 1 2 { , ,..., }q S  S S S 1 2 { , ,..., } X r  x x x 1 2 { , ,..., }q S  S S S 1 2 { , ,..., } X r  x x x 编码器 1 2 :{ , ,..., } C W W Wq 1 2 : { , , ..., } C W W W q i S wi wi Li wi wi

第二节码的分类 二元码: 码符号集Ⅹ={0,1},如果要将信源通过二元信道传输,必 须将信源编成二元码,这也是最常用的一种码。 2、等长码: 若一组码中所有码字的长度都相同,称为等长码 3、变长码 若一组码中所有码字的长度各不相同,称为变长码 4、韭奇异码: 若一组码中所有码字都不相同,称为非奇异码

1、二元码： 码符号集X={0,1}，如果要将信源通过二元信道传输，必 须将信源编成二元码，这也是最常用的一种码。 2、等长码： 若一组码中所有码字的长度都相同，称为等长码。 3、变长码： 若一组码中所有码字的长度各不相同，称为变长码。 4、非奇异码： 若一组码中所有码字都不相同，称为非奇异码。 第二节 码的分类

第二节码的分类 5、奇异码: 若一组码中有相同的码字,称为奇异码 6、码的N次扩展: 若码CW,W2,W,码B:{B=(WW2则称码B为 码C的N次扩展码。 7、唯一可译码: 若码的任意一串有限长的码符号序列只能被唯一的译成 所对应的信源符号序列,则称此码为唯一可译码

5、奇异码： 若一组码中有相同的码字，称为奇异码。 6、码的N次扩展： 若码 ， 码 则称码B为 码C的N次扩展码。 7、唯一可译码： 若码的任意一串有限长的码符号序列只能被唯一的译成 所对应的信源符号序列，则称此码为唯一可译码。 1 2 :{ , ,..., } C W W Wq 1 2 :{ ( ... )} B Bi  Wi Wi WiN 第二节 码的分类

第三节等长信源编码定理 若对信源进行等长编码,则必须满足q≤r 其中,|是码长,「是码符号集中的码元数,q信源符号个数。 例:如果有四个信源符号{s1,s2,s3,s4},采用二元编 码,|=2,则可以编成S1=00,s2=01,s3=10,54=11。 如果我们要对信源的N次扩展信源进行编码,也必须满足 q≤r,两边取对数得:10g9 og I N表示平均每个信源符号所需的码符号个数

例：如果有四个信源符号{s1，s2，s3，s4}，采用二元编 码，l=2，则可以编成s1=00，s2=01，s3=10，s4=11。 第三节 等长信源编码定理 如果我们要对信源的N次扩展信源进行编码，也必须满足 ， 两边取对数得： N l q  r lo g lo g l q N r  表示平均每个信源符号所需的码符号个数。 l N 若对信源进行等长编码，则必须满足 其中，l是码长，r是码符号集中的码元数，q信源符号个数。 l q  r

第二节等长码 例:对英文电报得32个符号进行二元编码,根据上述关系: log 32 og 我们继续讨论上面得例子,我们已经知道英文的极限 熵是1.4b远小于5bit,也就是说,5个二元码符号只携带 1.4bit的信息量,实际上,5个二元符号最多可以携带5bit 信息量。我们可以做到让平均码长缩短,提高信息传输率

第二节 等长码 例：对英文电报得32个符号进行二元编码，根据上述关系： log32 5 log 2 l   我们继续讨论上面得例子，我们已经知道英文的极限 熵是1.4bit,远小于5bit，也就是说，5个二元码符号只携带 1.4bit的信息量，实际上，5个二元符号最多可以携带5bit 信息量。我们可以做到让平均码长缩短，提高信息传输率

第二节等长码 我们举例说明: 设信源 Sy P(S)P(S) P(S2) P(S3) P(S ∑P(s) 而其依赖关系为: P(s2/s)=P(s1/S2)=P(S1/s3)=P(s3/s1)=1其余P(s/s)=0

第二节 等长码 我们举例说明： 设信源 1 2 3 4 1 2 3 4 ( ) ( ) ( ) ( ) ( ) S s s s s P s P s P s P s P s              4 1 ( ) 1 i i P s   而其依赖关系为： 2 1 1 2 4 3 3 4 ( / ) ( / ) ( / ) ( / ) 1, ( / ) 0 P j i s s  P s s  P s s  P s s  其余P s s 

第二节等长码 若不考虑符号间的依赖关系,可得码长|=2 若考虑符号间的依赖关系,则对此信源作二次扩展 ∑P(SS P(s2)LP(S 2) P(S2s1) P(S, S4)P(S4S3) 可见,由于符号间依赖关系的存在,扩展后许多符号出 现的概率为0,此信源只有4个字符,可得码长l=2 但平均每个信源符号所需码符号为

第二节 等长码 若不考虑符号间的依赖关系，可得码长l＝2 若考虑符号间的依赖关系，则对此信源作二次扩展 2 1 2 2 1 3 4 4 3 2 1 2 2 1 3 4 4 3 ( ) ( ) ( ) ( ) ( ) S s s s s s s s s P s P s s P s s P s s P s s              ( ) 1 i j ij P s s  可见，由于符号间依赖关系的存在，扩展后许多符号出 现的概率为0，此信源只有4个字符，可得码长 ， 但平均每个信源符号所需码符号为 ' l  2 ' 1 l N 