(57)【要約】【解決手段】データブロックに分解されたデータファイル用のアイドルタイム減少スケジューリング行列（５２０）のための方法およびシステム。スケジューリング行列が生成され、データブロックの元のシーケンスを維持したまま、アイドルタイムが行列の後の方に現れるデータブロックで満たされる。次に、この動作が繰り返されるか（５５０）、または、新しいアイドルタイム減少スケジューリング行列が生成される（５６０）。特別に設計されたセット・トップ・ボックスが、これらのデータブロックを受信する。【選択図】図９
2004514336.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータによって実行される汎用放送方法であって、
非クライアント固有の方式で複数のクライアントにオン・デマンドデータを放送するのに適したデータ伝送シーケンスを規定する配信行列を準備する工程を備え、
前記オン・デマンドデータファイルの伝送に必要な伝送帯域幅の量は、前記複数のクライアントの数と無関係となる、方法。
【請求項２】
請求項１に記載のコンピュータによって実行される方法であって、
配信行列を生成する工程は、
第１のデータファイルの伝送に適した第１のスケジューリング行列を準備する工程であって、前記第１のデータファイルは、第１の複数のデータブロックによって表され、前記第１のスケジューリング行列は、前記第１のスケジューリング行列に従って前記第１のデータファイルの伝送を受信する任意のクライアントが、１タイムスロット内で前記第１のデータファイルへアクセス開始できるように、前記第１の複数のデータブロックを、複数のタイムスロット内で順番に伝送するための第１のシーケンスを提供する工程を備える、方法。
【請求項３】
請求項２に記載のコンピュータによって実行される方法であって、
前記第１のスケジューリング行列は、一定帯域幅のスケジューリング行列である、方法。
【請求項４】
請求項３に記載のコンピュータによって実行される方法であって、
前記第１の複数のデータブロックからの一定量のデータは、割り当てられた帯域幅の中での伝送のためにスケジューリングされる、方法。
【請求項５】
請求項４に記載のコンピュータによって実行される方法であって、
割り当てられた帯域幅の中での伝送の制御は、下位ハードウェアデバイスによって実行される、方法。
【請求項６】
請求項３に記載のコンピュータによって実行される方法であって、
前記第１のスケジューリング行列は、可変帯域幅のスケジューリング行列である、方法。
【請求項７】
非クライアント固有のフォーマットでのオン・デマンドデータの配信に適した一定帯域幅アイドルタイム減少スケジューリング行列を生成するためのコンピュータによって実行される方法であって、
第１のデータファイルの伝送に適したスケジューリング行列を生成する工程であって、前記第１のデータファイルは、第１の複数のデータブロックによって表され、前記第１のスケジューリング行列は、前記第１のスケジューリング行列に従って前記第１のデータファイルの伝送を受信する任意のクライアントが、１タイムスロット内で前記第１のデータファイルへアクセス開始できるように、前記第１の複数のデータブロックを、複数のタイムスロット内で順番に伝送するための第１のシーケンスを提供する工程と、
所望の一定の伝送帯域幅を決定する工程であって、前記一定の帯域幅は、次いで、前記第１のスケジューリング行列の順序に従って、前記データブロックを順番に流すために用いられる工程と、
を備える、方法。
【請求項８】
汎用セット・トップ・ボックス（ＳＴＢ）を制御するためのコンピュータによって実行される方法であって、
複数のチャンネルでデジタルデータを受信すると共に、前記複数のチャンネルの各々で伝送されるデータの性質を示す電子番組ガイド（ＥＰＧ）を受信する工程であって、前記複数のチャンネルの内の第１のチャンネルは、非クライアント固有のフォーマットでオン・デマンドデータを提供するデータ・オン・デマンド番組を含み、前記ＥＰＧは、前記データ・オン・デマンド番組が、第１の複数のデータブロックによって表される第１のデータファイルを含むことを示し、前記第１の複数のデータブロックは、前記汎用ＳＴＢのユーザが１タイムスロット内で前記第１のデータファイルへ任意の時間にアクセス開始できるように、複数のタイムスロット内で順番に提供される工程と、
前記汎用ＳＴＢの前記ユーザに前記ＥＰＧデータを提供する工程と、
前記第１のデータファイルへのアクセスを必要とする前記汎用ＳＴＢの前記ユーザからデータ処理命令を受信する工程と、
前記汎用ＳＴＢの前記ユーザからの前記命令を実行する工程と、
を備える、方法。
【請求項９】
請求項８に記載のコンピュータによって実行される方法であって、
前記汎用ＳＴＢの前記ユーザからの命令を実行する前記工程は、
前記ＳＴＢを前記第１のチャンネルに同調させて、前記ユーザによって要求されるデータを選択する工程と、
受信の際に前記第１の複数のデータブロックを処理する工程であって、
前記受信されたデータブロックをデコードする工程と、
前記受信されたデータブロックを解凍する工程と、
前記受信されたデータブロックを必要に応じて再組み立てする工程と、
前記受信されたデータブロックを前記ＳＴＢ内に存在するローカルメモリに格納する工程のうち、少なくとも１つの工程を含む工程と、
前記第１のデータファイルを前記汎用ＳＴＢの前記ユーザによって選択された出力装置に提供する工程と、
を備える、方法。
【請求項１０】
請求項９に記載のコンピュータによって実行される方法であって、
前記出力装置はテレビである、方法。
【請求項１１】
請求項９に記載のコンピュータによって実行される方法であって、
前記出力装置はディスプレイモニタである、方法。
【請求項１２】
請求項９に記載のコンピュータによって実行される方法であって、
前記出力装置はビデオカセットレコーダ（ＶＣＲ）である、方法。
【請求項１３】
請求項９に記載のコンピュータによって実行される方法であって、
前記出力装置はコンピュータシステムである、方法。
【請求項１４】
請求項８に記載のコンピュータによって実行される方法であって、
前記第１の複数のデータブロックは、一定数のデータブロックが各タイムスロット中に受信される一定帯域幅の方式で提供される、方法。
【請求項１５】
コンピュータによって実行される汎用データ放送方法であって、
汎用データ放送システムにおいて、
非クライアント固有の方式で複数のクライアントにオン・デマンドデータを放送するのに適したデータ伝送シーケンスを規定する配信行列を準備する工程であって、前記オン・デマンドデータファイルの伝送に必要な伝送帯域幅の量は、前記複数のクライアントの数と無関係となる工程と、
第１のチャンネルを介してのオン・デマンドデータの伝送に適した第１のチャンネルサーバを提供する工程と、
データ放送に先立って、データ・オン・デマンド情報の伝送のために前記第１のチャンネルサーバを準備する工程であって、前記配信行列を前記第１のチャンネルサーバのメモリ内に読み出す工程および前記配信行列によって配信のためにスケジューリングされたデータブロックを前記第１のチャンネルサーバの前記メモリ内に読み出す工程を含む工程と、
前記第１のチャンネルがオン・デマンドデータを含むことを示す情報を含む電子番組ガイド（ＥＰＧ）を伝送する工程と、
前記第１のチャンネルおよび前記第２のチャンネルからのデータを伝送する工程と、
を実行し、
汎用ＳＴＢにおいて、
前記第１のチャンネルのデータと、前記ＥＰＧとを含むデジタルデータを受信する工程と、
前記汎用ＳＴＢのユーザに前記ＥＰＧデータを提供する工程と、
前記汎用ＳＴＢの前記ユーザからデータ処理命令を受信する工程と、
前記汎用ＳＴＢの前記ユーザからの前記命令を実行する工程と、
を実行する、方法。
【請求項１６】
請求項１５に記載のコンピュータによって実行される方法であって、
配信行列を生成する工程は、
第１のデータファイルの伝送に適した第１のスケジューリング行列を準備する工程であって、前記第１のデータファイルは、第１の複数のデータブロックによって表され、前記第１のスケジューリング行列は、前記第１のスケジューリング行列に従って前記第１のデータファイルの伝送を受信する任意のクライアントが、１タイムスロット内で前記第１のデータファイルへアクセス開始できるように、前記第１の複数のデータブロックを、複数のタイムスロット内で順番に伝送するための第１のシーケンスを提供する工程を備える、方法。
【請求項１７】
請求項１６に記載のコンピュータによって実行される方法であって、
前記第１のスケジューリング行列は、一定帯域幅のスケジューリング行列である、方法。
【請求項１８】
請求項１７に記載のコンピュータによって実行される方法であって、
一定数の前記第１の複数のデータブロックは、各タイムスロット内での伝送のためにスケジューリングされる、方法。
【請求項１９】
請求項１５に記載のコンピュータによって実行される方法であって、
前記第１のスケジューリング行列は、可変帯域幅のスケジューリング行列である、方法。
【請求項２０】
データ配信行列であって、
いくつかのデータブロックに分割されたデータファイルを備え、
前記いくつかのデータブロックが配列される順序は、
ａ）前記データファイルを前記いくつかのデータブロックに分割する工程と、
ｂ）第１の変数を０に設定する工程と、
ｃ）参照配列を消去する工程と、
ｄ）前記第１の変数を前記いくつかのデータブロックの総数と比較する工程と、
ｅ）前記第１の変数が前記いくつかのデータブロックの総数未満であった場合に、第２の変数を０に設定する工程と、
ｆ）前記第２の変数を前記いくつかのデータブロックの総数と比較する工程と、
ｇ）前記第２の変数が前記いくつかのデータブロックの総数未満であった場合に、スケジューリング行列の列に格納された１以上の格納データブロックを前記参照配列に書き込む工程であって、前記列が、ｉを前記第２の変数、ｊを前記第１の変数、ｘを前記いくつかのデータブロックとした場合の［（ｉ＋ｊ）ｍｏｄ（ｘ）］によって決定される工程と、
ｈ）前記参照配列が少なくとも１つの前記格納されたデータブロックをすでに有している場合には、第２のコピーを書き込まない工程と、
ｉ）前記参照配列が前記第２の変数に対応するブロックを含むか否かを調べる工程と、
ｊ）前記参照配列が前記第２の変数に対応する前記データブロックを含まない場合に、前記データブロックが、前記参照配列と、前記スケジューリング行列の［（ｉ＋ｊ）ｍｏｄ（ｘ），ｊ］に等しい前記行列内の位置に付加され、前記第２の変数が１だけ増加される工程と、
ｋ）前記参照配列が前記第２の変数に対応する前記データブロックを含む場合に、前記第２の変数が１だけ増加される工程と、
ｌ）前記第２の変数がデータブロックの前記総数に等しくなるまで、工程ｇ）からｋ）を繰り返す工程と、
ｍ）前記第１の変数を１だけ増分させる工程と、
ｎ）前記第１の変数がデータブロックの前記総数に等しくなるまで、工程ｃ）からｍ）を繰り返す工程と、
ｏ）前記スケジューリング行列をストリームに再構成する工程と、
によって決定され、
前記順序は、前記データファイルに割り当てられた帯域幅を有する媒体を介して反復信号で伝送され、前記帯域幅は、前記反復信号によって完全に利用される、データ配信行列。
【請求項２１】
請求項２０のデータ配信行列であって、
前記スケジューリング行列をストリームに再構成する前記工程は、前記データファイルに割り当てられる前記帯域幅のサイズを決定する工程を含む、データ配信行列。
【請求項２２】
請求項２１のデータ配信行列であって、
前記ファイルに割り当てる前記帯域幅のサイズを決定する工程は、前記帯域幅を最小限にする、データ配信行列。
【請求項２３】
請求項２１のデータ配信行列であって、
前記ファイルに割り当てる前記帯域幅のサイズを決定する工程は、前記帯域幅を最大限にする、データ配信行列。
【請求項２４】
請求項２０に記載のデータ配信行列から得られた複数のデータ配信ストリームを有するデータ配信システムであって、
前記データファイルは、複数の異なるデータファイルを備える、データ配信システム。
【請求項２５】
オン・デマンドデータファイルを伝送するためにコンピュータによって実行される方法であって、
非固有の方式で複数のクライアントに媒体を介して行う放送に適した反復データ伝送シーケンスを規定する配信行列を準備する工程を備え、
前記配信行列を準備する前記工程は、さらに、データファイルを、少なくとも第１のブロックを有する複数のデータブロックに変える工程と、前記データブロックを前記反復データ伝送シーケンスに順序付ける工程と、を備え、
ユーザは、前記反復データ伝送シーケンスを受信し、前記第１のブロックが受信されるとすぐに途切れずに前記データファイルの利用を開始することが可能であり、
前記反復データ伝送シーケンスは、所定の帯域幅を必要とし、さらに、前記反復データ伝送シーケンスの伝送においてアイドルタイムは最小限となり、
前記データ・オン・デマンドファイルの伝送に必要な伝送帯域幅の量は、前記複数のクライアントの数と無関係となる、方法。
【請求項２６】
請求項２５に記載のオン・デマンドデータファイルを伝送するためにコンピュータによって実行される方法であって、
前記反復データ伝送シーケンスは、新しいアイドルタイム減少スケジューリング行列に変換される、方法。
【請求項２７】
請求項２５に記載のオン・デマンドデータファイルを伝送するためにコンピュータによって実行される方法であって、
前記データ伝送シーケンスは、一定の帯域幅を有する、方法。
【請求項２８】
請求項２７に記載のオン・デマンドデータファイルを伝送するためにコンピュータによって実行される方法であって、
一定数の前記データブロックは、各タイムスロット内での伝送のためにスケジューリングされる、方法。
【請求項２９】
請求項２７に記載のオン・デマンドデータファイルを伝送するためにコンピュータによって実行される方法であって、
前記データ伝送シーケンスは、可変の帯域幅を有する、方法。
【請求項３０】
コンピュータによって実行される汎用データ放送方法であって、
非クライアント固有の方式で複数のクライアントにオン・デマンドデータを放送するのに適したデータ伝送シーケンスを規定する配信行列を準備する工程であって、前記オン・デマンドデータファイルの伝送に必要な伝送帯域幅の量は、前記複数のクライアントの数と無関係となり、伝送帯域幅の前記量の利用は、完全に最適化される工程と、
第１のチャンネルを介してのオン・デマンドデータの伝送に適した第１のチャンネルサーバを提供する工程と、
データ放送に先立って、データ・オン・デマンド情報の伝送のために前記第１のチャンネルサーバを準備する工程であって、前記配信行列を前記第１のチャンネルサーバのメモリ内に読み出す工程および前記配信行列によって配信のためにスケジューリングされたデータブロックを前記第１のチャンネルサーバの前記メモリ内に読み出す工程を含む工程と、
前記第１のチャンネルがオン・デマンドデータを含むことを示す情報を含む電子番組ガイド（ＥＰＧ）を伝送する工程と、
前記第１のチャンネルおよび前記第２のチャンネルからのデータを伝送する工程と、
を備え、
汎用セット・トップ・ボックス（ＳＴＢ）において、
前記第１のチャンネルのデータと、前記ＥＰＧとを含むデジタルデータを受信する工程と、
前記汎用ＳＴＢのユーザに前記ＥＰＧデータを提供する工程と、
前記汎用ＳＴＢの前記ユーザからデータ処理命令を受信する工程と、
前記汎用ＳＴＢの前記ユーザからの前記命令を実行する工程と、
を実行する、方法。
【請求項３１】
請求項３０に記載のコンピュータによって実行される方法であって、
配信行列を生成する工程は、
第１のデータファイルの伝送に適した第１のスケジューリング行列を準備する工程であって、前記第１のデータファイルは、第１の複数のデータブロックによって表され、前記第１のスケジューリング行列は、前記第１のスケジューリング行列に従って前記第１のデータファイルの伝送を受信する任意のクライアントが、１タイムスロット内で前記第１のデータファイルへアクセス開始できるように、前記第１の複数のデータブロックを、複数のタイムスロット内で順番に伝送するための第１のシーケンスを提供する工程を備える、方法。
【請求項３２】
請求項３１に記載のコンピュータによって実行される方法であって、
前記第１のスケジューリング行列は、一定帯域幅のスケジューリング行列である、方法。
【請求項３３】
請求項３２に記載のコンピュータによって実行される方法であって、
一定数の前記第１の複数のデータブロックは、各タイムスロット内での伝送のためにスケジューリングされる、方法。
【請求項３４】
請求項３０に記載のコンピュータによって実行される方法であって、
前記第１のスケジューリング行列は、可変帯域幅のスケジューリング行列である、方法。
【請求項３５】
非クライアント固有のフォーマットでのオン・デマンドデータの配信に適した一定帯域幅アイドルタイム減少スケジューリング行列を生成するためのコンピュータによって実行される方法であって、
第１のデータファイルの伝送に適したスケジューリング行列を生成する工程であって、前記第１のデータファイルは、第１の複数のデータブロックによって表され、前記第１のスケジューリング行列は、前記第１のスケジューリング行列に従って前記第１のデータファイルの伝送を受信する任意のクライアントが、１タイムスロット内で前記第１のデータファイルへアクセス開始できるように、前記第１の複数のデータブロックを、複数のタイムスロット内で順番に伝送するための第１のシーケンスを提供する工程と、
所望の一定の伝送帯域幅を決定する工程であって、前記一定の帯域幅は、タイムスロット当たりの規定された一定数のデータブロックの伝送によって規定される工程と、
次のタイムスロットに対して、前記規定された一定数のデータブロックに等しい伝送のためのいくつかのデータブロックを順番に選択すると共に、前記第１のシーケンスのデータブロックの全体が伝送のためにスケジューリングされると、前記第１のシーケンスのデータブロックの先頭に戻る工程であって、前記一定の帯域幅の利用は、完全に最適化される工程と、
を備える、方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
ビデオ・オン・デマンド（ＶＯＤ）システムは、データ・オン・デマンド（ＤＯＤ）システムの一種である。ＶＯＤシステムでは、ビデオデータファイルは、サーバまたは複数サーバのネットワークによって、１以上のクライアントにオン・デマンドで提供される。これらのシステムは、当業者にとって周知である。
【０００２】
【従来の技術】
従来のＶＯＤアーキテクチャでは、サーバまたは複数サーバのネットワークは、標準的な階層クライアント・サーバモデルでクライアントと通信する。例えば、クライアントは、データファイル（例えば、ビデオデータファイル）の要求をサーバに送信する。クライアントの要求に応じて、サーバは、要求されたファイルをクライアントに送信する。標準的なクライアント・サーバモデルでは、クライアントからのデータファイル要求は、１以上のサーバによって実現されることが可能である。クライアントは、受信されたデータファイルすべてを、後の使用のために不揮発性メモリにローカル格納する機能を有してもよい。標準的なクライアント・サーバモデルは、双方向通信のインフラストラクチャを必要とする。既存のケーブルは単方向の通信しか提供できないため、現時点で双方向通信を行うには、新しいインフラストラクチャを構築する必要がある。双方向通信インフラストラクチャの例として、光ファイバ・同軸ハイブリットケーブル（ＨＦＣ）や、すべてのファイバインフラストラクチャが挙げられる。既存のケーブルを置き換えると、非常にコストが掛かるため、その結果として提供されるサービスの価格は、大部分のユーザにとって手の届かないものになるだろう。
【０００３】
また、標準的なクライアント・サーバモデルは、サービスプロバイダ（例えば、ケーブル会社）が多数のクライアントにＶＯＤサービスを提供しようとする場合には、多くの制約を受ける。標準的なクライアント・サーバモデルの制約の１つは、サービスプロバイダが、ネットワーク内の各クライアントからの要求すべてを連続的に受け入れて実現するためのメカニズムを実装する必要があるために、サービスを受けることのできるクライアントの数が、このようなメカニズムの収容能力に依存するという点である。あるメカニズムは、大型で高速なディスクアレイを有する超並列コンピュータをローカルサーバとして用いる。しかしながら、既存のローカルサーバのうちで最速のものでも、一度に約１，０００から２，０００のクライアントにビデオデータストリームを配信できるにすぎない。したがって、より多くのクライアントにサービスを提供するためには、ローカルサーバの数を増やさなければならない。ローカルサーバの数が増えると、ローカルサーバの制御を維持するために、より多くの上位サーバが必要となる。
【０００４】
標準的なクライアント・サーバモデルが受ける別の制約は、各クライアントが専用の帯域幅を必要とする点である。したがって、必要となる全帯域幅は、加入クライアントの数に正比例する。帯域幅の制約に対処するために、これまでローカルサーバ内のキャッシュメモリが使用されてきたが、キャッシュメモリ自体にも限界があるため、キャッシュメモリを用いても問題は解決されない。
【０００５】
クライアントがより低価格でビデオ・オン・デマンドを利用できるようにするために、既存のサービスプロバイダは、ローカルサーバ当たりのクライアントの割合をローカルサーバの能力を超えて増大させている。典型的に、１，０００のクライアントにサービスを提供できるローカルサーバが、実際には、１０，０００のクライアントに対するサービスを請け負っている。この技術は、加入クライアントの大部分が同時にビデオを注文しないのであれば、機能し得る。しかしながら、大部分のクライアントが同時に（すなわち、夜間や週末に）ビデオの視聴を所望することで、ローカルサーバがオーバーロードされる可能性があるため、この技術の構成には欠陥がある。
【０００６】
したがって、既存のインフラストラクチャを置き換えることなく、実質的にすべての伝送媒体を通して多数のクライアントにオン・デマンドサービスを提供することができるシステムを提供することが望まれている。
【０００７】
【発明の概要】
代表的な実施形態では、サーバ側において、データ・オン・デマンドサービスを提供するためにクライアントにデータを送信する方法は、データファイルを受信するステップと、時間間隔を特定するステップと、時間間隔に基づいてデータファイルを複数のデータブロックに分解することで、その時間間隔中に各データブロックを表示できるようにするステップと、データファイルを送信するために必要とされるタイムスロットの数を決定するステップと、複数のデータブロックのうち少なくとも第１のデータブロックと、随意的に１以上の追加のデータブロックとを、各タイムスロットに割り当てることで、クライアントが、どのタイムスロット中にデータファイルにアクセスしても複数のデータブロックを順番に利用できるようにするステップと、割り当てステップに基づいて複数のデータブロックを送信するステップと、を備える。一実施形態において、分解ステップは、推定データブロックサイズを決定するステップと、チャンネルサーバ内のメモリのクラスタサイズを決定するステップと、推定データブロックサイズおよびクラスタサイズに基づいてデータファイルを分解するステップと、を含む。別の実施形態において、決定ステップは、リソースの割り当てと帯域幅の利用可能性とを評価するステップを含む。
【０００８】
代表的な実施形態では、クライアント側において、データ・オン・デマンドサービスを提供するためにサーバから受信されたデータを処理する方法は、（ａ）第１のタイムスロット中にデータファイルの選択を受信するステップと、（ｂ）第２のタイムスロット中にデータファイルのうちの少なくとも１つのデータブロックを受信するステップと、（ｃ）次のタイムスロット中に、まだ受信されていない任意のデータブロックを受信して、そのデータファイルのデータブロックを順次表示するステップと、データファイルの全データブロックが受信および表示されるまでステップ（ｃ）を繰り返すステップと、を備える。一実施形態では、サーバから受信されたデータを処理するための方法は、クライアント側のセット・トップ・ボックスによって実行される。
【０００９】
代表的な実施形態では、データファイルがいくつかのデータブロックに分割され、スケジューリング行列がデータブロックの数に基づいて生成される。サーバ側で、スケジューリング行列は、データブロックを送信するための送信順序を提供することで、クライアントがいつでも順番にデータブロックにアクセスできるようにする。代表的な実施形態では、データファイルのためのスケジューリング行列を生成する方法は、（ａ）１つのデータファイルのためのデータブロックの数［ｘ］を受信するステップと、（ｂ）第１の変数［ｊ］を０に設定するステップと、（ｃ）第２の変数［ｉ］を０に設定するステップと、（ｄ）参照配列のなかの全エントリを消去するステップと、（ｅ）行列内の列［（ｉ＋ｊ）　ｍｏｄｕｌｏ　ｘ］の行列位置に格納された少なくとも１つのデータブロックを参照配列が含んでいない場合に、そのデータブロックを参照配列に書き込むステップと、（ｆ）参照配列がデータブロック［ｉ］を含んでいない場合に、参照配列および行列の行列位置［（ｉ＋ｊ）　ｍｏｄｕｌｏ　ｘ，ｊ］にデータブロック［ｉ］を書き込むステップと、（ｇ）第２の変数［ｉ］を１だけ増分し、第２の変数［ｉ］がデータブロックの数［ｘ］に等しくなるまでステップ（ｅ）を繰り返すステップと、（ｈ）第１の変数［ｊ］を１だけ増分し、第１の変数［ｊ］がデータブロックの数［ｘ］に等しくなるまでステップ（ｃ）を繰り返すステップと、を備える。一実施形態では、スケジューリング行列は、１セットのデータファイル内のデータファイルごとに生成されるので、その１セットのデータファイルの送信用に、これらスケジューリング行列に基づいて配信行列を生成するために、畳み込み方法が用いられる。
【００１０】
データ・オン・デマンドシステムは、第１のセットのチャンネルサーバと、第１のセットのチャンネルサーバを制御するための中央制御サーバと、第１のセットのチャンネルサーバに接続された第１のセットのアップコンバータと、第１のセットのアップコンバータに接続されたコンバイナ／アンプリファイアと、伝送媒体を介してデータを伝送するよう適合されたコンバイナ／アンプリファイアとを備える。代表的な実施形態において、データ・オン・デマンドシステムは、さらに、システムを監視するためのチャンネル監視モジュールと、スイッチ行列と、第２のセットのチャンネルサーバと、第２のセットのアップコンバータとを備える。チャンネル監視モジュールは、システム障害が起きた際に中央制御サーバに報告するよう構成されている。中央制御サーバは、チャンネル監視モジュールからの報告に応答して、第１のセットのチャンネルサーバの中で不具合を生じたチャンネルサーバを第２のセットのチャンネルサーバ内のチャンネルサーバで置き換え、第１のセットのアップコンバータの中で不具合を生じたアップコンバータを第２のセットのアップコンバータで置き換えるよう、スイッチ行列に命令する。
【００１１】
データ・オン・デマンドサービスを提供するための方法は、データファイルの配信行列を計算するステップと、配信行列に従ってデータファイルを送信することで、多数のクライアントがデータファイルをオン・デマンドで視聴できるようにするステップとを備える。一実施形態では、データファイルはビデオファイルを含む。
【００１２】
本発明のさらに別の実施形態では、すべてのタイムスロットが満杯になり、帯域幅全体が用いられるまで、配信行列内の次のデータブロックを繰り上げることにより、配信行列に生じるアイドルタイムを減少できる。このように、配信行列は、むしろ、元の行列の順番を維持するデータのストリームとして考えられる。いつでも、ユーザは、そのストリームに加わって、開始ブロックが受信されるとすぐにデータ・オン・デマンドサービスを用いることができる。
【００１３】
行列をストリームとして考えることができるので、ユーザは、任意の時間にストリームに入り、開始ブロックを受信してデータ・オン・デマンドサービスを利用するまでの時間だけ待てばよい。その時間は、元の配信行列の所定の時間よりも短いだろう。
【００１４】
本発明の別の実施形態は、ＶＯＤおよびデジタル放送などの複数のデジタルサービスを受信して扱うことができる汎用ＳＴＢを開示している。この実施形態は、受信データの高度な処理が可能である非常に柔軟なアーキテクチャを有する汎用ＳＴＢを開示している。このアーキテクチャは、データバスと、デジタル放送の通信媒体への接続に適した第１の通信装置と、データバスに双方向的に接続された永続および一時メモリを典型的に含むメモリと、データバスに双方向的に接続されたデジタルデータデコーダと、データバスに双方向的に接続された中央処理装置（ＣＰＵ）と、を備える。本発明のこの実施形態のＣＰＵは、メモリと、デジタルデコーダと、デモジュレータとを制御するためのＳＴＢ制御プロセスを実行する。ＳＴＢ制御プロセスは、第１の通信装置で受信されるデータのようなデジタルデータを処理するよう動作可能である。ＳＴＢ制御プロセスは、データブロックの並列ストリーミングだけでなく、アイドルタイム減少スケジューリング行列から引き出されるデータも受信可能であることが好ましい。
【００１５】
【発明の実施の形態】
図１Ａは、本発明の一実施形態に従う代表的なＤＯＤシステム１００を示している。この実施形態では、ＤＯＤシステム１００は、ビデオファイルなどのデータファイルをオン・デマンドで提供する。しかしながら、ＤＯＤシステム１００は、ビデオファイルをオン・デマンドで提供することに限定されず、例えばゲームファイルなど、他のデータファイルをオン・デマンドで提供することもできる。ＤＯＤシステム１００は、中央制御サーバ１０２と、中央ストレージ１０３と、複数のチャンネルサーバ１０４ａ〜１０４ｎと、複数のアップコンバータ１０６ａ〜１０６ｎと、コンバイナ／アンプリファイア１０８とを含む。中央制御サーバ１０２は、チャンネルサーバ１０４を制御する。中央ストレージ１０３は、デジタルフォーマットでデータファイルを格納する。代表的な実施形態では、中央ストレージ１０３に格納されたデータファイルは、ネットワークに接続された中央制御サーバ１０２などの任意の許可コンピュータによって、標準的なネットワークインターフェース（例えば、イーサネット接続）を介してアクセス可能である。各チャンネルサーバ１０４は、１つのチャンネルに割り当てられ、１つのアップコンバータ１０６に接続されている。チャンネルサーバ１０４は、中央制御サーバ１０２からの命令に従って、中央ストレージ１０３から読み出されたデータファイルを提供する。各チャンネルサーバ１０４の出力は、対応するアップコンバータ１０６に適した周波数を有すると共に直交振幅変調（ＱＡＭ）によって変調された中間周波（ＩＦ）信号である。ＱＡＭ変調ＩＦ信号は、採用された規格によって決まる。米国で現在採用されている規格は、データ・オーバー・ケーブル・システムス・インターフェース・スペフィシケイション（ＤＯＣＳＩＳ）規格であり、約４３．７５ＭＨｚのＩＦ周波数を必要とする。アップコンバータ１０６は、チャンネルサーバ１０４から受信されたＩＦ信号を高周波信号（ＲＦ信号）に変換する。ＲＦ信号は、周波数および帯域幅を含んでおり、所望のチャンネルおよび採用規格によって決まる。例えば、米国における現行の規格では、ケーブルテレビチャンネル８０に対して、ＲＦ信号は、約５５９．２５ＭＨｚの周波数と約６ＭＨｚの帯域幅とを有する。アップコンバータ１０６の出力は、コンバイナ／アンプリファイア１０８に送られる。コンバイナ／アンプリファイア１０８は、受信されたＲＦ信号を増幅、調節、および結合し、次いで、伝送媒体１１０へと出力する。
【００１６】
代表的な実施形態では、中央制御サーバ１０２は、サービスプロバイダがドラッグ・アンド・ドロップ動作によってデータ配信をスケジューリングすることを可能とするために、グラフィックユーザインターフェース（図示せず）を備える。さらに、中央制御サーバ１０２は、チャンネルサーバ１０４を認証および制御して、配信行列に従って開始または停止させる。代表的な実施形態では、中央制御サーバ１０２は、チャンネルを自動的に選択し、選択されたチャンネルでデータファイルを伝送するための配信行列を計算する。中央制御サーバ１０２は、データファイル情報（例えば、継続時間、カテゴリ、レーティング、および／または、要旨）のオフラインでの追加、削除、および更新を提供する。さらに、中央制御サーバ１０２は、中央ストレージ１０３に格納されているデータファイルおよびデータベースを更新することによって中央ストレージ１０３を制御する。
【００１７】
代表的な実施形態では、既存のケーブルテレビシステム１２０は、クライアントに非ＤＯＤサービスを提供するために、コンバイナ／アンプリファイア１０８に信号を供給し続けてもよい。したがって、本発明に従ったＤＯＤシステム１００は、現在のケーブルテレビサービスを妨げることはない。
【００１８】
図１Ｂは、本発明に従って、ＤＯＤシステム１００の別の代表的な実施形態を示している。図１Ａに示した要素に加えて、ＤＯＤシステム１００は、スイッチ行列１１２と、チャンネル監視モジュール１１４と、１セットのバックアップ・チャンネルサーバ１１６ａ〜１１６ｂと、１セットのバックアップ・アップコンバータ１１８ａ〜１１８ｂとを含む。一実施形態では、スイッチ行列１１２は、アップコンバータ１０６とコンバイナ／アンプリファイア１０８との間に物理的に設けられる。スイッチ行列１１２は、中央制御サーバ１０２によって制御される。チャンネル監視モジュール１１４は、ＤＯＤシステム１００の正常性を監視するために、潜在的なクライアントをシミュレートするよう構成された複数のセット・トップ・ボックスを備える。監視の結果は、チャンネル監視モジュール１１４によって中央制御サーバ１０２に伝達される。チャンネル障害（すなわち、チャンネルサーバ障害、アップコンバータ障害、または通信回線障害）が生じた場合は、中央制御サーバ１０２は、スイッチ行列１１２を通して、機能不全の構成要素を外すと共に、正常なバックアップ構成要素１１６および／または１１８を用いて、サービスを再開する。
【００１９】
代表的な実施形態では、ＤＯＤシステム１００から放送されているデータファイルは、モーション・ピクチャース・イクスパート・グループ（ＭＰＥＧ）ファイル内に含まれている。各ＭＰＥＧファイルは、時間軸に沿ってデータファイルの特定部分に対してマップするデータブロックおよびサブブロックに動的に分割される。これらのデータブロックおよびサブブロックは、中央制御サーバ１０２によって提供される三次元の配信行列に従って、所定の期間中に送信される。フィードバックチャンネルは、ＤＯＤシステム１００がＤＯＤサービスを提供する際には必要ない。しかしながら、フィードバックチャンネルが利用可能であれば、フィードバックチャンネルは、請求やインターネットサービスの提供など、他の目的のために用いることができる。
【００２０】
図２は、本発明の一実施形態に従う代表的なチャンネルサーバ１０４を示している。チャンネルサーバ１０４は、サーバコントローラ２０２と、ＣＰＵ２０４と、ＱＡＭモジュレータ２０６と、ローカルメモリ２０８と、ネットワークインターフェース２１０とを備える。サーバコントローラ２０２は、データファイルをブロックに（さらに、サブブロックおよびデータパケットに）分割し、中央制御サーバ１０２によって提供された配信行列に従って伝送するためにデータブロックを選択し、選択されたデータをエンコードし、エンコードされたデータを圧縮し、次いで、圧縮されたデータをＱＡＭモジュレータ２０６に送信するよう、ＣＰＵ２０４に命令することにより、チャンネルサーバ１０４の動作全体を制御する。ＱＡＭモジュレータ２０６は、バス（すなわち、ＰＣＩまたはＣＰＵローカルバス）またはイーサネット接続を介して伝送されるデータを受信する。代表的な実施形態では、ＱＡＭモジュレータ２０６は、下流側ＱＡＭモジュレータ、前進型誤り訂正デコーダを備える上流側直交振幅変調／直交位相変位変調方式（ＱＡＭ／ＱＰＳＫ）バーストデモジュレータ、および／または、上流側チューナを備えてもよい。ＱＡＭモジュレータ２０６の出力は、アップコンバータ１０６に直接適用できるＩＦ信号である。
【００２１】
ネットワークインターフェース２１０は、中央制御サーバ１０２からのスケジューリングおよび制御の命令と、中央制御サーバ１０２へのステータスの報告と、中央ストレージ１０３からのデータファイルの受信と、を実行するために、チャンネルサーバ１０４を、他のチャンネルサーバ１０４および中央制御サーバ１０２に接続する。中央ストレージ１０３から読み出された任意のデータファイルは、サーバコントローラ２０２からの命令に従って処理される前に、チャンネルサーバ１０４のローカルメモリ２０８に格納することができる。代表的な実施形態では、チャンネルサーバ１０４は、ケーブルチャンネルの帯域幅（例えば６、６．５、または８ＭＨｚ）と、ＱＡＭ変調（例えばＱＡＭ６４またはＱＡＭ２５６）と、ＤＯＤデータストリームの圧縮規格／ビットレート（すなわち、ＭＰＥＧ−１またはＭＰＥＧ−２）とに応じて、１またはそれ以上のＤＯＤデータストリームを送信してよい。
【００２２】
図３は、本発明の一実施形態に従う汎用セット・トップ・ボックス（ＳＴＢ）３００を示している。ＳＴＢ３００は、ＱＡＭデモジュレータ３０２と、ＣＰＵ３０４と、ローカルメモリ３０８と、バッファメモリ３１０と、ビデオおよびオーディオをデコードできるデコーダ３１２と、グラフィクスオーバーレイモジュール３１４と、ユーザインターフェース３１８と、通信回線３２０と、図のようにこれらの装置を接続する高速データバス３２２と、を備える。ＣＰＵ３０２は、クライアントの要求に応じてデータを選択し、選択されたデータをデコードし、デコードされたデータを解凍し、デコードされたデータを再組み立てし、デコードされたデータをローカルメモリ３０８またはバッファメモリ３１０に格納し、格納されたデータをデコーダ３１２に送信するよう、汎用ＳＴＢ３００の動作全体を制御する。代表的な実施形態では、ローカルメモリ３０８は不揮発性メモリ（例えば、ハードドライブ）を備え、バッファメモリ３１０は揮発性メモリを備える。
【００２３】
一実施形態では、ＱＡＭデモジュレータ３０２は、送信および受信モジュールと、以下に示す要素の内の少なくとも１つとを備える。プライバシ暗号化／復号化モジュール、前進型誤り訂正デコーダ／エンコーダ、チューナ制御、下流側および上流側プロセッサ、ＣＰＵ、および、メモリインターフェース回路。ＱＡＭデモジュレータ３０２は、変調ＩＦ信号を受信し、信号をサンプリングおよび復調してデータを復元する。
【００２４】
代表的な実施形態では、アクセスが許可されると、デコーダ３１２は、少なくとも１つのデータブロックをデコードして、そのデータブロックを出力画面上で表示可能な画像に変換する。デコーダ３１２は、再生、停止、一時停止、コマ送り、巻き戻し、早送りなど、加入クライアントからの命令をサポートする。デコーダ３１２は、クライアントが利用できるように、デコードされたデータを出力装置３２４に提供する。出力装置３２４は、テレビ、コンピュータ、任意の適当なディスプレイモニタ、ＶＣＲなどの任意の適切な装置でよい。
【００２５】
グラフィクスオーバーレイモジュール３１４は、表示されたグラフィクスの質を、例えば、アルファブレンディングまたはピクチャ・イン・ピクチャ機能を提供することによって向上させる。代表的な実施形態において、グラフィクスオーバーレイモジュール３１４は、サービスプロバイダが、本発明に従ったシステムを用いてゲーム・オン・デマンドサービスを提供する際に、ゲームプレイングモード中にグラフィクスを加速させるために用いることもできる。
【００２６】
ユーザインターフェース３１８は、ユーザがＳＴＢ３００を制御することを可能とするものであり、リモートコントロール装置、キーボード、スマートカードなど、任意の適切な装置であってよい。通信回線３２０は、さらなる通信接続を提供する。これは、別のコンピュータに接続されてもよいし、双方向通信を実施するために用いられてもよい。データバス３２２は、本発明に必要とされるリアルタイムでのデータ通信を実行するのに適した市販の「高速」データバスであることが好ましい。適切な例としては、ＵＳＢ、ファイヤワイヤなどが挙げられる。
【００２７】
代表的な実施形態では、データファイルは、すべてのケーブルテレビ加入者に対して放送されるのだが、データ・オン・デマンドサービスをデコードして利用することができるのは、互換性のあるＳＴＢ３００を持っているＤＯＤ加入者のみである。代表的な実施形態では、オン・デマンドでデータファイルを取得するための許可は、ユーザインターフェース３１８のスマートカードシステムを介して取得することができる。スマートカードは、サービスプロバイダが設置した各地の小売店や自動販売機において再支払い可能であってよい。別の代表的な実施形態では、加入者は、定額の料金体系で、利用可能なデータファイルすべてに対して無制限にアクセスできる。
【００２８】
好ましい実施形態では、データ・オン・デマンドの対話式の特徴により、クライアントは、利用可能なデータファイルをいつでも選択できる。クライアントが選択ボタンを押してから、選択されたデータファイルが再生を開始するまでの時間は、応答時間と呼ばれる。ＤＯＤサービスを提供するために割り当てられるリソース（例えば、帯域幅、サーバの能力）が大きいほど、応答時間は短くなる。代表的な実施形態では、応答時間は、リソースの割り当ておよび所望のサービス品質に対する評価に基づいて決定することができる。第１のデータブロックを並列ストリームに置く実施形態と組み合わせると、応答時間は、第１のデータブロックを受信および処理するために掛かる時間だけの要素となる。
【００２９】
一実施形態では、各データファイルのデータブロックの数（ＮＵＭ＿ＯＦ＿ＢＬＫＳ）は、以下のように計算することができる。
【００３０】
【数１】
2004514336.tif 000003
【００３１】
式（１）〜（４）では、Ｅｓｔｉｍａｔｅｄ＿ＢＬＫ＿Ｓｉｚｅは、（バイト数で表される）推定ブロックサイズであり、ＤａｔａＦｉｌｅ＿Ｓｉｚｅは、（バイト数で表される）データファイルサイズであり、ＴＳは、（秒数で表される）タイムスロットの継続時間であり、ＤａｔａＦｉｌｅ＿Ｌｅｎｇｔｈは、（秒数で表される）データファイルの継続時間であり、ＢＬＫ ＳＩＺＥは、データブロックごとに必要とされるクラスタの数であり、ＣＬＵＳＴＥＲ＿ＳＩＺＥは、各チャンネルサーバ１０４のためのローカルメモリ２０８内のクラスタのサイズであり（例えば、６４キロバイトなど）、ＢＬＫ＿ＳＩＺＥ＿ＢＹＴＥＳは、バイト数で表されるブロックサイズである。この実施形態では、ブロックの数（ＮＵＭ＿ＯＦ＿ＢＬＫＳ）は、（バイト数で表される）データファイルサイズに、バイト数で表されるデータブロックのサイズを加え、そこから１バイトを引き、さらに、バイト数で表されるデータブロックサイズで割ったものに等しい。式（１）〜（４）は、１つの具体的な実施形態を示している。当業者にとって、データファイルのデータブロック数を計算するために、他の方法を用いてもよいことは明らかである。例えば、データファイルをいくつかのデータブロックに分割するステップは、主に、チャンネルサーバ１０４のローカルメモリ２０８の推定ブロックサイズおよびクラスタサイズの関数である。したがって、本発明は、上述の具体的な実施形態に限定されない。
【００３２】
図４は、本発明の一実施形態に従うデータファイルを送信するためのスケジューリング行列を生成する代表的なプロセスを示している。代表的な実施形態では、本発明は、サーバ側においてデータ配信を圧縮およびスケジューリングするために、時分割多重化（ＴＤＭ）および周波数分割多重化（ＦＤＭ）技術を用いる。代表的な実施形態では、スケジューリング行列は、データファイルごとに生成される。一実施形態において、各データファイルがいくつかのデータブロックに分割され、スケジューリング行列がデータブロックの数に基づいて生成される。一般に、スケジューリング行列は、データファイルのデータブロックをサーバからクライアントへと送信するための送信順序を提供することで、任意の時間にデータファイルにアクセスしようとする任意のクライアントが、順番にデータブロックにアクセスできるようにする。
【００３３】
ステップ４０２では、データファイルのデータブロックの数（ｘ）が受信される。第１の変数ｊが、０に設定される（ステップ４０４）。参照配列が、消去される（ステップ４０６）。参照配列は、内部管理のためにデータブロックのトラックを維持する。次に、ｊは、ｘと比較される（ステップ４０８）。ｊがｘ未満である場合には、第２の変数ｉが０に設定される（ステップ４１２）。次に、ｉは、ｘと比較される（ステップ４１４）。ｉがｘ未満である場合には、スケジューリング行列の列［（ｉ＋ｊ）　ｍｏｄｕｌｏ　（ｘ）］に格納されたデータブロックが、参照配列に書き込まれる（ステップ４１８）。参照配列がそのようなデータブロックをすでに有している場合には、重複して書き込まない。初めは、スケジューリング行列はまだ何のエントリも有していないので、このステップは省略することができる。次に、参照配列は、データブロックｉを含むか否か調べられる（ステップ４２０）。初めは、参照配列内のエントリはすべてステップ４０６で消去されているので、参照行列内には何も存在しない。参照配列がデータブロックｉを含まない場合には、スケジューリング行列の行列位置［（ｉ＋ｊ）　ｍｏｄｕｌｏ　（ｘ），ｊ］および参照配列に、データブロックｉが追加される（ステップ４２２）。データブロックｉがスケジューリング行列および参照配列に追加された後、ｉ＝ｉ＋１になるようにｉが１だけ増分され（ステップ４２４）、プロセスは、ｉ＝ｘになるまでステップ４１４を繰り返す。参照配列がデータブロックｉを含む場合には、ｉ＝ｉ＋１になるようにｉが１だけ増分され（ステップ４２４）、プロセスは、ｉ＝ｘになるまでステップ４１４を繰り返す。ｉ＝ｘである場合には、ｊ＝ｊ＋１になるようにｊが１だけ増分され（ステップ４１６）、プロセスは、ｊ＝ｘになるまでステップ４０６を繰り返す。プロセス全体は、ｊ＝ｘになると終了する（ステップ４１０）。
【００３４】
代表的な実施形態において、データファイルが６つのデータブロックに分割される（ｘ＝６）場合には、スケジューリング行列および参照配列は、以下のようになる。
【００３５】
【表１】
2004514336.tif 000004
【００３６】
【表２】
2004514336.tif 000005
【００３７】
本願に添付された別表Ａは、上述のスケジューリング行列および参照配列を生成するための図４に示された代表的なプロセスの段階的なプロセスを説明している。この代表的な実施形態では、上述のスケジューリング行列に基づいて、データファイルの６つのデータブロックが、以下の順番で送信される。
【００３８】
【数２】
2004514336.tif 000006
【００３９】
別の代表的な実施形態では、先読みスケジューリング行列を計算して、予測されるアクセス時間に先立ってデータファイルの所定数のデータブロックを送信するために、先読みプロセスを使用することができる。例えば、タイムスロットの番号が４以上の任意のタイムスロットに対して、所定の先読み時間が１タイムスロットの継続時間である場合には、データファイルのデータブロック４（ｂｌｋ４）は、加入クライアントのＳＴＢ３００によって、ＴＳ３またはそれよりも前に受信することが好ましいが、ｂｌｋ４は、ＴＳ４まで再生されない。先読みスケジューリング行列を生成するためのプロセスのステップは、この実施形態での先読みスケジューリング行列が、先読み時間に基づいて早めの送信シーケンスをスケジューリングするという点を除き、図４に関連して上述したプロセスのステップと実質的に同じである。データファイルが６つのデータブロックに分割されると仮定すると、先読みスケジューリング行列に基づいた代表的な送信シーケンスは、２タイムスロットの継続時間の先読み時間を有し、以下のように表すことができる。
【００４０】
【数３】
2004514336.tif 000007
【００４１】
１セットのデータファイルを送信するための三次元の配信行列は、その１セットのデータファイルの各データファイル用のスケジューリング行列に基づいて生成される。三次元の配信行列では、１セットのデータファイルの中の各データファイルのためのＩＤを含む第３の次元が生成される。三次元の配信行列は、各チャンネルの利用可能な帯域幅を効率的に用いて、複数のデータストリームを送信するために計算される。代表的な実施形態では、三次元のデリバリ行列を生成して、１セットのデータファイルの効率的な配信をスケジューリングするために、当該分野において周知である畳み込み方法が用いられる。例えば、畳み込み方法は、以下の方針を含んでよい。（１）任意のタイムスロット（ＴＳ）の継続時間中に送信されるデータブロックの総数は、可能な限り少数に保たれることが望ましい。（２）複数の部分的解決法が方針（１）に対して利用可能である場合は、任意の参照タイムスロットの継続時間中に送信されるデータブロックと、（参照タイムスロットの）前のタイムスロットの継続時間中に送信されるデータブロックと、（参照タイムスロットの）次のタイムスロットの継続時間中に送信されるデータブロックと、を加算することによって得られるデータブロックの和が最小である解決法が好ましい。例えば、２つの短いデータファイルすなわちＭおよびＮを送信する代表的なシステムが想定すると、各データファイルが６つのデータブロックにそれぞれ分割される場合には、スケジューリング行列に基づいた送信シーケンスは、以下のようになる。
【００４２】
【数４】
2004514336.tif 000008
【００４３】
上述したような代表的な畳み込み方法を適用すると、以下のような配信行列の組み合わせが可能である。
【００４４】
【表３】
2004514336.tif 000009
【００４５】
【表４】
2004514336.tif 000010
【００４６】
【表５】
2004514336.tif 000011
【００４７】
【表６】
2004514336.tif 000012
【００４８】
【表７】
2004514336.tif 000013
【００４９】
【表８】
2004514336.tif 000014
【００５０】
方針（１）を適用すると、オプション２、４、６は、任意のタイムスロット中に送信されるデータブロックの最大数が最も小さい（すなわち、６データブロック）。方針（２）を適用すると、この代表的な実施形態での最適な配信行列は、オプション４である。何故なら、オプション４では、任意の参照タイムスロットのデータブロックと、隣接するタイムスロットのデータブロックとの和が最小（すなわち、１６データブロック）であるからである。したがって、この実施形態では、データファイルＮの送信シーケンスは、３タイムスロットだけシフトされることが最も好ましい。代表的な実施形態では、三次元の配信行列は、チャンネルサーバ１０４ごとに生成される。
【００５１】
各データファイルのデータブロックが配信行列に従って送信されると、多数の加入クライアントがいつでもデータファイルにアクセスすることができるので、各加入クライアントは、データファイルの適切なデータブロックを適時に利用することが可能である。上述の例において、タイムスロットの継続時間が５秒間であると仮定すると、ＤＯＤシステム１００は、以下のように、最適な配信行列に従って（すなわち、データファイルＮの配信シーケンスを３タイムスロットだけシフトさせる）、データファイルＭおよびＮのデータブロックを送信する。
【００５２】
【数５】
2004514336.tif 000015
【００５３】
クライアントＡが、時刻００：００：００において映画Ｍを選択すると、クライアントＡのＳＴＢ３００は、データブロックの受信、格納、再生、および拒否を以下のように行う。
【００５４】
【数６】
2004514336.tif 000016
【００５５】
クライアントＢが、時刻００：００：１０において映画Ｍを選択すると、クライアントＢのＳＴＢ３００は、データブロックの受信、格納、再生、および拒否を以下のように行う。
【００５６】
【数７】
2004514336.tif 000017
【００５７】
クライアントＣが、時刻００：００：１５において映画Ｍを選択すると、クライアントＣのＳＴＢ３００は、データブロックの受信、格納、再生、および拒否を以下のように行う。
【００５８】
【数８】
2004514336.tif 000018
【００５９】
クライアントＤが、時刻００：００：３０において映画Ｍを選択すると、クライアントＤのＳＴＢ３００は、データブロックの受信、格納、再生、および拒否を以下のように行う。
【００６０】
【数９】
2004514336.tif 000019
【００６１】
上述の例で示したように、任意の組み合わせのクライアントが、サービスプロバイダによって提供される任意のデータファイルの選択および再生開始を、任意の時間に独立して行うことができる。システムは、タイムスロットによって決定されるデータブロックの連続的なストリームを常に受信しているが、ある任意の時間に、受信ＳＴＢは、ある特定のデータブロックのみを必要として、その他の受信データブロックをすでに受信して格納していてもよいため、「受信」という上述の用語は少し紛らわしい。この要求は、上では「受信」と呼ばれているが、「拒否せず」の方が正確である。したがって、「Ｍ４を受信」は、「Ｍ４以外のすべてを拒否」とすることができ、「受信せず」は、「すべてを拒否」とすることができる。
【００６２】
上述の例から明らかになることは、利用可能な帯域幅が、ある特定のタイムスロット中には完全には利用されていないことである。特に、少なくとも一部のタイムスロット中には、伝送が行われていない「アイドルタイム」が存在する。このアイドルタイムは、利用可能な帯域幅に関する本質的に無駄な利用である。それぞれのタイムスロット中に２つのデータブロックが伝送される上述のオプション４を例に取る。換言すると、６つのデータブロックを伝送するのに適した帯域幅を有するタイムスロットで、４つのデータブロック伝送期間がアイドル状態のままになる。これは、オプション４では劇的ではないが、データファイルが数千データブロックの大きさになると、より極端なものとなる。データを組み合わせるための最適な組み合わせプロトコルを用いても、なお、かなりの部分が、空のブロックスペースとなるだろう。
【００６３】
この空のブロックスペースは、利用されていない帯域幅と同一視されるため、無駄な帯域幅である。本発明の目的は、できる限り多くのアイドルタイムを減少させることであり、したがって、本発明の一実施形態は、スケジューリング行列（本明細書では、アイドルタイム減少スケジューリング行列と呼ぶ）が決定された後に、別のステップを実行することである。
【００６４】
アイドルタイム減少スケジューリング行列の代表的なモデルは、上述の６つのブロックスケジューリング行列を参照して説明できるが、ここでは、便宜上繰り返して説明する。帯域幅をデータブロックの伝送に利用できるアイドルタイムは、明確にするために＜−−＞で示されている。
【００６５】
【数１０】
2004514336.tif 000020
【００６６】
これは、図５に図示されている。スケジューリング行列は、明らかに、ほとんどのタイムスロット内にアイドルタイムの形態で未利用の帯域幅を有している。本発明は、タイムスロットごとに一定の帯域幅を利用することによって、このアイドルタイムを低減することを教示している。一定の帯域幅の利用によってアイドル伝送タイムの低減を実現する鍵は、データブロックの配信シーケンスは遵守される必要があるものの、データブロックがアクセスされる必要のある時間またはそれよりも前に受信されなければならないことを除けば、データブロックが正確なタイムスロットで配信される必要はないことを理解することである。したがって、一定の帯域幅の利用は、スケジューリング行列によって示される配信シーケンスに従って、スケジューリング行列によって割り当てられるタイムスロットに関係なく、各タイムスロットで一定数のデータブロックを伝送することにより実現される。
【００６７】
先に詳述した６つのブロックスケジューリング行列では、ＴＳ０、ＴＳ１、ＴＳ２およびＴＳ４にかなりの量のアイドルタイムが存在する。例えば、タイムスロット当たり４つのデータブロックの伝送に相当する所望の一定の帯域幅を想定する。したがって、アイドルタイムは、４つのデータスロットが各タイムスロット中に伝送されるようスケジューリングされるまで、前方のデータブロックを移動させることにより減少される。そのための手順は、シーケンス内の次のデータブロックを取って、それを空のスペースに移動させることである。故に、この例では、ＴＳ１内の第１のブロックｂｌｋ０がＴＳ０に移動される。さらに、ＴＳ１内の次のブロックｂｌｋ１が繰り上げられる。次いで、ＴＳ０は、まだ、空のデータブロックスペースを有しているので、さらに、ＴＳ１からｂｌｋ３が繰り上げられる。これで、ＴＳ０はスペースがすべて満たされ、以下のようになる。
【００６８】
【数１１】
2004514336.tif 000021
【００６９】
この時点で、ＴＳ１とＴＳ２のほとんどは空なので、ＴＳ３からデータブロックが繰り上げられる。この手順が終わると、行列は以下のようになる。
【００７０】
【数１２】
2004514336.tif 000022
【００７１】
これは、図６にも図示されている。この例のＴＳ４およびＴＳ５のように、空のタイムスロットと不完全なタイムスロットは、元のシーケンスを繰り返して、さらにアイドルタイムを埋めることにより、埋められる。したがって、第１の６つのタイムスロットは以下のようになる。
【００７２】
【数１３】
2004514336.tif 000023
【００７３】
このシーケンス内の次の２つのタイムスロットＴＳ６およびＴＳ７は、ＴＳ２およびＴＳ３と同じデータブロックを有する。したがって、新たな短いスケジューリング行列で、このプロセスによって実際に生成されるものは、４タイムスロットの長さにすぎない。図７は、アイドルタイムを埋めることによって生成される新しい反復行列を示している。
【００７４】
上述の例から、元々の順序が維持される限り、ユーザは、元のスケジューリング行列のオンタイム配信と違って、前もってデータファイルを受信することができることは明らかである。ユーザは、システムの中間のタイムスロットに入って、開始ブロックｂｌｋ０が受信されるとすぐにデータの利用を開始してもよい。
【００７５】
このように、データブロックが連続的なストリームになると、タイムスロットは、ほとんど計算上のフィクションとなるため、ストリームの任意の時点で、ユーザは、システムに入りデータの受信を開始してよい。図８に示すように、この追加のステップは、手順４１０の終了の位置したところで実行される比較的簡単なステップ５１０である。
【００７６】
簡単のため、図４〜１０の説明では、選択された帯域幅が、整数であるデータブロック数に等しい定数に設定された場合を扱った。しかしながら、その一定の帯域幅は、整数であるデータブロック数に等しい必要はない。むしろ、単に、配信シーケンスが、図８で作成されたシーケンスに従えばよい。図８で作成された配信シーケンスによって生成されるデータストリームは、次に、デジタルデータの放送を制御する下位のハードウェアデバイス（例えば、ネットワークカードまたはチャンネルサーバ）に提供される。整数のデータブロックを放送するというより、下位のハードウェアデバイスは、ファイルに割り当てられた帯域幅の範囲でできる限り多くのデータを伝送する。
【００７７】
当業者にとって明らかなように、配信シーケンスの抽象化レベルでは、データの実際の伝送を気にする必要はない。代わりに、配信行列がシーケンスを提供し、下位のハードウェアデバイスが、割り当てられた帯域幅を用いてデータの放送を制御する。したがって、割り当てられた帯域幅のうち、一部分のデータブロックサイズしか含まないものを完全に利用できる。割り当てられた帯域幅が利用されると、下位のデバイスは、帯域幅が再び利用可能となるまで、この特定のデータファイルの放送を中断する。
【００７８】
全体の動作：
サービスプロバイダは、放送に先立って、いくつかのデータファイル（例えばビデオファイル）をチャンネルサーバ１０４に送信するようスケジューリングすることができる。中央制御サーバ１０２は、三次元の配信行列（ＩＤ、タイムスロット、およびデータブロック送信順序）を計算してチャンネルサーバ１０４に送信する。放送中に、チャンネルサーバ１０４は、適切なデータブロックを適切な順序で送信するために三次元の配信行列を参照する。各データファイルは、複数のデータブロックに分割されるので、多数の加入クライアントが、独立して、任意の時間に連続的かつ順番にデータファイルの視聴を始めることができる。データファイルのデータブロックのサイズは、選択されたタイムスロットの継続時間と、データファイルのデータストリームのビットレートとに依存する。例えば、ビットレートが一定のＭＰＥＧデータストリームでは、各データブロックは、以下の式で表される固定サイズを有する。ブロックサイズ（メガバイト）＝ビットレート（メガバイト毎秒）×ＴＳ（秒）／８…（１）。
【００７９】
代表的な実施形態では、データブロックのサイズは、チャンネルサーバ１０４のローカルメモリ２０８内のメモリクラスタサイズの倍数になるように切り上げされる。例えば、上述の式（１）に従って計算されたデータブロックの長さが７２０キロバイトであり、ローカルメモリ２０８のクラスタサイズが６４キロバイトである場合は、結果として、データブロックの長さは７６８キロバイトであることが好ましい。この実施形態において、データブロックは、クラスタサイズと同じサイズをそれぞれ有する複数のサブブロックにさらに分割されることが好ましい。この例では、データブロックは、６４キロバイトである１２のサブブロックを有する。
【００８０】
サブブロックは、さらにデータパケットに分割することができる。各データパケットは、パケットヘッダとパケットデータとを含む。パケットデータの長さは、各チャンネルサーバのＣＰＵのデータ送信先である物理層の最大伝送単位（ＭＴＵ）に依存する。好ましい実施形態では、パケットヘッダおよびパケットデータの合計サイズは、ＭＴＵ未満であることが好ましい。しかしながら、最大限の効率を得るためには、パケットデータの長さはできるだけ長いことが好ましい。
【００８１】
代表的な実施形態では、パケットヘッダのデータは、加入クライアントのＳＴＢ３００が、任意の受信データをデコードして、データパケットが選択データファイルに属するか否かを決定することを許可する情報（例えば、プロトコル署名、バージョン、ＩＤ、またはパケットタイプ情報など）を含む。パケットヘッダは、さらに、ブロック／サブブロック／パケット番号、パケット長、サブブロック内での巡回冗長検査（ＣＲＣ）およびオフセット、および／またはエンコード情報など、他の情報を含んでもよい。
【００８２】
チャンネルサーバ１０４によって受信されると、データパケットは、ＱＡＭモジュレータ２０６に送信され、そこで、ＱＡＭ変調されたＩＦ出力信号を生成するために別のヘッダを追加される。ＱＡＭモジュレータ２０６に対する最大ビットレート出力は、利用可能な帯域幅に依存する。例えば、６ＭＨｚの帯域幅を有するＱＡＭモジュレータ２０６では、最大ビットレートは５．０５（ビット／シンボル）×６（ＭＨｚ）＝３０．３メガビット／秒である。
【００８３】
ＱＡＭ変調されたＩＦ信号は、アップコンバータ１０６に送信され、ある特定のチャンネルに適したＲＦ信号（例えばＣＡＴＶチャンネル８０では、５５９．２５０ＭＨｚで、６ＭＨｚの帯域幅）に変換される。例えば、ケーブルネットワークが高い帯域幅（またはビットレート）を有する場合には、各チャンネルは、それぞれが仮想サブチャンネルを占有する２以上のデータストリームを提供するために用いることができる。例えば、ＱＡＭ変調を用いて、３つのＭＰＥＧ１データストリームを６ＭＨｚチャンネルに適合させることができる。アップコンバータ１０６の出力は、結合された信号を伝送媒体１１０に送信するコンバイナ／アンプリファイア１０８に送られる。
【００８４】
代表的な実施形態では、「Ｎ」個のデータストリームを伝送するためのシステム帯域幅（ＢＷ）の合計は、ＢＷ＝Ｎ×ｂｗであり、ｂｗは、データストリーム当たりに必要な帯域幅である。例えば、各ＭＰＥＧ−１データストリームは、９メガビット／秒のシステム帯域幅を占めるので、３つのＭＰＥＧ−１データストリームは、３０．３メガビット／秒のシステム帯域幅を有するＤＯＣＳＩＳケーブルチャンネルによって、同時に伝送することができる。
【００８５】
一般に、帯域幅は、ＤＯＤサービスに実際にアクセスしている加入クライアントの数に関係なく消費される。したがって、ＤＯＤサービスを利用している加入クライアントが存在しない場合でも、システムのオン・デマンド能力を確保するために、やはり帯域幅が消費される。
【００８６】
ＳＴＢ３００は、作動されると、ＳＴＢ３００のローカルメモリ３０８に格納された番組ガイドの受信および更新を連続的に行う。代表的な実施形態では、ＳＴＢ３００は、最新の番組ガイドを含むデータファイル情報をＴＶ画面上に表示する。ビデオファイル情報などのデータファイル情報は、映画のＩＤ、映画のタイトル、（複数言語での）説明、カテゴリ（例えば、アクションや子供向けなど）、格付け（例えばＲ指定やＰＧ１３指定など）、ケーブル会社の方針（例えば、値段や無料試聴の長さなど）、加入期間、映画のポスタ、および映画の予告を含んでよい。代表的な実施形態では、データファイル情報は、ファームウェアの更新、コマーシャル、および／または緊急情報のために確保されたチャンネルなど、確保された物理チャンネルを介して送信される。別の代表的な実施形態では、情報は、他のデータストリームによって共有された物理チャンネルで送信される。
【００８７】
加入クライアントは、テレビ画面上に表示されたカテゴリごとの配列の利用可能データファイルのリストを見ることができる。クライアントが利用可能データファイルの１つを選択すると、ＳＴＢ３００は、そのデータファイルのデータパケットの受信を開始するために、ハードウェアを制御して、対応する物理チャンネルおよび／または仮想サブチャンネルに同調する。ＳＴＢ３００は、すべてのデータパケットヘッダを検査し、データパケット内のデータをデコードし、受信されたデータパケットを保存すべきか否かを決定する。ＳＴＢ３００が、データパケットを保存すべきでないと決定した場合は、そのデータパケットは廃棄される。そうでない場合は、データパケットは、後の読み出しに備えてローカルメモリ３０８に保存されるか、あるいは、デコーダ３１２に送信されるまで、バッファメモリ３１０に一時的に格納される。
【００８８】
ローカルメモリ３０８に対する頻繁な読み出し／書き込みを回避することによって性能効率を向上させるため、代表的な実施形態において、ＳＴＢ３００は、メモリバッファ３１０内の予測されるデータブロックを、可能であればいつでもロックする「スライディングウィンドウ」予測技術を用いる。予測ウィンドウにおいてヒットが生じた場合、データブロックは、メモリバッファ３１０から直接、デコーダ３１２へと伝送される。予測ミスが生じた場合、データブロックは、メモリバッファ３１０からデコーダ３１２へと伝送される前に、ローカルメモリ３０８からメモリバッファ３１０へと読み込まれる。
【００８９】
代表的な実施形態では、ＳＴＢ３００は、一時停止、スローモーション再生、巻き戻し、ズーム、およびシングルステップのためのボタンを備える赤外線（ＩＲ）リモコン装置ボタン、ＩＲキーボード、またはフロントパネル押しボタンを介して、加入クライアントの命令に応じる。代表的な実施形態では、加入クライアントが所定の期間に何のアクションも入力しなかった場合には、スケジューリングされたコマーシャルが自動的に再生される。スケジューリングされたコマーシャルは、加入クライアントがアクションを提供したとき（例えば、リモコン装置のボタンを押したとき）に自動的に停止される。別の代表的な実施形態では、ＳＴＢ３００は、ビデオの再生中にコマーシャルを自動的に挿入することができる。サービスプロバイダ（例えば、ケーブル会社）は、再生中のビデオにどれくらいの頻度でコマーシャルを割り込ませることが好ましいかを指示する価格決定方針を設定することができる。
【００９０】
緊急情報ビットがデータパケットヘッダ内で発見された場合は、ＳＴＢ３００は、あらゆるデータ受信動作を一時停止し、データファイル情報の受信用に確保されているチャンネルに同調するようハードウェアを制御して、出力画面上に表示すべきあらゆる緊急情報を取得およびデコードする。代表的な実施形態において、ＳＴＢ３００が待機状態の際には、ＳＴＢ３００は、データファイル情報の受信用に確保されたチャンネルに同調され、あらゆる緊急情報を遅滞なく受信および表示する用意が常に整っている。
【００９１】
上述の例は、本発明の特定の代表的な実施形態を例示したものであり、当業者は、これらから、他の実施形態、変形例、変更例を容易に導くことができるだろう。したがって、本発明は、上述した特定の実施形態に限定されず、添付した特許請求の範囲によって規定される。
【図面の簡単な説明】
【図１Ａ】本発明の一実施形態に従う代表的なＤＯＤシステムを示す図である。
【図１Ｂ】本発明の別の実施形態に従う代表的なＤＯＤシステムを示す図である。
【図２】本発明の一実施形態に従う代表的なチャンネルサーバを示す図である。
【図３】本発明の一実施形態に従う代表的なセット・トップ・ボックスを示す図である。
【図４】本発明の一実施形態に従うスケジューリング行列を生成する代表的なプロセスを示す図である。
【図５】６つのデータブロックファイルのスケジューリング行列の例を示す図である。
【図６】すべてのアイドルタイムスロットが満杯になるまで、図６のスケジューリング行列のデータブロックが繰り上げられる様子を示す図である。
【図７】新しいアイドルタイム減少スケジューリング行列を示す図である。
【図８】アイドルタイム減少の実施形態の追加を示す図である。
【図９】アイドルタイム減少の実施形態が実現される方法を示すフローチャート。
【図１０】元のスケジューリング行列から作成される反復データの複数ストリームを示す図である。
【符号の説明】
１００…ＤＯＤシステム
１０２…中央制御サーバ
１０３…中央ストレージ
１０４ａ〜１０４ｎ…チャンネルサーバ
１０６ａ〜１０６ｎ…アップコンバータ
１０８…コンバイナ／アンプリファイア
１１０…伝送媒体
１１２…スイッチ行列
１１４…チャンネル監視モジュール
１１６ａ〜１１６ｂ…バックアップ・チャンネルサーバ
１１８ａ〜１１８ｂ…バックアップ・アップコンバータ
１２０…ケーブルテレビシステム
２０２…サーバコントローラ
２０４…ＣＰＵ
２０６…ＱＡＭモジュレータ
２０８…ローカルメモリ
２１０…ネットワークインターフェース
３００…汎用セット・トップ・ボックス
３０２…ＱＡＭデモジュレータ
３０４…ＣＰＵ
３０８…ローカルメモリ
３１０…バッファメモリ
３１２…デコーダ
３１４…グラフィクスオーバーレイモジュール
３１８…ユーザインターフェース
３２０…通信回線
３２２…高速データバス
３２４…出力装置
【図１Ａ】
2004514336.tif 000024
【図１Ｂ】
2004514336.tif 000025
【図２】
2004514336.tif 000026
【図３】
2004514336.tif 000027
【図４】
2004514336.tif 000028
【図５】
2004514336.tif 000029
【図６】
2004514336.tif 000030
【図７】
2004514336.tif 000031
【図８】
2004514336.tif 000032
【図９】
2004514336.tif 000033
【図１０】
2004514336.tif 000034
【国際公開パンフレット】
2004514336.tif 000035
2004514336.tif 000036
2004514336.tif 000037
2004514336.tif 000038
2004514336.tif 000039
2004514336.tif 000040
2004514336.tif 000041
2004514336.tif 000042
2004514336.tif 000043
2004514336.tif 000044
2004514336.tif 000045
2004514336.tif 000046
2004514336.tif 000047
2004514336.tif 000048
2004514336.tif 000049
2004514336.tif 000050
2004514336.tif 000051
2004514336.tif 000052
2004514336.tif 000053
2004514336.tif 000054
2004514336.tif 000055
2004514336.tif 000056
2004514336.tif 000057
2004514336.tif 000058
2004514336.tif 000059
2004514336.tif 000060
2004514336.tif 000061
2004514336.tif 000062
2004514336.tif 000063
2004514336.tif 000064
2004514336.tif 000065
2004514336.tif 000066
2004514336.tif 000067
2004514336.tif 000068
2004514336.tif 000069
2004514336.tif 000070
2004514336.tif 000071
2004514336.tif 000072
2004514336.tif 000073
2004514336.tif 000074
2004514336.tif 000075
2004514336.tif 000076
2004514336.tif 000077
【手続補正書】
【提出日】平成14年7月10日(2002.7.10)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
以下では、６つのデータブロックを有するデータファイル用のスケジューリング行列を生成するための図４に示した代表的なプロセスが段階的に説明されている。
（ステップ４０２）データファイルのデータブロック数（ｘ）を受信する。ただし、データブロック数は６に等しい（ｘ＝６）と仮定する。
（ステップ４０４）ｊ＝０に設定する。
（ステップ４０６）参照配列（ＲＡ）を消去する。
（ステップ４０８）ｊとｘを比較する。
（ステップ４１２）ｊはｘ未満である（０＜６）ため、ｉ＝０とする。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（０＜６）。ＳＭ内の列［０］の行列位置を読み出し、ＲＡに書き込む。初めは、ＳＭは空なので、ＲＡには何も書き込まれない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ０を含むか？
（ステップ４２２）ＲＡは、空であるので何も含まない。ｂｌｋ０を、ＳＭ内の位置［０，０］およびＲＡに書き込む。
（ステップ４２４）ｉに１を追加し（ｉ＝１）、位置［１，０］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（１＜６）。ＳＭ内の列［１］の行列位置を読み出し、ＲＡに書き込む。初めは、ＳＭは空なので、ＲＡには何も書き込まれない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ１を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ１を含まない。ｂｌｋ１を、ＳＭ内の位置［１，０］およびＲＡに書き込む。
（ステップ４２４）ｉに１を追加し（ｉ＝２）、位置［２，０］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（２＜６）。ＳＭ内の列［２］の行列位置を読み出し、ＲＡに書き込む。初めは、ＳＭは空なので、ＲＡには何も書き込まれない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ２を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ２を含まない。ｂｌｋ２を、ＳＭ内の位置［２，０］およびＲＡに書き込む。
（ステップ４２４）ｉに１を追加し（ｉ＝３）、位置［３，０］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（３＜６）。ＳＭ内の列［３］の行列位置を読み出し、ＲＡに書き込む。初めは、ＳＭは空なので、ＲＡには何も書き込まれない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ３を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ３を含まない。ｂｌｋ３を、ＳＭ内の位置［３，０］およびＲＡに書き込む。
（ステップ４２４）ｉに１を追加し（ｉ＝４）、位置［４，０］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（４＜６）。ＳＭ内の列［４］の行列位置を読み出し、ＲＡに書き込む。初めは、ＳＭは空なので、ＲＡには何も書き込まれない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ４を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ４を含まない。ｂｌｋ４を、ＳＭ内の位置［４，０］およびＲＡに書き込む。
（ステップ４２４）ｉに１を追加し（ｉ＝５）、位置［５，０］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（５＜６）。ＳＭ内の列［５］の行列位置を読み出し、ＲＡに書き込む。初めは、ＳＭは空なので、ＲＡには何も書き込まれない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ５を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ５を含まない。ｂｌｋ５を、ＳＭ内の位置［５，０］およびＲＡに書き込む。
（ステップ４２４）ｉに１を加える（ｉ＝６）。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１６）ｉはｘに等しい（６＝６）。ｊを１だけ増分させる（ｊ＝１）。ステップ４０６に戻る。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
（ステップ４０６）参照配列（ＲＡ）を消去する。
（ステップ４０８）ｊとｘを比較する。
（ステップ４１２）ｊはｘ未満である（０＜６）ため、ｉ＝０とする。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（０＜６）。ＳＭ内の列［１］の行列位置を読み出し、ＲＡに書き込む。位置［１，０］はｂｌｋ１を含むので、ＲＡにｂｌｋ１が書き込まれる。その他の位置は、すべて空である。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ０を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ０を含まない。ｂｌｋ０を、ＳＭ内の位置［１，１］およびＲＡに書き込む。ＲＡは、現時点でｂｌｋ１およびｂｌｋ０を有する。
（ステップ４２４）ｉに１を追加し（ｉ＝１）、位置［２，１］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（１＜６）。ＳＭ内の列［２］の行列位置を読み出し、ＲＡに書き込む。位置［２，０］は、ｂｌｋ２を含む。その他の位置は、すべて空である。ＲＡは、現時点でｂｌｋ１、ｂｌｋ０、およびｂｌｋ２を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ１を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ１を含む。したがって、位置［２，１］には何も書き込まれない。ｉに１を追加し（ｉ＝２）、位置［３，１］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（２＜６）。ＳＭ内の列［３］の行列位置を読み出し、ＲＡに書き込む。位置［３，０］は、ｂｌｋ３を含む。その他の位置は、すべて空である。ＲＡは、現時点でｂｌｋ１、ｂｌｋ０、ｂｌｋ２、およびｂｌｋ３を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ２を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ２を含む。したがって、位置［３，１］には何も書き込まれない。ｉに１を追加し（ｉ＝３）、位置［４，１］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（３＜６）。ＳＭ内の列［４］の行列位置を読み出し、ＲＡに書き込む。位置［４，０］は、ｂｌｋ４を含む。その他の位置は、すべて空である。ＲＡは、現時点でｂｌｋ１、ｂｌｋ０、ｂｌｋ２、ｂｌｋ３、およびｂｌｋ４を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ３を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ３を含む。したがって、位置［４，１］には何も書き込まれない。ｉに１を追加し（ｉ＝４）、位置［５，１］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（４＜６）。ＳＭ内の列［５］の行列位置を読み出し、ＲＡに書き込む。位置［５，０］は、ｂｌｋ５を含む。その他の位置は、すべて空である。ＲＡは、現時点でｂｌｋ１、ｂｌｋ０、ｂｌｋ２、ｂｌｋ３、ｂｌｋ４、およびｂｌｋ５を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ４を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ４を含む。したがって、位置［５，１］には何も書き込まれない。ｉに１を追加し（ｉ＝５）、位置［０，１］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（５＜６）。ＳＭ内の列［０］の行列位置を読み出し、ＲＡに書き込む。位置［０，０］は、ｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは既にｂｌｋ０を含んでいるので、ｂｌｋ０は廃棄される。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ５を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ５を含む。したがって、位置［０，１］には何も書き込まれない。ｉに１を加える（ｉ＝６）。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１６）ｉはｘに等しい（６＝６）。ｊを１だけ増分させる（ｊ＝２）。ステップ４０６に戻る。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
（ステップ４０６）参照配列（ＲＡ）を消去する。
（ステップ４０８）ｊとｘを比較する。
（ステップ４１２）ｊはｘ未満である（２＜６）ため、ｉ＝０とする。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（０＜６）。ＳＭ内の列［２］の行列位置を読み出し、ＲＡに書き込む。位置［２，０］は、ｂｌｋ２を含む。その他の位置は、すべて空である。ＲＡは、この時点でｂｌｋ２を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ０を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ０を含まない。ｂｌｋ０を、ＳＭ内の位置［２，２］およびＲＡに書き込む。ＲＡは、現時点でｂｌｋ２およびｂｌｋ０を有する。
（ステップ４２４）ｉに１を追加し（ｉ＝１）、位置［３，２］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（１＜６）。ＳＭ内の列［３］の行列位置を読み出し、ＲＡに書き込む。位置［３，０］は、ｂｌｋ３を含む。その他の位置は、すべて空である。ＲＡは、現時点でｂｌｋ２、ｂｌｋ０、およびｂｌｋ３を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ１を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ１を含まない。ｂｌｋ１を、ＳＭ内の位置［３，２］およびＲＡに書き込む。ＲＡは、現時点でｂｌｋ２、ｂｌｋ０、ｂｌｋ３、およびｂｌｋ１を有する。
（ステップ４２４）ｉに１を追加し（ｉ＝２）、位置［４，２］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（２＜６）。ＳＭ内の列［４］の行列位置を読み出し、ＲＡに書き込む。位置［４，０］は、ｂｌｋ４を含む。その他の位置は、すべて空である。ＲＡは、現時点でｂｌｋ２、ｂｌｋ０、ｂｌｋ３、ｂｌｋ１、およびｂｌｋ４を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ２を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ２を含む。したがって、位置［４，２］には何も書き込まれない。ｉに１を追加し（ｉ＝３）、位置［５，２］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（３＜６）。ＳＭ内の列［５］の行列位置を読み出し、ＲＡに書き込む。位置［５，０］は、ｂｌｋ５を含む。その他の位置は、すべて空である。ＲＡは、現時点でｂｌｋ２、ｂｌｋ０、ｂｌｋ３、ｂｌｋ１、ｂｌｋ４、およびｂｌｋ５を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ３を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ３を含む。したがって、位置［５，２］には何も書き込まれない。ｉに１を追加し（ｉ＝４）、位置［０，２］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（４＜６）。ＳＭ内の列［０］の行列位置を読み出し、ＲＡに書き込む。位置［０，０］は、ｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは既にｂｌｋ０を含んでいるので、ｂｌｋ０は廃棄される。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ４を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ４を含む。したがって、位置［０，２］には何も書き込まれない。ｉに１を追加し（ｉ＝５）、位置［１，２］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（５＜６）。ＳＭ内の列［１］の行列位置を読み出し、ＲＡに書き込む。位置［１，０］はｂｌｋ１を含み、位置［１，１］はｂｌｋ０を含む。ＲＡは、既にｂｌｋ１およびｂｌｋ０を含む。したがって、ｂｌｋ１とｂｌｋ０は廃棄される。その他の位置は、すべて空である。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ５を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ５を含む。したがって、位置［１，２］には何も書き込まれない。ｉに１を加える（ｉ＝６）。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１６）ｉはｘに等しい（６＝６）。ｊを１だけ増分させる（ｊ＝３）。ステップ４０６に戻る。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
（ステップ４０６）参照配列（ＲＡ）を消去する。
（ステップ４０８）ｊとｘを比較する。
（ステップ４１２）ｊはｘ未満である（３＜６）ため、ｉ＝０とする。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（０＜６）。ＳＭ内の列［３］の行列位置を読み出し、ＲＡに書き込む。位置［３，０］はｂｌｋ３を含み、位置［３，２］はｂｌｋ１を含む。ｂｌｋ３とｂｌｋ１がＲＡに書き込まれる。その他の位置は、すべて空である。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ０を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ０を含まない。ｂｌｋ０を、ＳＭ内の位置［３，３］およびＲＡに書き込む。ＲＡは、現時点でｂｌｋ３、ｂｌｋ１、およびｂｌｋ０を有する。
（ステップ４２４）ｉに１を追加し（ｉ＝１）、位置［４，３］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（１＜６）。ＳＭ内の列［４］の行列位置を読み出し、ＲＡに書き込む。位置［４，０］は、ｂｌｋ４を含む。その他の位置は、すべて空である。ＲＡは、現時点でｂｌｋ３、ｂｌｋ１、ｂｌｋ０、およびｂｌｋ４を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ１を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ１を含む。したがって、位置［４，３］には何も書き込まれない。ｉに１を追加し（ｉ＝２）、位置［５，３］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（２＜６）。ＳＭ内の列［５］の行列位置を読み出し、ＲＡに書き込む。位置［５，０］は、ｂｌｋ５を含む。その他の位置は、すべて空である。ＲＡは、現時点でｂｌｋ３、ｂｌｋ１、ｂｌｋ０、ｂｌｋ４、およびｂｌｋ５を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ２を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ２を含まない。ｂｌｋ２を、ＳＭの位置［５，３］およびＲＡに書き込む。ＲＡは、現時点でｂｌｋ３、ｂｌｋ１、ｂｌｋ０、ｂｌｋ４、ｂｌｋ５、およびｂｌｋ２を有する。
（ステップ４２４）ｉに１を追加し（ｉ＝３）、位置［０，３］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（３＜６）。ＳＭ内の列［０］の行列位置を読み出し、ＲＡに書き込む。位置［０，０］は、ｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは既にｂｌｋ０を含んでいるので、ｂｌｋ０は廃棄される。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ３を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ３を含む。したがって、位置［０，３］には何も書き込まれない。ｉに１を追加し（ｉ＝４）、位置［１，３］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（４＜６）。ＳＭ内の列［１］の行列位置を読み出し、ＲＡに書き込む。位置［１，０］はｂｌｋ１を含み、位置［１，１］はｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは、既にｂｌｋ１とｂｌｋ０を含むので、重複して書き込まない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ４を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ４を含む。したがって、位置［１，３］には何も書き込まれない。ｉに１を追加し（ｉ＝５）、位置［２，３］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（５＜６）。ＳＭ内の列［２］の行列位置を読み出し、ＲＡに書き込む。位置［２，０］はｂｌｋ２を含み、位置［２，２］はｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは、既にｂｌｋ２とｂｌｋ０を含むので、重複して書き込まない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ５を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ５を含む。したがって、位置［２，３］には何も書き込まれない。ｉに１を加える（ｉ＝６）。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１６）ｉはｘに等しい（６＝６）。ｊを１だけ増分させる（ｊ＝４）。ステップ４０６に戻る。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
（ステップ４０６）参照配列（ＲＡ）を消去する。
（ステップ４０８）ｊとｘを比較する。
（ステップ４１２）ｊはｘ未満である（４＜６）ため、ｉ＝０とする。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（０＜６）。ＳＭ内の列［４］の行列位置を読み出し、ＲＡに書き込む。位置［４，０］は、ｂｌｋ４を含む。ｂｌｋ４が、ＲＡに書き込まれる。その他の位置は、すべて空である。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ０を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ０を含まない。ｂｌｋ０を、ＳＭ内の位置［４，４］およびＲＡに書き込む。ＲＡは、現時点でｂｌｋ４およびｂｌｋ０を有する。
（ステップ４２４）ｉに１を追加し（ｉ＝１）、位置［５，４］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（１＜６）。ＳＭ内の列［５］の行列位置を読み出し、ＲＡに書き込む。位置［５，０］はｂｌｋ５を含み、位置［５，３］はｂｌｋ２を含む。その他の位置は、すべて空である。ＲＡは、現時点でｂｌｋ４、ｂｌｋ０、ｂｌｋ５、およびｂｌｋ２を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ１を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ１を含まない。ｂｌｋ１を、ＳＭの位置［５，４］およびＲＡに書き込む。ＲＡは、現時点でｂｌｋ４、ｂｌｋ０、ｂｌｋ５、ｂｌｋ２、およびｂｌｋ１を有する。
（ステップ４２４）ｉに１を追加し（ｉ＝２）、位置［０，４］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（２＜６）。ＳＭ内の列［０］の行列位置を読み出し、ＲＡに書き込む。位置［０，０］は、ｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは、既にｂｌｋ０を含むので、重複して書き込まない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ２を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ２を含む。ｉに１を追加し（ｉ＝３）、位置［１，４］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（３＜６）。ＳＭ内の列［１］の行列位置を読み出し、ＲＡに書き込む。位置［１，０］はｂｌｋ１を含み、位置［１，１］（抜け？）。その他の位置は、すべて空である。ＲＡは、既にｂｌｋ１とｂｌｋ０を含むので、重複して書き込まない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ３を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ３を含まない。ｂｌｋ３を、ＳＭの位置［１，４］およびＲＡに書き込む。ＲＡは、現時点でｂｌｋ４、ｂｌｋ０、ｂｌｋ５、ｂｌｋ２、ｂｌｋ１、およびｂｌｋ３を有する。
（ステップ４２４）ｉに１を追加し（ｉ＝４）、位置［２，４］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（４＜６）。ＳＭ内の列［２］の行列位置を読み出し、ＲＡに書き込む。位置［２，０］はｂｌｋ２を含み、位置［２，２］はｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは、既にｂｌｋ２とｂｌｋ０を含むので、重複して書き込まない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ４を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ４を含む。したがって、位置［２，４］には何も書き込まれない。ｉに１を追加し（ｉ＝５）、位置［３，４］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（５＜６）。ＳＭ内の列［３］の行列位置を読み出し、ＲＡに書き込む。位置［３，０］はｂｌｋ３を含み、位置［３，２］はｂｌｋ１を含み、位置［３，３］はｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは、既にｂｌｋ３、ｂｌｋ１、およびｂｌｋ０を含むので、重複して書き込まない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ５を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ５を含む。したがって、位置［３，４］には何も書き込まれない。ｉに１を加える（ｉ＝６）。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１６）ｉはｘに等しい（６＝６）。ｊを１だけ増分させる（ｊ＝５）。ステップ４０６に戻る。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
（ステップ４０６）参照配列（ＲＡ）を消去する。
（ステップ４０８）ｊとｘを比較する。
（ステップ４１２）ｊはｘ未満である（５＜６）ため、ｉ＝０とする。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（０＜６）。ＳＭ内の列［５］の行列位置を読み出し、ＲＡに書き込む。位置［５，０］はｂｌｋ５を含み、位置［５，３］はｂｌｋ２を含み、位置［５，４］はｂｌｋ１を含む。ｂｌｋ５、ｂｌｋ２、およびｂｌｋ１がＲＡに書き込まれる。その他の位置は、すべて空である。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ０を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ０を含まない。ｂｌｋ０を、ＳＭ内の位置［５，５］およびＲＡに書き込む。ＲＡは、現時点でｂｌｋ５、ｂｌｋ２、ｂｌｋ１、およびｂｌｋ０を有する。
（ステップ４２４）ｉに１を追加し（ｉ＝１）、位置［０，５］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（１＜６）。ＳＭ内の列［０］の行列位置を読み出し、ＲＡに書き込む。位置［０，０］はｂｌｋ０を含み、その他の位置はすべて空である。ＲＡは、現時点でｂｌｋ５、ｂｌｋ２、ｂｌｋ１、およびｂｌｋ０を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ１を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ１を含む。ｉに１を追加し（ｉ＝２）、位置［１，５］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（２＜６）。ＳＭ内の列［１］の行列位置を読み出し、ＲＡに書き込む。位置［１，０］はｂｌｋ１を含み、位置［１，１］はｂｌｋ０を含み、位置［１，４］はｂｌｋ３を含む。その他の位置は、すべて空である。ＲＡは、既にｂｌｋ０とｂｌｋ１を含むので、重複して書き込まない。ｂｌｋ３をＲＡに書き込む。ＲＡは、現時点でｂｌｋ５、ｂｌｋ２、ｂｌｋ１、ｂｌｋ０、およびｂｌｋ３を有する。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ２を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ２を含む。ｉに１を追加し（ｉ＝３）、位置［２，５］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（３＜６）。ＳＭ内の列［２］の行列位置を読み出し、ＲＡに書き込む。位置［２，０］はｂｌｋ２を含み、位置［２，２］はｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは、既にｂｌｋ２とｂｌｋ０を含むので、重複して書き込まない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ３を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ３を含む。ｉに１を追加し（ｉ＝４）、位置［３，５］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（４＜６）。ＳＭ内の列［３］の行列位置を読み出し、ＲＡに書き込む。位置［３，０］はｂｌｋ３を含み、位置［３，２］はｂｌｋ１を含み、位置［３，３］はｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは、既にｂｌｋ３、ｂｌｋ１、およびｂｌｋ０を含むので、重複して書き込まない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ４を含むか？
（ステップ４２２）ＲＡは、ｂｌｋ４を含まない。ｂｌｋ４を、ＳＭの位置［３，５］およびＲＡに書き込む。ＲＡは、現時点でｂｌｋ５、ｂｌｋ２、ｂｌｋ１、ｂｌｋ０、ｂｌｋ３、およびｂｌｋ４を有する。
（ステップ４２４）ｉに１を追加し（ｉ＝５）、位置［４，５］の値を導く。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１８）ｉはｘ未満である（５＜６）。ＳＭ内の列［４］の行列位置を読み出し、ＲＡに書き込む。位置［４，０］はｂｌｋ４を含み、位置［４，４］はｂｌｋ０を含む。その他の位置は、すべて空である。ＲＡは、既にｂｌｋ４とｂｌｋ０を含むので、重複して書き込まない。
（ステップ４２０）ＲＡは、データブロックｉすなわちｂｌｋ５を含むか？
（ステップ４２４）ＲＡは、ｂｌｋ５を含む。したがって、位置［３，４］には何も書き込まれない。
（ステップ４２４）ｉに１を加える（ｉ＝６）。ステップ４１４に戻る。
（ステップ４１４）ｉとｘを比較する。
（ステップ４１６）ｉはｘに等しい（６＝６）。ｊを１だけ増分させる（ｊ＝５）。ステップ４０６に戻る。
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
（ステップ４０６）参照配列（ＲＡ）を消去する。
（ステップ４０８）ｊとｘを比較する。
（ステップ４１０）ｊはｘに等しい（６＜６）。
この代表的な実施形態では、上述のスケジューリング行列に基づいて、データファイルの６つのデータブロックが、以下の順番で送信される。




【国際調査報告】
2004514336.tif 000078
2004514336.tif 000079