【符号理論】クラフトの不等式と情報源符号化定理のメモ

したがって、
$$ a\in\Sigma $$
であることは、$a$ がアルファベット $\Sigma$ に属する文字(記号)であることを意味する。

空集合 $\varnothing$ から $\Sigma$ への写像はただ $1$ つしか存在しない。
実際、写像 $f:\varnothing\to\Sigma$ は、任意の $x\in\varnothing$ に対して値 $f(x)\in\Sigma$ を定めるものである。
$ $
しかし、$\varnothing$ には元が存在しないため、値を指定すべき対象が存在しない。
したがって、空集合から $\Sigma$ への写像はただ $1$ つである。この意味で、長さ $0$ の文字列は一意である。

空文字列 $\varepsilon$ は、長さ $0$ の文字列であって、アルファベット $\Sigma$ の文字ではない。
したがって、通常は
$$ \varepsilon\notin\Sigma $$
として扱う。
また、$\varepsilon$ はスペース記号ではない。
スペース記号を文字として扱いたい場合には、スペース記号を $\Sigma$ の元として明示的に含める必要がある。

定義より、空文字列は $\Sigma$ 上の長さ $0$ の文字列であるから、
$$ \varepsilon\in\Sigma^0\subseteq\Sigma^* $$
である。
したがって、
$$ \varepsilon\in\Sigma^* $$
である。

例えば $\Sigma=\{a,b,c\}$ とすると、
$$ \Sigma^1 = \{w\mid w:\{1\}\to\Sigma\} $$
である。
したがって、$\Sigma^1$ の元は、次の $3$ つの写像である。
$$ w_a:\{1\}\to\Sigma,\quad w_a(1)=a $$
$$ w_b:\{1\}\to\Sigma,\quad w_b(1)=b $$
$$ w_c:\{1\}\to\Sigma,\quad w_c(1)=c $$
よって、
$$ \Sigma^1=\{w_a,w_b,w_c\} $$
である。

$a\in\Sigma$ を文字とする。
厳密には、文字 $a$ と、長さ $1$ の文字列
$$ w_a:\{1\}\to\Sigma,\quad w_a(1)=a $$
は、一般には異なる対象である。
しかし、対応
$$ \Sigma\to\Sigma^1,\quad a\mapsto w_a $$
は全単射である。
$ $
実際、各 $a\in\Sigma$ に対して、$w_a$ は第 $1$ 文字が $a$ である長さ $1$ の文字列である。
また、長さ $1$ の文字列 $w:\{1\}\to\Sigma$ は、値 $w(1)\in\Sigma$ によって一意に定まる。
$ $
そのため、ここでは文字 $a$ と長さ $1$ の文字列 $w_a$ を同一視し、どちらも同じ記号 $a$ で表す。
この同一視のもとで、
$$ \Sigma^1=\Sigma $$
とみなす(※1)。
$ $
例えば、
$$ \Sigma=\{\mathtt{0},\mathtt{1}\} $$
ならば、厳密には $\Sigma^1$ の元は
$$ w_{\mathtt{0}}:\{1\}\to\Sigma,\quad w_{\mathtt{0}}(1)=\mathtt{0} $$
と
$$ w_{\mathtt{1}}:\{1\}\to\Sigma,\quad w_{\mathtt{1}}(1)=\mathtt{1} $$
である。
しかし、$w_{\mathtt{0}}$ を $\mathtt{0}$ と書き、$w_{\mathtt{1}}$ を $\mathtt{1}$ と書く約束をすれば、
$$ \Sigma^1=\{\mathtt{0},\mathtt{1}\} $$
とみなせる。
この同一視のもとで、
$$ \Sigma\subseteq\Sigma^* $$
とみなす(※2)。
$ $
※1 より厳密には、$\Sigma^1\cong\Sigma$ である。
※2 より厳密には、写像 $\Sigma\to\Sigma^*,\quad a\mapsto w_a$ によって、$\Sigma$ を $\Sigma^*$ の部分集合と同一視している。

例えば、形式言語で扱う対象の集合 $U$ の中から、$2$ つの対象 $\mathtt{0}$ と $\mathtt{1}$ を選び、
$$ \Sigma=\{\mathtt{0},\mathtt{1}\} $$
と定める。
このとき、$\Sigma$ は空でない有限集合であるから、アルファベットである。
また、$\mathtt{0}\in\Sigma$ と $\mathtt{1}\in\Sigma$ であるから、$\mathtt{0}$ と $\mathtt{1}$ はアルファベット $\Sigma$ に属する文字、または記号である。
$ $
$\Sigma$ 上の長さ $3$ の文字列の例として、写像
$$ w:\{1,2,3\}\to\Sigma $$
を
$$ w(1)=\mathtt{0},\quad w(2)=\mathtt{1},\quad w(3)=\mathtt{0} $$
で定める。このとき、$w$ は $\Sigma$ 上の長さ $3$ の文字列であり、通常は
$$ \mathtt{010} $$
と書く。
また、この文字列の長さは
$$ |w|=3 $$
である。
一方、$\Sigma$ 上の長さ $0$ の文字列は、空集合 $\varnothing$ から $\Sigma$ へのただ $1$ つの写像であり、これを空文字列と呼び、
$$ \varepsilon $$
で表す。このとき、
$$ |\varepsilon|=0 $$
である。さらに、
$$ \Sigma^0=\{\varepsilon\} $$
である。
また、文字と長さ $1$ の文字列を同一視すれば、
$$ \Sigma^1=\{\mathtt{0},\mathtt{1}\} $$
とみなせる。
また、長さ $2$ の文字列全体は
$$ \Sigma^2=\{\mathtt{00},\mathtt{01},\mathtt{10},\mathtt{11}\} $$
である。
このように、
$$ \varepsilon,\quad \mathtt{0},\quad \mathtt{1},\quad \mathtt{00},\quad \mathtt{01},\quad \mathtt{10},\quad \mathtt{11},\quad \mathtt{010} $$
などはすべて $\Sigma$ 上の有限文字列であり、
$$ \Sigma^* = \bigcup_{n=0}^{\infty}\Sigma^n $$
は、これらのような $\Sigma$ 上のすべての有限文字列からなる集合である。

この定義では、$X_1,X_2,\ldots$ の独立性や同分布性は仮定していない。
したがって、ここで定義した離散情報源は、一般の有限アルファベット値確率過程である。
無記憶情報源、定常情報源、独立同分布情報源などは、この離散情報源に追加の条件を課して得られる特別な場合である。
$ $
このように、調べると情報源にも様々な種類があるみたいなんだけど、
とりあえず、本稿ではそこまで立ち入る必要はない(と思われる)ので、この程度に留めておく(´ω｀)

