4.1 符号と一意復号可能性

第2章は $𝑛$ 文字のブロックをひとまとめにして番号を振る符号を考え，1 文字あたりの費用がエントロピーまで下がることを示した（定理 2.3.6）．ただしその符号には二つの癖がある． $𝑛$ を大きくとらないと働かないことと，復号に失敗する確率が残ること（ $𝑛 \to \infty$ で 0 に向かうだけである）である．本章では別の作り方を扱う．1 文字ごとに符号語を割り当て，符号語の長さのほうを文字によって変える．復号はつねに成功し，代わりに問うのは平均の符号語長である．

第1章 1.1 節で，確率 $𝑝 (𝑥)$ の記号におよそ $- l o g 𝑝 (𝑥)$ 文字ぶんの符号語を割り当てるのが最適で，そのとき平均符号長がちょうど $𝐻 (𝑋)$ になると予告した．本章はその予告を定理にする．下から抑えるのが 4.3 節，上から抑えるのが 4.4 節である．

記号の約束をしておく．本章では $l o g$ の底を $2$ に固定する．符号に使える文字の個数を $𝐷$ と書き，底を $𝐷$ にとった対数が要る箇所では $l o g 𝐷$ と明示する．裸の $𝐷$ はつねにこの個数を指し，第1章の相対エントロピー $𝐷 (𝑝 ‖ 𝑞)$ とは別物である．というのも後者はつねに二つの分布を引数にとるからである．主役は $𝐷 = 2$ で例もすべてその場合をとるが，4.6 節を除いて議論は文字の個数が $2$ であることを使わないので，一般の $𝐷$ のまま述べる．平均符号長は $𝐿 (𝑐)$ のようにつねに符号を引数にとって書き，第2章 2.4 節が裸の $𝐿$ で表した定数とは別物である．

符号と平均符号長

定義 4.1.1（ $𝐷$ 元情報源符号と平均符号長）. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とする． $X$ 上の $𝐷$ 元情報源符号 とは，各 $𝑥 \in X$ に対して ${0, 1, \dots, 𝐷 - 1}$ の文字を並べた空でない有限列 $𝑐 (𝑥)$ を定める写像 $𝑐$ である． $𝑐 (𝑥)$ を $𝑥$ の 符号語，その長さを $ℓ (𝑥)$ と書く． $X$ 上に分布 $𝑝$ が与えられているとき， $𝑐$ の 平均符号長 を

𝐿 (𝑐) : = \sum 𝑥 \in X 𝑝 (𝑥) ℓ (𝑥)

で定める．

読み方は素直で， $𝐿 (𝑐)$ は「1 文字を送るのに平均して何文字払うか」である．符号語の長さを文字ごとに変えてよいところが第2章との違いで，確率の高い記号に短い符号語を割り当てれば平均は下がる．どこまで下げられるかが本章の問いである．なお符号語を空列にすることは許さない．長さ $0$ の符号語を認めると，それを何個つないでも列が変わらず，送った文字数が受け取る側に伝わらなくなる．

形式化: 平均符号長 expectedLength (ソース)

形式化上の注記. 形式化の expectedLength は，符号 $𝑐$ ではなく符号語長の組 $ℓ$ を引数にとる．平均符号長に効くのは符号語の中身ではなく長さの組だけで，4.2 節ではその見方が主役になる．

定義 4.1.2（拡張と一意復号可能性と語頭符号）. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とし， $𝑐$ を $X$ 上の $𝐷$ 元情報源符号とする． $X$ の文字を並べた空でない有限列全体の上の写像 $𝑐 *$ を，長さ $𝑛 \geq 1$ の列 $𝑥 1, \dots, 𝑥 𝑛$ に対して符号語を順につないだ列

𝑐 * (𝑥 1, \dots, 𝑥 𝑛) : = 𝑐 (𝑥 1) 𝑐 (𝑥 2) \dots 𝑐 (𝑥 𝑛)

を与えるものとして定め， $𝑐 *$ を $𝑐$ の拡張と呼ぶ．定義域は長さの異なる列をすべて含む． $𝑐$ が 一意復号可能 であるとは， $𝑐 *$ が単射なことをいう．また，列 $𝑠$ が列 $𝑡$ の語頭であるとは， $𝑡$ の先頭の， $𝑠$ の長さぶんの文字が $𝑠$ に一致することをいう（ $𝑠 = 𝑡$ の場合も含める）． $𝑐$ が 語頭符号 であるとは，相異なる $𝑥, 𝑦 \in X$ について $𝑐 (𝑥)$ が $𝑐 (𝑦)$ の語頭にならないことをいう．

