第5章无失真信源编码

5.1有一信源，它有6个可能的输出，其概率分布如题5.1表所示，表中给出了对应的码EDCBA,,,,和F。题表5.1消息p(ai)ABCDEFa11/200000000a21/400101101010100a31/160100111101101100101a41/160110111111011101101110a51/16100011111111010111100111a61/1610101111111111011011111011(1)求这些码中哪些是唯一可译码；(2)求哪些是非延长码（即时码）；(3)对所有唯一可译码求出其平均码长L。解：(1)唯一可译码：A，B，CA是等长码，码长3，每个码字各不相同，因此是唯一可译码。B是非即时码，前缀码，是唯一可译码。C是即时码，是唯一可译码。D是变长码，码长}4,4,4,3,2,1{，不是唯一可译码，因为不满足Kraft不等式。10625.13212121214321ilirE是变长码，码长}4,4,4,4,2,1{，满足Kraft不等式，但是有相同的码字，110053WW，不是唯一可译码。114212121421ilirF是变长码，码长}3,3,3,3,3,1{，不满足Kraft不等式，不是唯一可译码。1125.15212131ilir(2)非延长码：A，C(3)3125.161615161416131612411213iiiCBAlpLLL5.7设离散信源的概率空间为05.010.015.020.025.025.0654321ssssssPS对其采用香农编码，并求出平均码长和编码效率。解：xip(xi)pa(xi)ki码字x10.203000x20.190.23001x30.180.393011x40.170.573100x50.150.743101x60.10.8941110x70.010.9971111110%7.897.2423.2)(423.205.0log05.0...25.0log25.0log)(7.2505.041.0315.032.0225.0225.0LSHbitppSHlpLiiiiii5.8设无记忆二元信源，其概率995.0,005.021pp。信源输出100N的二元序列。在长为100N的信源序列中只对含有3个或小于3个“1”的各信源序列构成一一对应的一组等长码。(1)求码字所需要的长度；(2)考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率Ep是多少？解：(1)码字中有0个“1”，码字的个数：10100C码字中有1个“1”，码字的个数：1001100C码字中有2个“1”，码字的个数：49502100C码字中有3个“1”，码字的个数：1617003100C1835.17166751loglog166751161700495010013100210011000100irillqlqrCCCCqis7s8s9s6s5s1s2s3s4s10s12s110.070.250.53(2)码字中有0个“1”，错误概率：100995.01ap码字中有1个“1”，错误概率：005.0995.0992ap码字中有2个“1”，错误概率：298500.0995.03ap码字中有3个“1”，错误概率：397500.0995.04ap0017.09983.0119983.0161700005.0995.04950005.0995.0100005.0995.01995.03972989910031002100110001004321NEaaaaNGppCpCpCpCpGp5.9设有离散无记忆信源02.005.008.010.015.018.020.022.087654321ssssssssPS码符号集}2,1,0{X，现对该信源S进行三元哈夫曼编码，试求信源熵)(SH，码平均长度L和编码效率。解：满树叶子节点的个数：...,9,7,5,3231krkr，8q，不能构成满树。iiilws1s112s2223s2124s2025s0226s0127s00038s001385.1302.0305.0208.021.0215.0218.022.0122.0iiilpL%9.933log85.175.2log)(75.202.0log02.0...22.0log22.0log)(rLSHbitppSHiii5.10设有离散无记忆信源，其概率空间为04.008.016.018.022.032.0654321ssssssPS进行费诺编码，并求其信源熵)(SH，码平均长度L和编码效率。解：xip(xi)Encodewilix10.3200002x20.221012x30.1810102x40.16101103x50.081011104x60.04111114%984.2352.2)(352.204.0log04.0...32.0log32.0log)(4.2404.0408.0316.0218.0222.0232.0LSHbitppSHlpLiiiiii5.17设有离散无记忆信源01.010.015.017.018.019.020.07654321sssssssPS(1)求该信源符号熵)(SH；(2)用霍夫曼编码编成二元变长码，计算其编码效率；(3)用霍夫曼编码编成三元变长码，计算其编码效率；(3)当译码错误小于310的定长二元码要达到(2)中霍夫曼码的效率时，估计要多少个信源符号一起编才能办到。解：(1)bitppSHiii609.201.0log01.0...2.0log2.0log)((2)s7s8s9s6s2s3s4s10s12s110.110.260.39s5s1s130.350.61s7s6s5s1s2s3s4s8s10s90.260.54iiilws1s1022s1123s01034s01135s00136s000047s00014%9.9572.2609.2)(72.2401.041.0315.0317.0318.0219.022.0LSHlpLiii(3)满树叶子节点的个数：...,9,7,5,3231krkr，7q，能构成满树。iiilws1s112s2023s2124s2225s0026s0127s022%4.913log8.1609.2log)(8.1201.021.0215.0217.0218.0219.012.0rLSHlpLiii5.19若某一信源有N个符号，并且每个符号均已等概率出现，对此信源用最佳霍夫曼二元编码，问当iN2和12iN（i为正整数）时，每个码字的长度等于多少？平均码长是多少？解：1221121log1loglog212112112)2(21log1loglog21212)1(11iiiiiiiiiiiiiiiiiiiiiiiiiiiiiilpLilplpppNwhenilpLilplppNwhen