6.7 一般の通信路の容量

本章はここまで，通信路に記憶がないことを仮定してきた．定義 6.1.1 の積の形がそれで，各時刻の雑音がそれ以前の入出力に一切依存しない，という仮定である．この仮定は強い．実際の伝送路では雑音が固まって起きることがある．つまり，ある時刻に誤りが起きると，次の時刻でも起きやすい．第3章で情報源に記憶を許したのと同じことを，こんどは通信路の側で許したい．

最小のモデルを一つ見ておく． $X = Y = {0, 1}$ とし，雑音の列 $𝑍 0, 𝑍 1, \dots$ を ${0, 1}$ 上のマルコフ情報源（定義 3.1.3）にとる．遷移確率を

P r [𝑍 𝑖 + 1 = 1 ∣ 𝑍 𝑖 = 0] = 0.05, P r [𝑍 𝑖 + 1 = 1 ∣ 𝑍 𝑖 = 1] = 0.55

とし，初期分布はその定常分布 $P r [𝑍 𝑖 = 1] = 0.1$ にとる．入力とは独立にこの列を走らせ，出力を $𝑌 𝑖 = 𝑋 𝑖 \oplus 𝑍 𝑖$ （排他的論理和）で定める． $𝑍 𝑖 = 1$ の時刻が誤りの起きる時刻である．

各時刻だけを切り出して見ると，誤りの確率は $0.1$ で入力によらないから，これは反転確率 $0.1$ の二元対称通信路（例 6.1.8）と区別がつかない．違いはブロックで見たときに出る．ある時刻に誤りが起きたと分かると，次の時刻に誤りが起きる確率は $0.1$ から $0.55$ へ跳ね上がる．誤りは 1 個ずつばらばらに現れるのではなく，続けて何個か固まって現れる．定義 6.1.1 の積の形は，まさにこの跳ね上がりを禁じている．

記憶を許すと，容量の定義そのものが立ち行かなくなる．定義 6.1.4 は通信路を 1 回使ったときの相互情報量 $𝐼 (𝑝; 𝑊)$ を最大化していたが，記憶のある通信路では「1 回使う」という操作がそれ単独では定まらない．時刻 $𝑖$ の振る舞いが過去に依存するのだから，1 文字だけ切り出して測っても，その通信路が何を運べるかは分からない．

出口は素直である．1 文字で測れないなら，長さ $𝑛$ のブロックでまとめて測る．ブロック全体を1 つの大きな通信路（入力アルファベットが $X 𝑛$ ，出力アルファベットが $Y 𝑛$ の通信路）と見れば，定義 6.1.4 がそのまま当たって容量 $𝐶 𝑛$ が定まる．あとはこれを $𝑛$ で割って 1 文字あたりに直し， $𝑛 \to \infty$ の極限をとればよい．本節ではこの定義を置き，それが記憶のない場合にはもとの $𝐶 (𝑊)$ に戻ることを確かめる．

ブロック通信路

定義 6.7.1（ブロック通信路）. ブロック通信路 とは，各ブロック長 $𝑛 \geq 1$ に対して，入力語 $𝑥 𝑛 \in X 𝑛$ ごとに $Y 𝑛$ 上の分布 $𝑊 (𝑛) (\cdot ∣ 𝑥 𝑛)$ を与える対応 $𝕎 = (𝑊 (𝑛)) 𝑛 \geq 1$ のことをいう．定義 6.1.1 の通信路 $𝑊$ に対し

𝑊 (𝑛) (𝑦 𝑛 ∣ 𝑥 𝑛) : = 𝑛 - 1 \prod 𝑖 = 0 𝑊 (𝑦 𝑖 ∣ 𝑥 𝑖)

と定めたブロック通信路を， $𝑊$ の 積による延長 と呼ぶ．

形式化: ブロック通信路 BlockwiseChannel，積による延長 Channel.toBlock とBlockwiseChannel.ofMemoryless (ソース)

定義 6.7.1 が定義 6.1.1 から落としたものは，ただ一つ，積の形である．各 $𝑛$ ごとに $X 𝑛$ から $Y 𝑛$ への条件付き分布が与えられるだけで，それらが 1 文字分の通信路から組み上がっているとは仮定しない．だから時刻をまたいで雑音が相関していてよいし，ブロック長ごとにまったく別の振る舞いをしていてもよい．記憶のない通信路は，積による延長という特別な場合として，この枠の中に入る．

極限としての容量

定義 6.7.2（ブロック通信路の容量）. $𝕎 = (𝑊 (𝑛)) 𝑛 \geq 1$ をブロック通信路とする．ブロック長 $𝑛$ のブロック容量 を， $X 𝑛$ 上の分布 $𝑝 (𝑛)$ 全体にわたる上限

