平成19年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
W−8
5つのシンボル‘P’、‘Q’、‘R’、‘S’、‘T’で構成された信号をハフマン符号化
したい。各シンボルの生起確率がそれぞれ順に 0.10、0.05、0.20、0.25、0.40 で
あるとき、最も適切な符号化方法を次の中から選べ。

 @ P:0010 Q:0011 R:000  S:01   T:1
 A P:01   Q:10   R:00   S:1    T:0
 B P:0010 Q:0001 R:0100 S:0101 T:1000
 C P:010  Q:001  R:011  S:100  T:101
 D P:000  Q:001  R:01   S:10   T:11



【正解】 @

ハフマン符号は出現頻度の高い文字には短いビット列を、
出現頻度の低い文字には長いビット列を割り当てることで
全体のデータ量を圧縮する方法である。
また符号化したビット列から元の信号に戻せなければならない。

基本的には、1、01、001、0001、00001、00000
、・・・のように
最も出現頻度の高い文字には1を、
次に出現頻度の高い文字には01を、
最も出現頻度の低い文字にはオール0を割り当てる。
※0と1が入れ替わっても可。

Aは例えば、
1010 のビット列の場合、 
STST なのか QQ なのか区別できない。
BCはビット列が同じであり、ハフマン符号化ではない。

@とDが候補となるが、
@の平均ビット長は
1×0.40 + 2×0.25 + 3×0.20 + 4×0.10 + 4×0.05 =
2.1
Dの平均ビット長は
2×0.40 + 2×0.25 + 2×0.20 + 3×0.10 + 3×0.05 =
2.15

従って、最も適切な符号化方法は@である。

EXCELのマクロのご相談なら ファーストマクロ 



W−7 目次 W−9
ファーストマクロ TOPページ