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

zuka

こんにちは。
zuka(@beginaid)です。

本記事は徹底解説シリーズの1つになります。記事一覧はこちらの目次ページからご覧ください。

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

概要

復号の仕方が一通りしかない符号のことを一意復号可能な符号と呼びます。また,符号化した系列を前(左)から読んでいったときに,ある符号語が現れたらそれを直ちに復号することができる符号のことを瞬時符号と呼びます。以下では,一意復号可能な符号と瞬時符号の関係性をお伝えしていこうと思います。

結論

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

一意復号可能な符号と瞬時符号の関係性

説明

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

そこで,以下では瞬時符号の判定方法(語頭条件)と瞬時符号にまつわる不等式(クラフトの不等式),そして一意復号可能な符号に関する条件(マクミランの不等式・SardinasPattersonの不等式)を紹介していきます。

語頭条件

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

クラフトの不等式

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

マクミランの不等式

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

Sardinas-Patterson(サーディナス・パターソン)の定理

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


zuka

お疲れさま!少し内部リンクが多くなってしまったけど,少しずつ理解してもらえれば嬉しいよ。「一意復号可能な符号」と聞いて「瞬時符号」「クラフトの不等式」「マクミランの不等式」「Sardinas-Pattersonの定理」の4つを思い浮かべられて,かつそれらの証明までできるようになれば鬼に金棒だよ。

シェアはこちらからお願いします!
URLをコピーする
URLをコピーしました!

コメント

コメントする