6.2 ブロック通信路符号と結合典型集合

6.1 節の容量 $𝐶 (𝑊)$ は，相互情報量の最大化問題の値でしかない．通信路をどう使うかという話はまだ一度も出てきていないので，そのままでは「 $𝐶 (𝑊)$ ビット送れる」と言う資格がない．本節ではまず，送るとはどういう操作かを符号として定義し，「誤りなく送れるレート」を第2章と同じ形で定める．そのうえで，達成可能性の証明を支える道具（結合典型集合）を用意する．

道具の役目は第2章と同じである．あちらは「実際に出る系列はほぼすべて典型集合に落ち，その個数が約 $2 𝑛 𝐻$ である」という数え上げが，そのまま圧縮の限界を与えた．こちらで数えたいのは，受け取った $𝑦 𝑛$ と辻褄の合う入力 $𝑥 𝑛$ が何通りあるか，である．その個数が少なければ，符号語を離して置いておくかぎり取り違えは起きない．結合典型集合は，この「辻褄が合う」を典型性の言葉で書いたものである．

以下，入力分布 $𝑝$ を一つ固定し， ${(𝑋 𝑖, 𝑌 𝑖)} 𝑖 \geq 0$ を結合分布 $𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥)$ からの i.i.d. 列とする．長さ $𝑛$ のブロックを $𝑋 𝑛 : = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ ， $𝑌 𝑛 : = (𝑌 0, \dots, 𝑌 𝑛 - 1)$ と書く．さらに，結合分布が $X \times Y$ の全点で正，すなわち $𝑝 (𝑥) 𝑊 (𝑦 ∣ 𝑥) > 0$ をすべての $(𝑥, 𝑦)$ で仮定する．第2章 2.2 節で周辺分布に置いたのと同じ仮定だが，こちらでは意味が違う．あちらは確率 0 の文字をアルファベットから落とせば済んだのに対し， $𝑊 (𝑦 ∣ 𝑥) = 0$ の対を落とすことはできない．同じ $𝑦$ が別の $𝑥$ からは正の確率で届くかもしれないからである．つまりこれは通信路への実質的な制約である．6.3 節の主定理はこの制約を必要としない形で述べる（本文が証明を付けるのはこの制約のある場合までで，外す段は道筋だけを示す）．

ブロック通信路符号

定義 6.2.1（ブロック通信路符号）. 長さ $𝑛$ の ブロック通信路符号 とは，メッセージ数 $𝑀 \geq 1$ と，符号化写像 $𝑐 : {1, \dots, 𝑀} \to X 𝑛$ ，復号器 $𝑑 : Y 𝑛 \to {1, \dots, 𝑀}$ の組である． $𝑐 (𝑚)$ をメッセージ $𝑚$ の 符号語 と呼ぶ．その レート を

𝑅 : = 1 𝑛 l o g 𝑀

で定める．メッセージ $𝑚$ を送ったときの 誤り確率，およびそれを $𝑚$ について最悪値と平均で束ねた 最大誤り確率・平均誤り確率 を

𝑃 𝑒 (𝑚) : = \sum 𝑦 𝑛 : 𝑑 (𝑦 𝑛) \neq 𝑚 𝑊 𝑛 (𝑦 𝑛 ∣ 𝑐 (𝑚)), 𝑃 𝑒, m a x : = m a x 1 \leq 𝑚 \leq 𝑀 𝑃 𝑒 (𝑚), ¯ 𝑃 𝑒 : = 1 𝑀 𝑀 \sum 𝑚 = 1 𝑃 𝑒 (𝑚)

で定める．

レート $𝑅$ は「通信路を 1 回使うあたり何ビット運べるか」である． $𝑀$ 通りのメッセージを区別するのに $l o g 𝑀$ ビット要り，それを $𝑛$ 回の使用で運んでいるから，割り算がそのまま1 回あたりの取り分になる．第2章のレート（定義 2.3.1）が「1 文字あたり何ビット使ったか」という費用だったのに対し，こちらは「1 回あたり何ビット稼げたか」という収入である．向きが逆なので，良い符号とはレートが高いものになる．

