(57)【要約】      （修正有）【課題】非周期有向ネットワークにおいて情報源ノードから終端ノードへ異なるメッセージを安全に同時配信する符号化を行う。【解決手段】情報源ノード、複数の中継ノード、複数の終端ノードが非周期有向ベクトルで結合されているネットワークにおいて、情報源ノードから異なるメッセージを終端ノードに送信する際に、情報源ノードからのメッセージｘ１，ｘ２，・・・，ｘｋ（ｘｉ∈ＧＦ（２）ｎωｉ）ｎはブロック長、ωiはメッセージの伝送レート、GF(2)は2元体）を送出し、中継ノードｉからｊへのメッセージ送信のための符号器を、2011103556.tif 000065次元で与えられた次元の行列とする。【選択図】図１
2011103556.tif 000002
【特許請求の範囲】
【請求項１】
情報源ノードｓ、複数の中継ノード、複数の終端ノードｔｉが非周期有向辺で結合されて構成されるネットワークにおけるネットワーク符号化方法であって、
前記情報源ノードｓから異なるメッセージ
【数４３】
2011103556.tif 000045
を前記終端ノードに送信する際に、
ノードｉからノードｊへメッセージを送信するための符号器が、ノードｉの入力情報を
【数４４】
2011103556.tif 000046
該符号器を行列表現
【数４５】
2011103556.tif 000047
とするとき、該ノードｉから該ノードｊへの出力情報が
【数４６】
2011103556.tif 000048
（但し、
【数４７】
2011103556.tif 000049
は、
【数４８】
2011103556.tif 000050
Ａijは、
【数４９】
2011103556.tif 000051
で与えられるように符号化する
ことを特徴とするネットワーク符号化方法。
【請求項２】
前記情報源ノードsは、
メッセージとして、
【数５０】
2011103556.tif 000052
（但し、nはブロック長、ωiはメッセージ
【数５１】
2011103556.tif 000053
の伝送レート、GF(2)は２元体）が入力されると、記憶手段からパリティ検査行列が与えられた際の組織符号に対する生成行列を求める手法により求められた行列Ｂiと、前記行列Ａijを前記行列Ｂiと前記行列Ａijを取得して、
【数５２】
2011103556.tif 000054
を計算し、前記ノードｉに出力する
請求項１記載のネットワーク符号化方法。
【請求項３】
情報源ノードｓ、複数の中継ノード、複数の終端ノードｔｉが非周期有向辺で結合されて構成されるネットワークにおけるネットワーク符号化システムであって、
前記中継ノードは、
前記情報源ノードｓから異なるメッセージ
【数５３】
2011103556.tif 000055
を前記終端ノードに送信する際に、
ノードｉからノードｊへメッセージを送信するための符号器が、ノードｉの入力情報を
【数５４】
2011103556.tif 000056
該符号器を行列表現
【数５５】
2011103556.tif 000057
とするとき、該ノードｉから該ノードｊへの出力情報が
【数５６】
2011103556.tif 000058
（但し、
【数５７】
2011103556.tif 000059
は、
【数５８】
2011103556.tif 000060
Ａijは、
【数５９】
2011103556.tif 000061
で与えられるように符号化する手段を有することを特徴とするネットワーク符号化システム。
【請求項４】
前記情報源ノードsは、
パリティ検査行列が与えられた際の組織符号に対する生成行列を求める手法により求められた行列Ｂiと、前記行列Ａijを格納した記憶手段と、
メッセージとして、
【数６０】
2011103556.tif 000062
（但し、nはブロック長、ωiはメッセージ
【数６１】
2011103556.tif 000063
の伝送レート、GF(2)は２元体）が入力されると、前記記憶手段から前記行列Ｂiと前記行列Ａijを取得して、
【数６２】
2011103556.tif 000064
を計算し、前記ノードｉに出力する処理手段と、
を有する
請求項３記載のネットワーク符号化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク符号化（Network Coding）システム及び方法に係り、特に、与えられた非周期有向ネットワークにおいて、情報源ノードから終端ノードへ異なるメッセージを安全に同時配信するためのネットワーク符号化システム及び方法に関する。
【背景技術】
【０００２】
従来、各辺にレート制限を持つ非周期有向グラフとしてネットワークが与えられた際に、情報源ノードから終端ノードへ同一のメッセージを伝送するためのネットワーク符号化方式として、単一の送信側が複数の受信側に対して情報をマルチキャストする状況において、中間ノードに符号化を許すことで、従来のルーティングでは達成できないレートが達成可能し、また、中間ノードで符号化が許される場合のレートの限界を与えて、ネットワークの各ノードで符号化を行う方式（例えば、非特許文献1参照）や、情報源ノードから終端ノードへ必ずしも同一でないメッセージを伝送するネットワーク符号化方式（例えば、非特許文献２参照）等がある。
【０００３】
また、ネットワーク符号の実現を、複数のベクトル集合に対して線型独立なベクトルを構成するJaggi-Sanders Algorithmに従って、十分大きい体上で構成している（例えば、非特許文献３参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】R. Ahlswede, N. Cai, S.・Y. R. Li, and R. W. Yeung, "Network information flow, "IEEE Trans. Inform. Theory, vol. 46, pp. 1204-1216, 2000.
【非特許文献２】R. W. Yeung, Information Theory and Network Coding, Springer, 2008.
【非特許文献３】S. Jaggi. P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen, "Polynomial time algorithms for multicast network code construction, " IEEE Trans. Inform. Theory, vol. 51, pp. 1973-1982, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のネットワーク符号化方式（非特許文献１）では、終端ノードへ送るメッセージは同一のメッセージであるという制限があった。
【０００６】
また、ネットワーク符号化の理論においては終端ノードへ送るメッセージが必ずしも同一でない場合も考察されているが（非特許文献２、及び、文献１：X. Yan, R. W. Yeung, and Z. Zhang, "The capacity region for multi-source multi-sink network coding," Proc. 2007 IEEE International 4215915）、現時点ではその考察結果から具体的な符号化方式が導出されていない。
【０００７】
本発明は、上記の点に鑑みなされたもので、与えられた非周期有向ネットワークにおいて、情報源ノードから終端ノードへ異なるメッセージを安全に同時に配信することが可能なネットワーク符号化システム及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
従来は、ネットワーク符号の実現を非特許文献３による手法に従って、十分大きい体上で構成していた。これに対し、本発明は、非特許文献１のランダム符号化による証明を線型符号に対して適用することにより符号語の体をＧＦ（２）（２元のガロア体）上のブロック符号（固定長の符号であり、ｋ桁の情報語からｎ桁の符号語を生成する）に対して適用できるパリティ検査符号の結果を利用することによってブロードキャスト可能な符号を実現するものである。
【０００９】
本発明（請求項１）は、情報源ノードｓ、複数の中継ノード、複数の終端ノードｔｉが非周期有向辺で結合されて構成されるネットワークにおけるネットワーク符号化方法であって、
情報源ノードｓから異なるメッセージ
【００１０】
【数１】
2011103556.tif 000003
を終端ノードｔに送信する際に、
ノードｉからノードｊへメッセージを送信するための符号器が、ノードｉの入力情報を
【００１１】
【数２】
2011103556.tif 000004
該符号器を行列表現
【００１２】
【数３】
2011103556.tif 000005
とするとき、該ノードｉから該ノードｊへの出力情報が
【００１３】
【数４】
2011103556.tif 000006
（但し、
【００１４】
【数５】
2011103556.tif 000007
は、
【００１５】
【数６】
2011103556.tif 000008
Ａijは、
【００１６】
【数７】
2011103556.tif 000009
で与えられるように符号化する。
【００１７】
また、本発明（請求項２）は、情報源ノードsにおいて、
メッセージとして、
【００１８】
【数８】
2011103556.tif 000010
（但し、nはブロック長、ωiはメッセージ
【００１９】
【数９】
2011103556.tif 000011
の伝送レート、GF(2)は２元体）が入力されると、記憶手段からパリティ検査行列が与えられた際の組織符号に対する生成行列を求める手法により求められた行列Ｂiと、行列Ａijを行列Ｂiと行列Ａijを取得して、
【００２０】
【数１０】
2011103556.tif 000012
を計算し、ノードｉに出力する。
【発明の効果】
【００２１】
上記のように本発明によれば、情報源ノードから終端ノードへ異なるメッセージを安全に同時配信することが可能となるため、以下の２点の効果が期待される。
【００２２】
１点目は、使用するアルファベットがGF(2)の元であること、及び、符号器を行列形式で定義したことによって実装が、従来のJaggi-Sanders Algorithm（非特許文献３）に比較して容易になった点である。従来の構成方法は、対象となるネットワークが変わる毎に（もしくはネットワークに別のネットワークが追加される毎に）新しく符号を再構成する必要があったが、本発明による符号構成法を用いれば新しく加わったネットワークノードに対してのみ追加的に行列を付与すればよい。
【００２３】
２点目は、ブロードキャスト（各終端ノードに対して異なったメッセージを送信すること）を実現する符号を初めて具体的に構成したことである。同時に、自分とは異なるメッセージを受け取るクラスに対しては自分が受け取るメッセージに関する情報は漏れないように設計されている。
【図面の簡単な説明】
【００２４】
【図１】本発明の一実施の形態におけるネットワーク符号の例である。
【図２】本発明の一実施の形態におけるノード構成例である。
【図３】本発明の一実施の形態における情報源ノードの構成図である。
【図４】本発明の一実施の形態における中間ノードｉ（ｉ≠ｓ、ｉ≠ｔ）の構成図である。
【図５】本発明の一実施の形態における復号器を構成する情報と行列の関係を示す図である。
【図６】本発明の一実施の形態における終端ノードが得る情報と入力メッセージとの関係を示す図である。
【図７】本発明の一実施の形態における終端ノード（ｔ∈Ｃｉ）の構成図である。
【図８】本発明の一実施の形態における終端ノードで正しい復号が行われるための条件式である。
【図９】本発明の一実施の形態における伝送可能なメッセージが存在するためのレート領域である。
【発明を実施するための形態】
【００２５】
以下、図面と共に本発明の実施の形態を説明する。
【００２６】
本発明は、各辺にレート制限を持つ非周期有向グラフとしてネットワークが与えられた際に、情報源ノードから終端ノードへメッセージを伝送するための符号化方式を与えるものである。このとき、一般に終端ノードtは複数存在するが、終端ノードへ配信されるメッセージは互いに異なっていてもよい。
【００２７】
情報ノードは、一つあるいは複数のメッセージを符号化して次のノード達へ送信する。各ノードは、得られた情報を次のノード達に対してノード毎に符号化した後送信する。以上の操作を各ノードが繰り返した後、各終端ノードに所望のメッセージが届くことが要請される。
【００２８】
さらに、１つの終端ノードからは、自分とは異なるメッセージを受け取ることになっている他の終端ノードが具体的にどのメッセージを受け取ったかについて、注目している終端ノードが受け取った情報から推定することはできないという意味で安全性が合わせて要請される。
【００２９】
図１は、本発明の一実施の形態におけるネットワーク符号の例である。
【００３０】
同図に示すように、非周期有向グラフＧ＝（Ｖ，Ｅ）（但し、Ｖはノードの集合、Eは辺の集合）と各辺（i，ｊ）∈Ｅに対するレート制限Ｒijの組Ｒが与えられたとき、（Ｇ，Ｒ）で決まるネットワークにおいて、１つの情報源ノードｓから複数のノードに対して１対多の通信を行う際に、各々の受信側が必要なメッセージを各々に対して同時に配信するための符号化方式を考察する。ここで、情報源ノードをｓ∈Ｖ（ｓはＶの要素）、終端ノードの集合をＴ＝｛ｔ１，ｔ２，…，ｔＬ｝⊂Ｖ（ＴはＶの部分集合）とする。さらに、Ｔを共通部分の無い部分集合Ｃｉで分割する。すなわち、Ｔ＝∪Ｃｉ、但し、Ｃｉ∩Ｃｊ＝φ（１≦ｉ，ｊ≦Ｋ）である。このとき、情報源ノードｓは、メッセージ
【００３１】
【数１１】
2011103556.tif 000013
を送出する。但し、
【００３２】
【数１２】
2011103556.tif 000014
（ここで、ｎはブロック長、ωｉはメッセージ
【００３３】
【数１３】
2011103556.tif 000015
の伝送レートである。ＧＦ（２）は２元のガロア体）
ノードｉからノードｊへ通信路１回あたり送られるビット数をｋijとすると、レート制限は、
ｋij／ｎ＜Ｒij          （１）
となる。
【００３４】
ノードｉからノードｊへの送信のための符号器をｆij、終端ノードｔiの復号器をｇｉとする。
【００３５】
上記のレート制限（１）を満足するように、各符号器及び復号器を構成して、各終端ノードｔｉにおいて、ｇｉ∈Ｃｉの出力が正しく
【００３６】
【数１４】
2011103556.tif 000016
となるようにする必要がある。
【００３７】
さらに、終端ノードのクラスＣｉに属する受信側が、自分が受け取った情報からは他のクラスＣｊ（ｉ≠ｊ）が受け取るメッセージは完全に分からないようにする必要がある。
【００３８】
以下に、本発明の符号器と復号器について説明する。
【００３９】
［１］符号器
図２は、本発明の一実施の形態におけるノード構成を示す。
【００４０】
ノードｉからノードｊへの送信のための符号器を行列によって構成する。
【００４１】
行列の次元はノードｉへの入力情報とノードｊへの出力情報を考えると、
【００４２】
【数１５】
2011103556.tif 000017
となる。
【００４３】
上記の（２）で与えられた次元の行列Aijは各要素を互いに独立に「０」もしくは「１」の値をランダムにとることによって構成される。
【００４４】
但し、クラスＣiに属する終端ノードに入射する辺を持つノードを｛ｉ１，…，ｉJ｝とすると、ノードｉｊからＣｉへ入射する辺に対応する符号を構成する行列
【００４５】
【数１６】
2011103556.tif 000018
は、
【００４６】
【数１７】
2011103556.tif 000019
となり、同一クラスＣｉに属する終端ノードｔに依存しないものとする。
【００４７】
符号器は、ノードｉへの入力情報
【００４８】
【数１８】
2011103556.tif 000020
を
【００４９】
【数１９】
2011103556.tif 000021
とすると、ノードｊへの出力として、
【００５０】
【数２０】
2011103556.tif 000022
を与える。
【００５１】
情報源ノードの構成を図３に、中間ノード（情報源ノード及び終端ノード以外のノード）の構成を図４に示す。
【００５２】
情報源ノードは、入力部１０、処理部Ａ１１、処理部Ｂ１４、記憶部１２、中間出力部１３、出力部１５から構成される。
【００５３】
当該情報源ノードの記憶部１２には、予め行列Ｂ１，…，Ｂｋ（パリティ検査行列が与えられた際の組織符号に対する行列）及び行列
【００５４】
【数２１】
2011103556.tif 000023
が格納されている。
【００５５】
処理部Ａ１１に入力部１０から
【００５６】
【数２２】
2011103556.tif 000024
（但し、nはブロック長、ωはnの系列がω個並んだもの）が入力され、記憶部１２から行列B1,…，Ｂkが入力されると、処理部Ａ１１は、
【００５７】
【数２３】
2011103556.tif 000025
を計算し、中間出力部１３に
【００５８】
【数２４】
2011103556.tif 000026
を出力する。上記の行列B1,…，Ｂkは、パリティ検査行列が与えられた際の組織符号に対する生成行列を求める手法をそのまま適用することによって得られる（例えば、文献２：平澤、西島、「符号理論入門」、培風館、1999.参照）。
【００５９】
なお、同図の例では、処理部Ａ、処理部Ｂの２つを記載しているが、１つの処理部で行うようにしてもよい。中間出力部１３は、処理部Ｂ１４に対して
【００６０】
【数２５】
2011103556.tif 000027
を出力する。処理部Ｂ１４は、記憶部１２からＡsiを取得し、
【００６１】
【数２６】
2011103556.tif 000028
を計算し、その結果を出力部１５に出力する。出力部１５は処理部Ｂ１４から受け取った計算結果をノードｉへ出力する。
【００６２】
中間ノードは、入力部２０、処理部２１、記憶部２２、出力部２３から構成される。記憶部２２には、行列Ａijが格納されている。
【００６３】
入力部２０は、前段のノードから
【００６４】
【数２７】
2011103556.tif 000029
が入力されると、処理部２１に渡す。処理部２１は、記憶部２２から行列Ａijを取得して、入力部２０から渡された
【００６５】
【数２８】
2011103556.tif 000030
を用いて、
【００６６】
【数２９】
2011103556.tif 000031
を計算し、出力部２３に渡す。出力部２３は、当該計算結果をノードｊに出力する。
【００６７】
［２］復号器の構成
次に、復号器（終端ノード)の構成について説明する。
【００６８】
図５は、本発明の一実施の形態における復号器を構成する情報と行列の関係示す図である。
【００６９】
中間ノードｊから終端ノードｔｉが受け取った情報
【００７０】
【数３０】
2011103556.tif 000032
を
【００７１】
【数３１】
2011103556.tif 000033
とする。
【００７２】
このとき、
【００７３】
【数３２】
2011103556.tif 000034
とメッセージ
【００７４】
【数３３】
2011103556.tif 000035
との関係は、図６で表されるように、線型となるので、復号器の出力は図６の線型方程式に対して掃き出し法を適用することによって与えられる（但し、図６のチルダが付いている行列は、情報源ノードからノードｉｊへの経路に存在する行列を掛け合わせたものである）。
【００７５】
掃き出し法で得られた行ベクトルが望ましいメッセージとなるように入力メッセージは適切な符号語でなければならない。この符号語の構成を次に述べる。
【００７６】
終端ノードの構成を図７に示す。終端ノードは、入力部３０、処理部３１、記憶部３２、出力部３３から構成される。記憶部３２には、
【００７７】
【数３４】
2011103556.tif 000036
が格納されている。入力部３０は、前段の中間ノードｊから
【００７８】
【数３５】
2011103556.tif 000037
が入力されると、処理部３１に送る。処理部３１は、記憶部３２から
【００７９】
【数３６】
2011103556.tif 000038
を取得し、入力部３０から取得した情報を用いて、方程式
【００８０】
【数３７】
2011103556.tif 000039
を掃き出し法で計算し、その解
【００８１】
【数３８】
2011103556.tif 000040
を出力部３３に出力する。出力部３３は、当該解を復号語として出力する。
【００８２】
［３］符号語の構成
次に、上記の符号語について説明する。
【００８３】
注目している終端ノードｔは、クラスCｉに属しているものとする。このとき、図６に示す方程式を掃き出し法を適用した結果
【００８４】
【数３９】
2011103556.tif 000041
を得るためには、図８で示した方程式が成り立つことが必要である。図８の式が成り立つためには、
【００８５】
【数４０】
2011103556.tif 000042
でなければならない。
【００８６】
一方、レート制限の条件より１≦ｉ≦Ｋに対して
【００８７】
【数４１】
2011103556.tif 000043
が成り立たなければならない。
【００８８】
但し、式（６）の右辺の量は、終端ノードのクラスＣｉへ入射する辺のレート制限を
【００８９】
【数４２】
2011103556.tif 000044
としたときのmaxflowを表すものとした。
【００９０】
上記の式（５）を仮定した際、クラスＣiへ送信可能なメッセージの自由度は式（５）の左辺と右辺の差で表される。
【００９１】
以上をまとめると、伝送可能なメッセージが存在するための伝送レートに関する十分条件は図９に示す領域によって表される。
【００９２】
さらに、図８の式を満足する行列Ｂｉは、パリティ検査行列が与えられた際の組織符号に対する生成行列を求める手法をそのまま適用することによって得られる（例えば、文献２参照）。すなわち、図８の［］で示された行列がパリティ検査行列、Ｂjが生成行列に対応する。
【００９３】
上記の情報源ノード、中間ノードの各符号器及び、終端ノード復号器の動作をプログラムとして構築し、各ノードとして利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００９４】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００９５】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００９６】
１０，２０，３０  入力部
１１  処理部Ａ
１２，２２，３２  記憶部
１３  中間出力部
１４  処理部Ｂ
１５，２３，３３  出力部
２１，３１  処理部
【図１】
2011103556.tif 000066
【図２】
2011103556.tif 000067
【図３】
2011103556.tif 000068
【図４】
2011103556.tif 000069
【図５】
2011103556.tif 000070
【図６】
2011103556.tif 000071
【図７】
2011103556.tif 000072
【図８】
2011103556.tif 000073
【図９】
2011103556.tif 000074