JP3391973B2

JP3391973B2 - アナログ・ロジックを用いたデジタル・パターンのマッチング

Info

Publication number: JP3391973B2
Application number: JP04448396A
Authority: JP
Inventors: エドワードオフォードグレン; リーソンタグジェフレイ
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1995-03-01
Filing date: 1996-03-01
Publication date: 2003-03-31
Anticipated expiration: 2016-03-01
Also published as: US5550528A; JPH08305780A

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、アナログ・ロジッ
クを用いたデジタル・パターンのマッチングに関する。

【０００２】

【従来の技術】デジタル・パターンのマッチングは、通
常デジタル・ロジックを用いて作成され、そこでは入力
パターンが参照パターンに対してマッチングされる。た
とえば、一つの方法の概観図である図１では、第１の入
力の組Ａ₁ ... Ａ₄ と第２の入力の組Ｂ₁ ... Ｂ₄ をそ
れぞれ持つ一連のＸＯＲゲート１０１，...，１０４が
示される。さらに一般化すれば、整数ｎについて、ｎ個
のＸＯＲゲートに対してｎ組の入力がある。「ペアの一
致」を調べるために、入力パターンの２進数が入力の第
１組になり、参照パターンの２進数は入力の第２組とさ
れる。ペアの一致が生じると、所与のＸＯＲゲートにつ
いて入力Ａ_n が入力Ｂ_n と等しくなり、所与のＸＯＲゲ
ートの出力が連想制御線（１０５、１０６、１０７、ま
たは１０８）を低い状態に設定する。

【０００３】しかし、ペアの不一致が生じると（すなわ
ちＡ_n ≠Ｂ_n のとき）、連想ＸＯＲゲートの出力からの
制御線は高くなる。このため、ペアの不一致の数は、第
１ステージ（１０９と１１０）およびマッチングされる
値の数によって１または複数の後続ステージ（１１１）
からなる一連の計数器の中でカウントすることができ
る。計数器１１８からの出力は、母線１１２を経由して
比較器１１３へ送られたペアの不一致の総数を表す。許
容されるペアの不一致の数、たとえば不一致２件は、母
線１１４を経由して比較器へ送られる。母線１１２にお
けるペアの不一致の数が母線１１４上での許容数より少
ないかまたは等しい場合には、比較器は「パターン一
致」信号を比較器の出力線１１５へ送る。それ以外の場
合には、「パターン不一致」の信号が出力線１１５へ送
られる。

【０００４】

【発明が解決しようとする課題】マッチングする値の数
が増えるにつれて、計数器１１８の複雑性が高まる。こ
のことは、第１ステージ計数器をより多く用意しなけれ
ばならないだけでなく、後続ステージ計数器もより多く
必要だということを意味する。こうして、入力の数
（ｎ）の増加に従い、回路の複雑性と規模の両方が増大
し、また計数器を通過するための遅延も増大する。その
他のパターン・マッチング技術にはソフトウエア・プロ
グラムを用いるものがあるが、基本的にはそれらはハー
ドウエアを備えた技術ほど速度が速くない。

【０００５】

【課題を解決するための手段】我々は、デジタル比較器
により第１の値の組が第２の値の組と比較されるデジタ
ル・パターン・マッチング技術を発明した。比較器の出
力は可制御電流源へ提供されるため、所与の電流源から
の出力電流は対応するデジタル比較器から一致の指示が
あるかどうかに依存する。電流源からの出力は合算さ
れ、総出力電流が所与の値と比較される。パターン一致
の信号は、固定値または代替的にプログラム可能な値で
ある所与の値より総出力電流が大きいか小さいかに応じ
て提供される。このようにして、第１および第２の値の
組が少なくとも部分的には望ましい範囲内で一致すると
きに、パターンの一致が表示される。

【０００６】

【発明の実施の形態】以下の詳細説明は、アナログ・ロ
ジックを用いたデジタル・パターンのマッチング技術に
関する。図２によると、本発明の実施例２００には排他
的ＮＯＲ（ＸＮＯＲ）ゲート２０１、２０２、および２
０３の組が含まれる。これらは、入力パターン（Ａ₁ 、
Ａ₂ 、Ａ_n ）の数字と参照パターン（Ｂ₁ 、Ｂ₂ 、Ｂ
_n ）の数字とのデジタルな比較をおこなう。これらのデ
ジタル・パターンのソース（それぞれ２１８、２１９）
は、たとえば光学および音声読み取り装置など、さまざ
まな種類の装置のいずれでもよい。一実施例では、ソー
スＡがデータを出力する磁気ディスクで、ソースＢは磁
気ディスク上の望ましい場所を獲得したことを示す参照
パターンを提供する。

