平成30年度 III-6

解説

この問題で問われていること

符号の性質(正則、一意復号可能、瞬時符号=語頭符号)の定義を、具体的な符号表に当てはめる問題。

解き方

① 符号の性質: 正則=記号ごとに違う符号語、一意復号可能=区切りが一通りに決まる、瞬時符号=どの符号語も他の符号語の頭の部分になっていない(瞬時符号なら一意復号可能)
② C1はcとdが同じ、C2は「10」がbaともcとも読める、C3は01が011の頭、C5は頭の重なりがなく瞬時符号。C4は2ビット固定長で重なりなし
③ ④

正解が正しい理由

符号C4は、a=00、b=01、c=10、d=11で、すべて2ビットの固定長である。異なる記号に、異なる符号語が割り当てられ(正則)、固定長なので、符号語の切れ目が一意に定まり、一意復号可能である。また、どの符号語も、他の符号語の語頭(接頭語)になっていないため、瞬時符号でもある。したがって④が最も適切である。

各選択肢について

• ① C1は、cとdがともに10で、異なる記号に同じ符号語が割り当てられており、正則ではない。
• ② C2は、正則(すべて異なる符号語)だが、10という符号語が、b(1)+a(0)とも、c(10)とも読めるため、一意復号可能ではない。
• ③ C3は、01(c)が011(d)の語頭になっているため、瞬時符号(語頭条件を満たす符号)ではない。「瞬時符号である」は誤り。
• ④ C4は、固定長で、一意復号可能かつ瞬時符号。これが正答。
• ⑤ C5は、0、10、110、111で、どの符号語も他の符号語の語頭になっておらず、瞬時符号(かつ一意復号可能)である。「瞬時符号ではない」は誤り。

覚えるべきポイント

瞬時符号=どの符号語も他の符号語の語頭にならない(語頭条件)。瞬時符号は必ず一意復号可能。符号語が重複すれば正則でなく、切れ目が一意でなければ一意復号可能ではない。