研究背景
ネットワーク符号化
ネットワーク符号化は2000年に初めてAhlswede et al．[1]によって提案された．従来の情報伝送では，2つ以上のノードから情報が送られてきた場合，受信したノードは数回に分けてその情報を送信しなければならなかった．しかし，ネットワーク符号化を用いることで，送られてきた複数の情報をノードの中で論理演算することによって1つの情報にし，1度に送信することを考えた．これによりネットワークの伝送効率が上がった．その後，ネットワーク符号化は代数的体系が整えられてきた．Li et al．[2]は各ノードへの入力と出力の関係を線形結合で表すことを提案した．そしてネットワーク符号化のデメリットである演算の複雑さが，線形結合で適切な係数を選ぶことにより解消されることを証明した．Koetter et al．[3]は，ソースから送る情報とシンクで受け取る情報の関係を行列で表すことを提案した．これによりその行列が正則であるとき，受け取った情報に逆行列を掛けることで元の情報を復号できることを示した．Ho et al．[4]が提案したランダムネットワーク符号化は，あるノードが故障した場合を想定した符号化である．これまでの符号化はネットワークトポロジーごとに線形結合や行列が決まっていたが，ランダムネットワーク符号化は各ノードごとで独立した符号化を行っているので他のノードに影響しない．また，符号化の係数をランダムに決定しているため，係数の有限体が大きいほど行列が正則になる確率が高くなり復号できることが示されている．
ネットワーク符号化と誤り訂正
ネットワーク符号化と誤り訂正の基礎となる, 誤り訂正についての符号数の限界について提案されたのが論文[5,6]である．エラーが発生したとき正しく復号できる符号数の上限と下限であるであるハミング限界とギルバート＝バルシャモフ限界などを示した．またその上限と下限をより正確なものにできることが証明された[7,8]．また, リンクが故障した場合のネットワーク符号化についてもKoetter et al．[3]で開発されていた．これまでの誤り訂正の研究では，送信情報が1bitである基本的な条件であったが，Silva et al．[9]は一般的な条件での誤り訂正を示した．Ho et al．[10]はランダムネットワーク符号化を用いてエラー検出を行った．Yang et al．[11]は従来のネットワーク符号化と誤り訂正にエラーベクトルのハミング重み(エラーの中の1の数)を距離とみなす概念を導入した．これにより, 非線形符号において, 訂正できるエラーの数が検出できるエラーの数の半分以上になることがわかった.
ネットワーク符号化と安全性
ネットワークのセキュリティについても考えられてきた．論文[12]ではセキュリティの中でも通信の傍受とネットワークのエラーについて考察されている．Cai et al．[13]は線形ネトワーク符号化を用いて, 傍受される通信ネットワークのモデルを提案した．また, ソースノードと中継ノードの間にエンコーダーを設置したモデルも提案された[14]．
ネットワーク符号化の実用化
ネットワーク符号化の実用の例として, MicrosoftはP2Pネットワークにネットワーク符号化を用いたAvalacheを提案した[15,16]．このシステムではファイルのダウンロード時間が符号化を用いない送信に比べ2～3倍速くなった[17]．
先行研究
An error correcting code in delay linear network coding
先行研究[18]は, ネットワーク符号化を動的に考え, 最初のノードからの送信情報を入力, 最後の情報を受信するノードで蓄積される情報を出力, エッジを通る情報を状態変数とし, 状態方程式をつくる．状態方程式からネットワーク符号化モデルをつくり, ガウスの消去法を用いて復号する．次にエラーが入るネットワークのモデルについて, ネットワーク符号化を用いた誤り訂正符号を考え, 符号器と復号器を設計した．
ネットワーク符号化と拡張バタフライネットワーク
通信ネットワークにおいて情報の伝送効率を向上させる手法としてネットワーク符号化が提案されている．ネットワーク符号化とは, 中継ノードに符号化機能を付加することにより, 複数の情報を受信したノードが論理演算することによって, ボトルネックとなるエッジを複数の情報をもつ符号化された情報が通ることができる手法である．そして, 別の通信路から復号に必要な情報を受信することによって, 効率よく複数の情報を得ることができる．本論文では, 先行研究[18]で扱っているネットワーク符号化と誤り訂正符号について考察する．まず, 先行研究[18]の状態方程式では適当な離散時刻に情報が出力されなかったので, 状態方程式を変更する．また, 復号についての定理を改善することにより計算効率が向上させる．これらの結果を用いることにより, 先行研究[18]のGJDを簡単な形に書き換える．
次に, 複雑なネットワークについて, 送信ノードと受信ノードの組を決定したとき, 送信ノードから受信ノードへ情報が送信可能である条件を求めることを目的とする．まず, 拡張バタフライネットワークを設定し, 送信可能である条件を求める．拡張バタフライネットワークについて, 局所的min-cutを定義する．そして, 送信ノードから4つの情報を送信し, 各受信ノードで2ずつ情報を受信するための必要条件を求める．必要条件ついて, 局所的min-cutを用いたネットワーク全体の中の一部に注目した条件と受信ノードにのみ注目した条件を求める．
 |
