14.1 多元接続通信路

第6章の通信路には，送り手が 1 人と受け手が 1 人しかいなかった．実際の通信では，同じ電波や同じ回線を何人もが同時に使う．いちばん簡単な形は送り手が 2 人で受け手が 1 人というもので，2 人は互いの送るものを知らないまま同じ通信路に入力を流し込み，受け手は混ざった出力だけを見て 2 人ぶんのメッセージを取り出す．

この設定では「いくら送れるか」の答えが 1 つの数にならない．片方が通信路を独り占めすれば多く送れるが，そのぶん相手の取り分は減る．答えは 2 人の取り分の対 $(𝑅 1, 𝑅 2)$ の集合になり，取り分をどう分け合えるかというその形そのものが，第6章で容量が果たした役を引き受ける．以下ではこの集合を領域と呼ぶ．

本章では $l o g$ の底を 2 にとる．第6章・第9章と同じく $2 𝑛 𝑅$ の形の量を扱うので，指数と対数の底をそろえておくと式が読みやすい．

下付きの添字について 1 つ断っておく．本章の下付きの $1$ と $2$ は利用者や受信者の番号であって，時刻ではない．番号と時刻の両方を書くときは番号を先に置き，時刻はコンマのあとに続けて $𝑋 1, 𝑖$ （利用者 1 の時刻 $𝑖$ の入力）と書く．番号の要らない記号では下付きがそのまま時刻で， $𝑋 𝑖$ と書く．長さ $𝑛$ のブロックはどちらも上付きにして $𝑋 𝑛 1$ ， $𝑋 𝑛$ と書く．第2章 2.1 節から第13章まで $𝑋 0, 𝑋 1, \dots$ は時刻の並びを表してきたので， $𝑋 1$ という字面はそのまま重なる．番号を付ける記号ではこれは番号のほうだが，番号を付けない記号では時刻のほうである．どちらの記号なのかは節ごとに定まり，14.8 節だけは同じ $𝑋 1$ と $𝑌 1$ が両方に読めるので，そこで断りを置く．

「達成可能」という語も本章に何度も出るが，その形は設定ごとに違う．レートの対の集合を領域として述べるときは，本節の定義 14.1.3 のように，レートを下から抑える不等式と誤り確率の条件で書く．領域として述べない節では，符号の族をとってレートが目標の値に収束することを求める形が出てくる．形が変わるところでは，その節の定義か，道具を借りるところでそれを書き下すので，前の節の形は持ち越さないでよい．

形式化上の注記（本章共通）. 単位は本文と形式化で違う．形式化は $l o g$ を自然対数にとるので，相互情報量もレートもナットが単位であり，本文が $2 𝑛 𝑅$ と書く量はあちらでは $e x p (𝑛 𝑅)$ にあたる．底をそろえれば同じ主張である．

形式化の MACChannel (InformationTheory/Shannon/MultipleAccess/Basic.lean) は条件付き分布の族そのもの（入力の対に対して出力の分布を返す核）であって，各対についての総和が 1 という条件は含まない．その条件は，これを使う主張の側に別の前提として付いている．また，長さ $𝑛$ への積による延長を束ねた宣言は多元接続の側には用意されておらず，誤り確率の定義が積測度を直に書いている．

通信路と符号

定義 14.1.1（多元接続通信路）. $X 1$ ， $X 2$ ， $Y$ をどれも空でない有限アルファベットとする．多元接続通信路（multiple access channel）とは，入力の対 $(𝑥 1, 𝑥 2) \in X 1 \times X 2$ ごとに $Y$ 上の分布 $𝑊 (\cdot ∣ 𝑥 1, 𝑥 2)$ を与える対応である．すなわち $𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2) \geq 0$ であって，各対について $\sum 𝑦 \in Y 𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2) = 1$ を満たす．長さ $𝑛$ の入力の組 $𝑥 𝑛 1 = (𝑥 1, 0, \dots, 𝑥 1, 𝑛 - 1)$ ， $𝑥 𝑛 2 = (𝑥 2, 0, \dots, 𝑥 2, 𝑛 - 1)$ に対する出力の分布を

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

