8.4 達成可能性

系 8.3.6 は，どんな符号の族を設計しても達成レートが $12 l o g (1 + 𝑃 / 𝑁)$ を超えられないことを示した．残るのは逆向きで，それ未満のレートなら実際に符号が作れるか，という問いである．第6章 6.3 節で離散の通信路について答えたのと同じ問いで，答えも同じく肯定である．

本節はまず，なぜ $12 l o g (1 + 𝑃 / 𝑁)$ という数がここに現れるのかを，符号語を $ℝ 𝑛$ の点として置く幾何の言葉で見る．そのうえで達成可能性を借用として置き，逆定理と突き合わせて本章の主定理に至る．第6章が達成可能性を先に置いて逆定理を後にしたのに対し，本章が順序を入れ替えたのは，借りるほうを後ろに回して，証明を載せる側だけで章が積み上がるようにするためである．

球で詰める

長さ $𝑛$ ，電力 $𝑃$ のブロック通信路符号（定義 8.3.1）をとり，そのメッセージ数を $𝑀$ とする．符号語 $𝑐 (𝑚)$ は $ℝ 𝑛$ の点である．電力制約は $\sum 𝑖 (𝑐 (𝑚) 𝑖) 2 \leq 𝑛 𝑃$ ，すなわち原点からの距離が $\sqrt 𝑛 𝑃$ 以下ということで，符号語は半径 $\sqrt 𝑛 𝑃$ の球の中に置かれる．雑音と出力の側は， $2$ 乗和の平均で測る．8.1 節の雑音 $𝑍 = 𝑌 - 𝑋$ を各時刻に並べた $𝑍 𝑛$ は，7.2 節で借りたガウス分布の基本性質より成分ごとに平均 $0$ ，分散 $𝑁$ をもつので， $𝔼 [\sum 𝑖 𝑍 2 𝑖] = 𝑛 𝑁$ である．出力のほうは， $𝑀$ 個のメッセージから一様に選んで送ったときの出力 $𝑌 𝑛$ で測る．これは補題 8.3.3 のガウス分布の混合を $𝑎 𝑚 : = 𝑐 (𝑚)$ ， $𝑘 : = 𝑛$ ととったものを密度にもつから，同じ補題より $𝔼 [𝑌 2 𝑖] = 𝑁 + 1 𝑀 \sum 𝑚 (𝑐 (𝑚) 𝑖) 2$ であり， $𝑖$ について足して電力制約 $\sum 𝑖 (𝑐 (𝑚) 𝑖) 2 \leq 𝑛 𝑃$ を当てると $𝔼 [\sum 𝑖 𝑌 2 𝑖] \leq 𝑛 (𝑃 + 𝑁)$ である．こちらは等号ではなく不等号で，符号語が電力を使い切らなければ左辺は小さくなる．

ここから先は見当である． $2$ 乗和は $𝑛$ 個の独立な項の和なので， $𝑛$ が大きければ平均のまわりに集まるだろう，と読む．この種の集まり方を呼ぶ名前が大数の法則で，第2章 2.1 節が借りたのもその一つの形である．そう読めば，受け取る点は送った符号語から距離 $\sqrt 𝑛 𝑁$ ほどのところに落ち，どの符号語を送った場合も半径 $\sqrt 𝑛 (𝑃 + 𝑁)$ の球の中に収まる．

そこで，半径 $\sqrt 𝑛 (𝑃 + 𝑁)$ の球の中に，半径 $\sqrt 𝑛 𝑁$ の球をいくつ重なりなく詰められるかを勘定する．詰められる個数だけメッセージを用意すれば，受け取った点がどの雑音球に入ったかで送った符号語が言い当てられる，という見当である．個数の見当は体積の比で与えられる．

命題 8.4.1（球の体積の比）. $𝑛 \geq 1$ とし， $𝑟 > 0$ に対し

𝐵 𝑛 (𝑟) : = {𝑦 \in ℝ 𝑛 : \sum 𝑛 - 1 𝑖 = 0 𝑦 2 𝑖 \leq 𝑟 2}

とおき，定数関数 $1$ の $𝐵 𝑛 (𝑟)$ の上での積分を $v o l 𝐵 𝑛 (𝑟)$ と書く．このとき $0 < v o l 𝐵 𝑛 (𝑟) < \infty$ であり， $𝑟' > 0$ について

v o l 𝐵 𝑛 (𝑟) v o l 𝐵 𝑛 (𝑟') = (𝑟 𝑟') 𝑛

