こんにちは！くるです！
今回は符号が瞬時符号であるための条件の「クラフトの不等式」について簡単に説明していきます！
そんなに長くないので、ぜひ最後までご覧ください！
クラフトの不等式とは？
クラフトの不等式の定義
あくまでも、瞬時符号が存在するための条件であることに注意！
$a=0, b=1$というように、コンピュータで通信するために記号を数字の並びに対応させた規則のことを「符号」と呼びます。
例えば、「0」という数字を受信したら「a」が送られてきたのだと解釈し、「1」という数字を受信したら「b」が送られてきたのだと解釈します。
また、「0」、「1」などの符号の規則1つ1つのことを「符号語」と呼びます。
$a=001, b=101$という符号なら、「001」、「101」が符号語です。
「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$$
であれば、符号語の重複は起こらないため、この式は「瞬時符号になるために必要不可欠な条件」と言えます。
なので、クラフトの不等式は「瞬時符号が存在するための条件」なんです。
今回はここまで！
お疲れ様でした！
各符号語の長さが${l_1, l_2, …, l_n}$であるr元瞬時符号が存在するための必要十分条件は次の不等式を満たすことである。
$$ \displaystyle \sum_{k=1}^n r^{-l_k} \leq 1$$
この不等式をクラフトの不等式と呼ぶ。