(57)【特許請求の範囲】
【請求項１】
対話型テレビジョン放送システムにおけるセクションの受信に関する情報を記録する方法であって、
セクションのヘッダからセクション番号を取り出すステップと、
セクションの受信に関する情報を記録するための第１のセクションマップにアクセスするステップであって、該第１のセクションマップは第１のビット数を有し、かつ、第１の部分および第２の部分を含む、ステップと、
前記セクション番号が前記第１のビット数より小さいか否かを判定するステップと、
前記セクション番号が前記第１のビット数より小さくない場合には、前記第１の部分を使用して第２のセクションマップをポイントするステップと、
前記セクション番号が前記第１のビット数より小さい場合には、前記第１のセクションマップに前記セクションの受信に関する情報を記録するステップと
を含むことを特徴とする方法。
【請求項２】
前記セクション番号が前記第１のビット数より小さい場合には、前記セクション番号が前記第２の部分の第２のビット数より小さいか否かを判定するステップと、
前記セクション番号が前記第２の部分の第２のビット数より小さい場合には、前記第２の部分にセクションの受信に関する情報を記録するステップと、
前記セクション番号が前記第２の部分の第２のビット数より小さくない場合には、前記第１の部分にセクションの受信に関する情報を記録するステップと
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記第１のセクションマップは、標識ビットをさらに含み、該標識ビットは、前記第１の部分が第２のセクションマップをポイントするために使用されるか、または前記第１の部分がセクションの受信に関する情報を記録するために使用されるか、を示すことを特徴とする請求項２に記載の方法。
【請求項４】
前記セクション番号が前記第１のビット数より小さくない場合には、所定の数だけ前記セクション番号を減じるステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記減じられたセクション番号が前記第１のビット数より小さいか否かを判定するステップをさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
対話型テレビジョン放送システムにおけるセクションの受信に関する情報を記録するシステムであって、
セクションのヘッダからセクション番号を取り出す手段と、
セクションの受信に関する情報を記録する第１のセクションマップにアクセスする手段であって、該第１のセクションマップは第１のビット数を有し、かつ、第１の部分および第２の部分を含む、手段と、
前記セクション番号が前記第１のビット数より小さいか否かを判定する手段と、
前記セクション番号が前記第１のビット数より小さくない場合には、前記第１の部分を使用して第２のセクションマップをポイントする手段と、
前記セクション番号が前記第１のビット数より小さい場合には、前記第１のセクションマップに前記セクションの受信に関する情報を記録する手段と
を含むことを特徴とするシステム。
【請求項７】
前記セクション番号が前記第１のビット数より小さい場合には、前記セクション番号が前記第２の部分の第２のビット数より小さいか否かを判定する手段と、
前記セクション番号が前記第２の部分の第２のビット数より小さい場合には、前記第２の部分にセクションの受信に関する情報を記録する手段と、
前記セクション番号が前記第２の部分の第２のビット数より小さくない場合には、前記第１の部分にセクションの受信に関する情報を記録する手段と
をさらに含むことを特徴とする請求項６に記載のシステム。
【請求項８】
前記第１のセクションマップは、標識ビットをさらに含み、該標識ビットは、前記第１の部分が第２のセクションマップをポイントするために使用されるか、または前記第１の部分がセクションの受信に関する情報を記録するために使用されるか、を示すことを特徴とする請求項７に記載のシステム。
【請求項９】
前記セクション番号が前記第１のビット数より小さくない場合には、所定の数だけ前記セクション番号を減じる手段をさらに含むことを特徴とする請求項６に記載のシステム。
【請求項１０】
前記減じられたセクション番号が前記第１のビット数より小さいか否かを判定する手段をさらに含むことを特徴とする請求項９に記載のシステム。
【発明の詳細な説明】
【０００１】
（発明の分野）
本発明は、情報の電子的な受信に関する。本発明は、特に、セットトップボックスによって受信される情報のソフトウェアフィルタリングに関する。
【０００２】
（発明の背景）
対話型テレビジョンシステムなどのデータ受信システムでは、番組配列情報（ＳＩ：Service Information）などの情報をセクションと呼ばれることがあるさまざまなデータブロックのヘッドエンドからさまざまなトランスポート媒体を介して送信することができる。例えば、データセクションはテレビジョンセットに接続されたセットトップボックスにケーブルまたは衛星を介して送信できる。そのようなデータセクションの例は現在または将来のイベント、セットトップボックスのユーザがアクセスできるサービス、現在の日時を含む。イベントの一例はテレビジョンプログラムまたはコマーシャルを含み、サービスの一例は視聴者が加入している１組のチャネルである。
【０００３】
特定のセットトップボックスはその特定のセットトップボックスが必要とするセクション、新たなセクション、または変更されたセクションを獲得すればよい。例えば、視聴者が１組の基本チャネルにしか加入していない場合、基本チャネルの組に含まれない特別のスポーツチャネルまたは映画チャネルに固有のセクションはセットトップボックスによって要求されない。したがって、特定のセットトップボックスの判定基準に合致しないすべてのセクションは無視できる。少数の選択したセクションを受け付けてその他のすべてのセクションをリジェクトすることはハードウェアおよびソフトウェアのフィルタリングされた機構の組み合わせによって達成できる。
【０００４】
ハードウェアフィルタリング機構（メカニズム）は通常１回フィルタリングを行い、ソフトウェアフィルタリング機構によって受け入れられたセクションは素通りする。ソフトウェアフィルタリング機構は、通常、一般にセクションの先頭の８〜１２バイトであるセクションのヘッダを分析する。新たなセクションの先頭が検出されると、トランスポートストリームから通常セクションヘッダが獲得される。このセクションヘッダは次いでソフトウェアフィルタ処理に渡され、ソフトウェアフィルタ処理は通常、セクションの残りを獲得するかリジェクトするかを判定する。セクションが必要であると判定されると、セクションの残りが獲得されて渡されてさらに処理される。したがって、ソフトウェアフィルタ処理を通過したセクションのみが通常転送されてさらに処理される。
【０００５】
セクションは、セクションヘッダ内のいくつかの個々のフィールドによって一意的に識別できる。例えば、セクションのタイプによって、最大４つの個々のフィールドを用いてセクションを識別できる。特定のセクションが必要な場合、ソフトウェアフィルタ処理はセクションヘッダの個々のデータフィールドの期待値を記憶できる。セクションヘッダがソフトウェアフィルタに渡されると、これらの期待値をセクションヘッダから取り出した実際の値と比較することができる。一致しない場合、期待値の次の組を比較して一致するか比較する期待値がなくなるまで比較できる。ソフトウェアフィルタは実質的に多数の期待値を検索することができるので、極めて効率的な比較アルゴリズムを有することが望ましい。極めて効率的な比較アルゴリズムが特に望ましいのは、ソフトウェアフィルタが現在のセクションの評価を終える前に新たなセクションが到着すると障害が発生することがあるからである。この状況によってオーバフローが発生し、または新たなセクションの損失が起こることがある。さらに、セットトップボックスは１度にさまざまな異なるセクションを検索できるので、効率を高める必要がある。
【０００６】
効率のニーズに加えて、別の共通要因はメモリのニーズである。多数の期待値（expected value）を記憶するためのメモリの利用は通常、セットトップボックスに共通に利用可能な極めて限られたメモリ容量のうちかなり大きなパーセンテージを占める。
【０００７】
メモリ空間効率が高いデータ構造体を用いる時間効率が高いマッチングアルゴリズムを有することが望ましい。本発明はそのようなニーズを対象とする。
【０００８】
（発明の概要）
本発明の一実施形態によると、高速マッチングアルゴリズムはメモリ空間効率が高いデータ構造体を用いてテレビジョンセットと併用されるセットトップボックスなどの情報受信システム内で情報フィルタリングを達成する。データ構造体（data structure）は、本発明の一実施形態によれば、特定のレベルの一致識別（a matching identification of a particular level）がない時に使用する別のノードへの対応するインデックスを備えたデータフィールドの複数のレベルの期待値（expected value）を備えたノードを含むことができる。さらに、本発明の一実施形態によれば、このデータ構造体内のノードはノード内で有効なレベルを識別するレベルフィールドを含むことができる。
【０００９】
さらに、本発明の一実施形態によれば、各々が３２ビットなどの所定の数のビットを含む一連のセクションマップを利用するセクションマップを使用することができる。各セクションマップは最初の１５ビット内に記憶された内容を示す単一のビットを含むことができる。例えば、セクションマップの最後の１６ビットは最初の１６セクションを受信したか否かを示すことができる。別のビットを用いて最初の１５ビット内に記憶された内容を示すこともできる。例えば、最初の１５ビットは次の１５セクションを受信したか否か、または次のセクションマップをポイントするインデックスを示すことができる。
【００１０】
本発明の一実施形態による対話型テレビジョン環境で情報をフィルタリングする方法を提示する。この方法はデータ構造体を提供するステップであって、データ構造体が複数のレベルを含むステップと、情報を第１の判定基準と比較するステップであって、第１の判定基準が複数のレベルの第１のレベルに関係するステップとを含む。またこの方法は情報を第２の判定基準と比較し、第２の判定基準は複数のレベルの第２のレベルに関係し、この比較は情報が第１の判定基準に一致した時に実行される。
【００１１】
本発明の一実施形態による対話型テレビジョン環境で情報をフィルタリングするシステムもまた提示する。本システムはデータ構造体を提供するように構成されたメモリを含み、データ構造体は複数のレベルを含む。また、本システムはメモリに接続されたプロセッサを含み、このプロセッサは情報を第１の判定基準と比較するように構成され、第１の判定基準は複数のレベルの第１のレベルに関係する。またプロセッサは情報を第２の判定基準と比較するように構成され、第２の判定基準は複数のレベルの第２のレベルに関係し、この比較は情報が第１の判定基準に一致した時に実行される。
【００１２】
本発明の一実施形態による情報の受信を記録する方法も提示する。この方法はセクション番号を提供するステップと第１のセクションマップを提供するステップとを含み、第１のセクションマップはいくつかのビットに関連する。この方法はまたセクション番号がビット数より小さいか否かを判定し、セクション番号がそのビット数より小さくない場合に第２のセクションマップをポイントする。
【００１３】
本発明の一実施形態による情報の受信を記録するシステムを提示する。本システムはいくつかのビットに関連する第１のセクションマップを提供するように構成されたメモリと、メモリに結合されたプロセッサを含む。このプロセッサは、セクション番号を提供し、そのセクション番号がビット数より小さいか否かを判定し、セクション番号がそのビット数より小さくない場合に第２のセクションマップをポイントするように構成されている。
【００１４】
（好ましい実施形態の詳細な説明）
以下の説明は当業者が本発明を製作して使用することができるように提示されており、特許出願とその要件に関して提供されている。当業者は好ましい実施形態を変更することができることが明らかであろうし、本明細書中の一般原理は他の実施形態にも適用可能である。したがって、本発明は図示の実施形態に限定されるものではなく、本明細書に記載の原理および特徴に一致する最も広い範囲を与えられるものである。
【００１５】
図１は、本発明の一実施形態を実施するのに適した情報受信システムのブロック図である。図１のシステムは、特定のビデオとそれに関連するオーディオをヘッドエンド１０２に供給するビデオおよびオーディオ装置１００に接続できるヘッドエンド１０２を含んだ状態で示されている。ビデオ情報はヘッドエンド１０２でデジタル化し、送信機１０４を介して受信システムに送信できる。ヘッドエンド１０２によって送信される情報はさまざまな方法で受信システムに送信できる。例えば、送信される情報は衛星１０６を介して受信システムに送信できる。あるいは、ケーブルを用いてヘッドエンド１０２から受信システムに情報を送信することができる。受信システムの一例はセットトップボックス１１０に接続されたテレビジョン１１２を含む。セットトップボックス１１０は衛星１０６から情報を受信する受信アンテナ１０８に接続できる。
【００１６】
情報が受信アンテナ１０８を介して受信されると、情報はセットトップボックス１１０によって処理され、テレビジョンセット１１２に表示される。このように、オーディオ、ビデオ、および対話データをセットトップボックス１１０で受信して処理することができる。
【００１７】
図２は本発明の一実施形態を実施するのに適した図１のセットトップボックス１１０のようなセットトップボックスを示すブロック図である。図２に示すセットトップボックス１１０は受信アンテナ１０８とテレビジョン１１２とに接続された状態で示されている。受信アンテナ１０８によって受信される信号はフロントエンド２００に送信され、フロントエンド２００は受信アンテナ１０８から受信した被変調信号を復調デジタル信号に変換する。次いで信号はフロントエンド２００からマイクロコントローラ２０２に送信される。マイクロコントローラはプライベートエレメンタリストリーム（ＰＥＳ）および番組配列情報（ＳＩ）フィルタ２０４などのハードウェアフィルタを含むことができる。図２には単一のＰＥＳフィルタ２０４が示されているが、実際には１組の複数のＰＥＳフィルタを使用できる。ＰＥＳフィルタ２０４は受信信号のパケットストリームからパケットを選択することができる。パケットがＰＥＳフィルタ２０４によって選択されると、送信されたパケットをマイクロコントローラ２０２内のソフトウェアフィルタによって処理することができる。次いでソフトウェアフィルタはＰＥＳフィルタ２０４から受信した１組のパケットからさらにパケットを選択する。次いでデジタルビデオ信号およびデジタルオーディオ信号がデジタル／アナログ変換装置２１０に送信され、ビデオとオーディオに関してデジタル−アナログ変換が実行される。
【００１８】
マイクロコントローラ２０２はＦＬＡＳＨメモリ２０６とシステムランダムアクセスメモリ（ＲＡＭ）２０８に接続された状態で示されている。マイクロコントローラ２０２によって実行されるプログラムはＦＬＡＳＨメモリ２０６内に配置できるが、データベースなどのその他の情報はシステムＲＡＭ２０８内に配置することができる。
【００１９】
デジタル／アナログ変換装置２１０は、圧縮された信号を圧縮解除する際に使用される圧縮解除用メモリ２１４に接続されている。デジタル／アナログ変換装置２１０は、オーディオおよびビデオ信号を再変調して適切なフォーマットでテレビジョン１１２に表示できるようにするリモジュレータ（再変調器）２１２に接続されている。
【００２０】
セットトップボックス１１０によって受信されたデータはさまざまなテーブルにフォーマット化することができる。一連のパケットが受信されると、パケットはネットワーク情報テーブル（ＮＩＴ：Network Information Table）、ブーケアソシエーションテーブル（ＢＡＴ：Bouquet Association Table）、サービス記述子テーブル（ＳＤＴ：Service Descriptor Table）、およびイベント情報テーブル（ＥＩＴ：Event Information Table）などのテーブルにフォーマット化できる。これらのテーブルはデジタルビデオブロードキャスティング（ＤＶＢ）標準に記載されている。ＤＶＢ標準の詳細については、インターネットサイト http://www.atsc.orgを参照されたい。
【００２１】
データストリームが受信されると、図２のＰＥＳフィルタ２０４などのＰＥＳフィルタがパケットストリームの初期フィルタ機能を実行する。その後、ＰＥＳフィルタによって選択されたパケットはソフトウェアフィルタを介して処理される。マイクロコントローラはシステムに超高速で着信するパケットを処理する１６〜３２のハードウェアＰＥＳフィルタなどの多数のＰＥＳフィルタを含む。着信パケットストリームは１８〜５０メガビット／秒で送信される。
【００２２】
受信システムはＮＩＴ、ＢＡＴ、ＳＤＴ、およびＥＩＴを含むすべてのタイプのテーブルを受信できる。テレビジョンネットワークは多数のサービスを有することができる。ＮＩＴはこれらのサービスがどこにあるかを識別する。ＢＡＴはこれらのサービスを映画やスポーツなどのカテゴリにグループ化できる。ＳＤＴはこれらのサービスに関する詳細情報を示す。ＥＩＴは一般にタイトルと言語などのサービスに関する追加情報を示す。
【００２３】
ソフトウェアフィルタ処理の間、さまざまなタイプのテーブルは異なるレベルのフィルタリング判断基準（filtering criteria）を有することができる。例えば、ＮＩＴテーブルはテーブルＩＤを識別するレベル１のフィルタリング判断基準と、ネットワークＩＤのレベル２のフィルタリング判断基準とを有することができる。テーブルＩＤはフォーマットされた時にセクションがその一部であるＮＩＴ、ＢＡＴなどのテーブルを識別する。ネットワークＩＤはネットワークを識別する。この例では、ＢＡＴテーブルはテーブルＩＤのレベル１判断基準とブーケＩＤのレベル２判断基準とを有することができる。ブーケは加入者が加入できるスポーツ番組と映画番組の組み合わせなどの所定のサービスの組み合わせである。ブーケＩＤは特定のタイプのブーケを識別する。またこの例では、ＳＤＴはテーブルＩＤのレベル１判断基準（level one criteria）、トランスポートストリームＩＤのレベル２判断基準、およびオリジナルネットワークＩＤのレベル３判断基準を有することができる。トランスポートストリームＩＤは衛星が信号を送信する際にどの周波数を使用するかを識別する。オリジナルネットワークＩＤは元々特定のサービスを同報通信（broadcast）するネットワークを識別する。ＥＩＴはテーブルＩＤのレベル１判断基準、サービスＩＤのレベル２判断基準、トランスポートストリームＩＤのレベル３判断基準、およびオリジナルネットワークＩＤのレベル４判断基準を有することができる。サービスＩＤは特定のトランスポートストリームＩＤ内のサービスを識別する。
【００２４】
セクションはいくつかのパケットを含むトランスポートユニットである。セクション内に含まれるパケットの総数はテーブルによって変わることがある。例えば、ＮＩＴの最大のセクションは約１０２４バイトである。ＮＩＴなどのテーブルは、２５６個のセクションなどの複数のセクションに分割できる。セクションはヘッダを含むことができる。セクションヘッダ内に含まれるバイト数の例は最初の８〜１２バイトである。新たなセクションの先頭が検出されると、トランスポート画面（transport sireen）からセクションヘッダを獲得してソフトウェアフィルタ処理に渡してセクションの残りを獲得すべきか否かが判定される。ＮＩＴ、ＢＡＴおよびＳＤＴセクションは最大１０２４バイト長を有することができる。ただし、ＥＩＴセクションは最大４０９６バイトを有することができる。
【００２５】
データパケットはハードウェアＰＥＳフィルタから渡されるので、ソフトウェアフィルタはパケットストリームをさらにフィルタリングすることができる。従来のフィルタリング処理の一例を図３に示す。図３はノード３００Ａ〜３００Ｐとリーフ３０２Ａ〜３０２Ｆとを含む２進のツリーを示す。図３に示すソフトウェアフィルタリング内で２進のツリーを使用する例において、ハードウェアＰＥＳフィルタによってソフトウェアフィルタまで渡されたパケットストリームのセクションがルートノード３００Ａに照らして検査され、このセクションが受け付けるべきセクションであるか否かが判定される。
【００２６】
分析されたセクションがレベル１のノード３００Ａ内に記録された判断基準に合致しない場合、分析されたセクションはレベル１のノード３００Ｂ内に記憶された判定基準と比較される。分析されたセクションがレベル１のノード３００Ａ〜３００Ｄ内に記憶された判断基準のいずれにも合致しない場合、セクションはリジェクトされる。ただし、分析されたセクションがレベル１のノード３００Ａ〜３００Ｄに関連する判定基準の１つに合致する場合、分析されたセクションは分析されたセクションに合致するレベル１の判断基準に関連するレベル２の判定基準の組と比較される。例えば、分析されたセクションがレベル１のノード３００Ａに関連する判定基準に合致しなかったが、レベル１のノード３００Ｂに関連する判定基準に合致した場合、分析されたセクションは合致するレベル１のノード３００Ｂに関連するレベル２のノードの組３００Ｆ〜３００Ｈと比較される。
【００２７】
分析されたセクションが合致するレベル１のノード３００Ｂに関連するレベル２のノード３００Ｆ〜３００Ｈのいずれにも合致しない場合、分析されたセクションはリジェクトされる。ただし、分析されたセクションがノード３００Ｈなどのレベル２のノードに関連する判定基準に合致する場合、分析されたセクションはレベル３のノードの組３００Ｋ〜３００Ｎと比較される。
【００２８】
上記の例のＮＩＴとＢＡＴなどの特定のテーブルに関連する２つのレベルの判定基準しかない場合、分析されたセクションはノード３００Ｈのレベル２の判定基準に合致した後に受け入れられる。
【００２９】
この処理は分析されたセクションが特定のレベルのノードに関連する判定基準のいずれにも合致しないことでリジェクトされるか、分析されたセクションがすべてのレベルの記述されたすべての判定基準に合致した後で受け入れられるまで継続する。リーフ３０２Ａ〜３０２Ｆは、分析されたセクションがリーフ３０２Ａ〜３０２Ｆに到達した場合に受け入れられる２進のツリーの特定のブランチの最終エレメントである。例えば、分析されたセクションはブランチ３００Ａ〜３００Ｂ、３００Ｆ〜３００Ｈ、３００Ｋ〜３００Ｍ〜３００Ｌを介して最終リーフ３０２Ｅまで進行することができる。
【００３０】
所定の数のノードとリーフはメモリ内に事前に割り付けられており、ソフトウェアフィルタリング処理をサポートする。ノードとリーフのために事前に割り付けられたメモリの一例は、所与の数のノード（９３０ノードなど）と所与の数のリーフ（２５０リーフなど）について約２７キロバイトである。この事前に割り付けられた量のメモリは通常、対話型テレビジョンシステムのセットトップボックスのメモリのかなりの部分を占めるが、これはセットトップボックスが通常約１／２メガバイト〜１メガバイト程度の少量のメモリしか有しないためである。
【００３１】
データの組がソフトウェアフィルタによって受け入れられると、特定のシステム情報テーブルに関連するどのセクションが正しく受信されたかを判定することが望ましい。図４は、所与のシステム情報テーブルに関連する特定のセクションが受信されたか否かを追跡する従来の方法を示す。通常３２ビットのアレイが特定のシステム情報テーブルのセクションが受信されたか否かを追跡するために予約される。この３２ビットのアレイは一般にセクションマップと呼ばれる。システム情報テーブルは多数のセクション、例えば２５６のセクションを含むことができる。セクションマップの３２バイト内の各ビットは特定のセクション番号が受信されたか否かを示すことができる。図４に示す例では、バイト１はセクション番号０〜７が受信されたか否かを示すビット１〜８を含み、第２バイトもセクション番号８〜１５が受信されたか否かを含む８ビットを含み、セクション２４８〜２５５が受信されたか否かを示すバイト３２まで以下同様になる。
【００３２】
テーブルは２５６のセクションを含むことができる。したがって、２５６のセクションの受信を示すことができるのに十分なメモリ空間が通常予約されている。ただし、２つまたは３つのセクションだけが通常システム情報テーブル内に含まれ、セクションマップ用に予約されたメモリ空間の大半は通常未使用のままである。
【００３３】
この処理はソフトウェアフィルタリング機構として有効ではあっても、ソフトウェアフィルタ処理の速度を下げることなくソフトウェアフィルタリング処理のメモリ要件を緩和することが望ましい。したがって、より少ないメモリを必要とするビットマップシステムを有することがまた望ましい。本発明はそのようなニーズを対象とする。
【００３４】
図５は、本発明の一実施形態によるデータ構造体（data structure）である。図５に示すデータ構造体４００は、行４０６〜４１２と列４０２〜４０４に示される多数のフィールドを含む。この例では、ソフトウェアフィルタが受信したテーブルデータへの合致を検索する最大４つのレベルの判定基準があるものとする。列４０２では、要求された判定基準が各レベル４０６〜４１２に関連するフィールド内に列挙されている。列４０４では、関連する要求された判定基準４０２への合致が検出された場合に使用される次のサブテーブルノードへのインデックス。要求された判定基準列４０２およびインデックス列４０４内の各フィールドについて、２バイトなどの所定の数のバイトを予約できる。
【００３５】
レベルフィールド４１４を含むサブテーブルノード４００も示されている。レベルフィールド４１４に予約できるメモリ空間の例は１バイトである。レベルフィールドは、どのレベルが有効なレベルであるかを示すレベルを示す値、この例では１〜４を含むことができる。例えば、レベルフィールド４１４がレベル１を示した場合、レベル１（行４０６）のみを所与のセクションに合致するか検査することが必要である。別の例では、レベルフィールドが３を示す場合、レベル１（行４０６）、２（行４０８）および３（行４１０）が有効でレベル４（行４１２）は受信セクションとの合致を検査する必要がない。
【００３６】
追加情報のために領域４１６を予約することができる。例えば、領域４１６はシステム情報テーブルのバージョン番号、サブテーブルノード４００が依然として有効であるか否かを示すフラグ、いくつのセクションが処理待ち状態であるかを示すカウンタ、クライアントインデックス、サブテーブルフィルタインデックス、タグ、およびセクションマップなどの情報を記憶する７つのフィールドなどのいくつかのフィールドである。セクションマップの詳細は図９Ａ〜図１１と関連して後述する。クライアントインデックスはこのサブテーブルノード４００に関連するルートサブテーブルノード（分析対象の第１のサブテーブルノード）をポイントするデータベース構造体であってもよい。サブテーブルフィルタインデックスはこのサブテーブルノードの２進ツリーに関係しないソフトウェアフィルタ内の他の構造体へのインデックスであってもよい。タグはクライアントによって決定されるさまざまな目的に使用するクライアントから発信されるタグであってもよい。
【００３７】
図６は、本発明の一実施形態による１組のサブテーブルノード４００Ａ〜４００Ｄの一例を示す。セクションが本発明の一実施形態によるソフトウェアフィルタによってハードウェアＰＥＳフィルタから受信される。このセクションは最初にルートサブテーブルノード４００Ａを介して分析される。ルートサブテーブルノード４００Ａは受信セクションと比較すべき最初のサブテーブルノードである。分析されたセクションに合致するレベル１  ４０６に判定基準４０２を備えた２つの適切なサブテーブルノードがある場合、レベルフィールド４１４内の最大の番号を備えたサブテーブルノードがレベルフィールド４１４内のより小さい番号を備えたサブテーブルノードより先に評価される。したがって、セクションに合致するレベル１の判定基準を備えたサブテーブルノードが最大レベルフィールド４１４によって最小レベルフィールド４１４まで順次評価される。
【００３８】
本発明の一実施形態では、サブテーブルノード４００のあるフィールドが有効な場合、同じサブテーブルノード４００内のそれより以前のフィールドも有効であるとみなされる。以前のフィールドはより低いレベル４０６〜４１２にある列４０２内のフィールドと次いで有効なフィールドである。例えば、レベルフィールド４１４がレベル３（行４１０）を識別する場合、レベル１（行４０６）および２（行４０８）も有効であるものとする。
【００３９】
図６に示す例では、ルートノード４００Ａの列４０２Ａの第１のレベル４０６Ａでセクションが評価（evaluate)される。セクションとルートノード４００Ａの第１のレベル４０６Ａに関連する判定基準とが合致した場合、ルートノード４００Ａの列４０２Ａの第２のレベル４０８Ａが合致するか検査（check）され、列４０２Ａの第２のレベル４０８Ａで合致が検出された場合、列４０２Ａの第３のレベル４１０Ａが検査され、列４０２Ａのすべてのレベル４０６Ａ〜４１２Ａがルートノード４００Ａ内で合致するか検査される。ルートノード４００Ａ内のレベル４０６Ａ〜４１２Ａで合致が検出されない場合、ルートノード４００Ａの列４０４Ａ内の同じレベルにあるそれに関連するインデックスが参照されて次にどのサブテーブルを検査するかが決定される。例えば、ルートノード４００Ａの列４０２Ａのレベル１  ４０６Ａで合致した場合、ルートノード４００Ａのレベル２  ４０８Ａを検査せずに、行４０６Ａ、列４０４Ａのフィールドにあるインデックスが検査されて参照する次のサブテーブルが決定される。この例では、サブテーブルノード４００Ｂはルートノード４００Ａのレベル１の合致判定基準に関連するインデックス内に示されたテーブルである。テーブル４００Ｂでは、ルートノード４００Ａ内で合致を検出できなかった同じレベルで合致するか検査される。上記の例では、ルートノード４００Ａのレベル１では合致が検出されなかったので、次いで次のサブテーブルノード４００Ｂのレベル１  ４０６Ｂが検査される。ルートノード４００Ａの第１のレベル４０６Ａがこのセクションに合致する場合、セクションはルートノード４００Ａの列４０２Ａの第２のレベル４０８Ａに合致するか検査される。
【００４０】
次のテーブル４００Ｂにおいて、検査対象の第１のレベル（以前のサブテーブルノード内のセクションに合致しなかったレベルに対応するレベル）も合致しない場合、合致しなかったレベルに対応するインデックス４０４Ｂが検査されて次の分析対象のサブテーブルノードが決定される。この例では、合致しなかったルートノード４００Ａ内の対応するレベルもレベル１  ４０６Ａ内にあるので、サブテーブルノード４００Ｂ内の最初の分析対象のレベルは列４０２Ｂのレベル１  ４０６Ｂである。
【００４１】
サブテーブルノード４００Ｂの列４０２Ｂのレベル１  ４０６Ｂ内で合致が検出された場合、サブテーブルノード４００Ｂの次のレベル４０８Ｂが合致するか検査される。ただし、サブテーブルノード４００Ｂの列４０２Ｂの第１のレベル４０６Ｂ内で合致が検出されなかった場合、行４０６Ｂ、列４０４Ｂのフィールド内に位置するそれに関連するインデックスが参照されて検査対象の次のサブテーブルノード４００Ｄが決定される。サブテーブル４００Ｂの列４０２Ｂのレベル１  ４０６Ｂ内で合致が検出された場合、サブテーブルノード４００Ｂの次のレベルであるレベル２  ４０８Ｂが合致するか検査される。そのレベルで合致しなかった場合、行４０８Ｂ、列４０４Ｂのフィールド内に位置するそれに関連するインデックスが参照されて検査対象の次のサブテーブルノード４００Ｃが決定される。
【００４２】
サブテーブルノード４００Ｂのレベル２  ４０８Ｂで合致が検出されなかったとした場合、列４０４Ｂ内のそれに関連するインデックスは次の比較をサブテーブルノード４００Ｃのレベル２  ４０８Ｃに向ける。
【００４３】
図７および図８は、パケットストリームからセクションをフィルタリングする本発明の一実施形態による方法を示す流れ図である。レベルは１にセットされ、サブテーブルノード（ＳＮ）はルートに等しくセットされている（ステップ５００）。レベル（レベルＤ）に対応するセクション内のフィールドが分析対象のセクションから取り出される（ステップ５０２）。このレベルのＩＤの例はテーブルＩＤ、ネットワークＩＤ、ブーケＩＤ、オリジナルネットワークＩＤ、トランスポートストリームＩＤおよびサービスＩＤなどの判定基準を含む。このレベルのＩＤはセクションヘッダ内にある。
【００４４】
図１２Ａ〜図１２Ｄは、さまざまなセクションヘッダの例を示す。図１２Ａはフィールド９０２ａ〜９０２ｄを含むＮＩＴヘッダ９００ａの一例を示す。この例では、フィールド９０２ａはテーブルＩＤ、フィールド９０２ｂはネットワークＩＤ、フィールド９０２ｃはバージョン番号、フィールド９０２ｄは現在のセクション番号と最後のセクション番号を含む。図１２Ｂはフィールド９０２ａ′〜９０２ｄ′を備えたＢＡＴヘッダ９００ｂの一例を示す。この例では、フィールド９０２ａ′はテーブルＩＤ、フィールド９０２ｂ′はブーケＩＤ、フィールド９０２ｃ′はバージョン番号、フィールド９０２ｄ′は現在のセクション番号と最後のセクション番号を含む。図１２Ｃはフィールド９０２ａ″〜９０２ｅを備えたＳＴＤヘッダ９００ｃの一例を示す。この例では、フィールド９０２ａはテーブルＩＤ、フィールド９０２ｂはトランスポートストリームＩＤ、フィールド９０２ｃ″はバージョン番号、フィールド９０２ｄ″は現在のセクション番号と最後のセクション番号を含み、フィールド９０２ｅはオリジナルネットワークＩＤである。図１２Ｄはフィールド９０２ａ′′′〜９０２ｆを備えたＥＩＴヘッダ９００ｄの一例を示す。この例では、フィールド９０２ａ′′′はテーブルＩＤ、フィールド９０２ｂ′′′はサービスＩＤ、フィールド９０２ｃ′′′はバージョン番号、フィールド９０２ｄ′′′は現在のセクション番号と最後のセクション番号を含み、フィールド９０２ｅ′はトランスポートストリームＩＤ、フィールド９０２ｆはオリジナルネットワークＩＤである。
【００４５】
図１２Ａ〜図１２Ｄに示す例では、フィールド９０２ａ〜９０２ａ′′′はレベル１のＩＤでよく、フィールド９０２ｂ〜９０２ｂ′′′はレベル２のＩＤでよく、フィールド９０２ｅ〜９０２ｅ′はレベル３のＩＤでよく、フィールド９０２ｆはレベル４のＩＤでよい。例えば、これらのフィールドは図７のステップ５０２で取り出せるレベルＩＤを含む。有効なレベルフィールドの数はセクションタイプ（ＮＩＴ、ＢＡＴ、ＳＤＴなど）に応じて変化することに留意されたい。フィールド９０２ａ、９０２ａ′、９０２ａ″、および９０２ａ′′′はテーブルＩＤを含むことが示されている。これらのフィールド９０２ａ〜９０２ａ′′′の内容は残りのレベルＩＤ９０２ｂ、９０２ｂ′、９０２ｂ″、９０２ｅ、９０２ｂ′′′、９０２ｅ′、および９０２ｇの内容を決定することができる。
【００４６】
レベルＩＤに加えて、ヘッダ９００もバージョン番号、現在のセクション番号および最後のセクション番号などの他のさまざまな情報を含むことができる。セクションヘッダ内に含むことができるフィールドの詳細は、デジタルビデオブロードキャスティング（ＤＶＢ）標準ＥＮ３００４６８に記載されている。
【００４７】
次いでセクションから取り出されたレベルＩＤ（セクションのフィールドの取り出された値）が同じレベルのサブテーブルノードの判定基準に合致するか否かが判定される（図７のステップ５０４）。例えば、レベルが１にセットされ、サブテーブルノードが図６のルートノード４００Ａなどのルートノードにセットされ、図６のルートノード４００Ａの列４０２Ａのレベル１  ４０６Ａ内のフィールドに関連する判定基準が特定のテーブルＩＤである場合、分析対象のセクションのセクションヘッダ内にあるレベル１の識別はルートノード４００Ａのレベル１内で識別されるテーブルＩＤと比較されて合致するか否かが検査される。
【００４８】
セクションから取り出されたレベルＩＤが現在のレベルのサブテーブルノード内で識別される判定基準と同じでない場合、次のサブテーブルノードが決定される（ステップ５０６）。次のサブテーブルノードは、図６に示すように、サブテーブルノードの現在のレベル行の列４０４内のインデックスによって決定することができる。
【００４９】
次いで、このサブテーブルノードが有効か否かが決定される（ステップ５０８）。サブテーブルノードが有効か否かを示すフラグは、図５に示すように、ノード４００の領域４１６内に記憶できる。サブテーブルノードが有効でない場合、現在のセクションはリジェクトされる（ステップ５１０）。ただし、現在のサブテーブルノードが有効な場合、セクションのレベルＩＤが同じレベルの現在のサブテーブルノード内の判定基準と同じか否かが再び判定される（ステップ５０４）。
【００５０】
セクションのレベルＩＤが同じレベルのサブテーブルノードの判定基準と同じ場合（ステップ５０４）、レベルが図５のレベルフィールド４１４のような現在のサブテーブルノードのレベルフィールドより大きいかそれに等しいかが判定される（ステップ５１２）。レベルがサブテーブルノードのレベルフィールドより小さい場合、次のレベルが考慮される（ステップ５１４）（レベル＝レベル＋１をセット）。この次のレベル（次のレベルＩＤ）に対応するこのセクション内のフィールドが次いで取り出される（ステップ５０２）。
【００５１】
レベルが図５のレベルフィールド４１４のようなサブテーブルノードのレベルフィールドより大きいかそれに等しいかが判定されると（ステップ５１２）、現在のサブテーブルノード内のバージョンがセクション内のバージョンに等しいか否かが判定される（図８のステップ５５０）。バージョン番号は図５に示すサブテーブルノード４００の追加フィールド４１６内にあってもよい。サブテーブルノード内に格納されたこのバージョン番号は図１２のヘッダ９００のフィールド９０２ｅなどのセクションヘッダ内に記憶されたバージョン番号と比較することができる。サブテーブルノード内のバージョン番号がセクションヘッダ内のバージョン番号に等しくない場合、サブテーブルノード内のバージョンは更新され、セクションマップはクリアされ、新たなセクションマップが作成される（ステップ５５２）。新たなバージョンを備えたセクションが受信されると、新たなバージョンに関連するすべてのセクションを再び獲得してすべての変更内容を受信したことを確認しなければならない。したがって、古いバージョンの受信を追跡しているセクションマップをクリアでき、新たなセクションマップを作成して新たなバージョンのセクションの受信を追跡することができる。セクションマップの操作の詳細は図９Ａ〜１１に関連して後述する。その後、セクションマップは獲得された時に新たなバージョンのセクションに更新される（ステップ５５４）。次いでセクションは受け入れられる（ステップ５５６）。
【００５２】
サブテーブルノード内のバージョンがセクション内のバージョンに等しい場合（ステップ５５０）、このセクションを以前に受信しているか否かが判定される（ステップ５５８）。テーブルのバージョンの一部がいくつかの不明なセクションと共に受信されることがある。したがって、このセクションがそれらの不明なセクションの１つであるか否かを判定するために検査が実行される。この判定の詳細は図１０に関連して後述する。このセクションが以前に受信されていれば、このセクションはリジェクトされる（ステップ５６０）。ただし、このセクションが以前に受信されていない場合、セクションマップが更新されてこのセクションを受け入れることが示され（ステップ５５４）、セクションは受け入れられる（ステップ５５６）。
【００５３】
図９Ａおよび図９Ｂは、本発明の一実施形態によるセクションマップを示す。セクションマップは図５に示すサブテーブルノードの領域４１６内にあってもよい。セクションマップは最後の１６ビット６０２が最初の１６セクションを受信したか否かを示す３２ビットフィールドなどの多数のビットを備えたフィールドを含む。１６ビット領域６０２内の各ビットはそれに対応するセクションを受信したか否かを示すことができる。別のビット６０４を用いて第１の１５ビット６０６の機能を示すことができる。例えば、標識（インジケータ）ビット６０４が１にセットされている場合、第１のビットの組６０６は次の１５のセクションを受信したか否かについての受信状態を示すことができる。ただし、標識（インジケータ）ビット６０４が０の場合、第１のセクション６０６が次のセクションマップフィールドをポイントするインデックスであってもよいことを示すことができる。
【００５４】
図９Ｂは、ゼロにセットされた時のインデックスを示す標識（インジケータ）ビットと、標識（インジケータ）ビットが１にセットされた時の次の１５セクションのステータスの一例である。この例では、第１の３２ビットフィールド６００Ａは第２の部分６０２Ａ内の第１の１６セクションのステータスを収集している。この例では、第２の部分６０２Ａは各々がセクションを受信したか否かを示す１６ビットを含む。標識（インジケータ）ビットは第１の部分６０２Ａと第２の部分６０６Ａとの間に位置する。この例では、標識（インジケータ）ビット６０４Ａはゼロにセットされ、１ビットである。標識（インジケータ）ビット６０４Ａ内がゼロであれば、第１の部分６０６Ａは次のセクションマップ６０６Ｂをポイントするインデックスであるということを示している。次のセクションマップ６００Ｂも第１の部分６０６Ｂと、第２の部分６０２Ｂ、および第１の部分６０６Ｂと第２の部分６０２Ｂとの間にある標識（インジケータ）ビットとを備えた３２ビットフィールドであってもよい。第２の部分６０２Ｂは１６セクションの第２の組のステータスを記録する。この例では、標識（インジケータ）ビット６０４Ｂもゼロにセットされ、第２のセクションマップ６００Ｂの第１の部分６０６Ｂも第３のセクションマップ６００Ｃをポイントするインデックスであることを示す。第３のセクションマップ６００Ｃも１６セクションのステータスを示す第３のビットの組を記憶する。ただし、標識（インジケータ）ビット６０４Ｃは１にセットされている。これは、このセクションマップ６００Ｃは最後のセクションマップであり、第１の部分６０６Ｃは次のセクション、この例では次の１５セクションの組のステータスを示すことを表している。
【００５５】
図１０は、図８のステップ５５８の判定のような、本発明の一実施形態による、セクションが受信済みであるか否かを判定する方法を示す流れ図である。セクションからセクション番号が受信される（ステップ７００）。図９Ｂのセクションマップ６００Ａなどの第１のセクションマップが分析される（ステップ７０２）。次いで、セクション番号がセクションマップフィールドについて事前に割り振られたビット数より小さいか否かが判定される（ステップ７０４）。この例では、セクション番号が３１より小さいか否かが判定される（この例ではセクションは０〜２５５の順にカウントされる）。
【００５６】
セクション番号がセクションマップフィールドについて事前に割り振られたビット数より小さくない場合、セクション番号はセクションマップフィールドの第２の部分について事前に割り振られたビット数だけ減じられる（ステップ７０６）。この例では、セクション番号は１６だけ減じられる。現在のセクションマップの第１の部分を用いて次のセクションマップがポイントされる（次の３２ビットのセクションマップフィールド）（ステップ７０８）。その後で、このセクション番号がセクションマップフィールド内のビット数より小さいか否かが判定される（ステップ７０４）。
【００５７】
セクション番号がセクションマップフィールド内のビット数より小さい場合（ステップ７０４）、セクション番号が第２の部分のビット数より小さいか否かが判定される（ステップ７１６）。この例では、第２の部分のビット数は１５である。セクション番号が第２の部分のビット数より小さくない場合、現在のセクションマップが別のセクションマップをポイントしているか否かが判定される（ステップ７１８）。この判定を実行する方法の一例は、標識（インジケータ）ビットをセットして別のセクションマップをポイントさせることである。このセクションマップが別のセクションマップをポイントしている場合、セクション番号は第２の部分のビット数だけ減じられる（ステップ７０６）。ただし、このセクションマップが別のセクションマップをポイントしていない場合（ステップ７１８）、またはセクション番号が第２の部分のビット数より小さい場合（ステップ７１６）、現在のセクションに関連するビットはセクションを受信したか否かを示す（ステップ７１０）。例えば、セクションが受信済みであることを示すには、現在のセクションに関連するビットに１を入れる（ステップ７１４）。ポイントされたセクションマップ内の関連するビットがセットされていない場合（ステップ７１０）、セクションはまだ受信されていない（ステップ７１２）。
【００５８】
図１１は、図８のステップ５５２のような、本発明の一実施形態による、新たなセクションマップを作成する方法を示す流れ図である。現在のセクションから最後のセクション番号が受信される（ステップ８００）。各セクションはそれ自身のセクション番号と最後のセクション番号とを識別する。したがって、受信側システムはまだ受信していないセクションの数を把握できる。図９Ｂのセクションマップ６００Ａなどの第１のセクションマップが使用される（ステップ８０２）。次いで、最後のセクション番号がセクションマップフィールド内のビット数よりも小さいか否かが判定される（ステップ８０４）。この例では、最後のセクション番号が３１より小さいか否かが判定される。最後のセクション番号がセクションマップフィールド内のビット数よりも小さい場合（ステップ８０４）、標識（インジケータ）ビットは１にセットされてセクションマップがこれ以上ないことを示す（ステップ８０６）。この例では、標識（インジケータ）ビットはビット１５である。したがって、新たなセクションマップの作成は完了する。
【００５９】
最後のセクション番号がセクションマップフィールド内のビット数よりも小さくない場合（ステップ８０４）、最後のセクション番号がセクションマップフィールドの第２の部分のビット数だけ減じられる（ステップ８０８）。セクションマップフィールドの最後のセクションのビット数の例は、図９Ａの第２の部分６０２にある１６ビットである。
【００６０】
次いで、標識（インジケータ）ビットがゼロにセットされ、まだセクションマップがあることを示す（ステップ８１０）。次いで、新たなセクションマップがランダムアクセスメモリ（ＲＡＭ）などのシステムから取り出されて現在のセクションマップにリンクされる（ステップ８１２）。次いで、新たなセクションマップは、図９Ａの第１の部分６０６などの以前のセクションマップの第１の部分によってポイントされる（ステップ８１４）。次いで、再び、最後のセクション番号がセクションマップフィールド内のビット数よりも小さいか否かが判定され（ステップ８０４）、処理が完了するまで以下同様である。
【００６１】
以上、情報フィルタリングの方法およびシステムについて記載してきた。本発明に従って記述されるソフトウェアはメモリまたはＣＤ−ＲＯＭなどの何らかの形式のコンピュータ可読媒体内に記憶でき、またはネットワーク上で送信でき、またプロセッサによって実行できる。
【００６２】
上記の説明では、図示の実施形態に従い本発明について述べてきたが、この実施形態には変更を加えることができ、またそれらの変更が本発明の精神と範囲内に入ることを当業者は直ちに理解できるであろう。したがって、添付の特許請求の範囲の精神と範囲から逸脱することなしに、当業者は本発明をさまざまに変更することができる。
【図面の簡単な説明】
【図１】  本発明の一実施形態を実現するのに適したシステムを示すブロック図である。
【図２】  本発明の一実施形態を実現するのに適したセットトップボックスの一例を示すブロック図である。
【図３】  ソフトウェアフィルタに使用できる解析ツリーを示す図である。
【図４】  ソフトウェアフィルタと併用できるセクションマッピングを示す図である。
【図５】  本発明の一実施形態によるソフトウェアフィルタと併用するサブテーブルノード構造体を示す図である。
【図６】  本発明の一実施形態によるサブテーブルノード間の関係を示す図である。
【図７】  本発明の一実施形態による情報セクションをフィルタリングする方法を示す流れ図である。
【図８】  本発明の一実施形態による情報セクションをフィルタリングする方法を示す流れ図である。
【図９Ａ】  本発明の一実施形態によるセクションマップを示す図である。
【図９Ｂ】  本発明の一実施形態によるセクションマップを示す図である。
【図１０】  本発明の一実施形態によるセクションが既に受信されているか否かを判定する流れ図である。
【図１１】  本発明の一実施形態による新たなセクションマップを作成する流れ図である。
【図１２Ａ】  本発明の一実施形態と併用するのに適したセクションヘッダを示す図である。
【図１２Ｂ】  本発明の一実施形態と併用するのに適したセクションヘッダを示す図である。
【図１２Ｃ】  本発明の一実施形態と併用するのに適したセクションヘッダを示す図である。
【図１２Ｄ】  本発明の一実施形態と併用するのに適したセクションヘッダを示す図である。
【図１】
0004445674.tif 000002
【図２】
0004445674.tif 000003
【図３】
0004445674.tif 000004
【図４】
0004445674.tif 000005
【図５】
0004445674.tif 000006
【図６】
0004445674.tif 000007
【図７】
0004445674.tif 000008
【図８】
0004445674.tif 000009
【図９Ａ】
0004445674.tif 000010
【図９Ｂ】
0004445674.tif 000011
【図１０】
0004445674.tif 000012
【図１１】
0004445674.tif 000013
【図１２Ａ】
0004445674.tif 000014
【図１２Ｂ】
0004445674.tif 000015
【図１２Ｃ】
0004445674.tif 000016
【図１２Ｄ】
0004445674.tif 000017