(57)【要約】【課題】より好適にパケットデータを取得し、データの再生を行う。【解決手段】ステップＳ２３において、ロスしたパケットが存在すると判定した場合、クライアントのデータ再生部は、取得したパケットおよび情報をパケット復元部に供給する。パケット復元部は、ステップＳ２４において、リードソロモン符号冗長パケットによるデータパケットの復元が可能であるか否かを判定する。復元可能である場合、パケット復元部は、ステップＳ２５において、ロスしたデータパケットの、リードソロモン符号冗長パケットを用いた復元処理を実行する。復元不可能である場合、パケット復元部は、ステップＳ２９において、ロスしたデータパケットの、ＥＯＲ冗長パケットを用いた復元処理を実行する。本発明は、ストリーミングデータ配信システムに適用できる。【選択図】      図７
2004165922.tif 000002
【特許請求の範囲】
【請求項１】
他の情報処理装置から配信用データを受信する情報処理装置において、
前記他の情報処理装置により送信された、前記配信用データのデータパケット、複数の前記データパケットに含まれる各データに基づいて生成されたリードソロモン符号を含む第１の冗長パケット、並びに、複数の前記データパケットに含まれる各データの排他的論理和演算結果を含む第２の冗長パケットを受信する受信手段と、
前記受信手段により受信できなかった前記データパケットを、前記受信手段により受信された前記第１の冗長パケットを用いて復元可能であるか否かを判定する可能性判定手段と、
前記可能性判定手段による判定結果に基づいて、復元可能である場合、前記受信手段により受信された前記データパケットおよび前記第１の冗長パケットを用いて、前記受信手段により受信できなかった前記データパケットを復元する第１の復元手段と、
前記可能性判定手段による判定結果に基づいて、復元不可能である場合、前記受信手段により受信された前記データパケットおよび前記第２の冗長パケットを用いて、前記受信手段により受信できなかった前記データパケットを復元する第２の復元手段と
を備えることを特徴とする情報処理装置。
【請求項２】
前記第１の冗長パケットは、所定の大きさに分割された前記配信用データであるブロック毎に、同一の前記ブロックに対応する全ての前記データパケットを用いて生成され、
前記第２の冗長パケットは、同一の前記ブロックに対応する、任意に選択された複数の前記データパケットを用いて、前記ブロック毎に生成される
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記データパケット、前記第１の冗長パケット、および前記第２の冗長パケットは、前記ブロック単位で前記他の情報処理装置より送信される
ことを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記受信手段は、同一の前記ブロックの前記データパケット、前記第１の冗長パケット、および前記第２の冗長パケットの受信処理が完了したか否かを監視する監視手段をさらに備える
ことを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記受信手段により受信できなかった前記データパケットが存在するか否かを判定する存在判定手段をさらに備える
ことを特徴とする請求項１に記載の情報処理装置。
【請求項６】
前記第２の冗長パケットの生成に関する情報を前記他の情報処理装置と共有する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項７】
前記可能性判定手段は、前記受信手段により受信できなかった前記データパケットの数と、前記受信手段により受信された前記第１の冗長パケットの数とを比較して、前記受信手段により受信できなかった前記データパケットを復元可能であるか否かを判定する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項８】
前記第１の復元手段は、前記第１の冗長パケットに含まれる前記リードソロモン符号を復号することによって、前記受信手段により受信できなかった前記データパケットを復元する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項９】
前記第２の復元手段は、値が０でない係数を選択するための処理方法であるピボット選択を用いたガウス消去法を用いて、前記受信手段により受信された前記データパケットおよび前記第２の冗長パケットに基づいて生成された連立一次方程式を解くことによって、前記受信手段により受信できなかった前記データパケットを復元する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項１０】
前記復元手段は、前記行列の所定の列について値が０でない係数を含む方程式のうち、隣り合う方程式同士で各項毎に排他的論理和を演算する応用ガウス消去法を用いて、前記受信手段により受信された前記データパケットおよび前記第２の冗長パケットに基づいて生成された連立一次方程式を解くことによって、前記受信手段により受信できなかった前記データパケットを復元する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項１１】
他の情報処理装置から配信用データを受信する情報処理装置の情報処理方法であって、
前記他の情報処理装置により送信された、前記配信用データのデータパケット、複数の前記データパケットに含まれる各データに基づいて生成されたリードソロモン符号を含む第１の冗長パケット、並びに、複数の前記データパケットに含まれる各データの排他的論理和演算結果を含む第２の冗長パケットの受信を制御する受信制御ステップと、
前記受信制御ステップの処理により受信できなかった前記データパケットを、前記受信制御ステップの処理により受信された前記第１の冗長パケットを用いて復元可能であるか否かを判定する可能性判定ステップと、
前記可能性判定ステップの処理による判定結果に基づいて、復元可能である場合、前記受信制御ステップの処理により受信された前記データパケットおよび前記第１の冗長パケットを用いて、前記受信制御ステップの処理により受信できなかった前記データパケットを復元する第１の復元ステップと、
前記可能性判定ステップの処理による判定結果に基づいて、復元不可能である場合、前記受信制御ステップの処理により受信された前記データパケットおよび前記第２の冗長パケットを用いて、前記受信制御ステップの処理により受信できなかった前記データパケットを復元する第２の復元ステップと
を含むことを特徴とする情報処理方法。
【請求項１２】
他の情報処理装置から配信用データを受信する処理をコンピュータに行わせるプログラムにおいて、
前記他の情報処理装置により送信された、前記配信用データのデータパケット、複数の前記データパケットに含まれる各データに基づいて生成されたリードソロモン符号を含む第１の冗長パケット、並びに、複数の前記データパケットに含まれる各データの排他的論理和演算結果を含む第２の冗長パケットの受信を制御する受信制御ステップと、
前記受信制御ステップの処理により受信できなかった前記データパケットを、前記受信制御ステップの処理により受信された前記第１の冗長パケットを用いて復元可能であるか否かを判定する可能性判定ステップと、
前記可能性判定ステップの処理による判定結果に基づいて、復元可能である場合、前記受信制御ステップの処理により受信された前記データパケットおよび前記第１の冗長パケットを用いて、前記受信制御ステップの処理により受信できなかった前記データパケットを復元する第１の復元ステップと、
前記可能性判定ステップの処理による判定結果に基づいて、復元不可能である場合、前記受信制御ステップの処理により受信された前記データパケットおよび前記第２の冗長パケットを用いて、前記受信制御ステップの処理により受信できなかった前記データパケットを復元する第２の復元ステップと
を含むことを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は情報処理装置および方法、並びにプログラムに関し、特に、より好適にパケットデータを取得し、データの再生を行うことができるようにした、情報処理装置および方法、並びにプログラムに関する。
【０００２】
【従来の技術】
近年、ブロードバンド通信網の発達などにより、インターネットに代表されるネットワークを介して、ユニキャストやマルチキャストでの、音声や映像等のデータのストリーミング配信やリアルタイムな放送などが数多く行われるようになってきた。
【０００３】
従来、このようなネットワークを介した通信において、ＵＤＰ／ＩＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）を用いたユニキャストやマルチキャスト等の配信に、ブロック内のデータ誤りを検出し訂正するブロック符号の１つであるリードソロモン符号等を用いたＦＥＣ（Ｆｏｒｗａｒｄ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ）を併用した配信方式が提案されている（例えば、非特許文献１乃至３参照）。
【０００４】
リードソロモン符号によるパケットロスに対するエラー訂正処理において、送信側では、所定の大きさのブロック単位ごとに、送信データの誤り訂正コードが生成され、その誤り訂正コードより冗長パケットが生成され、その生成された冗長パケットが、パケット化された送信データとともに配信される。
【０００５】
そして、受信側では、パケット化された送信データとともに冗長パケットも受信し、送信データのパケットのロスが生じた場合、そのパケットを、受信した冗長パケットを用いて復元する。ロスしたパケットの復元が不可能である場合は、送信側に対して、ロスしたパケットの再送が要求される。
【０００６】
また、ＦＥＣの符号化方式の例として、リードソロモン符号方式の代わりに、ＥＯＲ（ｅｘｃｌｕｓｉｖｅ  ＯＲ）演算を用いて冗長パケットを生成する方式もある（例えば、特許文献１参照）。
【０００７】
ＥＯＲ演算を用いた、パケットロスに対するエラー訂正処理において、送信側では、所定の大きさのブロック単位ごとに、ＥＯＲ演算を用いて、送信データの誤り訂正コードが生成され、その誤り訂正コードより冗長パケットが生成され、その生成された冗長パケットが、パケット化された送信データとともに配信される。
【０００８】
そして、受信側では、パケット化された送信データとともに冗長パケットも受信し、送信データのパケットのロスが生じた場合、そのパケットを、受信した冗長パケットを用いて復元する。ロスしたパケットの復元が不可能である場合は、送信側に対して、ロスしたパケットの再送が要求される。
【０００９】
【非特許文献１】
米山  清二郎、外２名、“Ｒｅｌｉａｂｌｅ  Ｍｕｌｔｉｃａｓｔ  −  Ｕｓｉｎｇ  ＦＥＣ  ｏｎ  ＩＰ  ｖｅｒｓｉｏｎ６”、［ｏｎｌｉｎｅ］、平成１１年１２月１５日、インターネットコンファレンス、［平成１４年１０月８日検索］、インターネット，＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｉｎｔｅｒｎｅｔｃｏｎｆｅｒｅｎｃｅ．ｏｒｇ／ｉｃ９９／ｐｒｏｇｒａｍ．ｈｔｍｌ＞
【００１０】
【非特許文献２】
窪  貴志、“信頼性マルチキャストを用いた実時間メディア伝送に関する考察”、［ｏｎｌｉｎｅ］、平成１３年２月１８日、奈良先端科学技術大学院大学修士論文・課題研究発表会、［平成１４年１０月８日検索］、インターネット，＜ＵＲＬ：  ｈｔｔｐ：／／ｉｓｗ３．ａｉｓｔ−ｎａｒａ．ａｃ．ｊｐ／ＩＳ／ＭａｓｔｅｒＴｈｅｓｉｓ／２００１／００５１０３１．ｈｔｍｌ＞
【００１１】
【非特許文献３】
米山  清二郎、“ＦＥＣ  ｏｎ  ＩＰｖ６  ｆｏｒ  Ｒｅｌｉａｂｌｅ  Ｍｕｌｔｉｃａｓｔ”、［ｏｎｌｉｎｅ］、平成１２年１１月１日、インターネットコンファレンス、［平成１４年１０月８日検索］、インターネット，＜ＵＲＬ：  ｈｔｔｐ：／／ｗｗｗ．ｃｓｌ．ｓｏｎｙ．ｃｏ．ｊｐ／ｉｃ２０００／ｐａｐｅｒｓ／Ｓ０３＿０１．ｐｄｆ＞
【００１２】
【特許文献１】
特開２００１−１８９６６５号公報（第２５−２６ページ、図３）
【００１３】
【発明が解決しようとする課題】
しかしながら、以上のような方法において、ロスしたパケットを復元できない場合、再送処理を行わなければならないので、送信データを再生するまでに要する処理時間が長くなってしまうという課題があった。
【００１４】
特に、ストリーミング配信やリアルタイムのデータ配信において、受信側の装置は、順次送信されるデータを受信し、再生しなければならず、復元処理を短時間で行わなければならない。従って、上述したような処理時間の増大は、再生能力に大きく影響する。
【００１５】
本発明はこのような状況に鑑みてなされたものであり、より好適にパケットデータを取得し、データの再生を行うことができるようにしたものである。
【００１６】
【課題を解決するための手段】
本発明の情報処理装置は、他の情報処理装置により送信された、配信用データのデータパケット、複数のデータパケットに含まれる各データに基づいて生成されたリードソロモン符号を含む第１の冗長パケット、並びに、複数のデータパケットに含まれる各データの排他的論理和演算結果を含む第２の冗長パケットを受信する受信手段と、受信手段により受信できなかったデータパケットを、受信手段により受信された第１の冗長パケットを用いて復元可能であるか否かを判定する可能性判定手段と、可能性判定手段による判定結果に基づいて、復元可能である場合、受信手段により受信されたデータパケットおよび第１の冗長パケットを用いて、受信手段により受信できなかったデータパケットを復元する第１の復元手段と、可能性判定手段による判定結果に基づいて、復元不可能である場合、受信手段により受信されたデータパケットおよび第２の冗長パケットを用いて、受信手段により受信できなかったデータパケットを復元する第２の復元手段とを備えることを特徴とする。
【００１７】
前記第１の冗長パケットは、所定の大きさに分割された配信用データであるブロック毎に、同一のブロックに対応する全てのデータパケットを用いて生成され、第２の冗長パケットは、同一のブロックに対応する、任意に選択された複数のデータパケットを用いて、ブロック毎に生成されるようにすることができる。
【００１８】
前記データパケット、第１の冗長パケット、および第２の冗長パケットは、ブロック単位で他の情報処理装置より送信されるようにすることができる。
【００１９】
前記受信手段は、同一のブロックのデータパケット、第１の冗長パケット、および第２の冗長パケットの受信処理が完了したか否かを監視する監視手段をさらに備えるようにすることができる。
【００２０】
前記受信手段により受信できなかったデータパケットが存在するか否かを判定する存在判定手段をさらに備えるようにすることができる。
【００２１】
前記第２の冗長パケットの生成に関する情報を他の情報処理装置と共有するようにすることができる。
【００２２】
前記可能性判定手段は、受信手段により受信できなかったデータパケットの数と、受信手段により受信された第１の冗長パケットの数とを比較して、受信手段により受信できなかったデータパケットを復元可能であるか否かを判定するようにすることができる。
【００２３】
前記第１の復元手段は、第１の冗長パケットに含まれるリードソロモン符号を復号することによって、受信手段により受信できなかったデータパケットを復元するようにすることができる。
【００２４】
前記第２の復元手段は、値が０でない係数を選択するための処理方法であるピボット選択を用いたガウス消去法を用いて、受信手段により受信されたデータパケットおよび第２の冗長パケットに基づいて生成された連立一次方程式を解くことによって、受信手段により受信できなかったデータパケットを復元するようにすることができる。
【００２５】
前記復元手段は、行列の所定の列について値が０でない係数を含む方程式のうち、隣り合う方程式同士で各項毎に排他的論理和を演算する応用ガウス消去法を用いて、受信手段により受信されたデータパケットおよび第２の冗長パケットに基づいて生成された連立一次方程式を解くことによって、受信手段により受信できなかったデータパケットを復元するようにすることができる。
【００２６】
本発明の情報処理方法は、他の情報処理装置により送信された、配信用データのデータパケット、複数のデータパケットに含まれる各データに基づいて生成されたリードソロモン符号を含む第１の冗長パケット、並びに、複数のデータパケットに含まれる各データの排他的論理和演算結果を含む第２の冗長パケットの受信を制御する受信制御ステップと、受信制御ステップの処理により受信できなかったデータパケットを、受信制御ステップの処理により受信された第１の冗長パケットを用いて復元可能であるか否かを判定する可能性判定ステップと、可能性判定ステップの処理による判定結果に基づいて、復元可能である場合、受信制御ステップの処理により受信されたデータパケットおよび第１の冗長パケットを用いて、受信制御ステップの処理により受信できなかったデータパケットを復元する第１の復元ステップと、可能性判定ステップの処理による判定結果に基づいて、復元不可能である場合、受信制御ステップの処理により受信されたデータパケットおよび第２の冗長パケットを用いて、受信制御ステップの処理により受信できなかったデータパケットを復元する第２の復元ステップとを含むことを特徴とする。
【００２７】
本発明のプログラムは、他の情報処理装置により送信された、配信用データのデータパケット、複数のデータパケットに含まれる各データに基づいて生成されたリードソロモン符号を含む第１の冗長パケット、並びに、複数のデータパケットに含まれる各データの排他的論理和演算結果を含む第２の冗長パケットの受信を制御する受信制御ステップと、受信制御ステップの処理により受信できなかったデータパケットを、受信制御ステップの処理により受信された第１の冗長パケットを用いて復元可能であるか否かを判定する可能性判定ステップと、可能性判定ステップの処理による判定結果に基づいて、復元可能である場合、受信制御ステップの処理により受信されたデータパケットおよび第１の冗長パケットを用いて、受信制御ステップの処理により受信できなかったデータパケットを復元する第１の復元ステップと、可能性判定ステップの処理による判定結果に基づいて、復元不可能である場合、受信制御ステップの処理により受信されたデータパケットおよび第２の冗長パケットを用いて、受信制御ステップの処理により受信できなかったデータパケットを復元する第２の復元ステップとをコンピュータに実現させることを特徴とする。
【００２８】
本発明の情報処理装置および方法、並びにプログラムにおいては、他の情報処理装置により送信された、配信用データのデータパケット、複数のデータパケットに含まれる各データに基づいて生成されたリードソロモン符号を含む第１の冗長パケット、並びに、複数のデータパケットに含まれる各データの排他的論理和演算結果を含む第２の冗長パケットが受信され、受信できなかったデータパケットを、受信された第１の冗長パケットを用いて復元可能であるか否かが判定され、その判定結果に基づいて、復元可能である場合、受信されたデータパケットおよび第１の冗長パケットを用いて、受信できなかったデータパケットが復元され、復元不可能である場合、受信されたデータパケットおよび第２の冗長パケットを用いて、受信できなかったデータパケットが復元される。
【００２９】
【発明の実施の形態】
図１は、本発明を適用したデータ配信システムの基本的な構成例を表す図である。
【００３０】
図１において、サーバ１は、ストリーミング配信用の、画像や音声等のストリーミングデータを蓄積しており、インターネット等に代表されるネットワーク２を介して、配信を要求したクライアント３−１または３−２に対して、ストリーミング配信サービスを提供する。サーバ１は、クライアント３−１または３−２より供給された配信要求に基づいて、ユニキャストまたはマルチキャストでデータを配信する。
【００３１】
また、サーバ１は、カメラやマイク等の図示せぬ外部入力装置を介して入力された画像や音声等のデータを送信用のデータに変換し、配信を要求したクライアント３−１または３−２に、ネットワーク２を介してリアルタイムに配信（以下、ＬＩＶＥ配信と称する）する。
【００３２】
クライアント３−１および３−２は、ユーザに操作され、ネットワーク２を介してサーバ１にアクセスし、ユーザに指示されたデータの配信を要求する。そして、その要求に基づいて、サーバ１が要求されたデータのストリーミング配信またはＬＩＶＥ配信を行うと、クライアント３−１および３−２は、そのデータを受信し、処理を行い、受信したデータに対応する画像をディスプレイに表示したり、受信したデータに対応する音声をスピーカより出力したりする。
【００３３】
なお、クライアント３−１，３−２を個々に区別する必要がない場合、単にクライアント３と称する。
【００３４】
サーバ１は、後述するように、上述したストリーミング配信やＬＩＶＥ配信において、ＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｏｃｏｌ）／ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）プロトコルに、リードソロモン符号によって形成された冗長パケット、およびＥＯＲによって形成された冗長パケットによるＦＥＣを併用して、データを配信する。すなわち、サーバ１は、データをパケット化するとともに、パケット化されたデータ（以下、データパケットと称する）より誤り訂正用の冗長パケットを生成し、それらのデータパケットおよび冗長パケットをクライアント３に配信する。
【００３５】
データパケットおよび冗長パケットを受信したクライアント３は、リードソロモン符号による誤り訂正処理を行い、受信したパケットからロスしたデータパケットを復元する。リードソロモン符号による誤り訂正処理が不可能な場合、クライアント３は、ＥＯＲ演算による誤り訂正処理を行い、受信したパケットからロスしたデータパケットを復元する。クライアント３は、受信されたデータパケットと、復元されたデータパケットを用いて、データを再生する。
【００３６】
なお、リードソロモン符号による誤り訂正処理も、ＥＯＲ演算による誤り訂正処理も不可能な場合、クライアント３は、その部分の再生処理を省略し、次のブロックに処理を進める。
【００３７】
図２は、図１に示すサーバ１の構成例を示すブロック図である。
【００３８】
図２において、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１１は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１２に記憶されているプログラム、または記憶部３３からＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１３にロードされたプログラムに従って各種の処理を実行する。ＲＡＭ１３にはまた、ＣＰＵ１１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【００３９】
パケット生成部１４は、ＣＰＵ１１に制御され、記憶部３３または通信部３４より供給された配信用のデータ（以下、配信データと称する）をパケット化してデータパケットを生成し、そのデータパケットを通信部３４に供給する。また、パケット生成部１４は、ＣＰＵ１１に制御され、後述するように、生成したデータパケットから、リードソロモン符号を用いて生成した誤り訂正用の冗長パケット（以下、リードソロモン符号冗長パケットと称する）、および、ＥＯＲ演算を用いて生成した誤り訂正用の冗長パケット（以下、ＥＯＲ冗長パケットと称する）を生成する。
【００４０】
ＣＰＵ１１、ＲＯＭ１２、ＲＡＭ１３、およびパケット生成部１４は、バス２０を介して相互に接続されている。このバス２０にはまた、入出力インタフェース３０も接続されている。
【００４１】
入出力インタフェース３０には、キーボードやマウスなどよりなる入力部３１、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）やＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）などよりなるディスプレイ、およびスピーカなどよりなる出力部３２、ハードディスクなどにより構成される記憶部３３、並びに、ＬＡＮカード、モデム、およびターミナルアダプタなどにより構成される通信部３４が接続されている。
【００４２】
記憶部３３には、入力部３１または通信部３４を介して取得された配信データ、並びに、各種の処理を実行するためのデータやプログラム等が記憶されており、各部にそれらのデータやプログラムを供給する。
【００４３】
通信部３４は、ネットワーク２を介しての通信処理を行う。例えば、通信部３４は、ＣＰＵ１１に制御され、パケット生成部１４より供給されたストリーミング配信用データパケットを、ＵＤＰやＲＴＰ（Ｒｅａｌ−ｔｉｍｅ  Ｔｒａｎｓｐｏｒｔ  Ｐｒｏｔｏｃｏｌ）／ＲＴＳＰ（Ｒｅａｌ  Ｔｉｍｅ  Ｓｔｒｅａｍｉｎｇ  Ｐｒｏｔｏｃｏｌ）等の所定のプロトコルを用いて配信する。また、通信部３４は、ＣＰＵ１１に制御され、接続された外部入力装置より供給されるデータを取得し、ＲＡＭ１３、パケット生成部１４、または記憶部３３に供給する。
【００４４】
入出力インタフェース３０にはまた、必要に応じてドライブ４０が接続され、磁気ディスク４１、光ディスク４２、光磁気ディスク４３、或いは半導体メモリ４４などが適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部３３にインストールされる。
【００４５】
以上において、バス２０に接続されるパケット生成部１４がデータパケットおよび冗長パケットの生成処理を行うように説明したが、これに限らず、パケット生成部１４において行われるパケット生成処理の全部または一部が、通信部６４またはＣＰＵ１１において実行されるようにしてもよい。
【００４６】
図３は、図１に示すクライアント３の構成例を示すブロック図である。
【００４７】
図３において、ＣＰＵ６１は、ＲＯＭ６２に記憶されているプログラム、または記憶部８３からＲＡＭ６３にロードされたプログラムに従って各種の処理を実行する。ＲＡＭ６３にはまた、ＣＰＵ６１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【００４８】
データ再生部６４は、ＣＰＵ６１に制御され、通信部８４において受信したデータパケット、およびパケット復元部６５において復元されたデータパケットより配信データを再構成し、ＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）方式やＡＴＲＡＣ３（Ａｄａｐｔｉｖｅ  ＴＲａｎｓｆｏｒｍ  Ａｃｏｕｓｔｉｃ  Ｃｏｄｉｎｇ  ３）（登録商標）方式等でデータがエンコードされている場合、対応する方式でデコードするなどしてデータを再生し、その再生されたデータ（以下、再生データと称する）をＣＰＵ６１、ＲＡＭ６２、出力部８２、または記憶部８３に供給する。
【００４９】
パケット復元部６５は、ＣＰＵ６１に制御され、後述するように、通信部８４において受信したリードソロモン符号冗長パケット、または通信部８４において受信したＥＯＲ冗長パケットを用いて、ロスしたデータパケットの復元処理を行う。そして、パケット復元部６５は、復元したデータパケットをＣＰＵ６１、ＲＡＭ６３、または、データ再生部６４に供給する。
【００５０】
ＣＰＵ６１、ＲＯＭ６２、ＲＡＭ６３、データ再生部６４、およびパケット復元部６５は、バス７０を介して相互に接続されている。このバス７０にはまた、入出力インタフェース８０も接続されている。
【００５１】
入出力インタフェース８０には、キーボードやマウスなどよりなる入力部８１、ＣＲＴやＬＣＤなどよりなるディスプレイ、およびスピーカなどよりなる出力部８２、ハードディスクなどにより構成される記憶部８３、並びに、モデム、ＬＡＮカード、およびターミナルアダプタなどにより構成される通信部８４が接続されている。
【００５２】
入力部８１は、キーボードやマウスなどにより構成され、ユーザからの要求を受け付け、その情報をＣＰＵ６１やＲＡＭ６２に供給する。出力部８２は、データ再生部６４などより供給されたデータに対応する画像をディスプレイに表示したり、供給されたデータに対応する音声をスピーカより出力したりする。
【００５３】
記憶部８３には、入力部３１または通信部３４を介して供給された各種の処理を実行するためのデータやプログラム等が記憶されており、各部にそれらのデータやプログラムを供給する。
【００５４】
通信部８４は、ネットワーク２を介しての通信処理を行う。例えば、通信部８４は、ネットワーク２を介して、サーバ１よりストリーミング配信されたデータパケットや冗長パケットを、ＵＤＰやＲＴＰ／ＲＴＳＰ等の所定のプロトコルを用いて受信し、受信したパケットをＣＰＵ６１、ＲＡＭ６３、データ再生部６４、またはパケット復元部６５等に供給する。また、通信部８４は、配信要求などの、ＣＰＵ６１などより供給された各種の情報を、ネットワーク２を介してサーバ１に供給する。
【００５５】
入出力インタフェース８０にはまた、必要に応じてドライブ９０が接続され、磁気ディスク９１、光ディスク９２、光磁気ディスク９３、或いは半導体メモリ９４などが適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部８３にインストールされる。
【００５６】
以上において、バス７０に接続されたデータ再生部６４において、配信データの再構成やデコード等の再生処理が行われるように説明したが、これに限らず、上述したデータ再生部６４が行う処理の全部または一部が、通信部８４またはＣＰＵ６１において実行されるようにしてもよい。
【００５７】
同様に、バス７０に接続されたパケット復元部６５において行われる、ロスしたパケットの復元処理の全部または一部が、通信部８４またはＣＰＵ６１において実行されるようにしてもよい。
【００５８】
次に、サーバ１による配信データのストリーミング配信処理について説明する。クライアント３より配信要求を、ネットワーク２を介して取得したサーバ１のＣＰＵ１１は、要求された配信データを記憶部３３より取得し、パケット生成部１４に供給し、データ送信処理を開始する。図４のフローチャートを参照して、サーバ１によるデータ送信処理を説明する。
【００５９】
配信データを供給されたパケット生成部１４は、取得した配信データを、所定の大きさのブロック単位で処理する。パケット生成部１４は、ステップＳ１において、１ブロック分の配信データを分割してパケット化し、データパケットを生成する。
【００６０】
図５は、パケット生成部１４において生成される１ブロック分のデータパケットおよび冗長パケットの構成例を示す模式図である。図５においてＥＯＲ演算は、「＋」を用いて表す。また、四則演算は、ガロア体上で行われる。
【００６１】
図５において、データパケット１０１は、パケット１０１−１乃至１０１−Ｎにより構成される。各パケットには、１ブロック分の配信データが所定の大きさで分割されたデータＤ１乃至ＤＮが１つずつ含まれている。
【００６２】
すなわち、パケット生成部１４は、式（１）のような演算を行い、Ｎ個のデータＤ１乃至ＤＮから、Ｎ個の送信データＳ１乃至ＳＮを生成する。
【００６３】
【数１】
2004165922.tif 000003
【００６４】
式（１）において、四則演算はガロア体上において行われ、各成分の加算は、対応するビットごとのＥＯＲ演算を用いて行う。
【００６５】
式（１）において、右辺第１項は、Ｎ行Ｎ列の単位行列であり、送信データＳ１乃至ＳＮは、それぞれ、データＤ１乃至ＤＮより構成される。
【００６６】
図４に戻り、データパケットを生成したパケット生成部１４は、処理をステップＳ２に進め、生成したデータパケットを用いて、リードソロモン符号による冗長パケットを生成する。
【００６７】
図５において、リードソロモン符号冗長パケット１０２は、パケット１０２−１乃至１０２−Ｍにより構成される。パケット生成部１４は、データＤ１乃至ＤＮに所定の係数を乗算し、それらの値のＥＯＲ演算を行う。パケット生成部１４は、この処理をＭ回繰り返して誤り訂正用の冗長データを生成し、さらにパケット化して誤り訂正用のリードソロモン符号冗長パケット１０２であるパケット１０２−１乃至１０２−Ｍを生成する。すなわち、パケット生成部１４は、以下に示される式（２）のような演算を行い、Ｎ個のデータＤ１乃至ＤＮから、Ｍ個の送信データＳＮ＋１乃至ＳＮ＋Ｍを生成する。
【００６８】
【数２】
2004165922.tif 000004
【００６９】
式（２）において、右辺第１項はＭ行Ｎ列の行列であり、リードソロモン符号冗長パケット１０２に対応する送信データＳＮ＋１乃至ＳＮ＋Ｍを生成するための係数である。この行列において、第Ｘ行第Ｙ列の成分ＡＸＹの値は、式（３）のように設定される。
【００７０】
【数３】
2004165922.tif 000005
【００７１】
なお、式（２）および式（３）において、四則演算はガロア体上において行われ、各成分の加算は、対応するビットごとのＥＯＲ演算を用いて行われる。
【００７２】
また、式（２）の右辺第１項の行列は、演算に用いられるまでに生成されていれば、どのようなタイミングで生成されてもよく、データ送信処理を行う前より予め準備されていてもよいし、演算の際に算出されるようにしてもよい。
【００７３】
図４に戻り、リードソロモン符号冗長パケット１０２を生成したパケット生成部１４は、ステップＳ３において、生成したデータパケットを用いて、ＥＯＲによる冗長パケットを生成する。
【００７４】
図５において、ＥＯＲ冗長パケット１０３は、パケット１０３−１乃至１０３−Ｌにより構成される。パケット生成部１４は、データＤ１乃至ＤＮより任意のデータを抽出し、それらの値のＥＯＲ演算を行う。パケット生成部１４は、この処理をＬ回繰り返して誤り訂正用の冗長データを生成し、さらにパケット化して誤り訂正用のＥＯＲ冗長パケット１０３であるパケット１０３−１乃至１０３−Ｌを生成する。すなわち、パケット生成部１４は、以下に示される式（４）のような演算を行い、Ｎ個のデータＤ１乃至ＤＮから、Ｌ個の送信データＳＮ＋Ｍ＋１乃至ＳＮ＋Ｍ＋Ｌを生成する。
【００７５】
【数４】
2004165922.tif 000006
【００７６】
式（４）において、右辺第１項はＬ行Ｎ列の行列であり、ＥＯＲ冗長パケット１０３に対応する送信データＳＮ＋Ｍ＋１乃至ＳＮ＋Ｍ＋Ｌを生成するための係数である。
【００７７】
なお、式（４）において、四則演算はガロア体上において行われ、各成分の加算は、対応するビットごとのＥＯＲ演算を用いて行われる。
【００７８】
式（４）の右辺第１項の行列は、例えば、ランダム関数等を用いて、「０」または「１」のいずれかの値がランダムに設定される。なお、ＥＯＲ演算されるデータの個数はいくつであってもでもよいが、各冗長パケット間でその個数を統一したり、所定の個数以上に限定したりする等、個数の範囲に制限を設けるようにしてもよい。
【００７９】
また、式（４）の右辺第１項の行列は、演算に用いられるまでに生成されていれば、どのようなタイミングで生成されてもよく、データ送信処理を行う前より予め準備されていてもよいし、演算の際に算出されるようにしてもよい。さらに、この行列は、ブロック毎に異なる成分で構成される行列を使用するようにしてもよいし、全てのブロックにおいて共通の行列を使用するようにしてもよい。
【００８０】
さらに、演算に使用された式（４）の右辺第１項の行列は、後述するように、データを受信するクライアント３によるパケット復元処理においても使用される。すなわち、データの授受を行うサーバ１およびクライアント３において、同じブロックに対しては、共通の行列を用いて処理できるように、式（４）の右辺第１項の行列に関する情報を共有する必要がある。この情報の共有は、どのような方法で行うようにしてもよく、例えば、クライアント３がサーバ１にデータの配信を要求する際に行うようにしてもよいし、サーバ１で使用された式（４）の右辺第１項の行列に関する情報をデータパケット１０１、リードソロモン符号冗長パケット１０２、またはＥＯＲ冗長パケット１０３に付加することによって行うようにしてもよい。
【００８１】
この、式（４）の右辺第１項の行列に関する情報は、その行列の各成分の内容を直接表す情報であってもよいし、間接的に行列の各成分の内容を表す情報であってももちろんよい。例えば、その行列の各成分がランダム関数によって決定されている場合、そのランダム関数の「種」を表す情報を式（４）の右辺第１項の行列に関する情報とすることも可能である。
【００８２】
なお、ＥＯＲ演算するデータの選択方法（すなわち、式（４）の右辺第１項の行列の第Ｎ＋１行乃至第Ｎ＋Ｍ行の各成分の値の決定方法）は、上述したランダムに選択する以外の方法であってもよく、例えば、複数の所定の組み合わせを用いる等、どのような方法であってもよい。さらに、パケット生成部１４が生成した誤り訂正用のパケットの性能評価を行い、それらの中から性能の良いパケットの組み合わせを選択し、ＥＯＲ冗長パケット１０３として採用するようにしてもよい。
【００８３】
また、生成される冗長パケット１０２のパケット数（Ｍ個）は、実用的な範囲であればいくつであってもよいが、１ブロックのデータに対して冗長パケット数を増加させると、データパケットの復元能力が上がるとともに、配信されるデータ量や処理に必要な負荷が増加するという特徴があり、システムやネットワーク等の環境や配信データの内容等に合わせて、最適な冗長パケット数を選択するのが望ましい。
【００８４】
以上のようにして、式（４）の演算により誤り訂正用のデータを生成したパケット生成部１４は、生成された各データをパケット化し、ＥＯＲ冗長パケット１０５を生成する。
【００８５】
図４に戻り、ステップＳ３の処理を完了したパケット生成部１４は、ＣＰＵ１１に制御され、生成されたデータパケット１０１、リードソロモン符号冗長パケット１０２、およびＥＯＲ冗長パケット１０３を通信部３４に供給する。
【００８６】
ステップＳ４において、通信部３４は、取得したデータパケット１０１、リードソロモン符号冗長パケット１０２、およびＥＯＲ冗長パケット１０３を、所定のプロトコルに従い、ネットワーク２を介して配信先のクライアント３に送信する。
【００８７】
そして、ステップＳ５においてＣＰＵ１１は、データ送信処理を終了するか否かを判定する。配信を要求された配信データに未送信の部分が存在し、終了しないと判定した場合、ＣＰＵ１１は、ステップＳ１に処理を戻し、次のブロックに対して、上述した処理を繰り返す。また、例えば、配信を要求された配信データの送信が完了したり、配信停止の指示を取得したりして、データ送信処理を終了すると判定した場合、ＣＰＵ１１は、データ送信処理を終了する。
【００８８】
以上のように、配信データは、サーバ１により、所定のブロックごとにデータ送信処理を施され、パケット化されてクライアント３に配信される。
【００８９】
図６は、サーバ１よりクライアント３に送信されるパケットの様子の例を示す模式図である。図６Ａに示されるように、サーバ１は、ブロック毎に生成されたデータパケットおよび冗長パケットを、ブロック毎に送信する。
【００９０】
すなわち、サーバ１は、第（Ｔ−１）ブロックの最後のＥＯＲ冗長パケット１１３−Ｌに続いて、第Ｔブロックのデータパケット１２１−１乃至１２１−Ｎ、リードソロモン符号冗長パケット１２２−１乃至１２２−Ｍ、およびＥＯＲ冗長パケット１２３−１乃至１２３−Ｌを送信する。
【００９１】
そして、サーバ１は、第Ｔブロックの最後のＥＯＲ冗長パケット１２３−Ｌを送信すると、次のブロックである第（Ｔ＋１）ブロックのデータパケット１３１−１を送信する。
【００９２】
パケットの送信先であるクライアント３は、通信部８４において各パケットを受信するが、ネットワーク２等のパケット転送経路上において、図６Ｂに示される、クライアント３に受信されたパケットをブロック毎に整列させた例のように、一部のパケットをロスしている場合がある。図６Ｂにおいて、クライアント３は、第Ｔブロックのデータパケット１２１−１乃至１２１−４、リードソロモン符号冗長パケット１２２−１、並びにＥＯＲ冗長パケット１２３−１をロスしている。
【００９３】
クライアント３は、後述するようにデータ受信処理を行い、受信したリードソロモン符号冗長パケット１２２−２乃至１２２−Ｍを用いて、ロスしたデータパケット１１２−１乃至１１２−４の復元処理を行う。復元不可能である場合はサーバ１にロスしたパケットの再送を要求する。
【００９４】
図６Ｂの第Ｔブロックに対する処理を例にして、クライアント３によるデータ受信処理を、図７のフローチャートを参照して説明する。
【００９５】
配信データの送信先であるクライアント３の通信部８４は、ステップＳ２１において、パケットの受信制御処理を行い、ネットワーク２を介してサーバ１より供給された第Ｔブロックのデータパケット１２１−５乃至１２１−Ｎ、リードソロモン符号冗長パケット１２２−２乃至１２２−Ｍ、並びにＥＯＲ冗長パケット１２３−２乃至１２３−Ｌを順次取得し、バス７０を介してデータ再生部６４に供給する。
【００９６】
なお、受信されたパケットは、通信部８４に内蔵されるＲＡＭに一時保持され、後述するステップＳ２２の処理において、対象ブロックのパケット受信が完了したと判定された場合に、ブロック毎にデータ再生部６４に供給されるようにしてもよい。また、受信されたパケットがＣＰＵ６１に内蔵されるＲＡＭ、ＲＡＭ６３、または記憶部８３に保持されるようにしてももちろんよい。さらに、受信されたパケットは、データ再生部６４に供給される際に、パケット復元部６５にも供給されるようにしてもよい。
【００９７】
ステップＳ２２において、ＣＰＵ６１は、通信部８４を制御して、受信対象ブロックのパケット受信が完了したか否かを判定する。受信対象ブロックについて未受信のパケットが存在し、受信対象ブロックのパケット受信が完了していないと判定した場合、ＣＰＵ６１は、処理をステップＳ２１に戻し、パケットの受信制御処理を繰り返す。
【００９８】
ステップＳ２２において、受信対象ブロックのパケットを全て受信し、受信が完了したと判定した場合、ＣＰＵ６１は、ステップＳ２３に処理を進める。
【００９９】
なお、パケットが受信される順番はパケットの到着順であり、送信された順序でパケットが受信されるとは限らない。従って、ＣＰＵ６１は、予め定められた所定の時間内において上述したようにステップＳ２２の判定処理を行う。ステップＳ２１およびＳ２２の処理を繰り返し、所定の時間が経過した場合、ＣＰＵ６１は、ステップＳ２２において、受信対象ブロックのパケット受信が完了したと判定し、処理をステップＳ２３に進める。
【０１００】
例えば、図６Ｂに示されるように、第Ｔブロックのデータパケット１１２−１乃至１１２−４をロスしており、所定の時間が経過しても、受信対象ブロックについて未受信のパケットが存在する場合、ＣＰＵ６１は、それらのパケットをロスしたと判定し、対象ブロックのパケット受信が完了したと判定し、ステップＳ２３に処理を進める。
【０１０１】
ステップＳ２３において、ＣＰＵ６１に制御されたデータ再生部６４は、供給されたデータパケット１０１が１ブロック分揃っているかを確認し、ロスしたデータパケットが存在するか否かを判定する。ロスしたデータパケット１０１が存在すると判定した場合、データ再生部６４は、取得したデータパケット１０１、リードソロモン符号冗長パケット１０２、ＥＯＲ冗長パケット１０３、並びに、式（３）の右辺第１項に関する情報をパケット復元部６５に供給し、処理をステップＳ２４に進める。
【０１０２】
ステップＳ２４において、データ再生部６４より各種のデータを取得したパケット復元部６５は、リードソロモン符号冗長パケット１０２によるデータパケット１０１の復元が可能であるか否かを判定する。
【０１０３】
リードソロモン符号の場合、後述するパケット復元処理において生成される連立一次方程式の各方程式は、その独立性より保証される。すなわち、データパケットのロス数が受信できたリードソロモン符号冗長パケット数以内であれば、ロスしたパケットは復元可能である。従って、パケット復元部６５は、ロスしたデータパケットの数と、受信したリードソロモン符号の数とを比較して、データパケット１０１の復元が可能であるか否かを判定し、復元可能であると判定した場合、処理をステップＳ２５に進める。
【０１０４】
ステップＳ２５において、パケット復元部６５は、リードソロモン符号冗長パケットを用いて、以下に示す式（５）のような連立一次方程式の解を求めることにより、ロスしたデータパケットを復元する。なお、パケット復元部６５は、受信したリードソロモン符号冗長パケットの数が、ロスしたデータパケットの数より多い場合、任意のリードソロモン符号冗長パケットを、データパケットのロス数だけ抽出し、復元処理に用いる。
【０１０５】
【数５】
2004165922.tif 000007
【０１０６】
式（５）は、図６Ｂに示される例において、受信したリードソロモン符号冗長パケット１２２−２乃至１２２−Ｍのうち、最初の４個のリードソロモン符号冗長パケット１２２−２乃至１２２−５を用いて、ロスしたデータパケット１２１−１乃至１２１−４を復元するための、変数Ｚ１乃至Ｚ４に関する連立一次方程式である。式（５）において、四則演算はガロア体上において行われ、各成分の加算は、対応するビットごとのＥＯＲ演算を用いて行われる。
【０１０７】
式（５）の右辺第１項の行列の成分Ｚ１乃至Ｚ４は、ロスしたデータパケットに対応する変数であり、パケット復元部６５は、式（５）において、Ｚ１乃至Ｚ４の解を算出することにより、ロスしたデータパケットを復元する。
【０１０８】
式（５）の左辺第１項の行列は、サーバ１と共有している式（２）の右辺第１項に関する情報に基づいて生成された４行４列の正方行列である。
【０１０９】
パケット復元部６５は、サーバ１と共有する式（２）の右辺第１項に関する情報に基づいて、式（２）の右辺第１項の行列の成分の中から、ロスしたデータパケットと、選択されたリードソロモン符号冗長パケットの両方に対応する成分を抽出し、式（５）の左辺第１項の行列を生成する。従って、例えばクライアント３がＨ個のデータパケットをロスしたとすると、式（５）の左辺第１項の行列は、Ｈ行Ｈ列の正方行列となる。
【０１１０】
式（５）の左辺第２項の行列の成分Ｖ１乃至Ｖ４は、受信したデータパケット、および復元処理に使用されるリードソロモン冗長パケットを用いて、パケット復元部６５により算出される変数である。パケット復元部６５は、復元処理に使用されるリードソロモン冗長パケット数分（データパケットのロス数分）、変数Ｖを生成する。すなわち、Ｈ個のデータパケットがロスされたとすると、パケット復元部６５は、変数Ｖ１乃至ＶＨを算出する。変数Ｖは、以下の式（６）のような連立一次方程式により算出される。
【０１１１】
【数６】
2004165922.tif 000008
【０１１２】
式（６）は、図６Ｂに示される例において、受信したリードソロモン符号冗長パケット１２２−２乃至１２２−Ｍのうち、最初の４個のリードソロモン符号冗長パケット１２２−２乃至１２２−５を用いて、ロスしたデータパケット１２１−１乃至１２１−４を復元するための、変数Ｖ１乃至Ｖ４に関する連立一次方程式である。式（６）において、四則演算はガロア体上において行われ、各成分の加算は、対応するビットごとのＥＯＲ演算を用いて行われる。
【０１１３】
式（６）の左辺第１項の行列は、サーバ１と共有している式（２）の右辺第１項に関する情報に基づいて生成された４行Ｎ−４列の行列である。
【０１１４】
パケット復元部６５は、サーバ１と共有する式（２）の右辺第１項に関する情報に基づいて、式（２）の右辺第１項の行列の成分の中から、受信したデータパケットと、受信したリードソロモン符号冗長パケットの中から選択されたリードソロモン符号冗長パケットの両方に対応する成分を抽出し、式（６）の左辺第１項の行列を生成する。従って、例えばクライアント３がＨ個のデータパケットをロスしたとすると、式（６）の左辺第１項の行列は、Ｈ行Ｎ−Ｈ列の行列となる。
【０１１５】
以上のように、パケット復元部６５は、式（６）より変数Ｖを算出し、その変数Ｖを用いて、式（５）を生成し、方程式の解を算出することで、ロスしたデータパケットを復元する。
【０１１６】
図４に戻り、ロスしたデータパケットを復元したパケット復元部６５は、復元したデータパケットをデータ再生部６４に供給する。
【０１１７】
ＣＰＵ６１に制御されたデータ再生部６４は、ステップＳ２６において、取得したデータパケット群より１ブロック分の配信データを再生し、出力部８２等に供給する。配信データを供給された出力部８２は、取得した配信データに対応する画像や音声等を所定の出力方法で出力する。
【０１１８】
ＣＰＵ６１は、ステップＳ２７において、データ受信処理を終了するか否かを判定し、配信されるデータの受信が完了しておらず、終了しないと判定した場合、処理をステップＳ２１に戻し、次のブロックに対して、それ以降の処理を繰り返す。
【０１１９】
ステップＳ２７において、配信データの受信が完了したり、ユーザより処理中止の指示を受け付けたりしてデータ受信処理を終了すると判定した場合、ＣＰＵ６１は、ステップＳ２８に処理を進めて終了処理を行った後、データ受信処理を終了する。
【０１２０】
ステップＳ２３において、対象ブロックのデータパケットを全て受信しており、ロスしたデータパケットが存在しないと判定した場合、データ再生部６４は、処理をステップＳ２６に進め、配信データの再生処理を実行する。
【０１２１】
パケット復元部６５は、ステップＳ２４において、例えば、ロスしたパケットが多すぎる場合等、ロスしたパケットがリードソロモン符号を用いた方法で、復元可能でないと判定した場合、処理をステップＳ２９に進め、ＥＯＲによるデータパケット復元処理を実行する。ＥＯＲによるデータパケット復元処理の詳細は、図８および９のフローチャートを参照して後述する。
【０１２２】
ＥＯＲによるデータパケット復元処理が完了すると、パケット復元部６５は、復元したデータパケットをデータ再生部６４に供給し、処理をステップＳ２６に進める。
【０１２３】
以上のようにして、クライアント３は、サーバ１より供給されるパケットを受信し、サーバ１によるストリーミング配信やライブ放送などを出力することができる。
【０１２４】
次に、図７のステップＳ２９において実行される、ＥＯＲによるデータパケット復元処理について説明する。
【０１２５】
クライアント３がＨ個のデータパケット１０１、およびＬ個のＥＯＲ冗長パケット１０３をロスしたものとし、ロスしたデータパケットに含まれるデータをＺ１乃至ＺＨとすると、パケット復元部６５によるデータパケットの復元は、以下に示す式（７）の連立一次方程式において、Ｚ１乃至ＺＨの解を求めることによって行われる。
【０１２６】
【数７】
2004165922.tif 000009
【０１２７】
なお、式（７）において、四則演算はガロア体上において行われ、各成分の加算は、対応するビットごとのＥＯＲ演算を用いて行われる。
【０１２８】
式（７）の左辺第１項は、サーバ１と共有している式（４）の右辺第１項に関する情報に基づいて生成されたＬ−Ｋ行Ｈ列の行列であり、左辺第２項の行列の成分Ｚ１乃至ＺＨの係数を表す行列である。
【０１２９】
パケット復元部６５は、サーバ１と共有する式（４）の右辺第１項に関する情報に基づいて、式（４）の右辺第１項の行列の成分の中から、ロスしたデータパケット、および受信された冗長パケットの両方に対応する成分を抽出し、式（７）の左辺第１項の行列を生成する。
【０１３０】
例えば、図６Ｂに示されるような例の場合、パケット復元部６５は、サーバ１において演算に用いられた式（４）の右辺第１項の行列の、第２行乃至第Ｌ行の、第１列乃至第４列を成分とする行列を生成する。
【０１３１】
式（７）の右辺第１項の行列の成分Ｗ１乃至ＷＬ−Ｋは、受信したデータパケット１０１およびＥＯＲ冗長パケット１０３に含まれるデータより算出された変数である。この各成分Ｗ１乃至ＷＬ−Ｋは、以下に示す式（８）により算出される。
【０１３２】
【数８】
2004165922.tif 000010
【０１３３】
なお、式（８）において、四則演算はガロア体上において行われ、各成分の加算は、対応するビットごとのＥＯＲ演算を用いて行われる。
【０１３４】
式（８）において、定数Ｎはサーバ１より送信されたデータパケット数であり、定数Ｈはクライアント３がロスしたデータパケット数であり、定数Ｌはサーバ１より送信された冗長パケット数であり、定数Ｋはクライアント３がロスした冗長パケット数である。また、式（８）において、Ｐ１乃至ＰＮ−Ｈはクライアント３が受信した各データパケットに含まれているデータを表し、Ｒ１乃至ＲＬーｋはクライアント３が受信した各冗長パケットに含まれているデータを表す。
【０１３５】
式（３）の右辺第１項は、サーバ１と共有している式（４）の右辺第１項に関する情報に基づいて生成されたＬ−Ｋ行Ｎ−Ｈ列の行列であり、右辺第２項の行列の成分Ｐ１乃至ＰＮ−Ｈの係数を表す行列である。
【０１３６】
パケット復元部６５は、サーバ１と共有する式（４）の右辺第１項に関する情報に基づいて、式（４）の右辺第１項の行列の成分の中から、受信されたデータパケット、および受信された冗長パケットの両方に対応する成分を抽出し、式（８）の右第１項の行列を生成する。
【０１３７】
例えば、図６Ｂに示されるような例の場合、パケット復元部６５は、サーバ１において演算に用いられた式（４）の右辺第１項の行列の、第２行乃至第Ｌ行の、第５列乃至第Ｎ列を成分とする行列を生成する。
【０１３８】
パケット復元部６５は、以上のような式（８）を演算することにより、左辺第１項の行列の各成分Ｗ１乃至ＷＬ−Ｋを算出し、それらの値を式（７）に代入して、Ｚ１乃至ＺＨの解を求める。その際、パケット復元部６５は、値が「０」でない係数を選択するための処理方法であるピボット選択を用いたガウス消去法を用いて解を算出する。ピボット選択を用いたガウス消去法は、前進消去および後退代入などのプロセスにより、方程式に含まれる変数を減らすことにより、解を算出する方法である。
【０１３９】
次に、図８のフローチャートを参照して、クライアント３によるデータパケット復元処理を説明する。
【０１４０】
最初に、パケット復元部６５は、ステップＳ４１において、式（８）の演算を行い、Ｗ１乃至ＷＬ−Ｋを算出して、式（７）のような、ロスしたデータパケットを復元するための連立一次方程式をたてる。
【０１４１】
そして、パケット復元部６５は、ステップＳ４２において、変数Ｙの値を「０」に設定して初期化し、ステップＳ４３において、式（７）の左辺第１項の行列の第Ｙ列の各成分について、値が「１」の成分を検出する。
【０１４２】
その検出結果に基づいて、パケット復元部６５は、ステップＳ４４において、値が「１」の成分が存在するか否かを判定し、存在すると判定した場合、パケット復元部６５は，処理をステップＳ４５に進める。
【０１４３】
ステップＳ４５において、パケット復元部６５は、値が「１」の成分が複数存在するか否かを判定し、複数存在すると判定した場合、処理をステップＳ４６に進める。
【０１４４】
値が「１」の成分が複数存在する場合、パケット復元部６５は、ステップＳ４６において、２番目以降に検出された成分を含む方程式と、最初に検出された成分を含む方程式との間で、各項についてＥＯＲ演算を行い、その演算結果を、演算に用いた２番目以降に検出された成分を含む行に置き換える。すなわち、パケット復元部６５は、前進消去のプロセスを行い、対象のＹ列について、最初に検出された成分を含む行以外の行の成分の値を全て「０」にする。
【０１４５】
そして、パケット復元部６５は、ステップＳ４７において、最初に検出された成分を含む方程式を求解用に抽出し、保持する。すなわち、この後ステップＳ４６の処理が繰り返される際のＥＯＲ演算は、抽出した方程式を対象とせずに、抽出されずに残された方程式の中で行われる。
【０１４６】
ステップＳ４７の処理を終えたパケット復元部６５は、ステップＳ４８に処理を進め、変数Ｙの値に「１」を加算し、ステップＳ４９において、その変数Ｙの値が列数Ｈ以下であるか否かを判定する。変数Ｙの値が、列数Ｈ以下であり、成分ＡＸＹが存在すると判定した場合、パケット復元部６５は、処理をステップＳ４３に戻し、新たな列に対してそれ以降の処理を繰り返す。
【０１４７】
ステップＳ４９において、変数Ｙの値がＨより大きい場合、すなわち、成分ＡＸＹが存在しないと判定した場合、パケット復元部６５は、処理をステップＳ５０に進め、変数Ｙの値を「Ｈ」に設定する。
【０１４８】
そして、ステップＳ５１において、パケット復元部６５は、ステップＳ４７の処理により求解用に保持されている方程式を用いて、ＰＹの解を算出し、ステップＳ５２において、変数Ｙの値より「１」を減算し、ステップＳ５３において、変数Ｙの値が「０」か否かを判定する。「０」でないと判定した場合、パケット復元部６５は、処理をステップＳ５１に戻し、それ以降の処理を繰り返す。
【０１４９】
そして、ステップＳ５３において、変数Ｙの値が「０」であると判定した場合、パケット復元部６５は、Ｚ１乃至ＺＨの解を算出したので、データパケット復元処理を終了し、図７のステップＳ２６に処理を進める。
【０１５０】
また、ステップＳ４４において、式（７）の左辺第１項の行列の第Ｙ列について、値が「１」の成分が存在しないと判定した場合、パケット復元部６５は、データパケット復元処理を終了し、図７のステップＳ２６に処理を進める。
【０１５１】
さらに、ステップＳ４５において、式（７）の左辺第１項の行列の第Ｙ列について、値が「１」の成分が複数存在しないと判定した場合、パケット復元部６５は、ステップＳ４６の処理を省略し、ステップＳ４７に処理を進める。
【０１５２】
以上のようにして、パケット復元部６５は、ガウス消去法を利用してロスしたデータパケットに含まれているデータを復元する。
【０１５３】
以上においては、パケット復元部６５が、値が「０」でない係数を選択するための処理方法であるピボット選択を用いたガウス消去法を利用して、式（７）に示される連立一次方程式の解を求めるように説明したが、これに限らず、パケット復元部６５が、ガウス消去法を応用した応用ガウス消去法を用いて、式（７）に示される連立一次方程式の解を求めるようにしてもよい。応用ガウス消去法は、式（７）に示される全ての連立一次方程式から変数を１つずつ減らしていき、残った最後の変数の解を用いて全ての解を算出する方法である。
【０１５４】
図９のフローチャートを参照して、クライアント３によるデータパケット復元処理の応用ガウス消去法を利用した他の例について説明する。
【０１５５】
最初に、パケット復元部６５は、ステップＳ７１において、式（８）の演算を行い、Ｗ１乃至ＷＬ−Ｋを算出して、式（７）のような、ロスしたデータパケットを復元するための連立一次方程式をたてる。
【０１５６】
そして、パケット復元部６５は、ステップＳ７２において、変数Ｙの値を「０」に設定して初期化し、ステップＳ７３において、式（７）の左辺第１項の行列の第Ｙ列の各成分について、値が「１」の成分を検出する。
【０１５７】
その検出結果に基づいて、パケット復元部６５は、ステップＳ７４において、値が「１」の成分が存在するか否かを判定し、存在すると判定した場合、パケット復元部６５は，処理をステップＳ７５に進める。
【０１５８】
ステップＳ７５において、パケット復元部６５は、最初に検出された成分を含む方程式を求解用に保持する。そして、ステップＳ７６において、パケット復元部６５は、値が「１」の成分が複数存在するか否かを判定し、複数存在すると判定した場合、処理をステップＳ７７に進める。
【０１５９】
値が「１」の成分が複数存在する場合、パケット復元部６５は、ステップＳ７７において、検出された順番が連続する２つの成分をそれぞれ含む２つの方程式間で、各項についてＥＯＲ演算処理を行い、その演算結果を、演算に用いた方程式のうち、検出された順番が後の方程式に置き換える。なお、最初に検出された方程式は、最後に検出された方程式とのＥＯＲ演算処理結果に置き換えられる。
【０１６０】
そして、パケット復元部６５は、ステップＳ７８において、変数Ｙの値に「１」を加算するし、ステップＳ７９において、その変数Ｙの値が列数Ｈ以下であるか否かを判定する。変数Ｙの値が、列数Ｈ以下であり、成分ＡＸＹが存在すると判定した場合、パケット復元部６５は、処理をステップＳ７３に戻し、新たな列に対してそれ以降の処理を繰り返す。
【０１６１】
ステップＳ７９において、変数Ｙの値がＨより大きい場合、すなわち、成分ＡＸＹが存在しないと判定した場合、パケット復元部６５は、処理をステップＳ８０に進め、変数Ｙの値を「Ｈ」に設定する。
【０１６２】
そして、ステップＳ８１において、パケット復元部６５は、ステップＳ７５の処理により求解用に保持されている方程式を用いて、ＺＹの解を算出し、ステップＳ８２において、変数Ｙの値より「１」を減算し、ステップＳ８３において、変数Ｙの値が「０」か否かを判定する。「０」でないと判定した場合、パケット復元部６５は、処理をステップＳ８１に戻し、それ以降の処理を繰り返す。
【０１６３】
そして、ステップＳ８３において、変数Ｙの値が「０」であると判定した場合、パケット復元部６５は、Ｚ１乃至ＺＨの解を算出したので、データパケット復元処理を終了し、図７のステップＳ２６に処理を進める。
【０１６４】
また、ステップＳ７４において、式（７）の左辺第１項の行列の第Ｙ列について、値が「１」の成分が存在しないと判定した場合、パケット復元部６５は、データパケット復元処理を終了し、図７のステップＳ２６に処理を進める。
【０１６５】
さらに、ステップＳ７６において、式（２）の左辺第１項の行列の第Ｙ列について、値が「１」の成分が複数存在しないと判定した場合、パケット復元部６５は、ステップＳ７７の処理を省略し、ステップＳ７８に処理を進める。
【０１６６】
以上のようにして、パケット復元部６５は、応用ガウス消去法を利用してロスしたデータパケットに含まれているデータを復元する。
【０１６７】
以上のように、配信データを受信するクライアント３において、ロスしたデータパケットを、リードソロモン符号を用いた方法とＥＯＲ演算を用いた方法の２つの方法で復元できるようにしたので、データパケット復元能力を向上させることができる。さらに、データパケット復元能力が向上することで、ロスしたデータパケットの再送処理を省略しても実用上問題が無い程度にまで、データパケットのロスによるエラー発生率を十分に低下させることができる。これにより、データパケットの再送処理によるデータ再生処理の処理時間増大を防止することができる。このような効果は、処理時間に制限のあるストリーミング配信やライブ放送等において特に有効である。
【０１６８】
なお、図１においては、１つのネットワーク２にサーバ１並びにクライアント３−１および３−２が接続されているシステムについて説明したが、システムの構成は、これ以外にも、例えば、複数のサーバがネットワーク２に接続されるようにしてもよいし、さらに多くのクライアント３が接続されるようにしてもよい。また、サーバ１が複数のネットワーク、さらには中継局等の他の装置を介してクライアント３に接続されるようにしてもよい。その場合、本発明を適用した配信処理は、例えば、サーバ１と中継局との間、または、中継局とクライアント３との間における配信処理であってもよい。
【０１６９】
また、図１において、サーバ１およびクライアント３は、有線を介してネットワーク２に接続されており、有線通信を行うように説明したが、これに限らず、サーバ１およびクライアント３が無線通信機能を有し、無線通信によりネットワーク２とそれぞれ接続し、ネットワーク２を介して通信を行うようにしてもよい。その際、利用される通信規格は、通信キャリアを介した電話回線経由の通信以外にも、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃ  Ｅｎｇｉｎｅｅｒｓ）８０２．１１ｘ、ブルートゥース、赤外線を用いたＩｒＤＡ（ＩｎｆｒａＲｅｄ  Ｄａｔａ  Ａｓｓｏｃｉａｔｉｏｎ）等の近距離無線通信であってもよい。
【０１７０】
さらに、図２において示されるサーバ１の内部の構成例における各ブロックは、その機能の一部または全部が、他のブロックと一体化されて構成されていてもよいし、１つのブロックとして示した機能が複数のブロックとして構成されていてもよい。図３において示されるクライアント３についても同様である。
【０１７１】
なお、サーバ１およびクライアント３は、上述したパーソナルコンピュータ以外にも、例えば、携帯電話機、デジタルビデオカメラ、あるいはテレビジョン受像機などの電子機器に広く適用することができる。
【０１７２】
上述した一連の処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【０１７３】
コンピュータにインストールされ、コンピュータによって実行可能な状態とされるプログラムを記録する記録媒体は、図２または図３に示されるように、磁気ディスク４１または９１（フレキシブルディスクを含む）、光ディスク４２または９２（ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）を含む）、光磁気ディスク４３または９３（ＭＤ（Ｍｉｎｉ−Ｄｉｓｃ）（登録商標）を含む）、もしくは半導体メモリ４４または９４などよりなるパッケージメディア、または、プログラムが一時的もしくは永続的に記録されるＲＯＭ１２または６２などにより構成される。記録媒体へのプログラムの記録は、必要に応じてルータ、モデムなどのインターフェースを介して、公衆回線網、ローカルエリアネットワーク、またはインターネットなどのネットワーク、デジタル衛星放送といった、有線または無線の通信媒体を利用して行われる。
【０１７４】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１７５】
【発明の効果】
以上のように、本発明によれば、他の装置より供給されたパケットデータを取得することができる。特に、より好適にパケットデータを取得し、データの再生を行うことができる。
【図面の簡単な説明】
【図１】本発明を適用したデータ伝送システムの基本的な構成例を示す図である。
【図２】図１のサーバの内部の構成例を示すブロック図である。
【図３】図１のクライアントの内部の構成例を示すブロック図である。
【図４】図１のサーバによるデータ伝送処理を説明するフローチャートである。
【図５】図１のサーバが生成するパケットの例を示す模式図である。
【図６】図１のデータ伝送システムにおいて、サーバより送信され、クライアントによって受信されるパケットの様子を示す模式図である。
【図７】図１のクライアントによるデータ受信処理を説明するフローチャートである。
【図８】図７のステップＳ２９において実行されるデータパケット復元処理の例について説明するフローチャートである。
【図９】図７のステップＳ２９において実行されるデータパケット復元処理の他の例について説明するフローチャートである。
【符号の説明】
１  サーバ，  ２  ネットワーク，  ３−１および３−２  クライアント，  １４  パケット生成部，  ６４  データ再生部，  ６５  パケット復元部，  １０１  データパケット，  １０２  リードソロモン符号冗長パケット，  １０３
ＥＯＲ冗長パケット
【図１】
2004165922.tif 000011
【図２】
2004165922.tif 000012
【図３】
2004165922.tif 000013
【図４】
2004165922.tif 000014
【図５】
2004165922.tif 000015
【図６】
2004165922.tif 000016
【図７】
2004165922.tif 000017
【図８】
2004165922.tif 000018
【図９】
2004165922.tif 000019