【徹底解説】瞬時符号と語頭条件

本記事は情報理論の徹底解説シリーズに含まれます。

初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

概要

瞬時符号であるためには，どの符号語も他の符号語の語頭であってはなりません。これを語頭条件と呼びます。語頭条件を満たす符号が瞬時符号であることは，語頭条件の定義から明らかです（どの符号語も他の符号語の語頭でないことから先頭から符号化系列を読んでいって適合するパターンを符号語として採用していけば逐次符号化できるから）。

瞬時符号は木構造を用いて直感的に理解することができます。木構造では，各枝が0と1表していて，実際の符号語は根元から対応するノードまでを辿り，通った枝の0と1をつないだものが符号語になります。

結論

結論から言うと，瞬時符号は符号語がすべて葉に対応付けられています。

なぜ符号語がすべて葉に対応付けられている符号が瞬時符号になるのかに関しては，実際に復号する過程を木構造でイメージすると分かりやすいです。0と1からなる系列を復号するとき，根から葉に向かって対応する枝を辿っていきます。もし，全ての符号語が葉に対応していれば，葉に到達するまで他の符号語と迷う余地はありません。

一方，もし節点に符号語が割り当てられているときは，その節点を通った場合に「葉に到達するまでこの節点の符号語を採用してよいのか分からない」という状況になってしまうため，瞬時に復号することができないのです。

この木構造の考え方を身につければ，接頭条件を直感的に理解することができます。節点に符号語を割り当てているとき，節点以下に必ず葉があることを踏まえれば（子がなければそのノードは節点とは呼ばない），必ずその符号語を語頭とする符号語が存在するからです。