で定める．

第6章定義 6.1.1 との違いは，条件に置く入力が 1 文字から対になったことだけである．積の形の条件が言っていることも同じで，各時刻の雑音がそれ以前の入出力に一切依存しない，すなわち通信路に記憶がない，ということである．違いは通信路の側ではなく，使う側にある．入力の対 $(𝑥 1, 𝑥 2)$ を選ぶ主体が 2 人に分かれていて，しかも互いの選んだものを見られないので，対を好きなように指定することはできない．

形式化: MACChannel (ソース)

定義 14.1.2（多元接続符号）. $𝑊$ を多元接続通信路（定義 14.1.1）とし， $𝑛 \geq 1$ とする．長さ $𝑛$ の 多元接続符号 とは，メッセージ数 $𝑀 1 \geq 1$ ， $𝑀 2 \geq 1$ と，符号化写像 $𝑐 1 : {1, \dots, 𝑀 1} \to X 𝑛 1$ ， $𝑐 2 : {1, \dots, 𝑀 2} \to X 𝑛 2$ ，および 共同復号器 $𝑑 : Y 𝑛 \to {1, \dots, 𝑀 1} \times {1, \dots, 𝑀 2}$ の組である．メッセージの対 $(𝑚 1, 𝑚 2)$ を送ったときの 誤り確率 と，対について平均した 平均誤り確率 を

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

で定める．

第6章定義 6.2.1 のブロック通信路符号を 2 人に広げた形だが，広げ方は左右で対称ではない．符号化は 2 本に分かれる．利用者 1 は自分のメッセージ $𝑚 1$ だけを見て $𝑐 1 (𝑚 1)$ を送り，相手のメッセージも相手の符号語も見ない．いっぽう復号は 1 本のままで，受け手は混ざった出力 $𝑦 𝑛$ から対を一度に言い当てる．誤りも対について数えるので，どちらか一方でも当たらなければ誤りである．この非対称さが，2 人ぶんのメッセージを 1 つの出力列から取り出すという問題の形をそのまま写している．

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

定義 14.1.3（達成可能なレート対）. $𝑊$ を多元接続通信路（定義 14.1.1）とする．実数の対 $(𝑅 1, 𝑅 2)$ が 達成可能 であるとは，任意の $𝜁 > 0$ に対してある $𝑁 \geq 1$ があって， $𝑁 \leq 𝑛$ を満たすすべての $𝑛$ について，長さ $𝑛$ の多元接続符号（定義 14.1.2）で

1 𝑛 l o g 𝑀 1 \geq 𝑅 1, 1 𝑛 l o g 𝑀 2 \geq 𝑅 2, ¯ 𝑃 𝑒 < 𝜁

を満たすものが存在することをいう．

第6章定義 6.2.2 と同じ「達成可能」という語を使うが，形は二つの点で違う．あちらは最大誤り確率で書かれていて，こちらは平均誤り確率である．また，あちらは符号の族に対して達成可能かどうかを定め，その族の下極限を達成レートと呼んだのに対し，こちらはレートの対そのものに対して定めている．第6章 6.3 節は，平均誤り確率の小さい符号からメッセージを半分捨てて最大誤り確率の小さい符号を作る段（補題 6.3.6）を用意していた．2 人の場合に対応する段を，本書は扱わない．

形式化: MACAchievable (ソース)

五角形

2 人の取り分を抑える量を作りたい．第6章では入力分布 $𝑝$ を与えると相互情報量 $𝐼 (𝑝; 𝑊)$ が定まり，それが 1 人ぶんの取り分の限界になった．2 人の場合は入力分布も 2 つあり，しかも現れる情報量が 3 つになる．そのうち 2 つには，見た目の違う二通りの書き方があって，入力が独立なら一致する．以下で使うのは条件付きの形のほうだが，二通りが一致することを先に確かめておく．