𝐶 𝑛 (𝕎) : = s u p 𝑝 (𝑛) 𝐼 (𝑝 (𝑛); 𝑊 (𝑛))

で定める（ $𝐼 (\cdot; \cdot)$ は定義 6.1.2 を入力アルファベット $X 𝑛$ ，出力アルファベット $Y 𝑛$ に対して読んだもの）．1 文字あたりに直した $1 𝑛 𝐶 𝑛 (𝕎)$ を 容量レート と呼ぶ． $𝑛 \to \infty$ でこの列が収束するとき，その極限を

𝐶 \infty (𝕎) : = l i m 𝑛 \to \infty 1 𝑛 𝐶 𝑛 (𝕎)

と書く．

形式化: ブロック容量 BlockwiseChannel.capacityN (ソース)，容量レート capacityRate と極限 capacity_lim (ソース)

$𝑛$ で割るのは， $𝐶 𝑛$ が「 $𝑛$ 回の使用で運べる量」だからである．定義 6.2.1 のレートが $1 𝑛 l o g 𝑀$ だったのと同じ割り算で，比べたいものを 1 回の使用あたりにそろえている．極限をとるのは，記憶のある通信路では短いブロックが不利になりうるからである．過去に依存する分だけ，ブロックの先頭では使える情報が少ない． $𝑛$ を大きくすればその端の効果は薄まるので，長いブロックほど 1 文字あたりの取り分は良くなる見込みがある．どこまで良くなるかを聞いているのが極限である．

形式化上の注記. 極限が存在するかどうかは，一般のブロック通信路については自明でない．本書はその存在を証明しないので，定義 6.7.2 は収束する場合にだけ $𝐶 \infty$ を定めている．形式化のほうは極限をとる操作を無条件に定義していて，収束しないブロック通信路に対しては意味のない値を返す．以下で扱う積による延長の場合には，命題 6.7.3 が容量レートの列を決定するので，この食い違いは起きない．

記憶がない場合に戻ること

命題 6.7.3. $𝑊$ を通信路（定義 6.1.1）， $𝕎$ をその積による延長（定義 6.7.1）とする．このときすべての $𝑛 \geq 1$ について

1 𝑛 𝐶 𝑛 (𝕎) = 𝐶 (𝑊)

が成り立つ．とくに容量レートの列は定数で， $𝐶 (𝑊)$ に収束する．

証明. $𝑛 \geq 1$ を固定し， $𝐶 𝑛 (𝕎) \leq 𝑛 𝐶 (𝑊)$ と $𝐶 𝑛 (𝕎) \geq 𝑛 𝐶 (𝑊)$ を別々に示す．

上界を示す． $X 𝑛$ 上の分布 $𝑝 (𝑛)$ を任意にとり， $(𝑋 𝑛, 𝑌 𝑛)$ を結合分布 $𝑝 (𝑛) (𝑥 𝑛) 𝑊 (𝑛) (𝑦 𝑛 ∣ 𝑥 𝑛)$ に従う対とする．定義 6.7.1 より $𝑊 (𝑛)$ は積の形だから，補題 6.4.6 より $𝑋 𝑛$ を与えたとき出力 $𝑌 0, \dots, 𝑌 𝑛 - 1$ は条件付き独立であり，各 $𝑌 𝑖$ の条件付き分布は $𝑊 (\cdot ∣ 𝑋 𝑖)$ である．これは定理 1.8.5 が記憶のなさとして要求する二つの条件そのものだから，

𝐼 (𝑋 𝑛; 𝑌 𝑛) \leq 𝑛 - 1 \sum 𝑖 = 0 𝐼 (𝑋 𝑖; 𝑌 𝑖)

である．補題 6.4.6 からはさらに， $𝑝 (𝑛)$ の第 $𝑖$ 周辺分布を $𝑝 𝑖$ と書けば対 $(𝑋 𝑖, 𝑌 𝑖)$ の同時分布が $𝑝 𝑖 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ であることも出る．よって命題 6.1.3 より $𝐼 (𝑋 𝑖; 𝑌 𝑖) = 𝐼 (𝑝 𝑖; 𝑊)$ であり，定義 6.1.4 よりこれは $𝐶 (𝑊)$ 以下である．したがって $𝐼 (𝑝 (𝑛); 𝑊 (𝑛)) \leq 𝑛 𝐶 (𝑊)$ となる． $𝑝 (𝑛)$ は任意だったから， $𝑛 𝐶 (𝑊)$ は値の集合の上界であり，上限はそれ以下である．