一意復号可能性は，受け取る側の立場から見た条件である．送られてくるのは符号語をつないだ 1 本の列だけで，どこが区切りかは書かれていない．それでも元の文字の列が一つに定まる，というのが $𝑐 *$ の単射性である．語頭符号はそれより強く，読みながらその場で区切れることを要求する．先頭から 1 文字ずつ読んでいって，読んだところまでがある符号語に一致したら，そこが区切りだと決めてよい．というのもその符号語は他のどの符号語の語頭でもないので，あとから読み直しを迫られることがないからである．

形式化: 語頭符号 IsPrefixFree (ソース)

語頭符号は実際に使われている．文字を計算機の中で表す UTF-8 は， $1$ 文字を $1$ 個から $4$ 個のバイトの列に写す符号である．符号語の長さは先頭のバイトの上位のビットだけで決まるので，短い符号語が長い符号語の先頭に現れることはない．すなわち UTF-8 は語頭符号であり，先頭から読んでいけばその場で文字の切れ目が決まる．

命題 4.1.3. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とする． $X$ 上の $𝐷$ 元語頭符号は一意復号可能である．また，一意復号可能な $𝐷$ 元情報源符号の符号語は，相異なる文字に対して相異なる．

証明（列の長さについての帰納法）. $𝑐$ を語頭符号とし， $𝑐 * (𝑥 1, \dots, 𝑥 𝑛) = 𝑐 * (𝑦 1, \dots, 𝑦 𝑛')$ とする． $𝑛$ についての帰納法で $(𝑥 1, \dots, 𝑥 𝑛) = (𝑦 1, \dots, 𝑦 𝑛')$ を示す．

先頭の文字が一致することを見る．両辺は同じ列であり， $𝑐 (𝑥 1)$ はその先頭 $ℓ (𝑥 1)$ 文字， $𝑐 (𝑦 1)$ はその先頭 $ℓ (𝑦 1)$ 文字である．したがって長さの短いほうは長いほうの語頭になっている（長さが等しいときは両者が一致し，定義 4.1.2 はこれも語頭の場合に含めてある）． $𝑥 1 \neq 𝑦 1$ とすると，これは $𝑐$ が語頭符号であることに反する．よって $𝑥 1 = 𝑦 1$ である．

