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

zuka

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

本記事は情報理論の徹底解説シリーズに含まれます。記事一覧はこちらの目次ページからご覧ください。

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

目次

概要

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

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

結論

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

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

説明

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

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

語頭条件

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

クラフトの不等式

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

マクミランの不等式

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

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

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

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

コメント

コメントする

※スパム対策のためコメントは日本語で入力してください。

目次
目次
閉じる