である．とくに $𝑁 > 0$ と $𝑃 \geq 0$ について $𝑟 : = \sqrt 𝑛 (𝑃 + 𝑁)$ ， $𝑟' : = \sqrt 𝑛 𝑁$ ととると，この比は $2 𝑛 2 l o g (1 + 𝑃 / 𝑁)$ に等しい．

証明. $v o l 𝐵 𝑛 (1)$ が有限で正であることを見る． $| 𝑦 𝑖 | \leq 1 / \sqrt 𝑛$ がすべての $𝑖$ で成り立てば $\sum 𝑖 𝑦 2 𝑖 \leq 1$ だから， $𝐵 𝑛 (1)$ は一辺 $2 / \sqrt 𝑛$ の立方体を含む．また $𝑦 \in 𝐵 𝑛 (1)$ なら各 $| 𝑦 𝑖 | \leq 1$ だから， $𝐵 𝑛 (1)$ は一辺 $2$ の立方体に含まれる．一辺 $𝑎$ の立方体の上での定数関数 $1$ の積分は，8.1 節で借りた累次積分を成分ごとに繰り返せば $𝑎 𝑛$ である．したがって 7.1 節で既知とした非負な関数についての積分の単調性より $(2 / \sqrt 𝑛) 𝑛 \leq v o l 𝐵 𝑛 (1) \leq 2 𝑛$ であり，左辺は正，右辺は有限である．

半径による変化を見る．7.3 節で借りた置換積分を，各成分の拡大率を $𝑟$ ，平行移動を $0$ にとった置き換え $𝑦 𝑖 = 𝑥 𝑖 / 𝑟$ で使う． $𝐵 𝑛 (𝑟)$ の各点をこの置き換えで送った集合は $𝐵 𝑛 (1)$ であり， $𝑑 𝑥 = 𝑟 𝑛 𝑑 𝑦$ だから $v o l 𝐵 𝑛 (𝑟) = 𝑟 𝑛 v o l 𝐵 𝑛 (1)$ である．よって $𝑟$ と $𝑟'$ についての比は $(𝑟 / 𝑟') 𝑛$ である．

最後の主張を確かめる． $𝑟 / 𝑟' = \sqrt (𝑃 + 𝑁) / 𝑁 = (1 + 𝑃 / 𝑁) 1 / 2$ だから比は $(1 + 𝑃 / 𝑁) 𝑛 / 2$ であり，底を $2$ にとった対数について $2 l o g 𝑢 = 𝑢$ （ $𝑢 > 0$ ）だから，これは $2 𝑛 2 l o g (1 + 𝑃 / 𝑁)$ に等しい． $◼$

命題 8.4.1 の指数に現れた $12 l o g (1 + 𝑃 / 𝑁)$ が，8.2 節で計算した容量にほかならない．雑音球の詰め込みという幾何の勘定と，微分エントロピーの最大化という 8.2 節の勘定が，同じ数に着いている．偶然ではない．どちらも「出力の散らばりの広さを雑音の散らばりの広さで割る」という同じ量を測っていて，前者は体積で，後者は $2 ℎ$ という実効的な幅（7.1 節）で測っているだけである．

命題 8.4.1 は体積の比についての主張であって，メッセージがその個数だけ区別できることを示してはいない．雑音の $2$ 乗和が正確に $𝑛 𝑁$ になるわけではないし，球を重なりなく詰める配置が実際に作れるかどうかも別の問題である．次に借りる主張は，この見当が正しい答えを与えていることを言うものだが，その根拠はこの勘定とは別の道をたどる．

達成可能性

記号を一つ引いておく．実数 $𝑡$ に対する天井関数 $⌈ 𝑡 ⌉$ ，すなわち $𝑡$ 以上の最小の整数と，その性質 $𝑡 \leq ⌈ 𝑡 ⌉ < 𝑡 + 1$ は，第4章 4.4 節で既知としたとおりに本節でも使う．

道具を一つ借りる．ガウス通信路の達成可能性，すなわち「レートが $12 l o g (1 + 𝑃 / 𝑁)$ を下回っているかぎり，誤り確率をいくらでも小さくできる符号がある」という主張である．使う形を書いておく．

$𝑁 > 0$ ， $𝑃 > 0$ とし， $0 < 𝑅 < 12 l o g (1 + 𝑃 / 𝑁)$ と $𝜁 > 0$ をとる．このとき，十分大きいすべての $𝑛$ について，メッセージ数 $𝑀 \geq ⌈ 2 𝑛 𝑅 ⌉$ の長さ $𝑛$ ，電力 $𝑃$ のブロック通信路符号（定義 8.3.1）で，最大誤り確率が $𝑃 𝑒, m a x < 𝜁$ を満たすものが存在する．