誤り確率を二通り定めたのは，この二つが実際に食い違うからである．定義から $¯ 𝑃 𝑒 \leq 𝑃 𝑒, m a x$ はつねに成り立つが，逆は言えない．平均が小さくても，特定のメッセージだけがひどく誤る符号はありうる．6.3 節では平均が小さい符号をまず作り，そのあとで悪いメッセージを捨てて最大誤り確率に直す．

形式化: 符号 Code，メッセージごとの誤り確率 errorProbAt，平均誤り確率 averageErrorProb (ソース)

形式化上の注記. 長さ $𝑛$ への延長 $𝑊 𝑛$ は積による延長 Channel.toBlock (InformationTheory/Shannon/BlockwiseChannel/Definition.lean) として形式化されているが，errorProbAt はそれを経由せず積測度を直に書いている．最大誤り確率のほうは束ねた宣言がなく，「すべてのメッセージについて errorProbAt が小さい」という形で書かれる．

定義 6.2.2（達成レート）. 長さ $𝑛$ のブロック通信路符号を第 $𝑛$ 項とする族 $(𝑀 𝑛, 𝑐 𝑛, 𝑑 𝑛) 𝑛 \geq 1$ が達成可能 であるとは，最大誤り確率が $𝑃 (𝑛) 𝑒, m a x \to 0$ を満たし，かつレートの列 $𝑅 𝑛 = 1 𝑛 l o g 𝑀 𝑛$ が上に有界なことをいう．このとき $l i m i n f 𝑛 𝑅 𝑛$ をその族の達成レート と呼び，達成レート全体の集合を $R (𝑊)$ と書く．

第2章の定義 2.3.5 をそのまま通信路側に移した定義である．上に有界という条件の役目も同じで，これがないと下極限が実数として定まらない族が混じる．違うのは求めるものの向きだけで，第2章は $R$ の下限がエントロピーに一致することを示した．こちらで知りたいのは $R (𝑊)$ の上限で，それが $𝐶 (𝑊)$ に一致する，というのが通信路符号化定理である．なお，最大誤り確率のかわりに平均誤り確率で定義したらどうなるかは6.3 節で扱う．補題 6.3.6 が，平均誤り確率の小さい符号からメッセージを半分捨てて最大誤り確率の小さい符号を得る手を与える．

形式化上の注記. 達成レートに対応する宣言は通信路側にはない．第2章の IsAchievableCode (InformationTheory/Shannon/AEP/Basic/Achievability.lean) にあたるものが，まだ用意されていないのである．

第2章の定理を積アルファベットに当てる. 本節が使う道具は第2章の典型集合の性質（定理 2.2.3・定理 2.2.4・定理 2.2.5）だけで，新しく借りるものはない．ただし当てる相手は $X$ 上の情報源ではなく，積アルファベット $X \times Y$ 上のi.i.d. 情報源 ${(𝑋 𝑖, 𝑌 𝑖)}$ と，その二つの成分列 ${𝑋 𝑖}$ ・ ${𝑌 𝑖}$ の三つである．どれも i.i.d. なので，第2章の定理は仮定を足さずにそのままの形で当たる．第2章が大数の法則を借りたぶんも，この三つを経由してだけ効く．

結合典型集合

定義 6.2.3（結合典型集合）. $𝜀 > 0$ と $𝑛 \geq 1$ に対し，結合典型集合 $𝐴 (𝑛) 𝜀 \subseteq X 𝑛 \times Y 𝑛$ を，次の三つをすべて満たす対 $(𝑥 𝑛, 𝑦 𝑛)$ の集合として定める：

∣ - 1 𝑛 l o g 𝑝 (𝑥 𝑛) - 𝐻 (𝑋) ∣ < 𝜀, ∣ - 1 𝑛 l o g 𝑞 (𝑦 𝑛) - 𝐻 (𝑌) ∣ < 𝜀, ∣ - 1 𝑛 l o g 𝑝 (𝑥 𝑛, 𝑦 𝑛) - 𝐻 (𝑋, 𝑌) ∣ < 𝜀 .

