《第四章 信源編碼 習(xí)題解答》由會(huì)員分享,可在線閱讀,更多相關(guān)《第四章 信源編碼 習(xí)題解答(7頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、【精品文檔】如有侵權(quán),請(qǐng)聯(lián)系網(wǎng)站刪除,僅供學(xué)習(xí)與交流
第四章 信源編碼 習(xí)題解答
.....精品文檔......
第四章信源編碼 習(xí)題解答
1、一個(gè)信源由6個(gè)消息組成,其概率分布已知,對(duì)其進(jìn)行信源編碼得如下表所示6種編碼方法:
信源X
p(X)
A
B
C
D
E
F
G
x1
1/2
000
0
0
01
1
01
1
x2
1/4
001
01
10
10
000
001
01
x3
1/16
010
011
110
1101
001
100
101
x4
1/16
011
2、0111
1110
1100
010
101
0011
x5
1/16
100
01111
11110
1001
110
110
101
x6
1/16
101
011111
111110
1111
101
111
1001
1) 哪些是非奇異碼?哪些是唯一可譯碼?哪些是即時(shí)碼?
2) 分別計(jì)算每個(gè)唯一可譯碼的平均碼長(zhǎng)和編碼效率。
解:1)A、B、C、D、E、F是非奇異碼。A、B、C、F是唯一可譯碼(E不滿足克拉夫特不等式)。A、C、F是即時(shí)碼(B是續(xù)長(zhǎng)碼)。
3) 編碼A:
平均碼長(zhǎng):
信源熵:比特/消息
編碼效率:
編碼B和C:
3、
平均碼長(zhǎng):
編碼效率:
編碼F:
平均碼長(zhǎng):
編碼效率:
2、離散無(wú)記憶信源X的概率空間為:
1)對(duì)其進(jìn)行費(fèi)諾編碼,并計(jì)算其編碼效率;
2)對(duì)其進(jìn)行哈夫曼編碼,并將其編碼效率與費(fèi)諾編碼相比較。
解:1)費(fèi)諾編碼:
信源X
p(X)
編碼過(guò)程
碼字
碼長(zhǎng)
x1
0.20
0
0
00
2
x2
0.19
1
0
010
3
x3
0.18
1
011
3
x4
0.17
1
0
10
2
x5
0.15
1
0
110
3
x6
0.10
1
0
1110
4
x
4、7
0.01
1
1111
4
平均碼長(zhǎng):碼元/符號(hào)
信源熵:
編碼后平均碼元熵:比特/碼元
編碼效率:
2)哈夫曼編碼:
碼長(zhǎng)
碼字
信源X
0
1
0
0.11
1
0
0.26
1
0.35
1
1
0.39
1
0
0
0.61
0
1.0
p(X)
2
10
x1
0.20
2
11
x2
0.19
3
000
x3
0.18
3
001
x4
0.17
3
010
x5
0.15
4
0110
x6
0.10
4
0111
x7
0.01
平均碼長(zhǎng):碼元/符號(hào)
5、編碼后平均碼元熵:比特/碼元
編碼效率:
與費(fèi)諾編碼相比,哈夫曼編碼的編碼效率要高于費(fèi)諾編碼。
一般情況下哈夫曼編碼效率較高,但費(fèi)諾編碼如果每次劃分概率很接近,則效率也很高。
3、離散無(wú)記憶信源X的概率空間為:
1)對(duì)其進(jìn)行費(fèi)諾編碼;
2)對(duì)其進(jìn)行哈夫曼編碼。
解:1)費(fèi)諾編碼:
信源X
p(X)
編碼過(guò)程
碼字
碼長(zhǎng)
x1
0.22
0
0
00
2
x2
0.20
1
01
2
x3
0.18
1
0
0
100
3
x5
0.15
1
101
3
x4
0.1
1
0
6、
110
3
x8
0.08
1
0
1110
4
x7
0.05
1
0
11110
5
x6
0.02
1
11111
5
2)哈夫曼編碼:
4、離散無(wú)記憶信源S描述為:
1)計(jì)算信源熵及其冗余度;
2)對(duì)其進(jìn)行費(fèi)諾編碼;
3)對(duì)其進(jìn)行哈夫曼編碼;
4*)對(duì)其進(jìn)行香農(nóng)-費(fèi)諾-埃利阿斯編碼;
5*)對(duì)其進(jìn)行香農(nóng)編碼;
6)計(jì)算哈夫曼碼的平均碼長(zhǎng)、編碼效率和碼冗余度;
7)把哈夫曼編碼器的輸出看成一個(gè)新信源X,計(jì)算其概率分布p(x1) 和 p(x2);
8)H[p(x1), p(x2)] 是否等于H碼(即平均碼元熵)?為什
7、么?
解:1)信源熵:
冗余度:
2)費(fèi)諾編碼:
信源S
p(S)
編碼過(guò)程
碼字
碼長(zhǎng)
s1
0.37
0
0
00
2
s2
0.25
1
01
2
s4
0.18
1
0
10
2
s3
0.1
1
0
110
3
s6
0.07
1
0
1110
4
s5
0.03
1
1111
4
3)哈夫曼編碼:
4) 香農(nóng)-費(fèi)諾-埃利阿斯編碼:
信源S
p(S)
F(s)
的二進(jìn)制數(shù)
碼長(zhǎng)
碼字
s1
0.37
0.37
0.185
0.00
8、101..
3
001
s2
0.25
0.62
0.495
0.01111..
3
011
s4
0.18
0.80
0.71
0.101101..
4
1011
s3
0.1
0.90
0.85
0.1101100..
5
11011
s6
0.07
0.97
0.935
0.1110111..
5
11101
s5
0.03
1.00
0.985
0.111111000..
7
1111110
5)香農(nóng)編碼:
信源S
p(S)
F(s)
F(s) 的二進(jìn)制數(shù)
碼長(zhǎng)
碼字
s1
0.37
0
9、
0.000...
2
00
s2
0.25
0.37
0.010...
2
01
s4
0.18
0.62
0.1001...
3
100
s3
0.1
0.8
0.11001...
4
1100
s6
0.07
0.9
0.11100...
4
1110
s5
0.03
0.97
0.1111100...
6
111110
6)分析哈夫曼碼,
其平均碼長(zhǎng):
平均碼元熵:
編碼效率:
碼冗余度:
7)把哈夫曼編碼器的輸出看成一個(gè)新信源X,計(jì)算其概率分布p(x1) 和 p(x2):
8)計(jì)算
相比平均碼元熵:
10、可見(jiàn),兩者很相近,但理論上不相同。因?yàn)槠骄a元熵計(jì)算的是算術(shù)平均值,而作的是統(tǒng)計(jì)平均。
5. 設(shè)有6個(gè)消息,其出現(xiàn)概率分別為
A B C D E F
1/16 1/16 2/16 3/16 4/16 5/16
將它們分別進(jìn)行費(fèi)諾編碼和霍夫曼編碼,并比較編碼效率。是否在任何情況下費(fèi)諾編碼比霍夫曼編碼效率都低?
解:信源:
費(fèi)諾編碼:
信源X
p(X)
編碼過(guò)程
碼字
碼長(zhǎng)
F
5/16
0
0
00
2
E
4/
11、16
1
01
2
D
3/16
1
0
10
2
C
2/16
1
0
110
3
B
1/16
1
0
1110
4
A
1/16
1
1111
4
平均碼長(zhǎng):碼元/符號(hào)
信源熵:比特/符號(hào)
編碼后平均碼元熵:比特/碼元
二元信源最大碼元熵為1比特/碼元,故編碼效率:
哈夫曼編碼:
由于平均碼長(zhǎng)與費(fèi)諾編碼一樣,故編碼效率也為99%。一般情況下哈夫曼編碼效率較高,但費(fèi)諾編碼如果每次劃分概率很接近,則效率也很高。
6. 有一冗余位序列,=15,碼字為001000000010000,試將其編成L-D碼,并將L-D碼譯回原序列。
解:001000000010000 N=15
編碼:
,于是得L-D碼: 0010 0101111
譯碼:
修正:
故譯碼恢復(fù)出原序列:001000000010000
作業(yè):1、2、4