(57)【要約】【課題】効率よくデータを分散して転送し、復元することができる符号化装置、復号装置、符号化プログラム、復号プログラム、データ転送システムを提供する。【解決手段】元データを分割することによりＮ個の部分データを生成し、該Ｎ個の部分データに順序を示す番号を付する分割部と、Ｎ個の番号の中から少なくとも１つの番号を指定するデータである第１データを取得する第１取得部と、第１データにより指定された番号が付された部分データに対して所定の演算を行うことにより第２データを算出する算出部と、第１取得部の処理と算出部の処理とをＬ回繰り返させ、第１取得部により得られた第１データと該第１データに基づいて算出部により得られた第２データとから成るＬ個のペアを出力する出力部と、Ｌ個のペアを分割して複数の情報送信装置に配布する配布部とを備えた。【選択図】図２
2008172617.tif 000002
【特許請求の範囲】
【請求項１】
１つの元データから複数の符号化されたデータへの符号化を行う符号化装置であって、
元データを分割することによりＮ（２以上の整数）個の部分データを生成し、該Ｎ個の部分データに順序を示す番号を付する分割部と、
前記分割部により付されたＮ個の番号の中から少なくとも１つの番号を指定するデータである第１データを取得する第１取得部と、
前記第１取得部により取得された第１データにより指定された番号が付された部分データに対して所定の演算を行うことにより第２データを算出する算出部と、
前記第１取得部の処理と前記算出部の処理とをＬ（２以上の整数）回繰り返させ、前記第１取得部により得られた第１データと該第１データに基づいて前記算出部により得られた第２データとから成るＬ個のペアを出力する出力部と、
前記Ｌ個のペアを分割して複数の情報送信装置に配布する配布部と、
を備える符号化装置。
【請求項２】
請求項１に記載の符号化装置において、
前記所定の演算は、前記第１データにより指定された番号が付された部分データ同士のビット位置毎の排他的論理和演算であることを特徴とする符号化装置。
【請求項３】
請求項１または請求項２に記載の符号化装置において、
第１データは、Ｎビットのビット列であり、第１データのうち少なくとも１ビットの値が１であり、該値が１であるビットのビット位置が前記番号に対応し、Ｌ回の前記第１取得部の処理により取得されるＬ個の第１データはそれぞれ異なることを特徴とする符号化装置。
【請求項４】
複数の符号化されたデータから１つの元データへの復号を行う復号装置であって、
複数の情報送信装置から送出される符号化データを受信する受信部と、
前記符号化データに含まれる第１データと第２データとから成る複数個のペアを順次取得する第２取得部と、
前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第１データに操作を行うことにより前記複数個の第１データを第３データに変換する第１操作部と、
前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第２データに前記第１操作部と同一の操作を行うことにより前記複数個の第２データを第４データに変換する第２操作部と、
を備える復号装置。
【請求項５】
請求項４に記載の復号装置において、
前記操作は、ガウスの消去法を用いることを特徴とする復号装置。
【請求項６】
１つの元データから複数の符号化されたデータへの符号化をコンピュータに実行させる符号化プログラムであって、
元データを分割することによりＮ（２以上の整数）個の部分データを生成し、該Ｎ個の部分データに順序を示す番号を付する分割ステップと、
前記分割ステップにより付されたＮ個の番号の中から少なくとも１つの番号を指定するデータである第１データを取得する第１取得ステップと、
前記第１取得ステップにより取得された第１データにより指定された番号が付された部分データに対して所定の演算を行うことにより第２データを算出する算出ステップと、
前記第１取得ステップと前記算出ステップとをＬ（２以上の整数）回繰り返させ、前記第１取得ステップにより得られた第１データと該第１データに基づいて前記算出ステップにより得られた第２データとから成るＬ個のペアを出力する出力ステップと、
前記Ｌ個のペアを分割して複数の情報送信装置に配布する配布ステップと、
をコンピュータに実行させる符号化プログラム。
【請求項７】
複数の符号化されたデータから１つの元データへの復号をコンピュータに実行させる復号プログラムであって、
複数の情報送信装置から送出される符号化データを受信する受信ステップと、
前記符号化データに含まれる第１データと第２データとから成る複数個のペアを順次取得する第２取得ステップと、
前記第２取得ステップにより取得された前記複数個のペアの取得順序に基づいて前記複数個の第１データに操作を行うことにより前記複数個の第１データを第３データに変換する第１操作ステップと、
前記第２取得ステップにより取得された前記複数個のペアの取得順序に基づいて前記複数個の第２データに前記第１操作ステップと同一の操作を行うことにより前記複数個の第２データを第４データに変換する第２操作ステップと、
をコンピュータに実行させる復号プログラム。
【請求項８】
元データを分割することによりＮ（２以上の整数）個の部分データを生成し、該Ｎ個の部分データに順序を示す番号を付する分割部と、
前記分割部により付されたＮ個の番号の中から少なくとも１つの番号を指定するデータである第１データを取得する第１取得部と、
前記第１取得部により取得された第１データにより指定された番号が付された部分データに対して所定の演算を行うことにより第２データを算出する算出部と、
前記第１取得部の処理と前記算出部の処理とをＬ（２以上の整数）回繰り返させ、前記第１取得部により得られた第１データと該第１データに基づいて前記算出部により得られた第２データとから成るＬ個のペアを出力する出力部と、
前記出力部により出力されたＬ個のペアを分割して配布する配布部と、
前記配布部により配布された複数個のペアを順次取得する第２取得部と、
前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第１データに操作を行うことにより前記複数個の第１データを第３データに変換する第１操作部と、
前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第２データに前記第１操作部と同一の操作を行うことにより前記複数個の第２データを第４データに変換する第２操作部と、
を備えるデータ転送システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを分散させて転送する符号化装置、復号装置、符号化プログラム、復号プログラム、データ転送システムに関するものである。
【背景技術】
【０００２】
送信装置から受信装置へのデータ転送の最中に、受信状態の変化や通信の混雑などにより、データの一部が消失してしまう場合がある。このような場合、受信装置から送信装置へ何らかのメッセージが送ることができる構成であれば、消失したデータを再送することで元のデータを復元することができる。しかし、マルチキャストなど、受信装置から送信装置へメッセージを送れない構成の場合、消失したデータだけを再送することが困難であるため、いくつかのデータ転送方式が提案されている。
【０００３】
なお、本発明の関連ある従来技術として、連続した消失に対しての耐性を高める非同期転送モード通信方式がある（例えば、特許文献１参照）。また、排他的論理和演算を用いてパリティデータを生成する送受信システムがある（例えば、特許文献２参照）。
【特許文献１】特開平５−２３５９７９号公報
【特許文献２】特開２００５−２２３６８３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
受信装置から送信装置へメッセージを送れない構成の場合のためのいくつかのデータ転送方式が提案されている。
【０００５】
まず、データカルーセルと呼ばれるデータ転送方式がある。デジタル放送などで用いられているデータ転送方式であり、送信装置は、送信するデータを複数個に分割した後、回転木馬のように繰り返し送信することから、このような名前が付いている。データカルーセル方式では以下のように元データＤを複数（ｎ個）の部分データ列に分割し、部分データを何回かに分けて繰り返し送信する。
【０００６】
元データＤ＝｛Ｄ1，Ｄ2，…，Ｄn｝
送信データＤ’＝｛Ｄ1，Ｄ2，…，Ｄn，Ｄ1，Ｄ2，…，Ｄn，Ｄ1，Ｄ2，…｝
受信データＤ”＝｛Ｄ1，Ｄ3，…，Ｄn，Ｄ1，Ｄ2｝
【０００７】
この方式によれば、上述した例のように、受信データＤ2が消失してしまった場合でも、１周期分待てばまた同じデータが送られてくるので、元データを復元することが可能である。しかし、送信しなければならないデータ量が増えてしまうという問題がある。また、１周期分待ったとしても同じ部分データが消失する場合もあり、その場合、更に１周期分待たなければならないということも起こり得る。
【０００８】
次に、あらかじめ送信するデータにパリティと呼ばれる冗長なデータを付けて送信するデータ転送方式がある。このデータ転送方式は、以下に示すように、元データＤがｎ個の部分データ列として表わされるとした場合、一定数（ｍ個）の部分データ毎に排他的論理和（ＸＯＲ：eXclusive OR）を計算したものをパリティデータとして元データと共に送信する方式である。以後、“＋”は排他的論理和演算子を表すものとする。
【０００９】
元データＤ＝｛Ｄ1，Ｄ2，…，Ｄn｝
送信データＤ’＝｛Ｄ1，Ｄ2，…，Ｄm，Ｐ1，Ｄm+1，…，Ｄn，Ｐk｝
パリティデータＰk＝Ｄk＋Ｄk+1＋…＋Ｄk+m-1
【００１０】
この方式によれば、送信途中で部分データの１つが消失してしまっても、残りの部分データとパリティデータの排他的論理和を計算することにより、消失したデータを復元することができる。復元の例を以下に示す。
【００１１】
元データＤ＝｛Ｄ1，Ｄ2，Ｄ3｝
送信データＤ’＝｛Ｄ1，Ｄ2，Ｄ3，Ｐ1｝
パリティデータＰ1＝Ｄ1＋Ｄ2＋Ｄ3
受信データＤ”＝｛Ｄ1，Ｄ2，Ｐ1｝（Ｄ3が消失）
消失したデータの復元：Ｄ3＝Ｄ1＋Ｄ2＋Ｐ1
【００１２】
しかし、パリティデータ１個につき、１個までのデータの消失は復元できるが、複数のデータが消失すると復元できないという問題がある。特許文献２の技術によれば、連続した部分データではなくｎ−１個おきの部分データの排他的論理和を取ることで、連続した消失に対しての耐性を高めているが、ランダムに消失した場合の耐性が低くなるという問題がある。
【００１３】
そこで、パリティを複数作り１個以上のデータの消失をも復元できるようにしたデータ転送方式が提案されている。ここで、パリティを作成するためにリードソロモン符号のような誤り訂正符号が用いられている。リードソロモン符号では、以下のように元データＤを複数（ｎ個）の部分データに分割し、ガロア体と呼ばれる有限体からｋ個の線形独立なベクトルα11，α21，α31，…αn1を選択し、以下のようにパリティデータを作成する。
【００１４】
元データＤ＝｛Ｄ1，Ｄ2，Ｄ3，…，Ｄn｝
送信データＤ’＝｛Ｃ1，Ｃ2，Ｃ3，…，Ｃm｝
パリティデータＣｋ＝α11・Ｄ1＋α21・Ｄ2＋…＋αn1・Ｄn
【００１５】
データを復元する際にはｎ個の部分データが取得できていれば、対応するｎ個のベクトルからｎ×ｎの行列Ａ＝（αij）1≦i,j≦nを構成し、取得した部分データにＡの逆行列をかければ元データが取得できる。つまり、以下のようにして、元データを復元する。
【００１６】
【数１】
2008172617.tif 000003
【００１７】
【数２】
2008172617.tif 000004
【００１８】
ここで、ｎ×ｎの逆行列を求める際にＯ（ｎ3）の計算量が必要になるため、ｎの値が大きくなると非常に大きな計算時間が必要になるという問題がある。
【００１９】
そこで、特許文献２の技術のようにパリティデータの生成方法に排他的論理和（ＸＯＲ）だけを用いることにより計算量を減らしているものもある。
【００２０】
以上、送信装置が１個の場合について説明してきたが、送信装置が１個であると送信装置に大きな負荷がかかってしまう。また、受信装置側の通信速度が送信装置側の通信速度よりも速い場合、送信装置の速度がボトルネックになり、受信装置側が期待する速度でデータ転送ができなくなる可能性がある。このような場合、送信装置を複数台用意し、受信装置は任意の送信装置からデータを受信するようにすることにより、送信装置の負荷を分散することが可能である。
【００２１】
上述したデータ転送方式を、送信装置が複数である場合に拡張しようとすると、以下の２つのデータ転送方式が考えられる。
【００２２】
・データ転送方式Ａ．すべての送信装置が元データを保持し、上記の方式を用いてデータを送信する。
・データ転送方式Ｂ．元データを分割して別々のデータとし、各送信装置が別々のデータを送信する。
【００２３】
図１０は、従来のデータ転送方式Ａの動作の一例を示すブロック図である。このデータ転送方式Ａは、分散器１１１、２つの送信器１１２ａ，１１２ｂ、受信器１１３を備える。分散器１１１は、部分データＡ，Ｂ，Ｃ，Ｄ，Ｅからなる送信すべき元データの全てを、送信器１１２ａ，１１２ｂの両方へ送信する。次に、送信器１１２ａ，１１２ｂはそれぞれ、部分データＡ，Ｂ，Ｃ，Ｄ，Ｅの全てを受信機１１３へ送信する。受信器１１３は、送信器１１２ａ，１１２ｂから受信した部分データから元データを復元する。
【００２４】
このデータ転送方式Ａによれば、送信器の数が増えれば、元データを復元できる可能性が上がるが各送信器が同じデータを持っているため送信器が保存するデータ量や、送信する総データ量の点で無駄が大きい。
【００２５】
図１１は、従来のデータ転送方式Ｂの動作の一例を示すブロック図である。
このデータ転送方式Ｂは、分散器１２１、２つの送信器１２２ａ，１２２ｂ、受信器１２３を備える。分散器１２１は、部分データＡ，Ｂ，Ｃ，Ｄ，Ｅからなる送信すべき元データを分割し、部分データＡ，Ｂ，Ｃを送信器１２２ａへ送信し、部分データＤ，Ｅを送信器１２２ｂへ送信する。受信器１２３は、送信器１２２ａ，１２２ｂから受信した部分データから元データを復元する。
【００２６】
データ転送方式Ｂによれば、送信器における記憶装置の容量は小さくすることができるが、仮に１台から部分データが全く取得できないような場合には、元データを復元できない可能性がある。
【００２７】
また、ＨＤＤ（Hard Disk Drive）や通信において、ＬＤＰＣ（Low Density Parity Check）行列を用いる誤り訂正方式がある。しかしながら、この誤り訂正方式は、繰り返し処理を用いるため、計算量が膨大になるという問題がある。
【００２８】
本発明は上述した問題点を解決するためになされたものであり、効率よくデータを分散して転送し、復元することができる符号化装置、復号装置、符号化プログラム、復号プログラム、データ転送システムを提供することを目的とする。
【課題を解決するための手段】
【００２９】
上述した課題を解決するため、本発明は、１つの元データから複数の符号化されたデータへの符号化を行う符号化装置であって、元データを分割することによりＮ（２以上の整数）個の部分データを生成し、該Ｎ個の部分データに順序を示す番号を付する分割部と、前記分割部により付されたＮ個の番号の中から少なくとも１つの番号を指定するデータである第１データを取得する第１取得部と、前記第１取得部により取得された第１データにより指定された番号が付された部分データに対して所定の演算を行うことにより第２データを算出する算出部と、前記第１取得部の処理と前記算出部の処理とをＬ（２以上の整数）回繰り返させ、前記第１取得部により得られた第１データと該第１データに基づいて前記算出部により得られた第２データとから成るＬ個のペアを出力する出力部と、前記Ｌ個のペアを分割して複数の情報送信装置に配布する配布部とを備えたものである。
【００３０】
また、本発明は、複数の符号化されたデータから１つの元データへの復号を行う復号装置であって、複数の情報送信装置から送出される符号化データを受信する受信部と、前記符号化データに含まれる第１データと第２データとから成る複数個のペアを順次取得する第２取得部と、前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第１データに操作を行うことにより前記複数個の第１データを第３データに変換する第１操作部と、前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第２データに前記第１操作部と同一の操作を行うことにより前記複数個の第２データを第４データに変換する第２操作部とを備えたものである。
【００３１】
また、本発明は、１つの元データから複数の符号化されたデータへの符号化をコンピュータに実行させる符号化プログラムであって、元データを分割することによりＮ（２以上の整数）個の部分データを生成し、該Ｎ個の部分データに順序を示す番号を付する分割ステップと、前記分割ステップにより付されたＮ個の番号の中から少なくとも１つの番号を指定するデータである第１データを取得する第１取得ステップと、前記第１取得ステップにより取得された第１データにより指定された番号が付された部分データに対して所定の演算を行うことにより第２データを算出する算出ステップと、前記第１取得ステップと前記算出ステップとをＬ（２以上の整数）回繰り返させ、前記第１取得ステップにより得られた第１データと該第１データに基づいて前記算出ステップにより得られた第２データとから成るＬ個のペアを出力する出力ステップと、前記Ｌ個のペアを分割して複数の情報送信装置に配布する配布ステップとをコンピュータに実行させるものである。
【００３２】
また、本発明は、複数の符号化されたデータから１つの元データへの復号をコンピュータに実行させる復号プログラムであって、複数の情報送信装置から送出される符号化データを受信する受信ステップと、前記符号化データに含まれる第１データと第２データとから成る複数個のペアを順次取得する第２取得ステップと、前記第２取得ステップにより取得された前記複数個のペアの取得順序に基づいて前記複数個の第１データに操作を行うことにより前記複数個の第１データを第３データに変換する第１操作ステップと、前記第２取得ステップにより取得された前記複数個のペアの取得順序に基づいて前記複数個の第２データに前記第１操作ステップと同一の操作を行うことにより前記複数個の第２データを第４データに変換する第２操作ステップとをコンピュータに実行させるものである。
【００３３】
また、本発明は、元データを分割することによりＮ（２以上の整数）個の部分データを生成し、該Ｎ個の部分データに順序を示す番号を付する分割部と、前記分割部により付されたＮ個の番号の中から少なくとも１つの番号を指定するデータである第１データを取得する第１取得部と、前記第１取得部により取得された第１データにより指定された番号が付された部分データに対して所定の演算を行うことにより第２データを算出する算出部と、前記第１取得部の処理と前記算出部の処理とをＬ（２以上の整数）回繰り返させ、前記第１取得部により得られた第１データと該第１データに基づいて前記算出部により得られた第２データとから成るＬ個のペアを出力する出力部と、前記出力部により出力されたＬ個のペアを分割して配布する配布部と、前記配布部により配布された複数個のペアを順次取得する第２取得部と、前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第１データに操作を行うことにより前記複数個の第１データを第３データに変換する第１操作部と、前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第２データに前記第１操作部と同一の操作を行うことにより前記複数個の第２データを第４データに変換する第２操作部とを備えたものである。
【発明の効果】
【００３４】
本発明によれば、効率よくデータを分散して転送し、復元することができる。
【発明を実施するための最良の形態】
【００３５】
以下、本発明の実施の形態について図面を参照しつつ説明する。
【００３６】
本実施の形態においては、本発明に係るデータ転送システム及びデータ転送方法を適用したマルチキャスト配信システムについて説明する。
【００３７】
まず、マルチキャスト配信システムの構成について説明する。
【００３８】
図１は、本実施の形態に係るマルチキャスト配信システムの構成の一例を示すブロック図である。このマルチキャスト配信システムは、分散装置（符号化装置）１、送信装置２ａ，２ｂ、受信装置（復号装置）３ａ，３ｂ，３ｃを備える。分散装置１と送信装置２ａ、分散装置１と送信装置２ｂは、それぞれネットワークを介して接続されている。送信装置２ａと受信装置３ａ，３ｂ，３ｃ、送信装置２ｂと受信装置３ａ，３ｂ，３ｃは、それぞれネットワークを介して接続されている。
【００３９】
図２は、本実施の形態に係るマルチキャスト配信システムにおける各装置の構成の一例を示すブロック図である。分散装置１は、通信部１１、記憶部１２、符号化部１３、符号化行列生成部１４を備える。送信装置２ａ，２ｂは同様の構成であり、通信部２１、記憶部２２を備える。受信装置３ａ，３ｂ，３ｃは同様の構成であり、通信部３１、記憶部３２、復号部３３を備える。
【００４０】
次に、マルチキャスト配信システムの動作について説明する。
【００４１】
このマルチキャスト配信システムは、分散装置１が元データをｎ（請求項におけるＮ、２以上の整数）個の部分データに分割し、符号化行列を用いてｌ（請求項におけるＬ、２以上の整数）個の符号化データに符号化し、符号化データを送信装置２ａ，２ｂへ送信する。送信装置２ａ，２ｂはそれぞれ、受信した符号化データをマルチキャストにより受信装置３ａ，３ｂ，３ｃへ送信する。受信装置３ａ，３ｂ，３ｃはそれぞれ、受信した符号化データを復号し、元データを復元するものである。
【００４２】
まず、分散装置１による符号化行列生成処理について説明する。
【００４３】
図３は、本実施の形態に係る符号化行列生成処理の一例を示すフローチャートである。まず、符号化行列生成部１４は、符号化行列の列数（部分データ数）ｎと符号化行列の行数（符号化データの最大数）ｌを決定する（Ｓ１１）。ここで、元データＤは、ｎ個の部分データ｛Ｄ1，Ｄ2，…，Ｄn｝に分割され、ｎ個の部分データが符号化データに変換され、ｍ台の送信装置に分散され、受信装置へ送信されるとする。ｎは任意の数であるが、大きいほど効率が良い。次に、符号化行列生成部１４は、部分データの総数に対する各送信装置が担当する部分データの個数の比である配布サイズ比（ｎを１として表す）をＳ1，Ｓ2，…Ｓmとし、Ｓ1，Ｓ2，…Ｓmの総和をＭとする。ここで、Ｓ1，Ｓ2，…Ｓmは、各送信装置の情報である送信装置情報に基づいて決定される。ここで、送信装置情報は、送信装置の記憶容量、通信速度、負荷等であり、例えば、記憶容量が大きい送信装置ｉほどＳiの値を大きくする。Ｓ1，Ｓ2，…Ｓmが変化する可能性がある場合、Ｍは、大きくしておく。次に、符号化行列生成部１４は、ｌ＝ｎ×Ｍとする。
【００４４】
次に、符号化行列生成部１４は、ｈ＝（Ｍ−１）×ｎとし、符号化行列Ａの各列における１の数がｈ個になるように、自然乱数を用いて０と１からなるｌ行ｎ列の符号化行列候補を生成する候補生成処理を行う（Ｓ１２）。ｈにより、符号化行列中の１の数は、０の数に比べて少ないという特徴がある。
【００４５】
次に、符号化行列生成部１４は、符号化行列候補の候補評価処理（Ｓ１３〜Ｓ１８）を行う。まず、符号化行列生成部１４は、ｋ＝１とし（Ｓ１３）、符号化行列候補の行のうちｋ行の組み合わせを取り出し、ｋ行の部分候補を生成する部分候補生成処理を行う（Ｓ１４）。次に、符号化行列生成部１４は、部分候補に対して後述する復号判定処理を行い、復号判定処理の回数、復号判定処理により復号可能と判定された回数を記録する（Ｓ１５）。次に、符号化行列生成部１４は、ｋ行の組み合わせの全てを取り出したか否かの判断を行い、まだ全てを取り出していない場合（Ｓ１６，ＮＯ）、処理Ｓ１４へ移行し、符号化行列生成部１４は、次の組み合わせを取り出す。組み合わせの全てを取り出した場合（Ｓ１６，ＹＥＳ）、符号化行列生成部１４は、ｋ＞ｌ−ｎの条件を満たすか否かの判断を行い、この条件を満たさない場合（Ｓ１７，ＮＯ）、符号化行列生成部１４は、ｋを１増加させ、処理Ｓ１４へ移行する。この条件を満たす場合（Ｓ１７，ＹＥＳ）、符号化行列生成部１４は、（復号効率）＝（復号可能と判定された回数）／（復号判定処理の回数）とし、生成された符号化行列候補の中で最も復号効率の高いものを記憶部１２に保存しておく（Ｓ１８）。
【００４６】
ｋが大きくなるとｋ行の組み合わせ数が膨大になるため、符号化行列生成部１４は、適当な条件（例えば、ｋが所定の値を超えた場合）で候補評価処理を終了する。
【００４７】
次に、符号化行列生成部１４は、候補生成処理と候補評価処理を所定の回数だけ繰り返したか否かの判断を行い、所定の回数だけ繰り返していない場合（Ｓ１９，ＮＯ）、処理Ｓ１２へ戻り、所定の回数だけ繰り返した場合（Ｓ１９，ＹＥＳ）、このフローを終了する。符号化行列生成部１４は、記憶部１２に保存された符号化行列候補、即ち最も復号効率の高い符号化行列候補を符号化行列Ａとする。
【００４８】
図４は、本実施の形態に係る符号化行列の一例を示す図である。ここでは、部分データ数ｎ＝８、送信装置数ｍ＝２とする。送信装置２ａの記憶容量が送信装置２ｂの記憶容量より大きいなどの理由により、配布サイズ比は、Ｓ1＝４／４＝１、Ｓ2＝３／４＝０．７５とする。従って、Ｍ＝１．７５、ｌ＝１４となり、符号化行列Ａは１４行８列となる。
【００４９】
この符号化生成処理によれば、復号効率の高い符号化行列Ａを生成することができる。
【００５０】
なお、符号化行列Ａは、予め外部で生成され、分散装置１に格納されても良い。この場合、分散装置１は、符号化行列生成部１４を必要としない。
【００５１】
次に、分散装置１による分散処理について説明する。
【００５２】
図５は、本実施の形態に係る分散処理の一例を示すフローチャートである。予め生成された符号化行列ＡにおけるＭをＭ0とする。まず、符号化行列生成部１４は、送信に使用する送信装置２ａ，２ｂの送信装置情報を収集する（Ｓ３１）。次に、符号化行列生成部１４は、送信装置情報に基づいて送信装置２ａ，２ｂの配布サイズ比Ｓ1，Ｓ2を決定し、Ｓ1，Ｓ2の総和をＭとする（Ｓ３２）。符号化行列生成部１４は、ＭがＭ0より大きいか否かの判断を行う（Ｓ３３）。ＭがＭ0より大きい場合（Ｓ３３，Ｙ）、符号化行列生成部１４は、Ｍの値を用いて新たな符号化行列Ａの生成を行う符号化行列生成処理を行い（Ｓ３４）、処理Ｓ３５へ移行する。ＭがＭ0より大きくない場合（Ｓ３３，Ｎ）、処理Ｓ３５へ移行する。
【００５３】
次に、符号化部１３は、記憶部１２に格納された元データＤの符号化処理を行うことにより、ｌ個の符号化データを生成する（Ｓ３５）。符号化データは、ヘッダ部とデータ部からなり、請求項における第１データと第２データからなるペアに対応する。次に、通信部１１は、ｌ個の符号化データのうちｌ×Ｓ1／Ｍ個の符号化データを送信装置２ａへ送信し、ｌ×Ｓ2／Ｍ個の符号化データを送信装置２ｂへ送信（配布）し（Ｓ３６）、このフローは終了する。
【００５４】
ｎ＝２、ｍ＝２、Ｓ1＝４／４＝１、Ｓ2＝３／４＝０．７５の場合、Ｍ＝１．７５、ｌ＝１４である。従って、分散処理により、元データから、８個の部分データが生成され、１４個の符号化データが生成され、分散装置１から送信装置２ａへｌ×Ｓ1／Ｍ＝８個の符号化データが送信され、分散装置１から送信装置２ｂへｌ×Ｓ2／Ｍ＝６個の符号化データが送信される。
【００５５】
この分散処理によれば、送信装置の性能差などに応じて、自由に配布サイズ比を決定することができることから、各送信装置が効率よく符号化データの送信を行うことができる。
【００５６】
次に、分散装置１による符号化処理について説明する。
【００５７】
図６は、本実施の形態に係る符号化処理の一例を示すフローチャートである。まず、符号化部１３は、記憶部１２に格納された元データＤをｎ個に分割し、番号を付して部分データ｛Ｄ1，Ｄ2，…，Ｄn｝を生成する（Ｓ４１）。次に、符号化部１３は、ｎ個目の部分データの長さが他の部分データの長さに対して不足しているか否かの判断を行い、短い場合（Ｓ４２，ＹＥＳ）、ｎ個目の部分データの不足分をダミーデータ（０など）で埋め（Ｓ４３）、次の処理へ移行し、ｎ個目の部分データの長さが他の部分データの長さと等しい場合（Ｓ４２，ＮＯ）、次の処理へ移行する。次に、符号化部１３は、符号化行列Ａから１行ずつを取得して選択データとし、選択データを符号化データのヘッダ部（第１データ）とする（Ｓ４４）。
【００５８】
次に、符号化部１３は、選択データ中のビットが１である位置の番号を取得し、この番号に対応する部分データを取得し、取得した部分データ同士についてビット位置毎の排他的論理和（ＸＯＲ）演算を行い、その結果を符号化データのデータ部とする（Ｓ４５）。
【００５９】
図７は、本実施の形態に係る符号化処理の一例を示す概念図である。ここでは、ｎ＝４の場合について説明する。処理Ｓ４１において、符号化部１３は、元データＤを部分データ｛Ｄ1，Ｄ2，Ｄ3，Ｄ4｝に分割する。処理Ｓ４４において、符号化部１３は、符号化行列Ａの１行ずつを取得して選択データ及びヘッダ部とする。ここでは、符号化行列Ａの１行目｛１，０，１，０｝を選択データとする。処理Ｓ４５において、符号化部１３は、選択データ中のビットが１である位置に従って部分データのうちＤ1とＤ3を取得し、Ｄ1とＤ3についてビット位置毎の排他的論理和演算を行い、その結果を符号化データのデータ部（第２データ）とする。次に、符号化部１３は、符号化行列Ａの２行目｛０，１，１，０｝以降についても同様の処理を繰り返す。
【００６０】
次に、符号化部１３は、ｌ個の選択データを取得し終えたか（ｌ個のデータ部を生成し終えたか）否かの判断を行う（Ｓ４６）。ｌ個の選択データを取得し終えていない場合（Ｓ４６，ＮＯ）、処理Ｓ４４へ戻り、符号化部１３は、次の選択データを取得する。ｌ個の選択データを取得し終えた場合（Ｓ４６，ＹＥＳ）、このフローは終了する。
【００６１】
この符号化処理により、選択データであるヘッダ部とし、部分データの演算結果であるデータ部とした符号化データを、ｌ個生成することができる。また、符号に用いる演算が排他的論理和演算であるため、分散装置の負担が小さく、高速に符号化を行うことができる。
【００６２】
次に、送信装置２ａ，２ｂによる送信処理について説明する。
【００６３】
送信装置２ａ，２ｂの通信部２１は、分散装置１から受信した幾つかの符号化データを記憶部２２へ格納する。次に、送信装置２ａ，２ｂの通信部２１は、記憶部２２に格納された符号化データを受信装置３ａ，３ｂ，３ｃへ送信する。
【００６４】
次に、受信装置３ａ，３ｂ，３ｃによる復号処理について説明する。
【００６５】
記憶部３２のスタックには、符号化データ長のスタックデータをｎ個だけスタックさせることができる。スタックデータは、符号化データと同様、ヘッダ部とデータ部を持つ。また、ｎ個のスタックデータのヘッダ部は、各スタックデータのヘッダ部を行とする行列として扱うことができ、ｎ個のスタックデータのデータ部は、各スタックデータのデータ部を行とする行列として扱うことができる。
【００６６】
図８は、本実施の形態に係る復号処理の一例を示すフローチャートである。まず、通信部３１は、送信装置２ａ，２ｂから１つの符号化データを受信する（Ｓ５１）。次に、復号部３３は、ｉ＝１とし（Ｓ５２）、符号化データのヘッダ部のｉ番目のビットが１であるか否かの判断を行う（Ｓ５３）。１でない場合（Ｓ５３，ＮＯ）、復号部３３は、ｉを１増加させ、処理Ｓ５３へ戻る。１である場合（Ｓ５３，ＹＥＳ）、復号部３３は、記憶部３２のスタック上にｉ番目のスタックデータが存在するか否かの判断を行う（Ｓ５４）。ｉ番目の符号化データが存在する場合（Ｓ５４，ＹＥＳ）、復号部３３は、符号化データとスタック上のｉ番目のスタックデータとについてビット位置毎の排他的論理和演算を行い、符号化データをその演算結果に更新する（Ｓ５５）。ｉ番目の符号化データが存在しない場合（Ｓ５４，ＮＯ）、復号部３３は、符号化データをスタックに乗せ、新たなスタックデータとする（Ｓ５６）。
【００６７】
次に、復号部３３は、スタックデータ数がｎ個以上であるか否かの判断を行う（Ｓ５７）。ｎ個以上でない場合（Ｓ５７，ＮＯ）、復号部３３は、処理Ｓ５１へ戻り、次の符号化データを受信する。ｎ個以上である場合（Ｓ５７，ＹＥＳ）、復号部３３は、スタックデータのヘッダ部分からなる行列であるヘッダ行列が上三角行列であるか否かの判断を行う（Ｓ５８）。上三角行列でない場合（Ｓ５８，ＮＯ）、復号部３３は、復号不可能であると判断し、処理Ｓ５１へ戻り、次の符号化データを受信する。上三角行列である場合（Ｓ５８，ＹＥＳ）、復号部３３は、復号可能であると判断し、ヘッダ行列を単位行列（第３データ）にする行列操作を施し（Ｓ５９）、スタックデータのデータ部からなる行列であるデータ行列に対して同じ行列操作を行う（Ｓ６０）。この行列操作により、データ行列は元の部分データを各行とする行列（第４データ）に変換され、このフローは終了する。
【００６８】
図９は、本実施の形態に係る復号処理の一例を示す概念図である。ここでは、ｎ＝４の場合について説明する。処理Ｓ５６までの処理により、復号部３３は、スタックにスタックデータを乗せる。これにより、スタックデータのヘッダ部はヘッダ行列の行となり、スタックデータのデータ部はデータ行列の行となる。処理Ｓ５８までの処理により、復号部３３は、ヘッダ行列を上三角行列化するまで行列操作を行い、更に、処理Ｓ５９により、復号部３３は、ヘッダ行列を単位行列化する行列操作を行う。処理Ｓ６０により、復号部３３は、ヘッダ行列に施した行列操作と同一の行列操作をデータ行列に施す。これにより、データ行列の各行は、元の部分データ｛Ｄ1，Ｄ2，Ｄ3，Ｄ4｝に変換される。
【００６９】
この復号処理において、復号部３３は、ガウス消去法を用いてヘッダ行列を単位行列にする。従って、ヘッダ行列が上三角行列になるまで符号化データの受信とヘッダ行列への行列操作とを続け、行列操作によりヘッダ行列が上三角行列になると復号可能であると判断し、更なる行列操作によりヘッダ行列を単位行列にする。なお、ヘッダ行列を単位行列にする操作であれば、ガウス消去法以外の方法を用いても良い。
【００７０】
この復元処理によれば、ｎ個以上の符号化データのデータ部から元データを復号することができる。復号に必要な符号化データの数は、どの符号化行列Ａを用いるかにより異なる。符号化行列Ａの１の配置はランダムであるほど復号効率が高い。また、復号に用いる演算が排他的論理和演算であるため、受信装置の負担が小さく、高速に復号を行うことができる。
【００７１】
次に、分散装置１による復号判定処理について説明する。
【００７２】
符号化行列生成部１４は、復号判定処理として、上述した復号処理のうち処理Ｓ５１〜Ｓ５８を実行するが、符号化データのヘッダ部の受信の代わりに部分候補の各行の入力を行う。符号化行列生成部１４は、処理Ｓ５８においてヘッダ行列が上三角行列になった場合に復号可能であると判定し、部分候補の全ての行を入力してもヘッダ行列が上三角行列にならない場合に復号不可能であると判定する。
【００７３】
復号処理及び復号判定処理によれば、受信装置３ａ，３ｂ，３ｃは、ｌ個の符号化データのうち、ｎ＋α（１＜α≦（ｌ−ｎ））個以上符号化データを正常に受信できれば、元データの復号が可能になる。上述した復号効率と同様、αの値は、符号化行列Ａにより異なり、αが最も小さい（１に近い）符号化行列候補を符号化行列Ａとして採用しても良い。
【００７４】
本実施の形態によれば、送信装置が送信すべきデータ量を少なくすることができると共に、受信装置は全ての符号化データを受信しなくても復元することができる。結果として、データの転送にかかる時間的な効率を改善することができる。
【００７５】
なお、分割部、第１取得部、算出部、出力部は、実施の形態における符号化部１３に対応する。また、生成部は、実施の形態における符号化行列生成部１４に対応する。配布部は、実施の形態における通信部１１に対応する。また、第２取得部は、実施の形態における通信部３１に対応する。また、第１操作部及び第２操作部は、実施の形態における復号部３３に対応する。
【００７６】
また、分割ステップは、実施の形態における処理Ｓ４１〜Ｓ４３に対応する。また、第１取得ステップは、実施の形態における処理Ｓ４４に対応する。また、算出ステップは、実施の形態における処理Ｓ４５に対応する。また、出力ステップは、実施の形態における処理Ｓ４６に対応する。また、配布ステップは、実施の形態における処理Ｓ３６に対応する。また、第２取得ステップは、実施の形態における処理Ｓ５１に対応する。また、第１操作ステップは、実施の形態における処理Ｓ５２〜Ｓ５９に対応する。また、第２操作ステップは、実施の形態における処理Ｓ６０に対応する。
【００７７】
また、本実施の形態に係る符号化装置及び復号装置は、情報処理装置に容易に適用することができ、情報処理装置の性能をより高めることができる。ここで、情報処理装置には、例えばサーバ、ＰＣ（Personal Computer）等が含まれ得る。
【００７８】
更に、符号化装置及び復号装置を構成するコンピュータにおいて上述した各ステップを実行させるプログラムを、それぞれ符号化プログラム及び復号プログラムとして提供することができる。上述したプログラムは、コンピュータにより読取り可能な記録媒体に記憶させることによって、それぞれ符号化装置及び復号装置を構成するコンピュータに実行させることが可能となる。ここで、上記コンピュータにより読取り可能な記録媒体としては、ＲＯＭやＲＡＭ等のコンピュータに内部実装される内部記憶装置、ＣＤ−ＲＯＭやフレキシブルディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカード等の可搬型記憶媒体や、コンピュータプログラムを保持するデータベース、或いは、他のコンピュータ並びにそのデータベースや、更に回線上の伝送媒体をも含むものである。
【００７９】
（付記１）  １つの元データから複数の符号化されたデータへの符号化を行う符号化装置であって、
元データを分割することによりＮ（２以上の整数）個の部分データを生成し、該Ｎ個の部分データに順序を示す番号を付する分割部と、
前記分割部により付されたＮ個の番号の中から少なくとも１つの番号を指定するデータである第１データを取得する第１取得部と、
前記第１取得部により取得された第１データにより指定された番号が付された部分データに対して所定の演算を行うことにより第２データを算出する算出部と、
前記第１取得部の処理と前記算出部の処理とをＬ（２以上の整数）回繰り返させ、前記第１取得部により得られた第１データと該第１データに基づいて前記算出部により得られた第２データとから成るＬ個のペアを出力する出力部と、
前記Ｌ個のペアを分割して複数の情報送信装置に配布する配布部と、
を備える符号化装置。
（付記２）  付記１に記載の符号化装置において、
前記所定の演算は、前記第１データにより指定された番号が付された部分データ同士のビット位置毎の排他的論理和演算であることを特徴とする符号化装置。
（付記３）  付記１または付記２に記載の符号化装置において、
前記分割部は、前記Ｎ個の部分データの長さを揃えることを特徴とする符号化装置。
（付記４）  付記１乃至付記３のいずれかに記載の符号化装置において、
第１データは、Ｎビットのビット列であり、第１データのうち少なくとも１ビットの値が１であり、該値が１であるビットのビット位置が前記番号に対応し、Ｌ回の前記第１取得部の処理により取得されるＬ個の第１データはそれぞれ異なることを特徴とする符号化装置。
（付記５）  付記１乃至付記４のいずれかに記載の符号化装置において、
Ｌ回の前記第１取得部の処理により取得されるＬ個の第１データ中の１の数は、０の数より少ないことを特徴とする符号化装置。
（付記６）  付記１乃至付記５のいずれかに記載の符号化装置において、
更に、少なくともＬ個のそれぞれ異なる第１データを生成する生成部を備えることを特徴とする符号化装置。
（付記７）  付記６に記載の符号化装置において、
前記生成部は、乱数に基づいて少なくともＬ個の第１データの候補を生成し、前記第１データの候補の中から少なくともＮ個である複数個の第１データの候補を順次取得し、該取得順序に基づいて前記複数個の第１データの候補に操作を行うことにより前記複数個の第１データの候補を所定のデータに変換することが可能であるか否かの判断を行い、該変換が可能である場合、前記複数個の第１データの候補の数に基づいて前記少なくともＬ個の第１データの候補を第１データとして採用するか否かの判断を行うことを特徴とする符号化装置。
（付記８）  複数の符号化されたデータから１つの元データへの復号を行う復号装置であって、
複数の情報送信装置から送出される符号化データを受信する受信部と、
前記符号化データに含まれる第１データと第２データとから成る複数個のペアを順次取得する第２取得部と、
前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第１データに操作を行うことにより前記複数個の第１データを第３データに変換する第１操作部と、
前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第２データに前記第１操作部と同一の操作を行うことにより前記複数個の第２データを第４データに変換する第２操作部と、
を備える復号装置。
（付記９）  付記８に記載の復号装置において、
全ての前記第１データの長さは、Ｎ（２以上の整数）ビットであり、
前記第３データは、Ｎ行Ｎ列の単位行列であり
前記第４データは、Ｎ行の行列であり、
前記第２取得部は、少なくともＮ個の前記ペアを取得することを特徴とする復号装置。
（付記１０）  付記９に記載の復号装置において、
前記第２操作部は更に、前記第４データの各行を順に連結して１つのデータとして出力することを特徴とする復号装置。
（付記１１）  付記９または付記１０に記載の復号装置において、
前記第１操作部は、前記Ｎ個の第１データに操作を行うことにより前記Ｎ個の第１データを上三角行列に変換できない場合、前記第２取得部に更にペアを取得させることを特徴とする復号装置。
（付記１２）  付記９乃至付記１１のいずれかに記載の復号装置において、
前記操作は、ガウスの消去法を用いることを特徴とする復号装置。
（付記１３）  １つの元データから複数の符号化されたデータへの符号化をコンピュータに実行させる符号化プログラムであって、
元データを分割することによりＮ（２以上の整数）個の部分データを生成し、該Ｎ個の部分データに順序を示す番号を付する分割ステップと、
前記分割ステップにより付されたＮ個の番号の中から少なくとも１つの番号を指定するデータである第１データを取得する第１取得ステップと、
前記第１取得ステップにより取得された第１データにより指定された番号が付された部分データに対して所定の演算を行うことにより第２データを算出する算出ステップと、
前記第１取得ステップと前記算出ステップとをＬ（２以上の整数）回繰り返させ、前記第１取得ステップにより得られた第１データと該第１データに基づいて前記算出ステップにより得られた第２データとから成るＬ個のペアを出力する出力ステップと、
前記Ｌ個のペアを分割して複数の情報送信装置に配布する配布ステップと、
をコンピュータに実行させる符号化プログラム。
（付記１４）  複数の符号化されたデータから１つの元データへの復号をコンピュータに実行させる復号プログラムであって、
複数の情報送信装置から送出される符号化データを受信する受信ステップと、
前記符号化データに含まれる第１データと第２データとから成る複数個のペアを順次取得する第２取得ステップと、
前記第２取得ステップにより取得された前記複数個のペアの取得順序に基づいて前記複数個の第１データに操作を行うことにより前記複数個の第１データを第３データに変換する第１操作ステップと、
前記第２取得ステップにより取得された前記複数個のペアの取得順序に基づいて前記複数個の第２データに前記第１操作ステップと同一の操作を行うことにより前記複数個の第２データを第４データに変換する第２操作ステップと、
をコンピュータに実行させる復号プログラム。
（付記１５）  元データを分割することによりＮ（２以上の整数）個の部分データを生成し、該Ｎ個の部分データに順序を示す番号を付する分割部と、
前記分割部により付されたＮ個の番号の中から少なくとも１つの番号を指定するデータである第１データを取得する第１取得部と、
前記第１取得部により取得された第１データにより指定された番号が付された部分データに対して所定の演算を行うことにより第２データを算出する算出部と、
前記第１取得部の処理と前記算出部の処理とをＬ（２以上の整数）回繰り返させ、前記第１取得部により得られた第１データと該第１データに基づいて前記算出部により得られた第２データとから成るＬ個のペアを出力する出力部と、
前記出力部により出力されたＬ個のペアを分割して配布する配布部と、
前記配布部により配布された複数個のペアを順次取得する第２取得部と、
前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第１データに操作を行うことにより前記複数個の第１データを第３データに変換する第１操作部と、
前記第２取得部により取得された前記複数個のペアの取得順序に基づいて前記複数個の第２データに前記第１操作部と同一の操作を行うことにより前記複数個の第２データを第４データに変換する第２操作部と、
を備えるデータ転送システム。
【図面の簡単な説明】
【００８０】
【図１】本実施の形態に係るマルチキャスト配信システムの構成の一例を示すブロック図である。
【図２】本実施の形態に係るマルチキャスト配信システムにおける各装置の構成の一例を示すブロック図である。
【図３】本実施の形態に係る符号化行列生成処理の一例を示すフローチャートである。
【図４】本実施の形態に係る符号化行列の一例を示す図である。
【図５】本実施の形態に係る分散処理の一例を示すフローチャートである。
【図６】本実施の形態に係る符号化処理の一例を示すフローチャートである。
【図７】本実施の形態に係る符号化処理の一例を示す概念図である。
【図８】本実施の形態に係る復号処理の一例を示すフローチャートである。
【図９】本実施の形態に係る復号処理の一例を示す概念図である。
【図１０】従来のデータ転送方式Ａの動作の一例を示すブロック図である。
【図１１】従来のデータ転送方式Ｂの動作の一例を示すブロック図である。
【符号の説明】
【００８１】
１  分散装置、２ａ，２ｂ  送信装置、３ａ，３ｂ，３ｃ  受信装置、１１  通信部、１２  記憶部、１３  符号化部、１４  符号化行列生成部、２１  通信部、２２  記憶部、３１  通信部、３２  記憶部、３３  復号部。
【図１】
2008172617.tif 000005
【図２】
2008172617.tif 000006
【図３】
2008172617.tif 000007
【図４】
2008172617.tif 000008
【図５】
2008172617.tif 000009
【図６】
2008172617.tif 000010
【図７】
2008172617.tif 000011
【図８】
2008172617.tif 000012
【図９】
2008172617.tif 000013
【図１０】
2008172617.tif 000014
【図１１】
2008172617.tif 000015