確率空間 $(\Omega,\mathcal F,\mathbb P)$ は、情報源に含まれるランダム性を記述するための基礎となる空間である。
各 $\omega\in\Omega$ は、情報源の $1$ つの実現結果を表す。
例えば、情報源が無限回のコイン投げにより記号を出力する場合、
$$ \Omega=\{\mathrm H,\mathrm T\}^{\mathbb N} $$
とおくことができる。
このとき、$\omega\in\Omega$ は
$$ \omega=(\omega_1,\omega_2,\omega_3,\ldots) $$
という無限列であり、各 $\omega_t$ は第 $t$ 回目のコイン投げの結果を表す。
$ $
厳密には、$\mathcal F$ を $\{\mathrm H,\mathrm T\}^{\mathbb N}$ 上の積 $\sigma$ 加法族とし、$\mathbb P$ をベルヌーイ測度の積測度として定める。
この確率空間 $(\Omega,\mathcal F,\mathbb P)$ 上で、各 $t\in\mathbb N$ に対して
$$ X_t:\Omega\to\{\mathrm H,\mathrm T\},\qquad X_t(\omega)=\omega_t $$
と定めれば、$X_t$ は第 $t$ 回目のコイン投げの結果を表す確率変数である。

符号 $f$ が文脈から明らかな場合には、$\ell_f(x)$ を単に
$$ \ell(x) $$
と書くことがある。

離散情報源
$$ S=(X_t)_{t\in\mathbb N} $$
の出力アルファベットが $\mathcal X$ であるとき、符号化では通常、この $\mathcal X$ の元を符号化対象とする。
すなわち、情報源が出力する記号 $x\in\mathcal X$ に対して、符号語
$$ f(x)\in\Sigma^* $$
を割り当てる。

上の定義では、符号 $f$ が単射であることは仮定していない。
したがって、異なる $x,y\in\mathcal X$ に対して
$$ f(x)=f(y) $$
となることも、定義上は排除されていない。
異なる符号化対象を異なる符号語で表したい場合には、追加で
$$ x\ne y\Rightarrow f(x)\ne f(y) $$
を仮定する。
この性質を満たす符号を非特異符号という。

$\Sigma^*$ には空文字列 $\varepsilon$ が含まれるため、上の定義だけでは
$$ f(x)=\varepsilon $$
となることも許される。
ただし、後で一意復号可能符号(後述)や接頭辞符号(後述)を扱う場合には、通常、各 $x\in\mathcal X$ に対して
$$ f(x)\ne\varepsilon $$
を追加で仮定する。

離散情報源
$$ S=(X_t)_{t\in\mathbb N} $$
の出力アルファベットを
$$ \mathcal X=\{\text{晴},\text{雨},\text{曇}\} $$
とする。
符号アルファベットを
$$ \Sigma=\{\mathtt 0,\mathtt 1\} $$
とし、符号
$$ f:\mathcal X\to\Sigma^* $$
を
$$ f(\text{晴})=\mathtt 0,\quad f(\text{雨})=\mathtt {10},\quad f(\text{曇})=\mathtt {11} $$
で定める。このとき、

1. 情報源がある時刻に $\text{晴}$ を出力したならば、その記号に符号語
   $$ \mathtt 0 $$
   を割り当てる。
   $ $
2. 同様に、情報源が $\text{雨}$ を出力したならば、
   $$ \mathtt {10} $$
   を割り当てる。
   $ $
3. 情報源が $\text{曇}$ を出力したならば、
   $$ \mathtt {11} $$
   を割り当てる。

-したがって、符号長は
$$ \ell_f(\text{晴})=1,\quad \ell_f(\text{雨})=2,\quad \ell_f(\text{曇})=2 $$
である。例えば、情報源が
$$ \text{晴},\text{雨},\text{曇} $$
という $3$ 個の記号を順に出力したとする。
このとき、それぞれの符号語を連結すると、
$$ f(\text{晴})f(\text{雨})f(\text{曇}) = \mathtt 0\ \mathtt {10}\ \mathtt {11} = \mathtt {01011} $$
となる。
この連結された文字列の長さは
$$ | \mathtt {01011} |=5 $$
であり、
$$ \ell_f(\text{晴})+\ell_f(\text{雨})+\ell_f(\text{曇}) = 1+2+2 = 5 $$
と一致する。

符号化対象の集合を
$$ \mathcal X=\{a,b,c\} $$
とし、符号アルファベットを
$$ \Sigma=\{\mathtt 0,\mathtt 1\} $$
とする。
写像
$$ f:\mathcal X\to\Sigma^* $$
を
$$ f(a)=\mathtt 0,\quad f(b)=\mathtt {10},\quad f(c)=\mathtt {11} $$
で定める。
このとき、異なる元には異なる符号語が対応している。すなわち、任意の $x,y\in\mathcal X$ に対して、
$$ x\ne y\Rightarrow f(x)\ne f(y) $$
が成り立つ。
したがって、この $f$ は非特異符号である。

符号化対象の集合を
$$ \mathcal X=\{a,b,c\} $$
とし、符号アルファベットを
$$ \Sigma=\{\mathtt 0,\mathtt 1\} $$
とする。ここで、写像
$$ g:\mathcal X\to\Sigma^* $$
を
$$ g(a)=\mathtt 0,\quad g(b)=\mathtt 0,\quad g(c)=\mathtt 1 $$
で定める。このとき、
$$ a\ne b $$
であるが、
$$ g(a)=g(b)=\mathtt 0 $$
である。したがって、$g$ は単射ではない。ゆえに、$g$ は非特異符号ではない。
この例では、符号語 $\mathtt 0$ だけを見ても、それが $a$ を表しているのか $b$ を表しているのか判別できない。

$n\in\mathbb N_0$ とする。
$\mathcal D$ 上の長さ $n$ の文字列を、長さ $n$ のビット列という。
すなわち、ビット列とは、二進アルファベット
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
上の有限文字列である。
したがって、ビット列全体の集合は
$$ \mathcal D^* $$
である。
特に、空文字列 $\varepsilon$ は長さ $0$ のビット列であり、
$$ \varepsilon\in\mathcal D^* $$
である。
例えば、
$$ \varepsilon,\quad \mathtt 0,\quad \mathtt 1,\quad \mathtt{00},\quad \mathtt{01},\quad \mathtt{10},\quad \mathtt{11},\quad \mathtt{0101} $$
などはビット列である。

$u\in\mathcal D^*$ とする。
文字列 $u$ の長さ $|u|$ を、$u$ のビット数という。
すなわち、$|u|$ はビット列 $u$ に含まれるビット記号の個数である。
$ $
例えば、
$$ u=\mathtt{0101} $$
であれば、
$$ |u|=4 $$
であるから、$u$ は $4$ ビットのビット列である。
また、
$$ |\varepsilon|=0 $$
であるから、空文字列 $\varepsilon$ は $0$ ビットのビット列である。

