多重アクセス通信路(multiple access channel)とは、複数の送信者がそれぞれ独立なメッセージを同時に 1 つの通信路へ入力し、1 人の受信者が出力から全員のメッセージを推定する通信の模型である。2 送信者の離散無記憶な場合、平均の誤りの確率を $0$ に近づけられる速さの組の閉包(容量領域)は、独立な入力の分布ごとの五角形 $R_1\le I(X_1;Y\mid X_2)$、$R_2\le I(X_2;Y\mid X_1)$、$R_1+R_2\le I(X_1,X_2;Y)$ の和集合の凸包に等しい。達成は無作為な符号と時分割で、逆は Fano の不等式で示される。2 元加算通信路では和の速さが $\frac32$ bit になる。
前提知識: 相互情報量, 情報理論, Shannonの通信路符号化定理
多重アクセス通信路(multiple access channel)は、2 人以上の送信者がそれぞれ独立なメッセージを同時に 1 つの通信路に入力し、1 人の受信者が出力から全員のメッセージを推定する通信の模型である。1 本の電話線や無線の周波数を複数の利用者が共有する状況を表す。送信者の数が 2 のとき、誤りの確率を $0$ に近づけられる速さの組 $(R_1,R_2)$ の全体(容量領域)は、独立な入力の分布ごとに決まる五角形
$$
R_1\le I(X_1;Y\mid X_2),\qquad R_2\le I(X_2;Y\mid X_1),\qquad R_1+R_2\le I(X_1,X_2;Y)
$$
の和集合の凸包に等しい。この形の容量領域は R. Ahlswede が 1971 年に与えた(AC02 の要旨と §1 による)。
この記事では、2 送信者の離散無記憶な多重アクセス通信路を定義し、容量領域の定理を、無作為な符号による達成と Fano の不等式による逆の両方について完全に証明する。続いて、角の点と逐次復号の読み方、2 元加算通信路で和の速さが時分割の $1$ bit を超えて $\frac32$ bit になること、Gauss の多重アクセス通信路の式を述べ、仮定を外すと何が成り立たなくなるかを表にする。以下 $\log$ は 2 を底とし、情報量の単位は bit とする。
有限集合 $\mathcal X_1,\mathcal X_2$(2 人の送信者の入力)と $\mathcal Y$(出力)と、$W(y\mid x_1,x_2)\ge0$、$\sum_yW(y\mid x_1,x_2)=1$ を満たす数の族 $W$ の組を、2 送信者の 多重アクセス通信路 という。$n$ 回使うときは無記憶とし、入力の列 $x_1^n,x_2^n$ から出力の列 $y^n$ が確率
$$
W^n(y^n\mid x_1^n,x_2^n):=\prod_{i=1}^nW(y_i\mid x_{1i},x_{2i})
$$
で出るとする。
正の整数 $M_1,M_2$ と長さ $n$ の 符号 とは、符号化の写像 $F_1\colon\{1,\dots,M_1\}\to\mathcal X_1^n$、$F_2\colon\{1,\dots,M_2\}\to\mathcal X_2^n$ と復号の写像 $g\colon\mathcal Y^n\to\{1,\dots,M_1\}\times\{1,\dots,M_2\}$ の組である。メッセージ $U_1,U_2$ を互いに独立で一様に分布するものとし、$F_1(U_1),F_2(U_2)$ を入力して出力 $Y^n$ を得たときの
$$
P_e:=P\bigl(g(Y^n)\ne(U_1,U_2)\bigr)
$$
を(平均の)誤りの確率 という。$R_1,R_2\ge0$ の組 $(R_1,R_2)$ が 達成可能 であるとは、各 $n\ge1$ について $M_j\ge2^{nR_j}$($j=1,2$)の長さ $n$ の符号がとれ、その誤りの確率が $n\to\infty$ で $0$ に近づくことをいう。達成可能な組の全体の閉包を 容量領域 といい、$\mathcal C$ と書く。
送信者 1 は $U_1$ だけを、送信者 2 は $U_2$ だけを知り、互いに相談しない。この記事では平均の誤りの確率で達成可能性を定める。
入力の分布の組 $p=(p_1,p_2)$($p_j$ は $\mathcal X_j$ 上の確率分布)に対し、$X_1\sim p_1$ と $X_2\sim p_2$ を独立にとり、$P(Y=y\mid X_1=x_1,X_2=x_2)=W(y\mid x_1,x_2)$ で $Y$ を定める。条件付き相互情報量 $I(X_1;Y\mid X_2)$ は 相互情報量 の定義「条件付き相互情報量」による。
$$
a(p):=I(X_1;Y\mid X_2),\qquad b(p):=I(X_2;Y\mid X_1),\qquad c(p):=I(X_1,X_2;Y)
$$
とおき、
$$
\mathcal P(p):=\bigl\{(R_1,R_2)\bigm|R_1,R_2\ge0,\ R_1\le a(p),\ R_2\le b(p),\ R_1+R_2\le c(p)\bigr\}
$$
を $p$ の定める 五角形 という。
$X_1$ と $X_2$ が独立なとき $\max(a,b)\le c\le a+b$ であり、$c-a=I(X_2;Y)$、$c-b=I(X_1;Y)$ である。$\mathcal P(p)$ は 5 点 $(0,0)$、$(a,0)$、$(a,c-a)$、$(c-b,b)$、$(0,b)$ の凸包である。
相互情報量の連鎖律(相互情報量 の定理「連鎖律」)から $c=I(X_2;Y)+I(X_1;Y\mid X_2)=I(X_2;Y)+a\ge a$ で、同様に $c=I(X_1;Y)+b\ge b$ である。また連鎖律を 2 通りに使うと $I(X_2;X_1,Y)=I(X_2;X_1)+I(X_2;Y\mid X_1)=I(X_2;Y)+I(X_2;X_1\mid Y)$ で、独立性から $I(X_2;X_1)=0$ なので $b\ge I(X_2;Y)=c-a$、すなわち $c\le a+b$ である。$\mathcal P(p)$ は有界な閉凸集合なので、その端点の凸包に等しい(Krein–Milmanの定理。平面の多角形なら直接にも分かる)。端点では、5 本の境界の直線 $R_1=0$、$R_2=0$、$R_1=a$、$R_2=b$、$R_1+R_2=c$ のうち傾きの違う 2 本が交わる。そのような交点で $\mathcal P(p)$ に入るものは、$\max(a,b)\le c\le a+b$ を使うと上の 5 点のどれかになる(たとえば $R_1=a$ と $R_2=b$ の交点が入るのは $c=a+b$ のときで、そのとき $(a,c-a)$ に一致する)。$\square$
2 送信者の離散無記憶な多重アクセス通信路の容量領域は
$$
\mathcal C=\operatorname{conv}\Bigl(\bigcup_{p}\mathcal P(p)\Bigr)
$$
である。ここで $p=(p_1,p_2)$ は入力の分布の組の全体を動き、$\operatorname{conv}$ は凸包を表す。
「$\supset$」は節「達成」の prop-mac-pentagon-achieve と lem-mac-timeshare で、「$\subset$」は節「逆」の prf-mac-converse で証明する。
右辺は閉集合である。実際、$a,b,c$ は $p$ の連続関数で、$p$ の動く範囲(2 つの確率単体の積)はコンパクトなので、$\bigcup_p\mathcal P(p)$ は有界な閉集合(コンパクト集合の連続な像の射影)であり、平面のコンパクト集合の凸包は、Carathéodoryの定理(凸幾何) により 3 点とその重みの組の連続な像として表せるのでコンパクトである。
和集合だけでなく凸包をとるのは、時間を分けて 2 つの符号を使い分けられるからである(下の lem-mac-timeshare)。送信者が 1 人のときは五角形が線分 $[0,I(X_1;Y)]$ になり、定理は Shannonの通信路符号化定理 の容量 $\max_{p_1}I(X_1;Y)$ に戻る。
有限集合の入出力をもつ通信路 $V(b\mid a_1,a_2)$ と入力の分布 $\pi_1,\pi_2$ を考える(下では $V:=W^n$、$\pi_j:=p_j^n$ として使う)。$(A_1,A_2,B)$ の分布を $\pi_1(a_1)\pi_2(a_2)V(b\mid a_1,a_2)$ とし、
$$
q(b\mid a_2):=\sum_{a_1}\pi_1(a_1)V(b\mid a_1,a_2),\quad q(b\mid a_1):=\sum_{a_2}\pi_2(a_2)V(b\mid a_1,a_2),\quad q(b):=\sum_{a_1,a_2}\pi_1(a_1)\pi_2(a_2)V(b\mid a_1,a_2)
$$
とおく。$\pi_1\pi_2V>0$ となる $(a_1,a_2,b)$ で次の 情報密度 を定める。
$$
\imath_1:=\log\frac{V(b\mid a_1,a_2)}{q(b\mid a_2)},\qquad\imath_2:=\log\frac{V(b\mid a_1,a_2)}{q(b\mid a_1)},\qquad\imath_{12}:=\log\frac{V(b\mid a_1,a_2)}{q(b)}
$$
正の整数 $M_1,M_2$ と実数 $\tau$ に対し、$\pi_1\pi_2V>0$ となる $(a_1,a_2,b)$ のうち、次を満たすものの集合を $\mathcal A$ とする:$M_1\ge2$ なら $\imath_1>\log M_1+\tau$、$M_2\ge2$ なら $\imath_2>\log M_2+\tau$、$M_1,M_2\ge2$ なら $\imath_{12}>\log(M_1M_2)+\tau$。このとき、$V$ を 1 回使う符号で、誤りの確率が
$$
P\bigl((A_1,A_2,B)\notin\mathcal A\bigr)+3\cdot2^{-\tau}
$$
以下のものがある。
1. 符号の作り方。 符号語 $\alpha_1(m_1)$($m_1\le M_1$)を分布 $\pi_1$ から、$\alpha_2(m_2)$($m_2\le M_2$)を分布 $\pi_2$ から、すべて互いに独立に選ぶ。復号器は、出力 $b$ に対し $(\alpha_1(m_1),\alpha_2(m_2),b)\in\mathcal A$ となる $(m_1,m_2)$ がちょうど 1 つならそれを返し、そうでなければ $(1,1)$ を返す。
2. 1 つのメッセージの組に帰着する。 どの組 $(m_1,m_2)$ を送っても、誤るなら下の 4 つの事象($1$ を $m_1,m_2$ に読み替えたもの)のどれかが起こり、その確率は番号の付け替えで変わらない。よって $(U_1,U_2)=(1,1)$ を送った場合に 4 つの事象の確率を抑えれば足りる。このとき $(\alpha_1(1),\alpha_2(1),B)$ の分布は $(A_1,A_2,B)$ と同じである。誤るなら、$(\alpha_1(1),\alpha_2(1),B)\notin\mathcal A$ であるか、次のどれかが起こる。(a) ある $m_1\ne1$ で $(\alpha_1(m_1),\alpha_2(1),B)\in\mathcal A$。(b) ある $m_2\ne1$ で $(\alpha_1(1),\alpha_2(m_2),B)\in\mathcal A$。(c) ある $m_1\ne1$、$m_2\ne1$ で $(\alpha_1(m_1),\alpha_2(m_2),B)\in\mathcal A$。
3. (a) の確率。 (a) が起こりうるのは $M_1\ge2$ のときで、そのとき $\mathcal A$ では $V>2^{\tau}M_1\,q(b\mid a_2)$ である。$m_1\ne1$ を固定すると、$\alpha_1(m_1)$ は $(\alpha_2(1),B)$ と独立で分布 $\pi_1$ に従い、$(\alpha_2(1),B)$ の分布は $\pi_2(a_2)q(b\mid a_2)$ である。よって
$$
P\bigl((\alpha_1(m_1),\alpha_2(1),B)\in\mathcal A\bigr)\le\sum_{a_1,a_2,b}\pi_1(a_1)\pi_2(a_2)q(b\mid a_2)\frac{V(b\mid a_1,a_2)}{2^\tau M_1q(b\mid a_2)}=\frac{2^{-\tau}}{M_1}
$$
で、$M_1-1$ 個の $m_1$ について足すと (a) の確率は $2^{-\tau}$ 以下である。
4. (b) と (c) の確率。 (b) は送信者を入れ替えて同じく $2^{-\tau}$ 以下である。(c) では $M_1,M_2\ge2$ で、$(\alpha_1(m_1),\alpha_2(m_2))$ は $B$ と独立に分布 $\pi_1\pi_2$ に従い、$B$ の分布は $q$ である。$\mathcal A$ では $V>2^\tau M_1M_2\,q(b)$ なので、段 3 と同じ計算で 1 組あたり $2^{-\tau}/(M_1M_2)$ 以下、全体で $2^{-\tau}$ 以下である。
5. 以上から期待値は主張の値以下で、それ以下の誤りの確率をもつ符号語の選び方がある。$\square$
どの入力の分布の組 $p$ についても $\mathcal P(p)\subset\mathcal C$ である。
$(R_1,R_2)\in\mathcal P(p)$ と $\varepsilon>0$ をとり、$R_j':=\max(R_j-\varepsilon,0)$、$M_j:=2^{\lceil nR_j'\rceil}$ とおく。$M_j\ge2^{nR_j'}$ である。lem-mac-oneshot を $V:=W^n$、$\pi_j:=p_j^n$($p_j$ の $n$ 個の積)、$\tau:=n\varepsilon/4$ に使う。
$\pi_1$ が積の形なので $q(y^n\mid x_2^n)=\prod_iq(y_i\mid x_{2i})$ となり(1 回分の $q$ を同じ記号で書く)、
$$
\imath_1=\sum_{i=1}^n\log\frac{W(Y_i\mid X_{1i},X_{2i})}{q(Y_i\mid X_{2i})}
$$
は互いに独立で同じ分布に従う有限個の値の確率変数の和である($(X_{1i},X_{2i},Y_i)$ は独立に分布 $p_1p_2W$ に従う)。$q(y\mid x_2)=P(Y=y\mid X_2=x_2)$ なので各項の期待値は $H(Y\mid X_2)-H(Y\mid X_1,X_2)=a(p)$ であり、大数の法則 の大数の弱法則により $P(\imath_1\le n(a-\frac\varepsilon2))\to0$ である。$M_1\ge2$ なら $R_1'=R_1-\varepsilon\le a-\varepsilon$ なので、$n\ge4/\varepsilon$ では
$$
\log M_1+\tau\le n(a-\varepsilon)+1+\frac{n\varepsilon}4\le n\Bigl(a-\frac\varepsilon2\Bigr)
$$
で、$P(\imath_1\le\log M_1+\tau)\to0$ である。$\imath_2$ も同じである。$M_1,M_2\ge2$ なら $R_1'+R_2'=R_1+R_2-2\varepsilon\le c-2\varepsilon$ で、$\imath_{12}$ の各項の期待値は $c(p)$ なので同じく $P(\imath_{12}\le\log(M_1M_2)+\tau)\to0$ である。よって補題の上界は $0$ に近づき、$(R_1',R_2')$ は達成可能である。$\varepsilon\to0$ とすれば $(R_1,R_2)\in\mathcal C$ である。$\square$
$\mathcal C$ は凸集合である。
$r=(R_1,R_2)$、$r'=(R_1',R_2')$ を達成可能とし、$0< \lambda< 1$、$\varepsilon>0$ とする。各 $n$ で $n_1:=\lfloor\lambda n\rfloor$、$n_2:=n-n_1$ とおき、$r$ を達成する列の長さ $n_1$ の符号と、$r'$ を達成する列の長さ $n_2$ の符号を前後に並べる。送信者 1 のメッセージは 2 つの符号のメッセージの組で、個数は $2^{n_1R_1+n_2R_1'}$ 以上である。$n_1R_1+n_2R_1'\ge n(\lambda R_1+(1-\lambda)R_1')-\lvert R_1-R_1'\rvert$ なので、$n\varepsilon\ge\lvert R_1-R_1'\rvert$ なら個数は $2^{n(\lambda R_1+(1-\lambda)R_1'-\varepsilon)}$ 以上である。送信者 2 も同じである。
組のメッセージは一様なら成分ごとに独立で一様であり、通信路は無記憶なので、前半の出力の分布は前半の入力だけで決まる。受信者は前半と後半を別々に復号し、和の上界により誤りの確率は 2 つの符号の誤りの確率の和以下で、$n_1,n_2\to\infty$ とともに $0$ に近づく。よって $(\lambda r+(1-\lambda)r'-\varepsilon(1,1))$ の各成分を $0$ 以上に切り詰めた点は達成可能で、$\varepsilon\to0$ として $\lambda r+(1-\lambda)r'\in\mathcal C$ である。$\mathcal C$ の点は達成可能な点の極限なので、$\mathcal C$ の 2 点の凸結合も $\mathcal C$ に入る。$\square$
prop-mac-pentagon-achieve と lem-mac-timeshare から、thm-mac-main の「$\supset$」が従う。
$p^{(1)},\dots,p^{(n)}$ を入力の分布の組とし、$\bar a:=\frac1n\sum_ia(p^{(i)})$、$\bar b$、$\bar c$ も同様に定める。このとき
$$
\bar{\mathcal P}:=\{R_1,R_2\ge0,\ R_1\le\bar a,\ R_2\le\bar b,\ R_1+R_2\le\bar c\}\subset\operatorname{conv}\Bigl(\bigcup_p\mathcal P(p)\Bigr)
$$
である。
prop-mac-shape の不等式 $\max(a,b)\le c\le a+b$ は平均をとっても保たれるので、$\bar{\mathcal P}$ は 5 点 $(0,0)$、$(\bar a,0)$、$(\bar a,\bar c-\bar a)$、$(\bar c-\bar b,\bar b)$、$(0,\bar b)$ の凸包である。各点は、$\mathcal P(p^{(i)})$ の対応する頂点の $i$ についての平均であり(頂点の座標は $a,b,c$ の 1 次式)、したがって $\bigcup_i\mathcal P(p^{(i)})$ の点の凸結合である。凸包の凸結合は凸包に入る。$\square$
$(R_1,R_2)$ を達成する符号の列をとり、長さ $n$ の符号の誤りの確率を $P_e^{(n)}$ とする。$X_j^n:=F_j(U_j)$ とし、$r_j:=\frac1n\log M_j\ge R_j$ とおく。
1. Fano の不等式。 情報理論 の定理「Fano の不等式」を底 2 で $(U_1,U_2)$ とその推定 $g(Y^n)$ に使い、同記事の補題「関数で条件を粗くするとエントロピーは減らない」を合わせると
$$
H(U_1,U_2\mid Y^n)\le1+P_e^{(n)}\log(M_1M_2)=:n\varepsilon_n
$$
である($M_1M_2=1$ なら左辺は $0$)。
2. 和の速さ。 $(U_1,U_2)$ を与えると $Y_1,\dots,Y_n$ は独立で、$Y_i$ の分布は $W(\cdot\mid X_{1i},X_{2i})$ である。$\psi(x_1,x_2)$ を $W(\cdot\mid x_1,x_2)$ のエントロピーとすると $H(Y^n\mid U_1,U_2)=\sum_iE[\psi(X_{1i},X_{2i})]=\sum_iH(Y_i\mid X_{1i},X_{2i})$ である(情報理論 の定理「通信路符号化定理の逆」の証明の段 3・4 と同じ計算)。劣加法性 $H(Y^n)\le\sum_iH(Y_i)$ と合わせて
$$
\log(M_1M_2)=H(U_1,U_2)=I(U_1,U_2;Y^n)+H(U_1,U_2\mid Y^n)\le\sum_{i=1}^nI(X_{1i},X_{2i};Y_i)+n\varepsilon_n
$$
である。
3. 一方の速さ。 $U_1$ と $U_2$ は独立なので $\log M_1=H(U_1\mid U_2)=I(U_1;Y^n\mid U_2)+H(U_1\mid Y^n,U_2)$ で、第 2 項は $H(U_1,U_2\mid Y^n)\le n\varepsilon_n$ 以下である。条件を増やすとエントロピーは増えず、$X_{2i}$ は $U_2$ の関数なので
$$
H(Y^n\mid U_2)\le\sum_iH(Y_i\mid U_2)\le\sum_iH(Y_i\mid X_{2i})
$$
であり、段 2 と同じく $H(Y^n\mid U_1,U_2)=\sum_iH(Y_i\mid X_{1i},X_{2i})$ なので、$\log M_1\le\sum_iI(X_{1i};Y_i\mid X_{2i})+n\varepsilon_n$ である。$\log M_2$ も同じである。
4. 1 回ずつの五角形にまとめる。 $X_{1i}$ は $U_1$ の、$X_{2i}$ は $U_2$ の関数なので独立であり、その分布を $p^{(i)}$ とすると $(X_{1i},X_{2i},Y_i)$ の分布は $p^{(i)}_1p^{(i)}_2W$ である。よって段 2・3 の右辺の和は $na(p^{(i)})$ などの和で、点 $((r_1-\varepsilon_n)^+,(r_2-\varepsilon_n)^+)$ は lem-mac-average の $\bar{\mathcal P}$ に入る($t^+:=\max(t,0)$)。$\bar{\mathcal P}$ は各座標を小さくしても閉じているので $((R_1-\varepsilon_n)^+,(R_2-\varepsilon_n)^+)\in\operatorname{conv}\bigl(\bigcup_p\mathcal P(p)\bigr)$ である。
5. 極限。 段 2 から $(1-P_e^{(n)})\log(M_1M_2)\le n\log\#\mathcal Y+1$ なので、$P_e^{(n)}\le\frac12$ となる $n$ では $\frac1n\log(M_1M_2)$ は有界で、$\varepsilon_n\to0$ である。右辺の集合は閉じているので $(R_1,R_2)$ はそれに属する。容量領域は達成可能な点の閉包なので、やはりそれに含まれる。$\square$
逆の証明では、段 4 で各時刻の入力の分布が異なってよいことが効いている。平均した五角形は 1 つの分布の五角形とは限らないが、凸包には入る。凸包が定理に現れるのは、達成の側の時分割と、逆の側のこの平均の、両方の理由による。
prop-mac-shape の角の点 $(c-b,b)=(I(X_1;Y),\ I(X_2;Y\mid X_1))$ は次のように読める。受信者はまず送信者 1 の符号語を、送信者 2 の信号を雑音とみなして復号する。$X_2$ を平均した 1 送信者の通信路 $x_1\mapsto P(Y\mid X_1=x_1)$ の相互情報量は $I(X_1;Y)$ である。次に、復号した $X_1^n$ を知ったうえで送信者 2 の符号語を復号すると、使える情報量は $I(X_2;Y\mid X_1)$ である。2 つの和は連鎖律で $I(X_1,X_2;Y)$ に等しく、和の速さの上限に届く。復号の順番を入れ替えれば、もう 1 つの角 $(a,c-a)$ になる。この復号の仕方を 逐次復号(successive decoding)という。2 つの角の間の点は時分割で得られる。
$\mathcal X_1=\mathcal X_2=\{0,1\}$、$\mathcal Y=\{0,1,2\}$ で、出力を入力の整数としての和 $Y=X_1+X_2$ とする(雑音はない)。容量領域は
$$
\mathcal C=\Bigl\{R_1,R_2\ge0,\ R_1\le1,\ R_2\le1,\ R_1+R_2\le\frac32\Bigr\}
$$
である。$Y=0$ と $Y=2$ は入力を決めるが、$Y=1$ は $(0,1)$ と $(1,0)$ を区別しない(Mac03 Exercise 15.18、p. 237 と Figure 15.3、p. 238 がこの通信路と領域の図を挙げている)。
両方の入力を一様にとると、$X_2$ を与えれば $Y$ と $X_1$ は 1 対 1 に対応するので $a=H(X_1)=1$、同様に $b=1$、$c=H(Y)=H(\frac14,\frac12,\frac14)=\frac32$ で、五角形は上の集合である。逆に、どの $p$ でも $a=H(X_1)\le1$、$b\le1$ であり、$c=H(Y)\le\frac32$ が成り立つ(下の折りたたみ)ので、すべての $\mathcal P(p)$ は一様な入力の五角形に含まれ、thm-mac-main から主張が従う。
1 回ごとに一方だけが送る時分割では $R_1+R_2\le1$ にとどまる。両者が同時に送れば、$Y=1$ の曖昧さが残るにもかかわらず和の速さを $\frac32$ bit まで上げられる。
$P(X_1=1)=\alpha$、$P(X_2=1)=\beta$、$s:=\alpha+\beta$、$t:=\alpha\beta$ とすると、$Y$ の分布は $(1-s+t,\ s-2t,\ t)$ で、$s$ を止めると $t$ は $\alpha=\beta=\frac s2$ で最大値 $\frac{s^2}4$ をとる。$\varphi(t):=H(1-s+t,s-2t,t)$ の微分は $\log\frac{(s-2t)^2}{(1-s+t)t}$ である。$D(t):=(s-2t)^2-(1-s+t)t$ は $D'(t)=-4(s-2t)-(1-s+2t)\le0$($s-2t=P(Y=1)\ge0$、$1-s+2t\ge0$)で減少し、$D(\frac{s^2}4)=\frac34s^2(1-\frac s2)^2\ge0$ なので、$t\le\frac{s^2}4$ で $\varphi$ は減少しない。よって $\alpha=\beta=\gamma$ の場合を調べればよい。このとき $Y$ は $(X_1,X_2)$ の関数で、$Y=1$ のときだけ 2 通りが等確率で残るので $H(Y)=H(X_1,X_2)-P(Y=1)\cdot1=2h_2(\gamma)-2\gamma(1-\gamma)$ である($h_2$ は 2 値エントロピー)。この関数は 2 階微分が $4-\frac2{\gamma(1-\gamma)\ln2}< 0$ で凹、$\gamma\leftrightarrow1-\gamma$ で対称なので、$\gamma=\frac12$ で最大値 $2-\frac12=\frac32$ をとる。
出力が $Y=X_1+X_2+Z$($Z$ は入力と独立な平均 $0$、分散 $N$ の正規分布)で、入力の平均電力を $P_1,P_2$ 以下に制限する通信路を考える。この記事の定理は有限の入出力についてのもので、この通信路は扱わないが、入力を独立な正規分布 $X_j\sim N(0,P_j)$ にとった五角形は次のように計算できる。$X_2$ を与えると $Y-X_2=X_1+Z$ で、分散 $\sigma_X^2$ の正規分布の入力 $X$ と、それと独立な分散 $\sigma_N^2$ の正規分布の雑音 $Z'$ について $I(X;X+Z')=\frac12\log(1+\frac{\sigma_X^2}{\sigma_N^2})$ である(PW25 Example 3.3、p. 48)から
$$
a=\frac12\log\Bigl(1+\frac{P_1}N\Bigr),\quad b=\frac12\log\Bigl(1+\frac{P_2}N\Bigr),\quad c=\frac12\log\Bigl(1+\frac{P_1+P_2}N\Bigr)
$$
となる($X_1+X_2\sim N(0,P_1+P_2)$)。逐次復号の角では、送信者 1 を送信者 2 の信号を雑音として復号する速さが $\frac12\log(1+\frac{P_1}{P_2+N})$ で、
$$
\frac12\log\Bigl(1+\frac{P_1}{P_2+N}\Bigr)+\frac12\log\Bigl(1+\frac{P_2}N\Bigr)=\frac12\log\frac{N+P_1+P_2}{P_2+N}\cdot\frac{P_2+N}N=c
$$
が成り立つ。$P_1=P_2=N$ では $a=b=\frac12$、$c=\frac12\log3\approx0.7925$ で、角は $(\frac12\log\frac32,\frac12)\approx(0.2925,0.5)$ である。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 送信者は相手のメッセージを知らない(入力は独立) | ex-mac-adder で、両方の符号化器が $(U_1,U_2)$ の両方を知って入力を決める | thm-mac-main の「$\subset$」が成り立たない:$R_1=R_2=0.79$(和 $1.58>\frac32$)が誤りなしで達成できる |
| 通信路が無記憶 | $Y_i=X_{1i}+X_{2i}+Z\bmod2$ で、一様なビット $Z$ を全回に共通に使う | thm-mac-main の「$\subset$」が成り立たない:1 回ずつ見ると $Y_i$ は入力と独立で右辺は $\{(0,0)\}$ だが、$R_1< 1$ なら $(R_1,0)$ が誤りなしで達成できる |
1 行目:$M_1=M_2:=2^{\lceil0.79n\rceil}$ とすると $M_1M_2\le2^{1.58n+2}\le3^n$($\log3\approx1.585$、$n$ が大きいとき)なので、メッセージの組を $\{0,1,2\}^n$ の相異なる列 $y^n$ に単射で対応させ、$y^n=(y_1,\dots,y_n)$ の各 $i$ で $x_{1i}+x_{2i}=y_i$ となる入力を両者で送れば、受信者は $y^n$ からメッセージの組を誤りなく読める。
2 行目:1 回目は両者が $0$ を送って $Y_1=Z$ を知らせ、2 回目以降は送信者 2 が $0$ を、送信者 1 がメッセージのビットを送れば、$Y_i+Y_1\bmod2=X_{1i}$ で、$M_1=2^{n-1}$、$M_2=1$ の符号が誤りなく働く。$n-1\ge nR_1$ となる $n$ で $M_1\ge2^{nR_1}$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する