パターン照合装置
本発明は、電子ドメインで完全に実現されるパターン認識相関器に関する。相関器は、入力シリアル２進データを少なくとも１つの入力パラレル２進電気信号に変換するシリアル−パラレル変換手段と、各入力パラレルデータ信号を参照パラレル２進データ信号と比較するコンパレータとを有する。シリアル−パラレル変換手段は、データ更新レートを効果的に遅くするデマルチプレクサと、パラレルデータ信号を発生する一連のラッチ回路とを備えてもよい。コンパレータは、ビット加算を実行するように配置されてもよく、総和ゼロが相関を示すように配置されてもよい。ビット加算は論理ゲートアレイによって実行されてもよい。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン認識用の電子装置、すなわち、検索データと参照データの相関のための電子装置に関し、特に、パターン照合を実行するために時系列データストリームをパラレルデータパターンに変換する電子装置に関する。
【背景技術】
【０００２】
パターン認識は、テキストまたは画像などの受信データの１つまたは複数の知られているオブジェクトを、知られている参照オブジェクトとそのデータを比較することによって認識するプロセスに関するものである。パターン認識を自発的に実行する理想的な方法は、相関の数学的演算によるものである。
【０００３】
パターン認識は、具体的な検索タームを探す問合せデータベースから生体ベースの認識システムおよび二次元画像の目標認識に至る多くの領域で使用される。一般に、検索は、知られている参照データ列を照合確認する検索対象データと比較するために適切にプログラムされたプロセッサを使ってディジタル的に実行される。一例は、１つまたは複数の入力参照タームをインターネットデータと比較して照合確認するインターネット検索エンジンである。
【０００４】
しかし、膨大な量のデータを検索する際は、ソフトウェアベースのパターン識別法は遅いことがあり、あるいは膨大な処理能力を必要とすることがある。また、遠隔通信のデータ転送速度などにおいて、データが高データ転送速度で受信されるときは、この速度で相関を実行するソフトウェアベースシステムが無効なこともある。
【０００５】
整合フィルタや相関器として知られる光学パターン認識システムも、知られており、空間パターンの照合に使用され得る。最も初期のこうした仕組みの１つは、ファンデルルクト（Ｖａｎｄｅｒ Ｌｕｇｔ）光整合フィルタであり、Ａ Ｖａｎｄｅｒ Ｌｕｇｔ，「Ｓｉｇｎａｌ ｄｅｔｅｃｔｉｏｎ ｂｙ ｃｏｍｐｌｅｘ ｓｐａｔｉａｌ ｆｉｌｔｅｒｉｎｇ」，ＩＥＥＥ ｔｒａｎｓ．Ｉｎｆ．Ｔｈｅｏｒｙ ＩＴ−１０，ｐ１３９−１４５（１９６４）に記載されている。このシステムでは、結合パターンに対して逆フーリエ変換を実行する前に参照パターンの共役フーリエ変換によって場面のフーリエ変換を展開する光学装置を使用する。参照画像（ｒｅｆｅｒｅｎｃｅ）と画像の間に強い相関が存在する場合は、鋭く明るいピークがシステムの後焦点面に出現する。したがって、このシステムは観測画像を参照画像と比較して相関があるかどうかを示し、相関があれば、どこに出現するか、すなわち、システムは場面における目標の存在と場所を認識する。最近の光学パターン認識システムは、場面のフーリエ変換（ＦＴ）を実行し、パターンを電子的に参照し、結合ＦＴを空間光変調器（ＳＬＭ）に表示して動作を簡素化し高速化する（たとえば、国際公開第００／１７８０９号パンフレットに記載された相関器を参照されたい）。このような光学パターン認識システムは、観測場面などにおける目標認識には役立つが、検索データの保存場所については、検索対象データまたは結合データおよび参照パターンのいずれかによるＳＬＭの更新を必要とする。高速ＳＬＭを使用した場合でも、ＳＬＭの更新速度はそのアプリケーションに関する相関速度を制限する。本明細書で使用される用語の相関器は整合フィルタベースシステムを含むものと解釈されて差し支えないことに留意されたい。
【０００６】
近年、光相関の利点を高速パターン照合に適用することが提案されている。本出願人の同時係属中の国際特許出願第ＰＣＴ／ＧＢ２００５／００４０２８号明細書および英国特許出願第ＧＢ０４２３０９３．４号明細書には、高速位相変調および並列光処理を使用して高速相関を可能とする相関器装置が記載されている。
【０００７】
図１は、この高速光相関器の第１の実施形態を示す。相関器は、時系列、すなわち順次入力データストリーム２に作用する。このデータストリームは、たとえば、遠隔通信に使用されるような振幅変調２進光信号の形態であってもよく、また特定データの存在に対して検索の対象となるデータベースからの流れであってもよい。振幅変調入力信号２は、光検出器４によって検出される。検出されたデータは、安定したレーザ８の位相を変調して時系列２進位相変調光信号を生成する位相変調器６の制御に使用される。高速位相変調器は、遠隔通信の分野に存在し、きわめて高い入力データ転送速度を処理し得る。しかし、データは任意の形式で入力されることが可能であり、たとえば、振幅変調された電気信号として着信してもよく、これらの信号は位相変調器６の制御に直接使用されてもよい。
【０００８】
位相変調光データ信号は、複数の光チャネルに分けられる。この実施形態において、各光チャネルは光ファイバ長１４１〜１４Ｎを有するが、他の光導波路も使用され得る。光ファイバチャネルの各々は異なる遅延長さを有し、各ファイバを１つ前のファイバと比べたときの遅延の増分が、システムのビットレートに等しい。したがって、ファイバ１４の出力では、第１のファイバがある特定のビットに等価な位相変調信号を出力することになり、遅延の大きい次のファイバが前のビットの位相変調信号を出力することになり、以下同様になる。したがって、各ファイバの出力は信号内の異なるビットとなる。したがって、装置は時系列光信号を並列光位相信号に変換する。光ファイバ以外の光遅延手段も使用され得る。
【０００９】
各ファイバ１４の出力は、レンズ２８によって位相変調空間光変調器（ＳＬＭ）１８の部分に導かれる。空間光変調器１８は、少なくとも１つの参照パターン（またはその反転パターン）、すなわち求められる一部の参照データに対応する参照パターン、に対応する位相変調パターンを表示する。
【００１０】
したがって、ＳＬＭから出る信号のいずれか１つの光チャネルの位相は、入力データの特定ビットに適用される位相変調と参照パターンの部分の位相変調との組合せとなる。入力データと参照データの間に相関がない場合は、得られる光信号における様々なチャネルの位相は不規則に変動することになり、したがって、信号は位相が変動する波面を有することになる。しかし、参照パターンが入力データとぴったり一致する場合は、すべての光チャネルが同じ位相を有することになり、換言すると、平面波面が形成される。
【００１１】
得られる光信号は、レンズ２０によって点検出器２２に集束される。相関がない場合は、１つの位相を有する信号の一部分は、他のチャネルの逆位相（これは２位相システム）に破壊的に干渉することになる。したがって、光信号は検出器２２に強力には集束されないことになる。しかし、相関がある場合は、すべての信号が同相になり、したがって、信号は検出器２２に強力に集束されることになる。したがって、検出器２２で検出される信号の強度は相関を示すものとして使用され得る。
【００１２】
ＳＬＭ１８は複数の参照パターンを表示するように配置されてもよく、この配置は、複数の参照データ列を検索することが望ましい場合や検索文字列が光チャネル数よりも長い場合に有用である。このような場合、光ファイバの出力は、複製光学系１６によって複数のパラレル光信号に複製されてもよい。光ファイバ遅延線１４の出力がリニアアレイとして配置されるものと想像してみよう。複製光学系１６、たとえば、ダンマン（Ｄａｍｍａｎｎ）格子は、横断方向における出力のリニアアレイを複製してもよく、すなわち、各ラインがパラレル光信号のコピーである場合は４０チャネルアレイが４０×４０アレイの出力を構成するために４０回複製され得る。これらの出力は、通常は４０×４０アレイの変調領域に同様に形成されるＳＬＭに導かれることになり、各ラインは特定の参照パターンを表わす。
【００１３】
したがって、前述の相関器装置は、逐次遅延を有する複数の光チャネルに信号を分けることによって、入力順次データをパラレル光データに効果的に変換する。また、参照位相変調は、各光チャネルに適用され、参照データと入力データの間に相関があるときは、各チャネルは光チャネルの干渉結合によって検出され得る位相と同じ位相を有することになる。したがって、この装置は、ＳＬＭまたはＥＯ位相変調器に適用される参照データが特定のデータパターンに対して有効に決定されると高速で動作し得る。しかし、関与する高データ転送速度は、やはり、システムのビットレートで動作し得る位相変調器を必要とする。また、最終検出器と関連処理回路は、システムのビットレートで動作する必要がある。このような部品のコストは高価であり、したがって、可能であれば必要な帯域幅を狭めることが望まれる。
【００１４】
さらに、光学部品の使用には、精密な位置合せを必要とし、定期的な較正と調整が必要となり得る。たとえば、ファイバの遅延は温度に敏感であり、温度変化が位相の変動を引き起こす可能性がある。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
したがって、完全に電子的に動作し、かつ、たとえば１０〜４０Ｇｂｐｓ以上のきわめて高い入力データ転送速度で動作し得るパターン照合装置または相関器が好都合となる。
【課題を解決するための手段】
【００１６】
したがって、本発明によると、入力シリアル２進データ電気信号を受け入れ、これを少なくとも１つのＮチャネル入力パラレル２進データ電気信号に変換するシリアル−パラレル変換手段と、前記入力パラレル信号の各チャネルをＮチャネルパラレル参照２進データ電気信号のチャネルと比較するコンパレータとを有し、パターンが一致するとそれを表示するパターン照合装置が提供される。
【００１７】
シリアル−パラレル変換手段は少なくとも１個の１：Ｎのデマルチプレクサを備えることが好ましい。デマルチプレクサは、シリアル−パラレル変換を実行する周知の１つの装置であり、シリアル−パラレル変換器として知られることもある。デマルチプレクサは、入力データストリームを受け入れる入力とＮ個の異なる出力を有する。デマルチプレクサは、受け入れられた各ビットを保存し、Ｎビットを保存した時点でＮ個の出力の各々に保存済みＮビットを１つずつ出力する。次に、デマルチプレクサは入力信号から次のＮビットを保存する。こうして、時系列すなわちシリアル入力データストリームのＮビットは、パラレルデータ信号に変換される。
【００１８】
したがって、デマルチプレクサは、Ｎビットを受け入れた後で信号を出力するだけであり、したがってデマルチプレクサからの出力レートは入力データストリームのビットレートの１／Ｎに低下する。したがって、入力データのビットレートがどうであれ、デマルチプレクサを使用すると、後に続く更新レートが１／Ｎに低下し、システム要件が緩和され、したがって市販の部品が使用され得る。
【００１９】
市販のマルチプレクサの多く（問題とする入力データレートが約１０〜４０Ｇｂｐｓまたはおそらくそれ以上の）は、１：４、１：８、または１：１６のデマルチプレクサに制限される傾向がある。好ましくは市販のデマルチプレクサが使用され、好都合には１：８のデマルチプレクサが使用される。
【００２０】
８パラレルチャネルは有用なパターン照合用として一般にチャネル数が十分でなく、さらに多くのチャネルが一般に必要とされる。したがって、好ましくは、１：Ｎデマルチプレクサの各出力は一連のラッチ回路に接続され、ラッチ回路はデマルチプレクサの出力レートでクロック駆動され、各ラッチ回路は出力チャネルを有する。ラッチ回路は、実際には、複数の出力を有するシフトレジスタを形成する。一連のラッチ回路の作用は、特定チャネルの出力を種々の遅延時間で反復することである。
【００２１】
したがって、特定出力チャネルのデマルチプレクサの出力は、一連のラッチ回路の第１ラッチ回路に行く。ラッチ回路は、デマルチプレクサの出力レートでクロック駆動され、各クロックパルスでデータはチェーン内の次のラッチ回路に移動され、さらに出力チャネルに出力される。デマルチプレクサの１つの特定出力チャネルを考えてみよう。時刻ｔ０において、この出力のデータは一連のラッチ回路の第１ラッチ回路に行き、さらに第１の出力チャネルに行く。次の時刻ｔ１において、第１ラッチ回路に保存されたデータの値はチェーン内の第２ラッチ回路に移され、さらに第２の出力チャネルに出力される。次の時刻ｔ２において、データの値は次のラッチ回路に移され、さらに別の出力チャネルに移される。したがって、いずれのクロックパルスでも一連のラッチ回路の第１ラッチ回路は保持するデータ値を出力しており、第２ラッチ回路は前のデータ値を出力しており、以下同様であることが分かる。したがって、ラッチ回路は電気ドメインで一連の（クロックド）遅延の機能を果たし、前述の光ファイバ遅延と同様に動作する。したがって、１：８デマルチプレクサは、４０ビット出力を発生する８出力の各々で一連の４つのラッチ回路とともに使用され得る。
【００２２】
低い入力データ転送速度で一連のラッチ回路を使用すると、一連の電気的遅延を提供する機会が与えられてマルチプレクサを必要とせずにシリアル−パラレル変換が実行されることに留意されたい。たとえば、実際のビットレートで順次クロック駆動される一連の３９個のラッチ回路は、各回路間にタップ点を有し、４０ビット長のシーケンスをパラレル電気信号に直接変換する。したがって、シリアル−パラレル変換手段は、各ラッチ回路が出力チャネルを有する一連のラッチ回路を備えるだけでよい。
【００２３】
しかし、前述のように、高データ転送速度ではラッチ回路はそれほど高速で動作することができない場合があり、デマルチプレクサを使用することによってラッチ回路と後続回路が動作するクロックレートが低下する。
【００２４】
したがって、シリアル−パラレル変換手段は、入力シリアル２進信号をＮチャネルパラレル２進信号に変換する。このパラレル信号はＮチャネル参照信号と比較される。参照信号は求められるデータパターンに対応し、所望の検索タームが変化するまでは不変である。したがって、装置は参照データパターンを保存し適切な２進値を各チャネルに出力するＮチャネル出力メモリ手段を備えてもよい。
【００２５】
コンパレータは、パラレル入力信号の各チャネルの２進値を参照信号の関連チャネルの値と比較する。比較は様々な方法で行なわれ得るが、好ましくは、ビット加算（ビット減算を含む）を実行することによって機能する。単一ビット出力の場合、同じ２進値を加算するとゼロが得られ、異なる２進値を加算すると値１が得られ、すなわち、２進値１＋２進値１＝２進値０、２進値０＋２進値０＝２進値０となることは２進法の特性である。しかし、不一致の場合は値が１になり、２進値１＋２進値０＝２進値１で２進値０＋２進値１＝２進値１である。
【００２６】
したがって、各チャネルに対する入力データのデータ値と関連参照データとの論理結合を実行すると、一致がある場合は０を発生し、一致がない場合は１を発生することになる。
【００２７】
各チャネルに対するビットの加算は、排他的ＯＲ（ＸＯＲ）による論理配列を使って実行されてデータ信号と参照信号の値を結合する。
【００２８】
完全な一致がある場合、各チャネルの結合結果はゼロになる。したがって、ゼロ出力の検出は、パターンの一致を示すものとして利用され得る。ゼロは様々な方法で検出され得る。たとえば、さらなる論理演算が採用され得る。一実施形態において、加算／差分またはレベル検出が使用される。加算回路は、すべてのＸＯＲゲートの出力に接続された加算抵抗器と、並列のすべての加算抵抗器に接続されたトランスインピーダンス増幅器（ＴＩＡ）を備えてもよい。ＴＩＡの出力に配置されるコンパレータは、ゼロ結果が検出されたときにトリガ信号を発生してもよい。
【００２９】
様々なパラレル入力信号が種々の参照パターンと比較され得るように、装置は入力データに基づく複数のパラレルデータ信号を生成するように配置されてもよい。これを実現する方法はいろいろある。入力シリアル信号は複数の異なる装置に渡され得る。あるいは、この入力信号はシリアル−パラレル変換手段によってパラレル信号に変換された後、各チャネルは複数のコンパレータに渡され、各コンパレータは異なる参照パターンと比較する。
【００３０】
一部のアプリケーションにおいて、検索対象となるデータは複数の異なる参照データ信号を必要とする。換言すると、入力データの検索範囲では、ある１つの参照パターンのすぐ後に別の参照パターンが現れる必要がある。特定の検索タームが複数の異なる参照パターンを備えてもよい。たとえば、パターン照合装置が４０のパラレルチャネルを有するものとしよう。検索タームが１２０ビット長であれば、これは３つの参照データ信号に広げられることになる。参照パターン１が現れた後に参照パターン２が続きさらに参照パターン３が続くとき、装置は単に一致を発生するように構成されてもよい。もちろん、入力シリアルデータの順次データからパターンが一致するようにするために、タイミングが正しくなければならない。したがって、パターン１が一致してから、ビット周期の４０倍に等しい時間後にパターン２が一致しなければならないことになる。
【００３１】
デマルチプレクサを使用することはパターン照合装置がデータの一部のスナップショットを見ているにすぎないこと当業者は理解されよう。たとえば、１：８デマルチプレクサが使用され、ラッチ回路がチャネル数を４０に拡大する場合を考えてみよう。シリアル信号が受け取られると、第１の完全パラレル信号は入力信号のビット１〜４０に対応することになる。デマルチプレクサは入力ビットレートの１／８のレートで出力するだけであるため、これらの値はビット周期の８倍の期間にわたって持続することになる。この時間後、出力は変化することになり、パラレル信号はここで入力信号のビット９〜４８に対応することになる。次に更新されるパラレル信号はビット１７〜５６を備えることになり、以下同様になる。
【００３２】
したがって、デマルチプレクサを含む前述のパターン照合装置は、入力データに現れることがあってもパラレル信号として形成されることになるシーケンスに対応しないビットシーケンスに対してパターン一致を発生することができないことになる。たとえば、参照パターンが実際にビットシーケンス１１〜５０に一致しなかった場合に上述の例を続けると、ビット１１〜５０に対応するパラレル信号が形成されないため一致が検出されないことになる。
【００３３】
しかし、いくつかのアプリケーションでは、データが任意でなく有意味な形式で配置されることになる。ディジタルデータは、一般に、バイト形式（８ビットの情報）で転送され、しかも実際には情報の全バイトに対応するシーケンスを検索することしか望まれないであろうということを当業者は理解されよう。あるバイトの末端部と次のバイトの先頭部に基づいて参照データと入力データの相関を検出すると誤検出となる。したがって、デマルチプレクサを使用すると、データの有意味なシーケンスのみが相関に使用可能になり、しかもすべての有意味な組合せが提示されるようにすることができる。したがって、デマルチプレクサとラッチ回路は、整合状態を確保するためにバイト境界コントローラによって制御されることが好ましい。
【００３４】
デマルチプレクサが使用されずにシリアル−パラレル変換が単に一連のラッチ回路によって実行される場合、パラレル信号は１ビットずつ更新されることになり、４０ビット（４０チャネル装置の場合）のすべてのシーケンスが考慮されることに留意されたい。
【００３５】
したがって、本発明は、たとえば、１０〜４０Ｇｂｐｓ以上の高データ転送速度で動作可能なすべての電子パターン照合装置を実現する。１個の電子装置として、この装置はＡＳＩＣなどの単一チップで実現され得る。
【００３６】
本発明は、以下で、図面を参照して単なる例として説明される。
【発明を実施するための最良の形態】
【００３７】
図１は、同時係属中の国際特許出願第ＰＣＴ／ＧＢ２００５／００４０２８号明細書および英国特許出願第ＧＢ０４２３０９３．４号明細書に記載されているような相関装置を示す。この相関器の動作は前述されている。
【００３８】
図２は、本発明によるパターン照合装置を示す。前述の相関器に類似した部品が使用される場合は、同じ参照符号を付けている。
【００３９】
振幅変調電気信号方式の入力データ信号４０は、１：８デマルチプレクサ３０に受け入れられる。当業者は、インファイ社（Ｉｎｐｈｉ）製５０８１ＤＸ ５０ Ｇｂｐｓの１：４デマルチプレクサまたはブロードコム社（Ｂｒｏａｄｃｏｍ）製ＢＣＭ８１２５の１：１６デマルチプレクサなど、特定の要求に対して使用され得るデマルチプレクサを知っているであろう。デマルチプレクサ３０は、バイト境界トリガ３２によって制御され、一連の入力データの８ビットバイトを８チャネルパラレルデータ信号に変換する。したがって、入力データのビットレートの１／８のレートで、デマルチプレクサ３０はその８出力チャネルの各々に異なるビット値を出力する（見やすいように３チャネルのみが示されていることに留意されたい）。
【００４０】
デマルチプレクサ３２の各出力は、コンパレータに渡されるパラレル電気信号の１チャネルを形成するために使用され、したがって、排他的ＯＲ（ＸＯＲ）論理ゲート７２の１つの入力に渡される。さらに、デマルチプレクサ３２の各出力は一連の４つのラッチ回路６２１〜６２４の入力にも接続される。各ラッチ回路は次のラッチ回路に接続される。さらに、各ラッチ回路の出力は、パラレル信号の別のチャネルとしても利用され、ＸＯＲゲート７２の入力に接続される。また、ラッチ回路６２はバイト境界コントローラ３２によって制御され、この一連の回路（ｔｈｅ ｓｅｒｉｅｓ）はシフトレジスタの機能を果たす。したがって、デマルチプレクサからのデータ値出力は、この一連の回路に沿って次々と伝達される。更新時には常に、デマルチプレクサからのデータ値出力は、ＸＯＲゲート７２の１つの入力に渡される。同時に、各チャネルの一連の回路の第１ラッチ回路は前のデータを異なるＸＯＲゲートの入力に出力することになり、各一連の回路の第２ラッチ回路は前のデータを異なるＸＯＲゲートの入力に出力することになり、以下同様になる。したがって、４０チャネルの電気信号は４０個のＸＯＲゲート７２の入力に形成される。
【００４１】
ＸＯＲゲートのアレイは、パラレル入力信号の各チャネルの２進データ値を参照パラレル信号からの２進値と比較するコンパレータへの入力を形成する。
【００４２】
参照パラレル信号は、ワード−ビット変換器７０によって形成される。
【００４３】
相関は、ビット加算に基づいて、すなわち、入力データの特定ビットが関連参照ビットに一致する場合に和がゼロになるが不一致があると和が１になるという原則に基づいて実行される。したがって、完全一致の場合、全チャネルの全出力の和は、ゼロになるべきで、ゼロよりも大きい値は不一致を示す。
【００４４】
図１を参照して説明された光相関器は様々な光チャネルの光出力を結合することによって動作し、その結果、光出力は振幅の２乗であるという長所が生かされることに留意されたい。この特性は、完全一致と完全に近い一致との間の強度差を明確にするものである。
【００４５】
たとえば、４０チャネルの光システムを考えてみよう。全チャネルが結合器でＡの振幅を有しかつすべて同相であれば、得られる振幅は４０Ａであるが、光出力（測定値）は（４０Ａ）２である。１ビットのみが逆位相であれば、得られる振幅は３８Ａ（１ビットは寄与しないだけでなく破壊的に干渉する）となるが、出力は（３８Ａ）２となる。したがって、１ビットの不正がある場合は、光出力が完全一致と比べて約１０％低下する。したがって、光出力を使用する仕組みは、完全に近い一致と完全一致を区別する際に好都合となる。
【００４６】
交流波のコヒーレントな組合せを使用することによって同じ効果を生むことが可能となる。あるいは、直流電流の直接加算が採用され得る（だが、当然、２乗機能の利点はない）。しかし、ビット加算は、実施が簡単であるだけでなくゼロ出力で一致する場合が生じるという利点を有する。前述の光相関器では、一致する場合が最大強度で生じ、したがって閾値が必要である。閾値はシステムのノイズに敏感である。ビット加算は２進であり、ゼロが真のゼロであるとすれば、１に対応する直流電圧のドリフトはほとんど問題ではなくなる。
【００４７】
ビット加算はＸＯＲ論理配列７２によって実行される。ＸＯＲゲートは、入力の両方でなくいずれか一方が値１のとき、値１を出力する。換言すると、真理値表は下記の通りである。
【表１】
【００４８】
この表は、ＸＯＲゲートへの両入力が一致するとき、すなわち、入力データの関連ビットが参照データの関連ビットに一致するとき所要の結果を示し出力はゼロであるが、一致しないときは出力が１である。
【００４９】
したがって、各ＸＯＲゲート７２の出力は完全に一致する場合にゼロである。各出力がゼロであることは、加算／差分回路を使って検出される。各ＸＯＲゲート７２の出力は加算抵抗器７４に接続され、ピーク／ディップ検出回路７４はゼロ和を検出する。
【００５０】
ピーク／ディップ検出回路７４は、図３にさらに詳しく示される。全ＸＯＲゲート７２からの結合入力はトランスインピーダンス増幅器８０および抵抗器８２に入力される。ＴＩＡの出力はピークホールド回路８２およびコンパレータ８４に行く。この回路は、完全一致を示すゼロ和をトリガするように配置される。
【００５１】
「ヒット率」は入力データ転送速度をはるかに下回ることになり、さらに、検索にはいくぶん長いパターン長が必要になることが予想される。１００％の一致（ゼロ差）を検出するに当り、場合によっては他の文字列も検出される「データページ長」に対応するある時間にわたって出力をハイに保つ「パルスストレッチャ」８６が設計される。このフラグが最初の一致検出の前と後の両方で実際にハイに保たれるように外部遅延が用意されて、これと求められている別の文字列に対応した同様の伸長パルスとの間で重なりが生じ得るようにされてもよい。
【００５２】
前述の「チップ上の検索エンジン」は、少数の（おそらく、モジュール当りたった１つ）の文字列を超高速で検索し得るが、おそらく一致の検出前に始まり検出後しばらく続くパルスの形のフラグを出力する。この大幅に低減された帯域幅の信号は、「データページ長」として定められる領域に求められる一群の文字列の出現にフラグを設定するために、他のパラレルチャネルからの他の電子信号と容易に結合され得る。
【００５３】
この技術はＡＳＩＣ型チップ上で実現され得るので、多くのチャネルの並列処理が可能である。
【図面の簡単な説明】
【００５４】
【図１】同時係属中の国際特許出願第ＰＣＴ／ＧＢ２００５／００４０２８号明細書および英国特許出願第ＧＢ０４２３０９３．４号明細書に記載されるような光相関器を示す。
【図２】本発明による全電子式の相関器を示す。
【図３】適切なピーク／ディップ検出回路を示す。
【技術分野】
【０００１】
本発明は、パターン認識用の電子装置、すなわち、検索データと参照データの相関のための電子装置に関し、特に、パターン照合を実行するために時系列データストリームをパラレルデータパターンに変換する電子装置に関する。
【背景技術】
【０００２】
パターン認識は、テキストまたは画像などの受信データの１つまたは複数の知られているオブジェクトを、知られている参照オブジェクトとそのデータを比較することによって認識するプロセスに関するものである。パターン認識を自発的に実行する理想的な方法は、相関の数学的演算によるものである。
【０００３】
パターン認識は、具体的な検索タームを探す問合せデータベースから生体ベースの認識システムおよび二次元画像の目標認識に至る多くの領域で使用される。一般に、検索は、知られている参照データ列を照合確認する検索対象データと比較するために適切にプログラムされたプロセッサを使ってディジタル的に実行される。一例は、１つまたは複数の入力参照タームをインターネットデータと比較して照合確認するインターネット検索エンジンである。
【０００４】
しかし、膨大な量のデータを検索する際は、ソフトウェアベースのパターン識別法は遅いことがあり、あるいは膨大な処理能力を必要とすることがある。また、遠隔通信のデータ転送速度などにおいて、データが高データ転送速度で受信されるときは、この速度で相関を実行するソフトウェアベースシステムが無効なこともある。
【０００５】
整合フィルタや相関器として知られる光学パターン認識システムも、知られており、空間パターンの照合に使用され得る。最も初期のこうした仕組みの１つは、ファンデルルクト（Ｖａｎｄｅｒ Ｌｕｇｔ）光整合フィルタであり、Ａ Ｖａｎｄｅｒ Ｌｕｇｔ，「Ｓｉｇｎａｌ ｄｅｔｅｃｔｉｏｎ ｂｙ ｃｏｍｐｌｅｘ ｓｐａｔｉａｌ ｆｉｌｔｅｒｉｎｇ」，ＩＥＥＥ ｔｒａｎｓ．Ｉｎｆ．Ｔｈｅｏｒｙ ＩＴ−１０，ｐ１３９−１４５（１９６４）に記載されている。このシステムでは、結合パターンに対して逆フーリエ変換を実行する前に参照パターンの共役フーリエ変換によって場面のフーリエ変換を展開する光学装置を使用する。参照画像（ｒｅｆｅｒｅｎｃｅ）と画像の間に強い相関が存在する場合は、鋭く明るいピークがシステムの後焦点面に出現する。したがって、このシステムは観測画像を参照画像と比較して相関があるかどうかを示し、相関があれば、どこに出現するか、すなわち、システムは場面における目標の存在と場所を認識する。最近の光学パターン認識システムは、場面のフーリエ変換（ＦＴ）を実行し、パターンを電子的に参照し、結合ＦＴを空間光変調器（ＳＬＭ）に表示して動作を簡素化し高速化する（たとえば、国際公開第００／１７８０９号パンフレットに記載された相関器を参照されたい）。このような光学パターン認識システムは、観測場面などにおける目標認識には役立つが、検索データの保存場所については、検索対象データまたは結合データおよび参照パターンのいずれかによるＳＬＭの更新を必要とする。高速ＳＬＭを使用した場合でも、ＳＬＭの更新速度はそのアプリケーションに関する相関速度を制限する。本明細書で使用される用語の相関器は整合フィルタベースシステムを含むものと解釈されて差し支えないことに留意されたい。
【０００６】
近年、光相関の利点を高速パターン照合に適用することが提案されている。本出願人の同時係属中の国際特許出願第ＰＣＴ／ＧＢ２００５／００４０２８号明細書および英国特許出願第ＧＢ０４２３０９３．４号明細書には、高速位相変調および並列光処理を使用して高速相関を可能とする相関器装置が記載されている。
【０００７】
図１は、この高速光相関器の第１の実施形態を示す。相関器は、時系列、すなわち順次入力データストリーム２に作用する。このデータストリームは、たとえば、遠隔通信に使用されるような振幅変調２進光信号の形態であってもよく、また特定データの存在に対して検索の対象となるデータベースからの流れであってもよい。振幅変調入力信号２は、光検出器４によって検出される。検出されたデータは、安定したレーザ８の位相を変調して時系列２進位相変調光信号を生成する位相変調器６の制御に使用される。高速位相変調器は、遠隔通信の分野に存在し、きわめて高い入力データ転送速度を処理し得る。しかし、データは任意の形式で入力されることが可能であり、たとえば、振幅変調された電気信号として着信してもよく、これらの信号は位相変調器６の制御に直接使用されてもよい。
【０００８】
位相変調光データ信号は、複数の光チャネルに分けられる。この実施形態において、各光チャネルは光ファイバ長１４１〜１４Ｎを有するが、他の光導波路も使用され得る。光ファイバチャネルの各々は異なる遅延長さを有し、各ファイバを１つ前のファイバと比べたときの遅延の増分が、システムのビットレートに等しい。したがって、ファイバ１４の出力では、第１のファイバがある特定のビットに等価な位相変調信号を出力することになり、遅延の大きい次のファイバが前のビットの位相変調信号を出力することになり、以下同様になる。したがって、各ファイバの出力は信号内の異なるビットとなる。したがって、装置は時系列光信号を並列光位相信号に変換する。光ファイバ以外の光遅延手段も使用され得る。
【０００９】
各ファイバ１４の出力は、レンズ２８によって位相変調空間光変調器（ＳＬＭ）１８の部分に導かれる。空間光変調器１８は、少なくとも１つの参照パターン（またはその反転パターン）、すなわち求められる一部の参照データに対応する参照パターン、に対応する位相変調パターンを表示する。
【００１０】
したがって、ＳＬＭから出る信号のいずれか１つの光チャネルの位相は、入力データの特定ビットに適用される位相変調と参照パターンの部分の位相変調との組合せとなる。入力データと参照データの間に相関がない場合は、得られる光信号における様々なチャネルの位相は不規則に変動することになり、したがって、信号は位相が変動する波面を有することになる。しかし、参照パターンが入力データとぴったり一致する場合は、すべての光チャネルが同じ位相を有することになり、換言すると、平面波面が形成される。
【００１１】
得られる光信号は、レンズ２０によって点検出器２２に集束される。相関がない場合は、１つの位相を有する信号の一部分は、他のチャネルの逆位相（これは２位相システム）に破壊的に干渉することになる。したがって、光信号は検出器２２に強力には集束されないことになる。しかし、相関がある場合は、すべての信号が同相になり、したがって、信号は検出器２２に強力に集束されることになる。したがって、検出器２２で検出される信号の強度は相関を示すものとして使用され得る。
【００１２】
ＳＬＭ１８は複数の参照パターンを表示するように配置されてもよく、この配置は、複数の参照データ列を検索することが望ましい場合や検索文字列が光チャネル数よりも長い場合に有用である。このような場合、光ファイバの出力は、複製光学系１６によって複数のパラレル光信号に複製されてもよい。光ファイバ遅延線１４の出力がリニアアレイとして配置されるものと想像してみよう。複製光学系１６、たとえば、ダンマン（Ｄａｍｍａｎｎ）格子は、横断方向における出力のリニアアレイを複製してもよく、すなわち、各ラインがパラレル光信号のコピーである場合は４０チャネルアレイが４０×４０アレイの出力を構成するために４０回複製され得る。これらの出力は、通常は４０×４０アレイの変調領域に同様に形成されるＳＬＭに導かれることになり、各ラインは特定の参照パターンを表わす。
【００１３】
したがって、前述の相関器装置は、逐次遅延を有する複数の光チャネルに信号を分けることによって、入力順次データをパラレル光データに効果的に変換する。また、参照位相変調は、各光チャネルに適用され、参照データと入力データの間に相関があるときは、各チャネルは光チャネルの干渉結合によって検出され得る位相と同じ位相を有することになる。したがって、この装置は、ＳＬＭまたはＥＯ位相変調器に適用される参照データが特定のデータパターンに対して有効に決定されると高速で動作し得る。しかし、関与する高データ転送速度は、やはり、システムのビットレートで動作し得る位相変調器を必要とする。また、最終検出器と関連処理回路は、システムのビットレートで動作する必要がある。このような部品のコストは高価であり、したがって、可能であれば必要な帯域幅を狭めることが望まれる。
【００１４】
さらに、光学部品の使用には、精密な位置合せを必要とし、定期的な較正と調整が必要となり得る。たとえば、ファイバの遅延は温度に敏感であり、温度変化が位相の変動を引き起こす可能性がある。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
したがって、完全に電子的に動作し、かつ、たとえば１０〜４０Ｇｂｐｓ以上のきわめて高い入力データ転送速度で動作し得るパターン照合装置または相関器が好都合となる。
【課題を解決するための手段】
【００１６】
したがって、本発明によると、入力シリアル２進データ電気信号を受け入れ、これを少なくとも１つのＮチャネル入力パラレル２進データ電気信号に変換するシリアル−パラレル変換手段と、前記入力パラレル信号の各チャネルをＮチャネルパラレル参照２進データ電気信号のチャネルと比較するコンパレータとを有し、パターンが一致するとそれを表示するパターン照合装置が提供される。
【００１７】
シリアル−パラレル変換手段は少なくとも１個の１：Ｎのデマルチプレクサを備えることが好ましい。デマルチプレクサは、シリアル−パラレル変換を実行する周知の１つの装置であり、シリアル−パラレル変換器として知られることもある。デマルチプレクサは、入力データストリームを受け入れる入力とＮ個の異なる出力を有する。デマルチプレクサは、受け入れられた各ビットを保存し、Ｎビットを保存した時点でＮ個の出力の各々に保存済みＮビットを１つずつ出力する。次に、デマルチプレクサは入力信号から次のＮビットを保存する。こうして、時系列すなわちシリアル入力データストリームのＮビットは、パラレルデータ信号に変換される。
【００１８】
したがって、デマルチプレクサは、Ｎビットを受け入れた後で信号を出力するだけであり、したがってデマルチプレクサからの出力レートは入力データストリームのビットレートの１／Ｎに低下する。したがって、入力データのビットレートがどうであれ、デマルチプレクサを使用すると、後に続く更新レートが１／Ｎに低下し、システム要件が緩和され、したがって市販の部品が使用され得る。
【００１９】
市販のマルチプレクサの多く（問題とする入力データレートが約１０〜４０Ｇｂｐｓまたはおそらくそれ以上の）は、１：４、１：８、または１：１６のデマルチプレクサに制限される傾向がある。好ましくは市販のデマルチプレクサが使用され、好都合には１：８のデマルチプレクサが使用される。
【００２０】
８パラレルチャネルは有用なパターン照合用として一般にチャネル数が十分でなく、さらに多くのチャネルが一般に必要とされる。したがって、好ましくは、１：Ｎデマルチプレクサの各出力は一連のラッチ回路に接続され、ラッチ回路はデマルチプレクサの出力レートでクロック駆動され、各ラッチ回路は出力チャネルを有する。ラッチ回路は、実際には、複数の出力を有するシフトレジスタを形成する。一連のラッチ回路の作用は、特定チャネルの出力を種々の遅延時間で反復することである。
【００２１】
したがって、特定出力チャネルのデマルチプレクサの出力は、一連のラッチ回路の第１ラッチ回路に行く。ラッチ回路は、デマルチプレクサの出力レートでクロック駆動され、各クロックパルスでデータはチェーン内の次のラッチ回路に移動され、さらに出力チャネルに出力される。デマルチプレクサの１つの特定出力チャネルを考えてみよう。時刻ｔ０において、この出力のデータは一連のラッチ回路の第１ラッチ回路に行き、さらに第１の出力チャネルに行く。次の時刻ｔ１において、第１ラッチ回路に保存されたデータの値はチェーン内の第２ラッチ回路に移され、さらに第２の出力チャネルに出力される。次の時刻ｔ２において、データの値は次のラッチ回路に移され、さらに別の出力チャネルに移される。したがって、いずれのクロックパルスでも一連のラッチ回路の第１ラッチ回路は保持するデータ値を出力しており、第２ラッチ回路は前のデータ値を出力しており、以下同様であることが分かる。したがって、ラッチ回路は電気ドメインで一連の（クロックド）遅延の機能を果たし、前述の光ファイバ遅延と同様に動作する。したがって、１：８デマルチプレクサは、４０ビット出力を発生する８出力の各々で一連の４つのラッチ回路とともに使用され得る。
【００２２】
低い入力データ転送速度で一連のラッチ回路を使用すると、一連の電気的遅延を提供する機会が与えられてマルチプレクサを必要とせずにシリアル−パラレル変換が実行されることに留意されたい。たとえば、実際のビットレートで順次クロック駆動される一連の３９個のラッチ回路は、各回路間にタップ点を有し、４０ビット長のシーケンスをパラレル電気信号に直接変換する。したがって、シリアル−パラレル変換手段は、各ラッチ回路が出力チャネルを有する一連のラッチ回路を備えるだけでよい。
【００２３】
しかし、前述のように、高データ転送速度ではラッチ回路はそれほど高速で動作することができない場合があり、デマルチプレクサを使用することによってラッチ回路と後続回路が動作するクロックレートが低下する。
【００２４】
したがって、シリアル−パラレル変換手段は、入力シリアル２進信号をＮチャネルパラレル２進信号に変換する。このパラレル信号はＮチャネル参照信号と比較される。参照信号は求められるデータパターンに対応し、所望の検索タームが変化するまでは不変である。したがって、装置は参照データパターンを保存し適切な２進値を各チャネルに出力するＮチャネル出力メモリ手段を備えてもよい。
【００２５】
コンパレータは、パラレル入力信号の各チャネルの２進値を参照信号の関連チャネルの値と比較する。比較は様々な方法で行なわれ得るが、好ましくは、ビット加算（ビット減算を含む）を実行することによって機能する。単一ビット出力の場合、同じ２進値を加算するとゼロが得られ、異なる２進値を加算すると値１が得られ、すなわち、２進値１＋２進値１＝２進値０、２進値０＋２進値０＝２進値０となることは２進法の特性である。しかし、不一致の場合は値が１になり、２進値１＋２進値０＝２進値１で２進値０＋２進値１＝２進値１である。
【００２６】
したがって、各チャネルに対する入力データのデータ値と関連参照データとの論理結合を実行すると、一致がある場合は０を発生し、一致がない場合は１を発生することになる。
【００２７】
各チャネルに対するビットの加算は、排他的ＯＲ（ＸＯＲ）による論理配列を使って実行されてデータ信号と参照信号の値を結合する。
【００２８】
完全な一致がある場合、各チャネルの結合結果はゼロになる。したがって、ゼロ出力の検出は、パターンの一致を示すものとして利用され得る。ゼロは様々な方法で検出され得る。たとえば、さらなる論理演算が採用され得る。一実施形態において、加算／差分またはレベル検出が使用される。加算回路は、すべてのＸＯＲゲートの出力に接続された加算抵抗器と、並列のすべての加算抵抗器に接続されたトランスインピーダンス増幅器（ＴＩＡ）を備えてもよい。ＴＩＡの出力に配置されるコンパレータは、ゼロ結果が検出されたときにトリガ信号を発生してもよい。
【００２９】
様々なパラレル入力信号が種々の参照パターンと比較され得るように、装置は入力データに基づく複数のパラレルデータ信号を生成するように配置されてもよい。これを実現する方法はいろいろある。入力シリアル信号は複数の異なる装置に渡され得る。あるいは、この入力信号はシリアル−パラレル変換手段によってパラレル信号に変換された後、各チャネルは複数のコンパレータに渡され、各コンパレータは異なる参照パターンと比較する。
【００３０】
一部のアプリケーションにおいて、検索対象となるデータは複数の異なる参照データ信号を必要とする。換言すると、入力データの検索範囲では、ある１つの参照パターンのすぐ後に別の参照パターンが現れる必要がある。特定の検索タームが複数の異なる参照パターンを備えてもよい。たとえば、パターン照合装置が４０のパラレルチャネルを有するものとしよう。検索タームが１２０ビット長であれば、これは３つの参照データ信号に広げられることになる。参照パターン１が現れた後に参照パターン２が続きさらに参照パターン３が続くとき、装置は単に一致を発生するように構成されてもよい。もちろん、入力シリアルデータの順次データからパターンが一致するようにするために、タイミングが正しくなければならない。したがって、パターン１が一致してから、ビット周期の４０倍に等しい時間後にパターン２が一致しなければならないことになる。
【００３１】
デマルチプレクサを使用することはパターン照合装置がデータの一部のスナップショットを見ているにすぎないこと当業者は理解されよう。たとえば、１：８デマルチプレクサが使用され、ラッチ回路がチャネル数を４０に拡大する場合を考えてみよう。シリアル信号が受け取られると、第１の完全パラレル信号は入力信号のビット１〜４０に対応することになる。デマルチプレクサは入力ビットレートの１／８のレートで出力するだけであるため、これらの値はビット周期の８倍の期間にわたって持続することになる。この時間後、出力は変化することになり、パラレル信号はここで入力信号のビット９〜４８に対応することになる。次に更新されるパラレル信号はビット１７〜５６を備えることになり、以下同様になる。
【００３２】
したがって、デマルチプレクサを含む前述のパターン照合装置は、入力データに現れることがあってもパラレル信号として形成されることになるシーケンスに対応しないビットシーケンスに対してパターン一致を発生することができないことになる。たとえば、参照パターンが実際にビットシーケンス１１〜５０に一致しなかった場合に上述の例を続けると、ビット１１〜５０に対応するパラレル信号が形成されないため一致が検出されないことになる。
【００３３】
しかし、いくつかのアプリケーションでは、データが任意でなく有意味な形式で配置されることになる。ディジタルデータは、一般に、バイト形式（８ビットの情報）で転送され、しかも実際には情報の全バイトに対応するシーケンスを検索することしか望まれないであろうということを当業者は理解されよう。あるバイトの末端部と次のバイトの先頭部に基づいて参照データと入力データの相関を検出すると誤検出となる。したがって、デマルチプレクサを使用すると、データの有意味なシーケンスのみが相関に使用可能になり、しかもすべての有意味な組合せが提示されるようにすることができる。したがって、デマルチプレクサとラッチ回路は、整合状態を確保するためにバイト境界コントローラによって制御されることが好ましい。
【００３４】
デマルチプレクサが使用されずにシリアル−パラレル変換が単に一連のラッチ回路によって実行される場合、パラレル信号は１ビットずつ更新されることになり、４０ビット（４０チャネル装置の場合）のすべてのシーケンスが考慮されることに留意されたい。
【００３５】
したがって、本発明は、たとえば、１０〜４０Ｇｂｐｓ以上の高データ転送速度で動作可能なすべての電子パターン照合装置を実現する。１個の電子装置として、この装置はＡＳＩＣなどの単一チップで実現され得る。
【００３６】
本発明は、以下で、図面を参照して単なる例として説明される。
【発明を実施するための最良の形態】
【００３７】
図１は、同時係属中の国際特許出願第ＰＣＴ／ＧＢ２００５／００４０２８号明細書および英国特許出願第ＧＢ０４２３０９３．４号明細書に記載されているような相関装置を示す。この相関器の動作は前述されている。
【００３８】
図２は、本発明によるパターン照合装置を示す。前述の相関器に類似した部品が使用される場合は、同じ参照符号を付けている。
【００３９】
振幅変調電気信号方式の入力データ信号４０は、１：８デマルチプレクサ３０に受け入れられる。当業者は、インファイ社（Ｉｎｐｈｉ）製５０８１ＤＸ ５０ Ｇｂｐｓの１：４デマルチプレクサまたはブロードコム社（Ｂｒｏａｄｃｏｍ）製ＢＣＭ８１２５の１：１６デマルチプレクサなど、特定の要求に対して使用され得るデマルチプレクサを知っているであろう。デマルチプレクサ３０は、バイト境界トリガ３２によって制御され、一連の入力データの８ビットバイトを８チャネルパラレルデータ信号に変換する。したがって、入力データのビットレートの１／８のレートで、デマルチプレクサ３０はその８出力チャネルの各々に異なるビット値を出力する（見やすいように３チャネルのみが示されていることに留意されたい）。
【００４０】
デマルチプレクサ３２の各出力は、コンパレータに渡されるパラレル電気信号の１チャネルを形成するために使用され、したがって、排他的ＯＲ（ＸＯＲ）論理ゲート７２の１つの入力に渡される。さらに、デマルチプレクサ３２の各出力は一連の４つのラッチ回路６２１〜６２４の入力にも接続される。各ラッチ回路は次のラッチ回路に接続される。さらに、各ラッチ回路の出力は、パラレル信号の別のチャネルとしても利用され、ＸＯＲゲート７２の入力に接続される。また、ラッチ回路６２はバイト境界コントローラ３２によって制御され、この一連の回路（ｔｈｅ ｓｅｒｉｅｓ）はシフトレジスタの機能を果たす。したがって、デマルチプレクサからのデータ値出力は、この一連の回路に沿って次々と伝達される。更新時には常に、デマルチプレクサからのデータ値出力は、ＸＯＲゲート７２の１つの入力に渡される。同時に、各チャネルの一連の回路の第１ラッチ回路は前のデータを異なるＸＯＲゲートの入力に出力することになり、各一連の回路の第２ラッチ回路は前のデータを異なるＸＯＲゲートの入力に出力することになり、以下同様になる。したがって、４０チャネルの電気信号は４０個のＸＯＲゲート７２の入力に形成される。
【００４１】
ＸＯＲゲートのアレイは、パラレル入力信号の各チャネルの２進データ値を参照パラレル信号からの２進値と比較するコンパレータへの入力を形成する。
【００４２】
参照パラレル信号は、ワード−ビット変換器７０によって形成される。
【００４３】
相関は、ビット加算に基づいて、すなわち、入力データの特定ビットが関連参照ビットに一致する場合に和がゼロになるが不一致があると和が１になるという原則に基づいて実行される。したがって、完全一致の場合、全チャネルの全出力の和は、ゼロになるべきで、ゼロよりも大きい値は不一致を示す。
【００４４】
図１を参照して説明された光相関器は様々な光チャネルの光出力を結合することによって動作し、その結果、光出力は振幅の２乗であるという長所が生かされることに留意されたい。この特性は、完全一致と完全に近い一致との間の強度差を明確にするものである。
【００４５】
たとえば、４０チャネルの光システムを考えてみよう。全チャネルが結合器でＡの振幅を有しかつすべて同相であれば、得られる振幅は４０Ａであるが、光出力（測定値）は（４０Ａ）２である。１ビットのみが逆位相であれば、得られる振幅は３８Ａ（１ビットは寄与しないだけでなく破壊的に干渉する）となるが、出力は（３８Ａ）２となる。したがって、１ビットの不正がある場合は、光出力が完全一致と比べて約１０％低下する。したがって、光出力を使用する仕組みは、完全に近い一致と完全一致を区別する際に好都合となる。
【００４６】
交流波のコヒーレントな組合せを使用することによって同じ効果を生むことが可能となる。あるいは、直流電流の直接加算が採用され得る（だが、当然、２乗機能の利点はない）。しかし、ビット加算は、実施が簡単であるだけでなくゼロ出力で一致する場合が生じるという利点を有する。前述の光相関器では、一致する場合が最大強度で生じ、したがって閾値が必要である。閾値はシステムのノイズに敏感である。ビット加算は２進であり、ゼロが真のゼロであるとすれば、１に対応する直流電圧のドリフトはほとんど問題ではなくなる。
【００４７】
ビット加算はＸＯＲ論理配列７２によって実行される。ＸＯＲゲートは、入力の両方でなくいずれか一方が値１のとき、値１を出力する。換言すると、真理値表は下記の通りである。
【表１】
【００４８】
この表は、ＸＯＲゲートへの両入力が一致するとき、すなわち、入力データの関連ビットが参照データの関連ビットに一致するとき所要の結果を示し出力はゼロであるが、一致しないときは出力が１である。
【００４９】
したがって、各ＸＯＲゲート７２の出力は完全に一致する場合にゼロである。各出力がゼロであることは、加算／差分回路を使って検出される。各ＸＯＲゲート７２の出力は加算抵抗器７４に接続され、ピーク／ディップ検出回路７４はゼロ和を検出する。
【００５０】
ピーク／ディップ検出回路７４は、図３にさらに詳しく示される。全ＸＯＲゲート７２からの結合入力はトランスインピーダンス増幅器８０および抵抗器８２に入力される。ＴＩＡの出力はピークホールド回路８２およびコンパレータ８４に行く。この回路は、完全一致を示すゼロ和をトリガするように配置される。
【００５１】
「ヒット率」は入力データ転送速度をはるかに下回ることになり、さらに、検索にはいくぶん長いパターン長が必要になることが予想される。１００％の一致（ゼロ差）を検出するに当り、場合によっては他の文字列も検出される「データページ長」に対応するある時間にわたって出力をハイに保つ「パルスストレッチャ」８６が設計される。このフラグが最初の一致検出の前と後の両方で実際にハイに保たれるように外部遅延が用意されて、これと求められている別の文字列に対応した同様の伸長パルスとの間で重なりが生じ得るようにされてもよい。
【００５２】
前述の「チップ上の検索エンジン」は、少数の（おそらく、モジュール当りたった１つ）の文字列を超高速で検索し得るが、おそらく一致の検出前に始まり検出後しばらく続くパルスの形のフラグを出力する。この大幅に低減された帯域幅の信号は、「データページ長」として定められる領域に求められる一群の文字列の出現にフラグを設定するために、他のパラレルチャネルからの他の電子信号と容易に結合され得る。
【００５３】
この技術はＡＳＩＣ型チップ上で実現され得るので、多くのチャネルの並列処理が可能である。
【図面の簡単な説明】
【００５４】
【図１】同時係属中の国際特許出願第ＰＣＴ／ＧＢ２００５／００４０２８号明細書および英国特許出願第ＧＢ０４２３０９３．４号明細書に記載されるような光相関器を示す。
【図２】本発明による全電子式の相関器を示す。
【図３】適切なピーク／ディップ検出回路を示す。
【特許請求の範囲】
【請求項１】
入力シリアル２進データ電気信号を受け入れ、これを少なくとも１つのＮチャネル入力パラレル２進データ電気信号に変換するシリアル−パラレル変換手段と、前記入力パラレル信号の各チャネルをＮチャネルパラレル参照２進データ電気信号のチャネルと比較するコンパレータとを有し、パターンが一致するとそれを表示する、パターン照合装置。
【請求項２】
前記シリアル−パラレル変換手段が少なくとも１つの１：Ｎデマルチプレクサを備えることが好ましい、請求項１に記載のパターン照合装置。
【請求項３】
前記デマルチプレクサが１：４、１：８、または１：１６デマルチプレクサである、請求項２に記載のパターン照合装置。
【請求項４】
前記１：Ｎデマルチプレクサの各出力が一連のラッチ回路に接続され、ラッチ回路が前記デマルチプレクサの出力レートでクロック駆動され、各ラッチ回路が出力チャネルを有する、請求項２または３に記載のパターン照合装置。
【請求項５】
前記シリアル−パラレル変換手段が一連のラッチ回路を備え、各ラッチ回路が出力チャネルを有する、請求項１に記載のパターン照合装置。
【請求項６】
前記参照データパターンを保存し、各チャネルに適切な２進値を出力するＮチャネル出力メモリ手段を備える、請求項１から５のいずれか一項に記載のパターン照合装置。
【請求項７】
前記コンパレータが前記入力パラレル信号の各チャネルの２進値をＮチャネル出力メモリの関連チャネルの値と比較する、請求項６に記載のパターン照合装置。
【請求項８】
前記コンパレータが、前記入力パラレル信号の各チャネルの値と前記パラレル参照信号のチャネルの値とのビット加算を実行する手段を備える、請求項１から７のいずれか一項に記載のパターン照合装置。
【請求項９】
前記コンパレータが各チャネルに対する前記入力データと前記参照データとからの値を加算する排他的ＯＲ（ＸＯＲ）論理配列を備える、請求項１から８のいずれか一項に記載のパターン照合装置。
【請求項１０】
加算／差分回路が各ＸＯＲ論理配列からの出力を加算する、請求項９に記載のパターン照合装置。
【請求項１１】
前記加算回路がすべてのＥｘＯＲゲートの出力に接続された加算抵抗器と、並列のすべての加算抵抗器に接続されるトランスインピーダンス増幅器（ＴＩＡ）とを備える、請求項１０に記載のパターン照合装置。
【請求項１２】
ゼロ結果が検出されたときトリガ信号を発生するように配置された前記トランスインピーダンス増幅器の出力にコンパレータが備えられる、請求項１１に記載のパターン照合装置。
【請求項１３】
様々な前記パラレル入力信号が種々の参照パターンと比較され得るように、前記入力データに基づいて複数のパラレルデータ信号を生成するように配置される、請求項１から１２のいずれか一項に記載のパターン照合装置。
【請求項１４】
バイト境界コントローラを備える、請求項１から１３のいずれか一項に記載のパターン照合装置。
【請求項１５】
請求項１から１４のいずれか一項に記載のパターン照合装置を備える、集積回路。
【請求項１】
入力シリアル２進データ電気信号を受け入れ、これを少なくとも１つのＮチャネル入力パラレル２進データ電気信号に変換するシリアル−パラレル変換手段と、前記入力パラレル信号の各チャネルをＮチャネルパラレル参照２進データ電気信号のチャネルと比較するコンパレータとを有し、パターンが一致するとそれを表示する、パターン照合装置。
【請求項２】
前記シリアル−パラレル変換手段が少なくとも１つの１：Ｎデマルチプレクサを備えることが好ましい、請求項１に記載のパターン照合装置。
【請求項３】
前記デマルチプレクサが１：４、１：８、または１：１６デマルチプレクサである、請求項２に記載のパターン照合装置。
【請求項４】
前記１：Ｎデマルチプレクサの各出力が一連のラッチ回路に接続され、ラッチ回路が前記デマルチプレクサの出力レートでクロック駆動され、各ラッチ回路が出力チャネルを有する、請求項２または３に記載のパターン照合装置。
【請求項５】
前記シリアル−パラレル変換手段が一連のラッチ回路を備え、各ラッチ回路が出力チャネルを有する、請求項１に記載のパターン照合装置。
【請求項６】
前記参照データパターンを保存し、各チャネルに適切な２進値を出力するＮチャネル出力メモリ手段を備える、請求項１から５のいずれか一項に記載のパターン照合装置。
【請求項７】
前記コンパレータが前記入力パラレル信号の各チャネルの２進値をＮチャネル出力メモリの関連チャネルの値と比較する、請求項６に記載のパターン照合装置。
【請求項８】
前記コンパレータが、前記入力パラレル信号の各チャネルの値と前記パラレル参照信号のチャネルの値とのビット加算を実行する手段を備える、請求項１から７のいずれか一項に記載のパターン照合装置。
【請求項９】
前記コンパレータが各チャネルに対する前記入力データと前記参照データとからの値を加算する排他的ＯＲ（ＸＯＲ）論理配列を備える、請求項１から８のいずれか一項に記載のパターン照合装置。
【請求項１０】
加算／差分回路が各ＸＯＲ論理配列からの出力を加算する、請求項９に記載のパターン照合装置。
【請求項１１】
前記加算回路がすべてのＥｘＯＲゲートの出力に接続された加算抵抗器と、並列のすべての加算抵抗器に接続されるトランスインピーダンス増幅器（ＴＩＡ）とを備える、請求項１０に記載のパターン照合装置。
【請求項１２】
ゼロ結果が検出されたときトリガ信号を発生するように配置された前記トランスインピーダンス増幅器の出力にコンパレータが備えられる、請求項１１に記載のパターン照合装置。
【請求項１３】
様々な前記パラレル入力信号が種々の参照パターンと比較され得るように、前記入力データに基づいて複数のパラレルデータ信号を生成するように配置される、請求項１から１２のいずれか一項に記載のパターン照合装置。
【請求項１４】
バイト境界コントローラを備える、請求項１から１３のいずれか一項に記載のパターン照合装置。
【請求項１５】
請求項１から１４のいずれか一項に記載のパターン照合装置を備える、集積回路。
【図１】
【図２】
【図３】
【図２】
【図３】
【公表番号】特表２００９−５１８７６５（Ｐ２００９−５１８７６５Ａ）
【公表日】平成２１年５月７日（２００９．５．７）
【国際特許分類】
【出願番号】特願２００８−５４５０７９（Ｐ２００８−５４５０７９）
【出願日】平成１８年１２月１２日（２００６．１２．１２）
【国際出願番号】ＰＣＴ／ＧＢ２００６／００４６３８
【国際公開番号】ＷＯ２００７／０６８９０９
【国際公開日】平成１９年６月２１日（２００７．６．２１）
【出願人】（５０１３５２８８２）キネテイツク・リミテツド (93)
【公表日】平成２１年５月７日（２００９．５．７）
【国際特許分類】
【出願日】平成１８年１２月１２日（２００６．１２．１２）
【国際出願番号】ＰＣＴ／ＧＢ２００６／００４６３８
【国際公開番号】ＷＯ２００７／０６８９０９
【国際公開日】平成１９年６月２１日（２００７．６．２１）
【出願人】（５０１３５２８８２）キネテイツク・リミテツド (93)
[ Back to top ]