令和2年度 10月 午前 問4

✓ これが正解ウa=0, b=10, c=110, d=111

解説

まず一意復号の可否、次に期待長で比べます。

符号化の候補を選ぶ設問は、二段の関門を順に通します。前の関門は、符号化されたビット列から元の並びへ戻せるかどうかで、これは各文字の符号がほかの文字の符号の頭にならないという性質、いわゆる語頭符号になっているかを確かめる作業に当たります。ここで戻せない候補はまず脱落します。後ろの関門は、戻せるものだけを対象に、頻度の高い文字に短い符号、低い文字に長い符号を割り当てて、頻度と符号長を掛けて足した平均ビット長が小さいかどうかを比べる作業です。二段を経て残るのは、頻度 50 の文字を 1 ビット、頻度 30 を 2 ビット、頻度 10 と 10 を 3 ビットで表す割り当てで、期待長は 0.5 × 1 ＋ 0.3 × 2 ＋ 0.1 × 3 ＋ 0.1 × 3 ＝ 1.7 ビットです。

ほかの選択肢はなぜ違うのか

• アa=0, b=1, c=00, d=11：割り当ては a=0、b=1、c=00、d=11 と書かれています。a=0 が c=00 の頭になり、b=1 が d=11 の頭になっていて、受け側は 00 を a a と読むのか c と読むのかを区別できず一意に復号できません。
• イa=0, b=01, c=10, d=1…：割り当ては a=0、b=01、c=10、d=11 と書かれています。a=0 が b=01 の頭になっており、受け側は 010 を a c と読むのか b a と読むのかを区別できず、こちらも一意復号の条件を満たしません。
• エa=00, b=01, c=10, d=…：割り当ては a=00、b=01、c=10、d=11 と書かれています。全部が 2 ビット固定なので一意に復号できます。ただし期待長が 2.0 ビットとなり、頻度に応じて長さを変えた割り当ての 1.7 ビットに及びません。