ここで $𝑝 (𝑥 𝑛) : = \prod 𝑖 𝑝 (𝑥 𝑖)$ ， $𝑞 (𝑦 𝑛) : = \prod 𝑖 𝑞 (𝑦 𝑖)$ ， $𝑝 (𝑥 𝑛, 𝑦 𝑛) : = \prod 𝑖 𝑝 (𝑥 𝑖) 𝑊 (𝑦 𝑖 ∣ 𝑥 𝑖)$ である．

三つの条件は，定義 2.2.1 の典型性を ${𝑋 𝑖}$ ， ${𝑌 𝑖}$ ， ${(𝑋 𝑖, 𝑌 𝑖)}$ という三つの情報源それぞれに当てたものにほかならない． $𝑥 𝑛$ が入力の側で典型で， $𝑦 𝑛$ が出力の側で典型で，しかも対として組んだときに結合分布から見ても典型である，というのが $(𝑥 𝑛, 𝑦 𝑛) \in 𝐴 (𝑛) 𝜀$ の内容である．

三つとも課すのは無駄に見えるが，以下の三つの定理でそれぞれ別の役目を果たす．結合の条件は集合の大きさを与え（定理 6.2.5），入力側と出力側の条件は，独立に選んだ組がこの集合に落ちる確率を押さえるのに要る（定理 6.2.7）．どれか一つを落とすと，対応する評価がそのまま失われる．

形式化: jointlyTypicalSet (ソース)

例 6.2.4（二元対称通信路の結合典型集合）. 例 6.1.8 の二元対称通信路で反転確率を $0 < 𝜌 < 1 / 2$ とし，入力分布を $𝑝 (0) = 𝑝 (1) = 1 / 2$ にとる．対 $(𝑥 𝑛, 𝑦 𝑛)$ の食い違う位置の個数を $𝑘$ と書くと， $𝜀 > 0$ と $𝑛 \geq 1$ に対し，定義 6.2.3 の三つの条件のうち第 1 と第 2 はどの対でも成り立ち，第 3 は

∣ 𝑘 𝑛 - 𝜌 ∣ < 𝜀 / l o g 1 - 𝜌 𝜌

と同値である．この通信路では，結合典型な対とは食い違いの割合が反転確率に近い対にほかならない．

証明. 入力が一様だから $𝑝 (𝑥 𝑛) = 2 - 𝑛$ であり， $- 1 𝑛 l o g 𝑝 (𝑥 𝑛) = 1$ である．例 6.1.8 の証明で見たとおり出力も一様だから $𝑞 (𝑦 𝑛) = 2 - 𝑛$ で，同じく $- 1 𝑛 l o g 𝑞 (𝑦 𝑛) = 1$ である．いっぽう例 1.1.3 より $𝐻 (𝑋) = 𝐻 (𝑌) = l o g 2 = 1$ だから，第 1 と第 2 の条件は左辺が 0 になってどの対でも成り立つ．

第 3 を計算する．食い違う位置では $𝑊 (𝑦 𝑖 ∣ 𝑥 𝑖) = 𝜌$ ，一致する位置では $1 - 𝜌$ だから

𝑝 (𝑥 𝑛, 𝑦 𝑛) = 2 - 𝑛 𝜌 𝑘 (1 - 𝜌) 𝑛 - 𝑘, - 1 𝑛 l o g 𝑝 (𝑥 𝑛, 𝑦 𝑛) = 1 - 𝑘 𝑛 l o g 𝜌 - (1 - 𝑘 𝑛) l o g (1 - 𝜌)

である．例 6.1.8 の証明より $𝐻 (𝑌 ∣ 𝑋) = 𝐻 𝑏 (𝜌)$ だから，定理 1.2.3 のチェイン則で $𝐻 (𝑋, 𝑌) = 𝐻 (𝑋) + 𝐻 (𝑌 ∣ 𝑋) = 1 + 𝐻 𝑏 (𝜌)$ である．二つの差をとると $𝑘 𝑛$ の一次の項だけが残り

- 1 𝑛 l o g 𝑝 (𝑥 𝑛, 𝑦 𝑛) - 𝐻 (𝑋, 𝑌) = (𝑘 𝑛 - 𝜌) l o g 1 - 𝜌 𝜌