情報理論におけるビットと、符号理論におけるビット記号は、密接に関係するが、使われ方が異なる。

1. 符号理論におけるビット記号は、二進アルファベット
   $$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
   の元である。
   ビット列のビット数は、そのビット列に含まれる二進記号の個数である。
   例えば、二進符号語
   $$ \mathtt{0101} $$
   は $4$ 個の二進記号からなるので、$4$ ビットの符号語である。
   $ $
2. 一方、情報理論におけるビットは、底 $2$ の対数で測った情報量の単位である。
   例えば、事象 $A$ が
   $$ \mathbb P(A)=\frac{1}{2} $$
   を満たすとき、自己情報量は
   $$ I_2(A) = -\log_2\mathbb P(A) = -\log_2\frac{1}{2} = 1 $$
   であるから、$A$ の自己情報量は $1$ ビットである( 詳しくはコチラ )。

-両者の関係は、符号化によって表される。
有限集合 $\mathcal X$ に値をもつ情報源 $X$ を二進符号 $C:\mathcal X\to\mathcal D^*$ によって符号化するとき、平均符号長
$$ L_X(C) = \sum_{x\in\mathcal X}p_X(x)\ell_C(x) $$
は、実際に平均して何個の二進記号を使うかを表す。
一方、エントロピー
$$ H_2(X) = -\sum_{x\in\mathcal X}p_X(x)\log_2 p_X(x) $$
は、情報源 $X$ が平均してどれだけの情報量をもつかを表す。
$ $
したがって、直感的には、
$$ \text{情報理論のビット} = \text{理論的な情報量の単位} $$
であり、
$$ \text{符号理論のビット} = \text{実際に使う二進記号の個数} $$
である。
適切な仮定のもとで、一意復号可能な二進符号では、平均符号長は情報源のエントロピーより小さくできない。
すなわち、有限値情報源 $X$ と一意復号可能な二進符号 $C$ に対して、
$$ L_X(C)\ge H_2(X) $$
が成り立つ。
この意味で、情報理論のビットは「どれだけの情報を表す必要があるか」を与え、符号理論のビットは「それを表すために実際に何個の二進記号を使うか」を与える。

すなわち、$\mathcal X\ne\varnothing$ のもとでは、任意の $x,y\in\mathcal X$ に対して、
$$ \ell_C(x)=\ell_C(y) $$
が成り立つことと同値である。

上の定義では、固定長符号の符号語長として $m=0$ も許している。
この場合、任意の $x\in\mathcal X$ に対して、
$$ \ell_C(x)=0 $$
である。
長さ $0$ の文字列は空文字列 $\varepsilon$ のみであるから、任意の $x\in\mathcal X$ に対して、
$$ C(x)=\varepsilon $$
が成り立つ。
したがって、$\mathcal X$ が $2$ 個以上の元をもつ場合、異なる $x,y\in\mathcal X$ に対しても
$$ C(x)=C(y)=\varepsilon $$
となる。
ゆえに、この固定長符号は非特異符号ではない。

情報源は、たとえば文字、単語、記号などを順に出力する確率的な仕組みとして考えられる。
このとき、各記号 $x\in\mathcal X$ には出現確率
$$ p(x) $$
が対応していると考えることができる。
自然言語の文章を情報源として見る場合、文字や単語の出現頻度は一般に一様ではない。
$ $
そのため、出現確率の高い記号と低い記号を同じ長さのビット列で表現する固定長符号よりも、
出現確率に応じて符号語の長さを変える可変長符号の方が、平均符号長を短くできる場合がある。

文字列 $\mathtt{HELLO}$ を考える。
この文字列で用いられている文字の集合は
$$ \mathcal X=\{\mathtt H,\mathtt E,\mathtt L,\mathtt O\} $$
である。
ここで、$\mathcal X$ の各文字に $\mathrm{ASCII}$ の $7$ ビット表現を割り当てると、
$$ C(\mathtt H)=\mathtt{1001000},\quad C(\mathtt E)=\mathtt{1000101},\quad C(\mathtt L)=\mathtt{1001100},\quad C(\mathtt O)=\mathtt{1001111} $$
である。
したがって、文字列 $\mathtt{HELLO}$ は
$$ \mathtt{1001000\,1000101\,1001100\,1001100\,1001111} $$
というビット列で表される。
この符号は、各文字に長さ $7$ のビット列を割り当てているので、固定長符号である。
$ $
ただし、この例で用いている $\mathrm{ASCII}$ は標準的な文字コードであり、$\mathcal X=\{\mathtt H,\mathtt E,\mathtt L,\mathtt O\}$ のみに対する最短の固定長符号ではない。
実際、$\mathcal X$ は $4$ 個の元からなるため、二進固定長符号としては長さ $2$ の符号語で各文字を区別できる。
例えば、
$$ C'(\mathtt H)=\mathtt{00},\quad C'(\mathtt E)=\mathtt{01},\quad C'(\mathtt L)=\mathtt{10},\quad C'(\mathtt O)=\mathtt{11} $$
とすれば、$C'$ は $\mathcal X$ 上の非特異な固定長二進符号である。

固定長符号では、すべての情報源記号に対して同じ長さの符号語を割り当てる。
例えば、$\mathcal X=\{a,b,c,d\}$ に対して、
$$ C(a)=\mathtt{00},\quad C(b)=\mathtt{01},\quad C(c)=\mathtt{10},\quad C(d)=\mathtt{11} $$
と定めると、すべての符号語の長さは $2$ であるから、この符号は固定長符号である。
$ $
一方、可変長符号では、情報源記号によって符号語の長さが異なる。
例えば、$\mathcal X=\{a,b,c\}$ に対して、
$$ C(a)=\mathtt{0},\quad C(b)=\mathtt{10},\quad C(c)=\mathtt{11} $$
と定めると、
$$ \ell_C(a)=1,\quad \ell_C(b)=2,\quad \ell_C(c)=2 $$
であるから、この符号は可変長符号である。

$\mathcal X$ の元が $1$ 個だけの場合、任意の二進符号 $C:\mathcal X\to\mathcal D^*$ は固定長符号である。
したがって、可変長符号が存在するためには、少なくとも
$$ |\mathcal X|\geq2 $$
であることが必要である。

可変長符号であることは、符号語の長さがすべて同じではないことだけを意味する。
したがって、可変長符号であることだけから、一意復号可能(後述)であることや接頭辞符号(後述)であることは従わない。
一意復号可能符号(後述)や接頭辞符号(後述)は、可変長符号に追加の条件を課して得られる符号のクラスである。

