第四章无失真信源编码 第一节引言 第二节码的分类 第三节等长信源编码定理 第四节变长信源编码定理 第五节香农编码 第六节费诺编码 第七节霍夫曼编码 第八节游程编码、算术编码、冗长编码
第四章 无失真信源编码 第一节 引言 第二节 码的分类 第三节 等长信源编码定理 第四节 变长信源编码定理 第八节 游程编码、算术编码、冗长编码 第六节 费诺编码 第七节 霍夫曼编码 第五节 香农编码
第一节引言 信源编码:以提髙通信有效性为目的的编码。通常通过压缩信 源的冗余度来实现。采用的一般方法是压缩每个信源符号的平 均比特数或信源的码率。即同样多的信息用较少的码率传送, 使单位时间内传送的平均信息量增加,从而提高通信的有效性 信道编码:是以提髙信息传输的可靠性为目的的编码。通常通 过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。 与信源编码正好相反 ■密码:是以提高通信系统的安全性为目的的编码。通常通过加 密和解密来实现。从信息论的观点出发,“加密”可视为增熵 的过程,“解密”可视为减熵的过程
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