PDF《欢迎各位同学拷贝！》

欢迎各位同学拷贝! 此课件挂在mail.

google.com网站上 用户名:jpkctxyl@gmail.com 密码:jpkctxyl123456 以饱满的热情 优良的学风 明显的进步 迎接教育部对我校进行 本科教学评估 第2章 无失真信源编码 信源编码概述 赫夫曼编码 游程编码 算术编码 通用编码 教学目的与要求 1. 深刻理解信源编码原理,明白为什么通 过编码能压缩代码长度. 2.学习信源编码基本概念,了解Shannon定 长码与变长码编码定理的内容和意义. 3.熟练掌握Huffman编码方法.(重点) 4.掌握游程编码、算术编码(难点)和字 典编码原理. 参考文献(见课本182页) 1.周炯磐:信源编码原理 人民邮电出版社(1996年10月第一版) 2. 吴乐南:数据压缩 电子工业出版社(2001年6月第一版) 3.吴伟陵:信息处理与编码 人民邮电出版社(1999年7月第一版) 4.曹雪虹:信息论与编码 北京邮电大学出版社 (2001年8月第一版) 第2章 无失真信源编码 2.1 信源编码的目的、原理 和方法概述 (第3讲2007.9.11.) 计划学时:2学时 要求掌握的主要内容: 1.深刻理解信源编码原理和意义. 2.熟练掌握编码有关概念:等长码、变长码、唯 一可译性、码树、平均码长等. 3.Shannon编码定理----概率匹配原则. 重点难点: 重点----信源编码原理 难点----Shannon编码定理 外语关键词: 信源编码: Source Coding 码树:Code Tree 变长码编码: Variable Length Coding 唯一可译性: Uniquely Decodable 即时性:Instantaneously Decodable 平均码长: Average code Length 克拉夫特不等式: Kraft Inequality 概率匹配原则: Principle of Matching with Probability 香农定理: Shannon'

s Theorems [温旧引新] 等概信源具有最大熵H0 = log m 不等概信源单符号信息熵H(X)=H1 0,只要满足: L/N=(HN +ε) / log r 则当N足够大时,几乎可实现无失真编码,使 错误任意小.反之,若L/N = (HN -2ε) / log r 则不能实现无失真编码. 定理告诉我们三个结果: (1)定长码在理论上是能够进行无失真信源 编码的;

(2)最短的极限码长是 l0=HN /log r;

(3)条件是实际码长 l =L/N >

l0 ,并且信源 序列分组N必须足够大. 然而,定理并没有给出具体的编码方案, 所以说Shannon定理是一个存在性定 理. 定理的证明:(可略) (1)契贝谢夫不等式:

2 ) ( )] ( [ } | )] ( [ ) ( | { ε δ ε N S I D N S I E S I P = ≤ ≥ ? 式中I(S)是长为N的信源序列S的自信息;

随机变量I(S)的统计平均值E[I(S)]=H(S)=N?HN;

D[I(S)]是方差,ε 是任意小正数;

契贝谢夫不等式告诉我们,统计规律的实质在于: 当随机样本数目较大时,随机变量的取值偏离它的 统计平均值较大的概率是很小的. (2)典型序列与非典型序列: ?香农把自信息取值处于H(S)?Nε范围内的那些序 列叫做典型序列.典型序列的集合记作G;

?把自信息取值处于H(S)?Nε范围外的那些序列叫 做非典型序列. ?契贝谢夫不等式告诉我们,非典型序列出现的概 率是很小的,同时也就等于告诉我们典型序列出现 的概率是很大的,所以典型序列集合又叫高概率 集. (3)典型序列的渐进等概性质: 典型序列满足:|I(S)-H(S)|<

Nε 即: -Nε<

[I(S)-N?HN] <

Nε 或: N?HNCNε <

I(S) <

N?HN +Nε N?HNCNε <

-log p(S) <

N?HN +Nε 可见: 2-N[HN -ε] >

p(S)>

2-N[HN +ε] 表明高概率集的所有典型序列其概率几乎都相 等,挤在 2-H(S)?Nε 的区间. (4)典型序列的数目: 设典型序列数目为M,则典型序列集G出现的 概率应满足: M ?2 -N(HN +ε) <