当前位置:首页 >> 计算机软件及应用 >> Ch2例题与证明五

Ch2例题与证明五


? 定长编码定理 由 L 个符号组成的, 每个符号的熵为 H(X) 的平稳无记忆符号序列 X 1 X 2 ? X l ? X L ,可用 K 个符号 Y1Y2 ?Yk ?YK (每个符号有 m 种可能 取值)进行定长编码,对任意 ? ? 0, ? ? 0 ,只要
K log 2 m ? H ( X ) ? ? ? (1) L

则当 L 足够大时,必可使译码差错小于 ? 。 反之当
K log 2 m ? H ( X ) ? 2? ?(2) L

时, 译码差错一定是有限值, 当 L 足够大时, 译码必定出错。 不等式(1)中,m 代表码序列中每个符 号的可能取值数, 假定 m 个取值是等概率的, 则单个符号的信息量为 log2 m 。对于定长编 码,每个码字的长度都是 K,故码字的总数 为 m 。若信源是平稳无记忆的,长度为 K 的码序列的总信息量为:
K

log2 mK ? K log2 m
K log2 m 代表的是消息(长为

L 的信源符号序

列)的信息量。平均每个符号的信息量即平
K 均符号熵为 L log 2 m 。显然传送一个信源符号 K 所需的信息率就是 L log 2 m 。定长编码定理中

的正定理说明,信息率略大于单符号熵时, 可做到几乎无失真译码,条件是 L 必须足够 大。可以证明,只要
? 2 [ I ( xi )] L? ? 2?

(3)

译码差错率一定小于任意正数 ? 。逆定理说 明,信息率比信源熵略小一点(小一个 ? ) 时, 译码差错未必超过限定值 ? , 但若比 H(X) 小 2? ,则译码失真一定大于 ? , L ? ? 时,必 定失真。 信源熵 H(X)其实就是一个界限,或者说 是一个临界值,当编码器输出的信息率超过 这个临界值时,就能无失真译码,否则就不 行。 信源编码定理从理论上阐明了编码效率 接近于 1,即 KH ( X )
L ?1

的理想编码器的存在

log2 m

性,代价是在实际编码时取无限长的信源符

号( L ? ? )进行统一编码。具体来说,就 是给定 ? 和 ? ,用式(3)规定的 L 计算所有 可能信源消息的概率,按由大到小的次序排 列,选用概率较大的消息进行编码,于是有 编码的消息构成一个集合 A? ,直到该集合的 概率 p( A? ) ? 1 ? ? , 意味着译码差错率必定小于 ? ,即完成了编码过程。只要 ? 足够小,就可 实现几乎无失真译码,所需的信息率也不会 超过 H ( x) ? ? ;若 ? 足够小,编码效率就接近于 1。 理想编码器实际上是很难实现的。 [例 2.4.1]设某单符号信源模型为
x2 x3 x4 x5 x6 x7 x8 ? ? X ? ? x1 ? ? p( x)? ?0.4 0.18 0.10 0.10 0.07 0.06 0.05 0.04? ? ? ? ?

计算得

H ( X ) ? 2.55(比特/ 符号)
? 2[I ( xi )] ? 1.323

若要求编码效率为 90%,即
H(X ) ? 0.90 H(X ) ? ?

? =0.28 则 设译码差错率为 10?6 ,由式(3)可得

L ? 1.6875? 107

由此可见,在差错率和效率的要求都不 苛刻的情况下,就必须有 1600 多万个信源 符号一起编码,技术实现非常困难。 不仅如此,它的编码效率也不高。对 8 种可能的取值编定长码,要无差错地译码, 每种取值需用 3 个比特,其编码效率
??
2.55 ? 85 % 3

为了解决这一问题,就出现了不等长编码, 也称变长编码。 不等长编码允许把等长的消息变换成 不等长的码序列。通常把经常出现的消息编 成短码,不常出现的消息编成长码。这样可 使平均码长最短,从而提高通信效率,代价 是增加了编译码设备的复杂度。例如在不等 长码字组成的序列中要正确识别每个长度 不同的码字的起点就比等长码复杂得多。另 外,接收到一个不等长码序列后,有时不能 马上断定码字是否真正结束,因而不能立即 译出该码,要等到后面的符号收到后才能正 确译出。这就是所谓的译码同步和译码延时

问题。 [例 2.4.2]
信源消息 出现概率 码A 码B 码C x1 x2 x3 x4 0.5 0.25 0.125 0.125 0 0 1 10 0 1 00 11 0 01 011 码D 0 10 110

