第三章无失真信源编码 无失真编码概述 ●是长信源编码多 变长信源编码 实用的无失真信源编码方法举 例
第三章无失真信源编码 无失真编码概述 定长信源编码 变长信源编码 实用的无失真信源编码方法举 例
§3H无失真编码概述-1 ●通信中信息传输所要解决的基本问题是: 有效性和可靠性 在不失真或允许一定失真条件下,如何用尽 可能烧得符号来传送信源信息以提高信息传 输率 信源编码 ●在信道受干扰情况下,如何增加信号的抗干 扰能力同时又使得信息传输率最大—信道 编码
§3.1无失真编码概述-1 通信中信息传输所要解决的基本问题是： 有效性和可靠性 ⚫ 在不失真或允许一定失真条件下，如何用尽 可能烧得符号来传送信源信息以提高信息传 输率－－－信源编码 ⚫ 在信道受干扰情况下，如何增加信号的抗干 扰能力同时又使得信息传输率最大——信道 编码
§3H无失真编码概述-2 离散、无失真、无记忆信源编码的—般模型 入 出 X={x1,x2.n} 信源 总组合数 编码 总码组合数: Y∈{yt,y2…ym
§3.1无失真编码概述-2 离散、无失真、无记忆信源编码的一般模型： 总组合数： 总码组合数： L n K m 入 出 信源 编码 X={x1,x2…xn} Y=(Y1,Y2,.Yk) Y∈{y1,y2….ym}
§3.1无失真编码概述-3 ●问题:能否进行无失真编码,怎样进行无失真编码 若:不考虑信源统计特性 ●应满足条件:(无失真:n≤h 相互矛盾 有效:n≥m 由n 09n ogn 结论:①当n=m时,K>L不有效 ②当K=L时,mn,亦不满足有效性 ·解决办法:引入信源统计特性
§3.1无失真编码概述-3 问题：能否进行无失真编码，怎样进行无失真编码 若：不考虑信源统计特性： 应满足条件： 相互矛盾！ L K L n m n 有效： 无失真： K m log log L K KL n n m L m 由 • 结论：①当 n = m 时，K≥L 不有效。 ②当K = L 时，m≥n，亦不满足有效性 • 解决办法： 引入信源统计特性
§3H无失真编码概述-4 考察无失真条件 K gm 分别表示等概条件下的消息熵H(X)gn与码字熵HY=1gm之比, 考虑信源的实际统计特性(非等概),实际消息熵为(X)=∑ p, log p 代入无失真条件得:k少 此时:即使m=n,只要gm>H(Y)就有可能实现K<L 即无失真与有效性同时满足。 ●具体实现时:定长与变长编码
§3.1无失真编码概述-4 考察无失真条件： 分别表示等概条件下的消息熵 与码字熵 之比， 考虑信源的实际统计特性（非等概），实际消息熵为： 代入无失真条件得： 此时：即使m=n,只要 就有可能实现KL<L。 即无失真与有效性同时满足。 具体实现时：定长与变长编码 log log L KL KL n n m L m ( ) log i i i H X p p = − ( ) log KL H X L m log ( ) m H X H(X)=logn H(Y)=logm
S32码的分类-1 编码器可以看作这样一个系统,它的输入端为原始信 源X,其符号集为xx2…xn};/而信道能传输的符号集 为{y1y2…ym}编码器的功能是用符号集Y中的元素,将 原始信源的符号变换为相应的码字符号,所以编码器 输出端的符号集为y=~Y2,Y) y称为码字,k为码字Y的码元个数,称为码字的码字 长度简称码长
编码器可以看作这样一个系统，它的输入端为原始信 源X，其符号集为 ；而信道所能传输的符号集 为 编码器的功能是用符号集Y中的元素，将 原始信源的符号 x 变换为相应的码字符号 ，所以编码器 输出端的符号集为 Y 称为码字， k 为码字 Y 的码元个数，称为码字 的码字 长度简称码长。 1 2 { , ,..., }q S S S S = 1 2 { , ,..., } X x x x = r 1 2 :{ , ,..., } C W W Wq i S wi {x1,x2…xn} Y=(Y1,Y2,.Yk) {y1,y2….ym} §3.2码的分类-1
§32码的分 1、二元码; 码符号集X={01,如果要将信源通过二元信道传输,必 须将信源编成二元码这也是最常用的一种码。 2、籌长码: 若一组码中所有码字的长度都相同,称为等长码 3、变长码: 若一组码中所有码字的长度各不相同,称为变长码 4、韭奇异码 若一组码中所有码字都不相同,称为非奇异码
1、二元码： 码符号集X={0,1}，如果要将信源通过二元信道传输，必 须将信源编成二元码，这也是最常用的一种码。 2、等长码： 若一组码中所有码字的长度都相同，称为等长码。 3、变长码： 若一组码中所有码字的长度各不相同，称为变长码。 4、非奇异码： 若一组码中所有码字都不相同，称为非奇异码。 §3.2码的分类-2
§3.2码的分类 5、奇异码 若一组码中有相同的码字,称为奇异码。 6、唯一可译码 若码的任意一串有限长的码符号序列只能被唯一的译成 所对应的信源符号序列,则称此码为唯一可译码 ●最佳码 唯一可译码的一类 ●其平均码长小于其他唯一可译码的平均长度
5、奇异码： 若一组码中有相同的码字，称为奇异码。 6、唯一可译码： 若码的任意一串有限长的码符号序列只能被唯一的译成 所对应的信源符号序列，则称此码为唯一可译码。 最佳码 ⚫唯一可译码的一类 ⚫其平均码长小于其他唯一可译码的平均长度 1 2 :{ ( ... )} B B W W W i i i iN = §3.2码的分类
例1唯一可译变长码与及时码 信源符号出现概率码1 码2 码3 码4 1/2 0 14 11 10 10 01 1/8 00 00 100 001 4 1/8 01 1000 0001
例1.唯一可译变长码与及时码 信源符号 出现概率 码1 码2 码3 码4 x1 x2 x3 x4 1/2 1/4 1/8 1/8 0 11 00 11 0 10 00 01 1 10 100 1000 1 01 001 0001
7.即时码 码1是一个奇异码,不是唯可译码;码2也不是唯 可译码,因为收到一串序列是,无法唯一译出对应的原符 号序列,如0100,即可译作X4×3x1,也可译作 ×4×1X3,X1X2x3或x1x2x1x1;码3和码4都是唯一可译的 但码3和码4也不太一样,码4称作逗点码,只要收到1, 就可以立即作出译码;而码3不同,当受到一个或几个码 是,必须参考后面的码才能作出判断 定义,在唯一可译码中,有一类码,它在译码是无须参 考后面的码字就可以作出判断,这种码称为即时码
码1是一个奇异码，不是唯一可译码；码2也不是唯一 可译码，因为收到一串序列是，无法唯一译出对应的原符 号序列，如0100，即可译作x4x3x1,也可译作 x4x1X3,x1x2x3或x1x2x1x1；码3和码4都是唯一可译的。 但码3和码4也不太一样，码4称作逗点码，只要收到1， 就可以立即作出译码；而码3不同，当受到一个或几个码 是，必须参考后面的码才能作出判断。 定义，在唯一可译码中，有一类码，它在译码是无须参 考后面的码字就可以作出判断，这种码称为即时码。 7.即时码