4.2 Kraft の不等式

符号語を短くする自由には限りがある． $𝐷 = 2$ で $X$ が $3$ 文字のとき，語頭符号では全部の符号語を長さ $1$ にはできない．長さ $1$ の列は $0$ と $1$ の二つしかなく，同じ列を二つの文字に与えれば一方が他方の語頭になってしまうからである．長さ $2$ の符号語，たとえば $01$ を一つ使えば， $01$ で始まる列はどれも他の符号語には使えなくなる．これは $0$ で始まる列の半分，全体の $4$ 分の $1$ にあたる．符号語が長いほど，使えなくなる割合は小さい．この割合を全部の符号語について足し合わせて一つの不等式にしたのが本節の主題である．

語頭符号が満たす制約

定理 4.2.1（Kraft の不等式）. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とする． $𝑐$ を $X$ 上の $𝐷$ 元語頭符号， $ℓ (𝑥)$ をその符号語長とすると

\sum 𝑥 \in X 𝐷 - ℓ (𝑥) \leq 1

が成り立つ．

証明. $X$ が空なら左辺は $0$ で主張は成り立つから，空でないとしてよい． $ℓ m a x : = m a x 𝑥 \in X ℓ (𝑥)$ とおく．

長さ $ℓ m a x$ の列を数える． ${0, 1, \dots, 𝐷 - 1}$ の文字を $ℓ m a x$ 個並べた列は全部で $𝐷 ℓ m a x$ 本ある．各 $𝑥 \in X$ について， $𝑐 (𝑥)$ を語頭にもつ長さ $ℓ m a x$ の列の集合を $𝑆 (𝑥)$ と書く． $𝑐 (𝑥)$ の後ろに残りの $ℓ m a x - ℓ (𝑥)$ 文字を自由に並べればよいので

| 𝑆 (𝑥) | = 𝐷 ℓ m a x - ℓ (𝑥)

である．

これらが互いに交わらないことを見る． $𝑥 \neq 𝑦$ で $𝑆 (𝑥) \cap 𝑆 (𝑦)$ に属する列があるとすると， $𝑐 (𝑥)$ と $𝑐 (𝑦)$ はどちらもその列の語頭だから，長さの短いほうが長いほうの語頭になる．これは $𝑐$ が語頭符号であることに反する．

交わらない集合の合併は全体に含まれるから

\sum 𝑥 \in X 𝐷 ℓ m a x - ℓ (𝑥) = ∣ ⋃ 𝑥 \in X 𝑆 (𝑥) ∣ \leq 𝐷 ℓ m a x

であり，両辺を $𝐷 ℓ m a x$ で割れば主張を得る． $◼$

形式化上の注記. 定理 4.2.1 に対応する，一般の $𝐷$ についての宣言はない．二元の場合について，空列を含まない語頭符号の符号語の集合の有限部分集合に対する同じ不等式が PrefixFree.kraft (InformationTheory/Shannon/Kolmogorov/PrefixMachine.lean) として形式化されている（符号語の集合そのものが無限であってよいので，本文より広い．集合全体にわたる和の形 PrefixFree.tsum_inv_two_pow_length_le_one も同じところにある）．ただしその証明は，語頭性から直接数え上げる本文とは違って，語頭符号よりも広い一意復号可能な符号に対する不等式を経由している．一般の $𝐷$ についてはその広いほうの形だけが形式化されており，4.5 節で扱う．

列の全体を， $1$ 文字伸ばすごとに枝分かれする木と見ておく．符号語は節点にあたり，語頭の関係は先祖と子孫の関係にあたる．以下の「深さ」はこの木の言葉で，列の長さのことである．証明が数えているのは「深さ $ℓ m a x$ でどれだけの場所が塞がるか」である．符号語 $𝑐 (𝑥)$ を一つ決めると，それを語頭にもつ長さ $ℓ m a x$ の列がまとめて使えなくなり，その本数は符号語が短いほど多い．語頭符号であるという条件は，塞がる範囲どうしが重ならないことを意味する．重ならないものの総量が全体を超えないというだけの勘定が，Kraft の不等式である． $𝐷 - ℓ (𝑥)$ という項は，符号語 $𝑥$ が全体の何割を塞ぐかを表している．

逆向きの構成

定理 4.2.2. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とし， $ℓ : X \to {1, 2, 3, \dots}$ が

\sum 𝑥 \in X 𝐷 - ℓ (𝑥) \leq 1

を満たすとする．このとき $X$ 上の $𝐷$ 元語頭符号 $𝑐$ で，すべての $𝑥 \in X$ について $𝑐 (𝑥)$ の長さが $ℓ (𝑥)$ に等しいものが存在する．