となる． $0 < 𝜌 < 1 / 2$ だから $l o g 1 - 𝜌 𝜌 > 0$ であり，絶対値をとって $𝜀$ と比べれば主張の形になる． $◼$

食い違いの個数だけで決まるのは，この通信路が対称で，しかも入力を一様にとったからである．それでも読み方は一般の場合に持ち越せる． $𝑛$ が大きければ実際の食い違いは $𝜌 𝑛$ の近くに集まるので，送った符号語と受け取った語の対はほぼ確実に結合典型になる（次に見る定理 6.2.6）．逆に無関係な符号語をひとつ持ってきて $𝑦 𝑛$ と組めば，食い違いの割合は $1 / 2$ のあたりになるから， $𝜌$ が $1 / 2$ から離れているかぎり結合典型にはならない．この二つの隔たりが，次節の復号器が働く余地である．

性質1：結合典型集合の大きさ

定理 6.2.5. $𝜀 > 0$ とする．任意の $𝑛 \geq 1$ に対し

∣ 𝐴 (𝑛) 𝜀 ∣ \leq 2 𝑛 (𝐻 (𝑋, 𝑌) + 𝜀) .

証明. ${(𝑋 𝑖, 𝑌 𝑖)}$ は積アルファベット $X \times Y$ 上の i.i.d. 情報源だから，第2章の典型集合 $𝑇 (𝑛) 𝜀$ をこの情報源に対して作れる．定義 6.2.3 の第 3 の条件は，対 $(𝑥 𝑛, 𝑦 𝑛)$ を並べ替えた系列 $((𝑥 0, 𝑦 0), \dots, (𝑥 𝑛 - 1, 𝑦 𝑛 - 1))$ がこの $𝑇 (𝑛) 𝜀$ に属することと同じである．並べ替えは単射だから $∣ 𝐴 (𝑛) 𝜀 ∣ \leq ∣ 𝑇 (𝑛) 𝜀 ∣$ であり，定理 2.2.5 の上界より $∣ 𝑇 (𝑛) 𝜀 ∣ \leq 2 𝑛 (𝐻 (𝑋, 𝑌) + 𝜀)$ である． $◼$

形式化: jointlyTypicalSet_card_le (ソース)

形式化上の注記. 形式化された定理には，本文と同じ「全点で正」の仮定が付く．形式化が $l o g 0 = 0$ という規約の上に乗っているために，確率 0 の対を含む系列の経験エントロピーが $+ \infty$ ではなく有限値になってしまうためで，ずれの理由は第2章 2.2 節と同じである．

上界を出すのに使ったのは結合の条件だけで，入力側・出力側の条件は捨てている．条件を捨てれば集合は大きくなるだけなので，上界としてはそれで足りる．

性質2：本物の組はほぼ確実に結合典型である

定理 6.2.6. $𝜀 > 0$ とする． $𝑛 \to \infty$ のとき

P r [(𝑋 𝑛, 𝑌 𝑛) \in 𝐴 (𝑛) 𝜀] ⟶ 1 .

証明. 定義 6.2.3 の三つの条件それぞれが定める事象を考える．第 1 の条件が定める事象は，情報源 ${𝑋 𝑖}$ に対する定理 2.2.3 より確率が 1 に収束する．第 2 の条件も情報源 ${𝑌 𝑖}$ に対して同様，第 3 の条件も積アルファベット上の情報源 ${(𝑋 𝑖, 𝑌 𝑖)}$ に対して同様である．

三つの余事象の確率はいずれも 0 に収束するから，その和も 0 に収束する．求める事象は三つの共通部分で，その余事象は三つの余事象の合併に含まれるので，確率は 1 に収束する． $◼$

形式化: jointlyTypicalSet_prob_tendsto_one (ソース)

形式化上の注記. 形式化された定理には「全点で正」の仮定が付かない．収束の証明だけは確率 0 の対があっても壊れないためである．独立性の要求も本文より弱く，組 $(𝑋 𝑖, 𝑌 𝑖)$ のどの二つをとっても独立であること，すなわち対独立で足りる．

性質3：無関係な組が結合典型になる確率

