4.4 Shannon 符号

定理 4.3.2 の等号条件は， $l o g 𝐷 1 𝑝 (𝑥)$ がすべての $𝑥$ で整数になることを要求していた．そうでない分布では，この値を整数に直さなければ符号語長にできない．いちばん素朴な直し方は切り上げである．本節はそれで作った符号を調べ，切り上げの代償が全体で高々 $1$ 文字であることを示す．

実数 $𝑡$ に対し， $𝑡$ 以上の最小の整数を $⌈ 𝑡 ⌉$ と書き，天井関数と呼ぶ．天井関数について $𝑡 \leq ⌈ 𝑡 ⌉ < 𝑡 + 1$ が成り立つことを既知とする．この性質を使うのは，本節と 4.6 節のほか，第2章 2.3 節，第6章 6.3 節，第8章 8.4 節，第12章 12.1 節，12.2 節と 12.4 節，第13章 13.3 節と 13.6 節である．

定義 4.4.1（Shannon 符号語長）. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とし， $𝑝$ を $X$ 上の分布ですべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする．

ℓ S (𝑥) : = ⌈ l o g 𝐷 1 𝑝 (𝑥) ⌉

を $𝑥$ の Shannon 符号語長 と呼ぶ．

$ℓ S$ は，第1章 1.6 節が先取りした「確率 $𝑝 (𝑥)$ の記号には $l o g 𝐷 1 𝑝 (𝑥)$ 文字」という割り当てを，そのまま整数に切り上げたものである．天井関数の性質から

l o g 𝐷 1 𝑝 (𝑥) \leq ℓ S (𝑥) < l o g 𝐷 1 𝑝 (𝑥) + 1

であり，記号ごとに見て高々 $1$ 文字の払いすぎで済んでいる（図 4.4.1）．確率の小さい記号の符号語が，確率の大きい記号の符号語より短くなることもない．切り上げる前の $l o g 𝐷 1 𝑝 (𝑥)$ が確率について減少しており，切り上げで大小が逆転することはないからである．

図 4.4.1. $𝐷 = 2$ のときの Shannon 符号語長 $ℓ S (𝑥)$ （階段）と，切り上げる前の $l o g 2 1 𝑝 (𝑥)$ （曲線）．横軸は記号の確率 $𝑝 (𝑥)$ で，印は例 4.4.5 の $𝑝 (𝑥) = 1 / 3$ である．

形式化: shannonLength (ソース)

符号として成立すること

命題 4.4.2. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とし， $𝑝$ を $X$ 上の分布ですべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする．このとき

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

である．

証明. $ℓ S (𝑥) \geq l o g 𝐷 1 𝑝 (𝑥)$ であり， $𝐷 > 1$ だから $𝑡 \mapsto 𝐷 - 𝑡$ は減少する．よって

𝐷 - ℓ S (𝑥) \leq 𝐷 - l o g 𝐷 (1 / 𝑝 (𝑥)) = 𝑝 (𝑥)

である． $𝑥$ について足し合わせると，右辺の総和は $1$ になる． $◼$

形式化: shannonLength_kraft_le_one (ソース)

系 4.4.3. $X$ を $2$ 個以上の文字からなる有限アルファベット， $𝐷 \geq 2$ を整数とし， $𝑝$ を $X$ 上の分布ですべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする．このときすべての $𝑥 \in X$ で $ℓ S (𝑥) \geq 1$ であり， $X$ 上の $𝐷$ 元語頭符号で，各 $𝑥$ の符号語長が $ℓ S (𝑥)$ に等しいものが存在する．

証明. $X$ は $2$ 文字以上あり分布はすべての点で正だから，どの $𝑥$ についても $𝑝 (𝑥) < 1$ である．よって $l o g 𝐷 1 𝑝 (𝑥) > 0$ となり，切り上げた $ℓ S (𝑥)$ は $1$ 以上の整数である．これと命題 4.4.2 の不等式を合わせると，定理 4.2.2 が求める語頭符号を与える． $◼$

形式化上の注記