【０００７】以下、例示に際し「入力パターン」および
「参照パターン」という用語を使用するが、どの２組の
数値も本発明の技術によって比較されることに注意を要
する。ＸＮＯＲゲート２０１、２０２、および２０３か
らの出力は、制御線２０４、２０５、および２０６を経
由して電流源２０７、２０８、および２０９の制御入力
へそれぞれ接続される。所与の入力のペアが不一致の場
合（すなわち一方の入力ロジックが「０」で他方の入力
ロジックが「１」のとき）、対応するＸＮＯＲゲートが
下がる。この低位の出力はＸＮＯＲゲートに接続された
電流源を接続状態にし、ＸＮＯＲゲートに対応する電流
線２１０、２１１、または２１２へ電流「ｉ」を提供す
る。しかし、所与の入力のペアが一致する場合は、対応
するＸＮＯＲゲートＸＮＯＲゲート出力は高まる。この
高位の出力はＸＮＯＲゲートに接続された電流源の接続
を切る。

【０００８】接続状態にされた電流源からの電流はノー
ド２１３で合算され、合計電流「Ｉ」を、線２１４から
電流シンク２１５へ送る。電流シンク２１５には、吸収
できる電流の最大値「Ｉ_max 」がある。Ｉ＜Ｉ_max のと
き、ノード２１３の電圧は、通常その回路がＣＭＯＳ技
術に用いられたときのＶＳＳ程度の低位のままである。
他方、Ｉ＞Ｉ_max のとき、ノード２１３の電圧は、通常
ＣＭＯＳ技術におけるＶ_DD程度に上昇する。

【０００９】実際には、他に電流源やシンクが存在しな
いとすれば、接続状態の電流源からノード２１３へ流入
する総電流は常に電流シンク２１５へ流入する電流Ｉと
等しいことに注意を要する。このため、所与の電流源ま
たはシンクを電圧が通過するとき、電流「ｉ」と「Ｉ
_max 」は公称値に対応する。しかし、ノード２１３の電
圧が上昇すると、電流源からの電流は公称値「ｉ」より
低下し、電流シンクが吸収できる電流の値は公称値「Ｉ
_max 」より上昇する。電流「ｉ」の合計は総電流「Ｉ」
であり、これは電流シンクへ流入する電流と等しい。

【００１０】総電流「Ｉ」が「Ｉ_max 」を越えると、ノ
ード２１３の電圧は上昇する。このため、Ｉ_max の値
は、望ましい範囲内で少なくとも部分的に一致するパタ
ーンを示しつつ、「パターン一致」信号がノード２１３
へ提供される前にいくつの入力ペア（Ａ₁ −Ｂ₁ ，...
，Ａ_n −Ｂ_n ）がデジタルに一致しなければならない
かを決定することに注意を要する。実際には、出力ノー
ド２１３は通常、線２１７へ逆転した出力を提供するた
めにインバーター２１６により緩衝される。

【００１１】電流源と電流シンクはアナログ設計技術で
知られているさまざまな技術を利用して作られる。その
うち、現在よく使われるものの実施例３００を、図３に
示した。一列に並んだ可制御電流源は、点線で囲まれた
ブロック３０９に示したトランジスタで構成される。図
２の電流源２０７、２０８、および２０９の制御部を含
む３個のｐチャンネル・トランジスタ３１０、３１１、
および３１２が図示される。一般に、図２に示すような
可制御電流源に対応する数の作成にあたり、同じ方法で
接続されたいくつかの（ｎ）トランジスタが使用され
る。ゲートはそれぞれ制御線２０４、２０５、および２
０６（図２）と接続する３１３、３１４、および３１５
へそれぞれつながる。独立の電流（ｉ）が接続された制
御トランジスタを通り、トランジスタ３１７と３１９を
通る総電流（Ｉ）を形成するためにノード３１６で合算
される。バイアス・ネットワークはトランジスタ３０
１、３０２、および３０４、および値Ｒを持つレジスタ
ー３０３を含む。このネットワークはトランジスタ３０
７および３１７のゲートにバイアス電圧を発生させ、Ｉ
ｒｅｆおよびＩの両方により高いインピーダンス電流源
をもたらす。

【００１２】トランジスタ３０５、３０７、および３０
８を流れる参照電流Ｉ_ref は、許容される不一致の数を
表す。Ｉ_ref は、Ｉ_max の値を算定するためにトランジ
スタ３１９を経由してミラー化され概算された電流であ
る。すなわち、接続状態の制御トランジスタの数が増え
る（ＸＮＯＲゲート２０１...２０３の入力におけるペ
アの不一致の数の増加のせいで）につれて、Ｉの値が増
加する。このため、ノード３１８の電圧は上昇する。

【００１３】

【外１】

