(57)【要約】  バイナリサーチ回路３６は、昇順又は降順に整列されたデータを格納した第１データベース５０から、バイナリサーチにより比較対象データを探索する。制御回路３６Ｚは、第１データベース５０の探索対象範囲を２ｎ個に分割したとき、比較対象データｘと、探索対象範囲の１／２ｎ、・・、（２ｎ−１）／２ｎの位置のデータとを、２ｎ−１個の比較回路３６Ａ〜３６Ｏのそれぞれに入力させ、第１段階として、探索対象範囲の１／２ｎ１、・・、（２ｎ１−１）／２ｎ１の位置のデータが入力された２ｎ１−１個の比較回路により範囲を判定し、第２段階として、第１段階で判定された範囲の１／２ｎ２、・・、（２ｎ２−１）／２ｎ２の位置のデータが入力された２ｎ２−１個の比較回路により範囲を判定し、以降同様にして、第Ｎ段階（ただし、ｎ１＋・・＋ｎＮ＝ｎ）まで繰り返すことにより、ｎ回分の探索を実行する。
2009066342.tif 000002
【特許請求の範囲】
【請求項１】
昇順又は降順に整列されたデータを格納したデータベースから、バイナリサーチにより比較対象データを探索する回路であって、
前記データベースから読み出されたデータと前記比較対象データとを比較する２ｎ−１個の比較回路と、
前記比較回路を制御する制御回路と、を備え、
前記制御回路は、前記データベースの探索対象範囲を２ｎ個に分割したとき、前記比較対象データと、前記探索対象範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータとを、前記２ｎ−１個の比較回路のそれぞれに入力させ、
まず、第１段階として、前記探索対象範囲の１／２ｎ１、２／２ｎ１、・・・、（２ｎ１−１）／２ｎ１の位置のデータが入力された２ｎ１−１個の比較回路により、前記比較対象データが、前記探索対象範囲を２ｎ１個に分割した範囲のいずれに属するかを判定し、つづいて、第２段階として、前記第１段階で判定された範囲の１／２ｎ２、２／２ｎ２、・・・、（２ｎ２−１）／２ｎ２の位置のデータが入力された２ｎ２−１個の比較回路により、前記比較対象データが、前記探索対象範囲を２ｎ１＋ｎ２個に分割した範囲のいずれに属するかを判定し、以降同様にして、第Ｎ段階（ただし、ｎ１＋ｎ２＋・・・＋ｎＮ＝ｎ）まで繰り返すことにより、ｎ回分の探索を実行し、
前記ｎ回分の探索において前記比較対象データが探索されなかった場合は、新たに、前記第Ｎ段階で判定された範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータを、前記２ｎ−１個の比較回路のそれぞれに入力させ、次のｎ回分の探索を実行することを特徴とするバイナリサーチ回路。
【請求項２】
第ｍ（１≦ｍ＜Ｎ）段階の比較回路の比較結果を示す出力信号から、次の第（ｍ＋１）段階の比較回路のうち前記第ｍ段階で判定された範囲のデータが入力されている比較回路に比較を実行させるトリガ信号を生成して第（ｍ＋１）段階の比較回路に入力するトリガ回路を更に備えることを特徴とする請求項１に記載のバイナリサーチ回路。
【請求項３】
前記トリガ回路は、第ｍ段階の２ｍ−１個の比較回路のうち、隣接する比較回路から異なる比較結果を示す出力信号が出力されたときに、それらの比較回路に入力されているデータの間の範囲のデータが入力された第（ｍ＋１）段階の比較回路に前記トリガ信号を入力することを特徴とする請求項２に記載のバイナリサーチ回路。
【請求項４】
第ｍ（１≦ｍ＜Ｎ）段階において、２ｍ−１個の比較回路は、同時に並列して比較を実行することを特徴とする請求項１から３のいずれかに記載のバイナリサーチ回路。
【請求項５】
前記比較回路のそれぞれに接続された２ｎ−１個の前記データベースを備え、
前記制御回路は、前記探索対象範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータを、それぞれの比較回路に接続されたデータベースから並列して入力させることを特徴とする請求項１から４のいずれかに記載のバイナリサーチ回路。
【請求項６】
昇順又は降順に整列されたデータを格納したデータベースの探索対象範囲を２ｎ個に分割したとき、比較対象データと、前記探索対象範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータとを、２ｎ−１個の比較回路のそれぞれに入力させるステップと、
第１段階として、前記探索対象範囲の１／２ｎ１、２／２ｎ１、・・・、（２ｎ１−１）／２ｎ１の位置のデータが入力された２ｎ１−１個の比較回路により、前記比較対象データが、前記探索対象範囲を２ｎ１個に分割した範囲のいずれに属するかを判定するステップと、
第２段階として、前記第１段階で判定された範囲の１／２ｎ２、２／２ｎ２、・・・、（２ｎ２−１）／２ｎ２の位置のデータが入力された２ｎ２−１個の比較回路により、前記比較対象データが、前記探索対象範囲を２ｎ１＋ｎ２個に分割した範囲のいずれに属するかを判定するステップと、
以降同様にして、第Ｎ段階（ただし、ｎ１＋ｎ２＋・・・＋ｎＮ＝ｎ）まで繰り返すことにより、ｎ回分の探索を実行するステップと、
前記ｎ回分の探索において前記比較対象データが探索されなかった場合は、新たに、前記第Ｎ段階で判定された範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータを、前記２ｎ−１個の比較回路のそれぞれに入力させ、次のｎ回分の探索を実行するステップと、
を含むことを特徴とするバイナリサーチ方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理技術に関し、特に、バイナリサーチ法によりデータベースからデータを探索するバイナリサーチ回路及び方法に関する。
【背景技術】
【０００２】
インターネットのインフラが整備され、携帯電話端末、パーソナルコンピュータ、ＶｏＩＰ（Voice over Internet Protocol）電話端末などの通信端末が広く普及した現在、インターネットの利用者は爆発的に増加している。このような状況下、コンピュータウイルス、ハッキング、スパムメールなど、セキュリティに関する問題が顕在化しており、通信を適切に制御する技術が求められている。通信環境の向上に伴って通信量も膨大になっており、大容量のデータを高速に処理する通信制御装置の必要性が増している。【０００３】
図１は、従来の通信制御装置１の構成を示す。従来の通信制御装置１は、受信側の通信制御部２と、パケット処理部３と、送出側の通信制御部４とを備える。通信制御部２及び４は、それぞれ、パケットの物理層の処理を行うＰＨＹ処理部５ａ及び５ｂと、パケットのＭＡＣ層の処理を行うＭＡＣ処理部６ａ及び６ｂとを備える。パケット処理部３は、ＩＰ（Internet Protocol）のプロトコル処理を行うＩＰ処理部７、ＴＣＰ（Transport Control Protocol）のプロトコル処理を行うＴＣＰ処理部８など、プロトコルに応じた処理を行うプロトコル処理部と、アプリケーション層の処理を行うＡＰ処理部９とを備える。ＡＰ処理部９は、パケットに含まれるデータに応じて、フィルタリングなどの処理を実行する。
【特許文献１】特開平４−１８０４２５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来の通信制御装置１では、パケット処理部３は、汎用プロセッサであるＣＰＵと、ＣＰＵ上で動作するＯＳとを利用して、ソフトウェアにより実現されていた。しかしながら、このような構成では、通信制御装置１の性能はＣＰＵの性能に依存することになり、高速に大容量のパケットを処理可能な通信制御装置を実現しようとしても、自ずと限界がある。例えば、６４ビットのＣＰＵであれば、一度に同時に処理可能なデータ量は最大で６４ビットであり、それ以上の性能を有する通信制御装置は存在しなかった。【０００５】
このように、光通信網などのインフラが普及してノード間のデータ通信速度は飛躍的に向上していても、通信制御装置の処理速度が律速となって、その能力を十分に発揮することができていないのが実状である。したがって、できる限り高速な通信制御装置を早急に実現することが強く求められている。【０００６】
本発明はこうした状況に鑑みてなされたものであり、その目的は、高速なデータベース検索を実現する技術の提供にある。
【課題を解決するための手段】
【０００７】
本発明のある態様は、バイナリサーチ回路に関する。このバイナリサーチ回路は、昇順又は降順に整列されたデータを格納したデータベースから、バイナリサーチにより比較対象データを探索する回路であって、前記データベースから読み出されたデータと前記比較対象データとを比較する２ｎ−１個の比較回路と、前記比較回路を制御する制御回路と、を備え、前記制御回路は、前記データベースの探索対象範囲を２ｎ個に分割したとき、前記比較対象データと、前記探索対象範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータとを、前記２ｎ−１個の比較回路のそれぞれに入力させ、まず、第１段階として、前記探索対象範囲の１／２ｎ１、２／２ｎ１、・・・、（２ｎ１−１）／２ｎ１の位置のデータが入力された２ｎ１−１個の比較回路により、前記比較対象データが、前記探索対象範囲を２ｎ１個に分割した範囲のいずれに属するかを判定し、つづいて、第２段階として、前記第１段階で判定された範囲の１／２ｎ２、２／２ｎ２、・・・、（２ｎ２−１）／２ｎ２の位置のデータが入力された２ｎ２−１個の比較回路により、前記比較対象データが、前記探索対象範囲を２ｎ１＋ｎ２個に分割した範囲のいずれに属するかを判定し、以降同様にして、第Ｎ段階（ただし、ｎ１＋ｎ２＋・・・＋ｎＮ＝ｎ）まで繰り返すことにより、ｎ回分の探索を実行し、前記ｎ回分の探索において前記比較対象データが探索されなかった場合は、新たに、前記第Ｎ段階で判定された範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータを、前記２ｎ−１個の比較回路のそれぞれに入力させ、次のｎ回分の探索を実行することを特徴とする。【０００８】
バイナリサーチ回路は、第ｍ（１≦ｍ＜Ｎ）段階の比較回路の比較結果を示す出力信号から、次の第（ｍ＋１）段階の比較回路のうち前記第ｍ段階で判定された範囲のデータが入力されている比較回路に比較を実行させるトリガ信号を生成して第（ｍ＋１）段階の比較回路に入力するトリガ回路を更に備えてもよい。【０００９】
前記トリガ回路は、第ｍ段階の２ｍ−１個の比較回路のうち、隣接する比較回路から異なる比較結果を示す出力信号が出力されたときに、それらの比較回路に入力されているデータの間の範囲のデータが入力された第（ｍ＋１）段階の比較回路に前記トリガ信号を入力してもよい。【００１０】
第ｍ（１≦ｍ＜Ｎ）段階において、２ｍ−１個の比較回路は、同時に並列して比較を実行してもよい。【００１１】
バイナリサーチ回路は、前記比較回路のそれぞれに接続された２ｎ−１個の前記データベースを備えてもよく、前記制御回路は、前記探索対象範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータを、それぞれの比較回路に接続されたデータベースから並列して入力させてもよい。【００１２】
本発明の別の態様は、バイナリサーチ方法に関する。このバイナリサーチ方法は、昇順又は降順に整列されたデータを格納したデータベースの探索対象範囲を２ｎ個に分割したとき、比較対象データと、前記探索対象範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータとを、２ｎ−１個の比較回路のそれぞれに入力させるステップと、第１段階として、前記探索対象範囲の１／２ｎ１、２／２ｎ１、・・・、（２ｎ１−１）／２ｎ１の位置のデータが入力された２ｎ１−１個の比較回路により、前記比較対象データが、前記探索対象範囲を２ｎ１個に分割した範囲のいずれに属するかを判定するステップと、第２段階として、前記第１段階で判定された範囲の１／２ｎ２、２／２ｎ２、・・・、（２ｎ２−１）／２ｎ２の位置のデータが入力された２ｎ２−１個の比較回路により、前記比較対象データが、前記探索対象範囲を２ｎ１＋ｎ２個に分割した範囲のいずれに属するかを判定するステップと、以降同様にして、第Ｎ段階（ただし、ｎ１＋ｎ２＋・・・＋ｎＮ＝ｎ）まで繰り返すことにより、ｎ回分の探索を実行するステップと、前記ｎ回分の探索において前記比較対象データが探索されなかった場合は、新たに、前記第Ｎ段階で判定された範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータを、前記２ｎ−１個の比較回路のそれぞれに入力させ、次のｎ回分の探索を実行するステップと、を含むことを特徴とする。【００１３】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１４】
本発明によれば、高速なバイナリサーチを実現する技術を提供することができる。
【図面の簡単な説明】
【００１５】
【図１】従来の通信制御装置の構成を示す図である。
【図２】実施の形態に係る通信制御装置の構成を示す図である。
【図３】パケット処理回路の構成を示す図である。
【図４】位置検出回路の構成を示す図である。
【図５】位置検出回路の別の例を示す図である。
【図６】位置検出回路の別の例を示す図である。
【図７】第１のデータベースの内部データを例を示す図である。
【図８】第１のデータベースの内部データを別の例を示す図である。
【図９】第１のデータベースの内部データを更に別の例を示す図である。
【図１０】インデックス回路の別の例を示す図である。
【図１１】バイナリサーチ回路に含まれる比較回路の構成を示す図である。
【図１２】バイナリサーチ回路の構成を示す図である。
【図１３】第１のデータベースの内部データの更に別の例を示す図である。
【図１４】第２のデータベースの内部データの例を示す図である。
【図１５】第２のデータベースの内部データの別の例を示す図である。
【図１６】バイナリサーチ回路の別の構成例を示す図である。
【図１７】バイナリサーチ回路の更に別の構成例を示す図である。
【符号の説明】
【００１６】
１０  通信制御装置、２０  パケット処理回路、３０  検索回路、３２  位置検出回路、３３  比較回路、３４  インデックス回路、３５  比較回路、３６  バイナリサーチ回路、３６Ａ〜３６Ｏ  比較回路、３７  否定回路、３８Ａ，３８Ｂ  排他的論理和回路、３６Ｚ  制御回路、４０  処理実行回路、５０  第１データベース、６０  第２データベース。
【発明を実施するための最良の形態】
【００１７】
図２は、本発明のデータ処理装置の一例である通信制御装置の構成を示す。本実施の形態の通信制御装置１０は、従来の通信制御装置においてはＣＰＵ及びＯＳを含むソフトウェアにより実現されていたパケット処理部に代えて、ワイヤードロジック回路による専用のハードウェアにより構成されたパケット処理回路２０を備える。汎用処理回路であるＣＰＵにおいて動作するＯＳとソフトウェアにより通信データを処理するのではなく、通信データを処理するための専用のハードウェア回路を設けることにより、ＣＰＵやＯＳなどに起因する性能の限界を克服し、処理能力の高い通信制御装置を実現することが可能となる。【００１８】
例えば、パケットフィルタリングなどを実行するために、パケットに含まれるデータに、フィルタリングの判断基準となる基準データが含まれるか否かを検索する場合に、ＣＰＵを用いて通信データと基準データを比較すると、一度に高々６４ビットしか比較することができず、処理速度を向上させようとしてもＣＰＵの性能で頭打ちになるという問題があった。ＣＰＵでは、通信データから６４ビットをメモリへ読み上げ、基準データとの比較を行い、つづいて、次の６４ビットをメモリへ読み上げる、という処理を何度も繰り返し行う必要があるので、メモリへの読み上げ時間が律速となり、処理速度に限界がある。【００１９】
それに対し、本実施の形態では、通信データと基準データとを比較するために、ワイヤードロジック回路により構成された専用のハードウェア回路を設ける。この回路は、６４ビットよりも長いデータ長、例えば、１０２４ビットのデータ長の比較を可能とするために、並列に設けられた複数の比較器を含む。このように、専用のハードウェアを設けることにより、同時に並列して多数のビットマッチングを実行することができる。従来のＣＰＵを用いた通信制御装置１では一度に６４ビットしか処理できなかったところを、一度に１０２４ビットの処理を可能にすることで、飛躍的に処理速度を向上させることができる。比較器の数を多くすれば処理能力も向上するが、コストやサイズも増大するので、所望の処理性能と、コスト、サイズ、などを考慮して、最適なハードウェア回路を設計すればよい。【００２０】
また、本実施の形態の通信制御装置１０は、ワイヤードロジック回路による専用のハードウェアにより構成されるので、ＯＳ（Operating System）を必要としない。このため、ＯＳのインストール、バグ対応、バージョンアップなどの作業が必要なく、管理やメンテナンスのためのコストや工数を低減させることができる。また、汎用的な機能が求められるＣＰＵとは異なり、不必要な機能を包含していないので、余計なリソースを用いることがなく、低コスト化、回路面積の低減、処理速度の向上などが望める。さらに、ＯＳを利用していた従来の通信制御装置とは異なり、余分な機能を有しないので、セキュリティホールなどが発生する可能性が低く、ネットワークを介した悪意ある第三者からの攻撃に対する耐性に優れている。【００２１】
従来の通信制御装置１は、ＣＰＵとＯＳを前提としたソフトウェアによりパケットを処理しており、パケットの全てのデータを受信してからプロトコル処理を行い、データがアプリケーションに渡される。それに対して、本実施の形態の通信制御装置１０では、専用のハードウェア回路により処理を行うので、パケットの全てのデータを受信してから処理を開始する必要はなく、処理に必要なデータを受信すれば、後続のデータの受信を待たずに、任意の時点で処理を開始することができる。例えば、後述する位置検出回路における位置検出処理は、比較対象データの位置を特定するための位置特定データを受信した時点で開始することができる。このように、全てのデータの受信を待たずに様々な処理をフローティングで実行することができるので、パケットのデータを処理するのに要する時間を短縮することができる。【００２２】
図３は、パケット処理回路の内部構成を示す。パケット処理回路２０は、通信データに対して実行する処理の内容を決定するための基準となる基準データを記憶する第１データベース５０Ａ、５０Ｂ、及び５０Ｃ（これらを総称して「第１データベース５０」という）と、受信された通信データの中に基準データが含まれているか否かを、通信データと基準データとを比較することにより検索する検索回路３０と、検索回路３０による検索結果と通信データに対して実行する処理の内容とを対応づけて記憶する第２データベース６０と、検索回路３０による検索結果と第２データベース６０に記憶された条件とに基づいて通信データを処理する処理実行回路４０とを含む。【００２３】
検索回路３０は、通信データの中から基準データと比較すべき比較対象データの位置を検出する位置検出回路３２と、第１データベース５０に記憶された基準データを３以上の範囲に分割したとき、比較対象データがそれらの範囲のうちいずれに属するかを判定する判定回路の一例であるインデックス回路３４と、判定された範囲の中で比較対象データと合致する基準データを検索するバイナリサーチ回路３６とを含む。比較対象データを基準データの中から検索する方法としては、任意の検索技術を利用可能であるが、本実施の形態ではバイナリサーチ法を用いる。本実施の形態では、後述するように、改良されたバイナリサーチ法を用いるので、そのために第１データベース５０を３つ設けている。第１データベース５０Ａ、５０Ｂ、及び５０Ｃには、同じ基準データが格納されている。【００２４】
図４は、位置検出回路の内部構成を示す。位置検出回路３２は、比較対象データの位置を特定するための位置特定データと通信データとを比較するための複数の比較回路３３ａ〜３３ｆを含む。ここでは、６個の比較回路３３ａ〜３３ｆが設けられているが、後述するように、比較回路の個数は任意でよい。それぞれの比較回路３３ａ〜３３ｆには、通信データが、所定のデータ長、例えば、１バイトずつずらして入力される。そして、これら複数の比較回路３３ａ〜３３ｆにおいて、同時に並列して、検出すべき位置特定データと通信データとの比較がなされる。【００２５】
本実施の形態においては、通信制御装置１０の動作を説明するための例として、通信データ中に含まれる「Ｎｏ．  ＃＃＃」という文字列を検出し、その文字列中に含まれる数字「＃＃＃」を基準データと比較して、基準データに合致した場合はパケットの通過を許可し、合致しなかった場合はパケットを破棄する処理を行う場合について説明する。【００２６】
図４の例では、通信データの中から、数字「＃＃＃」の位置を特定するための位置特定データ「Ｎｏ．」を検出するために、通信データ「０１Ｎｏ．  ３６１・・・」を、１文字ずつずらして比較回路３３ａ〜３３ｆに入力している。すなわち、比較回路３３ａには「０１Ｎ」が、比較回路３３ｂには「１Ｎｏ」が、比較回路３３ｃには「Ｎｏ．」が、比較回路３３ｄには「ｏ．  」が、比較回路３３ｅには「．  ３」が、比較回路３３ｆには「  ３６」が、それぞれ入力される。ここで、比較回路３３ａ〜３３ｆが同時に位置特定データ「Ｎｏ．」との比較を実行する。これにより、比較回路３３ｃがマッチし、通信データの先頭から３文字目に「Ｎｏ．」という文字列が存在することが検出される。こうして、位置検出回路３２により検出された位置特定データ「Ｎｏ．」の次に、比較対象データである数字のデータが存在することが検出される。【００２７】
ＣＰＵにより同様の処理を行うならば、まず、文字列「０１Ｎ」を「Ｎｏ．」と比較し、続いて、文字列「１Ｎｏ」を「Ｎｏ．」と比較する、というように、先頭から順に１つずつ比較処理を実行する必要があるため、検出速度の向上は望めない。これに対し、本実施の形態の通信制御装置１０では、複数の比較回路３３ａ〜３３ｆを並列に設けることにより、ＣＰＵではなしえなかった同時並列的な比較処理が可能となり、処理速度を格段に向上させることができる。比較回路は多ければ多いほど同時に比較可能な位置が多くなるので、検出速度も向上するが、コスト、サイズ、などを考慮の上、所望の検出速度を得られるのに十分な数の比較回路を設ければよい。【００２８】
位置検出回路３２は、位置特定データを検出するためだけでなく、汎用的に文字列を検出する回路として利用されてもよい。また、文字列だけでなく、ビット単位で位置特定データを検出するように構成されてもよい。【００２９】
図５は、位置検出回路の別の例を示す。図５に示した例では、位置検出回路３２に設けられたそれぞれの比較回路３３ａ〜３３ｆのデータ長よりも位置特定データの方が短い場合は、位置特定データの後に所定のデータ、例えば、「００Ｈ」又は「０１Ｈ」などをパディングする。また、位置特定データと比較する通信データについても、位置特定データと同じデータ長のみを抜き出して、その後に、位置特定データにパディングしたデータと同じデータをパディングする。このとき、通信データ自身を改変しないために、通信データをワークとしてコピーし、コピーしたデータを加工して比較回路３３ａ〜３３ｆに入力してもよい。これにより、位置特定データのデータ長によらず、位置検出回路３２を汎用的に用いることができる。【００３０】
図６は、位置検出回路の更に別の例を示す。図６に示した例では、図５に示した例と同様に、位置特定データの後に所定のデータをパディングするが、このデータをワイルドカードとして扱う。すなわち、比較回路３３ａ〜３３ｆは、ワイルドカードであるデータが入力されると、比較対象のデータが何であっても無条件に合致したと判定する。これにより、位置特定データのデータ長によらず、位置検出回路３２を汎用的に用いることができる。【００３１】
図７は、第１データベースの内部データの例を示す。第１データベース５０には、パケットのフィルタリング、ルーティング、スイッチング、置換などの処理の内容を決定するための基準となる基準データが、何らかのソート条件にしたがって昇順又は降順にソートされて格納されている。図７の例では、１０００個の基準データが記憶されている。【００３２】
インデックス回路３４は、第１データベース５０に格納されている基準データを３以上の範囲５２ａ〜５２ｄに分割したとき、比較対象データがそれらの範囲のうちいずれに属するかを判定する。図７の例では、１０００個の基準データは、２５０個ずつ４つの範囲５２ａ〜５２ｄに分割されている。インデックス回路３４は、範囲の境界の基準データと比較対象データとを比較する複数の比較回路３５ａ〜３５ｃを含む。比較回路３５ａ〜３５ｃにより比較対象データと境界の基準データとを同時に並列して比較することにより、比較対象データがいずれの範囲に属するかを１度の比較処理で判定することができる。【００３３】
インデックス回路３４の比較回路３５ａ〜３５ｃに入力される境界の基準データは、通信制御装置１０の外部に設けられた装置により設定されてもよいし、予め第１データベース５０の所定位置の基準データが自動的に入力されるようにしてもよい。後者の場合、第１データベース５０を更新しても、自動的に第１データベース５０の所定位置の基準データが比較回路３５ａ〜３５ｃに入力されるので、初期設定などを必要とせず、直ちに通信制御処理を実行させることができる。【００３４】
前述したように、ＣＰＵによりバイナリサーチを実行する場合は、同時に複数の比較を実行することができないが、本実施の形態の通信制御装置１０では、複数の比較回路３５ａ〜３５ｃを並列に設けることにより、同時並列的な比較処理を可能とし、検索速度を格段に向上させることができる。【００３５】
インデックス回路３４により範囲が判定されると、バイナリサーチ回路３６がバイナリサーチ法により検索を実行する。バイナリサーチ回路３６は、インデックス回路３４により判定された範囲をさらに２ｎ個に分割し、その境界位置にある基準データと比較対象データとを比較することにより、いずれの範囲に属するかを判定する。バイナリサーチ回路３６は、基準データと比較対象データとをビット単位で比較する比較器を複数個、例えば本実施の形態では１０２４個含んでおり、１０２４ビットのビットマッチングを同時に実行する。２ｎ分割された範囲のいずれに属するかが判定されると、さらに、その範囲を２ｎ分割して境界位置にある基準データを読み出し、比較対象データと比較する。以降、この処理を繰り返すことにより範囲をさらに限定し、最終的に比較対象データと合致する基準データを検索する。【００３６】
前述した例を用いてさらに詳細に動作を説明する。インデックス回路３４の比較回路３５ａ〜３５ｃには、比較対象データとして「３６１」が入力され、基準データとして、比較回路３５ａには、範囲５２ａと５２ｂの境界にある基準データ「３７８」が、比較回路３５ｂには、範囲５２ｂと５２ｃの境界にある基準データ「７０４」が、比較回路３５ｃには、範囲５２ｃと５２ｄの境界にある基準データ「９３７」が、それぞれ入力される。比較回路３５ａ〜３５ｃにより同時に比較が行われ、比較対象データ「３６１」が範囲５２ａに属することが判定される。以降、バイナリサーチ回路３６が基準データの中に比較対象データ「３６１」が存在するか否かを検索する。【００３７】
図８は、第１データベースの内部データの別の例を示す。図８に示した例では、基準データのデータ数が、第１データベース５０に保持可能なデータ数、ここでは１０００個よりも少ない。このとき、第１データベース５０には、最終データ位置から降順に基準データが格納される。そして、残りのデータには０が格納される。データベースのローディング方法として、先頭からデータを配置せずにローディングエリアの後方から配置し、ローディングエリア先頭に空きが生じた場合は全ての空きをゼロサプレスすることで、データーベースは常にフルの状態になり、バイナリー検索する場合の検索時間を一定にすることができる。また、バイナリサーチ回路３６は、検索中に基準データとして「０」を読み込んだときには、比較結果が自明であるから、比較を行わずに範囲を特定して、次の比較にうつることができる。これにより、検索速度を向上させることができる。【００３８】
ＣＰＵによるソフトウェア処理においては、第１データベース５０に基準データを格納する際に、最初のデータ位置から昇順に基準データが格納される。残りのデータには、例えば最大値が格納されることになるが、この場合、バイナリサーチにおいて、上述したような比較処理の省略はできない。上述した比較技術は、専用のハードウェア回路により検索回路３０を構成したことにより実現される。【００３９】
図９は、第１データベースの内部データのさらに別の例を示す。図９に示した例では、基準データを均等に３以上の範囲に分割するのではなく、範囲５２ａは５００個、範囲５２ｂは１００個というように、範囲に属する基準データの数が不均一になっている。これらの範囲は、通信データ中における基準データの出現頻度の分布に応じて設定されてもよい。すなわち、それぞれの範囲に属する基準データの出現頻度の和がほぼ同じになるように範囲が設定されてもよい。これにより、検索効率を向上させることができる。インデックス回路３４の比較回路３５ａ〜３５ｃに入力される基準データは、外部から変更可能になっていてもよい。これにより、範囲を動的に設定することができ、検索効率を最適化することができる。【００４０】
図１０は、インデックス回路の別の例を示す。図７〜９に示した例では、インデックス回路３４は、３つの比較回路３５ａ〜３５ｃを用いて、比較対象データが第１データベース５０の４つの範囲５２ａ〜５２ｄのいずれに属するかを判定したが、図１０の例では、インデックス回路３４には、比較対象データが、４つの範囲５２ａ〜５２ｄのそれぞれに含まれるか否かを判定するための４つの比較回路３５ｄ〜３５ｇが設けられている。例えば、比較回路３５ｄには、第１データベース５０の０件目の基準データと、２５０件目の基準データと、比較対象データとが入力され、それぞれの基準データと比較対象データとを比較することにより、基準データが範囲５２ａに含まれるか否かを判定する。それぞれの比較回路３５ｄ〜３５ｇの比較結果は判定回路３５ｚに入力され、判定回路３５ｚから、基準データがいずれの範囲に含まれているかが出力される。比較回路３５ｄ〜３５ｇは、基準データが入力された２つの基準データの間に含まれるか否かを出力してもよいし、範囲よりも大きい、範囲に含まれる、範囲よりも小さい、のいずれかを出力してもよい。比較対象データが、範囲５２ａ〜５２ｄのいずれにも含まれないと判定された場合は、比較対象データが第１データベース５０中に存在しないことが分かるので、以降のバイナリサーチを行うまでもなく、検索を終了することができる。【００４１】
図１１は、バイナリサーチ回路に含まれる比較回路の構成を示す。前述したように、バイナリサーチ回路３６に含まれる比較回路は、１０２４個の比較器３６ａ、３６ｂ、・・・、を含む。それぞれの比較器３６ａ、３６ｂ、・・・、には、基準データ５４と比較対象データ５６が１ビットずつ入力され、それらの大小が比較される。インデックス回路３４の各比較回路３５ａ〜３５ｃの内部構成も同様である。このように、専用のハードウェア回路で比較処理を実行することにより、多数の比較回路を並列して動作させ、多数のビットを同時に比較することができるので、比較処理を高速化することができる。【００４２】
図１２は、バイナリサーチ回路の構成を示す。バイナリサーチ回路３６は、図１１に示した１０２４個の比較器３６ａ、３６ｂ、・・・を含む比較回路３６Ａ、３６Ｂ、及び３６Ｃと、それらの比較回路を制御する制御回路３６Ｚを含む。【００４３】
従来のバイナリサーチ法では、まず１回目は、データが昇順又は降順に整列されたデータベースの探索対象範囲の１／２の位置にあるデータを読み出して比較対象データと比較する。データが昇順に並べられている場合、比較対象データの方が小さければ、比較対象データは探索対象範囲の前半に存在するので、２回目は前半を探索対象範囲としてその１／２、すなわち最初の探索対象範囲の１／４の位置にあるデータを読み出して比較対象データと比較する。逆に、比較対象データの方が大きければ、比較対象データは探索対象範囲の後半に存在するので、２回目は後半を探索対象範囲としてその１／２、すなわち最初の探索対象範囲の３／４の位置にあるデータを読み出して比較対象データと比較する。このように、探索対象範囲を半分ずつ絞っていき、最終的に対象データに到達する。【００４４】
本実施の形態では、バイナリサーチのための比較回路を３つ設けているので、１回目の探索のために探索対象範囲の１／２の位置にあるデータと比較対象データとを比較させるときに、同時に並行して、２回目の探索のために探索対象範囲の１／４及び３／４の位置にあるデータと比較対象データとを比較させる。これにより、２回分の探索を一度に行うことができるので、データベースからデータを読み上げる時間を短縮することができる。また、３つの比較回路を同時に並列して動作させることにより、比較の回数を半分に抑え、探索に要する時間を短縮することができる。【００４５】
図１２の例では、２回分の探索を同時に行うために、３つの比較回路を設けたが、一般に、ｎ回分の探索を同時に並行して行うためには、２ｎ−１個の比較回路を設ければよい。制御回路３６Ｚは、探索対象範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータを、２ｎ−１個の比較回路のそれぞれに入力させ、それらを同時に並列して動作させて比較対象データと比較させる。制御回路３６Ｚは、それぞれの比較回路の比較結果を取得して、比較対象データが探索されたか否かを判定する。制御回路３６Ｚは、いずれかの比較回路が、データが一致した旨の信号を出力した場合、比較対象データが探索されたと判定して、バイナリサーチを終了する。一致した旨の信号が出力されなかった場合、次回の探索に移る。比較対象データがデータベースに存在するならば、２ｎ−１個の比較回路の比較結果が反転する範囲に存在するはずである。例えば、１５個の比較回路が設けられているときに、５／１６の位置のデータが比較対象データより小さく、６／１６の位置のデータが比較対象データより大きければ、５／１６から６／１６の間の範囲に比較対象データがある。したがって、制御回路３６Ｚは、各比較回路の比較結果を取得して、比較結果が反転した範囲を次回の探索対象範囲と決定し、決定された次回の探索対象範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータをそれぞれの比較回路へ入力させる。【００４６】
本実施の形態では、第１データベース５０を３つ設けており、第１データベース５０Ａは比較回路３６Ａに接続されて探索対象範囲の１／４の位置にあるデータを比較回路３６Ａに供給し、第２データベース５０Ｂは比較回路３６Ｂに接続されて探索対象範囲の２／４の位置にあるデータを比較回路３６Ｂに供給し、第１データベース５０Ｃは比較回路３６Ｃに接続されて探索対象範囲の３／４の位置にあるデータを比較回路３６Ｃに供給する。これにより、それぞれの比較回路にデータを同時に並行して読み上げることができるので、データの読み上げに要する時間を更に短縮し、バイナリサーチを高速化することができる。【００４７】
比較回路は多ければ多いほど探索速度も向上するが、コスト、サイズなどを考慮の上、所望の探索速度を得られるのに十分な数の比較回路を設ければよい。また、比較回路の数と同じだけ第１データベースを設けるのが好ましいが、コスト、サイズなどを考慮の上、いくつかの比較回路でデータベースを共用してもよい。【００４８】
図１３は、第１データベースの内部データの更に別の例を示す。図１３に示した第１データベース５０は、フィルタリングの対象となるコンテンツのＵＲＬを格納している。第１データベース５０に格納されるデータは、ワイルドカードとして認識される所定のデータ、例えば、「００Ｈ」又は「０１Ｈ」などを含んでもよい。図１３に示した例において、「http://www.xx.xx/*********」は、「*********」がワイルドカードとして認識され、比較器３６ａ、３６ｂ、・・・において、比較対象データが何であっても合致すると判定される。したがって、「http://www.xx.xx/」で始まる文字列は全てバイナリサーチ回路３６により検出される。これにより、例えば、ドメイン「http://www.xx.xx/」の配下にあるコンテンツの全てにフィルタリングをかける処理などを容易に行うことができる。【００４９】
図１４は、第２データベースの内部データの例を示す。第２データベース６０は、検索回路３０による検索結果を格納する検索結果欄６２と、通信データに対して実行する処理の内容を格納する処理内容欄６４とを含み、検索結果と処理内容とを対応づけて保持する。図１４の例では、通信データに基準データが含まれている場合は、そのパケットの通過を許可し、含まれていない場合は、そのパケットを破棄するという条件が設定されている。処理実行回路４０は、検索結果に基づいて第２データベース６０から処理内容を検索し、通信データに対して処理を実行する。処理実行回路４０も、ワイヤードロジック回路により実現されてもよい。【００５０】
図１５は、第２データベースの内部データの別の例を示す。図１５の例では、基準データごとに、処理内容が設定されている。パケットの置換を行う場合、置換先のデータを第２データベース６０に格納しておいてもよい。パケットのルーティングやスイッチングを行う場合、経路に関する情報を第２データベース６０に格納しておいてもよい。処理実行回路４０は、検索回路３０による検索結果に応じて、第２データベース６０に格納された、フィルタリング、ルーティング、スイッチング、置換などの処理を実行する。図１５のように、基準データごとに処理内容を設定する場合、第１データベース５０と第２データベース６０とを統合してもよい。【００５１】
図１６は、バイナリサーチ回路の別の構成例を示す。図１６に示した例では、４回分の探索を一度に実行するために、１５個の比較回路３６Ａ〜３６Ｏが設けられている。制御回路３６Ｚは、１５個の比較回路３６Ａ〜３６Ｏのそれぞれに接続された第１データベース５０から、探索対象範囲の１／１６、２／１６、・・・、１５／１６の位置のデータを同時に並列して読み上げて比較回路３６Ａ〜３６Ｏに入力する。また、比較対象データｘをそれぞれの比較回路３６Ａ〜３６Ｏに入力する。【００５２】
制御回路３６Ｚは、まず、第１段階として、探索対象範囲の４／１６、８／１６、１２／１６の位置のデータが入力された３個の比較回路３６Ａ、３６Ｂ、３６Ｃにより、比較対象データｘが、探索対象範囲を４個に分割した範囲のいずれに属するかを判定する。つづいて、第２段階として、第１段階で判定された範囲の１／４、２／４、３／４の位置のデータが入力された３個の比較回路により、比較対象データｘが、探索対象範囲を１６個に分割した範囲のいずれに属するかを判定する。【００５３】
バイナリサーチ回路３６には、第１段階の比較回路３６Ａ、３６Ｂ、３６Ｃの比較結果を示す出力信号から、次の第２段階の比較回路３６Ｄ〜３６Ｏのうち第１段階で判定された範囲のデータが入力されている比較回路に比較を実行させるトリガ信号を生成して第２段階の比較回路３６Ｄ〜３６Ｏに入力するトリガ回路として、否定回路３７及び排他的論理和回路３８Ａ、３８Ｂを更に備えている。ここで、比較回路３６Ａ〜３６Ｏは、比較対象データｘが参照データよりも大きいときに「１」、小さいときに「０」を出力するものとする。【００５４】
まず、第１段階の比較回路３６Ａ、３６Ｂ、３６Ｃにトリガ信号が入力され、同時に並列して比較が実行される。比較回路３６Ａの出力が「０」であれば、比較対象データｘは、第１データベース５０の探索対象範囲のうち０／１６〜４／１６の範囲に属するので、その範囲の参照データが入力されている比較回路３６Ｄ、３６Ｅ、３６Ｆに、否定回路３７を介して、トリガ信号「１」が入力される。これにより、第２段階の比較回路３６Ｄ〜３６Ｏのうち、探索対象範囲の１／１６、２／１６、３／１６の位置の参照データが入力されている比較回路３６Ｄ、３６Ｅ、３６Ｆのみが起動され、同時に並列して第２段階の比較を実行する。比較対象データｘが、探索対象範囲のうち４／１６〜１６／１６の範囲に属する場合は、比較回路３６Ａの出力が「１」となるので、否定回路３７からは「０」が出力され、比較回路３６Ｄ、３６Ｅ、３６Ｆには、トリガ信号が入力されない。【００５５】
比較回路３６Ａの出力が「１」で、比較回路３６Ｂの出力が「０」であれば、比較対象データｘは、探索対象範囲のうち４／１６〜８／１６の範囲に属するので、その範囲の参照データが入力されている比較回路３６Ｇ、３６Ｈ、３６Ｉに、排他的論理和回路３８Ａを介して、トリガ信号「１」が入力される。これにより、第２段階の比較回路３６Ｄ〜３６Ｏのうち、探索対象範囲の５／１６、６／１６、７／１６の位置の参照データが入力されている比較回路３６Ｇ、３６Ｈ、３６Ｉのみが起動され、同時に並列して第２段階の比較を実行する。比較対象データｘが、探索対象範囲のうち４／１６〜８／１６の範囲に属さない場合は、比較回路３６Ａ及び３６Ｂの出力が同じになるので、排他的論理和回路３８Ａからは「０」が出力され、３６Ｇ、３６Ｈ、３６Ｉには、トリガ信号は入力されない。【００５６】
比較回路３６Ｂの出力が「１」で、比較回路３６Ｃの出力が「０」であれば、比較対象データｘは、探索対象範囲のうち８／１６〜１２／１６の範囲に属するので、その範囲の参照データが入力されている比較回路３６Ｊ、３６Ｋ、３６Ｌに、排他的論理和回路３８Ｂを介して、トリガ信号「１」が入力される。これにより、第２段階の比較回路３６Ｄ〜３６Ｏのうち、探索対象範囲の９／１６、１０／１６、１１／１６の位置の参照データが入力されている比較回路３６Ｊ、３６Ｋ、３６Ｌのみが起動され、同時に並列して第２段階の比較を実行する。比較対象データｘが、探索対象範囲のうち８／１６〜１２／１６の範囲に属さない場合は、比較回路３６Ｂ及び３６Ｃの出力が同じになるので、排他的論理和回路３８Ｂからは「０」が出力され、３６Ｊ、３６Ｋ、３６Ｌには、トリガ信号は入力されない。【００５７】
比較回路３６Ｃの出力が「１」であれば、比較対象データｘは、探索対象範囲のうち１２／１６〜１６／１６の範囲に属するので、その範囲の参照データが入力されている比較回路３６Ｍ、３６Ｎ、３６Ｏに、比較回路３６Ｃの出力信号がトリガ信号「１」として入力される。これにより、第２段階の比較回路３６Ｄ〜３６Ｏのうち、探索対象範囲の１３／１６、１４／１６、１５／１６の位置の参照データが入力されている比較回路３６Ｍ、３６Ｎ、３６Ｏのみが起動され、同時に並列して第２段階の比較を実行する。比較対象データｘが、探索対象範囲のうち０／１６〜１２／１６の範囲に属する場合は、比較回路３６Ｃの出力が「０」となるので、３６Ｍ、３６Ｎ、３６Ｏには、トリガ信号は入力されない。【００５８】
こうして、図１６に示した例では、２段階の比較処理で４回分の探索を実行することができる。この４回分の探索において比較対象データｘが探索されなかった場合は、制御回路３６Ｚは、新たに、第２段階で判定された範囲の１／１６、２／１６、・・・、１５／１６の位置のデータを、１５個の比較回路３６Ａ〜３６Ｏのそれぞれに入力させ、次の４回分の探索を実行する。【００５９】
このように、ｎ回分の探索を行うための比較回路を複数の段階に階層化させ、第２段階以降は、前段階までに判定された範囲の比較回路のみを動作させるので、消費電力を低減させることができる。【００６０】
図１６の例では、４回分の探索を同時に行うために、１５個の比較回路を設けたが、一般に、ｎ回分の探索を同時に並行して行うためには、２ｎ−１個の比較回路を設ければよい。制御回路３６Ｚは、第１データベース５０の探索対象範囲を２ｎ個に分割したとき、比較対象データｘと、探索対象範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータとを、２ｎ−１個の比較回路のそれぞれに入力させる。まず、第１段階として、探索対象範囲の１／２ｎ１、２／２ｎ１、・・・、（２ｎ１−１）／２ｎ１の位置のデータが入力された２ｎ１−１個の比較回路により、比較対象データｘが、探索対象範囲を２ｎ１個に分割した範囲のいずれに属するかを判定する。つづいて、第２段階として、第１段階で判定された範囲の１／２ｎ２、２／２ｎ２、・・・、（２ｎ２−１）／２ｎ２の位置のデータが入力された２ｎ２−１個の比較回路により、比較対象データｘが、探索対象範囲を２ｎ１＋ｎ２個に分割した範囲のいずれに属するかを判定する。以降同様にして、第Ｎ段階（ただし、ｎ１＋ｎ２＋・・・＋ｎＮ＝ｎ）まで繰り返すことにより、ｎ回分の探索を実行する。ｎ回分の探索において比較対象データｘが探索されなかった場合は、新たに、第Ｎ段階で判定された範囲の１／２ｎ、２／２ｎ、・・・、（２ｎ−１）／２ｎの位置のデータを、２ｎ−１個の比較回路のそれぞれに入力させ、次のｎ回分の探索を実行する。【００６１】
この場合、トリガ回路は、第ｍ（１≦ｍ＜Ｎ）段階の比較回路の比較結果を示す出力信号から、次の第（ｍ＋１）段階の比較回路のうち第ｍ段階で判定された範囲のデータが入力されている比較回路に比較を実行させるトリガ信号を生成して第（ｍ＋１）段階の比較回路に入力する。具体的には、第ｍ段階の２ｍ−１個の比較回路のうち、隣接する比較回路から異なる比較結果を示す出力信号が出力されたときに、それらの比較回路に入力されているデータの間の範囲のデータが入力された第（ｍ＋１）段階の比較回路にトリガ信号を入力すればよい。また、第ｍ段階で判定される２ｍの範囲のうち、最小の範囲と、最大の範囲のデータが入力された第（ｍ＋１）段階の比較回路には、第ｍ段階の２ｍ−１個の比較回路のうち、最小と最大の参照データが入力された比較回路の比較結果に応じてトリガ信号を入力すればよい。【００６２】
図１７は、バイナリサーチ回路の更に別の構成例を示す。図１７に示した例では、バイナリサーチ回路３６は、３つの比較回路３６Ａ〜３６Ｃを用いて、比較対象データｘが第１データベース５０の探索対象範囲を４つに分割した範囲のいずれに属するかを判定したが、図１７の例では、比較対象データｘが、４つの範囲のそれぞれに含まれるか否かを判定するための４つの比較回路３６Ｐ〜３６Ｓが設けられている。例えば、比較回路３６Ｐには、第１データベース５０の探索対象範囲の０／１６の位置にある基準データと、４／１６の位置にある基準データと、比較対象データｘとが入力され、それぞれの基準データと比較対象データｘとを比較することにより、基準データが探索対象範囲の０／１６から４／１６の範囲に含まれるか否かを判定する。範囲に含まれる場合には、比較回路３６Ｐから、その範囲に含まれるデータが参照データとして入力されている比較回路３６Ｄ、３６Ｅ、３６Ｆに、トリガ信号が入力される。これにより、第２段階では、第１段階で判定された範囲の比較回路のみが比較を実行するので、消費電力を低減させることができる。【００６３】
なお、図１６及び図１７に示した例では、ｎ回分の探索を一度に行うための２ｎ−１個の比較回路のうち、１／２ｎ１、２／２ｎ１、・・・、（２ｎ１−１）／２ｎ１の位置のデータが入力された２ｎ１−１個の比較回路を第１段階の比較回路としたが、これに限らず、任意の位置のデータが入力された比較回路を第１段階の比較回路としてもよい。要は、複数の比較回路を階層化し、前段階までに判定された範囲の比較回路のみを動作させるようにすればよい。【００６４】
第１のデータベース及び第２のデータベースは、外部から書き換え可能に設けられる。これらのデータベースを入れ替えることにより、同じ通信制御装置１０を用いて、さまざまなデータ処理や通信制御を実現することができる。また、検索対象となる基準データを格納したデータベースを２以上設けて、多段階の検索処理を行ってもよい。このとき、検索結果と処理内容とを対応づけて格納したデータベースを２以上設けて、より複雑な条件分岐を実現してもよい。このように、データベースを複数設けて多段階の検索を行う場合に、位置検出回路３２、インデックス回路３４、バイナリサーチ回路３６などを複数設けてもよい。【００６５】
上述した比較に用いられるデータは、同じ圧縮ロジックにより圧縮されてもよい。比較に際して、比較元のデータと比較先のデータが同じ方式で圧縮されていれば、通常と同様の比較が可能である。これにより、比較の際にローディングするデータ量を低減することができる。ローディングするデータ量が少なくなれば、メモリからデータを読み出すのに要する時間が短縮されるので、全体の処理時間も短縮することができる。また、比較器の量を削減することができるので、装置の小型化、軽量化、低コスト化に寄与することができる。比較に用いられるデータは、圧縮された形式で格納されていてもよいし、メモリから読み出した後、比較の前に圧縮されてもよい。【００６６】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【産業上の利用可能性】
【００６７】
本発明は、データベースからデータを探索するバイナリサーチ回路に利用することができる。
【図１】
2009066342.tif 000003
【図２】
2009066342.tif 000004
【図３】
2009066342.tif 000005
【図４】
2009066342.tif 000006
【図５】
2009066342.tif 000007
【図６】
2009066342.tif 000008
【図７】
2009066342.tif 000009
【図８】
2009066342.tif 000010
【図９】
2009066342.tif 000011
【図１０】
2009066342.tif 000012
【図１１】
2009066342.tif 000013
【図１２】
2009066342.tif 000014
【図１３】
2009066342.tif 000015
【図１４】
2009066342.tif 000016
【図１５】
2009066342.tif 000017
【図１６】
2009066342.tif 000018
【図１７】
2009066342.tif 000019
【国際調査報告】
2009066342.tif 000020
2009066342.tif 000021