証明. 以下は，符号語を長さの短い順に前から詰めていく手続きを，そのまま式で書き下したものである． $X$ が空なら空の符号が主張を満たすから，空でないとしてよい． $ℓ m a x : = m a x 𝑥 \in X ℓ (𝑥)$ とおく．長さ $ℓ m a x$ の列を，先頭を最上位の桁とする $𝐷$ 進表示と読んで， $0$ 以上 $𝐷 ℓ m a x$ 未満の整数と同一視する． $𝐷$ 進表示については三つのことを既知とする．第一に，長さ $ℓ m a x$ の列とこの範囲の整数との対応が $1$ 対 $1$ であること．第二に， $0 \leq 𝑘 \leq ℓ m a x$ のとき，整数が $𝐷 𝑘$ の倍数であることと，対応する列の末尾 $𝑘$ 文字がすべて $0$ であることが同値であること．第三に，長さ $𝑗$ の列を語頭にもつ長さ $ℓ m a x$ の列に対応する整数が， $𝐷 ℓ m a x - 𝑗$ 個の連続した整数の並びになることである．

順序を一つ選ぶ． $X$ に， $ℓ$ の値が小さい文字ほど先に来るような全順序 $≺$ を入れる（値が等しい文字どうしの順序はどう決めてもよい）．各 $𝑥 \in X$ に対して

𝑠 (𝑥) : = \sum 𝑦 ≺ 𝑥 𝐷 ℓ m a x - ℓ (𝑦)

とおく．仮定の不等式の両辺を $𝐷 ℓ m a x$ 倍すると $\sum 𝑦 𝐷 ℓ m a x - ℓ (𝑦) \leq 𝐷 ℓ m a x$ である． $𝑠 (𝑥)$ の和の範囲に $𝑥$ 自身を足したものは $X$ に含まれるから，どの $𝑥$ についても

𝑠 (𝑥) + 𝐷 ℓ m a x - ℓ (𝑥) \leq 𝐷 ℓ m a x

が従う．とくに $𝑠 (𝑥) < 𝐷 ℓ m a x$ であり， $𝐷$ 進表示の第一の性質より $𝑠 (𝑥)$ は長さ $ℓ m a x$ の列に対応する．

符号語を定める． $𝑦 ≺ 𝑥$ ならば $ℓ (𝑦) \leq ℓ (𝑥)$ なので， $𝑠 (𝑥)$ の各項 $𝐷 ℓ m a x - ℓ (𝑦)$ は $𝐷 ℓ m a x - ℓ (𝑥)$ の倍数である．したがって $𝑠 (𝑥)$ は $𝐷 ℓ m a x - ℓ (𝑥)$ で割り切れ， $𝐷$ 進表示の第二の性質より， $𝑠 (𝑥)$ に対応する長さ $ℓ m a x$ の列は末尾 $ℓ m a x - ℓ (𝑥)$ 文字がすべて $0$ である．そこで $𝑐 (𝑥)$ を，その列の先頭 $ℓ (𝑥)$ 文字と定める．長さは $ℓ (𝑥)$ である． $𝐷$ 進表示の第三の性質より， $𝑐 (𝑥)$ を語頭にもつ長さ $ℓ m a x$ の列に対応する整数はちょうど

𝑠 (𝑥), 𝑠 (𝑥) + 1, \dots, 𝑠 (𝑥) + 𝐷 ℓ m a x - ℓ (𝑥) - 1

の並びになる．

語頭符号であることを示す． $𝑥 \neq 𝑦$ で $𝑐 (𝑥)$ が $𝑐 (𝑦)$ の語頭だとする．このとき $ℓ (𝑥) \leq ℓ (𝑦)$ であり， $𝑐 (𝑦)$ を語頭にもつ列は $𝑐 (𝑥)$ も語頭にもつ．すなわち $𝑐 (𝑦)$ を語頭にもつ長さ $ℓ m a x$ の列の並びは， $𝑐 (𝑥)$ を語頭にもつ列の並びの中にすっぽり入る．二つの並びの左端と幅を比べると $𝑠 (𝑥) \leq 𝑠 (𝑦) < 𝑠 (𝑥) + 𝐷 ℓ m a x - ℓ (𝑥)$ が従う．一方， $𝑥 ≺ 𝑦$ ならば $𝑠 (𝑦)$ の和の範囲は $𝑠 (𝑥)$ の和の範囲に $𝑥$ を足したものを含むので $𝑠 (𝑦) \geq 𝑠 (𝑥) + 𝐷 ℓ m a x - ℓ (𝑥)$ となり，右側の不等号に反する． $𝑦 ≺ 𝑥$ ならば $≺$ の決め方から $ℓ (𝑦) \leq ℓ (𝑥)$ で， $ℓ (𝑥) \leq ℓ (𝑦)$ と合わせて $ℓ (𝑥) = ℓ (𝑦)$ であり，同じ理由で $𝑠 (𝑥) \geq 𝑠 (𝑦) + 𝐷 ℓ m a x - ℓ (𝑦) > 𝑠 (𝑦)$ となって，左側の不等号に反する．どちらの場合も矛盾するから， $𝑐$ は語頭符号である． $◼$

