ネットワーク符号化

同義語:ネットワークコーディングnetwork coding

概要

ネットワーク符号化(network coding)とは、通信網の中継点が受け取った記号を転送するだけでなく、それらを組み合わせた記号を作って送る方式である。有向閉路のない網で 1 つの送信元から $L$ 人の受信者へ同じ情報を送るマルチキャストでは、速さは各受信者への最小カットの最小値 $h$ 以下であり、$q\ge L$ の有限体 $\mathbb F_q$ の上の線形符号で速さ $h$ がちょうど達成される。辺素な道を使って各辺の 1 次結合を順に決める構成で証明でき、局所係数を無作為に選んでも高い確率でうまくいく。蝶ネットワークでは、経路の割り当てだけでは速さが $\frac32$ を超えない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 最大フロー最小カット定理, 有限体, 有向非巡回グラフ

ネットワーク符号化(network coding)は、通信網の中継点が受け取った記号をそのまま転送するだけでなく、それらを組み合わせた新しい記号(たとえば和)を作って送る方式である。1 つの送信元から複数の受信者へ同じ情報を届ける マルチキャスト では、各受信者への最小カットの最小値 $h$ が速さの上限であり、中継点での符号化を許せばこの上限がちょうど達成できる。一方、記号の転送と複製だけ(経路の割り当て)では一般に達成できない。記号の種類を増やせば上限に近い速さが中継点の符号化で達成できること、経路の割り当てだけでは足りない例があることを、R. Ahlswede、N. Cai、S.-Y. R. Li、R. W. Yeung が 2000 年に示した(ACLY00)。さらに、有限体の上の線形な操作だけで速さ $h$ がちょうど達成できることを Li、Yeung、Cai が示した(LYC03。2 つの帰属は Jag05 §I-B、p. 1974 の紹介による)。
この記事では、網と符号を定義し、カットによる上界と、受信者の数 $L$ 以上の大きさの有限体の上の線形符号で上界 $h$ が達成できることを完全に証明する。後者の証明は、各受信者への辺素な道を使って辺を順に決めていく S. Jaggi らの構成(Jag05)に沿う。蝶ネットワークで経路の割り当てでは速さ $\frac32$ までしか出ないことと、体が小さすぎると線形符号が働かない例も示す。

網と符号

網 とは、有限の有向グラフ $G=(V,E)$(同じ向きの平行な辺を許し、有向閉路をもたないもの)と、送信元 $s\in V$ と、$s$ と異なる 受信者 $t_1,\dots,t_L$ の組である。辺 $e$ の始点を $\mathrm{tail}(e)$、終点を $\mathrm{head}(e)$、頂点 $v$ に入る辺の集合を $\mathrm{In}(v)$ と書き、$s$ に入る辺はないとする。各辺は 1 回の使用で記号を 1 つ誤りなく運ぶ。容量が整数 $c$ の辺は $c$ 本の平行な辺とみなす。
頂点 $t$ について、取り除くと $s$ から $t$ への有向道がなくなる辺の集合の最小の大きさを $\lambda(t)$ と書き、
$$ h:=\min_{1\le l\le L}\lambda(t_l) $$
とおく。$s\in S$、$t\notin S$ となる頂点の集合 $S$(カット)から出る辺の集合を $\delta^+(S)$ と書くと、$\delta^+(S)$ を取り除けば $s$ から $t$ への道はなくなり、逆に辺の集合 $F$ を取り除いて道がなくなるなら、$G-F$ で $s$ から行ける頂点の集合 $S$ は $\delta^+(S)\subset F$ を満たすので、$\lambda(t)=\min_S\lvert\delta^+(S)\rvert$ である。最大フロー最小カット定理 の系「道の本数と弧カット」により、$s$ から $t$ への、互いに辺を共有しない有向道が $\lambda(t)$ 本ある。

網の上の符号

