パターンマッチングアーキテクチャ
【課題】 本発明の課題は、上記問題点に鑑み、基準テンプレートまたはパターンとデータとの迅速であり、複数のアルゴリズムを選択可能な低消費電力を実現するパターンマッチングアーキテクチャを提供することである。
【解決手段】
本発明による装置は、入力データをビット数がプログラム可能な入力ビットフィールドに分割し、１以上の基準テンプレートをビット数がプログラム可能な対応する基準ビットフィールドに分割する選択ユニットと、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の１以上の距離を決定し、前記基準ビットフィールドに係る１以上の距離を前記基準テンプレートに対応する１以上のネットの距離に合成する距離ユニットとから構成される。
【解決手段】
本発明による装置は、入力データをビット数がプログラム可能な入力ビットフィールドに分割し、１以上の基準テンプレートをビット数がプログラム可能な対応する基準ビットフィールドに分割する選択ユニットと、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の１以上の距離を決定し、前記基準ビットフィールドに係る１以上の距離を前記基準テンプレートに対応する１以上のネットの距離に合成する距離ユニットとから構成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にパターン認識に関し、より詳細には、基準テンプレートまたはパターンとデータとの迅速なマッチング処理に関する。
【背景技術】
【０００２】
一般的なパターンマッチングプロセスでは、基準テンプレートが入力データと比較され、どの基準テンプレートが入力データと最も良く一致するか判断される。
【０００３】
１つのパターンマッチングアーキテクチャは、パターン認識ソフトウェアを実行する汎用コンピュータである。このアーキテクチャは以下の利点を有する。ａ）このアーキテクチャは、ソフトウェアにより実現により各種パターン比較アルゴリズムを搭載することができる。ｂ）典型的には、基準テンプレートの個数が通常はコンピュータシステムメモリの容量のみの制約しか受けないため、多数の基準テンプレートを利用することが可能である。しかしながら、このアーキテクチャは、低速なパフォーマンス、大きな電力消費、多数のアプリケーション、高価で複雑なソフトウェアなどの短所を有する。このようなアーキテクチャは、迅速なパターンマッチングを必要としたり、あるいは埋め込みアプリケーションの低電力かつ携帯性の要求を満足する必要があるアプリケーションには適していない。
【０００４】
他のパターンマッチングアーキテクチャでは、各メモリセルの埋め込みハードウェア比較器を備えるＣＭＡ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）を用いて、それのメモリ位置のコンテンツと入力データの対応するビットを埋め込み比較器の比較機能により比較する。このアーキテクチャは、高速かつ比較的コンパクトであるという利点を有する（ハードウェアによる実現のため）。しかしながら、１）利用可能な比較アルゴリズムのタイプ及び複雑さに関する制約、２）比較的大きな電力消費、３）メモリセルレベルにおけるかなり複雑な構成、及び４）多数の基準テンプレートに対しスケーラブルでない、などのいくつかの短所を有する。各メモリセルに対してハードウェア比較器を実現することは、高コスト化を招くと共に、より複雑な比較基準を不可能にし、複数の比較基準を実現するフレキシビリティを制限する。例えば、そのようなパターン認識アーキテクチャは、典型的には、保持されている基準テンプレートの何れが入力データのすべてのビットに一致しているか判断するための正確なビット一致比較を有するだけであろう。より複雑な比較基準は複雑かつ／または高価なものであるため、このアーキテクチャには利用することはできない。
【０００５】
上述したようなアーキテクチャは一部のパターン認識アプリケーションには適しているが、他のアプリケーションでは高速な、複数の比較アルゴリズム（より複雑なアルゴリズムを含む）からの選択を与え、比較的電力消費の小さいパターンマッチングアーキテクチャが必要とされる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明の課題は、上記問題点に鑑み、基準テンプレートまたはパターンとデータとの迅速であり、複数のアルゴリズムを選択可能な低消費電力を実現するパターンマッチングアーキテクチャを提供することである。
【課題を解決するための手段】
【０００７】
上記課題を解決するため、本発明は、入力データをビット数がプログラム可能な入力ビットフィールドに分割し、１以上の基準テンプレートをビット数がプログラム可能な対応する基準ビットフィールドに分割する選択ユニットと、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の１以上の距離を決定し、前記基準ビットフィールドに係る１以上の距離を前記基準テンプレートに対応する１以上のネットの距離に合成する距離ユニットとから構成されることを特徴とする装置を提供する。
【０００８】
また本発明は、プログラム可能なビットフィールド幅に従って、入力データを入力ビットフィールドに分割するステップと、前記ビットフィールド幅に従って、１以上の基準テンプレートを前記入力ビットフィールドに対応する基準ビットフィールドに分割するステップと、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の距離を決定するステップと、前記基準ビットフィールドに係る距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するステップとから構成されることを特徴とする方法を提供する。
【０００９】
また本発明は、プロセッサによる実行のための命令を格納するよう接続されるダイナミックランダムアクセスシステムメモリと、プロセッサリクエストに応答して、入力データと基準テンプレート群との間の距離群を決定し、１以上の分類基準に従って、前記入力データにベストマッチする基準テンプレートを特定するパターンマッチングユニットと、
から構成されるシステムであって、前記パターンマッチングユニットは、選択ユニットと距離ユニットを有し、前記選択ユニットは、入力データをビット数がプログラム可能な入力ビットフィールドに分割し、１以上の基準テンプレートをビット数がプログラム可能な対応する基準ビットフィールドに分割し、前記距離ユニットは、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の１以上の距離を決定し、前記基準ビットフィールドに係る１以上の距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するよう構成されることを特徴とするシステムを提供する。
【００１０】
さらに本発明は、実行される場合にシステムが、プログラム可能なビットフィールド幅に従って、入力データを入力ビットフィールドに分割するステップと、前記ビットフィールド幅に従って、１以上の基準テンプレートを前記入力ビットフィールドに対応する基準ビットフィールドに分割するステップと、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の距離を決定するステップと、前記基準ビットフィールドに係る距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するステップとを実行することを可能にする命令を含むマシーンアクセス可能な媒体から構成される物品を提供する。
【発明の効果】
【００１１】
本発明によると、基準テンプレートまたはパターンとデータとの迅速であり、複数のアルゴリズムを選択可能な低消費電力を実現するパターンマッチングアーキテクチャを提供することが可能となる。
【発明を実施するための最良の形態】
【００１２】
パターンマッチングアーキテクチャのための方法、装置及びシステムが説明される。以下の説明では、本発明の様々な実施例を完全に理解するため、多数の具体的詳細が与えられる。しかしながら、本発明の実施例はこれらの具体的詳細なしに実現可能であるということは当業者には明らかであろう。また、本発明の実施例を不明瞭にすることを回避するため、一部の構成及び装置はブロック図により図示される。
【００１３】
明細書における「一実施例」あるいは「実施例」との表現は、当該実施例に関連して説明された特徴または構成が本発明の少なくとも１つの実施例に含まれるということを意味する。明細書のいくつかの場所に見受けられる「一実施例では」との表現は、必ずしもすべてが同一の実施例を参照するものでない。
【００１４】
パターンマッチングアプリケーションの例として、認証（顔、声、指紋、署名及び虹彩によるマッチングなど）、在庫管理（バーコードや無線周波数による識別など）、通信（発話、音声、画像認識及び比較、ヘッダ構文解析など）、及び工業用制御（部品検査や予知保全など）があげられる。
【００１５】
このようなアプリケーションからの入力データは、１以上の比較アルゴリズムに従って基準パターンまたはテンプレート群と比較され、リアルタイムデータと基準テンプレートとの各種距離測度が生成されるかもしれない。距離測度は、距離の公式やアルゴリズムに従って２つのデータ間の相違を定量化したものである。例えば、距離測度は、ビットイグザクトマッチ（ｂｉｔ ｅｘａｃｔ ｍａｔｃｈ）、ハミング距離、ユークリッド距離、ミーンアグニチュード（ｍｅａｎ ｍａｇｎｉｔｕｄｅ）距離及び相関距離などがある。いくつかの距離測度は、一部のアプリケーションには利用可能であるが、他のアプリケーションには利用可能でない。アプリケーションには、複数タイプの距離測度が利用可能なものもある。従って、１以上の距離測度の選択能力が、実現されるようにしてもよい。
【００１６】
一部のアプリケーションでは、距離測度が生成された後、当該距離測度にはさらなる処理または分類が行われ、選択された集合の中のどの基準テンプレートが入力データと最も良く比較するか、１以上の分類基準に従って判断される。例えば、どの基準テンプレートが与えられた入力データに対するベストマッチ、ワーストマッチ、ミーン（ｍｅａｎ）マッチ、及び／またはメディアン（ｍｅｄｉａｎ）マッチであるか判断されてもよい。これらの「マッチ」に基づき行われる判定タイプはアプリケーションに応じて可変とされ、選択可能な距離測度の分類を提供するパターンマッチングアーキテクチャが実現されてもよい。
【００１７】
図１を参照するに、本発明の一実施例によるパターンマッチングユニット１００のブロック図が示される。パターンマッチングユニット１００は、生成される１以上の距離測度（例えば、ビットイグザクトマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び／または相関距離など）を選択する機能を備えてもよいし、また選択された１以上の分類基準（例えば、ベストマッチ、ワーストマッチ、ミーンマッチ及び／またはメディアンマッチ）に従って距離測度を分類する機能を備えてもよいし、入力データと基準テンプレート群とをマッチングさせ、ユーザの選択に基づきマッチしたテンプレートのインデックスを提供する論理及び算術比較機構を有する検索テーブル機構を有するようにしてもよい。
【００１８】
一実施例では、パターンマッチングユニット１００は、オンチップメモリを用いてホストバスを占有することなく高速アクセス可能な大量の基準テンプレート群を格納するように、記憶装置の内部に一体化されてもよい。一実施例では、パターンマッチングユニット１００は、パターンマッチングアクセラレータとしてプロセッサに埋め込まれてもよい。一実施例では、埋め込みパターンマッチングユニット１００は、高速、フレキシブルかつ複雑なデータ比較及び分類を提供するため、プロセッサが他のタスクを実行するのを可能にしながら、プロセッサの比較命令に変換されてもよい。このようなプロセッサは、パターン認識、分岐予測、知的キャッシュ処理、適応的マッチフィルタリング及び命令レベル暗号化などの各種アプリケーションに対して、埋め込みパターンマッチングユニット１００を効果的に利用するようにしてもよい。
【００１９】
さらに図１を参照するに、入力バッファ１０６は、入力１０２を介し入力データを受信し、フレキシブル比較分類ユニット１０８による以降の処理のため、この入力データを格納するようにしてもよい。一実施例では、入力バッファ１０６は、フレキシブル比較分類ユニット１０８による処理のため以前の入力データが抽出されるに従って、新たな入力データの非同期ロード処理を可能にするようデュアルポートまたはダブルバッファ処理される。
【００２０】
テンプレートメモリ１０４は、入力１０２から基準パターンやテンプレートを受信し、フレキシブル比較分類ユニット１０８による以降の処理のため、これらの基準テンプレートを格納するのに利用されてもよい。一実施例では、テンプレートメモリ１０４は、基準テンプレートが同時にロード及びアクセスされるのを可能にするようデュアルポートまたはダブルバッファ処理されてもよい。様々な実施例では、テンプレートメモリ１０４は、対象となるアプリケーションのメモリサイズ、パワー、スピード、不揮発性などの各要求に一致するよう各種メモリ技術に基づくものであってもよい。例えば、テンプレートメモリ１０４は、ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ Ｐｒｏｇｒａｍｍａｂｌｅ Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）、フラッシュメモリあるいはＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ Ｅｒａｓａｂｌｅ Ｐｒｏｇｒａｍｍａｂｌｅ Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）などの半導体装置により実現されてもよい。
【００２１】
さらに図１を参照するに、入力バッファ１０６とテンプレートメモリ１０４からのデータまたはベクトルが、フレキシブル比較分類ユニット１０８の入力に与えられる。図２に関してより詳細に後述するように、フレキシブル比較分類ユニット１０８は、各データ幅を比較及び分類し、入力データと基準テンプレートを比較及び分類用のサブフィールドまたは次元に分割またはスライスし、各種比較を行うことにより入力データと基準テンプレートとの間の各種距離測度（例えば、ビットイグザクトマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び／または相関距離など）を生成し、入力データの各次元に対する距離測度を総計または合成することによりネットの距離測度を生成し、選択された１以上の基準（例えば、ベストマッチ、ワーストマッチ、ミーンマッチ及び／またはメディアンマッチ）に従ってネットの距離測度を分類する。フレキシブル比較分類ユニット１０８はまた、特定されたマッチと境界状態に基づき１以上の決定を行う機構を有するようにし、１以上の決定フラグ１２４を介しこれらの決定を示すようにしてもよい。フレキシブル比較分類ユニット１０８はまた、比較のための多数の基準テンプレートまたはベクトル次元を収容するため、複数のパターンマッチングユニット１０８のカスケード処理を可能にするカスケードＰＭＵ入力１１２を有するようにしてもよい。フレキシブル比較分類ユニット１０８の一実施例のさらなる詳細は、図２に関連して後述される。
【００２２】
さらに図１を参照するに、出力バッファ１１６が、フレキシブル比較分類ユニット１０８からの出力１２６を格納し、バッファされた結果１１８をマルチプレクサ１２０に与えるようにしてもよい。フレキシブル比較分類ユニット１０８からの出力１２６には、特定された基準テンプレートマッチのインデックス値、マッチした基準テンプレート、関連するネットの距離測度及び／または他の関連するマッチデータが含まれてもよい。一実施例では、出力バッファ１１６は、ＦＩＦＯ（Ｆｉｒｓｔ−Ｉｎ−Ｆｉｒｓｔ−Ｏｕｔ）スタックである。一実施例では、マルチプレクサ１２０は、出力バッファ１１６からバッファされた結果１１８を受信すると共に、フレキシブル比較分類ユニット１０８から直接的に出力１２６を受信する。１つのモード（例えば、スタンドアローンＰＭＵモード）では、マルチプレクサ１２０は、バッファされた結果１１８を最終的なＰＭＵ出力１２２に提供してもよい。他のモード（例えば、カスケードＰＭＵモード）では、マルチプレクサ１２０は、フレキシブル比較分類ユニット１０８の出力を最終的なＰＭＵ出力１２２に直接的に与えるようにしてもよい。この最終的なＰＭＵ出力１２２は、フレキシブル比較分類ユニット１０８の最終的な比較／分類出力としてホストシステムまたは他の装置に与えられるようにしてもよい。
【００２３】
一実施例では、出力バッファ１１６は、ホストシステムに状態情報を提供するため、適切なフラグ（例えば、アンダーフロー、オーバーフロー、ハーフフルなど）を生成するよう制御ユニット１１０と共に動作するようにしてもよい。このようなフラグは、ホストシステムがフラグを定期的に集計し、選択された個数の入力ベクトルが比較及び分類された後に応答するのを可能にするかもしれない。このようにして、ホストシステムは、パターンマッチングユニット１００が入力ベクトル群を比較及び分類しながら、他のタスクを実行するようにしてもよい。
【００２４】
さらに図１を参照するに、制御ユニット１１０は、パターンマッチングユニット１００の各種設定オプションを提供するようにしてもよい。例えば、制御ユニット１１０は、データサイズ／幅、入力データ及び基準テンプレートが分割されるベクトル次元数及び幅、各比較において生成される１以上の距離測度の選択、利用される１以上の分類基準の選択、及びカスケードモードなどの各種パターンマッチングモードの選択を制御するかもしれない。制御ユニット１１０はまた、パターンマッチングユニット１００の各種ユニット間のデータ処理及び転送のシーケンス処理を制御するようにしてもよい。制御ユニット１１０はまた、パターンマッチングユニット１００とやりとりするため、ホストシステムや他の装置のための外部インタフェースを提供するようにしてもよい。一実施例では、外部インタフェースは、メモリ変換インタフェースである。一実施例では、外部インタフェースは、入出力（Ｉ／Ｏ）変換インタフェースである。制御ユニット１１０の一実施例のさらなる詳細は、図３に関連して後述される。
【００２５】
図２を参照するに、本発明の一実施例による図１のフレキシブル比較分類ユニットのより詳細なブロック図が示される。ビットフィールド選択ユニット２０６は、入力バッファ１０６とテンプレートメモリ１０４からそれぞれ入力データ２０４と基準テンプレート２０２の各サイズまたはビット幅を処理するよう構成されてもよい。入力データ２０４と基準テンプレート２０２は、様々な次元またはサブフィールドを有するデータあるいはベクトルを表すものであってもよい。ビットフィールド選択ユニット２０６は、入力データ２０４と基準テンプレート２０２を様々な次元のベクトルを表す設定可能なサイズの１以上のビットフィールドにスライスまたは分割するよう構成されてもよい。例えば、入力データ２０４と基準テンプレート２０２は、赤、緑、青とカラー表示画素データの強度の４つの次元から構成される３２ビットベクトルとすることも可能である。この場合、ビットフィールド選択ユニット２０６は、３２ビットデータ幅を扱い、３２ビット入力データ２０４と３２ビット基準テンプレート２０２を、以下のベクトル次元を表す４つの８ビットシャンクまたはビットフィールド、すなわち、８ビットの赤（Ｒ）、８ビットの緑（Ｇ）、８ビットの青（Ｂ）及び８ビットの強度（Ｉ）に分割またはスライスするよう構成することが可能である。
【００２６】
さらに図２を参照するに、比較ユニット２０８は、入力データ２０４の各ビットフィールドまたは次元と基準テンプレート２０２の対応するビットフィールドまたは次元を１以上の比較アルゴリズムに従って比較し、設定に応じて１以上の距離測度を生成するようにしてもよい。一実施例では、比較ユニット２０８は、各次元の距離測度と内部レジスタから抽出されるかもしれない対応する加重係数と乗算してもよい。例えば、あるカラーベクトルマッチングアプリケーションは、赤と輝度が青と緑より重要な比較次元であると判断するかもしれない。この場合、０．９０、０．３０、０．４０及び０．９５の加重係数が、赤、緑、青と輝度次元にそれぞれ利用することができる。一実施例では、比較ユニット２０８は、ビットフィールドまたは次元のすべてからの距離測度を合計または合成し（設定に応じて加重係数を適用することにより）、入力データ２０４と基準テンプレート２０４との間のネットの距離測度を生成する。
【００２７】
対象とするアプリケーションに応じて、本発明の一実施例は、１以上の比較アルゴリズムを利用して１以上の距離測度を生成するよう構成されてもよい。いくつかの有用な距離測度として、ビットイグザクトマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び／または相関距離などがある。これらの距離測度が簡単に説明される。ビットイグザクト比較では、２つのデータの対応する各ビットを比較することにより、比較対象の２つのデータ間の正確なビット単位による一致があるか判断される。例えば、入力ベクトル「０１０１１１０１」は、基準テンプレート「０１０１１１０１」のビットイグザクトマッチであるが、基準テンプレート「０１０１１１００」のビットイグザクトマッチではない。ハミング距離測度は、一致する対応するビットの総数をトータルのビット幅により除することにより決定される（一致ビット数／トータルビット幅）。例えば、入力ベクトル「１０１１０１１０１０１０」と基準テンプレート「０１０１１１０１０１１１」との間のハミング距離は、３／１２、すなわち、０．２５である（右から２番目、７番目及び９番目がビットマッチに対応し、データビット幅が１２ビットであるため）。ユークリッド距離は、１次元ベクトルには（Ｘ−Ｙ）２を用いて、ｎ次元ベクトルまたはサブフィールドＸ１．．．ＸｎとＹ１．．．Ｙｎには
【００２８】
【数１】
を用いて計算することができる。ミーンマグニチュード距離は、１次元ベクトルには｜Ｘ−Ｙ｜を用いて、ｎ次元ベクトルまたはサブフィールドＸ１．．．ＸｎとＹ１．．．Ｙｎには
【００２９】
【数２】
を用いて計算することができる。相関距離は、１次元ベクトルにはＸ・Ｙを用いて、ｎ次元ベクトルまたはサブフィールドＸ１．．．ＸｎとＹ１．．．Ｙｎには
【００３０】
【数３】
を用いて計算することができる。
【００３１】
さらに図２を参照するに、比較ユニット２０８は、各入力データ２０４と複数の基準テンプレート２０２を比較し、各入力データに関するネットの距離測度を分類ユニット２１０に提供する。分類ユニット２１０は、選択された１以上の分類基準に従って入力データ２０４にマッチする基準テンプレート２０２を特定するよう構成されてもよい。例えば、分類ユニット２１０は、基準テンプレートの何れが、各入力データに対するベストマッチ、ワーストマッチ、ミーンマッチ及び／またはメディアンマッチであるか判断するよう構成されてもよい。ベストマッチは、与えられた分類基準に従って入力データ２０４と比較して最も好ましいネット距離測度を有する基準テンプレートである。ワーストマッチは、与えられた分類基準に従って入力データ２０４に最もふさわしくないネット距離測度を有する基準テンプレートである。ミーンマッチは、ネット距離測度の平均に最も近いネット距離測度を有する基準テンプレートである。メディアンマッチは、ネット距離測度の中央値に最も近いネット距離測度を有する基準テンプレートである。一実施例では、フレキシブル比較分類ユニット１０８は、基準テンプレートのインデックス値と、特定されたマッチに対応するネット距離測度を記録するようにしてもよい。
【００３２】
さらに図２を参照するに、一実施例では、フレキシブル比較分類ユニット１０８は、カスケード構成されたパターンマッチングユニットから選択されたマッチを分類する深さ拡張ユニット２１２を有するようにしてもよい。例えば、（図１の）複数のパターンマッチングユニット１００が、スピードを向上させるため（例えば、与えられた入力データをパラレルに処理する複数のユニットなど）、あるいは比較に利用可能な基準テンプレートの個数を増やすためカスケード構成されてもよい。深さ拡張モードが選択されると、深さ拡張ユニット２１２は、それの分類されたマッチとカスケードＰＭＵ入力２１４上に与えられる他のパターンマッチングユニットの何れかと比較し、複数のパターンマッチングユニット１００の選択されたマッチから最良の全体的なマッチを決定する。深さ拡張モードが選択されていないときには、深さ拡張ユニット２１２は、それの入力をそれの出力２１８に単にコピーするようにしてもよい。カスケード化されたパターンマッチングアーキテクチャの一実施例のさらなる詳細が、図４に関連して後述される。
【００３３】
さらに図２を参照するに、一実施例では、フレキシブル比較分類ユニット１０８はまた、判定ユニット２２０を有するようにしてもよい。判定ユニット２２０は、深さ拡張ユニット２１２から出力２１８（特定されたマッチと関連する距離測度を含む）を受け取り、判定基準または閾値を示す１以上の境界基準２２２を受信するようにしてもよい。判定ユニット２２０は、出力２１８と境界基準２２２を比較し、この比較に基づきパターンマッチングユニット１００による様々な判定を示す１以上の判定フラグを生成するようにしてもよい。例えば、指紋マッチングアプリケーションでは、判定ユニット２００は、最も近いネットのユークリッド距離測度の値が所定値未満である場合、「指紋マッチ」フラグをアサートするよう構成されるかもしれない。一実施例では、判定ユニット２２０は、埋め込みアプリケーションにおけるスタンドアローンによる利用のためのパターンマッチングユニット１００において利用されてもよい。各種制御入力２１６がまた、フレキシブル比較分類ユニット１０８のタイミング、シーケンス処理及び全体機能を制御するのに提供されてもよい。
【００３４】
図３を参照するに、本発明の一実施例による図１の制御ユニット１１０のブロック図が示される。外部インタフェース３０８は、ホストシステムまたは他の装置がアドレス信号３０２、データ信号３０４及びリード／ライト信号３０６を介しパターンマッチングユニット１００とやりとりするのを可能にする。外部インタフェース３０８を利用して、ホスト装置またはシステムは、テンプレートをテンプレートメモリ１０４に格納し、データを入力バッファ１０６にロードし、出力バッファ１１６から結果を読取ることが可能である。アドレス入力３０２とデータ入力３０４を介しホストにより与えられるアドレス及びデータ情報のパターンマッチングユニット１００の内部の通信は、内部アドレスバス３１０と内部データバス３１２を介し実行されるかもしれない。
【００３５】
一実施例では、制御ユニット１１０は、ホストシステムのメモリスペースの４つの場所を利用するパターンマッチングユニット１００に対するメモリ変換インタフェースを提供するかもしれない。テーブル１に変換例が示される。
【００３６】
【表１】
【００３７】
一実施例では、制御レジスタ３１４は、ａ）テンプレートメモリ１０４のテンプレートの開始アドレス、ｂ）比較されるテンプレートの個数、ｃ）次元ごとのビットフィールド幅、ｄ）ベクトルごとのベクトル次元数、ｅ）深さ拡張オン／オフ、及びｆ）距離測度の選択を含むようにしてもよい。一実施例では、制御ユニット１１０は、各種フラグ（例えば、実行済み／未実行、カスケードモード、メモリチェックなど）を含む状態レジスタ３１６を有するようにしてもよい。一実施例では、制御ユニット１１０は、各種デバッグ動作を提供するデバッグレジスタ３１８を有するようにしてもよい。
【００３８】
さらに図３を参照するに、設定タイミングデコーダ３２０は、設定情報３２６をパターンマッチングユニット１００に提供する。シーケンサ３２２は、パターンマッチングユニット１００の各種機能ブロックのタイミング及び動作を制御する制御信号３２４を与える。
【００３９】
図４を参照するに、本発明の一実施例によるカスケード構成されたパターンマッチングアーキテクチャ４００のブロック図が示される。図４は、（図１の）複数のパターンマッチングユニット１００が、スピードを向上させ（例えば、パラレルに１以上の入力データを処理する複数のユニットなど）、及び／または比較のため利用可能な基準テンプレートの個数を増やすためどのようにカスケード構成することが可能であるか示す。入力データは、入力１０２（ａ）、１０２（ｂ）及び１０２（ｃ）を介しパターンマッチングユニット１００（ａ）、１００（ｂ）及び１００（ｃ）にそれぞれ与えられる。パターンマッチングユニット１００（ａ）、１００（ｂ）及び１００（ｃ）は、パターンマッチングユニット１００（ａ）の最終的なＰＭＵ出力１２２（ａ）をパターンマッチングユニット１００（ｂ）のカスケードＰＭＵ入力１２２（ｂ）に接続すると共に、パターンマッチングユニット１００（ｂ）の最終的なＰＭＵ出力１２２（ｂ）をパターンマッチングユニット１００（ｃ）のカスケードＰＭＵ入力１１２（ｃ）に接続することにより、カスケードモードで接続されてもよい。本実施例では、パターンマッチングユニット１００（ａ）、１００（ｂ）及び１００（ｃ）の各々の深さ拡張ユニット２１２は、複数のパターンマッチングユニット１００により比較及び分類された最良の全体的マッチを決定するよう動作し、最終的なＰＭＵ出力１２２（ｃ）に最良の全体的マッチデータを提供する。一実施例では、カスケードアーキテクチャは、多数の基準テンプレートの比較を可能にするよう利用されてもよい。例えば、同じ入力データが、複数のカスケード接続されたパターンパッチングユニットに保持されている異なる基準テンプレートセットとパラレルに比較することが可能である。一実施例では、同一の基準テンプレートセットが、入力データ群を比較及び分類するスピードを向上させるため、カスケード接続されたパターンマッチングユニットに格納することが可能である。
【００４０】
実施例は、論理回路、状態マシーン、マイクロコードあるいはこれらの組み合わせにより実現されてもよい。実施例はコードにより実現されてもよく、命令を実行するようコンピュータシステムをプログラムするのに用いることが可能な命令を格納した記憶媒体に格納されてもよい。この記憶媒体は、以下に限定するものではないが、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｋ Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＣＤ−ＲＷ（Ｃｏｍｐａｃｔ Ｄｉｓｋ Ｒｅｗｒｉｔａｂｌｅ）、光磁気ディスクを含む任意のタイプのディスク、ＲＯＭ、ＲＡＭ、ＤＲＡＭ、ＥＰＲＯＭ、フラッシュメモリ、ＥＥＰＲＯＭなどの半導体装置、磁気または光カード、ネットワーク記憶装置、あるいは電子命令を格納するのに適した任意のタイプの媒体を含むものであってもよい。
【００４１】
実施例は、ハードウェア装置の適切な組み合わせにより構成された適切なコンピュータシステムによる実行のためのソフトウェアにより実現されてもよい。
【００４２】
図５を参照するに、本発明の実施例が利用可能なコンピュータシステム５００のブロック図が示される。一実施例では、コンピュータシステム５００は、マイクロプロセッサ、マイクロコントローラ、プログラマブルゲートアレイ（ＰＧＡ）などの汎用または特定用途向けプロセッサを有するプロセッサ５１０を備える。ここで用いられる「コンピュータシステム」という用語は、デスクトップコンピュータ、サーバコンピュータ、ラップトップコンピュータなどの任意のタイプのプロセッサベースシステム、あるいは他のタイプのホストシステムを表すかもしれない。
【００４３】
プロセッサ５１０は、一実施例では、メモリバス５２５を介しシステムメモリ５２０（ＤＲＡＭなど）に接続されるメモリハブ５３０にホストバス５１５を介し接続されてもよい。メモリハブ５３０はまた、ディスプレイ５３７に接続されるビデオコントローラ５３５にＡＧＰ（Ａｄｖａｎｃｅｄ Ｇｒａｐｈｉｃｓ Ｐｏｒｔ）を介し接続されてもよい。ＡＧＰバス５３３は、カリフォルニア州サンタクララのインテルコーポレイションにより１９９８年５月４日に刊行されたＡｃｃｅｌｅｒａｔｅｄ Ｇｒａｐｈｉｃｓ Ｐｏｒｔ Ｉｎｔｅｒｆａｃｅ 仕様書に準拠していてもよい。
【００４４】
（図１の）パターンマッチングユニット１００は、メモリバス５２５を介しメモリハブ５３０に接続されてもよい。本実施例では、パターンマッチングユニット１００は、メモリ変換装置であってもよい。他の実施例では、パターンマッチングユニット１００は、入出力（Ｉ／Ｏ）変換装置であってもよい。一実施例では、パターンマッチングユニット１００は、パターンマッチングアクセラレータとしてプロセッサ５１０に埋め込まれてもよい。一実施例では、埋め込みパターンマッチングユニット１００は、プロセッサ５１０が他のタスクを実行するのを可能としながら、高速、フレキシブルかつ複雑なデータ比較及び分類を提供するためプロセッサ５１０の比較命令に変換されるようにしてもよい。プロセッサ５１０は、パターン認識、分岐予測、知的キャッシュ処理、適応的マッチフィルタリング、命令レベル暗号化などの各種アプリケーションに対して、パターンマッチングユニット１００を効果的に利用するかもしれない。
【００４５】
メモリハブ５３０は、１９９５年６月のＰＣＩローカルバス仕様書、プロダクツバージョン改訂２．１により規定されるようなＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ）バス５４４と入出力（Ｉ／Ｏ）拡張バス５４２に接続される入出力（Ｉ／Ｏ）ハブ５４０に接続されてもよい（ハブリンク５３８を介し）。このＩ／Ｏ拡張バス５４２は、１以上のＩ／Ｏ装置へのアクセスを制御するＩ／Ｏコントローラ５４６に接続されてもよい。図５に示されるように、一実施例では、これらの装置には、フロッピー（登録商標）ディスクドライブ５５０などの記憶装置と、キーボード５５２やマウス５５４などの入力装置が含まれてもよい。Ｉ／Ｏハブ５４０はまた、図５に示されるように、ハードディスクドライブ５５６とＣＤドライブ５５８に接続されてもよい。他の記憶装置が本システムに設けられてもよいということは理解されるべきである。
【００４６】
ＰＣＩバス５４４はまた、例えば、ネットワークポート（図示せず）に接続されるネットワークコントローラ５６０を含む各種コンポーネントに接続されてもよい。パラレルポート、シリアルポート、不揮発性メモリなどのさらなる装置が、Ｉ／Ｏ拡張バス５４２とＰＣＩバス５４４に接続されてもよい。
【００４７】
上記説明はシステム５００の具体的コンポーネントを参照したが、説明及び図示された実施例の多数の改良及び変形が可能であるということが考えられる。また、図５はパーソナルコンピュータなどのシステムのブロック図を示しているが、本発明の実施例は特殊なパターン認識装置、携帯情報端末（ＰＤＡ）などにより実現されてもよいということは理解されるべきである。
【００４８】
図６を参照するに、本発明の一実施例によるパターンマッチング方法を示すフロー図が示される。設定オプションは、入力データと基準テンプレートまたはパターンの比較に利用される比較アルゴリズムや１以上の距離測度の選択を可能にするものであってもよく、選択された１以上の基準に従い与えられた入力データにベストマッチする１以上の基準テンプレートを特定するのに利用可能な１以上の分類基準の選択を可能にするものであってもよい（ブロック６０２）。設定オプションは、入力データと基準テンプレートの次元のサイズやビット幅の選択を可能にするものであってもよく、各入力データと基準テンプレートの次元数及び／またはサイズの選択を可能にするものであってもよい（ブロック６０４）。一実施例では、設定オプションは、入力データと基準テンプレートの全体的なビット幅と各入力データと基準テンプレートの次元数の選択を提供するものであってもよい。
【００４９】
設定オプションが設定された後、パターンマッチングプロセスは、比較及び分類対象の入力データをフェッチすることにより進められる（ブロック６０６）。入力データが比較される基準テンプレートもまたフェッチされる（ブロック６０８）。複数の次元を有するデータの比較においてフレキシビリティを提供するため、入力データと基準テンプレートの各々は、設定オプションに従って複数の時限またはビットフィールドに分割され（ブロック６１０）、入力データと基準テンプレートの対応する各次元に対し距離測度が決定されるのを可能にするようにしてもよい（ブロック６１２）。各次元の距離測度が決定されると、１以上の加重係数が１以上の次元に関連する距離測度に適用されてもよい（ブロック６１４）。その後、これらの距離測度は、当該入力データと基準テンプレートのネット距離測度に合計または合成されてもよい（ブロック６１６）。ブロック６０８〜６１６は、与えられた基準データが選択された基準テンプレートのすべてと比較されるまで繰り返されるようにしてもよい（ブロック６１８）。この入力データがすべての基準テンプレートと比較されると、どの距離測度（及び対応する基準テンプレート）が入力データにベストマッチするか判断するため、選択された分類基準に従って分類されるようにしてもよい（ブロック６２０）。一実施例では、ブロック６２０において特定されたマッチは、１以上の境界基準と比較され、この比較に基づき１以上の判定がなされるようにしてもよい（ブロック６２２）。
【００５０】
以上のように、パターンマッチングアーキテクチャのための方法、装置及びシステムが説明された。本発明は限られた実施例に関して説明されたが、本開示により、当業者は多数の改良及び変形を理解するであろう。添付された請求項は、このようなあらゆる改良及び変形を本発明の真の趣旨及び範囲に属するものとしてカバーしようとするものである。
【図面の簡単な説明】
【００５１】
【図１】図１は、本発明の一実施例によるパターンマッチングユニットのブロック図である。
【図２】図２は、本発明の一実施例による図１のフレキシブル比較分類ユニットのブロック図である。
【図３】図３は、本発明の一実施例による図１の制御ユニットのブロック図である。
【図４】図４は、本発明の一実施例によるカスケード構成されたパターンマッチングアーキテクチャのブロック図である。
【図５】図５は、本発明の実施例が利用可能なコンピュータシステムのブロック図である。
【図６】図６は、本発明の一実施例によるパターンマッチング方法を示すフロー図である。
【符号の説明】
【００５２】
１００ パターンマッチングユニット
１０４ テンプレートメモリ
１０６ 入力バッファ
１０８ フレキシブル比較分類ユニット
１１０ 制御ユニット
１１６ 出力バッファ
１２０ マルチプレクサ
２０６ ビットフィールド選択ユニット
２０８ 比較ユニット
２１０ 分類ユニット
２１２ 深さ拡張ユニット
２２０ 判定ユニット
３０８ 外部インタフェース
３１４ 制御レジスタ
３１６ 状態レジスタ
３１８ デバッグレジスタ
３２０ 設定タイミングデコーダ
３２２ シーケンサ
【技術分野】
【０００１】
本発明は、一般にパターン認識に関し、より詳細には、基準テンプレートまたはパターンとデータとの迅速なマッチング処理に関する。
【背景技術】
【０００２】
一般的なパターンマッチングプロセスでは、基準テンプレートが入力データと比較され、どの基準テンプレートが入力データと最も良く一致するか判断される。
【０００３】
１つのパターンマッチングアーキテクチャは、パターン認識ソフトウェアを実行する汎用コンピュータである。このアーキテクチャは以下の利点を有する。ａ）このアーキテクチャは、ソフトウェアにより実現により各種パターン比較アルゴリズムを搭載することができる。ｂ）典型的には、基準テンプレートの個数が通常はコンピュータシステムメモリの容量のみの制約しか受けないため、多数の基準テンプレートを利用することが可能である。しかしながら、このアーキテクチャは、低速なパフォーマンス、大きな電力消費、多数のアプリケーション、高価で複雑なソフトウェアなどの短所を有する。このようなアーキテクチャは、迅速なパターンマッチングを必要としたり、あるいは埋め込みアプリケーションの低電力かつ携帯性の要求を満足する必要があるアプリケーションには適していない。
【０００４】
他のパターンマッチングアーキテクチャでは、各メモリセルの埋め込みハードウェア比較器を備えるＣＭＡ（Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）を用いて、それのメモリ位置のコンテンツと入力データの対応するビットを埋め込み比較器の比較機能により比較する。このアーキテクチャは、高速かつ比較的コンパクトであるという利点を有する（ハードウェアによる実現のため）。しかしながら、１）利用可能な比較アルゴリズムのタイプ及び複雑さに関する制約、２）比較的大きな電力消費、３）メモリセルレベルにおけるかなり複雑な構成、及び４）多数の基準テンプレートに対しスケーラブルでない、などのいくつかの短所を有する。各メモリセルに対してハードウェア比較器を実現することは、高コスト化を招くと共に、より複雑な比較基準を不可能にし、複数の比較基準を実現するフレキシビリティを制限する。例えば、そのようなパターン認識アーキテクチャは、典型的には、保持されている基準テンプレートの何れが入力データのすべてのビットに一致しているか判断するための正確なビット一致比較を有するだけであろう。より複雑な比較基準は複雑かつ／または高価なものであるため、このアーキテクチャには利用することはできない。
【０００５】
上述したようなアーキテクチャは一部のパターン認識アプリケーションには適しているが、他のアプリケーションでは高速な、複数の比較アルゴリズム（より複雑なアルゴリズムを含む）からの選択を与え、比較的電力消費の小さいパターンマッチングアーキテクチャが必要とされる。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明の課題は、上記問題点に鑑み、基準テンプレートまたはパターンとデータとの迅速であり、複数のアルゴリズムを選択可能な低消費電力を実現するパターンマッチングアーキテクチャを提供することである。
【課題を解決するための手段】
【０００７】
上記課題を解決するため、本発明は、入力データをビット数がプログラム可能な入力ビットフィールドに分割し、１以上の基準テンプレートをビット数がプログラム可能な対応する基準ビットフィールドに分割する選択ユニットと、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の１以上の距離を決定し、前記基準ビットフィールドに係る１以上の距離を前記基準テンプレートに対応する１以上のネットの距離に合成する距離ユニットとから構成されることを特徴とする装置を提供する。
【０００８】
また本発明は、プログラム可能なビットフィールド幅に従って、入力データを入力ビットフィールドに分割するステップと、前記ビットフィールド幅に従って、１以上の基準テンプレートを前記入力ビットフィールドに対応する基準ビットフィールドに分割するステップと、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の距離を決定するステップと、前記基準ビットフィールドに係る距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するステップとから構成されることを特徴とする方法を提供する。
【０００９】
また本発明は、プロセッサによる実行のための命令を格納するよう接続されるダイナミックランダムアクセスシステムメモリと、プロセッサリクエストに応答して、入力データと基準テンプレート群との間の距離群を決定し、１以上の分類基準に従って、前記入力データにベストマッチする基準テンプレートを特定するパターンマッチングユニットと、
から構成されるシステムであって、前記パターンマッチングユニットは、選択ユニットと距離ユニットを有し、前記選択ユニットは、入力データをビット数がプログラム可能な入力ビットフィールドに分割し、１以上の基準テンプレートをビット数がプログラム可能な対応する基準ビットフィールドに分割し、前記距離ユニットは、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の１以上の距離を決定し、前記基準ビットフィールドに係る１以上の距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するよう構成されることを特徴とするシステムを提供する。
【００１０】
さらに本発明は、実行される場合にシステムが、プログラム可能なビットフィールド幅に従って、入力データを入力ビットフィールドに分割するステップと、前記ビットフィールド幅に従って、１以上の基準テンプレートを前記入力ビットフィールドに対応する基準ビットフィールドに分割するステップと、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の距離を決定するステップと、前記基準ビットフィールドに係る距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するステップとを実行することを可能にする命令を含むマシーンアクセス可能な媒体から構成される物品を提供する。
【発明の効果】
【００１１】
本発明によると、基準テンプレートまたはパターンとデータとの迅速であり、複数のアルゴリズムを選択可能な低消費電力を実現するパターンマッチングアーキテクチャを提供することが可能となる。
【発明を実施するための最良の形態】
【００１２】
パターンマッチングアーキテクチャのための方法、装置及びシステムが説明される。以下の説明では、本発明の様々な実施例を完全に理解するため、多数の具体的詳細が与えられる。しかしながら、本発明の実施例はこれらの具体的詳細なしに実現可能であるということは当業者には明らかであろう。また、本発明の実施例を不明瞭にすることを回避するため、一部の構成及び装置はブロック図により図示される。
【００１３】
明細書における「一実施例」あるいは「実施例」との表現は、当該実施例に関連して説明された特徴または構成が本発明の少なくとも１つの実施例に含まれるということを意味する。明細書のいくつかの場所に見受けられる「一実施例では」との表現は、必ずしもすべてが同一の実施例を参照するものでない。
【００１４】
パターンマッチングアプリケーションの例として、認証（顔、声、指紋、署名及び虹彩によるマッチングなど）、在庫管理（バーコードや無線周波数による識別など）、通信（発話、音声、画像認識及び比較、ヘッダ構文解析など）、及び工業用制御（部品検査や予知保全など）があげられる。
【００１５】
このようなアプリケーションからの入力データは、１以上の比較アルゴリズムに従って基準パターンまたはテンプレート群と比較され、リアルタイムデータと基準テンプレートとの各種距離測度が生成されるかもしれない。距離測度は、距離の公式やアルゴリズムに従って２つのデータ間の相違を定量化したものである。例えば、距離測度は、ビットイグザクトマッチ（ｂｉｔ ｅｘａｃｔ ｍａｔｃｈ）、ハミング距離、ユークリッド距離、ミーンアグニチュード（ｍｅａｎ ｍａｇｎｉｔｕｄｅ）距離及び相関距離などがある。いくつかの距離測度は、一部のアプリケーションには利用可能であるが、他のアプリケーションには利用可能でない。アプリケーションには、複数タイプの距離測度が利用可能なものもある。従って、１以上の距離測度の選択能力が、実現されるようにしてもよい。
【００１６】
一部のアプリケーションでは、距離測度が生成された後、当該距離測度にはさらなる処理または分類が行われ、選択された集合の中のどの基準テンプレートが入力データと最も良く比較するか、１以上の分類基準に従って判断される。例えば、どの基準テンプレートが与えられた入力データに対するベストマッチ、ワーストマッチ、ミーン（ｍｅａｎ）マッチ、及び／またはメディアン（ｍｅｄｉａｎ）マッチであるか判断されてもよい。これらの「マッチ」に基づき行われる判定タイプはアプリケーションに応じて可変とされ、選択可能な距離測度の分類を提供するパターンマッチングアーキテクチャが実現されてもよい。
【００１７】
図１を参照するに、本発明の一実施例によるパターンマッチングユニット１００のブロック図が示される。パターンマッチングユニット１００は、生成される１以上の距離測度（例えば、ビットイグザクトマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び／または相関距離など）を選択する機能を備えてもよいし、また選択された１以上の分類基準（例えば、ベストマッチ、ワーストマッチ、ミーンマッチ及び／またはメディアンマッチ）に従って距離測度を分類する機能を備えてもよいし、入力データと基準テンプレート群とをマッチングさせ、ユーザの選択に基づきマッチしたテンプレートのインデックスを提供する論理及び算術比較機構を有する検索テーブル機構を有するようにしてもよい。
【００１８】
一実施例では、パターンマッチングユニット１００は、オンチップメモリを用いてホストバスを占有することなく高速アクセス可能な大量の基準テンプレート群を格納するように、記憶装置の内部に一体化されてもよい。一実施例では、パターンマッチングユニット１００は、パターンマッチングアクセラレータとしてプロセッサに埋め込まれてもよい。一実施例では、埋め込みパターンマッチングユニット１００は、高速、フレキシブルかつ複雑なデータ比較及び分類を提供するため、プロセッサが他のタスクを実行するのを可能にしながら、プロセッサの比較命令に変換されてもよい。このようなプロセッサは、パターン認識、分岐予測、知的キャッシュ処理、適応的マッチフィルタリング及び命令レベル暗号化などの各種アプリケーションに対して、埋め込みパターンマッチングユニット１００を効果的に利用するようにしてもよい。
【００１９】
さらに図１を参照するに、入力バッファ１０６は、入力１０２を介し入力データを受信し、フレキシブル比較分類ユニット１０８による以降の処理のため、この入力データを格納するようにしてもよい。一実施例では、入力バッファ１０６は、フレキシブル比較分類ユニット１０８による処理のため以前の入力データが抽出されるに従って、新たな入力データの非同期ロード処理を可能にするようデュアルポートまたはダブルバッファ処理される。
【００２０】
テンプレートメモリ１０４は、入力１０２から基準パターンやテンプレートを受信し、フレキシブル比較分類ユニット１０８による以降の処理のため、これらの基準テンプレートを格納するのに利用されてもよい。一実施例では、テンプレートメモリ１０４は、基準テンプレートが同時にロード及びアクセスされるのを可能にするようデュアルポートまたはダブルバッファ処理されてもよい。様々な実施例では、テンプレートメモリ１０４は、対象となるアプリケーションのメモリサイズ、パワー、スピード、不揮発性などの各要求に一致するよう各種メモリ技術に基づくものであってもよい。例えば、テンプレートメモリ１０４は、ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ Ｐｒｏｇｒａｍｍａｂｌｅ Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）、フラッシュメモリあるいはＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ Ｅｒａｓａｂｌｅ Ｐｒｏｇｒａｍｍａｂｌｅ Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）などの半導体装置により実現されてもよい。
【００２１】
さらに図１を参照するに、入力バッファ１０６とテンプレートメモリ１０４からのデータまたはベクトルが、フレキシブル比較分類ユニット１０８の入力に与えられる。図２に関してより詳細に後述するように、フレキシブル比較分類ユニット１０８は、各データ幅を比較及び分類し、入力データと基準テンプレートを比較及び分類用のサブフィールドまたは次元に分割またはスライスし、各種比較を行うことにより入力データと基準テンプレートとの間の各種距離測度（例えば、ビットイグザクトマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び／または相関距離など）を生成し、入力データの各次元に対する距離測度を総計または合成することによりネットの距離測度を生成し、選択された１以上の基準（例えば、ベストマッチ、ワーストマッチ、ミーンマッチ及び／またはメディアンマッチ）に従ってネットの距離測度を分類する。フレキシブル比較分類ユニット１０８はまた、特定されたマッチと境界状態に基づき１以上の決定を行う機構を有するようにし、１以上の決定フラグ１２４を介しこれらの決定を示すようにしてもよい。フレキシブル比較分類ユニット１０８はまた、比較のための多数の基準テンプレートまたはベクトル次元を収容するため、複数のパターンマッチングユニット１０８のカスケード処理を可能にするカスケードＰＭＵ入力１１２を有するようにしてもよい。フレキシブル比較分類ユニット１０８の一実施例のさらなる詳細は、図２に関連して後述される。
【００２２】
さらに図１を参照するに、出力バッファ１１６が、フレキシブル比較分類ユニット１０８からの出力１２６を格納し、バッファされた結果１１８をマルチプレクサ１２０に与えるようにしてもよい。フレキシブル比較分類ユニット１０８からの出力１２６には、特定された基準テンプレートマッチのインデックス値、マッチした基準テンプレート、関連するネットの距離測度及び／または他の関連するマッチデータが含まれてもよい。一実施例では、出力バッファ１１６は、ＦＩＦＯ（Ｆｉｒｓｔ−Ｉｎ−Ｆｉｒｓｔ−Ｏｕｔ）スタックである。一実施例では、マルチプレクサ１２０は、出力バッファ１１６からバッファされた結果１１８を受信すると共に、フレキシブル比較分類ユニット１０８から直接的に出力１２６を受信する。１つのモード（例えば、スタンドアローンＰＭＵモード）では、マルチプレクサ１２０は、バッファされた結果１１８を最終的なＰＭＵ出力１２２に提供してもよい。他のモード（例えば、カスケードＰＭＵモード）では、マルチプレクサ１２０は、フレキシブル比較分類ユニット１０８の出力を最終的なＰＭＵ出力１２２に直接的に与えるようにしてもよい。この最終的なＰＭＵ出力１２２は、フレキシブル比較分類ユニット１０８の最終的な比較／分類出力としてホストシステムまたは他の装置に与えられるようにしてもよい。
【００２３】
一実施例では、出力バッファ１１６は、ホストシステムに状態情報を提供するため、適切なフラグ（例えば、アンダーフロー、オーバーフロー、ハーフフルなど）を生成するよう制御ユニット１１０と共に動作するようにしてもよい。このようなフラグは、ホストシステムがフラグを定期的に集計し、選択された個数の入力ベクトルが比較及び分類された後に応答するのを可能にするかもしれない。このようにして、ホストシステムは、パターンマッチングユニット１００が入力ベクトル群を比較及び分類しながら、他のタスクを実行するようにしてもよい。
【００２４】
さらに図１を参照するに、制御ユニット１１０は、パターンマッチングユニット１００の各種設定オプションを提供するようにしてもよい。例えば、制御ユニット１１０は、データサイズ／幅、入力データ及び基準テンプレートが分割されるベクトル次元数及び幅、各比較において生成される１以上の距離測度の選択、利用される１以上の分類基準の選択、及びカスケードモードなどの各種パターンマッチングモードの選択を制御するかもしれない。制御ユニット１１０はまた、パターンマッチングユニット１００の各種ユニット間のデータ処理及び転送のシーケンス処理を制御するようにしてもよい。制御ユニット１１０はまた、パターンマッチングユニット１００とやりとりするため、ホストシステムや他の装置のための外部インタフェースを提供するようにしてもよい。一実施例では、外部インタフェースは、メモリ変換インタフェースである。一実施例では、外部インタフェースは、入出力（Ｉ／Ｏ）変換インタフェースである。制御ユニット１１０の一実施例のさらなる詳細は、図３に関連して後述される。
【００２５】
図２を参照するに、本発明の一実施例による図１のフレキシブル比較分類ユニットのより詳細なブロック図が示される。ビットフィールド選択ユニット２０６は、入力バッファ１０６とテンプレートメモリ１０４からそれぞれ入力データ２０４と基準テンプレート２０２の各サイズまたはビット幅を処理するよう構成されてもよい。入力データ２０４と基準テンプレート２０２は、様々な次元またはサブフィールドを有するデータあるいはベクトルを表すものであってもよい。ビットフィールド選択ユニット２０６は、入力データ２０４と基準テンプレート２０２を様々な次元のベクトルを表す設定可能なサイズの１以上のビットフィールドにスライスまたは分割するよう構成されてもよい。例えば、入力データ２０４と基準テンプレート２０２は、赤、緑、青とカラー表示画素データの強度の４つの次元から構成される３２ビットベクトルとすることも可能である。この場合、ビットフィールド選択ユニット２０６は、３２ビットデータ幅を扱い、３２ビット入力データ２０４と３２ビット基準テンプレート２０２を、以下のベクトル次元を表す４つの８ビットシャンクまたはビットフィールド、すなわち、８ビットの赤（Ｒ）、８ビットの緑（Ｇ）、８ビットの青（Ｂ）及び８ビットの強度（Ｉ）に分割またはスライスするよう構成することが可能である。
【００２６】
さらに図２を参照するに、比較ユニット２０８は、入力データ２０４の各ビットフィールドまたは次元と基準テンプレート２０２の対応するビットフィールドまたは次元を１以上の比較アルゴリズムに従って比較し、設定に応じて１以上の距離測度を生成するようにしてもよい。一実施例では、比較ユニット２０８は、各次元の距離測度と内部レジスタから抽出されるかもしれない対応する加重係数と乗算してもよい。例えば、あるカラーベクトルマッチングアプリケーションは、赤と輝度が青と緑より重要な比較次元であると判断するかもしれない。この場合、０．９０、０．３０、０．４０及び０．９５の加重係数が、赤、緑、青と輝度次元にそれぞれ利用することができる。一実施例では、比較ユニット２０８は、ビットフィールドまたは次元のすべてからの距離測度を合計または合成し（設定に応じて加重係数を適用することにより）、入力データ２０４と基準テンプレート２０４との間のネットの距離測度を生成する。
【００２７】
対象とするアプリケーションに応じて、本発明の一実施例は、１以上の比較アルゴリズムを利用して１以上の距離測度を生成するよう構成されてもよい。いくつかの有用な距離測度として、ビットイグザクトマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び／または相関距離などがある。これらの距離測度が簡単に説明される。ビットイグザクト比較では、２つのデータの対応する各ビットを比較することにより、比較対象の２つのデータ間の正確なビット単位による一致があるか判断される。例えば、入力ベクトル「０１０１１１０１」は、基準テンプレート「０１０１１１０１」のビットイグザクトマッチであるが、基準テンプレート「０１０１１１００」のビットイグザクトマッチではない。ハミング距離測度は、一致する対応するビットの総数をトータルのビット幅により除することにより決定される（一致ビット数／トータルビット幅）。例えば、入力ベクトル「１０１１０１１０１０１０」と基準テンプレート「０１０１１１０１０１１１」との間のハミング距離は、３／１２、すなわち、０．２５である（右から２番目、７番目及び９番目がビットマッチに対応し、データビット幅が１２ビットであるため）。ユークリッド距離は、１次元ベクトルには（Ｘ−Ｙ）２を用いて、ｎ次元ベクトルまたはサブフィールドＸ１．．．ＸｎとＹ１．．．Ｙｎには
【００２８】
【数１】
を用いて計算することができる。ミーンマグニチュード距離は、１次元ベクトルには｜Ｘ−Ｙ｜を用いて、ｎ次元ベクトルまたはサブフィールドＸ１．．．ＸｎとＹ１．．．Ｙｎには
【００２９】
【数２】
を用いて計算することができる。相関距離は、１次元ベクトルにはＸ・Ｙを用いて、ｎ次元ベクトルまたはサブフィールドＸ１．．．ＸｎとＹ１．．．Ｙｎには
【００３０】
【数３】
を用いて計算することができる。
【００３１】
さらに図２を参照するに、比較ユニット２０８は、各入力データ２０４と複数の基準テンプレート２０２を比較し、各入力データに関するネットの距離測度を分類ユニット２１０に提供する。分類ユニット２１０は、選択された１以上の分類基準に従って入力データ２０４にマッチする基準テンプレート２０２を特定するよう構成されてもよい。例えば、分類ユニット２１０は、基準テンプレートの何れが、各入力データに対するベストマッチ、ワーストマッチ、ミーンマッチ及び／またはメディアンマッチであるか判断するよう構成されてもよい。ベストマッチは、与えられた分類基準に従って入力データ２０４と比較して最も好ましいネット距離測度を有する基準テンプレートである。ワーストマッチは、与えられた分類基準に従って入力データ２０４に最もふさわしくないネット距離測度を有する基準テンプレートである。ミーンマッチは、ネット距離測度の平均に最も近いネット距離測度を有する基準テンプレートである。メディアンマッチは、ネット距離測度の中央値に最も近いネット距離測度を有する基準テンプレートである。一実施例では、フレキシブル比較分類ユニット１０８は、基準テンプレートのインデックス値と、特定されたマッチに対応するネット距離測度を記録するようにしてもよい。
【００３２】
さらに図２を参照するに、一実施例では、フレキシブル比較分類ユニット１０８は、カスケード構成されたパターンマッチングユニットから選択されたマッチを分類する深さ拡張ユニット２１２を有するようにしてもよい。例えば、（図１の）複数のパターンマッチングユニット１００が、スピードを向上させるため（例えば、与えられた入力データをパラレルに処理する複数のユニットなど）、あるいは比較に利用可能な基準テンプレートの個数を増やすためカスケード構成されてもよい。深さ拡張モードが選択されると、深さ拡張ユニット２１２は、それの分類されたマッチとカスケードＰＭＵ入力２１４上に与えられる他のパターンマッチングユニットの何れかと比較し、複数のパターンマッチングユニット１００の選択されたマッチから最良の全体的なマッチを決定する。深さ拡張モードが選択されていないときには、深さ拡張ユニット２１２は、それの入力をそれの出力２１８に単にコピーするようにしてもよい。カスケード化されたパターンマッチングアーキテクチャの一実施例のさらなる詳細が、図４に関連して後述される。
【００３３】
さらに図２を参照するに、一実施例では、フレキシブル比較分類ユニット１０８はまた、判定ユニット２２０を有するようにしてもよい。判定ユニット２２０は、深さ拡張ユニット２１２から出力２１８（特定されたマッチと関連する距離測度を含む）を受け取り、判定基準または閾値を示す１以上の境界基準２２２を受信するようにしてもよい。判定ユニット２２０は、出力２１８と境界基準２２２を比較し、この比較に基づきパターンマッチングユニット１００による様々な判定を示す１以上の判定フラグを生成するようにしてもよい。例えば、指紋マッチングアプリケーションでは、判定ユニット２００は、最も近いネットのユークリッド距離測度の値が所定値未満である場合、「指紋マッチ」フラグをアサートするよう構成されるかもしれない。一実施例では、判定ユニット２２０は、埋め込みアプリケーションにおけるスタンドアローンによる利用のためのパターンマッチングユニット１００において利用されてもよい。各種制御入力２１６がまた、フレキシブル比較分類ユニット１０８のタイミング、シーケンス処理及び全体機能を制御するのに提供されてもよい。
【００３４】
図３を参照するに、本発明の一実施例による図１の制御ユニット１１０のブロック図が示される。外部インタフェース３０８は、ホストシステムまたは他の装置がアドレス信号３０２、データ信号３０４及びリード／ライト信号３０６を介しパターンマッチングユニット１００とやりとりするのを可能にする。外部インタフェース３０８を利用して、ホスト装置またはシステムは、テンプレートをテンプレートメモリ１０４に格納し、データを入力バッファ１０６にロードし、出力バッファ１１６から結果を読取ることが可能である。アドレス入力３０２とデータ入力３０４を介しホストにより与えられるアドレス及びデータ情報のパターンマッチングユニット１００の内部の通信は、内部アドレスバス３１０と内部データバス３１２を介し実行されるかもしれない。
【００３５】
一実施例では、制御ユニット１１０は、ホストシステムのメモリスペースの４つの場所を利用するパターンマッチングユニット１００に対するメモリ変換インタフェースを提供するかもしれない。テーブル１に変換例が示される。
【００３６】
【表１】
【００３７】
一実施例では、制御レジスタ３１４は、ａ）テンプレートメモリ１０４のテンプレートの開始アドレス、ｂ）比較されるテンプレートの個数、ｃ）次元ごとのビットフィールド幅、ｄ）ベクトルごとのベクトル次元数、ｅ）深さ拡張オン／オフ、及びｆ）距離測度の選択を含むようにしてもよい。一実施例では、制御ユニット１１０は、各種フラグ（例えば、実行済み／未実行、カスケードモード、メモリチェックなど）を含む状態レジスタ３１６を有するようにしてもよい。一実施例では、制御ユニット１１０は、各種デバッグ動作を提供するデバッグレジスタ３１８を有するようにしてもよい。
【００３８】
さらに図３を参照するに、設定タイミングデコーダ３２０は、設定情報３２６をパターンマッチングユニット１００に提供する。シーケンサ３２２は、パターンマッチングユニット１００の各種機能ブロックのタイミング及び動作を制御する制御信号３２４を与える。
【００３９】
図４を参照するに、本発明の一実施例によるカスケード構成されたパターンマッチングアーキテクチャ４００のブロック図が示される。図４は、（図１の）複数のパターンマッチングユニット１００が、スピードを向上させ（例えば、パラレルに１以上の入力データを処理する複数のユニットなど）、及び／または比較のため利用可能な基準テンプレートの個数を増やすためどのようにカスケード構成することが可能であるか示す。入力データは、入力１０２（ａ）、１０２（ｂ）及び１０２（ｃ）を介しパターンマッチングユニット１００（ａ）、１００（ｂ）及び１００（ｃ）にそれぞれ与えられる。パターンマッチングユニット１００（ａ）、１００（ｂ）及び１００（ｃ）は、パターンマッチングユニット１００（ａ）の最終的なＰＭＵ出力１２２（ａ）をパターンマッチングユニット１００（ｂ）のカスケードＰＭＵ入力１２２（ｂ）に接続すると共に、パターンマッチングユニット１００（ｂ）の最終的なＰＭＵ出力１２２（ｂ）をパターンマッチングユニット１００（ｃ）のカスケードＰＭＵ入力１１２（ｃ）に接続することにより、カスケードモードで接続されてもよい。本実施例では、パターンマッチングユニット１００（ａ）、１００（ｂ）及び１００（ｃ）の各々の深さ拡張ユニット２１２は、複数のパターンマッチングユニット１００により比較及び分類された最良の全体的マッチを決定するよう動作し、最終的なＰＭＵ出力１２２（ｃ）に最良の全体的マッチデータを提供する。一実施例では、カスケードアーキテクチャは、多数の基準テンプレートの比較を可能にするよう利用されてもよい。例えば、同じ入力データが、複数のカスケード接続されたパターンパッチングユニットに保持されている異なる基準テンプレートセットとパラレルに比較することが可能である。一実施例では、同一の基準テンプレートセットが、入力データ群を比較及び分類するスピードを向上させるため、カスケード接続されたパターンマッチングユニットに格納することが可能である。
【００４０】
実施例は、論理回路、状態マシーン、マイクロコードあるいはこれらの組み合わせにより実現されてもよい。実施例はコードにより実現されてもよく、命令を実行するようコンピュータシステムをプログラムするのに用いることが可能な命令を格納した記憶媒体に格納されてもよい。この記憶媒体は、以下に限定するものではないが、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｋ Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＣＤ−ＲＷ（Ｃｏｍｐａｃｔ Ｄｉｓｋ Ｒｅｗｒｉｔａｂｌｅ）、光磁気ディスクを含む任意のタイプのディスク、ＲＯＭ、ＲＡＭ、ＤＲＡＭ、ＥＰＲＯＭ、フラッシュメモリ、ＥＥＰＲＯＭなどの半導体装置、磁気または光カード、ネットワーク記憶装置、あるいは電子命令を格納するのに適した任意のタイプの媒体を含むものであってもよい。
【００４１】
実施例は、ハードウェア装置の適切な組み合わせにより構成された適切なコンピュータシステムによる実行のためのソフトウェアにより実現されてもよい。
【００４２】
図５を参照するに、本発明の実施例が利用可能なコンピュータシステム５００のブロック図が示される。一実施例では、コンピュータシステム５００は、マイクロプロセッサ、マイクロコントローラ、プログラマブルゲートアレイ（ＰＧＡ）などの汎用または特定用途向けプロセッサを有するプロセッサ５１０を備える。ここで用いられる「コンピュータシステム」という用語は、デスクトップコンピュータ、サーバコンピュータ、ラップトップコンピュータなどの任意のタイプのプロセッサベースシステム、あるいは他のタイプのホストシステムを表すかもしれない。
【００４３】
プロセッサ５１０は、一実施例では、メモリバス５２５を介しシステムメモリ５２０（ＤＲＡＭなど）に接続されるメモリハブ５３０にホストバス５１５を介し接続されてもよい。メモリハブ５３０はまた、ディスプレイ５３７に接続されるビデオコントローラ５３５にＡＧＰ（Ａｄｖａｎｃｅｄ Ｇｒａｐｈｉｃｓ Ｐｏｒｔ）を介し接続されてもよい。ＡＧＰバス５３３は、カリフォルニア州サンタクララのインテルコーポレイションにより１９９８年５月４日に刊行されたＡｃｃｅｌｅｒａｔｅｄ Ｇｒａｐｈｉｃｓ Ｐｏｒｔ Ｉｎｔｅｒｆａｃｅ 仕様書に準拠していてもよい。
【００４４】
（図１の）パターンマッチングユニット１００は、メモリバス５２５を介しメモリハブ５３０に接続されてもよい。本実施例では、パターンマッチングユニット１００は、メモリ変換装置であってもよい。他の実施例では、パターンマッチングユニット１００は、入出力（Ｉ／Ｏ）変換装置であってもよい。一実施例では、パターンマッチングユニット１００は、パターンマッチングアクセラレータとしてプロセッサ５１０に埋め込まれてもよい。一実施例では、埋め込みパターンマッチングユニット１００は、プロセッサ５１０が他のタスクを実行するのを可能としながら、高速、フレキシブルかつ複雑なデータ比較及び分類を提供するためプロセッサ５１０の比較命令に変換されるようにしてもよい。プロセッサ５１０は、パターン認識、分岐予測、知的キャッシュ処理、適応的マッチフィルタリング、命令レベル暗号化などの各種アプリケーションに対して、パターンマッチングユニット１００を効果的に利用するかもしれない。
【００４５】
メモリハブ５３０は、１９９５年６月のＰＣＩローカルバス仕様書、プロダクツバージョン改訂２．１により規定されるようなＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ）バス５４４と入出力（Ｉ／Ｏ）拡張バス５４２に接続される入出力（Ｉ／Ｏ）ハブ５４０に接続されてもよい（ハブリンク５３８を介し）。このＩ／Ｏ拡張バス５４２は、１以上のＩ／Ｏ装置へのアクセスを制御するＩ／Ｏコントローラ５４６に接続されてもよい。図５に示されるように、一実施例では、これらの装置には、フロッピー（登録商標）ディスクドライブ５５０などの記憶装置と、キーボード５５２やマウス５５４などの入力装置が含まれてもよい。Ｉ／Ｏハブ５４０はまた、図５に示されるように、ハードディスクドライブ５５６とＣＤドライブ５５８に接続されてもよい。他の記憶装置が本システムに設けられてもよいということは理解されるべきである。
【００４６】
ＰＣＩバス５４４はまた、例えば、ネットワークポート（図示せず）に接続されるネットワークコントローラ５６０を含む各種コンポーネントに接続されてもよい。パラレルポート、シリアルポート、不揮発性メモリなどのさらなる装置が、Ｉ／Ｏ拡張バス５４２とＰＣＩバス５４４に接続されてもよい。
【００４７】
上記説明はシステム５００の具体的コンポーネントを参照したが、説明及び図示された実施例の多数の改良及び変形が可能であるということが考えられる。また、図５はパーソナルコンピュータなどのシステムのブロック図を示しているが、本発明の実施例は特殊なパターン認識装置、携帯情報端末（ＰＤＡ）などにより実現されてもよいということは理解されるべきである。
【００４８】
図６を参照するに、本発明の一実施例によるパターンマッチング方法を示すフロー図が示される。設定オプションは、入力データと基準テンプレートまたはパターンの比較に利用される比較アルゴリズムや１以上の距離測度の選択を可能にするものであってもよく、選択された１以上の基準に従い与えられた入力データにベストマッチする１以上の基準テンプレートを特定するのに利用可能な１以上の分類基準の選択を可能にするものであってもよい（ブロック６０２）。設定オプションは、入力データと基準テンプレートの次元のサイズやビット幅の選択を可能にするものであってもよく、各入力データと基準テンプレートの次元数及び／またはサイズの選択を可能にするものであってもよい（ブロック６０４）。一実施例では、設定オプションは、入力データと基準テンプレートの全体的なビット幅と各入力データと基準テンプレートの次元数の選択を提供するものであってもよい。
【００４９】
設定オプションが設定された後、パターンマッチングプロセスは、比較及び分類対象の入力データをフェッチすることにより進められる（ブロック６０６）。入力データが比較される基準テンプレートもまたフェッチされる（ブロック６０８）。複数の次元を有するデータの比較においてフレキシビリティを提供するため、入力データと基準テンプレートの各々は、設定オプションに従って複数の時限またはビットフィールドに分割され（ブロック６１０）、入力データと基準テンプレートの対応する各次元に対し距離測度が決定されるのを可能にするようにしてもよい（ブロック６１２）。各次元の距離測度が決定されると、１以上の加重係数が１以上の次元に関連する距離測度に適用されてもよい（ブロック６１４）。その後、これらの距離測度は、当該入力データと基準テンプレートのネット距離測度に合計または合成されてもよい（ブロック６１６）。ブロック６０８〜６１６は、与えられた基準データが選択された基準テンプレートのすべてと比較されるまで繰り返されるようにしてもよい（ブロック６１８）。この入力データがすべての基準テンプレートと比較されると、どの距離測度（及び対応する基準テンプレート）が入力データにベストマッチするか判断するため、選択された分類基準に従って分類されるようにしてもよい（ブロック６２０）。一実施例では、ブロック６２０において特定されたマッチは、１以上の境界基準と比較され、この比較に基づき１以上の判定がなされるようにしてもよい（ブロック６２２）。
【００５０】
以上のように、パターンマッチングアーキテクチャのための方法、装置及びシステムが説明された。本発明は限られた実施例に関して説明されたが、本開示により、当業者は多数の改良及び変形を理解するであろう。添付された請求項は、このようなあらゆる改良及び変形を本発明の真の趣旨及び範囲に属するものとしてカバーしようとするものである。
【図面の簡単な説明】
【００５１】
【図１】図１は、本発明の一実施例によるパターンマッチングユニットのブロック図である。
【図２】図２は、本発明の一実施例による図１のフレキシブル比較分類ユニットのブロック図である。
【図３】図３は、本発明の一実施例による図１の制御ユニットのブロック図である。
【図４】図４は、本発明の一実施例によるカスケード構成されたパターンマッチングアーキテクチャのブロック図である。
【図５】図５は、本発明の実施例が利用可能なコンピュータシステムのブロック図である。
【図６】図６は、本発明の一実施例によるパターンマッチング方法を示すフロー図である。
【符号の説明】
【００５２】
１００ パターンマッチングユニット
１０４ テンプレートメモリ
１０６ 入力バッファ
１０８ フレキシブル比較分類ユニット
１１０ 制御ユニット
１１６ 出力バッファ
１２０ マルチプレクサ
２０６ ビットフィールド選択ユニット
２０８ 比較ユニット
２１０ 分類ユニット
２１２ 深さ拡張ユニット
２２０ 判定ユニット
３０８ 外部インタフェース
３１４ 制御レジスタ
３１６ 状態レジスタ
３１８ デバッグレジスタ
３２０ 設定タイミングデコーダ
３２２ シーケンサ
【特許請求の範囲】
【請求項１】
入力データをビット数がプログラム可能な入力ビットフィールドに分割し、１以上の基準テンプレートをビット数がプログラム可能な対応する基準ビットフィールドに分割する選択ユニットと、
前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の１以上の距離を決定し、前記基準ビットフィールドに係る１以上の距離を前記基準テンプレートに対応する１以上のネットの距離に合成する距離ユニットと、
から構成されることを特徴とする装置。
【請求項２】
請求項１記載の装置であって、
前記入力データと前記基準テンプレートのビット数は、プログラム可能であることを特徴とする装置。
【請求項３】
請求項１記載の装置であって、
前記距離ユニットは、各基準テンプレートに係る距離が前記１以上のネットの距離に合成される前に、１以上の加重係数を前記距離に適用するよう構成されることを特徴とする装置。
【請求項４】
請求項１記載の装置であって、
前記距離ユニットは、イグザクトビットマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び相関距離の少なくとも１つを含む１以上のタイプの距離及びネットの距離を決定するよう設定可能となるよう構成されることを特徴とする装置。
【請求項５】
請求項１記載の装置であって、さらに、
前記入力データと前記基準テンプレートを格納するメモリを有し、
当該装置は、単一の集積回路上で実現されることを特徴とする装置。
【請求項６】
請求項１記載の装置であって、さらに、
前記入力データ、前記基準テンプレート、制御データ及び状態データを当該装置と交換するホストインタフェースを有することを特徴とする装置。
【請求項７】
請求項６記載の装置であって、
前記ホストインタフェースは、メモリ変換または入出力（Ｉ／Ｏ）変換されることを特徴とする装置。
【請求項８】
請求項１記載の装置であって、さらに、
１以上の選択可能な分類基準に従って、前記１以上のネットの距離を分類する分類ユニットを有することを特徴とする装置。
【請求項９】
請求項８記載の装置であって、
前記選択可能な分類基準は、ベストマッチ、ワーストマッチ、ミーンマッチ及びメディアンマッチの１以上を含むことを特徴とする装置。
【請求項１０】
請求項８記載の装置であって、さらに、
他のネットの距離を受け取り、前記１以上の選択可能な分類基準に従って、前記他のネットの距離と前記１以上の分類されたネットの距離を比較するカスケードユニットを有することを特徴とする装置。
【請求項１１】
請求項８記載の装置であって、さらに、
前記１以上の分類されたネットの距離と１以上の境界基準との比較に基づき、１以上の判定フラグを生成する判定ユニットを有することを特徴とする装置。
【請求項１２】
プログラム可能なビットフィールド幅に従って、入力データを入力ビットフィールドに分割するステップと、
前記ビットフィールド幅に従って、１以上の基準テンプレートを前記入力ビットフィールドに対応する基準ビットフィールドに分割するステップと、
前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の距離を決定するステップと、
前記基準ビットフィールドに係る距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するステップと、
から構成されることを特徴とする方法。
【請求項１３】
請求項１２記載の方法であって、さらに、
前記入力データと前記基準テンプレートのビット数を設定するステップを有することを特徴とする方法。
【請求項１４】
請求項１２記載の方法であって、さらに、
各基準テンプレートに係る距離を前記１以上のネットの距離に合成する前に、１以上の加重係数を前記距離に適用するステップを有することを特徴とする方法。
【請求項１５】
請求項１２記載の方法であって、
イグザクトビットマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び相関距離の少なくとも１つを含む１以上のタイプの距離及びネットの距離が決定されることを特徴とする方法。
【請求項１６】
請求項１２記載の方法であって、さらに、
１以上の選択可能な分類基準に従って、前記１以上のネットの距離を分類するステップを有することを特徴とする方法。
【請求項１７】
請求項１６記載の方法であって、
前記選択可能な分類基準は、ベストマッチ、ワーストマッチ、ミーンマッチ及びメディアンマッチの１以上を含むことを特徴とする方法。
【請求項１８】
請求項１６記載の方法であって、さらに、
他のネットの距離と前記分類されたネットの距離を比較し、前記他のネットの距離に関連して前記分類されたネットの距離をさらに分類するステップを有することを特徴とする方法。
【請求項１９】
請求項１６記載の方法であって、さらに、
前記１以上の分類されたネットの距離と１以上の境界基準との比較に基づき、１以上の判定フラグを生成するステップを有することを特徴とする方法。
【請求項２０】
プロセッサによる実行のための命令を格納するよう接続されるダイナミックランダムアクセスシステムメモリと、
プロセッサリクエストに応答して、入力データと基準テンプレート群との間の距離群を決定し、１以上の分類基準に従って、前記入力データにベストマッチする基準テンプレートを特定するパターンマッチングユニットと、
から構成されるシステムであって、
前記パターンマッチングユニットは、選択ユニットと距離ユニットを有し、
前記選択ユニットは、入力データをビット数がプログラム可能な入力ビットフィールドに分割し、１以上の基準テンプレートをビット数がプログラム可能な対応する基準ビットフィールドに分割し、
前記距離ユニットは、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の１以上の距離を決定し、前記基準ビットフィールドに係る１以上の距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するよう構成される、
ことを特徴とするシステム。
【請求項２１】
請求項２０記載のシステムであって、
前記入力データと前記基準テンプレートのビット数は、プログラム可能であることを特徴とするシステム。
【請求項２２】
請求項２０記載のシステムであって、
前記距離ユニットは、各基準テンプレートに係る距離が前記１以上のネットの距離に合成される前に、１以上の加重係数を前記距離に適用するよう構成されることを特徴とするシステム。
【請求項２３】
請求項２０記載のシステムであって、
前記パターンマッチングユニットはさらに、前記入力データ、前記基準テンプレート、制御データ及び状態データを前記プロセッサと交換するメモリ変換または入出力（Ｉ／Ｏ）変換されたホストインタフェースを有することを特徴とするシステム。
【請求項２４】
請求項２０記載のシステムであって、
前記パターンマッチングユニットはさらに、１以上の選択可能な分類基準に従って、前記１以上のネットの距離を分類する分類ユニットを有することを特徴とするシステム。
【請求項２５】
実行される場合にシステムが、
プログラム可能なビットフィールド幅に従って、入力データを入力ビットフィールドに分割するステップと、
前記ビットフィールド幅に従って、１以上の基準テンプレートを前記入力ビットフィールドに対応する基準ビットフィールドに分割するステップと、
前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の距離を決定するステップと、
前記基準ビットフィールドに係る距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するステップと、
を実行することを可能にする命令を含むマシーンアクセス可能な媒体から構成される物品。
【請求項２６】
請求項２５記載の物品であって、さらに、
実行される場合に前記システムが、前記入力データと前記基準テンプレートのビット数を設定するステップを実行することを可能にする命令を有することを特徴とする物品。
【請求項２７】
請求項２５記載の物品であって、さらに、
実行される場合に前記システムが、イグザクトビットマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び相関距離の１以上を含む１以上のタイプの距離及びネットの距離を決定することを可能にする命令を有することを特徴とする物品。
【請求項２８】
請求項２５記載の物品であって、さらに、
実行される場合に前記システムが、ベストマッチ、ワーストマッチ、ミーンマッチ及びメディアンマッチの１以上を含む１以上の選択可能な分類基準に従って、前記１以上のネットの距離を分類することを可能にする命令を有することを特徴とする物品。
【請求項１】
入力データをビット数がプログラム可能な入力ビットフィールドに分割し、１以上の基準テンプレートをビット数がプログラム可能な対応する基準ビットフィールドに分割する選択ユニットと、
前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の１以上の距離を決定し、前記基準ビットフィールドに係る１以上の距離を前記基準テンプレートに対応する１以上のネットの距離に合成する距離ユニットと、
から構成されることを特徴とする装置。
【請求項２】
請求項１記載の装置であって、
前記入力データと前記基準テンプレートのビット数は、プログラム可能であることを特徴とする装置。
【請求項３】
請求項１記載の装置であって、
前記距離ユニットは、各基準テンプレートに係る距離が前記１以上のネットの距離に合成される前に、１以上の加重係数を前記距離に適用するよう構成されることを特徴とする装置。
【請求項４】
請求項１記載の装置であって、
前記距離ユニットは、イグザクトビットマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び相関距離の少なくとも１つを含む１以上のタイプの距離及びネットの距離を決定するよう設定可能となるよう構成されることを特徴とする装置。
【請求項５】
請求項１記載の装置であって、さらに、
前記入力データと前記基準テンプレートを格納するメモリを有し、
当該装置は、単一の集積回路上で実現されることを特徴とする装置。
【請求項６】
請求項１記載の装置であって、さらに、
前記入力データ、前記基準テンプレート、制御データ及び状態データを当該装置と交換するホストインタフェースを有することを特徴とする装置。
【請求項７】
請求項６記載の装置であって、
前記ホストインタフェースは、メモリ変換または入出力（Ｉ／Ｏ）変換されることを特徴とする装置。
【請求項８】
請求項１記載の装置であって、さらに、
１以上の選択可能な分類基準に従って、前記１以上のネットの距離を分類する分類ユニットを有することを特徴とする装置。
【請求項９】
請求項８記載の装置であって、
前記選択可能な分類基準は、ベストマッチ、ワーストマッチ、ミーンマッチ及びメディアンマッチの１以上を含むことを特徴とする装置。
【請求項１０】
請求項８記載の装置であって、さらに、
他のネットの距離を受け取り、前記１以上の選択可能な分類基準に従って、前記他のネットの距離と前記１以上の分類されたネットの距離を比較するカスケードユニットを有することを特徴とする装置。
【請求項１１】
請求項８記載の装置であって、さらに、
前記１以上の分類されたネットの距離と１以上の境界基準との比較に基づき、１以上の判定フラグを生成する判定ユニットを有することを特徴とする装置。
【請求項１２】
プログラム可能なビットフィールド幅に従って、入力データを入力ビットフィールドに分割するステップと、
前記ビットフィールド幅に従って、１以上の基準テンプレートを前記入力ビットフィールドに対応する基準ビットフィールドに分割するステップと、
前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の距離を決定するステップと、
前記基準ビットフィールドに係る距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するステップと、
から構成されることを特徴とする方法。
【請求項１３】
請求項１２記載の方法であって、さらに、
前記入力データと前記基準テンプレートのビット数を設定するステップを有することを特徴とする方法。
【請求項１４】
請求項１２記載の方法であって、さらに、
各基準テンプレートに係る距離を前記１以上のネットの距離に合成する前に、１以上の加重係数を前記距離に適用するステップを有することを特徴とする方法。
【請求項１５】
請求項１２記載の方法であって、
イグザクトビットマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び相関距離の少なくとも１つを含む１以上のタイプの距離及びネットの距離が決定されることを特徴とする方法。
【請求項１６】
請求項１２記載の方法であって、さらに、
１以上の選択可能な分類基準に従って、前記１以上のネットの距離を分類するステップを有することを特徴とする方法。
【請求項１７】
請求項１６記載の方法であって、
前記選択可能な分類基準は、ベストマッチ、ワーストマッチ、ミーンマッチ及びメディアンマッチの１以上を含むことを特徴とする方法。
【請求項１８】
請求項１６記載の方法であって、さらに、
他のネットの距離と前記分類されたネットの距離を比較し、前記他のネットの距離に関連して前記分類されたネットの距離をさらに分類するステップを有することを特徴とする方法。
【請求項１９】
請求項１６記載の方法であって、さらに、
前記１以上の分類されたネットの距離と１以上の境界基準との比較に基づき、１以上の判定フラグを生成するステップを有することを特徴とする方法。
【請求項２０】
プロセッサによる実行のための命令を格納するよう接続されるダイナミックランダムアクセスシステムメモリと、
プロセッサリクエストに応答して、入力データと基準テンプレート群との間の距離群を決定し、１以上の分類基準に従って、前記入力データにベストマッチする基準テンプレートを特定するパターンマッチングユニットと、
から構成されるシステムであって、
前記パターンマッチングユニットは、選択ユニットと距離ユニットを有し、
前記選択ユニットは、入力データをビット数がプログラム可能な入力ビットフィールドに分割し、１以上の基準テンプレートをビット数がプログラム可能な対応する基準ビットフィールドに分割し、
前記距離ユニットは、前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の１以上の距離を決定し、前記基準ビットフィールドに係る１以上の距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するよう構成される、
ことを特徴とするシステム。
【請求項２１】
請求項２０記載のシステムであって、
前記入力データと前記基準テンプレートのビット数は、プログラム可能であることを特徴とするシステム。
【請求項２２】
請求項２０記載のシステムであって、
前記距離ユニットは、各基準テンプレートに係る距離が前記１以上のネットの距離に合成される前に、１以上の加重係数を前記距離に適用するよう構成されることを特徴とするシステム。
【請求項２３】
請求項２０記載のシステムであって、
前記パターンマッチングユニットはさらに、前記入力データ、前記基準テンプレート、制御データ及び状態データを前記プロセッサと交換するメモリ変換または入出力（Ｉ／Ｏ）変換されたホストインタフェースを有することを特徴とするシステム。
【請求項２４】
請求項２０記載のシステムであって、
前記パターンマッチングユニットはさらに、１以上の選択可能な分類基準に従って、前記１以上のネットの距離を分類する分類ユニットを有することを特徴とするシステム。
【請求項２５】
実行される場合にシステムが、
プログラム可能なビットフィールド幅に従って、入力データを入力ビットフィールドに分割するステップと、
前記ビットフィールド幅に従って、１以上の基準テンプレートを前記入力ビットフィールドに対応する基準ビットフィールドに分割するステップと、
前記入力ビットフィールドと前記対応する基準ビットフィールドとの間の距離を決定するステップと、
前記基準ビットフィールドに係る距離を前記１以上の基準テンプレートに対応する１以上のネットの距離に合成するステップと、
を実行することを可能にする命令を含むマシーンアクセス可能な媒体から構成される物品。
【請求項２６】
請求項２５記載の物品であって、さらに、
実行される場合に前記システムが、前記入力データと前記基準テンプレートのビット数を設定するステップを実行することを可能にする命令を有することを特徴とする物品。
【請求項２７】
請求項２５記載の物品であって、さらに、
実行される場合に前記システムが、イグザクトビットマッチ、ハミング距離、ユークリッド距離、ミーンマグニチュード距離及び相関距離の１以上を含む１以上のタイプの距離及びネットの距離を決定することを可能にする命令を有することを特徴とする物品。
【請求項２８】
請求項２５記載の物品であって、さらに、
実行される場合に前記システムが、ベストマッチ、ワーストマッチ、ミーンマッチ及びメディアンマッチの１以上を含む１以上の選択可能な分類基準に従って、前記１以上のネットの距離を分類することを可能にする命令を有することを特徴とする物品。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００６−５９３３９（Ｐ２００６−５９３３９Ａ）
【公開日】平成１８年３月２日（２００６．３．２）
【国際特許分類】
【出願番号】特願２００５−２１２９７４（Ｐ２００５−２１２９７４）
【出願日】平成１７年７月２２日（２００５．７．２２）
【出願人】（５９３０９６７１２）インテル コーポレイション (931)
【Ｆターム（参考）】
【公開日】平成１８年３月２日（２００６．３．２）
【国際特許分類】
【出願日】平成１７年７月２２日（２００５．７．２２）
【出願人】（５９３０９６７１２）インテル コーポレイション (931)
【Ｆターム（参考）】
[ Back to top ]