当てる対象は定義 8.3.1 のブロック通信路符号だけで，依存するのは系 8.4.2 の証明だけである．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．符号語は設計するのではなく，くじで引く． $1$ 本の符号語の各成分を独立に $N (0, 𝑃)$ から引き，それを $𝑀$ 本ぶん独立に繰り返す．引く分布をガウス分布にとるのは 8.2 節と同じ理由で，出力の微分エントロピーを最大にする入力がそれだからである．復号は，受け取った $𝑦 𝑛$ に対して， $𝑦 𝑛$ と $𝑐 (𝑚)$ の差の $2$ 乗和がおよそ $𝑛 𝑁$ で，かつ $𝑦 𝑛$ の $2$ 乗和がおよそ $𝑛 (𝑃 + 𝑁)$ である，という条件を満たす符号語 $𝑐 (𝑚)$ を探す．そういう符号語がちょうど $1$ 本あればそれを答え， $0$ 本のときと $2$ 本以上のときは誤りとする．この条件が，第6章 6.2 節の結合典型集合にあたるものである．前半は受け取った点が $𝑐 (𝑚)$ を中心とする半径 $\sqrt 𝑛 𝑁$ ほどの球に入っていること，後半は原点を中心とする半径 $\sqrt 𝑛 (𝑃 + 𝑁)$ ほどの球に入っていることを言っているので，命題 8.4.1 が体積をくらべた二つの球が，そのまま復号の規則になっている．送った符号語がこの条件を満たさないことは， $𝑛$ を大きくすれば起こりにくい．いっぽう無関係な符号語がたまたまこの条件を満たす確率は，第6章 6.2 節の勘定を系列の個数から体積に置き換えて測ることになり，命題 8.4.1 の体積の比の逆数，すなわち $2 - 𝑛 2 l o g (1 + 𝑃 / 𝑁)$ ほどになる．これを $𝑀 - 1$ 本ぶん足すと $2 𝑛 𝑅$ 倍されるので， $𝑅$ が $12 l o g (1 + 𝑃 / 𝑁)$ を下回っているかぎり和は $0$ に向かう．レートの限界がここにそのまま現れる．

本書はこの主張を証明しない．第6章 6.3 節のランダム符号化をそのまま連続版にすればよいのだが，そのために二つの部品を連続版に取り替える必要がある．一つは結合典型集合の勘定で，第6章では系列の個数を数えた（定理 6.2.5）ところを， $ℝ 𝑛$ の部分集合の体積で測ることになる．もう一つは電力制約の始末である．入力分布から独立に引いた符号語が $\sum 𝑖 (𝑐 (𝑚) 𝑖) 2 \leq 𝑛 𝑃$ を満たすとはかぎらないので，破っている符号語を捨てる段が要る．捨てる操作そのものは補題 6.3.6 と同じ形だが，捨てる基準が誤り確率ではなく電力になるので，捨てられる符号語が少ないことを別に示すことになる．どちらも第2章・第6章の道具の連続版で，本書はそれを用意していない．「本書で証明しない」ことと「形式化されていない」ことは別である．本節が借りた主張は，本書が証明を載せないだけで，無条件の機械検証済みの定理として形式化されている．

形式化: awgn_channel_coding_theorem_of_isAwgnChannelMeasurable (ソース)

形式化上の注記. 形式化の宣言の仮定は，借りた主張と一つずつ対応している． $𝑃 > 0$ ，雑音の分散が $0$ でないこと， $𝑅 > 0$ ， $𝑅$ が閉じた式より小さいこと，目標の誤り確率が正であることの五つで，これがすべてである．核が可測であるという正則性の条件は，この宣言では引数になっていない．同じ名前空間の isAwgnChannelMeasurable (InformationTheory/Shannon/AWGN/ChannelMeasurability.lean) が中で当てて解消しており，宣言の名前の後半がそのことを表している．結論も同じ形で，ある番号から先のすべての $𝑛$ について，メッセージ数の下界と電力制約を満たす符号があり，どのメッセージについても誤り確率が目標を下回る，という形をしている．形式化は $l o g$ を自然対数にとるので，本文が $2 𝑛 𝑅$ と書く量はあちらでは $e x p (𝑛 𝑅)$ にあたり，レートの単位もナットである．底をそろえれば同じ主張である．