可変長符号では、記号ごとに符号語の長さを変える。
たとえば、出現確率の高い記号には短い符号語を割り当て、出現確率の低い記号には長い符号語を割り当てることで、符号長の平均を小さくできる場合がある。
$ $
ただし、この方針が数学的に最適であるというためには、符号のクラスと最小化する量を明示する必要がある。
たとえば、与えられた確率分布に対して、接頭辞符号の中で平均符号長
$$ \sum_{x\in\mathcal X}p(x)|C(x)| $$
を最小にする符号を考えると、ハフマン符号と呼ばれる符号化では、そのような最適な接頭辞符号を与える。

可変長符号を使えば、必ずすべての個別の記号列が固定長符号より短く表現できるわけではない。
正確には、確率分布に適した可変長符号を用いることで、平均符号長を固定長符号より短くできる場合がある。
したがって、可変長符号の利点は、個々の記号列の長さではなく、確率分布に関する平均的な符号長によって評価するのが自然である。

$\mathcal X^*$ や $\mathcal D^*$ の $*$ は、クリーネ閉包を表す。
一方、$C^\dagger$ の $\dagger$ は、符号 $C$ から定まる拡張写像を表す記号として用いる。

$u,v\in\mathcal D^*$ とする。
$u$ と $v$ の連結とは、文字列 $u$ の後ろに文字列 $v$ を続けて得られる文字列のことをいう。
この連結を
$$ uv $$
で表す。
例えば、
$$ u=\mathtt{01},\quad v=\mathtt{110} $$
であるとき、
$$ uv=\mathtt{01110} $$
である。
したがって、
$$ C(x_1)C(x_2)\cdots C(x_n) $$
は、各記号 $x_1,\ldots,x_n$ に対応する符号語を順番に連結して得られる $1$ つの二進文字列を表す。

符号の拡張 $C^\dagger$ は、任意の二進符号 $C:\mathcal X\to\mathcal D^*$ に対して定義できる。
ただし、$C^\dagger$ が単射であるとは限らない。
$C^\dagger$ が単射であるとき、符号語を連結して得られた二進文字列から、もとの $\mathcal X$ 上の文字列を一意に復元できる。
この性質をもつ符号を、一意復号可能符号という。

同じく、
$$ \mathcal X=\{a,b,c\},\quad \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とし、
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt {10},\quad C(c)=\mathtt {11} $$
とする。
このとき、空文字列 $\varepsilon\in\mathcal X^*$ については、拡張の定義により、
$$ C^\dagger(\varepsilon)=\varepsilon $$
である。
つまり、入力側で記号が何も並んでいない場合、出力側でも符号記号は何も出力されない。

二進符号
$$ C:\mathcal X\to\mathcal D^* $$
を
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt {10},\quad C(c)=\mathtt {11} $$
で定める。このとき、
$$ \ell_C(a)=1,\quad \ell_C(b)=2,\quad \ell_C(c)=2 $$
である。文字列
$$ bbac\in\mathcal X^* $$
を考えると、
$$ \begin{align} C^\dagger(bbac) &=C(b)C(b)C(a)C(c)\\ &=\mathtt {10}\mathtt {10}\mathtt 0\mathtt {11}\\ &=\mathtt {1010011} \end{align} $$
である。したがって、
$$ |C^\dagger(bbac)|=|\mathtt {1010011}|=7 $$
である。一方で、
$$ \ell_C(b)+\ell_C(b)+\ell_C(a)+\ell_C(c) = 2+2+1+2 = 7 $$
である。
よって、この例では
$$ |C^\dagger(bbac)| = \ell_C(b)+\ell_C(b)+\ell_C(a)+\ell_C(c) $$
が成り立っている。
一般に、$x_1,\ldots,x_n\in\mathcal X$ に対して、
$$ |C^\dagger(x_1x_2\cdots x_n)| = \sum_{i=1}^{n}|C(x_i)| = \sum_{i=1}^{n}\ell_C(x_i) $$
である。

二進アルファベットを
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とし、情報源アルファベットを
$$ \mathcal X=\{a,b,c\} $$
とする。二進符号
$$ C:\mathcal X\to\mathcal D^* $$
を
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt {01},\quad C(c)=\mathtt 1 $$
で定める。このとき、$C$ 自体は異なる記号に異なる符号語を割り当てているので、非特異符号である。
実際、
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt {01},\quad C(c)=\mathtt 1 $$
は互いに異なる。
しかし、拡張 $C^\dagger$ を考えると、
$$ C^\dagger(b)=C(b)=\mathtt {01} $$
であり、また、
$$ C^\dagger(ac)=C(a)C(c)=\mathtt 0\mathtt 1=\mathtt {01} $$
である。したがって、
$$ C^\dagger(b)=C^\dagger(ac) $$
である。
一方で、$\mathcal X^*$ の文字列としては、
$$ b\ne ac $$
である。
ゆえに、この例では
$$ C^\dagger:\mathcal X^*\to\mathcal D^* $$
は単射ではない。
これは、符号語列として $\mathtt {01}$ が送られてきたとき、それを
$$ b $$
と読むことも、
$$ ac $$
と読むこともできることを意味する。

二進アルファベットを
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とし、情報源アルファベットを
$$ \mathcal X=\{a,b\} $$
とする。二進符号
$$ C:\mathcal X\to\mathcal D^* $$
を
$$ C(a)=\varepsilon,\quad C(b)=\mathtt 0 $$
で定める。このとき、
$$ C^\dagger(a)=C(a)=\varepsilon $$
である。
また、拡張の定義により、
$$ C^\dagger(\varepsilon)=\varepsilon $$
である。したがって、
$$ C^\dagger(a)=C^\dagger(\varepsilon) $$
である。
しかし、$\mathcal X^*$ の文字列としては、
$$ a\ne\varepsilon $$
である。ゆえに、この例では $C^\dagger$ は単射ではない。
さらに、
$$ \begin{align} C^\dagger(ab) &=C(a)C(b)\\ &=\varepsilon\mathtt 0\\ &=\mathtt 0 \end{align} $$
であり、
$$ C^\dagger(b)=C(b)=\mathtt 0 $$
である。
したがって、
$$ C^\dagger(ab)=C^\dagger(b) $$
である。
このように、空符号語を許すと、拡張後の文字列の区切りが失われやすくなる。

一意復号可能符号では、空文字列 $\varepsilon$ は符号語として現れない。
実際、ある $x\in\mathcal X$ に対して
$$ C(x)=\varepsilon $$
であると仮定する。
このとき、(例えば 長さ $1$ の)文字列 $x\in\mathcal X^*$ について、
$$ C^\dagger(x)=C(x)=\varepsilon $$
となる。
一方、拡張の定義より
$$ C^\dagger(\varepsilon)=\varepsilon $$
である。
したがって、
$$ C^\dagger(x)=C^\dagger(\varepsilon) $$
である。
しかし、$x$ は長さ $1$ の文字列であり、$\varepsilon$ は長さ $0$ の文字列であるから、
$$ x\ne\varepsilon $$
である。よって、$C^\dagger$ は単射ではない。
したがって、一意復号可能符号であるためには、任意の $x\in\mathcal X$ に対して
$$ C(x)\ne\varepsilon $$
でなければならない。

