クラフトの不等式って何?分かりやすく解説!

こんにちは!krです!

今回は符号が瞬時符号であるための条件の「クラフトの不等式」について簡単に説明していきます!

そんなに長くないので、ぜひ最後までご覧ください!

初学者におすすめの情報理論の参考書3選

クラフトの不等式とは?

クラフトの不等式の定義

クラフトの不等式

各符号語の長さが${l_1, l_2, …, l_n}$であるr元瞬時符号が存在するための必要十分条件は次の不等式を満たすことである。

$$ \displaystyle \sum_{k=1}^n r^{-l_k} \leq 1$$

この不等式をクラフトの不等式と呼ぶ。

あくまでも、瞬時符号が存在するための条件であることに注意!

先生
先生
符号と符号語

$a=0, b=1$というように、コンピュータで通信するために記号を数字の並びに対応させた規則のことを「符号」と呼びます。

例えば、「0」という数字を受信したら「a」が送られてきたのだと解釈し、「1」という数字を受信したら「b」が送られてきたのだと解釈します。

また、「0」、「1」などの符号の規則1つ1つのことを「符号語」と呼びます。

$a=001, b=101$という符号なら、「001」、「101」が符号語です。

r元とは?

r元」というのは、「符号語に使われる数字の種類」のことを表しています。例えば、2元符号なら「0,1」、3元なら「0, 1, 2」が符号語の構成要素として使われます。

なぜ”存在するため”の条件なのか?

例えば、次のような符号を考えてみましょう。

$$a=00, \ b=01, \ c=10, \ d=11$$

この符号は完全符号と呼ばれているもので、次のように符号木の全ての枝に符号が割り振られていることからそう呼ばれています。

ここで、$e=00$という符号が追加されたとしましょう。

この符号は瞬時符号になるでしょうか?

先生
先生
くるる
くるる

「$00$」を受信しても、「$a$」なのか「$e$」なのか分からないから瞬時符号じゃないっす!

その通り!

先生
先生

ということは、完全符号より符号語が多くなってしまうと、どこかで符号語の重複が起きてしまい、瞬時符号にはならないということです。

なので、瞬時符号になるためには、符号語の数は完全符号の符号語の数より少ない必要があります。

上の例の完全符号の$\displaystyle \sum_{k=1}^n r^{-l_k}$を計算すると、

$$\displaystyle \sum_{k=1}^4 r^{-l_k}=2^{-2}+2^{-2}+2^{-2}+2^{-2}=1$$

となります。したがって、

$$ \displaystyle \sum_{k=1}^n r^{-l_k} \leq 1$$

であれば、符号語の重複は起こらないため、この式は「瞬時符号になるために必要不可欠な条件」と言えます。

なので、クラフトの不等式は「瞬時符号が存在するための条件」なんです。

今回はここまで!

お疲れ様でした!

先生
先生
おすすめの参考書

初学者におすすめな参考書を調査してまとめてみました。良かったら参考にしてください。

初学者におすすめの情報理論の参考書3選

コメントを残す

CAPTCHA


PHP Code Snippets Powered By : XYZScripts.com