011 1110

显然码 A 与信源消息不是一一对应,因而 它不是唯一可译码。码 B 虽然能完成消息的 唯一编码,但它仍然不是唯一可译的。因为 若收到 00,可译为 x1 x1 ,也可译为 x3 ;同样 11 也不是唯一可译的。 码 C 虽是唯一可译的, 但它要等到下一个“ 0”收到后才能确定码 字的结束,于是有译码延时。只有码 D 既是 唯一可译的,又没有延时。 如果一个码的任何一个码字都不是其它 码字的前缀, 则称该码为前缀码、 异前置码、 异字头码、逗点码,也称即时码。 码 D 是即时码,可用树图法来构造。对 于 m 元或 m 进制树图,在最顶部画一个起始 点,成为树根。从根部引出 m 条线段,每条

线段都称为树枝。通过树枝到达另一个节 点, 从这个节点往下, 有可以分出 m 个树枝。 如此下去,就可以构造出一个树形图,称为 m 元或 m 进制码树图。自根部起,通过一条 树枝到达的接点为一级节点,一级节点最多 有 m 个;通过两条树枝到达的节点称为二级 节点,二级节点最多有 m 2 个;如此则通过 n 条树枝到达的节点称为 n 级节点,n 级节点 最多有 m n 个。 下面不再有树枝的节点称为终 端节点或终节点。除了树根和终结点以外, 其余的节点都称为中间节点。串联的树枝称 为联枝。从树根开始到每一个终结点的联枝 代表一个码字。3 元码树图如下:
0 1 2 0 1 2 0 1 2 (a)满树 0 1 2 0 1 2 0 1 2 0 1 2

0 1 2

0 1 2

0 1 2

3元码树图

(b)非满树

在码树图中,当每一个码字的串联枝数 都相同时,就是定长码。此时的码树称为满 树,如上图(a)。码长为 N 的满树的终节点 个数为 m ,即可表示 m 个码字。当有些树枝 未用时,称为非满树,如上图 (b)所示。非 满树构造的就是变长码。如果每一个码字都 被安排在终节点上,这种码就是异前置码。 M 元长度为 ki , i ? 1,2,?, n 的异前置码存在 的充要条件是
N N

?m
i ?1

n

? ki

?1

(4)

式(4)称为克拉夫特不等式。 现在来证明这个不等式。 设异前置码第 i 个码字的长度为 ki , i ? 1,2,?, n ,我们构造了一个码树图,在第 k i k 级,总共有 m 个节点。第 i 个码字占据了第
i

k i 级的

1 m ki

。根据异前置码的定义,其后的树
i

枝不能再用。对于 N 级满而言,其后不能用 N ?k 的枝数为 m ,那么总共不用的枝数为
N ?ki m ? 。N 级满树第 N 级上的总枝数已知为 i ?1 n

m N ,所以必有
N ?ki N m ? m ? i ?1 n

(5)

两边除以 m ,就得
?ki m ? ?1 i ?1 n

N

这就是异前置码存在的必要条件。 反之, 如果式(4)成立, 则式(5)必成立, 总可以把第 N 级上的树枝分成 n 组,各组中 从第 N 级开始删除 m N ?k (i ? 1,2,?, n) 个枝。相对 于 N 级满树而言,等于删除了所有可能的 k i
i

级节点的 m k

1

i

? m ?ki 。在该组中以第 k i 级节点作

为终节点,就构造好了第 i 个码字。对所有 的 n 个码字均如法炮制,则总共删除了所有
?ki m m ?1 ? m 个节点中的 ? 。由于 i ?1 i ?1
N

n

?ki

n

于是构造了一个异前置码。这是异前置码存 在的充分条件。 根据克拉夫特不等式,证明变长编码定 理。

变长编码定理 若一离散无记忆信源的符 号熵为 H ( X ) , 对信源符号进行 m 元变长编码, 一定存在一种无失真编码方法,其码字平均 长度 K 满足下列不等式
1? H(X ) H(X ) ?K? log2 m log2 m

(6) (7 )

其平均信息率满足不等式
H(X ) ? R ? H(X ) ? ?

式中, ? 为任意正数。 证明 设信源符号 X ? ?x1 , x2 ,?, xi ,?, xn ? ,概率 为 p( xi )(i ? 1,2,?, n) ,若对 x i 用一个长度为 k i 的码 字,使
1? log2 p( xi ) log p( xi ) ? ki ? ? 2 log2 m log2 m

