第5章_無失真信源編碼 題與答案

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

2、各不相同，因此是唯一可譯碼。B 是非即時(shí)碼，前綴碼，是唯一可譯碼。C 是即時(shí)碼，是唯一可譯碼。D 是變長(zhǎng)碼，碼長(zhǎng)，不是唯一可譯碼，因?yàn)椴粷M足Kraft不等式。E 是變長(zhǎng)碼，碼長(zhǎng)，滿足Kraft不等式，但是有相同的碼字，不是唯一可譯碼。F 是變長(zhǎng)碼，碼長(zhǎng)，不滿足Kraft不等式，不是唯一可譯碼。(2) 非延長(zhǎng)碼：A，C(3)5.7 設(shè)離散信源的概率空間為對(duì)其采用香農(nóng)編碼，并求出平均碼長(zhǎng)和編碼效率。解：xip(xi)pa(xi)ki碼字x10.203000x20.190.23001x30.180.393011x40.170.573100x50.150.743101x60.10.8941110x70

3、.010.99711111105.8 設(shè)無記憶二元信源，其概率。信源輸出的二元序列。在長(zhǎng)為的信源序列中只對(duì)含有3個(gè)或小于3個(gè)“1”的各信源序列構(gòu)成一一對(duì)應(yīng)的一組等長(zhǎng)碼。(1) 求碼字所需要的長(zhǎng)度；(2) 考慮沒有給予編碼的信源序列出現(xiàn)的概率，該等長(zhǎng)碼引起的錯(cuò)誤概率是多少？解：(1)碼字中有0個(gè)“1”，碼字的個(gè)數(shù)：碼字中有1個(gè)“1”，碼字的個(gè)數(shù)：碼字中有2個(gè)“1”，碼字的個(gè)數(shù)：碼字中有3個(gè)“1”，碼字的個(gè)數(shù)：(2)碼字中有0個(gè)“1”，錯(cuò)誤概率：碼字中有1個(gè)“1”，錯(cuò)誤概率：碼字中有2個(gè)“1”，錯(cuò)誤概率：碼字中有3個(gè)“1”，錯(cuò)誤概率：5.9 設(shè)有離散無記憶信源碼符號(hào)集，現(xiàn)對(duì)該信源進(jìn)行三元哈夫曼編碼

4、，試求信源熵，碼平均長(zhǎng)度和編碼效率。解：滿樹葉子節(jié)點(diǎn)的個(gè)數(shù)：，不能構(gòu)成滿樹。 1 1 22 2 21 2 20 2 02 2 01 2 000 3 001 35.10 設(shè)有離散無記憶信源，其概率空間為進(jìn)行費(fèi)諾編碼，并求其信源熵，碼平均長(zhǎng)度和編碼效率。解：xip(xi)Encodewilix10.3200002x20.221012x30.1810102x40.16101103x50.081011104x60.041111145.17 設(shè)有離散無記憶信源(1) 求該信源符號(hào)熵；(2) 用霍夫曼編碼編成二元變長(zhǎng)碼，計(jì)算其編碼效率；(3) 用霍夫曼編碼編成三元變長(zhǎng)碼，計(jì)算其編碼效率；(3) 當(dāng)譯碼錯(cuò)誤小于的定長(zhǎng)二元碼要達(dá)到(2)中霍夫曼碼的效率時(shí)，估計(jì)要多少個(gè)信源符號(hào)一起編才能辦到。解：(1)(2) 10 2 11 2 010 3 011 3 001 3 0000 4 0001 4(3)滿樹葉子節(jié)點(diǎn)的個(gè)數(shù)：，能構(gòu)成滿樹。 1 1 20 2 21 2 22 2 00 2 01 2 02 25.19 若