定理 6.2.7. $𝜀 > 0$ と $𝑛 \geq 1$ とする． $˜ 𝑋 𝑛$ を $𝑋 𝑛$ と同じ分布をもち， $𝑌 𝑛$ とは独立なブロックとすると

P r [(˜ 𝑋 𝑛, 𝑌 𝑛) \in 𝐴 (𝑛) 𝜀] \leq 2 - 𝑛 (𝐼 (𝑝; 𝑊) - 3 𝜀) .

証明. $˜ 𝑋 𝑛$ と $𝑌 𝑛$ は独立だから，求める確率は

P r [(˜ 𝑋 𝑛, 𝑌 𝑛) \in 𝐴 (𝑛) 𝜀] = \sum (𝑥 𝑛, 𝑦 𝑛) \in 𝐴 (𝑛) 𝜀 𝑝 (𝑥 𝑛) 𝑞 (𝑦 𝑛)

である．和の各項を上から抑える． $(𝑥 𝑛, 𝑦 𝑛) \in 𝐴 (𝑛) 𝜀$ なら定義 6.2.3 の第 1 の条件が成り立つので，情報源 ${𝑋 𝑖}$ に対する定理 2.2.4 より $𝑝 (𝑥 𝑛) \leq 2 - 𝑛 (𝐻 (𝑋) - 𝜀)$ ．第 2 の条件と情報源 ${𝑌 𝑖}$ から同様に $𝑞 (𝑦 𝑛) \leq 2 - 𝑛 (𝐻 (𝑌) - 𝜀)$ ．項数は定理 6.2.5 で押さえられるから

\sum (𝑥 𝑛, 𝑦 𝑛) \in 𝐴 (𝑛) 𝜀 𝑝 (𝑥 𝑛) 𝑞 (𝑦 𝑛) \leq 2 𝑛 (𝐻 (𝑋, 𝑌) + 𝜀) \cdot 2 - 𝑛 (𝐻 (𝑋) - 𝜀) \cdot 2 - 𝑛 (𝐻 (𝑌) - 𝜀) = 2 - 𝑛 (𝐻 (𝑋) + 𝐻 (𝑌) - 𝐻 (𝑋, 𝑌) - 3 𝜀)

となる．命題 6.1.3 より $𝐻 (𝑋) + 𝐻 (𝑌) - 𝐻 (𝑋, 𝑌) = 𝐼 (𝑝; 𝑊)$ だから，これが主張の右辺である． $◼$

形式化: jointlyTypicalSet_indep_prob_le (ソース)

形式化上の注記. 形式化された定理には，定理 6.2.5 と同じ規約の都合で本文と同じ「全点で正」の仮定が付く．独立性の要求は定理 6.2.6 より強く，ブロックの分布を成分の積に分解するので相互独立を求める．

三つの役割を並べて読む. 定理 6.2.6 は「送ったものと受け取ったものは辻褄が合う」，定理 6.2.7 は「無関係な入力が偶然辻褄を合わせる確率は $2 - 𝑛 𝐼$ 程度しかない」と言っている．この二つが次節の復号器を挟み撃ちにする．受け取った $𝑦 𝑛$ に対して結合典型になる符号語を探せば，正しい符号語はほぼ確実に見つかり（定理 6.2.6），他の符号語がまぎれこむ確率は 1 個あたり $2 - 𝑛 (𝐼 - 3 𝜀)$ 以下である（定理 6.2.7）．符号語が $2 𝑛 𝑅$ 個あるとして，まぎれこみの総量はおよそ $2 𝑛 𝑅 \cdot 2 - 𝑛 𝐼$ だから， $𝑅 < 𝐼$ ならこれは 0 に向かう．定理 6.2.5 は，その $2 - 𝑛 𝐼$ という数を出すための個数の勘定を担っている． $𝑅 < 𝐼$ という条件がここで初めて姿を見せることに注意したい．入力分布 $𝑝$ を容量を達成するものにとれば $𝐼 (𝑝; 𝑊) = 𝐶 (𝑊)$ になり，条件は $𝑅 < 𝐶 (𝑊)$ になる．

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