残りに帰納法の仮定を当てる．両辺の先頭から共通の $𝑐 (𝑥 1)$ を取り去ると，残った二つの列が等しい． $𝑛 = 1$ ならば左に残るのは空列であり， $𝑛' \geq 2$ とすると右に残る列は空でない符号語 $𝑐 (𝑦 2)$ を先頭に含むから，両者は等しくなりえない．よって $𝑛' = 1$ で，このとき主張は $𝑥 1 = 𝑦 1$ そのものである． $𝑛 \geq 2$ のときは同じ理由で $𝑛' \geq 2$ であり， $𝑐 * (𝑥 2, \dots, 𝑥 𝑛) = 𝑐 * (𝑦 2, \dots, 𝑦 𝑛')$ に帰納法の仮定を当てて $(𝑥 2, \dots, 𝑥 𝑛) = (𝑦 2, \dots, 𝑦 𝑛')$ を得る．

後半を示す． $1$ 文字だけの列に対しては $𝑐 * (𝑥) = 𝑐 (𝑥)$ だから， $𝑐 *$ が単射なら $𝑐$ も単射である． $◼$

形式化上の注記. 命題 4.1.3 に対応する，一般の $𝐷$ についての宣言はない．二元の場合について，符号語の集合がどの二つの元のあいだにも語頭の関係をもたず空列を含まなければ一意復号可能である，という形で PrefixFree.uniquelyDecodable (InformationTheory/Shannon/Kolmogorov/PrefixMachine.lean) が形式化されている．一意復号可能性そのものは，符号語の集合に対する述語 UniquelyDecodable として Mathlib にあるものをそのまま使う．この宣言が述べているのは符号語の集合についてのことで，命題 4.1.3 の前半に当たる．後半，すなわち符号語が文字ごとに相異なるという主張に対応する宣言はなく，形式化では写像 $𝑐$ の単射性は結論ではなく仮定の側に置かれている．

三つの例

例 4.1.4（二元語頭符号）. $X = {1, 2, 3, 4}$ ， $𝐷 = 2$ とし

𝑐 (1) = 0, 𝑐 (2) = 10, 𝑐 (3) = 110, 𝑐 (4) = 111

と定める． $𝑐$ は語頭符号である． $𝑋$ を $X$ 上に分布 $𝑝 (1) = 1 / 2$ ， $𝑝 (2) = 1 / 4$ ， $𝑝 (3) = 𝑝 (4) = 1 / 8$ をもつ確率変数とすると， $𝐿 (𝑐) = 7 / 4$ であり，これは $𝐻 (𝑋) = 7 / 4$ に等しい．

証明. 語頭符号であることを確かめる． $𝑐 (1)$ は $0$ で始まり他の三つは $1$ で始まるから， $𝑐 (1)$ はどれの語頭でもなく，どれも $𝑐 (1)$ の語頭でない． $𝑐 (2) = 10$ に対し $𝑐 (3)$ と $𝑐 (4)$ は $11$ で始まるので，やはり互いに語頭の関係がない． $𝑐 (3) = 110$ と $𝑐 (4) = 111$ は長さが同じで相異なるから，一方が他方の語頭になることはない．

値を計算する．平均符号長は定義 4.1.1 より

𝐿 (𝑐) = 12 \cdot 1 + 14 \cdot 2 + 18 \cdot 3 + 18 \cdot 3 = 74

である．エントロピーは定義 1.1.1 より

𝐻 (𝑋) = 12 l o g 2 + 14 l o g 4 + 18 l o g 8 + 18 l o g 8 = 12 + 12 + 38 + 38 = 74

である． $◼$

この符号では，各記号の符号語長がちょうど $- l o g 𝑝 (𝑥)$ になっている（ $1, 2, 3, 3$ に対して確率が $2 - 1, 2 - 2, 2 - 3, 2 - 3$ ）．第1章 1.1 節の予告どおりの割り当てが，この分布ではぴったり整数で実現できたということである．二つの値が一致したのは偶然ではなく，4.3 節でこれが等号成立の条件そのものだと分かる．

次の例では列を逆順に並べる操作を使う．列 $𝑠$ を逆順に並べたものを $˜ 𝑠$ と書き，連結の反転が反転どうしを逆順に連結したものに等しいこと，すなわち二つの列 $𝑠, 𝑡$ について $̃ 𝑠 𝑡 = ˜ 𝑡 ˜ 𝑠$ が成り立つことを既知とする．

例 4.1.5（一意復号可能だが語頭符号でない）. $X = {1, 2, 3}$ ， $𝐷 = 2$ とし， $𝑐 (1) = 0$ ， $𝑐 (2) = 01$ ， $𝑐 (3) = 011$ と定める． $𝑐$ は語頭符号ではないが一意復号可能である．

証明. $𝑐 (1) = 0$ は $𝑐 (2) = 01$ の語頭だから， $𝑐$ は語頭符号ではない．

一意復号可能性を示す．符号 $˜ 𝑐$ を $˜ 𝑐 (𝑥) : = ̃ 𝑐 (𝑥)$ で定めると $˜ 𝑐 (1) = 0$ ， $˜ 𝑐 (2) = 10$ ， $˜ 𝑐 (3) = 110$ であり，これは例 4.1.4 の符号の一部だから語頭符号で，命題 4.1.3 より一意復号可能である．いま $𝑐 * (𝑥 1, \dots, 𝑥 𝑛) = 𝑐 * (𝑦 1, \dots, 𝑦 𝑛')$ とすると，連結の反転が反転どうしを逆順に連結したものに等しいことを繰り返し使って両辺を逆順にすれば

˜ 𝑐 * (𝑥 𝑛, \dots, 𝑥 1) = ˜ 𝑐 * (𝑦 𝑛', \dots, 𝑦 1)

を得る． $˜ 𝑐$ の一意復号可能性より $(𝑥 𝑛, \dots, 𝑥 1) = (𝑦 𝑛', \dots, 𝑦 1)$ であり，もう一度逆順にすれば $(𝑥 1, \dots, 𝑥 𝑛) = (𝑦 1, \dots, 𝑦 𝑛')$ である． $◼$

この符号では， $0$ を受け取った時点で文字 $1$ が終わったとは決められない．次が $1$ ならその $0$ は $𝑐 (2)$ か $𝑐 (3)$ の先頭だったことになるので，判断は先を読むまで保留になる．区切りが一意に決まることと，読みながらその場で決められることは別である．

例 4.1.6（符号語がすべて相異なっても一意復号可能とは限らない）. $X = {1, 2, 3}$ ， $𝐷 = 2$ とし， $𝑐 (1) = 0$ ， $𝑐 (2) = 01$ ， $𝑐 (3) = 10$ と定める．三つの符号語は相異なるが， $𝑐$ は一意復号可能でない．

証明. $𝑐 * (1, 3) = 0 \cdot 10 = 010$ であり， $𝑐 * (2, 1) = 01 \cdot 0 = 010$ である．列 $(1, 3)$ と $(2, 1)$ は相異なるのに同じ列に写るから， $𝑐 *$ は単射でない． $◼$

三つの例が三つの階層を示している．命題 4.1.3 によれば，語頭符号は一意復号可能であり，一意復号可能なら符号語は相異なる．逆はどちらも成り立たず，例 4.1.5 と例 4.1.6 がそれぞれの反例である．語頭符号はこの中でいちばん狭いクラスだが，読みながら区切れるという実用上の利点をもつ．そこで自然に浮かぶのは，その狭さの代償として平均符号長で損をしていないか，という問いである．4.5 節で，一意復号可能な符号まで許しても平均符号長の下界は変わらないことを見る．

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