(57)【要約】【課題】参照ベクトルと入力ベクトルの類似度を求めるパターンマッチング装置を、メムリスタを使って実現する。【解決手段】マッチング装置２は、格子回路３０と電源５とコントローラ７を備える。格子回路３０の行と列と一方の対角の夫々の方向で隣接する接続点３がメムリスタユニット４を介して接続されている。メムリスタユニット４は、２個の接続点３を、メムリスタを介して接続するメムリスタ経路とメムリスタを介さずに直結するバイパス経路のいずれかで接続する。コントローラ７は、格子回路３０の各行に対して参照ベクトルの各要素値を対応させ、各列に対して入力ベクトルの各要素値を対応させ、要素が一致したら対応するメムリスタユニットをバイパス経路に設定し一致しなかったらメムリスタ経路に設定する。コントローラは、電源５から電圧パルスを出力させ、電源５からグランド９までの総抵抗値を両ベクトルの類似度として出力する。【選択図】図１
2018206193.tif 000002
【特許請求の範囲】
【請求項１】
ｍ次元の二値の参照ベクトルに対するｎ次元の二値の入力ベクトルの類似度を出力するパターンマッチング装置であり、
ｍ行ｎ列の格子状に接続点が配置されている格子回路と、
２個の前記接続点を電気的に接続するユニットであって、前記２個の接続点を、メムリスタを介して接続するメムリスタ経路と前記メムリスタを介さずに直結するバイパス経路のいずれかで接続する複数のメムリスタユニットと、
電源と、
コントローラと、
を備えており、
前記格子回路にて行方向で隣接する前記接続点同士が前記メムリスタユニットで接続されており、
前記格子回路にて列方向で隣接する前記接続点同士が前記メムリスタユニットで接続されており、
前記格子回路にて（ｉ，ｊ）接続点と（ｉ＋１、ｊ＋１）接続点が前記メムリスタユニットで接続されており（ここで、ｉ＝１〜ｍ−１、ｊ＝１〜ｎ−１）、
（１，１）接続点が前記メムリスタユニットを介して前記電源に接続されており、（ｍ，ｎ）接続点がグランドに接続されており、
前記コントローラは、
前記格子回路の各行に対して前記参照ベクトルの各要素値を対応させるとともに各列に対して前記入力ベクトルの各要素値を対応させ、
前記格子回路の（ｉ，ｊ）接続点に対応する前記参照ベクトルの要素値と前記入力ベクトルの要素値が等しい場合は、当該（ｉ，ｊ）接続点と前記電源に近い側で隣接する（ｉ−１、ｊ）接続点、（ｉ，ｊ−１）接続点、及び、（ｉ−１、ｊ―１）接続点の夫々とを接続している前記メムリスタユニットを前記バイパス経路に設定し、等しくない場合は、当該（ｉ，ｊ）接続点と前記電源に近い側で隣接する（ｉ−１、ｊ）接続点、（ｉ，ｊ−１）接続点、及び、（ｉ−１、ｊ―１）接続点の夫々とを接続している前記メムリスタユニットを前記メムリスタ経路に設定し、
少なくとも一つの前記メムリスタの両端に加わる電圧が前記メムリスタの閾値電圧を超えるように前記電源の出力電圧を調整して所定回数のパルス電圧を前記電源から出力させた後、前記電源から前記グランドまで前記格子回路において電流がもっとも多く流れる経路の総抵抗値を前記参照ベクトルと前記入力ベクトルの類似度として出力する、パターンマッチング装置。
【請求項２】
全てのメムリスタの特性が同じであり、前記格子回路にて対角方向で隣接している前記接続点の間に２個の前記メムリスタユニットが直列に接続されており、行方向及び列方向で隣接している前記接続点の間には１個の前記メムリスタユニットが接続されている、請求項１に記載のパターンマッチング装置。
【請求項３】
前記格子回路にて対角方向で隣接している前記接続点同士を接続する前記メムリスタユニットの前記メムリスタの最小抵抗値が行方向及び列方向で隣接している前記接続点同士を接続する前記メムリスタユニットの前記メムリスタの最小抵抗値よりも大きい、請求項１に記載のパターンマッチング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書が開示する技術は、メムリスタを用いたパターンマッチング装置に関する。
【背景技術】
【０００２】
近年、メムリスタ（メモリスタ）と呼ばれる受動素子が注目を集めている。メムリスタは、通過した電流量（電荷量）に応じて抵抗値が変化し、電流が遮断されてもその抵抗値が記憶される、という特性を有している。なお、メムリスタには、最大抵抗値と最小抵抗値が存在する。また、メムリスタは、閾値電圧を超える電圧が印加されないと電流が流れない、という特性も有している。なお、「メムリスタ」との呼称は、抵抗値を記憶する特性に由来する。メムリスタは、１９７１年にLeon Chuaの論文でその存在が指摘されていた。２００８年に米国企業により実際の素子が開発され、それ以降、様々な応用先が研究されている。例えば、特許文献１には、メムリスタを用いたニューラルネットワーク回路が開示されている。また、特許文献２には、メムリスタを積層メモリに利用する技術が開示されている。さらに、非特許文献１には、最短経路探索と巡回セールスマン問題を解く回路を、メムリスタを用いて実現することが提案されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１５−１９５０１１号公報
【特許文献２】特開２０１７−０１０６０５号公報
【非特許文献】
【０００４】
【非特許文献１】Yuriy V. Pershin and Massimiliano Di Ventra,“Self-organization and solution of short-path optimization problems with memristive networks”, Phis. Rev. E 88, 013305(2013)
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本願の発明者は、メムリスタの特性が、動的時間伸縮法（Dynamic Time Warping）と呼ばれる、２つの二値化ベクトル（要素値が２個の値のいずれかである信号列）の類似度を求めるアルゴリズムに適していることを見出した。動的時間伸縮法は、２つのベクトルの類似度を数値で表すことができる、いわゆるパターンマッチングの一種である。動的時間伸縮法は、例えば、音声データから特定の単語を抽出する手法として利用されてきた。動的時間伸縮法は、時間又は長さの異なる２つのベクトルの類似度を求めることができる点で優れている。一方、動的時間伸縮法は、計算量が多いという短所を有する。本明細書は、動的時間伸縮法を、メムリスタを用いたハードウエアで実現する、全く新しいパターンマッチング装置を提供する。本明細書が開示するパターンマッチング装置は、類似度をハードウエアで求めるので、類似度を高速に求めることができる。
【課題を解決するための手段】
【０００６】
本明細書が開示するパターンマッチング装置は、ｍ次元の二値の参照ベクトルに対するｎ次元の二値の入力ベクトルの類似度を数値化して出力するデバイスである。このパターンマッチング装置は、ｍ行ｎ列の格子状に接続点が配置されている格子回路と、複数のメムリスタユニットと、電源と、コントローラを備えている。夫々のメムリスタユニットは、格子回路の２個の接続点を電気的に接続するユニットであって、２個の接続点を、メムリスタを介して接続するメムリスタ経路とメムリスタを介さずに直結するバイパス経路のいずれかで接続する。メムリスタ経路とバイパス経路の切換はコントローラが行う。格子回路にて行方向で隣接する接続点同士がメムリスタユニットで接続されており、格子回路にて列方向で隣接する接続点同士もメムリスタユニットで接続されている。また、格子回路にて接続点（ｉ，ｊ）と接続点（ｉ＋１、ｊ＋１）もメムリスタユニットで接続されている（ここで、ｉ＝１〜ｍ−１、ｊ＝１〜ｎ−１）。そして、接続点（１，１）がメムリスタユニットを介して電源に接続されており、接続点（ｍ，ｎ）がグランドに接続されている。コントローラは、格子回路の各行に対して参照ベクトルの各要素値を対応させるとともに各列に対して入力ベクトルの各要素値を対応させる。そして、コントローラは、格子回路の接続点（ｉ，ｊ）に対応する参照ベクトルの要素値と入力ベクトルの要素値が等しい場合は、その接続点（ｉ，ｊ）と電源に近い側で隣接する接続点とを接続しているメムリスタユニットをバイパス経路に設定する。別言すれば、コントローラは、格子回路の接続点（ｉ，ｊ）に対応する参照ベクトルの要素値と入力ベクトルの要素値が等しい場合は、その接続点（ｉ，ｊ）と、接続点（ｉ−１，ｊ−１）、接続点（ｉ，ｊ−１）、接続点（ｉ−１，ｊ）の夫々とを接続しているメムリスタユニットをバイパス経路に設定する。一方、コントローラは、格子回路の接続点（ｉ，ｊ）に対応する参照ベクトルの要素値と入力ベクトルの要素値が等しくない場合は、その接続点（ｉ，ｊ）と電源に近い側で隣接する接続点とを接続しているメムリスタユニットをメムリスタ経路に設定する。別言すれば、コントローラは、格子回路の接続点（ｉ，ｊ）に対応する参照ベクトルの要素値と入力ベクトルの要素値が等しくない場合は、その接続点（ｉ，ｊ）と、接続点（ｉ−１，ｊ−１）、接続点（ｉ，ｊ−１）、接続点（ｉ−１，ｊ）の夫々とを接続しているメムリスタユニットをメムリスタ経路に設定する。なお、接続点（１，１）については、対応する参照ベクトルと入力ベクトルの要素の一致／不一致に応じて電源と接続点（１，１）とを接続しているメムリスタユニットの経路を設定する。
【０００７】
そして、コントローラは、少なくとも一つのメムリスタの両端に加わる電圧がメムリスタの閾値電圧を超えるように電源の出力電圧を調整して所定回数のパルス電圧を電源から出力させる。コントローラは、パルス電圧出力後、電源からグランドまで格子回路において電流がもっとも多く流れる経路の総抵抗値を、参照ベクトルと入力ベクトルの類似度として出力する。詳しくは後述するが、所定回の電圧パルスを印加した後に電流が最も多く流れる経路の総抵抗値が、動的時間伸縮法における、いわゆるＤＴＷ距離に相当することになる。上記のパターンマッチング装置では、所定回数の電圧パルスを印加することで、ＤＴＷ距離が得られる。複数の異なる入力ベクトルに対して上記の処理を行うと、総抵抗値が最も小さくなるときの入力ベクトルが、参照ベクトルに最も類似していることがわかる。
【０００８】
なお、全てのメムリスタの特性が同じであり、格子回路にて対角方向で隣接している接続点の間に２個のメムリスタユニットが直列に接続されており、行方向及び列方向で隣接している接続点の間には１個のメムリスタユニットが接続されているとよい。対角方向で隣接している接続点間のマンハッタン距離は、行方向及び列方向で隣接している接続点の距離の２倍に相当する。対角方向で隣接している接続点の間に２個のメムリスタユニットを直列に接続することで、対角方向で隣接する接続点間のマンハッタン距離を考慮することができる。
【０００９】
マンハッタン距離を考慮するのに、次のように構成してもよい。即ち、格子回路にて対角方向で隣接している接続点同士を接続するメムリスタユニットのメムリスタの最小抵抗値を、行方向及び列方向で隣接している接続点同士を接続する前記メムリスタユニットのメムリスタの最小抵抗値よりも大きくする。
【００１０】
なお、「ｍ行ｎ列の格子状に接続点が配置されている格子回路」とは、電気的な接続関係が「ｍ行ｎ列の格子状に」表せればよいことを意味しており、機械的な構造が「格子状」である必要はないことに留意されたい。また、「参照ベクトル」を「入力ベクトル」と読み替えるとともに、「入力ベクトル」を「参照ベクトル」と読み替えても技術的には等価であることに留意されたい。本明細書が開示する技術の詳細とさらなる改良は以下の「発明を実施するための形態」にて説明する。
【図面の簡単な説明】
【００１１】
【図１】実施例のパターンマッチング装置の回路図である。
【図２】メムリスタユニットの模式的回路図である。
【図３】パターンマッチング装置と動的時間伸縮法との関係性を説明する部分回路図である。
【図４】３行２列の格子回路を有するパターンマッチング装置の回路図である。
【図５】入力ベクトルＹ１のときのメムリスタユニットの状態を示す回路図である。
【図６】入力ベクトルＹ２のときのメムリスタユニットの状態を示す回路図である。
【発明を実施するための形態】
【００１２】
本明細書は、メムリスタ（メモリスタ）を用いたパターンマッチング装置を開示する。本明細書の最初で述べたように、メムリスタとは、通過した電流量（電荷量）に応じて抵抗値が変化し、電流が遮断されてもその抵抗値が記憶される、という特性を有した受動素子である。また、メムリスタは、閾値電圧を超える電圧が印加されないと電流が流れない、という特性も有している。さらに、メムリスタは、その最大抵抗値と最小抵抗値が決まっている。メムリスタ自体の構造の詳しい説明はここでは省略する。
【００１３】
図面を参照して実施例のパターンマッチング装置２を説明する。パターンマッチング装置２は、ｍ次元の２値化ベクトルである参照ベクトルＸとｎ次元の２値化ベクトルである入力ベクトルＹの類似度を数値（あるいは電圧などの電気信号）で出力する装置である。類似度は、動的時間伸縮法により求められる。動的時間伸縮法をソフトウエアで実行すると膨大な計算が必要となる。しかし、パターンマッチング装置２は、動的時間計算法を、メムリスタを使ったハードウエアで実行するので類似度を高速に求めることができる。
【００１４】
図１に、パターンマッチング装置２の回路図を示す。パターンマッチング装置２は、複数のメムリスタユニット４を含む格子回路３０と、電源５とコントローラ７を備える。なお、図１では、いくつかのメムリスタユニットに符号４ａ−４ｆを付して区別している。全てのメムリスタユニットを区別なく示す場合にはメムリスタユニット４と表記する。また、図１では、いくつかのメムリスタユニットに対する符号を省略してある。
【００１５】
格子回路３０は、複数の接続点３がｍ行ｎ列に配置されている回路であり、隣接する接続点がメムリスタユニット４を介して電気的に接続されている。なお、図１では、いくつかの接続点には符号３ａ−３ｇを付して区別している。全ての接続点を区別なく示す場合には接続点３と表記する。また、図１では、いくつかの接続点に対する符号を省略してある。
【００１６】
複数の接続点３は、ｍ行ｎ列に格子状に配置されている。ここで、「格子状に配置されている」とは、電気的な接続関係を示す回路図が格子状に描けるということを意味しており、接続点が機械的（物理的）に格子状に配置されていることを必要としないことに留意されたい。
【００１７】
図１に示すように、格子回路３０にて行方向（図中の縦方向）で隣接する接続点３がメムリスタユニット４で接続されており、列方向（図中の横方向）で隣接する接続点３もメムリスタユニット４で接続されている。格子回路３０のひとつの角の接続点３ａが、２個のメムリスタユニット４の直列接続を介して電源５に接続されている。電源５に接続されている接続点３ａを、説明の便宜上、「（１，１）接続点」と表記する。また、電源５に接続された接続点３ａと対角の位置にある接続点３ｇには、グランド９が接続されている。接続点３ｇを、説明の便宜上、「（ｍ、ｎ）接続点」と表記する。接続点３がｍ行ｎ列に配置された格子回路３０において、第ｉ行第ｊ列に位置する接続点３を、「（ｉ，ｊ）接続点」と表記する。
【００１８】
格子回路３０では、（ｉ，ｊ）接続点と（ｉ＋１、ｊ＋１）接続点は、２個のメムリスタユニット４の直列接続を介して接続されている。なお、ここで、ｉ＝１〜ｍ−１、ｊ＝１〜ｎ−１である。別言すれば、電源５と接続されている接続点３ａとグランド９に接続されている接続点３ｇとを結ぶ対角方向で隣接する接続点同士が２個のメムリスタユニット４の直列接続を介して接続されている。詳しい説明は後述するが、各メムリスタユニット４と電源５は、コントローラ７によって制御される。
【００１９】
メムリスタユニット４について説明する。図２にメムリスタユニット４の回路図を示す。図２には、格子回路３０の接続点３ａと３ｂを接続するメムリスタユニット４を図示してある。メムリスタユニット４は、隣接する接続点３ａ、３ｂを、メムリスタ４４を介して接続するメムリスタ経路４３と、メムリスタ４４を介さずに直結するバイパス経路４２のいずれかで接続することができる。バイパス経路４２とメムリスタ経路４３は、切換器４１によって選択される。切換器４１は、コントローラ７によって制御される。図２における信号線Ｓ１は、図１のコントローラ７と接続されている。メムリスタ４４は、通過した電流量（電荷量）によって抵抗値が変化する。メムリスタ４４は、通過した電流量（電荷量）が多いほど、抵抗値が下がる。逆方向に電流を流すと抵抗値が上がる。なお、メムリスタ４４の抵抗値には、最大値Ｒｍａｘと最小値Ｒｍｉｎがある。本実施例では、メムリスタ４４は、接続点３ａから３ｂに向かって電流が流れるときに抵抗値が下がる向きに接続される。他のメムリスタ４４についても、図１において電源５に近い側の接続点から遠い側の接続点に向けて電流が流れるときの抵抗値が下がる向きでメムリスタ４４は接続される。また、メムリスタ４４は、閾値電圧よりも大きい電圧が印加されないと電流が流れない、という特徴も有している。なお、閾値電圧には正値の閾値電圧と負値の閾値電圧がある。「閾値電圧よりも大きい電圧」とは、絶対値での比較において閾値電圧よりも大きい電圧、という意味である。図２における矢印破線Ｓ２は、メムリスタ４４からコントローラ７への信号線を示しており、コントローラ７は、メムリスタ４４の抵抗値を知ることができるようになっている。
【００２０】
パターンマッチング装置２は、ｍ次元の二値の参照ベクトルＸとｎ次元の二値の入力ベクトルＹとの類似度を出力する。図１の回路で２つのベクトルの類似度が得られる仕組みを説明する。図１のパターンマッチング装置２は、動的時間伸縮法（Dynamic Time Warping）と呼ばれる類似度算出アルゴリズムをハードウエアで実現する。まず、動的時間伸縮法について説明する。今、ｍ次元の参照ベクトルをベクトルＸ＝（ｘ１，ｘ２，・・・，ｘｍ）と表し、ｎ次元の入力ベクトルを、ベクトルＹ＝（ｙ１，ｙ２，・・・，ｙｎ）と表す。このとき、参照ベクトルＸと入力ベクトルＹの類似度はＤＴＷ距離Ｄ（Ｘ，Ｙ）という変数で表される。ＤＴＷ距離（Ｘ，Ｙ）は、次の（数１）で求めることができる。
【００２１】
【数１】
2018206193.tif 000003
【００２２】
（数１）において、||ｘｉ−ｙｉ||は２つの要素値の距離を表す。距離の定義は様々であるが、ここでは例えば、マンハッタン距離を採用する。マンハッタン距離とは、格子状の経路を辿る場合の距離である。その場合、２つの要素が行方向で隣接する場合、及び、列方向で隣接する場合は、その距離は格子の１区画となる。一方、２つの要素が格子の対角方向で隣接する場合は、一方の要素から他方の要素への移動距離は、行方向に１区画、さらに列方向に１区画の移動となるため、||ｘｉ−ｙｉ||は２区画となる。
【００２３】
（数１）の第３行目の式は、第２行目の式において、ｆ（ｉ，１）、ｆ（１，ｊ）を計算するための便宜上の境界条件である。第３行目の境界条件より、ｆ（１，１）＝||ｘ１−ｙ１||となる。
【００２４】
（数１）の第２行目の式が、図１のパターンマッチング装置２で計算できる。このことを、図３を参照しつつ説明する。以下では、格子回路３０のｉ行ｊ列の接続点を、記号「Ｐ（ｉ，ｊ）」で表す。図３は、接続点Ｐ（ｉ，ｊ）と、電源５に近い側でそれに隣接する接続点Ｐ（ｉ−１，ｊ）、Ｐ（ｉ，ｊ−１）、Ｐ（ｉ−１，ｊ−１）との間のメムリスタユニット４ａ、４ｂ、４ｃを描いた図である。
【００２５】
図１のパターンマッチング装置２のコントローラ７は、格子回路３０の各行に対して参照ベクトルＸの各要素値を順に対応させ、各列に対して入力ベクトルＹの各要素値を順に対応させる。すなわち、格子回路３０の接続点Ｐ（ｉ，ｊ）には、参照ベクトルＸの第ｉ要素（ｘｉ）と入力ベクトルＹの第ｊ要素（ｙｊ）が対応する。
【００２６】
今、電源５の正極から接続点Ｐ（ｉ−１，ｊ―１）までの抵抗値と、正極から接続点Ｐ（ｉ−１，ｊ）までの抵抗値と、正極から接続点Ｐ（ｉ，ｊ―１）までの抵抗値が既知であると仮定する。また、今、参照ベクトルＸの第ｉ要素（ｘｉ）と入力ベクトルＹの第ｊ要素（ｙｊ）は等しくないと仮定する。即ち、||ｘｉ−ｙｉ||≠０であると仮定する。このとき、コントローラ７は、メムリスタユニット４ａ、４ｂ、４ｃの夫々の切換器４１を制御し、それらのメムリスタユニット４ａ、４ｂ、４ｃにおいてメムリスタ経路（図２参照）に設定する。なお、メムリスタユニット４ａ、４ｂ、４ｃの夫々のメムリスタ４４の抵抗値は最大値Ｒｍａｘになっているとする。
【００２７】
次に、コントローラ７は、メムリスタユニット４ａ、４ｂ、４ｃに含まれるメムリスタ４４の少なくとも一つに閾値電圧を超える電圧が印加されるとともに別の少なくとも一つには閾値電圧を下回る電圧が印加されるように電源５の出力電圧を調整して所定回数のパルス電圧を印加する。
【００２８】
ここで、メムリスタユニット４ａ、４ｂ、４ｃの夫々に含まれるメムリスタ４４に印加される電圧は、接続点Ｐ（ｉ−１，ｊ―１）、Ｐ（ｉ−１，ｊ）、Ｐ（ｉ，ｊ―１）の夫々と電源５の正極までの間の抵抗値に依存する。すなわち、上記３個の接続点のうち、正極との間の抵抗値が最も小さい接続点と接続点Ｐ（ｉ，ｊ）との間のメムリスタ４４だけに閾値電圧を超える電圧が印加され、電流が流れる度に抵抗値が下がる。パルス電圧を印加し続ける結果、電流が流れたメムリスタ４４の抵抗値は最小値Ｒｍｉｎまで下がる。一方、上記３個の接続点のうち、正極との間の抵抗値が最も小さい接続点以外の接続点と接続点Ｐ（ｉ，ｊ）との間には電流は流れない。電流は、正極との間の抵抗値が最も小さい接続点と接続点Ｐ（ｉ，ｊ）の間だけに流れることになる。すなわち、３個の接続点Ｐ（ｉ−１，ｊ−１）、Ｐ（ｉ−１，ｊ）、Ｐ（ｉ，ｊ−１）のうち、電源５の正極からの抵抗値が最も小さい接続点が自動的に選ばれることになる。なお、抵抗値の大きい接続点にも多少の電流が流れるが、抵抗値の小さい接続点に流れる電流に対して抵抗値の大きい接続点に流れる電流は無視し得るほどに小さい。
【００２９】
今、仮に、３個の接続点Ｐ（ｉ−１，ｊ−１）、Ｐ（ｉ−１，ｊ）、Ｐ（ｉ，ｊ−１）のうち、接続点Ｐ（ｉ−１，ｊ）が、電源５の正極からの抵抗値が最も小さい接続点であるとする。電源５から所定回数の電圧パルスを印加すると、接続点Ｐ（ｉ−１，ｊ）と接続点Ｐ（ｉ，ｊ）との間のメムリスタユニット４ｂの抵抗値（即ち、メムリスタユニット４ｂのメムリスタ４４の抵抗値）は、最小値であるＲｍｉｎまで下がる。その他のメムリスタユニット４ａ、４ｃには閾値電圧より小さい電圧しか印加されず、それらの抵抗値は下がらない。その結果、電源５の正極から接続点Ｐ（ｉ，ｊ）までの総抵抗値は、「接続点Ｐ（ｉ−１，ｊ）の抵抗値＋Ｒｍｉｎ」となる。電源５の正極から接続点Ｐ（ｉ，ｊ）まで電流が流れる経路として、接続点Ｐ（ｉ−１，ｊ−１）、Ｐ（ｉ−１，ｊ）、Ｐ（ｉ，ｊ−１）の夫々と電源５の正極までの抵抗値のうち、抵抗値が最も小さい接続点が選ばれる。このことは、（数１）の第２行目の式の右辺第２項、即ち、ｍｉｎ（ｆ（ｉ，ｊ−１）、ｆ（ｉ−１，ｊ）、ｆ（ｉ−１，ｊ−１））が実行されることに他ならない。そして、選択された接続点（例えば、接続点Ｐ（ｉ−１，ｊ））と接続点Ｐ（ｉ，ｊ）との間のメムリスタユニット４の抵抗値の最小値Ｒｍｉｎが、||ｘｉ−ｙｊ||に対応すると考えると、パターンマッチング装置２は、（数１）の第２行の式を実行しているとみなすことができる。
【００３０】
上記は、||ｘｉ−ｙｉ||≠０であると仮定した場合である。||ｘｉ−ｙｉ||＝０の場合は、コントローラ７は、図３におけるメムリスタユニット４ａ、４ｂ、４ｃの夫々においてバイパス経路４２を選択させる。
【００３１】
なお、格子回路３０において、格子の対角線上で隣接する接続点Ｐ（ｉ，ｊ）と接続点Ｐ（ｉ−１，ｊ−１）の間には２個のメムリスタユニット４が直列に接続されている。これは、本実施例において||ｘｉ−ｙｉ||の項が、要素ｘｉと要素ｙｉのマンハッタン距離を表していると定義したからである。「マンハッタン距離」は、先に説明した通りである。即ち、行方向あるいは列方向で隣接する場合の距離が１個のメムリスタユニット４の抵抗の最小値Ｒｍｉｎである場合、対角方向で隣接する場合の距離は、その２倍、即ち、２個のメムリスタユニット４の最小抵抗値の和（２Ｒｍｉｎ）となる。なお、||ｘｉ−ｙｉ||の項が、要素ｘｉと要素ｙｉが一致する場合は、||ｘｉ−ｙｉ||の項の値がゼロとなるので、直列に接続された２個のメムリスタユニット４はバイパス経路に設定されてよい。
【００３２】
数学的帰納法により、上記の説明は、ｉ＝１〜ｎ、ｊ＝１〜ｍの全てについて成立する。よって、コントローラ７が電源５から所定回数の電圧パルスを発生させた後、格子回路３０において最も多く電流が流れる経路の総抵抗値が、（数１）の第１行目の式、即ち、ｆ（ｎ，ｍ）に相当する。先に述べたように、ｆ（ｎ，ｍ）が、参照ベクトルＸと入力ベクトルＹの類似度を示すＤＴＷ距離Ｄ（Ｘ，Ｙ）を意味する。即ち、格子回路３０において電流が最も多く流れる経路の総抵抗値が、参照ベクトルＸと入力ベクトルＹの類似度を示す。総抵抗値が小さいほど、参照ベクトルＸと入力ベクトルＹは類似度が高いことを意味する。電流が最も多く流れる経路の総抵抗値は、格子回路３０に印加した電圧と流れる電流から求めればよい。あるいは、コントローラ７は、格子回路３０に接続されているメムリスタ４４の中で、抵抗値が最小値Ｒｍｉｎとなっているメムリスタ４４の数をカウントし、その数に最小値Ｒｍｉｎを乗じた値を総抵抗値として出力してもよい。図２を参照して説明したように、コントローラ７は、信号線Ｓ２によって各メムリスタ４４の抵抗値を知ることができる。
【００３３】
このように、図１の回路は、（数１）に示した動的時間伸縮法のアルゴリズムを実行することができる。コントローラ７が電源５から所定回数の電圧パルスを発生させた後、格子回路３０において電流が最も多く流れる経路の総抵抗値が、参照ベクトルＸと入力ベクトルＹの類似度Ｑ（図１参照）を表す。
【００３４】
なお、参照ベクトルＸと入力ベクトルＹはともに二値化ベクトルである。それゆえ、参照ベクトルＸの第ｉ要素（ｘｉ）と入力ベクトルＹの第ｊ要素（ｙｊ）が相違するとき、||ｘｉ−ｙｊ||は、ｉとｊの値に関わらず常に一定であり、その値が、メムリスタ４４の抵抗の最小値Ｒｍｉｎに相当する（ただし、先に述べたように、要素（ｘｉ）と要素（ｙｊ）が対角方向で隣接する場合は２Ｒｍｉｎとなる）。
【００３５】
コントローラ７は、例えば、次のように電源５の電圧を決める。コントローラ７は、参照ベクトルＸと入力ベクトルＹに応じて各メムリスタユニット４をバイパス経路４２とメムリスタ経路４３のどちらかに設定する。各メムリスタユニット４のメムリスタ４４の抵抗値は、初期値として最大値Ｒｍａｘに設定されている。その後、コントローラ７は電源５の電圧を徐々に高めながら電圧パルスを一定間隔で出力させる。電圧が低いうちは、いずれのメムリスタ４４にも電流が流れない。電圧を高めていくと、電源５とグランド９の間に接続されている格子回路３０において、最も抵抗値の低い経路上のメムリスタ４４の電圧が閾値を超える。コントローラ７は、そのときの電圧を保持し、繰り返しパルス電圧を印加する。パルス電圧を印加する毎にその経路上のメムリスタ４４の抵抗値が下がり、最終的には特定の経路上のメムリスタ４４は全て抵抗値が最小値Ｒｍｉｎになる。コントローラ７は、各メムリスタ４４の抵抗値をモニタしており、抵抗値が下がり始めたメムリスタ４４の抵抗値が最小値Ｒｍｉｎに達したら電圧パルスを止める。電流が最も多く流れた経路の総抵抗値が、ＤＴＷ距離、即ち、参照ベクトルＸと入力ベクトルの類似度を示す。上記は電圧の決め方の一例であり、上記の説明とは異なる規則で電圧を定めてもよい。
【００３６】
コントローラ７の処理をまとめると、次の通りである。コントローラ７には、ｎ次元の二値の参照ベクトルＸとｍ次元の二値の入力ベクトルＹが与えられる。コントローラ７は、格子回路３０の各行に対して参照ベクトルＸの各要素値を対応させるとともに各列に対して入力ベクトルＹの各要素値を対応させる。コントローラ７は、格子回路３０の接続点（ｉ，ｊ）に対応する参照ベクトルＸの要素値と入力ベクトルＹの要素値が等しい場合は、その接続点（ｉ，ｊ）と電源５に近い側で隣接する接続点（ｉ−１、ｊ）、（ｉ，ｊ−１）、及び、（ｉ−１、ｊ―１）の夫々とを接続しているメムリスタユニット４をバイパス経路４２に設定する。一方、コントローラ７は、接続点（ｉ，ｊ）に対応する参照ベクトルＸの要素値と入力ベクトルＹの要素値が等しくない場合は、その接続点（ｉ，ｊ）と電源５に近い側で隣接する接続点（ｉ−１、ｊ）、（ｉ，ｊ−１）、及び、（ｉ−１、ｊ―１）の夫々とを接続しているメムリスタユニット４をメムリスタ経路４３に設定する。そしてコントローラ７は、少なくとも一つのメムリスタ４４の両端に加わる電圧がメムリスタ４４の閾値電圧を超えるように電源５の出力電圧を調整して所定回数のパルス電圧を電源５から出力させる。最後にコントローラ７は、電源５からグランド９（別言すれば接続点（ｎ，ｍ））まで、格子回路３０において最も電流が流れる経路の総抵抗値を参照ベクトルＸと入力ベクトルＹの類似度Ｑとして出力する。総抵抗値（類似度Ｑ）が小さいほど、参照ベクトルＸと入力ベクトルＹの類似度が高いことを意味する。
【００３７】
コントローラ７は、格子回路３０に逆電圧を印加し、すべてのメムリスタ４４の抵抗値を最大値Ｒｍａｘに戻してから、別の入力ベクトルに対して上記の処理を繰り返す。
【００３８】
図４から図６を用いて一つの事例を説明する。この事例では、３次元の参照ベクトルＸ＝（１、１、０）と２次元の入力ベクトルＹ１＝（１、１）及びＹ２＝（０、０）の類似度を求める。図４は、パターンマッチング装置２ａの回路図である。パターンマッチング装置２ａは、接続点が３行２列の格子状に接続された格子回路３０ａを備える。接続点（１，１）と電源５は、２個のメムリスタユニット４ａを介して接続されている。行方向で隣接する接続点３の間にはメムリスタユニット４が接続されており、列方向で隣接する接続点３の間にもメムリスタユニット４が接続されている。接続点（ｉ，ｊ）と接続点（ｉ−１，ｊ−１）は２個のメムリスタユニット４の直列接続で接続されている。接続点（１，１）の対角に位置する接続点３ｆ（接続点（３，２））はグランド９に接続されている。なお、図４-図６では、コントローラ７の図示は省略した。
【００３９】
まず、参照ベクトルＸ（１，１，０）と入力ベクトルＹ１＝（１，１）との類似度を求める。不図示のコントローラ７は、参照ベクトルＸ＝（１，１，０）の各要素を格子回路３０ａの行方向の各接続点に対応させ、入力ベクトルＹ１＝（１，１）の各要素を格子回路３０ａの列方向の各接続点に対応させる。接続点（ｉ，ｊ）に対応する参照ベクトルＸの要素（Ｘｉ）と入力ベクトルＹ１の要素（ｙ１ｊ）が等しい場合は、接続点（ｉ，ｊ）と電源５に近い側で隣接する接続点（ｉ−１，ｊ−１）、（ｉ−１，ｊ）、（ｉ，ｊ−１）との間のメムリスタユニット４をバイパス経路４２（図２参照）に設定する。接続点（ｉ，ｊ）に対応する参照ベクトルＸの要素（Ｘｉ）と入力ベクトルＹ１の要素（ｙ１ｊ））が等しくない場合は、接続点（ｉ，ｊ）と電源５に近い側で隣接する接続点（ｉ−１，ｊ−１）、（ｉ−１，ｊ）、（ｉ，ｊ−１）との間のメムリスタユニット４をメムリスタ経路４３（図２参照）に設定する。入力ベクトルＹ１＝（１，１）の場合、接続点３ａ（１，１）、３ｂ（１，２）、３ｃ（２，１）、３ｄ（２，２）において、参照ベクトルＸの要素と入力ベクトルＹ１の要素が等しくなる。それゆえ、図５に示すように、メムリスタユニット４ａ、４ｂ、４ｃ、４ｄ、４ｆではバイパス経路に設定される。図５では、バイパス経路に設定されたメムリスタユニット４ａ、４ｂ、４ｃ、４ｄ、４ｆを点線で描いてある。
【００４０】
接続点３ｅ（３，１）と３ｆ（３，２）では参照ベクトルＸの要素と入力ベクトルＹ１の要素が異なる。それゆえ、メムリスタユニット４ｊ、４ｇ、４ｈ、４ｋでは、メムリスタ経路４３（図２参照）に設定される。そして、コントローラ７は、電源５から所定回数のパルス電圧を出力させる。図５によく示されているように、太矢印線で示す経路Ｒ１が、メムリスタ経路４３が選択されているメムリスタユニット４の数が最も少ない。即ち、経路Ｒ１の合計抵抗値が最も小さくなる。図５では、経路Ｒ１上のメムリスタユニット４ｈのみ、グレーで示してある。電源５からパルス電圧が出力されると、太線矢印Ｒ１上のメムリスタユニット４ｈのみ、印加される電圧が閾値電圧を超え、電流が流れる。その結果、メムリスタユニット４ｈのメムリスタ４４だけ、抵抗値が最小値Ｒｍｉｎとなる。経路Ｒ１上の総抵抗値は、Ｒｍｉｎとなる。即ち、入力ベクトルＹ１の場合、参照ベクトルＸとの類似度ＱはＲｍｉｎとなる。
【００４１】
次に、入力ベクトルＹ２＝（０，０）の場合を説明する。図６は、入力ベクトルがＹ２の場合の各メムリスタユニット４の設定状態を示した図である。図５の場合と逆に、コントローラ７は、メムリスタユニット４ｇ、４ｊ、４ｈ、４ｋをバイパス経路４２（図２参照）に設定し、それ以外のメムリスタユニット４ａ、４ｂ、４ｃ、４ｄ、４ｅ、４ｆをメムリスタ経路４３（図２参照）に設定する。太矢印線で示す経路Ｒ２が最もメムリスタ４４の少ない経路である。図６では、経路Ｒ２上のメムリスタユニット（２個のメムリスタユニット４ａとメムリスタユニット４ｃ）をグレーで示してある。コントローラ７が所定数のパルス電圧を印加すると、経路Ｒ２上のメムリスタユニット４ａ、４ｃのメムリスタ４４に印加される電圧が閾値電圧を超え、それらのメムリスタ４４の抵抗値は最小値Ｒｍｉｎとなる。入力ベクトルＹ２の場合、３個のメムリスタユニット４ａ、４ｃのメムリスタ４４の抵抗値が最小値Ｒｍｉｎに下がる。経路Ｒ２上の総抵抗値は、３×Ｒｍｉｎとなる。即ち、入力ベクトルＹ２の場合、参照ベクトルＸとの類似度Ｑは３×Ｒｍｉｎとなる。
【００４２】
図５と図６の結果から、入力ベクトルＹ１とＹ２では、入力ベクトルＹ１の方が参照ベクトルＸに対する類似度が高いことが判明する。類似度は、電源５が所定回数の電圧パルスを出力した後に判明する。パターンマッチング装置２ａは、所定回数の電圧パルスを出力するだけで、動的時間伸縮法の計算が実行される。それゆえ、パターンマッチング装置２ａは、２個のベクトルの類似度を高速に求めることができる。
【００４３】
メムリスタ４４（図２参照）の動作はシミュレーションで検証することができる。次の（数２）に、メムリスタ４４の動作の数式モデルを示す。（数２）において、記号Ｍがメムリスタ４４の抵抗値を表す。記号ＶＴはメムリスタ４４の閾値電圧を表す。記号ＶＭとＩＭは夫々、メムリスタ４４に印加される電圧と流れる電流を表す。記号ＲｍｉｎとＲｍａｘは、それぞれ、メムリスタ４４の抵抗の最小値と最大値を表す。記号Ｂは定数を表す。記号Ｔ（・）は、ステップファンクションを示し、かっこ内が正値のときに「１」となり、それ以外のときには「０」となる。
【００４４】
【数２】
2018206193.tif 000004
【００４５】
メムリスタ４４の動作は、抵抗値Ｍの時間変化（ｄＭ／ｄｔ）（ｔは時間）で表される。（数２）の第２行目の式が、抵抗値Ｍの時間変化を表す式である。第２行目の式の２個のステップファンクションの積は、最小値Ｒｍｉｎ≦抵抗値Ｍ≦最大値Ｒｍａｘの間で「１」となり、それ以外の範囲では「０」となる。すなわち、抵抗値Ｍは、最小値Ｒｍｉｎ≦抵抗値Ｍ≦最大値Ｒｍａｘの間でのみ変化し、それ以外の範囲では変化しない。また、（ＶＭ−０．５［|ＶＭ＋ＶＴ|−|ＶＴ―ＶＭ|］）の項は、印加電圧ＶＭ≧閾値電圧ＶＴのときに（ＶＭ−ＶＴ）となり、印加電圧ＶＭ＜閾値電圧ＶＴのときにゼロとなる。従って、（数２）の第２行目の式は、最小値Ｒｍｉｎ≦抵抗値Ｍ≦最大値Ｒｍａｘかつ、印加電圧ＶＭ≧閾値電圧ＶＴのとき、抵抗値Ｍの時間変化（ｄＭ／ｄｔ）がＢ・（ＶＭ−ＶＴ）となり、それ以外ではｄＭ／ｄｔ＝０であることを示している。（数２）を使うことで、パターンマッチング装置２、２ａの動作をシミュレーションすることができる。
【００４６】
実施例で説明した技術に関する留意点を述べる。実施例では、対角方向で隣接する接続点３の間は、２個のメムリスタユニット４の直列接続で接続されている。これは、対角方向で隣接する接続点のマンハッタン距離を考慮するためである。格子回路を次のように構成しても、マンハッタン距離を考慮することができる。即ち、格子回路３０にて対角方向で隣接している接続点３同士を接続するメムリスタユニット４のメムリスタ４４として、最小抵抗値が行方向及び列方向で隣接している接続点同士を接続するメムリスタユニットのメムリスタの最小抵抗値よりも大きいものを選択する。
【００４７】
距離の定義を単純なユークリッド距離で定義してもよい。即ち、先の（数１）において、||ｘｉ−ｙｉ||＝（ｘｉ−ｙｉ）２と定義してもよい。その場合は、格子回路３０において、格子の対角線上で隣接する接続点Ｐ（ｉ，ｊ）と接続点Ｐ（ｉ−１，ｊ−１）との間も１個のメムリスタユニット４で接続すればよい。同様に、Ｐ（１，１）と電源５との間も１個のメムリスタユニット４で接続すればよい。２つのベクトルの要素の間の距離の定義に応じて、対角方向で隣接する接続点の間を接続するメムリスタユニット４の個数を調整すればよい。なお、行方向、あるいは、列方向で隣接する接続点間の距離は、１個のメムリスタユニット４に含まれるメムリスタ４４の抵抗の最小値Ｒｍｉｎで表される。それゆえ、距離の定義に応じて、対角方向で隣接する接続点間を接続するメムリスタユニット（メムリスタ）の抵抗値の最小値を調整してもよい。多くの距離の定義では、行方向あるいは列方向で隣接する接続点間の距離より、対角方向で隣接する接続点間の距離の方が大きい。それゆえ、格子回路にて対角方向で隣接している接続点同士を接続するメムリスタユニットのメムリスタの最小抵抗値を、行方向及び列方向で隣接している接続点同士を接続するメムリスタユニットのメムリスタの最小抵抗値よりも大きくするとよい。
【００４８】
実施例では、ｍ次元の参照ベクトルとｎ次元の入力ベクトルの類似度を求めるパターンマッチング装置を例示した。参照ベクトルと入力ベクトルを入れ替えてもよい。即ち、実施例の装置は、ｎ次元の参照ベクトルとｍ次元の入力ベクトルの類似度を求めることもできる。
【００４９】
以上、本発明の具体例を詳細に説明したが、これらは例示に過ぎず、特許請求の範囲を限定するものではない。特許請求の範囲に記載の技術には、以上に例示した具体例を様々に変形、変更したものが含まれる。本明細書または図面に説明した技術要素は、単独であるいは各種の組合せによって技術的有用性を発揮するものであり、出願時請求項記載の組合せに限定されるものではない。また、本明細書または図面に例示した技術は複数目的を同時に達成し得るものであり、そのうちの一つの目的を達成すること自体で技術的有用性を持つものである。
【符号の説明】
【００５０】
２、２ａ：パターンマッチング装置
３、３−３ｇ：接続点
４、４ａ−４ｋ：メムリスタユニット
５：電源
７：コントローラ
９：グランド
３０、３０ａ：格子回路
４１：切換器
４２：バイパス経路
４３：メムリスタ経路
４４：メムリスタ
【図１】
2018206193.tif 000005
【図２】
2018206193.tif 000006
【図３】
2018206193.tif 000007
【図４】
2018206193.tif 000008
【図５】
2018206193.tif 000009
【図６】
2018206193.tif 000010