命題 14.1.4. $𝑊$ を多元接続通信路（定義 14.1.1）とし， $𝑝 1$ を $X 1$ 上の分布， $𝑝 2$ を $X 2$ 上の分布とする．三つ組 $(𝑋 1, 𝑋 2, 𝑌)$ を，同時分布が $𝑝 1 (𝑥 1) 𝑝 2 (𝑥 2) 𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2)$ であるような確率変数の組とする（すなわち $𝑋 1$ と $𝑋 2$ は独立にそれぞれ $𝑝 1$ ， $𝑝 2$ に従い， $𝑌$ は入力の対 $(𝑋 1, 𝑋 2)$ に対して $𝑊$ が返す出力である）．このとき

𝐼 (𝑋 1; (𝑋 2, 𝑌)) = 𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2), 𝐼 (𝑋 2; (𝑋 1, 𝑌)) = 𝐼 (𝑋 2; 𝑌 ∣ 𝑋 1) .

証明. 第 1 の等式を示す．第 2 は添字の 1 と 2 を入れ替えれば同じ論法である．命題 1.3.3 の対称性より $𝐼 (𝑋 1; (𝑋 2, 𝑌)) = 𝐼 ((𝑋 2, 𝑌); 𝑋 1)$ であり，対 $(𝑋 2, 𝑌)$ から $𝑋 2$ を先に取り出すチェイン則（定理 1.5.1）で

𝐼 ((𝑋 2, 𝑌); 𝑋 1) = 𝐼 (𝑋 2; 𝑋 1) + 𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2)

を得る（右辺の第 2 項は命題 1.4.2 の対称性で向きをそろえた）．同時分布の作り方から $𝑋 1$ と $𝑋 2$ は独立なので，命題 1.3.2 の等号条件より第 1 項は $0$ である． $◼$

形式化: 利用者 1 について macJoint_mutualInfo_eq_condMutualInfo₁，利用者 2 について macJoint_mutualInfo_eq_condMutualInfo₂ (ソース)

左辺と右辺は問いとしては別物である．右辺は「相手の入力を知っている受け手にとって，こちらの入力が出力について持つ情報」であり，左辺は「相手の入力と出力をまとめて渡されたときに，こちらの入力について分かる情報」である．入力が独立なら相手の入力それ自体はこちらについて何も語らないので，まとめて渡されても増える分は出力からの分だけになり，二つが一致する．

定義 14.1.5（五角形）. $𝑊$ ， $𝑝 1$ ， $𝑝 2$ と三つ組 $(𝑋 1, 𝑋 2, 𝑌)$ を命題 14.1.4 のとおりとする．五角形 $P (𝑝 1, 𝑝 2)$ を，

0 \leq 𝑅 1, 0 \leq 𝑅 2, 𝑅 1 \leq 𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2), 𝑅 2 \leq 𝐼 (𝑋 2; 𝑌 ∣ 𝑋 1), 𝑅 1 + 𝑅 2 \leq 𝐼 ((𝑋 1, 𝑋 2); 𝑌)

の五つをすべて満たす実数の対 $(𝑅 1, 𝑅 2)$ の集合として定める．

三つの上界はそれぞれ別のことを言っている． $𝑅 1 \leq 𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2)$ は，相手の入力を教えてもらえたとしても，利用者 1 が 1 回の使用で運べるのはこれだけだ，という意味である．相手の入力が分かっている受け手は，残る雑音だけを相手にすればよいので，これが 1 人ぶんの取り分としてはいちばん甘い評価になる． $𝑅 1 + 𝑅 2 \leq 𝐼 ((𝑋 1, 𝑋 2); 𝑌)$ は逆に，2 人が示し合わせて 1 人のように送ったとしても，出力から取り出せる合計はこれだけだ，という意味である．名前は五つの不等式が平面から切り取る形から来ている．量のとり方によっては辺が潰れて五角形に見えないこともあるが，呼び名はこのままにする．

