信息论作业2012春第二次参

lim logP(XX,X )H(UN 1limP(X1X2,XN)NN

exp(H(UKPlogP(U)

0 n0lo

(Nn0)lo

log

lo

lo

11

0 log N

1P 4 N1N3C4

)4()

0.05N k1k3NN C()(

4

0 没有满足上述条0H(U1)log42(bit)H(U)limH(UN| UN1)limH(UN|UN1)0.9log0.90.1logN N＝0.469U)lim1[H(U)HU)lim1[H(U)H(U|U)N H(U| UN1Nlim1[H(U)H(U|U)H(U|U) H(U| N Nlim1[H(U)(N1)H(U| )]lim1[H(U)(N1)(0.9log0.90.1logN N N 1)M2jkj0,0k2jj的二叉满树，并在2j个叶子节点中取k个节点，以这k个节点为根节点，生成k个深度为1的子树，于是得到了一个有2j2kkMHalfman方法进行编码，即得到最优的二元即时2）IM

(j1)2kM

jkj2klog 当且仅当k=0M2jIlog2

不妨设u(i=…-2,-1,0,1,2,…)取自字母表{a，a…a}，设一阶转移概率为 2n

n1 nn所以在当前码字uj进行编码时，由uj1ak，对uj可能的取值，依概率分布Pk1Pkn)Huffman熵率公式，可以计算得到信源熵率为0.801bit/sample P17，P27，P37，再利用离散马尔可夫信源的熵率公式，可以计算得到信源熵率为2)按马尔可夫信源进行编码：状态1时：a→0,b→10,c→11状态2时：a→0,b→1

1212)

11

11)20

( (叶子节点的平均深度，即为j，所以，I＝j；个节点，以这(x1)2j个节点为根节点，生成(x1)2j1j的叶子节点有2jx1)2j(2x)2jj+1的叶子节点有，2(x1)2j个，于是I1[j(2x)2j(j1)2(x1)2j]1(xj2x2)j2 2Ij2x1)H(X)=－（plogp+qlogq）H(Y)lim1H Y)lim1[H(Y)H(Y|Y) H(Y| N 1 N 1N lim1[H(Y)H(Y|Y)H(Y|Y)

H

N Nlim1[H(Y)(N1)H(Y| )]H(X)plogpqlogN N {

22)p=q=1时，H(Y)1bit/2p94HuffmanHuffman编码最好统一编码规则，比如同一深度，P91：P(aj)logP(aj)log23P(aj)lj j

P(a)[logP(a)log3lj logxx1 P(aj)logP(a P(aj)P(a)13j1j

j

j

即P(aj

1 )j(

，k=ljl 即H(U)=log3l或l log

) kk3k32j1）考虑信源U

a a C1P(a1 其中MP(ak

l

又 H(U)H(U)

CkP(ak)logCkP(ak∴

M

C

)

k

CP(a2）∵H(U)lH(U)

即

(U)C

(U)1M

(U)CM

(U)又CminMHK∴CminCCminP(ak设有两个字母A，BP{Xt1AXtBP{Xt1BXtA}。1）P{Xt1AXtBP{Xt1B}P{XtAP{Xt1BXtA}2）m阶马尔科夫信源。对于转移概率简化表示，形如PXtA|XtmAXtm1BXt1BPA|特别的，当m=1时，只有两个状态ABPAP(B。AP(A)P(A|B)P(B)P(A|A)P(A)1P(A|A)P(A)P(A|P(B|A1PA|A).则上式变为：PAB)P(B|A)PA)PA|B)P(B)P(BA)，结论成立。m2时，此时的状态数为P(BmP(B|ABm1)PABm1P(B|Bm)P(Bm)P(Bm1A)PA|ABm1)PABm1PA|Bm)P(Bm)P(Bm)P(Bm1A)P(A|ABm1)P(B|ABm1)P(ABm1)P(B|Bm)P(A|Bm)P(Bm) PA|ABm1P(B|ABm1P(B|BmPA|Bm1P(BmP(Bm1A)PABm1P(Bm)m2PABP(BA成立。m3，由于：P(AB)P(ABA)P(AB2A)...P(ABm2A)P(P(BAPABAPAB2APABm2AP(Bm1A 说明:试图通过证明i有 i, i,

在这种情况下，概率为0.26的码字对应的Shannon-Fano码的长度为3，而对应的Shannon码的长度为2。 1/ 1/ 1/ 1/ 1/ 1/ 1/ P 1/ 1/ 1/ 1/ 0那么有P[1/31/41/41/4H(U)P(j)H(U|sjj

51log3 1n小码长为log2n。另L1(2k(m1)(n2k)m)lognn

2 rLlognm ln(2m 2m lnr2m1(2mk) (2m k2ln21)2m2m,0.3863时，r取得最大值，此时n2mk2m1ln2 1nlog(P(X))nlog(P(X1X

Xn)) log(P(Xinn

log(P(X))H(X)|}