非特異符号は、$1$ つの情報源記号を符号化したときに、異なる記号が同じ符号語に写らないことを意味する。
すなわち、二進符号 $C:\mathcal X\to\mathcal D^*$ が非特異であるとは、写像 $C$ が単射であることをいう。
$ $
一方、一意復号可能符号は、記号列全体を符号化したときに、異なる記号列が同じ符号列に写らないことを意味する。
すなわち、二進符号 $C:\mathcal X\to\mathcal D^*$ が一意復号可能であるとは、拡張写像
$$ C^\dagger:\mathcal X^*\to\mathcal D^* $$
が単射であることをいう。

二進アルファベットを
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とする。
情報源アルファベットを
$$ \mathcal X=\{a,b,c\} $$
とし、二進符号
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt {10},\quad C(c)=\mathtt {11} $$
を考える。
このとき、符号列
$$ \mathtt {010110} $$
を受け取ったとする。
左から順に区切ると、
$$ \mathtt 0\,\mathtt {10}\,\mathtt {11}\,\mathtt 0 $$
である。
したがって、
$$ \mathtt 0=C(a),\quad \mathtt {10}=C(b),\quad \mathtt {11}=C(c),\quad \mathtt 0=C(a) $$
より、
$$ \mathtt {010110} = C^\dagger(abca) $$
である。
この符号では、この二進文字列を他の情報源記号列から得ることはできない。
すなわち、
$$ C^\dagger(u)=\mathtt {010110} $$
を満たす $u\in\mathcal X^*$ は
$$ u=abca $$
に限られる。
このように、符号化された二進文字列から元の情報源記号列がただ $1$ 通りに決まることが、一意復号可能性の意味である。

二進アルファベットを
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とする。情報源アルファベットを
$$ \mathcal X=\{a,b,c\} $$
とし、二進符号
$$ C:\mathcal X\to\mathcal D^* $$
を
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt {01},\quad C(c)=\mathtt 1 $$
で定める。このとき、
$$ C(a),\ C(b),\ C(c) $$
は互いに異なる。したがって、$C$ は非特異符号である。
しかし、
$$ b\in\mathcal X^* $$
と
$$ ac\in\mathcal X^* $$
を考えると、
$$ b\ne ac $$
である。一方で、
$$ C^\dagger(b)=C(b)=\mathtt {01} $$
であり、
$$ \begin{align} C^\dagger(ac) &=C(a)C(c)\\ &=\mathtt 0\mathtt 1\\ &=\mathtt {01} \end{align} $$
である。したがって、
$$ C^\dagger(b)=C^\dagger(ac) $$
である。
よって、異なる情報源記号列 $b$ と $ac$ が同じ二進文字列 $\mathtt {01}$ に符号化される。
ゆえに、$C^\dagger$ は単射ではない。
したがって、この符号 $C$ は一意復号可能符号ではない。

二進アルファベットを
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とする。
情報源アルファベットを
$$ \mathcal X=\{a,b,c\} $$
とし、二進符号
$$ C:\mathcal X\to\mathcal D^* $$
を
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt 0,\quad C(c)=\mathtt 1 $$
で定める。
このとき、
$$ a\ne b $$
であるが、
$$ C(a)=C(b)=\mathtt 0 $$
である。したがって、$C$ は非特異符号ではない。
さらに、長さ $1$ の文字列 $a,b\in\mathcal X^*$ を考えると、
$$ a\ne b $$
である。
しかし、
$$ C^\dagger(a)=C(a)=\mathtt 0 $$
であり、
$$ C^\dagger(b)=C(b)=\mathtt 0 $$
である。したがって、
$$ C^\dagger(a)=C^\dagger(b) $$
である。よって、$C^\dagger$ は単射ではない。
したがって、この符号 $C$ は一意復号可能符号ではない。

二進アルファベットを
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とする。
情報源アルファベットを
$$ \mathcal X=\{a,b\} $$
とし、二進符号
$$ C:\mathcal X\to\mathcal D^* $$
を
$$ C(a)=\varepsilon,\quad C(b)=\mathtt 0 $$
で定める。
このとき、長さ $1$ の文字列 $a\in\mathcal X^*$ について、
$$ C^\dagger(a)=C(a)=\varepsilon $$
である。
一方で、空文字列 $\varepsilon\in\mathcal X^*$ について、拡張の定義より、
$$ C^\dagger(\varepsilon)=\varepsilon $$
である。
したがって、
$$ C^\dagger(a)=C^\dagger(\varepsilon) $$
である。
しかし、
$$ a\ne\varepsilon $$
である。
よって、$C^\dagger$ は単射ではない。
したがって、この符号 $C$ は一意復号可能符号ではない。

任意の $u\in\Sigma^*$ に対して、
$$ u=u\varepsilon $$
であるから、$u$ は自分自身の接頭辞である。
一方、真の接頭辞では、後ろに連結する文字列 $w$ が非空であることを要求する。
したがって、$u$ は自分自身の真の接頭辞ではない。

二進アルファベットを
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とする。情報源アルファベットを
$$ \mathcal X=\{a,b,c\} $$
とし、二進符号
$$ C:\mathcal X\to\mathcal D^* $$
を
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt {10},\quad C(c)=\mathtt {11} $$
で定める。
このとき、例えば
$$ abc\in\mathcal X^* $$
に対して、
$$ \begin{align} C^\dagger(abc) &=C(a)C(b)C(c)\\ &=\mathtt 0\mathtt {10}\mathtt {11}\\ &=\mathtt {01011} \end{align} $$
である。また、
$$ cab\in\mathcal X^* $$
に対して、
$$ \begin{align} C^\dagger(cab) &=C(c)C(a)C(b)\\ &=\mathtt {11}\mathtt 0\mathtt {10}\\ &=\mathtt {11010} \end{align} $$
である。
この符号では、符号語
$$ \mathtt 0,\quad \mathtt {10},\quad \mathtt {11} $$
のどれも、他の符号語の真の接頭辞ではない。
したがって、左から順に読むと、
$$ \mathtt 0 $$
が出たときは $a$ と復号でき、
$$ \mathtt {10} $$
が出たときは $b$ と復号でき、
$$ \mathtt {11} $$
が出たときは $c$ と復号できる。
例えば、
$$ \mathtt {01011} $$
は
$$ \mathtt 0\,\mathtt {10}\,\mathtt {11} $$
と一意に区切られるので、
$$ abc $$
と一意に復号される。ゆえに、この符号 $C$ は一意復号可能符号である。