【００１４】デジタル比較器、制御電流源、および電流
シンクは、通常単一の集積回路上に形成され、入力パタ
ーンのソースは通常その外側に設置される。参照パター
ン・ソースには、パターン・マッチング・ロジックとし
て同じ集積回路上に形成された、ハードワイヤード・ロ
ジックまたは代替的にメモリー（例、静的記憶装置、読
みだし専用メモリー、またはプログラム可能読みだし専
用メモリー）がある。しかし、他にもさまざまな作成方
法が可能である。前述の実施例では、所与の２進数の入
力ペアが不一致のとき所与の電流源が接続状態になるこ
とを示している。このため、所与の値より大きい複数の
デジタル入力ペアの不一致はノード２１３の上昇を引き
起こし、これによってパターン不一致を示す。

【００１５】しかし、他の実施例では、所与の電流源は
所与の２進数の入力ペアが一致するときに接続状態にな
る。この場合には、ノード２１３の電圧の上昇はパター
ンの一致を表す。上記のデジタル２進比較器はＸＯＲゲ
ート（図１）およびＸＮＯＲゲート（図２）を使用して
作成され、一般的に「排他的論理和」の働きをするもの
と考えられる。排他的論理和の機能は、業界周知のさま
ざまな回路を用いて果たすことができる。さらに、複数
レベル論理比較器は２個以上のパターンを同時に比較す
るために使用され、不一致の入力なし、不一致入力１
対、不一致入力２対などを表す複数レベル出力信号を提
供する。

【００１６】電流源は、１列のｐチャンネル・トランジ
スタ（３０９）の代わりに１列のｎチャンネル・トラン
ジスタにより制御される。また、電流源とシンクについ
ては別の設計も可能である。最後に、電流シンクは固定
最大電流値（Ｉ_max ）を持つものとして示してきたが、
この値をプログラム可能なものとすることもできる。こ
れは、たとえば３０５に平行したトランジスタを提供
し、不一致のレベルの上昇／下降に応じて適当に断続す
ることにより、簡便に達成することができる。望むなら
ば、参照パターンもプログラム化することができる。こ
のアプローチは、パターン一致と見なすにはＭビット・
パターンのうちいずれかのＮビットが一致しなければな
らないという「ファジー」マッチングにおいて、特に有
益である。

【図面の簡単な説明】

【図１】デジタルな値を比較する従来の技法を示す図で
ある。

【図２】本発明の実施例を示す図である。

【図３】本発明の実施に適した電流源のアレーの概要を
示す図である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者ジェフレイリーソンタグアメリカ合衆国 19522 ニュージャーシィ，フリートウッド，シュウエイツロード 93エー (56)参考文献特表平９−500749（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06G 7/14 H03K 19/20

Claims

(57)【特許請求の範囲】

【請求項１】デジタル値の第１組が少なくとも部分的
に第２組のデジタル値と望ましい範囲内で一致するかど
うかを示すための集積回路であって、前記集積回路は、それぞれ前記第１組のデジタル値（２１８）に接続する
ための第１入力（Ａ１−Ａ_n ）と、前記第２組のデジタ
ル値（２１９）に接続するための第２入力（Ｂ１−Ｂ
_n ）と、出力（２０４−２０６）とを有する１組のデジ
タル比較器（２０１−２０３）を含み、前記の第１および第２組の１対のデジタル値が等しいと
きに第１の電流の値を提供するため、および前記の第１
および第２組の１対のデジタル値が等しくないときに第
２の電流の値を提供するためにそれぞれデジタル比較器
の出力と接続された電流源（２０７−２０９）と、前記
の電流源からの電流（ｉ）を合算して総電流（Ｉ）を算
出するための電流加算器（２１３）とをさらに含み、前記総電流が所与の値（Ｉ_max ）を越えたときに第１の
出力信号を提供し、前記総電流が所与の値より低いとき
に第２の出力信号を提供する電流比較器（２１５）をさ
らに含む集積回路。
【請求項２】前記デジタル比較器が排他的論理和ゲー
ト、または代替的に排他的否定論理和ゲートである、請
求項１に記載の集積回路。
【請求項３】前記電流源が前記デジタル比較器の出力
に接続されたゲート（３１３−３１５）と、電圧源（Ｖ
_DD）に接続されたソースと、一括して共通ノード（３１
６）へ接続されたそれらのドレーンとを有する電界効果
トランジスタ（３１０−３１２）の並列アレー（３０
９）を含む、請求項１に記載の集積回路。
【請求項４】前記電流比較器が、最大値までの電流の
値を吸収する電流シンクから成り、その最大値以上のと
き前記電流シンクにかかる電圧が上昇することを特徴と
する、請求項１に記載の集積回路。
【請求項５】前記電流シンクが第１支線を流れる参照
電流（Ｉ_ref ）と、第２支線を流れる総電流（Ｉ）とを
有する比例的電流ミラーを含む、請求項４に記載の集積
回路。
【請求項６】前記第２組のデジタル値が参照パターン
であり、前記集積回路が前記第２組のデジタル値のソー
スをさらに含む、請求項１に記載の集積回路。