| 図1: Expansion of butterfly network |
今後の目標
今後の課題として, 誤り訂正について, 誤り検知の具体的な手法を提案したい．そして, 復号できる情報のクラスを広げた復号器の設計をしたい．
そして, 十分条件を求めたり, 必要条件のクラスを広げていき必要十分条件を求めたい．また, 3つの情報の送信や, 2つの情報の送信についての必要十分条件を求めたい．最終的には, ネットワーク符号化が用いられる一般的なネットワークで送信ノードと受信ノードの組を決めたとき送信可能である必要十分条件を求めたい．
参考文献
[1] R. Ahlswede, N. Cai, S. Li, and R. Yeung, "Network informmation flow," IEEE Transaction on Information Theory, vol. 46, pp. 1204-1216, 2000.
[2] S. Li, R. Yeung, and N. Cai, "Linear network coding," IEEE Transaction on Information Theory, vol. 49, pp. 371-381, 2003.
[3] R. Koetter and M. Medard, "An algebraic approach to network coding," IEEE/ACM Transactions on Networking, vol. 11, pp. 782-795, 2003.
[4] T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, "A random linear network coding approach to multicast," IEEE Transactions on Information Theory, vol. 52, no. 10, pp. 4413-4430, 2006.
[5] R. W. Yeung and N. Cai, "Network error correction, part I: Basic concepts and upper bounds," Commun. Inform. Syst., vol. 6, no. 1, pp. 19-36, 2006.
[6] N. Cai and R. W. Yeung, "Network error correction, part II: Lower bounds," Commun. Inform. Syst., vol. 6, no. 1, pp. 37-54, 2006.
[7] S. Yang, C. K. Ngai, and R. W. Yeung, "Construction of linear network codes that achieve a refined singleton bound," IEEE International Symposium on Information Theory, pp. 3673-3676, 2007.
[8] S. Yang, and R. W. Yeung, "Refined coding bounds for network error correction," IEEE Information Theory Workshop on Information Theory for Wireless Networks, pp. 1-5, 2007.
[9] D. Silva and F. Kschischang, "Adversarial error correction for network coding: models and metrics," Forty-Sixth Annual Allerton Conference, pp. 1246-1253, 2008.
[10] T. Ho, R. Koetter, M. Efforts, and D. Karger, "Byzantine modification detection in multicast networks with random network coding," IEEE Transactions on Information Theory, vol. 54, no. 6, pp. 2798-2803, 2008.
[11] S. Yang, R. Yeung, and Z. Zhang, "Weight properties of network codes," European Transactions on Telecommunication, vol. 19, no. 4, pp. 371-383, 2008.
[12] C. Ngai and R. Yeung, "Secure error-correcting (SEC) network codes," Workshop on Network Coding, Theory and Applications, 2009.
[13] N. Cai and R. W. Yeung, "Secure network coding," Proc. of 2002 IEEE Int. Symp. on Information Theory (ISIT’02), vol. 46, pp. 323, 2002.
[14] SY. El. Rouayheb and E. Soljanin, "On wiretap networks II," IEEE International Symposium on Information Theory, pp. 551-555, 2007.
[15] C. Gkantsidis, J. Miller, and P. Rodriguez, "Comprehensive view of a live network coding P2P system," in Proc. ACM SIGCOMM/USENIX IMC’06, 2006.
[16] C. Gkantsidis, J. Miller, and P. Rodriguez, "Anatomy of a P2P content distribution system with network coding," in Proc. of the 5th International Workshop on Peer-to-Peer Systems, 2006.
[17] C. Gkantsidis and P. R. Rodriguez, "Network coding for large scale content distribution," Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 4, pp. 2235-2245, 2005.
[18] L. Vu and T. Hayakawa, "An error-correcting code in delay linear network coding," IEEE Conference on Decision and Control, 2016.