ガウス通信路の符号化定理

達成可能性と逆定理がそろったので，本章の主定理を述べる．第6章定理 6.4.9 と同じ形の合わせ方である．

系 8.4.2（ガウス通信路の符号化定理）. $𝑁 > 0$ ， $𝑃 > 0$ とする．このとき定義 8.3.2 の達成レートの集合 $R (𝑃, 𝑁)$ は空でなく

s u p R (𝑃, 𝑁) = 12 l o g (1 + 𝑃 𝑁) = 𝐶 (𝑃, 𝑁)

である．

証明. $R (𝑃, 𝑁)$ は空でない. 各 $𝑛$ でメッセージ数 $1$ の符号をとる．符号語は $𝑐 (1) : = 0 \in ℝ 𝑛$ の $1$ 本で，これは電力制約 $0 \leq 𝑛 𝑃$ を満たす．復号器はつねに $1$ を返すものとし，誤りの事象は空だから最大誤り確率は $0$ である．レートの列は $𝑅 𝑛 = 0$ で上に有界だから，この族は定義 8.3.2 の意味で達成可能で，その達成レートは $0$ である．

$s u p R (𝑃, 𝑁) \leq 12 l o g (1 + 𝑃 / 𝑁)$ . 系 8.3.6 より $R (𝑃, 𝑁)$ のどの元も $12 l o g (1 + 𝑃 / 𝑁)$ 以下だから，これは上界である．上限は上界のうち最小のものだから，不等式が従う．

$12 l o g (1 + 𝑃 / 𝑁) \leq s u p R (𝑃, 𝑁)$ . $0 < 𝑅 < 12 l o g (1 + 𝑃 / 𝑁)$ を満たす実数 $𝑅$ を任意にとり， $𝑅 \in R (𝑃, 𝑁)$ を示す．手順は第6章系 6.3.8 の証明と同じ三段で，そこで定理 6.3.7 が果たした役は，本節で借りたガウス通信路の達成可能性が果たす．

長さごとの符号を $1$ 本の族に貼り合わせる．各 $𝑘 \geq 1$ について，借りたガウス通信路の達成可能性を目標の誤り確率 $1 / 𝑘$ に対して使い，そこで得られる長さの下限を $𝑛 𝑘$ と書く． $𝑛' 𝑘 : = m a x (𝑛 1, \dots, 𝑛 𝑘, 𝑘)$ とおけば $(𝑛' 𝑘)$ は広義単調増加で $𝑛' 𝑘 \geq 𝑘$ だから $𝑛' 𝑘 \to \infty$ であり， $𝑛 \geq 𝑛' 1$ のとき ${𝑘 : 𝑛' 𝑘 \leq 𝑛}$ は空でない有限集合になる．その最大値を $𝑘 (𝑛)$ と書くと $𝑛 \geq 𝑛' 𝑘 (𝑛) \geq 𝑛 𝑘 (𝑛)$ だから，長さ $𝑛$ について，メッセージ数が $⌈ 2 𝑛 𝑅 ⌉$ 以上で最大誤り確率が $1 / 𝑘 (𝑛)$ 未満の符号がとれる． $𝑛 < 𝑛' 1$ の有限個の長さには，上で作ったメッセージ数 $1$ の符号をとる．

メッセージ数をちょうどに削る． $𝑛 \geq 𝑛' 1$ でとった符号のメッセージ数は $⌈ 2 𝑛 𝑅 ⌉$ 以上でしかないので，レートの列をそろえるために削る．残すメッセージを $⌈ 2 𝑛 𝑅 ⌉$ 個だけ選び，それを $𝑚 1, \dots, 𝑚 ⌈ 2 𝑛 𝑅 ⌉$ として，新しい番号 $1, \dots, ⌈ 2 𝑛 𝑅 ⌉$ に付け替える．以下， $𝑛 \geq 𝑛' 1$ では $𝑀 𝑛 : = ⌈ 2 𝑛 𝑅 ⌉$ ， $𝑛 < 𝑛' 1$ では $𝑀 𝑛 : = 1$ とする．