二進アルファベットを
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とする。文字列
$$ u=\mathtt {01},\quad v=\mathtt {0110} $$
を考える。このとき、
$$ v=\mathtt {01}\mathtt {10} $$
と書ける。すなわち、
$$ v=uw $$
を満たす文字列
$$ w=\mathtt {10} $$
が存在する。さらに、
$$ w\ne\varepsilon $$
である。
したがって、$u=\mathtt {01}$ は $v=\mathtt {0110}$ の真の接頭辞である。
$ $
また、このとき
$$ |u|=2,\quad |v|=4 $$
であるから、
$$ |u|<|v| $$
も成り立つ。

$\mathcal X=\{a,b,c,d\}$ とし、
$$ C(a)=\mathtt{00},\quad C(b)=\mathtt{01},\quad C(c)=\mathtt{10},\quad C(d)=\mathtt{11} $$
と定める。
$ $
このとき、すべての符号語の長さは $2$ である。したがって、この符号は二進固定長符号である。
また、異なる記号には異なる符号語が割り当てられているので、非特異符号である。
さらに、すべての符号語の長さが等しく、かつ互いに異なるため、ある符号語が別の符号語の接頭辞になることはない。
したがって、この符号は接頭辞符号である。

$\mathcal X=\{a,b,c\}$ とし、
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt{10},\quad C(c)=\mathtt{11} $$
と定める。このとき、
$$ \ell_C(a)=1,\quad \ell_C(b)=2,\quad \ell_C(c)=2 $$
であるから、この符号は可変長符号である。また、どの符号語も他の符号語の接頭辞ではない。
したがって、この符号は接頭辞符号である。ゆえに、この符号は一意復号可能である。

接頭辞符号は一意復号可能である。
接頭辞符号では、どの符号語も他の符号語の接頭辞にならない。
したがって、符号列を左から読んだとき、$1$ つの符号語が読み終わった時点で、その符号語の切れ目を一意に判断できる。
$ $
このため、接頭辞符号によって得られる符号列は、左から順に一意に復号できる。
ゆえに、
$$ \text{接頭辞符号} \Rightarrow \text{一意復号可能符号} $$
が成り立つ。
ただし、一意復号可能な符号が必ず接頭辞符号であるとは限らない。
すなわち、逆向きの
$$ \text{一意復号可能符号} \Rightarrow \text{接頭辞符号} $$
は一般には成り立たない。

1. 接頭辞符号である例を考える。
   $\mathcal X=\{a,b,c\}$ とし、二進符号 $C:\mathcal X\to\mathcal D^*$ を
   $$ C(a)=\mathtt 0,\quad C(b)=\mathtt{10},\quad C(c)=\mathtt{11} $$
   で定める。
   このとき、どの符号語も他の符号語の接頭辞ではない。したがって、$C$ は接頭辞符号である。
   よって、$C$ は一意復号可能符号である。
   例えば、符号列
   $$ \mathtt{01011} $$
   は、左から順に
   $$ \mathtt 0,\quad \mathtt{10},\quad \mathtt{11} $$
   とただ $1$ 通りに分割できる。したがって、元の記号列は
   $$ abc $$
   であると一意に分かる。
   $ $
2. 一意復号可能であるが、接頭辞符号ではない例を考える。
   $\mathcal X=\{a,b,c\}$ とし、二進符号 $C:\mathcal X\to\mathcal D^*$ を
   $$ C(a)=\mathtt 0,\quad C(b)=\mathtt{01},\quad C(c)=\mathtt{011} $$
   で定める。このとき、
   $$ C(b)=C(a)\mathtt 1 $$
   であるから、$C(a)=\mathtt 0$ は $C(b)=\mathtt{01}$ の真の接頭辞である。
   また、
   $$ C(c)=C(a)\mathtt{11} $$
   であるから、$C(a)=\mathtt 0$ は $C(c)=\mathtt{011}$ の真の接頭辞である。
   したがって、この符号は接頭辞符号ではない。
   $ $
   しかし、この符号は一意復号可能である。
   実際、この符号の各符号語は、すべて $\mathtt 0$ から始まり、その後に $\mathtt 1$ が $0$ 個、$1$ 個、または $2$ 個続く形をしている。
   すなわち、
   $$ C(a)=\mathtt 0,\quad C(b)=\mathtt 0\mathtt 1,\quad C(c)=\mathtt 0\mathtt 1\mathtt 1 $$
   である。
   したがって、符号列の中に現れる各 $\mathtt 0$ は、新しい符号語の始まりを表す。
   そのため、符号列全体を左から見て、$\mathtt 0$ が現れる位置で区切れば、符号語の切れ目が一意に定まる。
   例えば、
   $$ C^\dagger(abca) = C(a)C(b)C(c)C(a) = \mathtt 0\mathtt{01}\mathtt{011}\mathtt 0 = \mathtt{0010110} $$
   である。
   この符号列は、$\mathtt 0$ が現れる位置を符号語の始まりとして見ると、
   $$ \mathtt 0\ |\ \mathtt{01}\ |\ \mathtt{011}\ |\ \mathtt 0 $$
   とただ $1$ 通りに分割できる。したがって、元の記号列は
   $$ abca $$
   であると一意に分かる。
   同様に、任意の符号列についても、各 $\mathtt 0$ の位置が次の符号語の始まりを表すため、符号語の切れ目は一意に定まる。
   ゆえに、この符号は一意復号可能である。

-以上より、一意復号可能であっても接頭辞符号ではない符号が存在する。
したがって、
$$ \text{接頭辞符号} \Rightarrow \text{一意復号可能符号} $$
は成り立つが、その逆は一般には成り立たない。

ただし、本稿では、接頭辞符号を考えるとき、各 $x\in\mathcal X$ に対して
$$ C(x)\ne\varepsilon $$
を仮定する。
この仮定の動機は、空符号語を許すと、一意復号可能性は必ず壊れる。
実際、ある $x\in\mathcal X$ に対して
$$ C(x)=\varepsilon $$
であるとする。
このとき、符号の拡張の定義より、
$$ C^\dagger(x)=C(x)=\varepsilon $$
である。
一方、拡張の定義より
$$ C^\dagger(\varepsilon)=\varepsilon $$
である。
したがって、
$$ C^\dagger(x)=C^\dagger(\varepsilon) $$
である。
しかし、$x$ は長さ $1$ の文字列であり、$\varepsilon$ は長さ $0$ の文字列であるから、
$$ x\ne\varepsilon $$
である。
よって、$C^\dagger$ は単射ではない。
したがって、一意復号可能性を考える上では、空符号語を符号語として許さないのが自然である。