(8)

只要我们规定 ?

log2 p( xi ) log2 m 为整数时,式(8)取

等号,非整数时, k i 取比它大一些的最接近 的整数, 则满足上式的整数必存在。 将式 ( 8) 分别乘以 p( xi ) 再对 i 求和。得
n log2 p( xi ) n log2 p( xi ) 1 ? ? p ( xi ) ? ? p ( x i ) k i ? ?? p ( x i ) log2 m log2 m i ?1 i ?1 i ?1 n

对 k i 取数学期望就是平均值 K ,故
1? H(X ) H(X ) ?K ? log2 m log2 m

由式(8) k i log2 m ? ? log2 p ( xi ) 1 或m k ? ? p ( xi ) ? m ? k p ( xi )
i

i

两边对i求和

?m
i ?1

n

? ki

?1

码字长度满足克拉夫特不等式,因而是异前 置码。 对于平稳无记忆信源来说,当信源输出的 是长度为 L 的消息序列时,易证式(6)可改 进为 1 ?
LH ( X ) LH ( X ) ?K? 此时的 K 代表平均码 log2 m log2 m

序列长度。 已知信源平均输出信息率为 R ?
2

K log2 m ,故 L

有 H ( X ) ? R ? H ( X ) ? logL m ,当 L 足够大时,可使
log2 m ? ? 。此即式(7) L

对信源进行变长编码一般所要求的信源

符号长度 L 比定长编码小得多。编码效率的 下界为
??
H (X ) ? R H (X ) log 2 m H (X ) ? L

[例 2.4.3]如例 2.4.1,要求变长编码, 编码 效率为 90%,则

2.55 3 2.55 ? L L ? 12

? 0.9


更多相关文档:

Ch2例题与证明二

0.10 p( x2 y2 ) ? p( x2 ) p( y2 / x2 ) ? 0.5 ? 0.80...线性 组合, p3 ( xi ) 构成一个新的概率分布(参见上节熵的上凸性的 证明...

Ch2例题与证明一

Ch2例题与证明一_数学_高中教育_教育专区。信息论与编码典型例题? 推导求条件熵为什么要用联合概率? 先取一个 y j ,在已知 y j 条件下,X 的条件熵 H ( ...

...& Coding信息论与编码(英文版)Ch2例题与证明三

扩 展信源的每个元素是信源 X 的输出长度为 2 的消息序 列。由于扩展信源是无记忆的,故 p(ai ) ? p( xi1 ) p( xi2 ) X 2 信源的元素 (i1 ,...

线性代数ch2习题解答1(肖蓬)

线性代数ch2 39页 1财富值 线性代数课后习题解答第五... 20页 2财富值 线性...3 注意:对于判断题,认为正确的,应当予以证明. 注意:对于判断题,认为正确的,...

Ch2点估计习题课应用统计

§CH2习题课 5页 免费 Ch2-习题课 53页 1财富值 CH2习题课(1) 32页 免费...? P78,Ex13 证明: 证明:①母体 X ~ P(λ ),∴ E ( S *2 ) = D...

Ch2例题与证明四

C​h​2​例​题​与​证​明​四 暂无评价|0人阅读|0次下载...0 (5) 同理可得 (6) 容易证明,连续信源的平均互信息也满 足对称性。即 ...

2014—2015学年度第二学期五校联考高二化学试题

考试五校联考高二年级化学科试题试卷说明:本试卷分选择题和非选择题两部分,满分...欲证明 CH2=CHCHO 中含有碳碳双键 鉴定氯乙烷中氯元素的存在 证明纤维素水解...

化学选修5第二章单元测试题

化学选修 5 第二章单元测试题一、选择题 1 等...→ NH4+ + OH⑤ CH3CH2ONa + H2O → CH3CH2...(2)请你设计实验证明 2-氯丙烷中含有氯原子. ...

经典例题

共五种 (1)CH3 -CH2 -CH2 -CH = CH2 1-戊烯 (2)CH3 -CH2 -CH =...(2)①②③④为装有各种溶液的洗气瓶, 所以依据题目要求证明混合气中含有水...

证明1

证明2页 免费如要投诉违规内容,请到百度文库投诉...求证:∠1 > ∠2 18、已知如图,在△ABC 中,CH ...2 C B 5 1 五、解答题 24.已知如图,AB∥DE....
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com