問題プレビューID: be3d69b4応用情報技術者試験 2020年(令和2年度)10月 午前

問 4
応用情報技術者試験 2020年(令和2年度)10月 午前

a,b,c,d の 4 文字から成るメッセージを符号化してビット列にする方法として,表のア〜エの 4 通りを考えた。この表は a,b,c,d の各 1 文字を符号化するときのビット列を表している。メッセージ中での a,b,c,d の出現頻度は,それぞれ 50%,30%,10%,10% であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって,ビット列の長さが最も短くなるものはどれか。

Label

a

b

c

d

ア

0

1

00

11

イ

0

01

10

11

ウ

0

10

110

111

エ

00

01

10

11

解説

正解は「ウ」です。

一意に復号できるためには,どの符号語も他の符号語の先頭部分(プリフィックス)になっていないことが必要です。この条件を満たすのはウとエです。

  • ア: a の「0」が c の「00」の先頭部分になっており,一意に復号できません。
  • イ: a の「0」が b の「01」の先頭部分になっており,一意に復号できません。
  • エ: すべて 2 ビットの固定長なので一意に復号できますが,1 文字当たり常に 2 ビット必要で平均符号長は 2 ビットになります。
  • ウ: 平均符号長は 0.5×1+0.3×2+0.1×3+0.1×3=1.70.5 \times 1 + 0.3 \times 2 + 0.1 \times 3 + 0.1 \times 3 = 1.7 ビットとなり,エより短くなります。

よって,正解は「ウ」です。

関連問題

本文が同じ・似ている問題を表示しています