【徹底解説】一意復号可能な符号とは

2023年6月30日

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

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

概要

一意復号可能な符号とは，復号の仕方が一通りしかない符号のことを指します。

また，瞬時符号とは符号化した系列を前（左）から読んでいったときに，ある符号語が現れたらそれを直ちに復号することができる符号のことを指します。本記事では，一意復号可能な符号について，瞬時符号との関係性を踏まえながら分かりやすく解説していきます。

瞬時符号の集合は一意復号可能な符号の集合の真部分集合になります。

ある符号が一意復号可能かどうかを判定するのと瞬時符号かどうかを判定するのでは，瞬時符号の判定の方が簡単です。さらに，多くの場合は一意復号可能な符号として瞬時符号を扱うことがほとんどです。なぜなら，一意復号可能であって，瞬時符号でない符号を扱うメリットがないからです。

そこで，以下では瞬時符号の判定方法（語頭条件）と瞬時符号にまつわる不等式（クラフトの不等式），そして一意復号可能な符号に関する条件（マクミランの不等式・サーディナスパターソンの定理）を紹介していきます。

語頭条件は瞬時符号の判定方法です。

クラフトの不等式は瞬時符号にまつわる不等式です。本質的にはマクミランの不等式と変わりません。

マクミランの不等式は一意復号可能な符号にまつわる不等式です。

サーディナスパターソンの定理は一意復号可能な符号に関する必要十分条件です。

シェアはこちらからお願いします！