形式化: macPentagon (ソース)

形式化上の注記. 形式化の五角形の三つの枠は， $𝐼 (𝑋 1; (𝑋 2, 𝑌))$ ， $𝐼 (𝑋 2; (𝑋 1, 𝑌))$ ， $𝐼 ((𝑋 1, 𝑋 2); 𝑌)$ を周辺分布のエントロピーの差の形で書いた macInfo₁，macInfo₂，macInfoBoth (InformationTheory/Shannon/MultipleAccess/Achievability/Codebook.lean) である．独立な入力のもとで前の二つが本文の条件付きの形と一致することは，命題 14.1.4 が述べているとおりである．三つがそれぞれ本文の三つの枠に等しいことは，形式化の側にも macInfo₁_eq_condMutualInfo_toReal，macInfo₂_eq_condMutualInfo_toReal，macInfoBoth_eq_mutualInfo_toReal (InformationTheory/Shannon/MultipleAccess/Reconciliation.lean) として置かれている．集合としては同じでも，宣言としては別の式である．以下で五角形を名指す宣言は，どれもこの三つの量で書かれている．

例 14.1.6（二元加算多元接続通信路）. $X 1 = X 2 = {0, 1}$ ， $Y = {0, 1, 2}$ とし， $𝑊$ を，入力の和が確率 $1$ で出力になる通信路，すなわち $𝑊 (𝑥 1 + 𝑥 2 ∣ 𝑥 1, 𝑥 2) = 1$ であり， $𝑦 \neq 𝑥 1 + 𝑥 2$ では $𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2) = 0$ であるものとする．入力分布はどちらも一様，すなわち $𝑝 1 (0) = 𝑝 1 (1) = 𝑝 2 (0) = 𝑝 2 (1) = 1 / 2$ にとる．このとき命題 14.1.4 の三つ組について

𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2) = 𝐼 (𝑋 2; 𝑌 ∣ 𝑋 1) = 1, 𝐼 ((𝑋 1, 𝑋 2); 𝑌) = 32

である．五角形 $P (𝑝 1, 𝑝 2)$ で定義 14.1.5 の五つの不等式のうち二つが同時に等号になる点は， $(0, 0)$ ， $(1, 0)$ ， $(0, 1)$ ， $(1, 12)$ ， $(12, 1)$ の五つである．最後の二つが折れ点である．

証明. 条件付きの二つは添字の入れ替えで移り合うので，第 1 のものを計算する．エントロピーの差の形（定理 1.4.3）で $𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2) = 𝐻 (𝑋 1 ∣ 𝑋 2) - 𝐻 (𝑋 1 ∣ 𝑋 2, 𝑌)$ である．第 1 項を見る． $𝑋 1$ と $𝑋 2$ は独立だから，各 $𝑥 2$ のもとでの $𝑋 1$ の条件付き分布は $𝑝 1$ そのもので，これは一様だから例 1.1.3 より $𝐻 (𝑋 1 ∣ 𝑋 2 = 𝑥 2) = l o g 2 = 1$ である．定義 1.2.2 はこれを $𝑥 2$ について平均したものだから $𝐻 (𝑋 1 ∣ 𝑋 2) = 1$ である．第 2 項を見る．確率が正である対 $(𝑥 2, 𝑦)$ を固定すると $𝑥 1 = 𝑦 - 𝑥 2$ に決まるので，条件付き分布は 1 点に集中しており，そのエントロピーは定義 1.1.1 より $0$ である．平均しても $0$ だから $𝐻 (𝑋 1 ∣ 𝑋 2, 𝑌) = 0$ で，差は $1$ である．

