第三章离散信源及离散熵
- 格式:ppt
- 大小:267.50 KB
- 文档页数:26
第三章 离散信源无失真编码3.2离散无记忆信源,熵为H[x],对信源的L 长序列进行等长编码,码字是长为n 的D 进制符号串,问:(1)满足什么条件,可实现无失真编码。
(2)L 增大,编码效率 也会增大吗? 解:(1)当log ()n D LH X ≥时,可实现无失真编码;(2)等长编码时,从总的趋势来说,增加L 可提高编码效率,且当L →∞时,1η→。
但不一定L 的每次增加都一定会使编码效率提高。
3.3变长编码定理指明,对信源进行变长编码,总可以找到一种惟一可译码,使码长n 满足D X H log )(≤n <D X H log )(+L 1,试问在n >D X H log )(+L1时,能否也找到惟一可译码? 解:在n >D X H log )(+L1时,不能找到惟一可译码。
证明:假设在n >D X H log )(+L1时,能否也找到惟一可译码,则由变长编码定理当n 满足D X H log )(≤n <D X H log )(+L 1,总可以找到一种惟一可译码知:在n ≥DX H log )( ① 时,总可以找到一种惟一可译码。
由①式有:Ln ≥L X H )(logD ② 对于离散无记忆信源,有H(x)=LX H )( 代入式②得:n L≥ D x H log )(即在nL≥Dx H log )(时,总可以找到一种惟一可译码;而由定理给定熵H (X )及有D 个元素的码符号集,构成惟一可译码,其平均码长满足D X H log )(≤n L <DX H log )(+1 两者矛盾,故假设不存在。
所以,在n >D X H log )(+L1时,不能找到惟一可译码。
3.7对一信源提供6种不同的编码方案:码1~码6,如表3-10所示信源消息 消息概率 码1 码2 码3 码4 码5 码6 u1 1/4 0 001 1 1 00 000 u2 1/4 10 010 10 01 01 001 U3 1/8 00 011 100 001 100 011 u4 1/8 11 100 1000 0001 101 100 u5 1/8 01 101 10000 00001 110 101 u6 1/16 001 110 100000 000001 1110 1110 u71/161111111000000000000111111111(1) 这些码中哪些是惟一可译码? (2) 这些码中哪些是即时码?(3) 对所有唯一可译码求出其平均码长。
3.1 设有一离散无记忆信源,其概率空间为⎭⎬⎫⎩⎨⎧=====⎥⎦⎤⎢⎣⎡8/14/1324/18/310)(4321x x x x X P X 该信源发出的信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。
求:(1) 此消息的自信息量是多少?(2) 此消息中平均每符号携带的信息量是多少?解: (1)此消息总共有14个0、13个1、12个2、6个3,因此消息发出的概率是:62514814183⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛=p此消息的信息量是:bit p I 811.87log =-=(2)此消息中平均每符号携带的信息量是:bit n I 951.145/811.87/==3.2 某一无记忆信源的符号集为{0, 1},已知信源的概率空间为⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡4/34/110)(X P X(1) 求信息符号的平均熵;(2) 由100个符号构成的序列,求某一特定序列(例如有m 个“0”和(100 - m )个“1”)的自信息量的表达式; (3) 计算(2)中序列的熵。
解: (1)bit x p x p X H ii i 811.043log 4341log 41)(log )()(=⎪⎭⎫ ⎝⎛+-=-=∑(2)bit m x p x I x p mi i m mm i 585.15.4143log)(log )(434341)(100100100100100+=-=-==⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛=---(3)bit X H X H 1.81811.0100)(100)(100=⨯==3.5 某信源的消息符号集的概率分布和二进制代码如题表3.2所列。
题表 3.2(1) (2) 求每个消息符号所需要的平均二进制码的个数或平均代码长度。
进而用这一结果求码序列中的一个二进制码的熵;(3) 当消息是由符号序列组成时,各符号之间若相互独立,求其对应的二进制码序列中出现0和1的无条件概率0p 和1p ,求相邻码间的条件概率1/0p 、0/1p 、1/1p 、0/0p 。
3.1 设有一离散无记忆信源,其概率空间为⎭⎬⎫⎩⎨⎧=====⎥⎦⎤⎢⎣⎡8/14/1324/18/310)(4321x x x x X P X 该信源发出的信息序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210)。
求:(1) 此消息的自信息量是多少?(2) 此消息中平均每符号携带的信息量是多少?解: (1)此消息总共有14个0、13个1、12个2、6个3,因此消息发出的概率是:62514814183⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛=p此消息的信息量是:bit p I 811.87log =-=(2)此消息中平均每符号携带的信息量是:bit n I 951.145/811.87/==3.2 某一无记忆信源的符号集为{0, 1},已知信源的概率空间为⎭⎬⎫⎩⎨⎧=⎥⎦⎤⎢⎣⎡4/34/110)(X P X(1) 求信息符号的平均熵;(2) 由100个符号构成的序列,求某一特定序列(例如有m 个“0”和(100 - m )个“1”)的自信息量的表达式; (3) 计算(2)中序列的熵。
解: (1)bit x p x p X H ii i 811.043log 4341log 41)(log )()(=⎪⎭⎫ ⎝⎛+-=-=∑(2)bit m x p x I x p mi i m mm i 585.15.4143log)(log )(434341)(100100100100100+=-=-==⎪⎭⎫ ⎝⎛⨯⎪⎭⎫ ⎝⎛=---(3)bit X H X H 1.81811.0100)(100)(100=⨯==3.5 某信源的消息符号集的概率分布和二进制代码如题表3.2所列。
题表 3.2(1) (2) 求每个消息符号所需要的平均二进制码的个数或平均代码长度。
进而用这一结果求码序列中的一个二进制码的熵;(3) 当消息是由符号序列组成时,各符号之间若相互独立,求其对应的二进制码序列中出现0和1的无条件概率0p 和1p ,求相邻码间的条件概率1/0p 、0/1p 、1/1p 、0/0p 。