下界に移る．定理 6.1.5 より $𝐼 (𝑝 *; 𝑊) = 𝐶 (𝑊)$ となる入力分布 $𝑝 *$ をとり， $𝑝 (𝑛) (𝑥 𝑛) : = \prod 𝑖 𝑝 * (𝑥 𝑖)$ と定める．このとき $𝑋 0, \dots, 𝑋 𝑛 - 1$ は互いに独立でどれも $𝑝 *$ に従い，積の形から，対 $(𝑋 0, 𝑌 0), \dots, (𝑋 𝑛 - 1, 𝑌 𝑛 - 1)$ は互いに独立でどれも同じ同時分布 $𝑝 * (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ に従う．よって定理 1.5.3 より

𝐼 (𝑋 𝑛; 𝑌 𝑛) = 𝑛 𝐼 (𝑋 0; 𝑌 0) = 𝑛 𝐼 (𝑝 *; 𝑊) = 𝑛 𝐶 (𝑊)

である．上限はこの値以上だから $𝐶 𝑛 (𝕎) \geq 𝑛 𝐶 (𝑊)$ となる．

二つを合わせて $𝐶 𝑛 (𝕎) = 𝑛 𝐶 (𝑊)$ であり， $𝑛$ で割れば主張を得る．定数列は自身の値に収束する． $◼$

形式化: ブロック容量の各 $𝑛$ の値 capacityN_ofMemoryless_eq (ソース)

形式化上の注記. 形式化は容量レートの側でも定数性を述べているが，そちらは「十分大きい $𝑛$ で定数」という形の capacityRate_ofMemoryless_eventually_const (InformationTheory/Shannon/GeneralDMC/Basic.lean) で，閾値を主張に含めない．命題 6.7.3 の「すべての $𝑛 \geq 1$ について」にそのまま対応するのは，ブロック容量の側の宣言である．

定理 6.7.4. $𝑊$ を通信路（定義 6.1.1）， $𝕎$ をその積による延長（定義 6.7.1）とする．このとき $𝐶 \infty (𝕎)$ は定まり，

𝐶 \infty (𝕎) = 𝐶 (𝑊)

である．

証明. 命題 6.7.3 より容量レートの列は定数 $𝐶 (𝑊)$ で， $𝐶 (𝑊)$ に収束する．よって定義 6.7.2 の極限は存在し，その値は $𝐶 (𝑊)$ である． $◼$

形式化: capacity_lim_eq_capacity_of_memoryless，容量レートの列が $𝐶 (𝑊)$ に収束することcapacity_lim_tendsto_of_memoryless (ソース)

一般化したら，もとの場所で値を確かめる. 定理 6.7.4 は驚きのない主張である．それでも確かめなければならない．定義を広げたとき，新しい定義がもとの場合にもとの値を返すことは保証されていないからである．もし $𝐶 \infty$ が記憶のない通信路で $𝐶 (𝑊)$ と違う値を出したら，どちらかの定義が悪いということになり，6.1 節から 6.6 節までに積み上げた $𝐶 (𝑊)$ の操作的な意味（定理 6.3.7 と系 6.6.12 が両側から挟んだ意味）は新しい定義には引き継がれない．定理 6.7.4 は，その引き継ぎが起きていることの確認である．一般化の作法として，この確認は省けない．

証明の中身を見ると，二つの向きで効いた道具が違うことに気づく．上からの評価では定理 1.8.5 が，入力に相関を許しても 1 文字あたりの取り分は増えないと言っていた．下からの評価では定理 1.5.3 が，入力を独立にとれば取り分がちょうど $𝑛$ 倍になると言っていた．記憶のない通信路では，入力を相関させても得はしないし，独立にとれば損もしない．だから $𝐶 𝑛$ は $𝑛$ に正比例し，容量レートは $𝑛$ によらない．記憶のある通信路でこの二つが崩れることが，極限を定義に持ち込まざるをえない理由である．

本章で $𝐶 (𝑊)$ は三つの顔を見せた．定義 6.1.4 の最大化問題の値，定理 6.3.7 と系 6.6.12 が両側から挟んだ「誤りなく運べるレートの限界」，そして命題 6.6.2 と系 6.6.3 が描いた「どの入力記号からも等しく遠い出力分布までの隔たり」である．三つ目は最大化子を見分ける道具になり，それがそのまま強逆定理を動かした．フィードバックを許しても値が変わらず（系 6.5.5），ブロックで測り直しても値が変わらない（定理 6.7.4）ことまで確かめたので， $𝐶 (𝑊)$ は通信路そのものに属する量だと言ってよい．

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