和のほうに移る．定理 1.3.4 の $𝐼 (𝑋; 𝑌) = 𝐻 (𝑌) - 𝐻 (𝑌 ∣ 𝑋)$ を，対 $(𝑋 1, 𝑋 2)$ を 1 つの変数とみなして当てると $𝐼 ((𝑋 1, 𝑋 2); 𝑌) = 𝐻 (𝑌) - 𝐻 (𝑌 ∣ 𝑋 1, 𝑋 2)$ である． $𝑌 = 𝑋 1 + 𝑋 2$ は入力の対で決まるので，第 2 項は上と同じ理由で $0$ である．第 1 項は， $𝑋 1$ と $𝑋 2$ が独立な一様分布だから $𝑌$ が $0$ ， $1$ ， $2$ をそれぞれ確率 $1 / 4$ ， $1 / 2$ ， $1 / 4$ でとることと，定義 1.1.1 から

𝐻 (𝑌) = 14 l o g 4 + 12 l o g 2 + 14 l o g 4 = 32

である．

最後に形を見る．三つの枠が $1$ ， $1$ ， $3 / 2$ だから，定義 14.1.5 の五つの条件は $0 \leq 𝑅 1$ ， $0 \leq 𝑅 2$ ， $𝑅 1 \leq 1$ ， $𝑅 2 \leq 1$ ， $𝑅 1 + 𝑅 2 \leq 3 / 2$ である．このうち二つが同時に等号になる点を拾うと $(0, 0)$ ， $(1, 0)$ ， $(0, 1)$ ， $(1, 12)$ ， $(12, 1)$ の五つが残る．残りの組み合わせは，二つの等式が両立しないか（ $𝑅 1 = 0$ と $𝑅 1 = 1$ など），決まる点が残りの不等式を破る（ $𝑅 1 = 0$ と $𝑅 1 + 𝑅 2 = 3 / 2$ から $𝑅 2 = 3 / 2$ が出て $𝑅 2 \leq 1$ を破る， $𝑅 1 = 𝑅 2 = 1$ が $𝑅 1 + 𝑅 2 \leq 3 / 2$ を破る，など）．最後の二点が折れ点で， $𝑅 1 = 1$ のとき $𝑅 2$ は $1 / 2$ まで， $𝑅 2 = 1$ のとき $𝑅 1$ は $1 / 2$ までとれることを言っている． $◼$

合計の上限 $3 / 2$ が，1 人あたりの上限 $1$ の 2 倍に届いていない．届かない理由は受け手の側にある． $𝑌 = 1$ を受け取ったとき，送られた対が $(0, 1)$ だったのか $(1, 0)$ だったのかは区別できない．和の枠が $1$ の 2 倍に届かないのは，この取り違えのぶんである．片方の枠を $1$ にとるともう片方の枠が $1 / 2$ までに切り詰められる，という取り引きの形が折れ点に出ている．

この通信路では出力が入力の対で決まってしまうので， $𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2)$ には値が $0$ の組がある．次に借りる 多元接続通信路の達成可能性 は，どの入力の対からもどの出力が正の確率で出ることを求めるので，この例はその条件を満たさない．全点で正であることは借りる主張の側に付いている条件であって，定義 14.1.5 の五角形にも定義 14.1.3 の達成可能性にも現れない．だから，この例では五角形の内側が達成できない，と言っているのではない．達成できるかどうかを本書も形式化も述べていない，ということである．ここでは五角形の形を見るための例として置いている．全点で正な通信路で同じ計算をやり直したものが，次節の例 14.2.7 である．

達成可能性

道具を一つ借りる．多元接続通信路の達成可能性，すなわち「五角形の内側のレート対は実際に達成できる」という主張である．使う形を書いておく．

$𝑊$ ， $𝑝 1$ ， $𝑝 2$ と三つ組 $(𝑋 1, 𝑋 2, 𝑌)$ を命題 14.1.4 のとおりとし， $𝑝 1$ ， $𝑝 2$ ， $𝑊$ がどれも全点で正，すなわち $𝑝 1 (𝑥 1) > 0$ ， $𝑝 2 (𝑥 2) > 0$ ， $𝑊 (𝑦 ∣ 𝑥 1, 𝑥 2) > 0$ がすべての $𝑥 1 \in X 1$ ， $𝑥 2 \in X 2$ ， $𝑦 \in Y$ で成り立つとする．実数の対 $(𝑅 1, 𝑅 2)$ が $0 < 𝑅 1$ ， $0 < 𝑅 2$ と