$\Sigma$ を $Q\ge2$ 個の元からなる有限集合(記号)、$\mathcal W$ を有限集合(メッセージ)とする。網の上の 符号 とは、次の写像の族である。

  1. $s$ から出る辺 $e$ ごとの $\varphi_e\colon\mathcal W\to\Sigma$。
  2. それ以外の辺 $e$ ごとの $\varphi_e\colon\Sigma^{\mathrm{In}(\mathrm{tail}(e))}\to\Sigma$。
  3. 受信者ごとの復号の写像 $\psi_l\colon\Sigma^{\mathrm{In}(t_l)}\to\mathcal W$。
    メッセージ $w$ に対し、辺の値 $y_e$ を、$s$ から出る辺では $\varphi_e(w)$、それ以外では始点に入る辺の値に $\varphi_e$ を施したものとして、有向非巡回グラフ の位相的な順に定める。受信者 $t_l$ の推定は $\psi_l((y_e)_{e\in\mathrm{In}(t_l)})$ である。$\log_Q\lvert\mathcal W\rvert$ を符号の 速さ(辺 1 回の使用あたりの記号の数)という。

網を $n$ 回使う方式は、記号を $\Sigma^n$ に替えた 1 回の符号とみなせる。そのとき速さは $\frac1n\log_Q\lvert\mathcal W\rvert$ である。

線形符号と大域符号化ベクトル

