_無失真信源編碼題與答案資料

1、5.1有一信源，它有6個可能的輸出，其概率分布如題5.1表所示，表中給出了對應(yīng)的碼A,B,C,D,E和F。題表5.1消息P(ai)ABCDEFa11/200000000a21/400101101010100a31/160100111101101100101a41/160110111111011101101110a51/16100011111111010111100111a61/1610101111111111011011111011(1)求這些碼中哪些是唯一可譯碼；(2)求哪些是非延長碼(即時碼)；(3)對所有唯一可譯碼求出其平均碼長L解：(1)唯一可譯碼：A,B,CA是等長碼，碼長3,每個碼

2、字各不相同，因此是唯一可譯碼。B是非即時碼，前綴碼，是唯一可譯碼。C是即時碼，是唯一可譯碼。D是變長碼，碼長1,2,3,4,4,4,不是唯一可譯碼，因?yàn)椴粷M足Kraft不等式。3=1.0625一1E是變長碼，碼長1,2,4,4,4,4,滿足Kraft不等式，但是有相同的碼字，W4=W5=1100,不是唯一可譯碼。4-1<1F是變長碼，碼長1,3,3,3,3,3,不滿足Kraft不等式，不是唯一可譯碼。(2)非延長碼：A,CLa=3Lb=Lc=一Pi1111111123456=1.312524161616165.7設(shè)離散信源的概率空間為s182sss425s60.250.250.200.1

3、50.100.05對其米用香農(nóng)編碼，并求出平均碼長和編碼效率解：Xip(Xi)pa(Xi)ki碼字X10.203000X20.190.23001X30.180.393011X40.170.573100X50.150.743101X60.10.8941110X70.010.9971111110LcpL=0.2520.2520.230.1530.140.055=2.7H(S)=r1，plogp=70.25log0.25.0.05log0.05=2.423bitH(S)2.423L-2.7=89.7%5.8設(shè)無記憶二元信源，其概率=0.005,p2=0.995。信源輸出N=100的二元序列。在長為N

4、=100的信源序列中只對含有3個或小于3個“1”的各信源序列構(gòu)成對應(yīng)的一組等長碼。(1)求碼字所需要的長度；(2)考慮沒有給予編碼的信源序列出現(xiàn)的概率，該等長碼引起的錯誤概率pe是多少？解：碼字中有0個“1”，碼字的個數(shù)：C000=1碼字中有1個“1”，碼字的個數(shù)：C；00=100碼字中有2個“1”，碼字的個數(shù)：C1200=4950碼字中有3個“1”，碼字的個數(shù)：C1300=161700q=C；00C；00C1200cl盆=11004950161700=166751rli-qli-logrq-log166751=17.35li=18(2)碼字中有0個1”,錯誤概率:Pa1100=0.995碼字

5、中有1個1”,錯誤概率:-J0.995990.005碼字中有2個1”,錯誤概率:=(0.99518x(0.0052碼字中有3個1”,錯誤概率:=(0.995外父(0.0053012PGN-Pa1cioo.Pa2c100'Pa3C100Pa,CoO=0.99510010.995990.0051000.9959829730.00549500.9950.005161700=0.9983Pe=1-pGn=1-0.9983=0.00175.9設(shè)有離散無記憶信源818283s425s60.220.200.180.150.100.08S7S80.050.02碼符號集X=0,1,2,現(xiàn)對該信源S進(jìn)行三

6、元哈夫曼編碼,試求信源嫡H(S),碼平均長度L和編碼效率n。解:r+k(r-1)=3+2k=電5,7,9,.%q=8,sWli611S2222s212S4202S5022S6012S7000340013LPili=0.2210.22滿樹葉子節(jié)點(diǎn)的個數(shù):不能構(gòu)成滿樹。0.1820.1520.120.0820.0530.023=1.85H(S)-，R10gpi-0.22log0.22.0.02log0.02=2.75bitH(S)Llogr1.851og32.75=93.9%5.10設(shè)有離散無記憶信源，具概率空間為S1S2S30.320.220.182425s60.160.080.04進(jìn)行費(fèi)諾編碼

7、，并求其信源嫡H(S),碼平均長度L和編碼效率n。解:Xip(Xi)EncodewliX10.3200002X20.221012X30.1810102X40.16101103X50.081011104X60.04111114匚八Pili=0.3220.2220.1820.1630.0840.044=2.4H(S)=，pilogPi=-0.32log0.32.0.04log0.04=2.352bit2.45.17設(shè)有離散無記憶信源飛1_飛S2S3S4S5S6S71p'p.200.190.180.170.150.100.01'(1)求該信源符號嫡H(S);(2)用霍夫曼編碼編成二元

8、變長碼，計(jì)算其編碼效率；(3)用霍夫曼編碼編成三元變長碼，計(jì)算其編碼效率；(3)當(dāng)譯碼錯誤小于10，的定長二元碼要達(dá)到(2)中霍夫曼碼的效率時，估計(jì)要多少個信源符號一起編才能辦到。解：H(S)-pilogpi-10.2log0.2.0.0110g0.01)=2.609bit(2)swliG102s2112s0103s40113s50013琵00004s00014L='、.Pili=0.220.192n_H(S)2.609=95.9%L一2.72(3)滿樹葉子節(jié)點(diǎn)的個數(shù)：rkr-1swli611s2202s3212si222s5002琵012s022s9.s6s8s8s50.110.61s10.s3s130.35s11,s1s40.390.26s12Xs2s70.1830.1730.1530.140.014=2.72)=3+2k=電，5,7,9,.1,q=7,能構(gòu)成滿樹。L="pli=0.210.1920.1820.1720.1520.120.012=1.8_H(S)=2.609Llogr1.8log3=91.4%5.19若某一信源有N個符號，并且每個符號均已等概率出現(xiàn)，對此信源用最佳霍夫曼二元編碼，問當(dāng)N=21口N=2i+1（