削ったあとの符号が定義 8.3.1 の符号になっていることを確かめる．この確認だけは，誤り確率が積分で定まるガウス通信路に固有である．メッセージを削っても符号語は元のままだから，電力制約はそのまま保たれる．復号器は元のものを使い，捨てたメッセージを指したときは $1$ を返すことにする．新しい番号 $𝑗 \neq 1$ に対する誤りの事象は元の番号 $𝑚 𝑗$ の誤りの事象と同じ集合なので，そこでどの符号語に対応する密度も積分できることは，定義 8.3.1 からそのまま引き継がれる．新しい番号 $1$ に対する誤りの事象は，捨てなかった番号 $𝑗 \neq 1$ にわたる ${𝑦 𝑛 : 𝑑 (𝑦 𝑛) = 𝑚 𝑗}$ の互いに素な和である．各項の上での積分は，全積分 $1$ から ${𝑦 𝑛 : 𝑑 (𝑦 𝑛) \neq 𝑚 𝑗}$ の上での積分を引いたものとして，どの符号語に対応する密度についても定まる．よって 8.3 節で既知とした，積分できる集合どうしの有限個の和と差についての扱いにより，誤りの事象の上でも密度は積分できる．しかもこの集合は元の番号 $𝑚 1$ の誤りの事象に含まれるから，最大誤り確率は増えない．

誤り確率とレートの極限をとる． $𝜁 > 0$ をとり， $1 / 𝑘 < 𝜁$ となる $𝑘$ を選ぶと， $𝑛 \geq 𝑛' 𝑘$ では $𝑘 (𝑛) \geq 𝑘$ だから最大誤り確率は $1 / 𝑘$ 未満であり， $𝜁$ 未満である．よって $𝑃 (𝑛) 𝑒, m a x \to 0$ である．レートのほうは， $𝑅 > 0$ と $𝑛 \geq 1$ より $2 𝑛 𝑅 \geq 1$ だから，天井関数の性質 $𝑡 \leq ⌈ 𝑡 ⌉ < 𝑡 + 1$ より $2 𝑛 𝑅 \leq ⌈ 2 𝑛 𝑅 ⌉ < 2 𝑛 𝑅 + 1 \leq 2 \cdot 2 𝑛 𝑅$ である．補題 8.2.5 より $l o g$ は単調だから，対数をとって $𝑛$ で割ると $𝑛 \geq 𝑛' 1$ について $𝑅 \leq 𝑅 𝑛 < 𝑅 + 1 / 𝑛$ を得る．とくにレートの列は上に有界で， $𝑛 \to \infty$ で $𝑅$ に収束する．残る有限個の $𝑛$ では $𝑅 𝑛 = 0$ だから，上に有界であることも下極限の値も変わらない．よってこの族は定義 8.3.2 の意味で達成可能で，その達成レートは $𝑅$ である．

$𝑅$ は $12 l o g (1 + 𝑃 / 𝑁)$ 未満の任意の正数だったから $s u p R (𝑃, 𝑁) \geq 12 l o g (1 + 𝑃 / 𝑁)$ である．二つを合わせて等号を得る．最後の等号は定理 8.2.4 による． $◼$

形式化上の注記. 系 8.4.2 に対応する単独の宣言はない．第6章 6.4 節で触れたとおり，達成レートの集合そのものに対応する宣言が通信路の側に用意されていないので，両側を突き合わせるこの主張も形式化の外にある．片側ずつの機械検証は，達成可能性が本節で借りた主張に，逆定理が定理 8.3.5 に紐付けた宣言まで及んでいる．

系 8.4.2 によって，8.2 節で最大化問題の値として定めた $𝐶 (𝑃, 𝑁)$ が， $1$ 回の使用あたりに運べるビット数という操作的な意味をもつ．第6章定理 6.4.9 のときと同じで，上限が達成されるかどうかは言っていない． $𝑅 = 𝐶 (𝑃, 𝑁)$ ちょうどのレートで最大誤り確率が $0$ に収束する符号族があるかは，ここでは問わない．

符号語の本数で見る. $𝑃 / 𝑁 = 1$ とすると $𝐶 (𝑃, 𝑁) = 0.5$ ビットである．ここで $𝑅 = 0.4$ ， $𝑛 = 100$ とすれば，符号語は $240$ 本（およそ $1.1 \times 1012$ 本），どれも $ℝ 100$ の点で，原点からの距離は $\sqrt 100 𝑃 = 10 \sqrt 𝑃$ 以下である．命題 8.4.1 の勘定でいえば，半径 $10 \sqrt 2 𝑃$ の球の中に半径 $10 \sqrt 𝑃$ の雑音球を $250$ 個ほど詰める配置にあたり， $240$ 本はそれよりだいぶ余裕をとった本数になっている．その余裕が，雑音の $2$ 乗和が $𝑛 𝑁$ ちょうどにはならないぶんを吸収する．

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