平均符号長 $L_X(f)$ は、確率変数 $X$ が出力する記号を符号 $f$ で符号化するとき、$1$ 回の出力あたり平均して何個の符号記号を使うかを表す。
特に、二進符号
$$ C:\mathcal X\to\mathcal D^* $$
の場合、$L_X(C)$ は $1$ 回の出力あたり平均して何ビット使うかを表す。

確率空間 $(\Omega,\mathcal F,\mathbb P)$ 上の確率変数 $X$ が、有限集合
$$ \mathcal X=\{a,b,c\} $$
に値をもつとする。
また、$X$ の確率質量関数が
$$ p_X(a)=\frac{1}{2},\quad p_X(b)=\frac{1}{4},\quad p_X(c)=\frac{1}{4} $$
で与えられているとする。
二進アルファベットを
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とし、二進符号
$$ C:\mathcal X\to\mathcal D^* $$
を
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt {10},\quad C(c)=\mathtt {11} $$
で定める。
このとき、各符号語の長さは
$$ \ell_C(a)=1,\quad \ell_C(b)=2,\quad \ell_C(c)=2 $$
である。
したがって、$C$ の $X$ に関する平均符号長は、
$$ \begin{align} L_X(C) &=\sum_{x\in\mathcal X}p_X(x)\ell_C(x)\\ &=p_X(a)\ell_C(a)+p_X(b)\ell_C(b)+p_X(c)\ell_C(c)\\ &=\frac{1}{2}\cdot 1+\frac{1}{4}\cdot 2+\frac{1}{4}\cdot 2\\ &=\frac{1}{2}+\frac{1}{2}+\frac{1}{2}\\ &=\frac{3}{2} \end{align} $$
である。
ゆえに、この符号では $1$ 回の出力あたり平均して
$$ \frac{3}{2} $$
個の二進符号記号を使う。
二進符号の場合、これは $1$ 回の出力あたり平均して
$$ \frac{3}{2}\text{ ビット} $$
を使うという意味である。

有限集合を
$$ \mathcal X=\{a,b,c\} $$
とし、二進符号
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt {10},\quad C(c)=\mathtt {11} $$
を考える。
このとき、
$$ \ell_C(a)=1,\quad \ell_C(b)=2,\quad \ell_C(c)=2 $$
である。
まず、確率変数 $X$ の分布が
$$ p_X(a)=\frac{1}{2},\quad p_X(b)=\frac{1}{4},\quad p_X(c)=\frac{1}{4} $$
であるとする。このとき、
$$ L_X(C) = \frac{1}{2}\cdot 1+\frac{1}{4}\cdot 2+\frac{1}{4}\cdot 2 = \frac{3}{2} $$
である。
一方、確率変数 $Y$ の分布が
$$ p_Y(a)=\frac{1}{3},\quad p_Y(b)=\frac{1}{3},\quad p_Y(c)=\frac{1}{3} $$
であるとする。このとき、
$$ \begin{align} L_Y(C) &= \frac{1}{3}\cdot 1+\frac{1}{3}\cdot 2+\frac{1}{3}\cdot 2\\ &= \frac{1}{3}+\frac{2}{3}+\frac{2}{3}\\ &= \frac{5}{3} \end{align} $$
である。
したがって、同じ符号 $C$ を使っていても、情報源記号の出やすさが変わると、平均符号長も変わる。

二進アルファベットを
$$ \mathcal D=\{\mathtt 0,\mathtt 1\} $$
とする。

1. $m=0$ の場合、長さ $0$ の二進符号語は空文字列だけである。
   $$ \mathcal D^0=\{\varepsilon\} $$
   したがって、
   $$ |\mathcal D^0|=1=2^0 $$
   である。
   $ $
2. $m=1$ の場合、長さ $1$ の二進符号語は
   $$ \mathcal D^1=\{\mathtt 0,\mathtt 1\} $$
   である。したがって、
   $$ |\mathcal D^1|=2=2^1 $$
   である。
   $ $
3. $m=2$ の場合、長さ $2$ の二進符号語は
   $$ \mathcal D^2= \{\mathtt{00},\mathtt{01},\mathtt{10},\mathtt{11}\} $$
   である。
   したがって、
   $$ |\mathcal D^2|=4=2^2 $$
   である。
   $ $
4. $m=3$ の場合、長さ $3$ の二進符号語は
   $$ \mathcal D^3= \{\mathtt{000},\mathtt{001},\mathtt{010},\mathtt{011}, \mathtt{100},\mathtt{101},\mathtt{110},\mathtt{111}\} $$
   である。
   したがって、
   $$ |\mathcal D^3|=8=2^3 $$
   である。

-一般に、長さ $m$ の二進符号語では、各位置に $\mathtt 0$ または $\mathtt 1$ の $2$ 通りの選択肢がある。
したがって、積の法則より、
$$ |\mathcal D^m| = \underbrace{2\cdot2\cdots2}_{m\text{ 個}} = 2^m $$
である。

固定長二進符号の範囲では、$N$ 個の記号を一意に識別するために必要なビット数の最小値は
$$ \lceil\log_2 N\rceil $$
である。ただし、これは各記号に同じ長さの符号語を割り当てる場合の最適性である。
(何度も言うようで悪いけど...)情報源の確率分布を考慮して可変長符号を用いると、平均符号長を固定長符号より短くできる場合がある。

英語の大文字 $26$ 文字だけを固定長二進符号で表す場合、
$$ \lceil\log_2 26\rceil=5 $$
である。したがって、少なくとも $5$ ビットが必要である。
$ $
標準 $\mathrm{ASCII}$ は $128$ 個のコードポイントを扱うため、
$$ \lceil\log_2 128\rceil=7 $$
より、$7$ ビットで表現できる。
$ $
一方、いわゆる拡張 $\mathrm{ASCII}$ では $256$ 個の値を扱うことが多く、
$$ \lceil\log_2 256\rceil=8 $$
より、$8$ ビット表現になる。

ただし、逆は一般には成り立たない。
例えば、$\mathcal X=\{a,b,c\}$ とし、
$$ C(a)=\mathtt 0,\quad C(b)=\mathtt{01},\quad C(c)=\mathtt 1 $$
と定める。
このとき、$C(a),C(b),C(c)$ は互いに異なるので、$C$ は非特異符号である。
しかし、
$$ C^\dagger(b)=\mathtt{01} $$
である一方、
$$ C^\dagger(ac)=C(a)C(c)=\mathtt 0\mathtt 1=\mathtt{01} $$
である。
したがって、
$$ C^\dagger(b)=C^\dagger(ac) $$
である。
一方で、$\mathcal X^*$ の文字列として、
$$ b\ne ac $$
である。ゆえに、$C^\dagger$ は単射ではない。
したがって、この符号は非特異符号であるが、一意復号可能符号ではない。