系 4.4.3 に対応する単独の宣言はない．命題 4.4.2 の形式化と定理 4.2.2 の形式化を合わせた形になるが，その組み合わせを書いた宣言はない．また，Shannon 符号語長が $1$ 以上であることは定理 4.2.2 の形式化が仮定として求めるところで，それを与える宣言もないので，形式化では別に要る．

挟み撃ち

定理 4.4.4. $X$ を有限アルファベット， $𝐷 \geq 2$ を整数とし， $𝑋$ を $X$ 上に分布 $𝑝$ をもつ確率変数で，すべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする．このとき

𝐻 𝐷 (𝑋) \leq \sum 𝑥 \in X 𝑝 (𝑥) ℓ S (𝑥) < 𝐻 𝐷 (𝑋) + 1

である．

証明. 左側は命題 4.4.2 と定理 4.3.2 から従う． $𝑝 (𝑥) \leq 1$ より $l o g 𝐷 1 𝑝 (𝑥) \geq 0$ だから， $ℓ S (𝑥)$ は $0$ 以上の整数であり，命題 4.4.2 より $ℓ S$ は Kraft の不等式を満たすからである．

右側を示す．天井関数の性質より $ℓ S (𝑥) < l o g 𝐷 1 𝑝 (𝑥) + 1$ であり， $𝑝 (𝑥) > 0$ を掛けて足し合わせると

\sum 𝑥 𝑝 (𝑥) ℓ S (𝑥) < \sum 𝑥 𝑝 (𝑥) l o g 𝐷 1 𝑝 (𝑥) + \sum 𝑥 𝑝 (𝑥) = 𝐻 𝐷 (𝑋) + 1

となる（ $X$ は分布が載っているので空でなく，項が少なくとも一つあるから狭義の不等号が保たれる）． $◼$

形式化: 挟み撃ち shannonCode_expected_length_bounds，上からの評価 expectedLength_shannon_lt_entropyD_add_one (ソース)

定理 4.4.4 と定理 4.3.2 を並べると，最小の平均符号長が幅 $1$ 文字まで決まる．下からは $𝐻 𝐷 (𝑋)$ で押さえられ，上からは，アルファベットが $2$ 文字以上ですべての記号の確率が正なら Shannon 符号語長をもつ語頭符号がとれて（系 4.4.3），その平均符号長が $𝐻 𝐷 (𝑋) + 1$ 未満に収まる（定理 4.4.4）．幅は $1$ 文字で，しかもその $1$ は切り上げから来ている．記号ごとに $1$ 文字未満の払いすぎがあり，平均をとってもそれ以上にはならない，というだけのことである．

例 4.4.5（Shannon 符号は最適とは限らない）. $𝐷 = 2$ ， $X = {1, 2, 3}$ とし， $𝑋$ は $X$ 上の一様分布に従うとする．このとき $ℓ S (𝑥) = 2$ がすべての $𝑥$ で成り立ち，その平均符号長は $2$ である．一方，例 4.3.4 の長さの組 $ℓ (1) = 1$ ， $ℓ (2) = ℓ (3) = 2$ は Kraft の不等式を満たし，平均符号長は $5 / 3$ で，こちらのほうが小さい．

証明. $𝑝 (𝑥) = 1 / 3$ だから $l o g 2 3 = 1.5849 \dots$ を切り上げて $ℓ S (𝑥) = 2$ であり，平均符号長は $13 (2 + 2 + 2) = 2$ である．後半は例 4.3.4 で確かめた． $5 / 3 < 2$ である． $◼$

Shannon 符号は定理 4.4.4 の幅に収まるが，その幅の中でいちばん良いとは限らない．例 4.4.5 では，切り上げの丸め方を記号ごとに独立に決めたせいで場所が余っている． $ℓ S$ の Kraft 和は $3 \times 2 - 2 = 3 / 4$ で，4.2 節の木の言葉でいえば，深さ $2$ に $4$ つある場所のうち $1$ つが空いたまま残っている．例 4.3.4 の長さの組は，その空きを使って符号語を $1$ 本だけ長さ $1$ に縮め，和を $1$ にしている．すなわち例 4.4.5 は，記号ごとに独立に切り上げるという一つの規則が最小を与えないことを示している．どの長さの組が最小を与えるかという問いには，4.6 節が符号アルファベットが $2$ 文字の場合について答える．

