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
② P:01 Q:10 R:00 S:1 T:0
③ P:0010 Q:0001 R:0100 S:0101 T:1000
④ P:010 Q:001 R:011 S:100 T:101
⑤ P:000 Q:001 R:01 S:10 T:11
①
ハフマン符号は、出現頻度の高い文字には短いビット列を、出現頻度の低い文字には長いビット列を割り当てることで全体のデータ量を圧縮する方法である。
また符号化したビット列から元の信号に戻せなければならない。
基本的には、1、01、001、0001、00001、00000、・・・のように
最も出現頻度の高い文字には1を、
次に出現頻度の高い文字には01を、
最も出現頻度の低い文字にはオール0を割り当てる。
※0と1が入れ替わっても可。
① 正しい。平均ビット長は
1×0.40 ＋ 2×0.25 ＋ 3×0.20 ＋ 4×0.10 ＋ 4×0.05 = 2.1である。
② 例えば、1010のビット列の場合、STST なのか QQ なのか区別できない。
③ ビット列が同じであり、ハフマン符号化ではない。
④ ビット列が同じであり、ハフマン符号化ではない。
⑤ 平均ビット長は
2×0.40 ＋ 2×0.25 ＋ 2×0.20 ＋ 3×0.10 ＋ 3×0.05 = 2.15で①より長くなる。
| Ⅳ－７ | 目次 | Ⅳ－９ |