この証明では、
$$ s:=|u|+|v| $$
に関する強い数学的帰納法を用いている。
$ $
通常の数学的帰納法では、$s-1$ の場合から $s$ の場合を示すことが多い。
しかし、今回の証明では、先頭の $1$ 文字を取り除いた
$$ u',\quad v' $$
を考えるため、長さの和は
$$ |u'|+|v'|=|u|+|v|-2=s-2 $$
となる。
したがって、直前の $s-1$ の場合ではなく、$s$ より小さい場合全体について主張が使える形にしておくと自然である。
$ $
そのため、ここでは強い数学的帰納法を用いる。
すなわち、長さの和が $s$ より小さい任意の文字列の組 $(u,v)$ について、
$$ C^\dagger(u)=C^\dagger(v)\Rightarrow u=v $$
が成り立つと仮定し、長さの和が $s$ である組について同じ主張を示す。

$\Sigma$ をアルファベットとし、$a,b,z\in\Sigma^*$ とする。
$a$ と $b$ がともに $z$ の先頭部分であるとする。すなわち、$a$ と $b$ はともに $z$ の接頭辞であるとする。
さらに、
$$ |a|\leq |b| $$
とする。このとき、$a$ は $b$ の接頭辞である。
$ $
実際、
$$ |a|=m,\qquad |b|=n $$
とおく。仮定より、
$$ m\leq n $$
である。
$ $
$a$ と $b$ はともに $z$ の先頭部分であるから、$z$ の第 $1$ 文字から第 $m$ 文字までを並べた文字列が $a$ であり、
$z$ の第 $1$ 文字から第 $n$ 文字までを並べた文字列が $b$ である。
$ $
いま $m\leq n$ であるから、$b$ は、先頭の $m$ 文字からなる部分と、その後ろに続く残りの $n-m$ 文字からなる部分に分けられる。
$b$ の先頭の $m$ 文字は、$z$ の第 $1$ 文字から第 $m$ 文字までと一致する。これは $a$ である。
$ $
したがって、ある文字列 $r\in\Sigma^*$ が存在して、
$$ b=ar $$
と書ける。よって、接頭辞の定義より、$a$ は $b$ の接頭辞である。
$ $
特に、
$$ |a|<|b| $$
である場合には、$n-m>0$ であるから、$r$ は非空文字列である。
したがって、この場合には $a$ は $b$ の真の接頭辞である。

1. まず、$|D_k|=q^{L-l_k}$ を示す。
   $k\in\{1,\ldots,K\}$ を固定する。
   $c_k$ の長さは
   $$ |c_k|=l_k $$
   であり、$L$ は符号語長の最大値であるから、
   $$ l_k\leq L $$
   である。
   したがって、
   $$ L-l_k\in\mathbb N_0 $$
   である。
   ここで、写像
   $$ \Phi_k:\mathcal A^{L-l_k}\to D_k $$
   を
   $$ \Phi_k(z):=c_kz $$
   で定める。
   $ $
2. $\Phi_k$ が well-defined であることを示す。
   $z\in\mathcal A^{L-l_k}$ とする。このとき、
   $$ |z|=L-l_k $$
   である。
   文字列の連結と長さの性質(証明済み)より、
   $$ |\Phi_k(z)| = |c_kz| = |c_k|+|z| = l_k+(L-l_k) = L $$
   である。
   したがって、
   $$ c_kz\in\mathcal A^L $$
   である。
   また、定義より $c_k$ は $c_kz$ の接頭辞である。
   ゆえに、
   $$ \Phi_k(z)=c_kz\in D_k $$
   である。
   したがって、$\Phi_k$ は $\mathcal A^{L-l_k}$ から $D_k$ への写像である。
   $ $
3. 次に、$\Phi_k$ が単射であることを示す。
   $z,z'\in\mathcal A^{L-l_k}$ とし、
   $$ \Phi_k(z)=\Phi_k(z') $$
   と仮定する。
   このとき、
   $$ c_kz=c_kz' $$
   である。
   文字列の連結の左消去律(証明済み)より、
   $$ z=z' $$
   である。
   したがって、$\Phi_k$ は単射である。
   $ $
4. 次に、$\Phi_k$ が全射であることを示す。
   任意に
   $$ w\in D_k $$
   を取る。
   $D_k$ の定義より、$w\in\mathcal A^L$ であり、$c_k$ は $w$ の接頭辞である。
   したがって、接頭辞の定義より、ある $z\in\mathcal A^*$ が存在して、
   $$ w=c_kz $$
   と書ける。
   両辺の長さを取ると、
   $$ |w|=|c_kz| $$
   である。
   ここで、
   $$ |w|=L $$
   であり、文字列の連結と長さの性質(証明済み)より、
   $$ |c_kz|=|c_k|+|z|=l_k+|z| $$
   である。したがって、
   $$ L=l_k+|z| $$
   であるから、
   $$ |z|=L-l_k $$
   である。ゆえに、
   $$ z\in\mathcal A^{L-l_k} $$
   である。また、
   $$ \Phi_k(z)=c_kz=w $$
   である。
   したがって、任意の $w\in D_k$ に対して、ある $z\in\mathcal A^{L-l_k}$ が存在して $\Phi_k(z)=w$ となる。
   よって、$\Phi_k$ は全射である。
   $ $

-以上より、$\Phi_k$ は全単射である。
したがって、
$$ |D_k| = |\mathcal A^{L-l_k}| $$
である。
また、$\mathcal A$ は大きさ $q$ のアルファベットであるから、任意の $r\in\mathbb N_0$ に対して、
$$ |\mathcal A^r|=q^r $$
である。
これを $r=L-l_k$ に適用すると、
$$ |\mathcal A^{L-l_k}|=q^{L-l_k} $$
である。
したがって、
$$ |D_k|=q^{L-l_k} $$
である。

接頭辞符号に対するクラフトの不等式では、符号語を接頭辞にもつ長さ $L$ の語の集合を互いに排反にして数えた。
一方、一意復号可能符号は接頭辞符号とは限らないので、その方法をそのまま使うことはできない。
そこで、一意復号可能性を使うために、$n$ 個の符号語の連結を考える。
一意復号可能性により、異なる符号語列は異なる連結語を与える。
したがって、長さ $t$ の連結語として現れるものの個数は、長さ $t$ の全語の個数 $q^t$ 以下である。
この数え上げから、
$$ \left(\sum_{k=1}^{K}q^{-l_k}\right)^n\leq nL+1 $$
が得られ、$n\to\infty$ とすることで、
$$ \sum_{k=1}^{K}q^{-l_k}\leq1 $$
が従う。