$\mathbb F_q$ を $q$ 元の有限体とし、$\Sigma=\mathbb F_q$、$\mathcal W=\mathbb F_q^h$ とする。辺ごとにベクトル $g_e\in\mathbb F_q^h$ を定め、メッセージ $x\in\mathbb F_q^h$ のとき辺 $e$ の値が内積 $y_e=x\cdot g_e$ になる符号で、次を満たすものを 線形符号 という:$s$ から出ない辺 $e$ では、$\mathrm{In}(\mathrm{tail}(e))$ 上の係数 $k_{e',e}\in\mathbb F_q$ があって
$$ g_e=\sum_{e'\in\mathrm{In}(\mathrm{tail}(e))}k_{e',e}\,g_{e'},\qquad y_e=\sum_{e'}k_{e',e}\,y_{e'} $$
となる。$g_e$ を辺 $e$ の 大域符号化ベクトル、$k_{e',e}$ を 局所係数 という。

中継点は、入ってきた値の 1 次結合を送るだけである。$s$ から出る辺の $g_e$ は自由に選べる。大域符号化ベクトルの考え方は Jag05 p. 1975 による。

線形符号で復号できる条件

線形符号で受信者 $t$ が $x$ を必ず復元できる($x\ne x'$ なら入ってくる辺の値の組が異なる)のは、$\{g_e\mid e\in\mathrm{In}(t)\}$ が $\mathbb F_q^h$ を張るとき、かつそのときに限る。

張るなら、その中から基底をなす $h$ 本の辺をとり、その $g_e$ を列とする正則な行列を $G_t$ とすると、値の組は $xG_t$ で、$x=(xG_t)G_t^{-1}$ と復元できる。張らないなら、それらすべてと内積が $0$ になる $z\ne0$ がとれ(直交補空間の次元は正)、$x=0$ と $x=z$ で入ってくる値がすべて一致する。$\square$

主定理

マルチキャストの容量
  1. (カットの上界)$\Sigma$ が $Q$ 元のどの符号でも、すべての受信者が誤りなく復元するなら $\lvert\mathcal W\rvert\le Q^h$ である。メッセージを一様に選び、ある受信者 $t_l$ の誤りの確率が $\varepsilon$ 以下なら、$\lambda(t_l)=h$ のとき
    $$ (1-\varepsilon)\log_2\lvert\mathcal W\rvert\le h\log_2Q+1 $$
    である。
  2. (線形符号による達成)$q\ge L$ となる素数べき $q$ について、すべての受信者が誤りなく復元できる $\mathbb F_q$ 上の線形符号(速さ $h$)がある。
    したがって、網を $n$ 回使う符号の速さは $h$ 以下で(誤りの確率が $0$ に近づく符号の列でも、速さの上極限は $h$ 以下)、速さ $h$ は線形符号でちょうど達成される。
証明の構成

1 は lem-nc-cut と prf-nc-main-1 で、2 は lem-nc-avoid と prf-nc-main-2 で証明する。

2 の体の大きさの条件 $q\ge L$ は Jag05 Theorem 3(p. 1975)の決定的な構成の条件と同じである。記号がビットなら、$2^m\ge L$ となる $m$ をとって $\mathbb F_{2^m}$ の元を $m$ ビットとみなし、網を $m$ 回使えばよい。

カットの上界の証明

カットの外の値はカットの値で決まる

カット $S$($s\in S$、$t\notin S$)について、始点が $S$ の外にある辺の値は、$\delta^+(S)$ の辺の値の組の関数である。とくに $t$ に入る辺の値の組はそうである。

始点が $S$ の外にある辺を位相的な順にとり、帰納法で示す。始点 $u\notin S$ は $s$ でないので、その辺の値は $\mathrm{In}(u)$ の辺の値の関数である。$\mathrm{In}(u)$ の辺のうち始点が $S$ にあるものは $\delta^+(S)$ に属し、始点が $S$ の外にあるものは順の前にあって帰納法の仮定から $\delta^+(S)$ の値の関数である。$\square$

最小カットを通る値の個数を数える(定理の 1)

$\lambda(t_l)=h$ となる $t_l$ と、$\lvert\delta^+(S)\rvert=h$ のカット $S$ をとる。lem-nc-cut により $t_l$ の推定 $\hat W$ は $\delta^+(S)$ の値の関数で、その値は $Q^h$ 通り以下である。誤りがなければ $\hat W=W$ なので $\lvert\mathcal W\rvert\le Q^h$ である。誤りを許す場合、$\lvert\mathcal W\rvert\ge2$ として 情報理論 の定理「Fano の不等式」を底 2 で使うと $H(W\mid\hat W)\le1+\varepsilon\log_2\lvert\mathcal W\rvert$ で、$I(W;\hat W)\le H(\hat W)\le h\log_2Q$ だから、$\log_2\lvert\mathcal W\rvert=H(W)=I(W;\hat W)+H(W\mid\hat W)$ から主張を得る。$n$ 回使う符号では $Q$ を $Q^n$ に替えて $n$ で割ればよい。$\square$

線形符号による達成の証明

部分空間の和集合

$d\ge1$ とし、$B_1,\dots,B_m$ を $\mathbb F_q^d$ の真の部分空間とする。$m\le q$ なら、どの $B_i$ にも属さないベクトルがある。

各 $B_i$ は次元 $d-1$ 以下なので元は $q^{d-1}$ 個以下で、どれも $0$ を含む。よって $\bigl\lvert\bigcup_iB_i\bigr\rvert\le m(q^{d-1}-1)+1\le q^d-q+1< q^d$ である。$\square$

辺を順に決めて基底を保つ(定理の 2)

1. 準備。 新しい頂点 $s'$ と、$s'$ から $s$ への $h$ 本の辺 $e_1,\dots,e_h$ を加え、$g_{e_j}$ を $j$ 番目の単位ベクトルとする。$s$ から出る辺の $g_e$ を $e_1,\dots,e_h$ の 1 次結合として選ぶことは、$g_e$ を自由に選ぶことと同じである。各受信者 $t_l$ について、$s$ から $t_l$ への辺素な有向道を $h$ 本とり、それぞれの先頭に $e_1,\dots,e_h$ を 1 本ずつ付けた道を $P_{l,1},\dots,P_{l,h}$ とする。これらは互いに辺を共有しない。$E$ の辺を、始点の位相的な順に並べ、この順に $g_e$ を決める。
2. 不変条件。 各 $l$ と各 $j$ について、$P_{l,j}$ の辺のうちすでに決めた最後の辺を集めた集合を $C_l$ とする(はじめは $C_l=\{e_1,\dots,e_h\}$)。次を保つ:
$$ \text{すべての }l\text{ で、}\{g_c\mid c\in C_l\}\text{ は }\mathbb F_q^h\text{ の基底である。} $$
はじめは単位ベクトルなので成り立つ。
3. 1 本の辺を決める。 次に決める辺を $e$、$u:=\mathrm{tail}(e)$ とし、$e$ を含む道 $P_{l,j}$ をもつ $l$ の集合を $\Lambda$ とする。$l\in\Lambda$ について $j$ はただ 1 つで(道は辺素)、その道で $e$ の直前の辺 $f_l$ は $\mathrm{In}(u)$ に属し、すでに決まっていて、同じ道のそれより後の辺はまだ決まっていないので $f_l\in C_l$ である。$H_l$ を $\{g_c\mid c\in C_l\setminus\{f_l\}\}$ の張る $h-1$ 次元の部分空間とする。$k\in\mathbb F_q^{\mathrm{In}(u)}$ に $g_e(k):=\sum_{e'}k_{e'}g_{e'}$ を対応させると、$B_l:=\{k\mid g_e(k)\in H_l\}$ は部分空間で、$f_l$ の成分だけが $1$ の $k$ では $g_e(k)=g_{f_l}\notin H_l$ なので真の部分空間である。$\lvert\Lambda\rvert\le L\le q$ なので、lem-nc-avoid により、どの $B_l$($l\in\Lambda$)にも属さない $k$ がある。これを局所係数として $g_e$ を決め、$l\in\Lambda$ について $C_l$ の $f_l$ を $e$ に替える。$g_e\notin H_l$ なので新しい $C_l$ も基底である。$\Lambda$ が空なら $k$ は何でもよい。
4. 終わり。 すべての辺を決めると、$C_l$ は $P_{l,1},\dots,P_{l,h}$ の最後の辺からなり、どれも $t_l$ に入る。よって $\{g_e\mid e\in\mathrm{In}(t_l)\}$ は $\mathbb F_q^h$ を張り、prop-nc-span により $t_l$ は復元できる。$\square$

段 3 の要点は、1 本の辺を決めるときに守るべき条件が、その辺を通る道をもつ受信者ごとに「1 つの超平面を避ける」ことだけだという点である。受信者が $L$ 人なら避ける部分空間は高々 $L$ 個で、体が $L$ 元以上あれば避けられる。

局所係数を無作為に選ぶ

$s$ から出る辺の $g_e$ とすべての局所係数を、互いに独立に $\mathbb F_q$ 上一様に選ぶと、すべての受信者が復元できる確率は $1-\frac{L\lvert E\rvert}q$ 以上である。

証明を開く

prf-nc-main-2 と同じ道と順をとる(道は解析にだけ使い、係数の選び方は道によらない)。辺 $e$ の番で不変条件がそれまで保たれていたとすると、$k$ は $\mathbb F_q^{\mathrm{In}(u)}$ 上一様でそれまでの選択と独立なので、$k$ がある $B_l$ に入る確率は $\sum_{l\in\Lambda}\lvert B_l\rvert/q^{d}\le L/q$ 以下である($d=\lvert\mathrm{In}(u)\rvert$、$\lvert B_l\rvert\le q^{d-1}$)。不変条件が初めて満たされなくなる辺について足すと、どこかで満たされなくなる確率は $L\lvert E\rvert/q$ 以下で、どこでも満たされていれば段 4 のとおり全員が復元できる。$\square$

体を大きくとれば、中継点が局所係数を勝手に(網全体を知らずに)選んでも、高い確率でうまくいく。T. Ho らはこの無作為な方式を詳しく調べている(Jag05 §I-B、p. 1974 の紹介による)。

例

蝶ネットワーク

頂点 $s,u,v,w,x,y,z$ と辺 $s\to u$、$s\to v$、$u\to w$、$v\to w$、$w\to x$、$u\to y$、$x\to y$、$x\to z$、$v\to z$ の網で、受信者を $y,z$ とする(Jag05 Fig. 1、p. 1973)。$y$ へは $s\to u\to y$ と $s\to v\to w\to x\to y$ の辺素な 2 本の道があり、$y$ に入る辺は 2 本なので $\lambda(y)=2$、同様に $\lambda(z)=2$ で、$h=2$ である。
$\mathbb F_2$ 上で、$s\to u$ に $b_1$、$s\to v$ に $b_2$ を送り、$u$ は $b_1$ を、$v$ は $b_2$ をそのまま転送し、$w$ は和 $b_1+b_2$ を送る。$y$ は $b_1$ と $b_1+b_2$ から $b_2$ を、$z$ は $b_2$ と $b_1+b_2$ から $b_1$ を得る。大域符号化ベクトルでは $g_{w\to x}=(1,1)$ で、$y$ に入る辺のベクトルは $(1,0)$ と $(1,1)$、$z$ には $(0,1)$ と $(1,1)$ で、どちらも $\mathbb F_2^2$ を張る。受信者は $L=2$ 人で、$q=2\ge L$ である。

経路の割り当てとは、メッセージを独立な記号の列 $w_1,\dots,w_k$ とし、各辺が網を $n$ 回使う間に高々 $n$ 個の記号の写しを運び、$s$ 以外の頂点から出る辺は、その頂点に入る辺のどれかが運んだ記号しか運ばない方式をいう。受信者は、入ってくる辺のどれかが運んだ記号を受け取る。

蝶ネットワークでの経路の割り当ての限界

ex-nc-butterfly の網で、網を $n$ 回使う経路の割り当てで $k$ 個の記号を $y$ と $z$ の両方に届けるなら $k\le\frac32n$ である。$n=2$、$k=3$ は実現できる。

1 つの記号が使う辺を数える

記号 $w_j$ が $y$ に届くなら、$y$ に入る辺で $w_j$ を運ぶものがあり、その始点が $s$ でなければ、そこに入る辺で $w_j$ を運ぶものがある。網に有向閉路はないので、たどると $s$ に着き、$w_j$ を運ぶ辺だけからなる $s$ から $y$ への道ができる。$z$ についても同じである。
$w\to x$ が $w_j$ を運ばないとする。$x$ に入る辺は $w\to x$ だけなので、$y$ への道は $u\to y$ を通り、$u$ に入る辺は $s\to u$ だけなので $s\to u$ も通る。同様に $z$ への道は $v\to z$ と $s\to v$ を通る。よって $w_j$ は $s\to u$ と $s\to v$ の両方で運ばれる。$w\to x$ が $w_j$ を運ぶなら、$s$ から出る道は $s\to u$ か $s\to v$ を通るので、少なくとも一方で運ばれる。
前者の記号の個数を $k_A$、後者を $k_B$ とすると、$w\to x$ の運べる量から $k_B\le n$、$s$ から出る 2 本の辺の運べる量から $2k_A+k_B\le2n$ である。よって $k=k_A+k_B=\frac12(2k_A+k_B)+\frac12k_B\le n+\frac n2$ である。
$n=2$、$k=3$ では、$w_1$ を $s\to u\to y$ と $s\to v\to z$ で、$w_2$ を $s\to u\to y$ と $s\to u\to w\to x\to z$ で、$w_3$ を $s\to v\to z$ と $s\to v\to w\to x\to y$ で運ぶ。各辺の運ぶ記号は $s\to u$、$s\to v$、$u\to y$、$v\to z$、$w\to x$ で 2 個、ほかの辺で 1 個で、どれも $n=2$ 以下である。$y$ は $u\to y$ から $w_1,w_2$ を、$x\to y$ から $w_3$ を受け取り、$z$ も同様に 3 つとも受け取る。$\square$

符号化すれば 1 回の使用あたり $2$ 個、経路の割り当てでは $\frac32$ 個が上限で、比は $\frac43$ である。Jag05 Theorem 2(p. 1974)は、この比が限りなく大きくなる網の族があることを示している。受信者が 1 人なら、$h$ 本の辺素な道に記号を 1 つずつ流せば経路の割り当てで速さ $h$ が出るので、符号化の利点は受信者が複数のときに現れる。送信元以外のすべての頂点が受信者である場合にも符号化は速さを増やさないことが J. Edmonds の結果から分かる(Jag05 p. 1973 の紹介による)。

反例:仮定を外すと成り立たないこと

外した仮定反例成り立たなくなる結論
体の大きさ $q\ge L$$s$ から 4 つの中継点 $m_1,\dots,m_4$ へ辺を 1 本ずつ張り、2 つの中継点の組 $\{i,j\}$ ごとに受信者 $t_{ij}$ を置いて $m_i\to t_{ij}$、$m_j\to t_{ij}$ を張る網($L=6$、$h=2$)で $q=2$ とするthm-nc-main の 2 が成り立たない:$\mathbb F_2$ 上の線形符号では、6 人の受信者すべてが復元することはできない
中継点で符号化してよい(経路の割り当てに限らない)ex-nc-butterfly の網thm-nc-main の 2 の結論(速さ $h$ の達成)が経路の割り当てでは成り立たない:$h=2$ だが、経路の割り当てでは速さは $\frac32$ 以下(prop-nc-routing)

1 行目:$m_i$ に入る辺は $s\to m_i$ だけなので、$m_i$ から出る辺の大域符号化ベクトルはどれも $g_i:=g_{s\to m_i}$ の定数倍で、$t_{ij}$ に入る辺のベクトルの張る空間は $g_i,g_j$ の張る空間に含まれる。prop-nc-span により、$t_{ij}$ が復元するには $g_i,g_j$ が 1 次独立でなければならない。$\mathbb F_2^2$ の $0$ でないベクトルは $(1,0),(0,1),(1,1)$ の 3 つしかなく、4 つの $g_i$ のうち 2 つは一致するか $0$ になるので、その組の受信者は復元できない。各 $t_{ij}$ への 2 本の道 $s\to m_i\to t_{ij}$、$s\to m_j\to t_{ij}$ は辺素で、$t_{ij}$ に入る辺は 2 本なので $\lambda(t_{ij})=2$ である。なお $\mathbb F_3$ なら $(1,0),(0,1),(1,1),(1,2)$ がどの 2 つも 1 次独立なので復元でき、$q\ge L$ は十分条件であって必要条件ではない。

関連項目

参考文献

[1]
Sidharth Jaggi; Peter Sanders; Philip A. Chou; Michelle Effros; Sebastian Egner; Kamal Jain; Ludo M. G. M. Tolhuizen, Polynomial time algorithms for multicast network code construction, IEEE Transactions on Information Theory 51 (2005), no. 6, pp. 1973–1982, 2005, Fig. 1(p. 1973)、§I-B(p. 1974)、Theorem 2(p. 1974)、Theorem 3 と大域符号化ベクトルの説明(p. 1975)
[2]
Rudolf Ahlswede; Ning Cai; Shuo-Yen Robert Li; Raymond W. Yeung, Network information flow, IEEE Transactions on Information Theory 46 (2000), no. 4, pp. 1204–1216, 2000
[3]
Shuo-Yen Robert Li; Raymond W. Yeung; Ning Cai, Linear network coding, IEEE Transactions on Information Theory 49 (2003), no. 2, pp. 371–381, 2003

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する