𝑅 1 < 𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2), 𝑅 2 < 𝐼 (𝑋 2; 𝑌 ∣ 𝑋 1), 𝑅 1 + 𝑅 2 < 𝐼 ((𝑋 1, 𝑋 2); 𝑌)

を満たすならば， $(𝑅 1, 𝑅 2)$ は定義 14.1.3 の意味で達成可能である．

当てる対象は定義 14.1.1 の多元接続通信路と定義 14.1.2 の多元接続符号だけで，依存するのは 14.2 節の冒頭の地の文と，14.2 節が借りる 五角形の包含 および 14.3 節が借りる Slepian–Wolf の達成可能性 の筋書きである．本書の証明がこの主張を直に引く箇所はない．

借りたままにするので，中で何が起きているかの筋書きだけ書いておく．第6章 6.3 節のランダム符号化を，符号帳 2 本に置き換える．利用者 1 の $𝑀 1$ 本の符号語を $𝑝 1$ の $𝑛$ 重積から，利用者 2 の $𝑀 2$ 本を $𝑝 2$ の $𝑛$ 重積から，それぞれ独立に引く．復号器は，受け取った $𝑦 𝑛$ に対して，三つ組 $(𝑐 1 (𝑚 1), 𝑐 2 (𝑚 2), 𝑦 𝑛)$ が結合典型（第6章定義 6.2.3 を三つ組に広げたもの）になる対 $(𝑚 1, 𝑚 2)$ を探し，ちょうど 1 つあればそれを答える．誤りの起こり方が第6章と違って 3 種類に分かれる．利用者 1 のメッセージだけを取り違える，利用者 2 のだけを取り違える，両方を取り違える，の三つで，取り違えた側の符号語は $𝑦 𝑛$ と無関係に引かれているから，第6章定理 6.2.7 にあたる評価がそれぞれ $2 - 𝑛 𝐼 (𝑋 1; 𝑌 ∣ 𝑋 2)$ ， $2 - 𝑛 𝐼 (𝑋 2; 𝑌 ∣ 𝑋 1)$ ， $2 - 𝑛 𝐼 ((𝑋 1, 𝑋 2); 𝑌)$ ほどになる．これに取り違え先の本数を掛けたものが $0$ に向かう条件が，三つの不等式そのものである．三つの不等式が別々に要るのは，潰すべき誤りが 3 種類あるからだ，と読める．

本書はこの主張を証明しない．3 種の誤りの勘定は，どの符号語が $𝑦 𝑛$ と無関係かが種類ごとに違うので，第6章定理 6.2.7 をそのまま当てるのではなく，独立性の使い分けに応じて三通りに作り直すことになる．そのうえ，2 本の符号帳についての平均から良い 1 組を取り出す段が要る．第6章 6.3 節が 1 本の符号帳について行ったことの 2 本版だが，本書はその形を用意していない．「本書で証明しない」ことと「形式化されていない」ことは別である．本章が借りる情報理論の主張は，これも含めてどれも，本書が証明を載せないだけで，無条件の機械検証済みの定理として形式化されている．以下の借用ではこの断りを繰り返さない．本章が扱う設定のうち，達成可能性が本書にも形式化にも無いものが一つだけあって，14.8 節がその場で断る．

形式化: mac_strict_interior_achievable (ソース)

形式化上の注記. 形式化の宣言の仮定は，借りた主張の仮定と一つずつ対応している．三つの全点で正であること，二つのレートが正であること，三つの不等式の，合わせて八つで，これがすべてである．結論も定義 14.1.3 の達成可能性そのものである．

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