応用情報技術者試験 応用情報技術者試験 令和2年度 午前 問4: a，b，c，d の 4 文字から成るメッセージを符号化してビット列にする方法として表のア〜エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号

正解

ウ. a=0, b=10, c=110, d=111

正答率 74.7%（1,306人中 975人が正解）

問題の解説

一意に復号できるには、どの符号語も別の符号語の先頭部分にならない必要がある。そのうえで、出現頻度の高い文字に短い符号を割り当てると平均のビット長が短くなる。条件を満たすのは、a を 1 ビットにした符号と全て 2 ビットの固定長の符号で、平均長は 0.5×1 + 0.3×2 + 0.1×3 + 0.1×3 = 1.7 ビットと 2 ビットなので、前者が最短になる。

選択肢ごとの解説

• ア00 が aa とも c とも読めるなど、一意に復号できない。平均は 1.2 ビットと短いが、条件を満たさない。
• イ010 が a と c の並びとも b と a の並びとも読めるので、一意に復号できない。平均は 1.5 ビットと短いが、条件を満たさない。
• ウ正しい。どの符号語も他の符号語の先頭にならないので一意に復号でき、平均は 0.5×1 + 0.3×2 + 0.1×3 + 0.1×3 = 1.7 ビットで、条件を満たす中で最短である。
• エ全て 2 ビットの固定長で一意に復号できるが、平均が 2 ビットで、頻度の偏りを生かした符号より長い。