ブロックにまとめる

系 4.4.6. $X$ を $2$ 個以上の文字からなる有限アルファベット， $𝐷 \geq 2$ を整数とし， $𝑋 0, 𝑋 1, \dots$ を $X$ 上の分布 $𝑝$ に従う i.i.d. 情報源で，すべての $𝑥 \in X$ で $𝑝 (𝑥) > 0$ を満たすものとする． $𝑋$ を分布 $𝑝$ に従う確率変数とする．このとき各 $𝑛 \geq 1$ について， $X 𝑛$ 上の $𝐷$ 元語頭符号 $𝑐 𝑛$ であって， $𝑋 𝑛 : = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ の分布について定めた平均符号長が

𝐻 𝐷 (𝑋) \leq 𝐿 (𝑐 𝑛) 𝑛 < 𝐻 𝐷 (𝑋) + 1 𝑛

を満たすものが存在する．

証明. $𝑋 𝑛$ の分布は $X 𝑛$ 上の分布で，独立性より各点の確率は $𝑝$ の値の積だから，すべての点で正である．また $| X 𝑛 | = | X | 𝑛 \geq 2$ である．よって系 4.4.3 を $X 𝑛$ とこの分布に当てると，Shannon 符号語長を符号語長にもつ $𝐷$ 元語頭符号 $𝑐 𝑛$ がとれる．定理 4.4.4 より

𝐻 𝐷 (𝑋 𝑛) \leq 𝐿 (𝑐 𝑛) < 𝐻 𝐷 (𝑋 𝑛) + 1

である．補題 2.3.3 より $𝐻 (𝑋 𝑛) = 𝑛 𝐻 (𝑋)$ であり，両辺を $l o g 𝐷$ で割ると $𝐻 𝐷 (𝑋 𝑛) = 𝑛 𝐻 𝐷 (𝑋)$ となる．これを代入して $𝑛$ で割れば主張を得る． $◼$

形式化上の注記

系 4.4.6 に対応する単独の宣言はない．平均符号長の評価は，定理 4.4.4 の形式化を $X 𝑛$ 上の分布に当て，補題 2.3.3 の形式化と組み合わせれば得られるが，その組み合わせを書いた宣言はない．符号の存在のほうは系 4.4.3 を経由するので，Shannon 符号語長が $1$ 以上であることが要り，それを与える宣言はない．対数の底のそろえ方（補題 2.3.3 のエントロピーは自然対数で測ってあり， $𝐻 𝐷$ は底を $𝐷$ にとる）と， $X 𝑛$ 上の分布を像測度として与える手当ても，形式化では別に要る．

系 4.4.6 は第2章の結論と本章の結論をつなぐ．第2章のブロック情報源符号は誤り確率を許す代わりにレートを $𝐻 (𝑋)$ に近づけたが，ここでは復号がつねに成功する符号だけを使って， $1$ 文字あたりの符号長を $𝐻 𝐷 (𝑋)$ に近づけている．代償として払っているのは同じもの，すなわちブロック長 $𝑛$ を大きくとる必要である．切り上げの $1$ 文字は $𝑛$ 文字で割り勘にされるので， $𝑛$ を大きくすれば消える．

逆に，本章の符号が第2章の符号より余分に払っているものもある．符号語の長さが送るものによって変わることである．第2章のブロック情報源符号は $X 𝑛$ を ${1, \dots, 𝑀 𝑛}$ に写すので，出力の長さはどのブロックでも同じだった（定義 2.3.1）．長さを固定したまま復号を確率 $1$ で成功させようとすると，確率が正の系列どうしは相異なる番号に写らなければならず，番号は台の元の個数だけ要る．系 4.4.6 のようにすべての記号の確率が正なら台は $X 𝑛$ 全体だから，レートは $l o g | X |$ に戻って，圧縮の余地が消える．第2章が誤りを許したのは，長さを固定したままレートを下げるためである．

情報理論入門（Lean による形式証明つき）・GitHub