形式化: exists_prefix_code_of_kraft (ソース)

証明は「深さ $ℓ m a x$ の $𝐷 ℓ m a x$ 個の場所を，長さの短い順に前から詰めていく」という手続きそのものである． $𝑠 (𝑥)$ が詰め始めの位置で， $𝑥$ が占める幅が $𝐷 ℓ m a x - ℓ (𝑥)$ である．短いものから詰めるので，占める幅は単調に狭くなり，境界がつねに幅の倍数のところに来る．そのおかげで区間が入れ子にならず，語頭の関係が生じない．Kraft の不等式は，最後まで詰めきっても場所が足りるという条件として使われている．

例 4.2.3（実現できる長さの組とできない長さの組）. $𝐷 = 2$ とし， $4$ 文字からなるアルファベットを考える．四つの符号語長が $1, 2, 3, 3$ である二元語頭符号は存在する．四つの符号語長が $1, 2, 2, 3$ である二元語頭符号は存在しない．

証明. 前半は $2 - 1 + 2 - 2 + 2 - 3 + 2 - 3 = 1$ だから定理 4.2.2 で従う．その構成をたどると例 4.1.4 の符号がそのまま出てくる． $ℓ m a x = 3$ で，長さの小さい順に並べた四つの文字の詰め始めの位置は $0$ ， $2 3 - 1 = 4$ ， $4 + 2 3 - 2 = 6$ ， $6 + 2 3 - 3 = 7$ である．これらを長さ $3$ の二進表示 $000$ ， $100$ ， $110$ ， $111$ と読み，先頭からそれぞれ $1, 2, 3, 3$ 文字を取れば $0$ ， $10$ ， $110$ ， $111$ となる．後半は $2 - 1 + 2 - 2 + 2 - 2 + 2 - 3 = 9 / 8 > 1$ だから，定理 4.2.1 の対偶による． $◼$

定義 4.2.4（Kraft の不等式を満たす長さの組）. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とする． $X$ 上で定義され $0$ 以上の整数値をとる関数 $ℓ$ を， $X$ 上の 長さの組 と呼ぶ．長さの組 $ℓ$ が

\sum 𝑥 \in X 𝐷 - ℓ (𝑥) \leq 1

を満たすとき， $ℓ$ は Kraft の不等式を満たす と言う．

形式化: $\sum 𝑥 𝐷 - ℓ (𝑥)$ にあたる kraftSum (ソース)

長さの組の値に $0$ を許してあるのは，確率 $1$ の記号に切り上げが長さ $0$ を与える場合（4.4 節）にも，次節の下界をそのまま当てるためである．符号から来る長さの組がこの値をとることはない．定義 4.1.1 より符号語は空でないから $ℓ (𝑥) \geq 1$ である．

系 4.2.5. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とし， $ℓ$ を $X$ 上の長さの組（定義 4.2.4）とする． $ℓ$ がある $𝐷$ 元語頭符号の符号語長の組であることと， $ℓ$ が Kraft の不等式を満たしかつすべての $𝑥 \in X$ で $ℓ (𝑥) \geq 1$ であることは同値である．

証明. $ℓ$ がある $𝐷$ 元語頭符号 $𝑐$ の符号語長の組ならば，定義 4.1.1 より符号語は空でないので $ℓ (𝑥) \geq 1$ であり，定理 4.2.1 より $ℓ$ は Kraft の不等式を満たす．逆に $ℓ$ が Kraft の不等式を満たしすべての $𝑥$ で $ℓ (𝑥) \geq 1$ ならば，定理 4.2.2 より各 $𝑥$ の符号語長が $ℓ (𝑥)$ に等しい $𝐷$ 元語頭符号が存在する． $◼$

系 4.2.5 が言っているのは，符号語の中身は長さの組さえ許されていれば必ず作れる，ということである．だから符号を設計する問題は，長さの組を選ぶ問題に置き換えてよい．次節はこの形の $ℓ$ すべてにわたって平均符号長を下から抑える．

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．