JPH07192477A - 検索メモリ装置、検索メモリ、データ検索装置及び検索メモリの使用方法 - Google Patents

Abstract

(57)【要約】 【目的】 内容参照アクセスが可能で、更に効率的なキ
ーストリングデータの合致データセットのアクセスが可
能な大容量のメモリ装置の構造を実現する。 【構成】 ストリングデータとこれに対応するデータセ
ットを入出力する入出力線ＩＯｉ、／ＩＯｉをメモリセ
ルのビット線Ｂｉ、／Ｂｉに接続する巡回読出し回路Ｃ
ＲＣと、検索用のストリングデータを入力するためのス
トリングデータ線ＳＢｉのデータを一時的に格納するス
トリングビットレジスタＳＢＲと、メモリセルのビット
線Ｂｉ、／Ｂｉのストリングデータをストリングビット
レジスタＳＢＲに格納したデータと比較するビット比較
器ＢＣＭを備え、ビット比較器ＢＣＭによりビット線Ｂ
ｉ、／Ｂｉのストリングデータを検索し、検索結果に基
づき、ストリング合致マーク回路ＳＭＭによりビット線
Ｂｉ、／Ｂｉの特定ビット位置に一定のデータを書き込
み、この特定ビットのデータに基づき巡回読出し回路Ｃ
ＲＣによるメモリアクセスを行わせる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、検索メモリ及び検索デ
ータ転送装置に係り、特に大容量の内容参照アクセスで
きるメモリにおいて、キーストリングデータの合致デー
タセットの効率的なアクセスと大容量化を図った検索メ
モリ装置及び検索データ転送装置に関する。

【０００２】

【従来の技術】近年の、半導体メモリの容量の増大とあ
いまって、情報機器で扱うデータの量も膨大になってき
ている。このような状況において、蓄積されたデータの
中から、条件にかなったデータを見つけ出す、いわゆる
データ検索の重要性がますます増大してきている。

【０００３】一方、一般的なメモリ装置においては、図
２０に示すように、アドレスＡｄｄとセルデータＣＤが
一対一に対応している、このため、データ検索するに
は、全てのアドレスをアクセスし、セルデータを読み出
し、その上でデータ検索する必要がある。ところが、メ
モり容量が大きくなると、それに応じて、メモリアクセ
スとデータ検索に要する時間は増大する。

【０００４】このような状況を解決するために、近年、
内容参照アクセスの方法が提案されている。これは、メ
モリ中の記憶データのひとまとまりの一部をキーストリ
ングデータとし、メモリのアクセスの際に、このキース
トリングを与える、これが合致するデータのまとまりの
みをアクセスするものである。

【０００５】図２１は、かかる内容参照アクセスの概念
を示す説明図である。

【０００６】キーストリングデータＫＳＤは、例えば２
の８乗個のデータの中から任意に設定できる。この１つ
のキーにどのようなデータセットＤＳを対応させるか
は、全く任意である。例えば、キーストリングデータ
に、点線内のデータセットＤＳ0でも、実線内のデータ
セットＤＳ1 で対応させることができる。このように、
対応付けにより記憶されたデータセットの読み出しは、
メモリ内の全てのデータを読み出すのではなく、キース
トリングデータを与えることにより行われる。

【０００７】上記のように、大容量のメモリのデータ検
索に適した、内容参照アクセス方式のダイナミックメモ
リについては、米国特許第４，９８９，１８０号明細書
に“Ｄｙｎａｍｉｃ Ｍｅｍｏｒｙ ｗｉｔｈ Ｌｏｇ
ｉｃ−Ｉｎ−Ｒｅｆｒｅｓｈ”として開示されている。
ここで開示されているのは、ダイナミックメモリのリフ
レッシュの際に、併せてキーストリングデータによるデ
ータ検索を行い、一致を検出した場合には、データの特
定ビットをマーク用のビットとして特定のデータを書き
込んでおく、というものである。また、データ読み出し
の際には、このビットを検出して読み出し、検索行に複
数の一致データがあるときには優先回路がひとつの一致
データのみを選択して出力し、２番目以降の一致データ
については、改めて行を選び直し、読み出すという考え
方が示されている。

【０００８】

【発明が解決しようとする課題】従来のメモリ装置は、
以上のように構成されるので、技術的な思想的としては
成立しても、具体的に大容量のメモリ、例えばＤＲＡＭ
等に直ちに適用するのは困難である。また、同一の行に
読み出し対象としての複数のデータがある場合は、読み
出し効率が非常に悪くなるという問題もある。

【０００９】本発明は、上記に鑑みてなされたもので、
その目的は、内容参照アクセスが可能で、更に効率的な
キーストリングデータの合致データセットのアクセスが
可能な大容量のメモリ装置及びデータ転送装置を提供す
ることにある。

【００１０】

【課題を解決するための手段】上記目的を達成するため
に、本発明では、ほぼ行列状に配列された複数のメモリ
セルから構成され、複数のカラムブロックに分割された
メモリセルアレイと、外部から入力されたストリングデ
ータと各カラムブロック内のデータとを比較し、この比
較結果に応じてカラムブロックのいくつかにマークを付
し、このマークが付されたカラムブロック内のデータを
順次転送出力する検索データ転送手段とから構成される
検索メモリ装置を提供する。

【００１１】

【作用】上記手段を用いることにより、外部から入力さ
れたストリングデータと各カラムブロック内のデータと
を比較し、この比較結果に応じてカラムブロックのいく
つかにマークを付するステップにより、一致検索が行わ
れる。続いて、第２のステップにおいて検索データ転送
手段がこのマークが付されたカラムブロック内のデータ
を順次転送出力する。この結果、内容参照アクセスが可
能で、効率的なキーストリングデータの合致データセッ
トのアクセスが可能となる。

【００１２】

【実施例】以下、図面を参照しながら本発明の実施例を
説明する。

【００１３】図１は本発明の第１の実施例にかかる検索
メモリを用いた検索システムの概略構成図である。この
検索システムは検索メモリ装置１００と、検索制御回路
２００とから構成され、両者は外部バス１０８にて接続
されている。

【００１４】検索メモリ装置１００はメモリセルアレイ
１０１、検索データ転送回路１０２、ロウデコード回路
１０３、データ入出力回路１０４及び制御回路１０５か
ら構成される。また、メモリセルアレイ１０１及び検索
データ転送回路１０２は複数のカラムロックＣＢに分割
されており、このカラムブロック毎にデータ転送が行わ
れる。さらに、検索データ転送回路１０２とデータ入出
力回路１０４とはデータバス１０６及びストリングデー
タバス１０７により接続されている。

【００１５】メモリセルアレイ１０１は、ダイナミック
型セル、スタティック型セル等のランダムアクセスメモ
リセルもしくはマスクＲＯＭセル、書き込み・消去可能
な不揮発性メモリセル等を行列状に配置して構成されて
いる。

【００１６】検索データ転送回路１０２は外部から入力
された若しくは前サイクルにより得られたストリングデ
ータを基に各カラムブロック毎に読出データの比較を行
い、比較結果を記憶しておき、この記憶された比較結果
に基づいてデータ転送を行う。このデータ転送は制御回
路１０５より与えられるクロック信号に基づいて、順次
行われる。このデータ転送は全てのカラムブロックのデ
ータにつき行われるのではなく、上記比較結果に基づい
て、部分的に行われる。後述するように、この検索デー
タ転送回路１０２が比較結果に基づいて部分的にデータ
転送を行うことが検索速度の向上に寄与するのである。

【００１７】制御回路１０５はロウデコード回路１０３
のアドレス指定動作の制御、検索データ転送回路１０２
の各種動作の制御、データ入出力回路１０４の動作制御
等を行う。特に、検索制御回路２００より与えられる信
号に基づきクロック信号を発生させ、検索データ転送回
路１０２のデータ転送を順次制御する。

【００１８】検索制御回路２００はレジスタファイル２
０１、ストリンデータレジスタ２０２、データ入出力回
路２０３、制御回路２０４から構成されている。レジス
タファイル２０１は検索メモリ装置１００中の検索デー
タ転送回路１０２により順次転送された検索データを順
次記憶する。ストリングデータレジスタ２０２は検索デ
ータ転送回路１０２に与えるストリングデータを保持す
る。データ入出力回路１０４は外部データバス１０８と
のインタフェースを行う。制御回路２０４はレジスタフ
ァイル２０１、ストリングデータレジスタ２０２、デー
タ入出力回路２０３等を制御すると共に、検索メモリ装
置１００内の制御回路１０５に制御信号を与える。以上
のように構成することにより、検索制御回路２００は検
索メモリ１００にストリングデータを与え、検索データ
を順次受領するとともに内部のレジスタファイル２０１
に記憶し、場合によっては、レジスタファイル２０１に
記憶された検索データの内から次サイクルのストリング
データを選び出すという動作を行う。

【００１９】続いて、図２に検索データ転送回路１０２
の回路構成を示す。検索データ転送回路は、前述したよ
うに、各カラムブロックＣＢに属するカラム検索単位か
ら構成される。また、各カラム検索単位乃至各カラムブ
ロックは８ビットのデータバスＩＯ（図１におけるデー
タバス１０６の延長したもの）及び８ビットのストリン
グデータバスＳＢ（図１におけるストリングデータバス
１０７の延長したもの）と接続されている。

【００２０】各カラムブロックＣＢはメモリセルと接続
された８ビットの各カラムデータ線束３０３を含み、こ
のカラムデータ線束３０３は１ビットの上位カラムデー
タ線３０３1 と７ビットの下位カラムデータ線束３０３
2 から構成される。各カラムブロックＣＢはさらに、カ
ラムゲート回路３０１、巡回読出し回路ＣＲＣ、ストリ
ングビットレジスタＳＢＲ、ビット比較・マーク回路３
０２から構成される。

【００２１】カラムゲート回路３０１はデータバスＩＯ
とカラムデータ線束とを接続する。

【００２２】巡回読出し回路は１ビットの上位カラムデ
ータ線のデータ及び上側に隣接するカラムブロックより
供給される信号ＣＲに基づいてカラムゲート回路３０１
を制御する。

【００２３】ストリングビットレジスタＳＢＲは８ビッ
トのレジスタ列から構成され、ストリングデータバスＳ
Ｂのデータを取り込み、これを一時的に保持する。

【００２４】ビット比較・マーク回路３０２はカラムデ
ータ線束３０３の８ビットのデータとストリングビット
レジスタＳＢＲに保持されている８ビットのストリング
データとを比較し、比較結果をカラムデータ線束３０３
に書き戻す。この書き戻し手法は後述するように種々の
方法があるが、代表的なものとして、一致した場合には
“Ｈ”データを次の（図２において下側に隣接したカラ
ムブロック内の）上位カラムデータ線３０３1' に書き
込む場合、一致した場合には“Ｈ”データを自分自身の
（カラム検索単位が属するカラムブロックの）カラムデ
ータ線３０３1に書き込む場合等がある。このビット比
較・マーク回路３０２は後述するように、ビット比較器
ＢＣＭ及びストリング合致マーク回路ＳＭＭから構成さ
れる。

【００２５】図３は本発明の一実施例にかかるメモリ装
置のブロック図である。図３に示すように、ビット線Ｂ
０〜Ｂ７は８ビット構成となっており、それぞれビット
線／Ｂ０〜／Ｂ７とペアをなしている。これら８ビット
のビット線対が一つのカラムブロックＣＢ1 を構成す
る。図２において、カラムデータ線束３０３はこの８ビ
ット線対に相当し、上位カラムデータ線３０３1 はビッ
ト線対Ｂ０、／Ｂ０に相当し、下位カラムデータ線束３
０３2 はビット線対Ｂ１、／Ｂ１〜Ｂ７、／Ｂ７にそれ
ぞれ対応する。この中で、キーストリングデータは８ビ
ットであり、このキーストリングデータに続く８ビット
のデータセットを、キーストリングに属する１つの内容
データとしている。９ビット目は次に続くカラムデータ
線束３０３' の上位カラムデータ線３０３1' に対応す
ると同時にカラムデータ線束３０３のデータに対応する
属性ビット（すなわちマークビット）として用いられ
る。

【００２６】なお、図中で、ダイナミックセルは図示し
ていない。

【００２７】各カラム線にはそれぞれ、センス増幅器Ｓ
ＡとイコライザＥＱが接続される。

【００２８】一方、データバスＩＯは８ビット分であ
り、ＩＯ０、／ＩＯ０〜ＩＯ７、／ＩＯ７とそれぞれペ
アを構成しており、これらのＩＯ線ペアはＩＯＧ（Ｉｎ
ｐｕｔＯｕｔｐｕｔ Ｇａｔｅ）信号によって制御され
るゲートＧ１を介してビット線対に接続される。これら
ゲートはカラムゲート回路３０１を構成している。巡回
読出し回路ＣＲＣはこれらゲートＧ１をオン・オフ制御
する。この巡回読出し回路ＣＲＣには、ＩＯＧＯＮ（Ｉ
Ｏ Ｇａｔｅ ＯＮ）信号、ＳＡＣ（Ｓｅｒｉａｌ Ａ
Ｃｃｅｓｓ）信号が供給される。なお、巡回読出し回路
ＣＲＣには他の巡回読出し回路（図中上側のカラムブロ
ックに属する巡回読出し回路）ＣＲＣからＣＲ信号を入
力され、次に続く巡回読出し回路（図中下側のカラムブ
ロックに属する巡回読出し回路）ＣＲＣ' にＣＲ’信号
を出力する。

【００２９】一方、ストリングビットレジスタＳＢＲは
Ｂ０〜Ｂ８のビット線対毎に対応して設けられる。キー
ストリングデータとしては、キーストリングビットデー
タ線ＳＢ０〜ＳＢ７の８ビットが対応している。ストリ
ングビットレジスタＳＢＲにはＳＴＲ（Ｓｔｒｉｎｇ
ＴＲａｎｓｆｅｒ）信号が与えられ、キーストリングビ
ットデータ線ＳＢ０−ＳＢ７からキーストリングデータ
を取り込むようになっている。

【００３０】ストリングビットレジスタＳＢＲにはビッ
ト比較器ＢＣＭが接続される。ビット比較器ＢＣＭには
ＣＭＰ（ＣｏＭＰａｒｅ）信号とＣＭＰＴＲ（ＣｏＭＰ
ａｒｅ ｄａｔａ ＴＲａｎｓｆｅｒ）信号が与えられ
る。

【００３１】ビット比較器ＢＣＭは、ストリング合致マ
ーク回路ＳＭＭに、ＢＭＴＣ（Ｂｉｔ ＭａＴＣｈ）ｉ
（０−７）信号を接続する。ストリング合致マーク回路
ＳＭＭには、他のストリング合致マーク回路ＳＭＭから
のＳＭＴＣ（Ｓｔｒｉｎｇ ＭａＴＣｈ）信号が入力さ
れると共に、他のストリング合致マーク回路ＳＭＭにＳ
ＭＴＣ’信号を出力する。一方、ストリング合致マーク
回路ＳＭＭには、ＲＳＭＫ（ＲｅＳｅｔ ＭａｒＫ）信
号の反転信号である／ＲＳＭＫ信号、ＲＳ（ＲｅＳｅ
ｔ）信号、ＭＫＣＭＰ（ＭａｒＫ ＣｏＭＰａｒｅ）信
号の反転信号である／ＭＫＣＭＰ信号、ＭＫＣＮＴ（Ｍ
ａｒＫ ＣｏＮｔｅｎＴ）信号の反転信号である／ＭＫ
ＣＮＴ信号が入力される。ストリング合致マーク回路Ｓ
ＭＭの間はＳＭＴＣ’信号により接続される。

【００３２】なお、このメモリ装置には、カラムデコー
ダは必要ない。ロウデコード回路は図１に示したよう
に、メモリチップ内部または外部から供給されるアドレ
スをデコードして、ある行のワード線を活性化して選択
する。

【００３３】以上述べたような構成において、次に、そ
の動作を説明する。

【００３４】まず、メモリセルアレイに対するデータの
書き込み動作について説明する。

【００３５】セルアレイへのデータの書き込みにおいて
は、あるワード線を選択してセルとビット線をつないで
おき、ＩＯ線対ＩＯ０〜ＩＯ７、／ＩＯ０〜／ＩＯ７を
ビット線対Ｂ０〜Ｂ７、／Ｂ０〜／Ｂ７に接続すること
により行われる。図３では、８ビットが同時に書き込ま
れる場合を想定しているので、ＩＯ線ペアはビット分あ
る。

【００３６】書き込みは、選択されたワード線に属する
セルに対して、８ビットずつシリアルに行われる。ワー
ド線を選択した後に、ＩＯＧＯＮ信号を一回“Ｈ”レベ
ルとしてＣＲＣをリセットした後、ＳＡＣ信号をパルス
状に“Ｈ”レベルとして巡回読出し回路ＣＲＣを全て選
択状態にする。その後に、ＣＲ信号をパルス的に与える
と、ＣＲ信号が“Ｈ”レベルの期間、ＩＯＧ信号が
“Ｈ”レベルとなり、Ｉ／Ｏ線ペアとビット線がつなが
る。つまり、ＣＲ信号のパルス毎に巡回読出し回路ＣＲ
Ｃが順番に選択されて、８カラムずつが順番にＩ／Ｏ線
につながる。この状態において、Ｉ／Ｏ線ペアに適宜デ
ータを与えることにより、セルにデータを書き込むこと
ができる。

【００３７】以上のような動作を通じて、メモリセルへ
のデータ書き込み時には、データセットに対応付けてキ
ーストリングデータも併せて格納する。ここで、キース
トリングデータとは、データ検索キーとして用いるデー
タのことであり、通常データ構造の先頭に位置する。す
なわち、カラムブロック１がキーストリングデータに対
応するとすると、カラムブロック２、３、４等が被検索
データである。さらに、カラムブロック５がキーストリ
ングデータに対応するとすると、カラムブロック６、
７、８が被検索データである。

【００３８】次に、データの検索について説明する。

【００３９】データの書き込み時には、メモリセルには
キーストリングデータをデータセットに対応付けして格
納したが、これを検索して読み出すための準備動作を説
明する。

【００４０】先ず、ＳＴＲ信号を“Ｈ”レベルにして、
ストリングビット０〜７に対応するストリングビットレ
ジスタＳＢＲを開き、この状態でストリングビットデー
タ線ＳＢ０〜ＳＢ７に検索するキーストリングデータを
与える。その結果、ストリングビットレジスタＳＢＲに
キーストリングデータが書き込まれる。ストリングビッ
トレジスタＳＢＲは８ビット単位で構成されているが、
この場合、８ビット分の全てのストリングビットレジス
タＳＢＲに同じキーストリングデータが書き込まれる。

【００４１】検索はセルアレイの行単位で行われて行く
ので、図３に示したようにメモリセルアレイとしてＤＲ
ＡＭセルアレイを用いた場合においては、セルデータの
リフレッシュと同時に行うことができる。その動作順
は、先ず、従来のＤＲＡＭと同じように、ある行を選択
して、ワード線を活性化し、セルデータをセンス増幅器
ＳＡでセンスする。次に、ビット線Ｂｉ、／Ｂｉにおい
て確定したデータを、ＣＭＰＴＲ信号をパルス状に
“Ｈ”レベルにすることにより、ビット比較器ＢＣＭに
取り込む。次に、ＣＭＰ信号を“Ｈ”レベルにすること
によって、カラムのビット線に確定したデータとストリ
ングビットレジスタＳＢＲに書き込まれた各ビットのデ
ータの比較が行われる。比較したビットのデータが一致
した場合は、ビット比較器ＢＣＭから出ている／ＢＭＴ
Ｃｉ信号が“Ｌ”レベルに変化する。８ビットのストリ
ングビットの全てが一致すると、ストリング合致マーク
回路ＳＭＭからのＳＭＴＣ信号が“Ｈ”レベルとなる。
なお、この信号はＳＭＴＣ’信号として、次のストリン
グ合致マーク回路ＳＭＭに供給される。

【００４２】ここで、この一致検索結果をどのように使
うかで、動作が２通りに分かれる。始めに、キーストリ
ングデータに属するデータ検索についてを説明し、続い
て、キーストリングデータがあるカラムの検索について
説明する。

【００４３】（１）キーストリングデータに属するデー
タ検索 検索の結果、キーストリングに一致するデータが見つか
った場合、一致したキーストリングデータに隣接する８
ビットが、それに属するデータであることがわかる。こ
の場合、このデータセットにマークを付ける必要があ
る。本実施例では、マーク用のビットは８ビット単位の
第０ビットとしている。このため、図に示されている始
めの８ビット（０〜７）が一致したキーストリングデー
タとすると、ＳＭＴＣ’信号は“Ｈ”レベルとなり、図
３のＢ８と／Ｂ８のカラムのストリング合致マーク回路
ＳＭＭに与えられる。ここで／ＭＫＣＮＴ信号を“Ｌ”
レベルにすると、Ｂ８／Ｂ８のカラムに“１”が書き込
まれることになる。このような、“１”の書き込みは、
選択活性化されている行の全ての一致ストリングの属す
るカラムブロックで同時に行われる。

【００４４】（２−１）キーストリングデータがあるカ
ラムの検索（マークのセット） キーストリングデータの一部の書き換えや、一致したデ
ータセット自体の変更書き替え等では、一致したキース
トリングデータのあるカラムをマークしておく必要があ
る。この時には、ストリング合致マーク回路ＳＭＭは自
分自身で作ったＳＭＴＣ’信号を用いて、一致した８ビ
ットの第０ビットに“１”マークの書き込みを行う。こ
のために、／ＭＫＣＭＰ信号を／ＭＫＣＮＴ信号の代わ
りに“Ｌ”レベルにする。

【００４５】（２−２）キーストリングデータがあるカ
ラムの検索（マークのリセット） また、キーストリングデータ自体にマークの第０ビット
が“１”であるものを用いることもあるが、一致したス
トリングでは、このマークをリセットしたいこともあ
る。これを行うのが／ＲＳＭＫ信号であり、これを
“Ｌ”レベルにすると、ストリング合致マーク回路ＳＭ
Ｍは自分自身が作ったＳＭＴＣ’信号が“Ｈ”レベルで
あれば、そのストリングデータの第０ビットに“０”を
書き込む。

【００４６】以上のような動作を、各行のリフレッシュ
の間に行うことにより、全セルに対する検索を、リフレ
ッシュと同時に行うことができる。また、検索されて選
ばれたストリングは、その第０ビットが“１”となって
マークされるか、または、“０”にリセットされる。

【００４７】以上説明したように、一致検索の結果に関
して、２通りの処理を説明したが、次に、選択されたス
トリングへのアクセスについて説明する。

【００４８】アクセスは第０ビットが“１”にマークさ
れたストリングに対して行われる。マークされたストリ
ングは多数あり、選択された１つの行のなかにも複数の
マークされたストリングが存在し得る。

【００４９】これらに対しては、巡回的にアクセスす
る。つまり、ある行にマークされたストリングが存在す
るかどうかは、アクセス時には不明であるが、先ずは検
索したい行を選択し、活性化する。次に、センスされた
各カラムのうちで、ストリングの第０ビットを巡回読出
し回路ＣＲＣに取り込むために、ＩＯＧＯＮ信号を
“Ｈ”レベルにパルス状に変化させる。その後、ＩＯＧ
ＯＮ信号を“Ｌ”レベルにし、普通のＤＲＡＭのページ
モードでのアクセスと同様に、ＣＲ信号をトグルする。
その結果、ＣＲ信号が“Ｈ”レベルの期間、選択された
行内で、先ず最初のマークされたストリングの８ビット
がＩ／Ｏ線に接続される。

【００５０】更に、ＣＲ信号のトグルを続けると、順番
にマークされたストリングに対するアクセスができ、そ
のストリングに対するデータの読み出しと書き込みを行
うことができる。

【００５１】選択された行にマークされたストリングが
存在しない場合や最後のマークされたストリングがアク
セスされた後に、ＣＲ信号が“Ｈ”レベルになると、Ｃ
ＲＬ信号が“Ｈ”レベルとなる。これで、この行には、
アクセスすべきストリングが存在しないことが判る。

【００５２】更に、別の行に対してアクセスを行うため
には、同様の動作をそれぞれの行について実施すること
により、マークされたストリングのアクセスができる。
そして、メモリの全ての行に対して、同様のアクセス動
作を行えば、リフレッシュ動作と同時にアクセス動作を
行うことができる。

【００５３】以上、キーストリングデータとデータセッ
トの書き込み、ストリングの検索、マークされたストリ
ングへのアクセスについてＤＲＡＭセルを用いた例につ
いて説明した。しかし、上述の構成はＤＲＡＭのみでな
く、ＳＲＡＭ等のランダムアクセスメモリに用いること
ができることは言うまでもない。さらに、ＮＡＮＤ型Ｅ
ＥＰＲＯＭと上記構成は非常に相性がよい。ＮＡＮＤ型
ＥＥＰＲＯＭは各列毎にデータラッチ兼センスアンプを
有しており、イコライズ回路ＥＱを除き、図３と全く同
一の回路構成を用いることができるからである。さら
に、漢字ＲＯＭの検索等に用いる場合は、メモリセルア
レイはＲＯＭセルアレイであることが必要であろう。

【００５４】次に、図３の回路中の個々の要素を詳細に
説明する。

【００５５】図４は巡回読出し回路ＣＲＣの詳細な構成
を示すブロック図である。図４に示すように、ビット線
につながるデータＢ０、又はＢ８はＮチャンネルＭＯＳ
トランジスタ４を介して入力され、インバータ６の入力
側、インバータ８の出力側、ナンド回路２２、Ｎチャン
ネルＭＯＳトランジスタ１２のドレインに供給される。
トランジスタ４のゲートとＮチャンネルＭＯＳトランジ
スタ１６のゲートにはＩＯＧＯＮ信号が入力される。Ｓ
ＡＣ信号はＮチャンネルＭＯＳトランジスタ２のゲート
に入力される。トランジスタ２のドレインはインバータ
６の出力側、インバータ８の入力側、ＮチャンネルＭＯ
Ｓトランジスタ１０のゲート、ナンド回路１８に接続さ
れる。ＣＲ信号はナンド回路１８、２２とトランジスタ
１２のソースに供給される。トランジスタ１６のドレイ
ンはＰチャンネルＭＯＳトランジスタ１４のドレインと
トランジスタ１２のゲートと、トランジスタ１０のドレ
インに接続される。ナンド回路２２の出力はトランジス
タ１４のゲートとインバータ２４に与えられる。また、
ナンド回路２０の出力はインバータ２０に与えられる。
インバータ２０の出力はＣＲ’信号として導出され、イ
ンバータ２４の出力はＩＯＧ信号として導出される。ト
ランジスタ２、１０、１６の各ソースは接地され、トラ
ンジスタ１４のソースは電源に接続される。

【００５６】以上述べたような構成において、Ｂ０、Ｂ
８とあるのが、図３のストリングデータの第０ビットの
カラムに対応するビット線の、マークされた場合に
“Ｈ”レベルとなるビットである。このビット線のレベ
ルはＩＯＧＯＮ信号が“Ｈ”レベルの期間にトランジス
タ４を通じてこの回路に取り込まれる。レベルを取り込
んだ後は、ビット線とこの巡回読出し回路ＣＲＣとは切
り離される。ここで、ＳＡＣ信号を“Ｈ”レベルにする
と、ビット線のレベルに関係なく、巡回読出し回路ＣＲ
Ｃは、ビット線が“Ｈ”レベルである時と同じ状態にな
る。

【００５７】この巡回読出し回路ＣＲＣに、最初に、Ｃ
Ｒ信号が“Ｈ”レベルとして入力されとする。このとき
取り込まれたビット線の状態が“Ｌ”レベルならば、Ｃ
Ｒ信号の変化はそのままナンド回路１８、インバータ２
０を通じて、ＣＲ’信号として出力される。取り込まれ
たビット線の状態が“Ｈ”レベルならば、ＣＲ信号が
“Ｈ”レベルの期間、ナンド回路２２、インバータ２４
を通じて、ＩＯＧ信号が“Ｈ”レベルとなり、さらにト
ランジスタ１４を通じてノードＮ１が“Ｈ”レベルにな
る。

【００５８】次に、ＣＲ信号が“Ｌ”レベルに変化する
と、取り込まれたビット線の“Ｈ”レベルの状態保持を
リセットしながら、ＩＯＧ信号を“Ｌ”レベルにする。
したがって、次にＣＲ信号が“Ｈ”レベルにパルス変化
しても、今度は、巡回読出し回路ＣＲＣはＣＲ’信号を
“Ｈ”レベルとして出力するのみである。

【００５９】この巡回読出し回路ＣＲＣは、セルアレイ
の行に沿って、図５のように直列接続されている。した
がって、「選択」、「選択’」、「選択”」で示されて
いる巡回読出し回路ＣＲＣのビット線が“Ｈ”レベルで
あり、この状態を取り込んだとする。この場合、１回目
のＣＲ信号パルスで「選択」のＩＯＧ信号が立ち、２回
目のＣＲ信号パルスで「選択’」のＩＯＧ信号が立ち、
３回目のＣＲ信号パルスで「選択”」のＩＯＧ信号が立
つことになる。

【００６０】以上のような動作の状況を図６のタイミン
グチャートに示す。図６（Ａ）はＣＲ信号、同図（Ｂ）
はＩＯＧＯＮ信号、同図（Ｃ）はノードＮ１の状態、同
図（Ｄ）はノードＮ１’の状態、同図（Ｅ）はノードＮ
１”の状態をそれぞれ示すものである。ちなみに、ノー
ドＮ１、ノードＮ１’、ノードＮ１”はそれぞれ異なる
巡回読出し回路ＣＲＣの同一のノードを表しており、ノ
ードＮ１は「選択」、ノードＮ１’は「選択’」、ノー
ドＮ１”は「選択”」に対応する。

【００６１】最初に、時刻ｔ１にて、ＩＯＧＯＮ信号を
“Ｈ”レベルパルスにして、ビット線レベルを巡回読出
し回路ＣＲＣに取り込むことについては先に説明したと
おりである。後は、ＣＲ信号を時刻ｔ２、時刻ｔ３、時
刻ｔ４と順次トグル動作させることにより、ノードＮ
１、ノードＮ１’、ノードＮ１”が順次“Ｈ”レベルと
なる。

【００６２】なお、図５の回路で、全ての巡回読出し回
路ＣＲＣでＩＯＧ信号が立った後、次にＣＲ信号パルス
を与えても立つべきＩＯＧ信号がない場合には、最後の
巡回読出し回路ＣＲＣからＣＲ信号に同期したＣＲＬ信
号が出力される。これによって、全ての該当するＩＯＧ
信号が選択され尽くしたことが判る。

【００６３】以上、巡回読出し回路ＣＲＣの動作の概略
を図５、６を用いて説明したが、この巡回読出し回路Ｃ
ＲＣの動作の詳細を図７、８を用いてより具体的に再度
説明する。

【００６４】図７に示した通り、巡回読出し回路ＣＲＣ
はインバータ６及び８のデータ保持状態に基づいて動作
が決定される。インバータ８の出力が“Ｈ”レベルの時
を“１”状態、ロウレベルの時を“０”状態と定義する
と、“１”状態のときには出力であるＣＲ' は“Ｌ”レ
ベルに固定され、別の出力であるＩＯＧは入力であるＣ
Ｒと同相の信号となり、“０”状態の時には出力である
ＣＲ' は入力であるＣＲと同相の信号となり、別の出力
であるＩＯＧは“Ｌ”レベルに固定される。これを図７
の（ａ）、（ｂ）に図式的に示した。

【００６５】図８は６個のカラムブロックからなるメモ
リセルアレイを仮定した場合の巡回読出し回路ＣＲＣの
動作説明図である。時刻ｔ1 において、ＩＯＧＯＮの
“Ｈ”パルスが全ての巡回読出し回路ＣＲＣに入力され
ることにより、上位カラムデータバス線のデータに転送
され、その結果、ＣＲＣ2 、ＣＲＣ4 、ＣＲＣ5 が
“１”状態となり、その他は“０”状態となる。すなわ
ち、巡回読出し回路の状態は、上から順に、０１０１１
０となる。この時、ＣＲと同相に駆動されるのはＣＲＣ
2 のＩＯＧのみであり、他は“Ｌ”レベルに固定され
る。続いて、時刻ｔ2 においてＣＲが“Ｌ”から“Ｈ”
に立ち上がるとＣＲＣ2 のＩＯＧが“Ｈ”レベルに立ち
上がり、この結果、二番目のカラムブロックのデータの
転送が行われる。続いて、時刻ｔ3 においてＣＲが立ち
下がると、ＣＲＣ2 の状態が“１”から“０”に遷移す
る。この結果、巡回読出し回路の状態は、上から順に、
０００１１０となる。この時、ＣＲと同相に駆動される
のはＣＲＣ4 のＩＯＧのみであり、他は“Ｌ”レベルに
固定される。続いて、時刻ｔ4 においてＣＲが“Ｌ”か
ら“Ｈ”に立ち上がるとＣＲＣ4 のＩＯＧが“Ｈ”レベ
ルに立ち上がり、この結果、四番目のカラムブロックの
データの転送が行われる。続いて、時刻ｔ5 においてＣ
Ｒが立ち下がると、ＣＲＣ4 の状態が“１”から“０”
に遷移する。この結果、巡回読出し回路の状態は、上か
ら順に、００００１０となる。この時、ＣＲと同相に駆
動されるのはＣＲＣ5 のＩＯＧのみであり、他は“Ｌ”
レベルに固定される。続いて、時刻ｔ6 においてＣＲが
“Ｌ”から“Ｈ”に立ち上がるとＣＲＣ5 のＩＯＧが
“Ｈ”レベルに立ち上がり、この結果、五番目のカラム
ブロックのデータの転送が行われる。続いて、時刻ｔ7
においてＣＲが立ち下がると、ＣＲＣ5 の状態が“１”
から“０”に遷移する。この結果、巡回読出し回路の状
態は、上から順に、００００００となる。続いて、時刻
ｔ8 においてＣＲが“Ｌ”から“Ｈ”に立ち上がると、
ＣＲＣ6 の出力であるＣＲ' が初めて“Ｈ”レベルに遷
移する。この結果、全ての（対応するキーストリングデ
ータが一致し、マークがなされた）データが転送された
ことが了承される。

【００６６】以上、図７、８を用いて説明したように、
マークされたカラムブロックのデータのみを読み出すこ
とができ、それ以外のカラムブロックのデータの読出動
作を行わないので、非常に高速なデータ転送が可能とな
る。例えば、２５６カラムブロックが存在するとして、
３個のカラムブロックにマークが付されているとした場
合、３回のデータ転送を行うのみであり、従来のように
２５６回のデータ転送を行う必要がない。全てのマーク
付けされたデータの出力が終了したことの検出は、最終
のカラムブロック内の巡回読出し回路の出力であるＣＲ
' を用いて行う。このＣＲ' は図１において制御回路１
０５を解して検索メモリ装置１００外部に出力される。
より詳細には、周辺回路装置である２００に転送され
る。

【００６７】図９は図３のビット比較器ＢＣＭとストリ
ングビットレジスタＳＢＲの具体例を示す回路図であ
る。

【００６８】図９に示すように、ストリングビットレジ
スタＳＢＲは、相互に逆並列接続されて自己保持系を構
成する２つのインバータと、ストリングビットＳＢｉが
入力されるＮチャンネルＭＯＳトランジスタ３０とを有
する。トランジスタ３０のゲートにはＳＴＲ信号が入力
される。また、インバータ２８からは保持されたストリ
ングビットＳＢｉ’が出力され、インバータ２６からは
保持されたストリングビット／ＳＢｉが出力され、いず
れもビット比較器ＢＣＭに与えられる。

【００６９】ビット比較器ＢＣＭにおいては、ストリン
グビットＳＢｉ’がＮチャンネルＭＯＳトランジスタ５
６とＰチャンネルＭＯＳトランジスタ４６のゲートにそ
れぞれ入力される。ストリングビット／ＳＢｉがＰチャ
ンネルＭＯＳトランジスタ５４とＮチャンネルＭＯＳト
ランジスタ４８のゲートそれぞれに入力される。トラン
ジスタ５４、４６、５６、４８の各ドレインは互いに共
通に接続され、／ＢＭＴＣｉ信号を出力する。ビット線
ＢｉはＮチャンネルＭＯＳトランジスタ３４のソースに
接続され、ビット線／ＢｉはＮチャンネルＭＯＳトラン
ジスタ３６のソースに接続される。トランジスタ３４、
３６のゲートにはＣＭＰＴＲ信号が接続される。トラン
ジスタ３４のドレインはＰチャンネルＭＯＳトランジス
タ５０のゲート、ＮチャンネルＭＯＳトランジスタ５２
のゲートに接続される。一方、トランジスタ３６のドレ
インはＰチャンネルＭＯＳトランジスタ４２のゲート、
ＮチャンネルＭＯＳトランジスタ４４のゲートに接続さ
れる。トランジスタ５０のドレインはトランジスタ５４
ソースに、トランジスタ４２のドレインはトランジス
タ４６のソースに、トランジスタ５２のドレインはトラ
ンジスタ５６のソースに、トランジスタ４４のドレイン
はトランジスタ４８のソースにそれぞれ接続される。ト
ランジスタ３４のドレインにはコンデンサ３８が、トラ
ンジスタ３６のドレインにもコンデンサ４０が接続さ
れ、コンデンサ３８、４０同士は相互接続される。トラ
ンジスタ４２、５０のソースは電源に接続され、トラン
ジスタ４４、５２のソースはＮチャンネルＭＯＳトラン
ジスタ５８のドレインに接続される。トランジスタ５８
のゲートにはＣＭＰ信号が与えられる。トランジスタ５
８のソースは接地される。

【００７０】ストリングビットレジスタＳＢＲはいわゆ
るラッチ回路であり、トランジスタ３０のゲートに入力
されるＳＴＲ信号が“Ｈ”レベルの期間にストリングビ
ット線ＳＢｉからデータを取り込み、インバータ２６、
２８によりこのデータを自己保持する。

【００７１】ストリングビットレジスタＳＢＲの出力Ｓ
Ｂｉ、／ＳＢｉと、セルから読み出されビット線に確定
したデータＢｉ、／Ｂｉとを比較するのが、ビット比較
器ＢＣＭである。ビット比較器ＢＣＭはビット線からデ
ータを取り込み、ビット線と切り離された後に比較動作
を行う。これは、比較の結果によって、データを書き換
えるべきマークされたカラム等があるため、ビット線デ
ータの変化が比較結果に干渉しないようにするためであ
る。

【００７２】ビット線データの取り込みはＣＭＰＴＲ信
号を“Ｈ”レベルにすることにより行われる。ビット線
データはトランジスタ３４、３６を通じて取り込まれ、
コンデンサ３８、４０に記憶保持される。ＣＭＰＴＲ信
号を“Ｌ”レベルにした後に、ＣＭＰ信号を“Ｈ”レベ
ルにすることにより、トランジスタ５８が導通する。そ
の結果、トランジスタ４２、４６、５０、５４、４４、
５２、４８、５６による比較動作が行われ、比較結果が
／ＢＭＴＣｉ信号として出力される。この／ＢＭＴＣｉ
信号出力は、一致の場合に“Ｌ”レベル、不一致の場合
に“Ｈ”レベルとして出力される。

【００７３】以上の、ビット比較器ＢＣＭからの比較結
果をまとめて、ストリングの一致、不一致を検出し、マ
ークビットを書き込むのがストリング合致マーク回路Ｓ
ＭＭである。図１０はこのストリング合致マーク回路Ｓ
ＭＭの詳細な構成を示す回路図である。

【００７４】図１０において、ＮチャンネルＭＯＳトラ
ンジスタ６２、６０のドレインは、ビット線Ｂ０、Ｂ８
に接続され、ソースは接地される。一方、Ｎチャンネル
ＭＯＳトランジスタ６８、７０のドレインはビット線／
Ｂ０、／Ｂ８に接続され、ソースは接地される。トラン
ジスタ６２のゲートにはＲＳ信号が与えられる。／ＭＫ
ＣＮＴ信号はＮチャンネルＭＯＳトランジスタ６４のゲ
ート、ＰチャンネルＭＯＳトランジスタ６６のゲートに
入力される。トランジスタ６６のソースにはＳＭＴＣ信
号が接続される。トランジスタ６４、６６のドレインは
トランジスタ６８のゲートに接続される。トランジスタ
６４のソースは接地される。一方、／ＲＳＭＫ信号はＰ
チャンネルＭＯＳトランジスタ７２のゲートとＮチャン
ネルＭＯＳトランジスタ７４のゲートに入力される。ト
ランジスタ７４のソースは接地され、ドレインはトラン
ジスタ６０のゲートとトランジスタ７２のソースに接続
される。／ＭＫＣＭＰ信号はＮチャンネルＭＯＳトラン
ジスタ７６のゲート、ＰチャンネルＭＯＳトランジスタ
７８のゲートに接続される。トランジスタ７６のソース
は接地され、そのドレインはトランジスタ７０のゲート
とトランジスタ７８のドレインに接続される。／ＢＭＴ
Ｃｉ信号（ｉ＝０〜７）は直列接続されるＰチャンネル
ＭＯＳトランジスタ８０、８１、８６、８７のゲートに
それぞれ入力される。トランジスタ８７のソースは電源
に接続される。一方、トランジスタ８０のドレインはト
ランジスタ７２のドレイン、トランジスタ７８のソース
に接続され、ＳＭＴＣ’信号として導出される。

【００７５】以上述べたような構成において、／ＢＭＴ
Ｃｉ信号がストリングを構成する８つのカラムのビット
比較器ＢＣＭからの比較結果である。ストリングが一致
した場合は、全ての／ＢＭＴＣｉ信号のレベルが“Ｌ”
レベルとなるので、ＳＭＴＣ’信号が“Ｈ”レベルとな
る。

【００７６】ＳＭＴＣ信号はこのストリング合致マーク
回路ＳＭＭが属するストリングに隣接するストリング合
致マーク回路ＳＭＭからの同様の出力である。

【００７７】先に説明したように、比較したストリング
自体にマークする場合には、／ＭＫＣＭＰ信号を“Ｌ”
レベルにする。こうすることによって、ＳＭＴＣ’信号
が“Ｈ”レベルならば／Ｂ０が“Ｌ”レベルとなり、比
較されたストリング自体の第０ビットに“１”が書き込
まれることになる。一方、内容検索ということで、比較
したストリングに属するストリングにマークする場合に
は、／ＭＫＣＮＴ信号を“Ｌ”レベルにする。ＳＭＴＣ
信号が“Ｈ”レベルであれば、比較したストリングの次
のストリングの第０ビットに“１”が書き込まれる。

【００７８】なお、ＲＳ信号を、全てのストリング合致
マーク回路ＳＭＭで共通に“Ｈ”レベルにすることによ
り、全てのストリングの第０ビットに“０”を書き込む
ことができる。これは、新たなキーストリングデータに
対して、一致検索を行う前にマークをリセットする意味
において必要な機能である。

【００７９】更に、ストリング合致マーク回路ＳＭＭに
は、ストリングが合致したものについてのみマークをリ
セットする回路が設けられる。／ＲＳＭＫ信号を“Ｌ”
レベルにすると、比較したストリングが一致してＳＭＴ
Ｃ’信号が“Ｈ”レベルであれば、比較したストリング
の第０ビットに“０”を書き込み、マークをリセットす
るものである。

【００８０】これは、ツリー構造のストリングデータを
順次検索して行って、最後のストリングデータのみにア
クセスする場合に有用である。また、ツリー構造におけ
る独立したデータのアクセス、例えばＡ→Ｂ→ＣとＢ→
Ｄのような構造において、ＢからＤを検索するような場
合に有用である。すなわち、Ａで検索して、その下のＢ
にマークし、次にマークなしのＢで検索してＤにマーク
し、更に、マークありのＢで検索してそのマークをリセ
ットしてアクセスすれば、マークがあるのはＤのみであ
るので、Ｄのみを読み出したり書き込んだりすることが
できる。

【００８１】更に、Ａ→Ａ→Ｂのようなデータ構造で
は、Ａをキーストリングデータとして検索した場合、２
番目のＡとＢにマークされるが、マークありのＡで検索
して、このマークをリセットし、この状態でアクセスす
ればＢのみにアクセスすることができる。

【００８２】続いて、本発明の第２の実施例に関わる検
索メモリ装置の回路構成を図１１〜図１４を用いて説明
する。図１、図２の概略構成は第２の実施例についても
当てはまるので説明を省略する。

【００８３】図１１に示すように、第２の実施例は第１
の実施例につき、巡回読出し回路ＣＲＣの構成、ストリ
ングビットレジスタＳＢＲの構成、ストリング合致マー
ク回路ＳＭＭの構成に対し、それぞれ変更を加え、若干
の制御信号線を追加したものである。

【００８４】巡回読出し回路ＣＲＣは下側に隣接するカ
ラムブロック内の上位カラムデータ線Ｂ８（すなわちＢ
０' ）と接続されており、さらに、ＰＲＥＳＴＲ信号が
入力されている。

【００８５】ストリングビットレジスタＳＢＲには、第
１の実施例においてＳＴＲが入力されていたのを、本実
施例においてはＳＴＲ１、ＳＴＲ２の２種の信号が入力
されている。

【００８６】ストリング合致マーク回路ＳＭＭには第１
の実施例に加えて、ＣＭＰ、ＲＳＭＫＫ、ＲＳＭＫＳ、
／ＭＫＮＸＴの４種の信号が入力され、ＲＳＭＫの信号
が削除されている。

【００８７】図１２は第２の実施例におけるストリング
合致マーク回路の回路構成図である。この回路は、以下
に説明する３つの機能を実現すべく、図１０の回路の一
部を改変したものである。

【００８８】（１）前にで述べた「キーストリングデー
タに属するデータ検索」の際に、隣接する８ビットのマ
ークをリセットできるように、トランジスタ６８のノー
ドＮ１に信号ＲＳＭＫＳを供給している（このノードＮ
１は、図１０では接地電位とされていたものであ
る。）。これによって、信号ＲＳＭＫＳが“０”ならば
マークビットに“１”が書き込まれ、（２−１）で述べ
たキーストリング自体のマーク、（２−２）で述べたキ
ーストリング自体のマークのリセット回路を簡略化する
ために、トランジスタ７０のノードＮ２へ信号ＲＳＭＫ
Ｋを供給した（このノードＮ２は、図１０では接地電位
とされていた。）。これにより、信号ＲＳＭＫＫが
“０”ならマークビットに“１”が書き込まれ、“１”
ならマークビットに“０”が書き込まれリセットされ
る。これによって、図１０のトランジスタ６０，７２，
７４は不要になり、信号／ＲＳＭＫを加える必要もなく
なる。

【００８９】さらに、マークビットが“１”のストリン
グの次のストリングのマークビットに、“０”または
“１”をセットするために、新たなトランジスタＴ１と
信号／ＭＫＮＸＴを設けた。このトランジスタＴ１は図
１０のトランジスタ８１〜８７をバイパスして、信号／
ＢＭＴＣ０と信号／ＭＫＮＸＴが“０”であれば信号Ｓ
ＭＴＣ′を“１”とする。すなわち、キーストリングの
内容に関わらず“１”をマークビットとしてもつストリ
ングか次のストリングにマークをセットできるようにす
る。この時セットできる内容は信号ＲＳＭＫＳ，ＲＳＭ
ＫＫのレベルによる。この機能を備えさせたことに基づ
いて、トランジスタ６２と信号ＲＳを省略することもで
きる。すなわち、で説明したマークのリセット動作の替
わりに、マークビット“１”で／ＭＫＮＸＴが“０”、
／ＭＫＣＭＰ“０”，ＲＳＭＫＫとＲＳＭＫＳが“１”
で検索すれば良い。このとき、／ＭＫＣＮＴが“１”な
らば、ＲＳＭＫＳは“０”でもよい。

【００９０】なお、新たな信号ＣＭＰによって制御され
る信号ＳＭＴＣ′が加えられる回路ＣＫＴ１は、信号ノ
ードＮ３が“０”フローティングになるのを防ぐための
“０”ラッチ回路である。信号ＣＭＰは、信号ＣＭＰＴ
Ｒのほぼ逆相信号として、“０”パルスとなるので、こ
の時ノードＮ３を“０”にリセット保持する。

【００９１】続いて、第２の実施例のストリングビット
レジスタの回路構成の詳細について述べる。

【００９２】図９の回路では、キーストリングの一致検
索をストリングを構成するビットの全てで行い、全てが
一致したとき一致が成立するようにしている。しかし、
実際の検索では、ストリングの一部のビットは無視した
検索をしたいこともある。このため、図１３では、ビッ
トレジスタの構成を修正することによって、部分的にビ
ットが一致した場合においても、一致が成立するように
した。

【００９３】図９においては、信号／ＳＢｉ′とＳＢ
ｉ′は、インバータ２６，２８によって構成されるひと
つのラッチ回路から生成されていた。これに対し、図１
３では、信号／ＳＢｉ′用とＳＢｉ′用の２つのラッチ
回路ＬＣＨ１，ＬＣＨ２を設けている。さらに、データ
線ＳＢｉからのデータ取り込み用のトランスファーゲー
トＴＧ１，ＴＧ２のコントロール信号もＳＴＲ１とＳＴ
Ｒ２と別々にした。読み出されたデータを無視する比較
ビットにおいては、／ＳＢｉ′とＳＢｉ′の何れもが
“１”であれば、Ｂｉ，／Ｂｉのデータに関係なく、／
ＢＴＣｉが“０”となる。つまり、そのビットでの一致
が成立したのと同じ結果になる。つまり、実質的にラッ
チデータを３値制御している。

【００９４】この機能があれば、ストリング合致マーク
回路の／ＭＫＮＸＴの信号の機能を代行できる。すなわ
ち、マークビット以外のビットを無視するようにストリ
ングビットレジスタを設定すれば良い。

【００９５】図１３（ｂ）にトランスファー信号ＳＴＲ
１とＳＴＲ２のタイミングと、ストリングビットデータ
の与え方を示す。右側には、ストリングビットレジスタ
の状態を示す。

【００９６】次に、巡回読み出し回路の変形例について
図１４を参照しつつ説明する。

【００９７】すでに説明したように、マークビットへの
書き込みは、キーストリング自体かその次のストリング
かであり、一方向的である。これは図１４の回路例にお
いても変わらない。巡回読出し回路によって読み出すこ
とができるストリングは、マークビットに“１”がセッ
トできるもののみである。このため、与えられたキース
トリングに一致したストリングより前方のストリングの
データを読出して内容を調べることはできない。これは
キーストリングより後方検索しかできないことを意味
し、キーストリングデータがどの様なデータ状況の中に
あるのかを調べるときに不便である。

【００９８】図４の回路では、ビット線データＢ０，Ｂ
８はトランスファーゲート４に直接接続されている。こ
れに対し、図１４の回路では、ビット線データ／Ｂ０は
ロジック回路ＬＣＫＴを経て接続される。すなわち、巡
回読出し回路は、その受け持ちのストリングのマークビ
ットに加えて、その次のストリングのマークビットのビ
ット線データＢ０′によっても、信号ＩＯＧを出力でき
るように設定できる。図中の信号／Ｂ０は受け持ちスト
リングのマークビットカラムのビット線データＢ０の相
補信号、Ｂ０′は受け持ちストリングの次のストリング
のマークビットカラムのビット線データを示す。信号Ｐ
ＲＥＳＴＲ（PRE CEDING STRING)が“１”であって、次
のストリングのマークビットが“１”であれば、受け持
ちストリングのマークビットが“０”であっても、巡回
読出し回路はＩＯＧ“１”を出力できるように設定され
る。したがって、巡回読出しを実施すると、マークされ
たストリングのひとつ前のストリングも読み出され、前
方のストリングデータの検索が可能となる。

【００９９】以下に、本発明の第２の実施例の回路構成
を用いたデータ検索の例のいくつかを説明する。 （ｉ）ランダムパケットデータの並び替え この例の１具体例を表１に示す。

【０１００】

【表１】 表１からわかるように、非同期データ転送（ＡＴＭ）で
読み込んだデータを、ヘッダーをキーストリングとして
与え、巡回読出しすることによって復元できる。

【０１０１】より詳しくは、表１からわかるように、各
データパケットは、固定長で、ヘッダーとデータ部で構
成され、ヘッダーにぶら下がったデータパケットがラン
ダムに並んでいる。ここには、１ストリングのヘッダー
と１ストリングのデータとでデータパケットが構成され
ている例を示した。ストリング合致マーク回路へ入力す
る信号が、次の状態のときに一致検索をして、巡回読出
しを行う。

【０１０２】 ／ＭＫＣＭＰ “１” ／ＭＫＣＮＴ “０” ／ＭＫＮＸＴ “１” ＲＳＭＫＫ “０”又は“１” ＲＳＭＫＳ “０” ヘッダーやデータが多くのストリングで構成される場合
には、このあとで述べる応用例を組み合わせて検索方法
を作ることができる。 （ii）階層分類データの検索 この例の１具体例を表２に示す。

【０１０３】

【表２】 表２からわかるように、階層的に分類された状態にデー
タが存在する場合には、階層的な分類項目は、前述の
（ｉ）のヘッダーを構成すると見なすことができる。こ
の例では、分類項目データａ1 ｂ2 ｃ2 の下にぶら下が
っているデータを検索する場合を説明する。各データの
上のドットは、そのストリングにマークが設定されてい
ることを示す。検索によってマークを付けた後、それら
のマークのうちの不用なマークを消して目的のデータの
みが巡回読出しされるようにする。キーの後の（Ｒ）
は、一致したストリングの次のストリングのマークをリ
セットする検索を示す。それぞれのキーでの検索のスト
リング合致マーク回路の状態設定を以下に示す。

【０１０４】

【表３】 （iii)先頭キーの重複の無いキーストリングをもつデー
タの検索 この例の１具体例を表４に示す。

【０１０５】

【表４】 表４からわかるように、この応用例は、固定長でないデ
ータの検索を示す。先頭キーがキーストリングに重複し
ていないとは、検索すべき一連のキーデータの中にＡが
存在しないと言うことを意味し、Ａ以外の他のキーは重
複していてもかまわない。先頭キーＡから始まって線で
結んだ様な各種の検索パスが存在するが、ここではこれ
らのパスにぶら下がったデータの内のＴを読み出す場合
を示す。

【０１０６】一般的なキー手順も示してあるが先頭キー
ＩＮはＫ１からＫｎまでのキー列に含まれてはならな
い。マーク付きキーで検索して、キーデータストリング
に付いているマークを前のキーで消すという検索動作を
続ける。先頭キーのみはマークなしのキーで検索するの
で、先頭キーがつながるストリング列のキーＡの次のキ
ーの全てにマークが付くことになる。このマークを消す
ために、マーク付きの先頭キーＡドットで自分自信のマ
ークを消す（ＳＲ）の検索を行う。

【０１０７】この検索では、始めからキーストリング列
が与えられていても、キーストリングを一つずつ検索し
て読出しをしながら選択して、キーストリングを辿って
行っても良い。後の検索の場合は、キー候補の中から一
つ一つデータを選択して、分岐をしながら進んである一
つの枝に入って行くという検索である。

【０１０８】キー手順でＩＮ（ＳＲ）のような自分のマ
ークを消す場合のストリング合致マーク回路の状態設定
を以下に示す。

【０１０９】 ／ＭＫＣＭＰ “０” ／ＭＫＣＮＴ “１” ／ＭＫＮＸＴ “１” ＲＳＭＫＫ “１” ＲＳＭＫＳ “０”又は“１” 他の検索の場合の状態設定は以前の応用例で示されてい
るとおりである。 （iv）ストリングデータの順次読出し この例の１具体例を表５に示す。

【０１１０】

【表５】 これは、読み出したデータ自体を伴って、順次、次のデ
ータを読み出す方法である。巡回読出ししたデータのマ
ークビットとＥｎｄを無視すればストリングデータが得
られる。先頭のＸ１にしかＨｅａｄｉｎｇをつけないた
め、各ＸｉにＨｅａｄｉｎｇを付ける場合よりも、メモ
リを節約することができるが、読出しに手間がかかる。
ここで説明した応用例は、前に（iii)で説明した応用例
において、先頭キーの後のキーではデータの分岐がな
く、データが先頭キーのもとに孤立している場合にあた
り、先頭キーがＨｅａｄｉｎｇに相当する。ここで説明
した例によれば、キーのマークを消去する必要はなく、
ＨｅａｄｉｎｇからＥｎｄまでのデータを巡回読出しで
読み出せる。マークを消す必要がない分検索時間が節約
できる。 （ｖ）前方読出しと検索 この例の１具体例を表６に示す。

【０１１１】

【表６】 表６からわかるように、この応用例では、キーデータと
一致したストリングと次のストリングにマークし、巡回
読出し回路にマークビットをセットする際に、一つ手前
のストリングの読出し回路にもマークビットをセットす
ることによって前方読出しを行う。キーデータと一致し
た自分自信のストリングと次のストリングにマークする
操作である、検索Ｘ＆Ｋｅｙ Ｍａｒｋでのストリング
合致マーク回路の状態設定は、以下に示すとおりであ
る。

【０１１２】 ／ＭＫＣＭＰ “０” ／ＭＫＣＮＴ “０” ／ＭＫＮＸＴ “１” ＲＳＭＫＫ “０” ＲＳＭＫＳ “０” 更に巡回読出し回路の状態設定としては、ＰＲＥＳＴＲ
を“１”に設定して、読み出せばストリングデータｃを
読み出すことができる。これをまたキーとして用いて遡
ることにより、前方にデータを辿ることができる。 （vi）ふるい分け検索 この例の１具体例を表７に示す。

【０１１３】

【表７】 この検索によれば、キーストリングのビットにいろいろ
な属性を持たせることによって、条件に合うデータの検
索ができる。

【０１１４】また、データが複数のストリングにわたっ
て連続する長いデータであるときには、ＭＫＮＸＴによ
って、マークのあるストリングの次のストリングにもマ
ークする。

【０１１５】この応用例は今までの応用例の全てに適用
できる。すなわち、１つは、ストリングを構成する全て
のビットではなく、一部のビットのみと一致検索をした
いときであり、もう１つでは、データが複数のストリン
グに連続してまたがって存在するときに、マークのある
ストリングの次のストリングにマークしたいときであ
る。

【０１１６】この例では、×のビットが無視されるが、
このビットはストリングビットレジスタ回路を対応する
状態に設定すれば良い。

【０１１７】データを構成する複数のストリングのうち
のマークのあるストリングの次のストリングにマークを
付ける検索では、マークビットを“１”とし、ストリン
グ合致マーク回路の状態を以下のようにして検索する。

【０１１８】 ／ＭＫＣＭＰ “１” ／ＭＫＣＮＴ “０” ／ＭＫＮＸＴ “０” ＲＳＭＫＫ “０”又は“１” ＲＳＭＫＳ “０” ただし、本件マーク付けの機能は、マークビット以外を
無視するストリングビットレジスタ回路の設定によって
同様の結果を得られる。

【０１１９】マークビット以外を無視できる検索は、様
々なマークリセット機能の替わりをすることができる。
例えば前に説明したＲＳ信号の機能は、マークビット以
外を無視したストリングビットレジスタ回路を、マーク
ビットのみは“１”とし、一致ストリングのマークリセ
ットをするためにストリング合致マーク回路を以下のＩ
又はIIのように状態設定することによって行える。

【０１２０】 Ｉ II ／ＭＫＣＭＰ “０” “０” ／ＭＫＣＮＴ “１” “１” ／ＭＫＮＸＴ “０” “１” ＲＳＭＫＫ “１” “１” ＲＳＭＫＳ “０”又は“１” “０”又は“１” また、応用例の（II），（III)の（Ｒ）の付いたマーク
リセットの検索動作において、具体的なキーストリング
を与える替わりに、マークビット以外を無視したストリ
ングビットレジスタ回路の設定で、マークビットのみは
“０”と設定し、マークをリセットする検索を行っても
良い。

【０１２１】以上に（ｉ）〜（vi）で説明したように、
マークビットの様々な操作と、マークされたストリング
の巡回読出し回路によって、従来のメモリには出来ない
情報内容に即したデータアクセスができ、将来の情報処
理システムであるＩＯＳ（Information Oriented Syste
m)を構成するに必要なメモリを提供できる つまり、上述の各応用例によれば、例えばキーに一致し
たストリングとその次にストリングに対してマーク状態
を任意に設定でき、巡回読出し回路にマークストリング
の手前のストリングに対しても読み出すことができ、さ
らに、マークの有無によってのみでストリングのマーク
を自由に設定できる検索機能を実現できる。

【０１２２】続いて、本発明の第３の実施例を図１５に
示す。全体回路構成は図１と同様のため、省略する。

【０１２３】図１５に第３の実施例に対応する変形され
た検索データ転送回路１０２' の回路構成を示す。検索
データ転送回路は、前述したように、各カラムブロック
ＣＢに属するカラム検索単位から構成される。また、各
カラム検索単位乃至各カラムブロックは８ビットのデー
タバス兼ストリングデータバスＩＯＳＢ（図１における
データバス１０６及びストリングデータバス１０７の延
長したもの、図示しないマルチプレクサ回路が挿入され
ている）と接続されている。さらに、第３の実施例の検
索データ転送回路１０２' は８ビットのデータレジスタ
４００がデータバス兼ストリングデータバスＩＯＳＢに
接続されている。

【０１２４】各カラムブロックＣＢはメモリセルと接続
された８ビットの各カラムデータ線束３０３を含み、こ
のカラムデータ線束３０３は１ビットの上位カラムデー
タ線３０３1 と７ビットの下位カラムデータ線束３０３
2 から構成される。各カラムブロックＣＢはさらに、カ
ラムゲート回路３０１、巡回読出し回路ＣＲＣ、ストリ
ングビットレジスタＳＢＲ、ビット比較・マーク回路３
０２から構成される。

【０１２５】カラムゲート回路３０１はデータバス兼ス
トリングデータバスＩＯＳＢとカラムデータ線束とを接
続する。

【０１２６】巡回読出し回路は１ビットの上位カラムデ
ータ線のデータ及び上側に隣接するカラムブロックより
供給される信号ＣＲに基づいてカラムゲート回路３０１
を制御する。

【０１２７】ストリングビットレジスタＳＢＲは８ビッ
トのレジスタ列から構成され、データバス兼ストリング
データバスＳＢのデータを取り込み、これを一時的に保
持する。

【０１２８】ビット比較・マーク回路３０２はカラムデ
ータ線束３０３の８ビットのデータとストリングビット
レジスタＳＢＲに保持されている８ビットのストリング
データとを比較し、比較結果をカラムデータ線束３０３
に書き戻す。この書き戻し手法は種々の方法があるが、
代表的なものとして、一致した場合には“Ｈ”データを
次の（図２において下側に隣接したカラムブロック内
の）上位カラムデータ線３０３1' に書き込む場合、一
致した場合には“Ｈ”データを自分自身の（カラム検索
単位が属するカラムブロックの）カラムデータ線３０３
1 に書き込む場合等がある。このビット比較・マーク回
路３０２は後述するように、ビット比較器ＢＣＭ及びス
トリング合致マーク回路ＳＭＭから構成される。

【０１２９】データレジスタ４００は、一回目に検索さ
れたデータを、引き続いて行う二回目の検索において、
ストリングデータとして用いる際に、それまで検索され
たデータを保持しておくのに用いる。

【０１３０】以上の様に構成することにより、第１・第
２の実施例においてはデータバス及びストリングデータ
バスの２本のバスが必要であったのを１本のデータバス
に兼用することが可能となり、チップ面積の削減に寄与
する。さらに、データレジスタ４００の存在により、上
述した「ストリングデータの順次読出し」において読み
だしたデータをキーストリングとして戻す際にチップ外
部にデータを出力すること無く順次検索を行うことがで
きる。この結果、検索速度の向上にも寄与する。

【０１３１】以上のように、内容検索においては、行す
なわちワード線をランダムではなく、順次全て活性化す
ることが重要となる。そこで、従来のＤＲＡＭよりも更
に適したセル構造が存在する。

【０１３２】検索およびアクセス動作には、ランダムア
クセス性よりもリフレッシュの必要回数を増やすことな
く、セル密度を上げることが重要である。このような構
造に適しているのが、いわゆるカスケードタイプのダイ
ナミックセル構造である。このタイプのセル構造につい
ては、文献“ＩＥＥＥ ＪＯＵＲＮＡＬ ＯＦ ＳＯＬＩＤ−ＳＴＡＴＥ ＣＩＲＣＵＩＴＳ（Ｎｏｖ．
１９９１．Ｖｏｌ．２６．Ｎｏ．１１．ｐｐ１５１１−
１５１８）”に一例が示されている。

【０１３３】続いて、この様なカスケードタイプのセル
からなるメモリセルアレイを有する検索メモリ装置を第
４の実施例として、図１６〜図１７を参照して説明す
る。

【０１３４】図１６はカスケードタイプのセル構造の概
略構成図である。

【０１３５】この構造が、一般的なＤＲＡＭの構造と異
なる点は、カスケードセルアレイＣＣＡ中のセルＣが直
列に、ワード線ＷＬで隔てられた状態にカスケード接続
されている点にある。したがって、セルＣからのデータ
の読み出しは、ビット線ＢＬに一番近いセルＣから順番
に奥のセルＣに向かって行われ、書き込みは読み出しと
逆の順序で行われる。

【０１３６】カスケード接続されたセルのうちの奥のセ
ルのデータを読み出している時には、それより手前のセ
ルがデータの転送路となる。このため、転送路となる手
前のセル中のデータをどこかに保持しておかなければ、
データが消えてしまう。この保持を行うのが、リストア
用のレジスタである。カスケードセルの内容は、ここに
一時蓄えられ、ワード線を閉じる時に、奥のセルから順
番に書き戻される。

【０１３７】図１６では、４本のビット線ＢＬが共通ビ
ット線Ｂｉに共通に接続され、これらのビット線ＢＬに
つながるセル中のデータは共通のセンス増幅器ＳＡによ
りセンスされる。図１６には示していないが、やはり共
通ビット線／Ｂｉにも４本のビット線／ＢＬが接続され
ている。選択転送ゲートＳＴＧはこれらの４本のビット
線ＢＬの内のどれを選択するかを決めるものである。

【０１３８】選択転送ゲートＳＴＧもワード線とみなせ
ば、図１６では１６行毎にアクセスの順番はシリアルに
決まっている。すなわち、カスケードセルの一番上のワ
ード線ＷＬを開き、選択転送ゲートＳＴＧを順番に開い
てセンスし、リストア用のレジスタＲＲにデータを格納
する。続いて、２番目のワード線ＷＬを開いて、また順
番に選択転送ゲートＳＴＧを開き、センスしてデータを
レジスタＲＲに格納するという動作を一番奥のセルに向
かって行う。リストア用レジスタＲＲからセルＣへの書
き込みがこの逆の順序で行われ、一連の読み出し、また
は書き込み、またはリフレッシュの動作を完了する。

【０１３９】以上の動作の順番は、あるカスケードセル
を選択すれば決まってしまう。ランダムアクセスが必要
な一般的なＤＲＡＭとしては、このような行のアクセス
に関する制限はメモりの機能を大きく限定するが、内容
参照メモリにおいては、全ての行に対してアクセスする
ことが基本となるので、この制限が問題になることはな
い。

【０１４０】つまり、本発明の実施例のメモリ装置にお
いて、図１、図２、図３に示した第１の実施例の構成に
対して、図１６のような構成のメモリセルを接続するこ
とにより、セルの密度を、通常のＤＲＡＭのセルに比べ
て、少なくとも数１０パーセント向上することができ
る。つまり、大容量に適した構成とすることができる。

【０１４１】図１７はカスケードセルを用いた場合のセ
ンスアレイの行スキャンの説明図である。図にも示すよ
うに、セルアレイＣＡにおいて、アクセス順の決まった
まとまりの行における先頭行の設定は任意にできるが、
まとまり内では、カスケードセルのアクセス方式の制限
からシリアルなアクセスしかできない。このことは先に
も説明した通りである。図１７中、ＳＬは任意設定可能
先頭スキャン行を示す。

【０１４２】なお、本実施例では、Ｄタイプ（ダイナミ
ック型）のメモリセルを用い、１つのセンスアンプに属
する１群のビットラインをストリングデータを構成する
カラムとしてきたが、メモリセルはＤタイプである必要
はなく、リフレッシュ動作の必要のないメモリセルに対
しても上記と同様のアクセスを行わせることができる。

【０１４３】図１８は本発明のメモリ装置におけるメモ
リアクセス方式を従来のアクセスと比較して示す説明図
である。

【０１４４】今、ある行に注目した場合、この中に、あ
るキーストリングに属する第１、第２データセット１、
２があるものとする。この場合、従来のアクセスＣＡＣ
では、セルアレイＣＡ中の全てのセルをとにかく読み出
して、キーストリングを探さなければならない。これに
対して、本発明の実施例の方式では、データセットにリ
フレッシュ時にマークが付けられ、データセットのみが
巡回的にアクセスされる。このため、データセットのな
いことの確認も含めて、この場合３回のアクセスサイク
ルを必要とするのみである。つまり、読み出し行ＲＬに
着目し、内容参照アクセスＣＲＡ、第１データセットア
クセスＤＳＡ１、データセットアクセスＤＳＡ２と３回
アクセスすればよい。このように、検索型のアクセスに
おいては、本発明の実施例の方式によれば、大幅に効率
を上げることができる。

【０１４５】以上述べたように、本発明の実施例のメモ
リ装置によれば、内容参照型のメモリにおいて、キース
トリングデータとデータセットを合わせて書き込み、ス
トリング検索結果に応じてマークを付して、これに基づ
きアクセスするようにし、更に、検索のデータ構造がツ
リー構造になっていても、検索とマークの付け方で必要
な枝の先のデータのみにアクセスできるように構成した
ので、内容検索の効率を大幅に向上できると共に、構造
的にカスケードセルの適用を可能にしたので、セル密度
を向上して大容量化に適した構造を実現することができ
る。

【０１４６】続いて、第５の実施例を図１９を参照して
説明する。第１〜第４の実施例は検索メモリ装置を例に
取り、本発明を説明してきたが、本発明は、検索メモリ
装置に限られるわけではなく、むしろ、検索データ転送
装置として応用することができる。例えば、データ通信
において、受信したパケットデータを復号化する際に用
いられる。パケットデータ通信においては、複数の異な
った種類のデータ群が一つのパケットに混載している。
したがって、パケットデータの受信においては、これら
複数のデータ群に分解する必要がある。それぞれのデー
タ群にキーストリングを対応させて、データ列の先頭に
付しておけば、本発明の検索データ転送装置によって、
パケットデータの分解乃至復号化を行うことができる。

【０１４７】図１９はこのパケットデータの複合化に用
いるデータ受信器の構成を示す。データ受信機５００は
レジスタアレイ５０１、検索データ転送回路５０２、デ
ータ受信回路５０４及び制御回路５０５から構成され
る。また、レジスタアレイ５０１及び検索データ転送回
路５０２は複数のカラムブロックＣＢに分割されてお
り、このカラムブロック毎にデータ転送が行われる。さ
らに、検索データ転送回路５０２とデータ受信回路５０
４とはデータバス５０６により接続されている。レジス
タアレイ５０１は、フリップフロップ回路を列状に配置
して構成する。

【０１４８】検索データ転送回路５０２は外部から入力
された若しくは前サイクルにより得られたストリングデ
ータを基に各カラムブロック毎に読出データの比較を行
い、比較結果を記憶しておき、この記憶された比較結果
に基づいてデータ転送を行う。このデータ転送は制御回
路５０５より与えられるクロック信号に基づいて、順次
行われる。このデータ転送は全てのカラムブロックのデ
ータにつき行われるのではなく、上記比較結果に基づい
て、部分的に行われる。前述したように、この検索デー
タ転送回路５０２が比較結果に基づいて部分的にデータ
転送を行うことが検索速度の向上に寄与するのである。

【０１４９】制御回路５０５はレジスタアレイ５０１の
動作の制御、検索データ転送回路５０２の各種動作の制
御、データ受信回路５０４の動作制御等を行う。

【０１５０】さらに、このデータ受信機５００はレジス
タファイル６０１、ストリンデータレジスタ６０２を含
む。レジスタファイル６０１は検索データ転送回路５０
２により順次転送された検索データを順次記憶する。ス
トリングデータレジスタ６０２は検索データ転送回路６
０２に与えるストリングデータを保持する。ストリング
データレジスタ６０２は検索データ転送回路５０２とス
トリングデータバスによって接続されている。検索デー
タ転送回路５０２はセンスアンプＳＡ及びイコライズ回
路ＥＱを除く図１１における検索データ転送回路と同様
の回路が用いられているので説明を省略する。ビット線
対にはデータレジスタとしてのフリップフロップが接続
されている続いて、図１１を用いてこのデータ受信機の
動作を説明する。

【０１５１】まず、レジスタアレイに対するデータの入
力動作について説明する。

【０１５２】レジスタアレイへのデータの入力において
は、レジスタとビット線線をつないでおき、ＩＯ線対Ｉ
Ｏ０〜ＩＯ７、／ＩＯ０〜／ＩＯ７をビット線対Ｂ０〜
Ｂ７、／Ｂ０〜／Ｂ７に接続することにより行われる。

【０１５３】入力は、８ビットずつシリアルに行われ
る。ＳＡＣ信号をパルス状に“Ｈ”レベルとして巡回読
出し回路ＣＲＣを全て選択状態にする。その後に、ＣＲ
信号をパルス的に与えると、ＣＲ信号が“Ｈ”レベルの
期間、ＩＯＧ信号が“Ｈ”レベルとなり、Ｉ／Ｏ線ペア
とビット線がつながる。つまり、ＣＲ信号のパルス毎に
巡回読出し回路ＣＲＣが順番に選択されて、８カラムず
つが順番にＩ／Ｏ線につながる。この状態において、Ｉ
／Ｏ線ペアに適宜データを与えることにより、レジスタ
アレイにパケットデータを入力することができる。

【０１５４】次に、パケットデータの復号化について説
明する。

【０１５５】先ず、ＳＴＲ信号を“Ｈ”レベルにして、
ストリングビット０〜７に対応するストリングビットレ
ジスタＳＢＲを開き、この状態でストリングビットデー
タ線ＳＢ０〜ＳＢ７に検索するキーストリングデータ、
すなわちデータ群の先頭データを与える。その結果、ス
トリングビットレジスタＳＢＲにキーストリングデータ
が書き込まれる。ストリングビットレジスタＳＢＲは８
ビット単位で構成されているが、この場合、８ビット分
の全てのストリングビットレジスタＳＢＲに同じキース
トリングデータが書き込まれる。続いて、ＣＭＰＴＲ信
号をパルス状に“Ｈ”レベルにすることにより、ビット
比較器にレジスタアレイのデータを取り込む。次に、Ｃ
ＭＰ信号を“Ｈ”レベルにすることによって、カラムの
ビット線に確定したデータとストリングビットレジスタ
ＳＢＲに書き込まれた各ビットのデータの比較が行われ
る。比較したビットのデータが一致した場合は、ビット
比較器ＢＣＭから出ている／ＢＭＴＣｉ信号が“Ｌ”レ
ベルに変化する。８ビットのストリングビットの全てが
一致すると、ストリング合致マーク回路ＳＭＭからのＳ
ＭＴＣ信号が“Ｈ”レベルとなる。なお、この信号はＳ
ＭＴＣ’信号として、次のストリング合致マーク回路Ｓ
ＭＭに供給される。

【０１５６】検索の結果、キーストリングに一致するデ
ータが見つかった場合、一致したキーストリングデータ
に隣接する８ビットが、それに属するデータであること
がわかる。この場合、このデータセットにマークを付け
る必要がある。図に示されている始めの８ビット（０〜
７）が一致したキーストリングデータとすると、ＳＭＴ
Ｃ’信号は“Ｈ”レベルとなり、図３のＢ８と／Ｂ８の
カラムのストリング合致マーク回路ＳＭＭに与えられ
る。ここで／ＭＫＣＮＴ信号を“Ｌ”レベルにすると、
Ｂ８／Ｂ８のカラムに“１”が書き込まれることにな
る。このような、“１”の書き込みは、選択活性化され
ている行の全ての一致ストリングの属するカラムブロッ
クで同時に行われる。

【０１５７】以上のような動作を、同時に行うことがで
きる。また、検索されて選ばれたストリングは、その第
０ビットが“１”となってマークされるか、または、
“０”にリセットされる。

【０１５８】アクセスは第０ビットが“１”にマークさ
れたストリングに対して行われる。マークされたストリ
ングは多数あり、選択された１つの行のなかにも複数の
マークされたストリングが存在し得る。

【０１５９】これらに対しては、巡回的にアクセスす
る。つまり、ある行にマークされたストリングが存在す
るかどうかは、アクセス時には不明であるが、各カラム
のうちで、ストリングの第０ビットを巡回読出し回路Ｃ
ＲＣに取り込むために、ＩＯＧＯＮ信号を“Ｈ”レベル
にパルス状に変化させる。その後、ＩＯＧＯＮ信号を
“Ｌ”レベルにし、ＣＲ信号をトグルする。その結果、
ＣＲ信号が“Ｈ”レベルの期間、選択された行内で、先
ず最初のマークされたストリングの８ビットがＩ／Ｏ線
に接続される。

【０１６０】更に、ＣＲ信号のトグルを続けると、順番
にマークされたストリングに対するアクセスができ、そ
のストリングに対するデータの読み出しを行うことがで
きる。

【０１６１】選択された行にマークされたストリングが
存在しない場合や最後のマークされたストリングがアク
セスされた後に、ＣＲ信号が“Ｈ”レベルになると、Ｃ
ＲＬ信号が“Ｈ”レベルとなる。これで、この行には、
アクセスすべきストリングが存在しないことが判る。

【０１６２】以上説明したように、巡回読出し回路を用
いて連続的に読み出されたデータがレジスタファイル６
０１に格納され、これが所定キーストリングに対応する
データ群である。つまり、復号化がなされたのである。

【０１６３】このように、本発明の回路構成を用いる
と、非常に簡単にかつ高速にパケットデータの復号化を
行うことができる。

【０１６４】以上、本発明を第１から第５の実施例を参
照して説明したが、本発明は上記実施例に限定されるも
のではなく、発明の主旨を逸脱しない限り種々の応用例
・変形例が可能であることは言うまでもない。

【０１６５】

【発明の効果】本発明の検索メモリ装置によれば、外部
から加える外部データストリングによってセルデータス
トリングに特定のデータを書き込み、書き込んだセルデ
ータストリングのみを読み出し対象とすることができ、
さらに本発明のデータ転送装置によれば、外部から加え
るくり返しパルス状の駆動信号によって予め特定のデー
タが書き込まれたセルデータストリングをデータ転送対
象とすることができる。

【図面の簡単な説明】

【図１】本発明の第１の実施例に係る検索メモリ装置及
びその周辺回路のブロック図である。

【図２】本発明の第１の実施例に係る検索データ転送装
置のブロック図である。

【図３】図２の主要部の詳細を示した回路図である。

【図４】図３の巡回読出し回路の詳細を示す回路図であ
る。

【図５】巡回読出し回路の相互接続の説明図である。

【図６】巡回読出し回路の動作を説明するためのタイミ
ングチャートである。

【図７】巡回読出し回路の動作を説明するための説明図
である。

【図８】巡回読出し回路の動作を説明するための説明図
である。

【図９】ストリングビットレジスタとビット比較器の詳
細を示す回路図である。

【図１０】ストリング合致マーク回路の詳細を示す回路
図である。

【図１１】本発明の第２の実施例を示した回路図であ
る。

【図１２】本発明の第２の実施例に係るストリング合致
マーク回路の詳細を示す回路図である。

【図１３】本発明の第２の実施例に係るストリングビッ
トレジスタとビット比較器の詳細を示す回路図およびそ
の動作を示すタイミングチャートである。

【図１４】本発明の第２の実施例に係る巡回読出し回路
の詳細を示す回路図である。

【図１５】本発明の第３の実施例に係る検索データ転送
装置のブロック図である。

【図１６】本発明の第４の実施例に用いるカスケードタ
イプのセル構造の説明図である。

【図１７】カスケードセルを用いた場合の行スキャンの
説明図である。

【図１８】本発明によるメモリアクセス方式の説明図で
ある。

【図１９】本発明の第５の実施例に係るパケットデータ
受信機のブロック図である。

【図２０】一般的なメモリアクセスの説明図である。

【図２１】内容参照アクセスの説明図である。

【符号の説明】

ＣＲＣ 巡回読出し回路 ＳＢＲ ストリングビットレジスタ ＢＣＭ ビット比較器 ＳＭＭ ストリング合致マーク回路 ＳＡ センス増幅器 ＥＱ イコライザ

Claims (25)

【特許請求の範囲】
1. 【請求項１】ほぼ行列状に配列された複数のメモリセル
   から構成され、複数のカラムブロックに分割されたメモ
   リセルアレイと、 外部から入力されたストリングデータと各カラムブロッ
   ク内のデータとを比較し、この比較結果に応じてカラム
   ブロックのいくつかにマークを付し、このマークが付さ
   れたカラムブロック内のデータを順次転送出力する検索
   データ転送手段とから構成される検索メモリ装置。
2. 【請求項２】請求項１記載の検索メモリにおいて、前記
   検索データ転送手段は各カラムブロック内のデータの所
   定ビットをマークとして用いることを特徴とする検索メ
   モリ装置。
3. 【請求項３】請求項１記載の検索メモリにおいて、前記
   複数のカラムブロックは順序付けされており、前記検索
   データ転送手段は、前記比較結果に応じ、ストリングデ
   ータと各カラムブロック内のデータとが一致したカラム
   ブロックの次のカラムブロックに対しマークを付するこ
   とを特徴とする検索メモリ装置。
4. 【請求項４】請求項１記載の検索メモリにおいて、前記
   複数のカラムブロックは順序づけされており、前記検索
   データ転送手段は、前記比較結果に応じ、ストリングデ
   ータと各カラムブロック内のデータとが一致したカラム
   ブロックに対しマークを付することを特徴とする検索メ
   モリ装置。
5. 【請求項５】請求項１記載の検索メモリにおいて、前記
   複数のカラムブロックは順序づけされており、前記検索
   データ転送手段は、第１の信号を受けることにより、マ
   ークを付されたカラムブロックの直前のカラムブロック
   内のデータを転送出力することを特徴とする検索メモリ
   装置。
6. 【請求項６】請求項１記載の検索メモリにおいて、前記
   複数のカラムブロックは順序付けされており、前記検索
   データ転送手段は、前記比較結果に応じ、第２の信号を
   受けることにより、ストリングデータと各カラムブロッ
   ク内のデータとが一致したカラムブロックの次のカラム
   ブロックに対しマークを付すると共に、第３の信号を受
   けることにより、ストリングデータと各カラムブロック
   内のデータとが一致したカラムブロックの次のカラムブ
   ロックのマークを消去することを特徴とする検索メモリ
   装置。
7. 【請求項７】請求項１記載の検索メモリにおいて、前記
   複数のカラムブロックは順序付けされており、前記検索
   データ転送手段は、前記比較結果に応じ、第２の信号を
   受けることにより、ストリングデータと各カラムブロッ
   ク内のデータとが一致したカラムブロックの次のカラム
   ブロックに対しマークを付すると共に、第４の信号を受
   けることにより、ストリングデータと各カラムブロック
   内のデータとが一致したカラムブロックのマークを消去
   することを特徴とする検索メモリ装置。
8. 【請求項８】請求項１記載の検索メモリにおいて、前記
   複数のカラムブロックは順序付けされており、前記検索
   データ転送手段は前記複数のカラムブロックに対応して
   複数のカラム検索単位に分割されており、前記検索デー
   タ転送手段はこれら複数のカラム検索単位にわたって延
   在するデータバスを具備し、各カラムブロックは読み出
   されたデータを転送するカラムデータ線束を具備し、こ
   のカラムデータ線束は所定カラムデータ線とそれ以外の
   カラムデータ線から構成され、各カラム検索単位は前記
   カラムデータ線束と前記データバスとを選択的に接続す
   るカラムゲート及び前記所定カラムデータ線のデータに
   応じてこのカラムゲートを制御する巡回読出し回路を具
   備することを特徴とする検索メモリ。
9. 【請求項９】請求項８記載の検索メモリにおいて、巡回
   読出し回路は前記所定カラムデータ線のデータが第１の
   レベルであるときには当該巡回読出し回路が属するカラ
   ムブロックの直前のカラムブロック内の巡回読出し回路
   から与えられる信号に応じて前記カラムゲートを接続制
   御すると共に直後のカラムブロック内の巡回読出し回路
   へ所定レベルの信号を与え、前記所定カラムデータ線の
   データが第２のレベルであるときには当該巡回読出し回
   路の属するカラムブロックの直後のカラムブロック内の
   巡回読出し回路へ直前のカラムブロック内の巡回読出し
   回路から与えられた信号を与えると共にカラムゲートを
   開放制御することを特徴とする検索メモリ。
10. 【請求項１０】請求項１記載の検索メモリにおいて、前
    記複数のカラムブロックは順序付けされており、前記検
    索データ転送手段は前記複数のカラムブロックに対応し
    て複数のカラム検索単位に分割されており、前記検索デ
    ータ転送手段はこれら複数のカラム検索単位にわたって
    延在するストリングデータバスを具備し、各カラムブロ
    ックは読み出されたデータを転送するカラムデータ線束
    を具備し、このカラムデータ線束は所定カラムデータ線
    とそれ以外のカラムデータ線から構成され、各カラム検
    索単位は前記カラムデータ線束と前記ストリングデータ
    バスにより与えられた前記ストリングデータとを比較し
    この比較結果に応じて第５の信号に応じて直後のカラム
    ブロックに比較結果を与え、且つ直前のカラムブロック
    から与えられた比較結果に基づいて前記所定カラムデー
    タ線にマークを付するビット比較・マーク手段を具備す
    ることを特徴とする検索メモリ。
11. 【請求項１１】請求項１０記載の検索メモリにおいて、
    前記ビット比較・マーク手段は前記ストリングデータバ
    ス上の前記ストリングデータを取り込み、これを保持す
    るストリングビットレジスタ手段を具備し、このストリ
    ングヒットレジスタ手段に保持されているデータは第
    １、第２、第３の３値のデータであり、このストリング
    ビットレジスタ手段があるビットにつき前記第３のデー
    タを保持しているときには前記カラムデータ線束と前記
    ストリングデータとの比較の際、当該ビットについては
    比較結果に関わらず一致したものとみなすことを特徴と
    する検索メモリ。
12. 【請求項１２】請求項１記載の検索メモリにおいて、前
    記メモリセルはダイナミック型メモリセルであることを
    特徴とする検索メモリ。
13. 【請求項１３】請求項１記載の検索メモリにおいて、前
    記メモリセルはスタテック型メモリセルであることを特
    徴とする検索メモリ。
14. 【請求項１４】請求項１記載の検索メモリにおいて、前
    記メモリセルはカスケード接続されたダイナミック型メ
    モリセルであることを特徴とする検索メモリ。
15. 【請求項１５】請求項１記載の検索メモリにおいて、前
    記メモリセルはＮＡＮＤ型ＥＥＰＲＯＭセルであること
    を特徴とする検索メモリ。
16. 【請求項１６】請求項１記載の検索メモリにおいて、前
    記メモリセルはＭＲＯＭセルであることを特徴とする検
    索メモリ。
17. 【請求項１７】複数のレジスタから構成され、複数のカ
    ラムブロックに分割されたレジスタアレイと、 外部から入力されたストリングデータと各カラムブロッ
    ク内のデータとを比較し、この比較結果に応じてカラム
    ブロックのいくつかにマークを付し、このマークが付さ
    れたカラムブロック内のデータを順次転送出力する検索
    データ転送手段とから構成されるデータ検索装置。
18. 【請求項１８】請求項１７記載のデータ検索装置におい
    て、前記検索データ転送手段は各カラムブロック内のデ
    ータの所定ビットをマークとして用いることを特徴とす
    るデータ検索装置。
19. 【請求項１９】請求項１７記載のデータ検索装置におい
    て、前記複数のカラムブロックは順序付けされており、
    前記検索データ転送手段は、前記比較結果に応じ、スト
    リングデータと各カラムブロック内のデータとが一致し
    たカラムブロックの次のカラムブロックに対しマークを
    付することを特徴とするデータ検索装置。
20. 【請求項２０】請求項１７記載のデータ検索装置におい
    て、前記複数のカラムブロックは順序づけされており、
    前記検索データ転送手段は、前記比較結果に応じ、スト
    リングデータと各カラムブロック内のデータとが一致し
    たカラムブロックに対しマークを付することを特徴とす
    るデータ検索装置。
21. 【請求項２１】請求項１７記載の検索メモリにおいて、
    前記複数のカラムブロックは順序づけされており、前記
    検索データ転送手段は、第１の信号を受けることによ
    り、マークを付されたカラムブロックの直前のカラムブ
    ロック内のデータを転送出力することを特徴とするデー
    タ検索装置。
22. 【請求項２２】請求項１７記載のデータ検索装置におい
    て、前記複数のカラムブロックは順序付けされており、
    前記検索データ転送手段は、前記比較結果に応じ、第２
    の信号を受けることにより、ストリングデータと各カラ
    ムブロック内のデータとが一致したカラムブロックの次
    のカラムブロックに対しマークを付すると共に、第３の
    信号を受けることにより、ストリングデータと各カラム
    ブロック内のデータとが一致したカラムブロックの次の
    カラムブロックのマークを消去することを特徴とするデ
    ータ検索装置。
23. 【請求項２３】複数の記憶素子から構成され、複数の順
    序付けされたカラムブロックに分割された記憶素子列
    と、外部から入力されたストリングデータと各カラムブ
    ロック内の前記記憶素子が格納するデータとを比較し、
    この比較結果に応じてカラムブロックのいくつかにマー
    クを付し、このマークが付されたカラムブロック内の記
    憶素子が格納するデータを順次転送出力する検索データ
    転送手段とから構成される検索装置の使用方法におい
    て、 第１のストリングデータを前記検索データ転送手段に入
    力しこの第１のストリングデータと各カラムブロック内
    の前記記憶素子が格納するデータとを比較し、両者が一
    致したカラムブロックの直後のカラムブロックにマーク
    を付するステッ プと、第２のストリングデータを前記検索データ転送手
    段に入力しこの第２のストリングデータと各カラムブロ
    ック内の前記記憶素子が格納するデータとを比較し、両
    者が一致し、且つマークが付されているカラムブロック
    の直後のカラムブロックにマークを付するステップと、 再度前記第１のストリングデータを前記検索データ転送
    手段に入力しこの第１のストリングデータと各カラムブ
    ロック内の前記記憶素子が格納するデータとを比較し、
    両者が一致したカラムブロックの直後のカラムブロック
    のマークを消去するステップとを具備することにより階
    層構造のデータの検索を行う検索装置の使用方法。
24. 【請求項２４】複数の記憶素子から構成され、複数の順
    序付けされたカラムブロックに分割された記憶素子列
    と、外部から入力されたストリングデータと各カラムブ
    ロック内の前記記憶素子が格納するデータとを比較し、
    この比較結果に応じてカラムブロックのいくつかにマー
    クを付し、このマークが付されたカラムブロック内の記
    憶素子が格納するデータを順次転送出力する検索データ
    転送手段とから構成される検索装置の使用方法におい
    て、 第１のストリングデータを前記検索データ転送手段に入
    力しこの第１のストリングデータと各カラムブロック内
    の前記記憶素子が格納するデータとを比較し、両者が一
    致したカラムブロックの直後のカラムブロックにマーク
    を付するステップと、 第２のストリングデータを前記検索データ転送手段に入
    力しこの第２のストリングデータと各カラムブロック内
    の前記記憶素子が格納するデータとを比較し、両者が一
    致し、且つマークが付されているカラムブロックの直後
    のカラムブロックにマークを付するステップと、 再度前記第１のストリングデータを前記検索データ転送
    手段に入力しこの第１のストリングデータと各カラムブ
    ロック内の前記記憶素子が格納するデータとを比較し、
    両者が一致したカラムブロックのマークを消去するステ
    ップとを具備することにより階層構造のデータの検索を
    行う検索装置の使用方法。
25. 【請求項２５】複数の記憶素子から構成され、複数の順
    序付けされたカラムブロックに分割された記憶素子列
    と、外部から入力されたストリングデータと各カラムブ
    ロック内の前記記憶素子が格納するデータとを比較し、
    この比較結果に応じてカラムブロックのいくつかにマー
    クを付し、このマークが付されたカラムブロック内の記
    憶素子が格納するデータを順次転送出力する検索データ
    転送手段とから構成される検索装置の使用方法におい
    て、 第１のストリングデータを前記検索データ転送手段に入
    力しこの第１のストリングデータと各カラムブロック内
    の前記記憶素子が格納するデータとを比較し、両者が一
    致したカラムブロックの直後のカラムブロックにマーク
    を付するステップと、 複数回繰り返されるサブステップからなり、このサブス
    テップは、直前のステップ若しくはサブステップにより
    転送出力された最後のデータがデータ列の末尾を示すデ
    ータであるときには該サブステップを終了し、最後のデ
    ータがデータ列の末尾を示すデータでないときにはこれ
    を第２のストリングデータとして前記検索データ転送手
    段に入力し、この第２のストリングデータと各カラムブ
    ロック内の前記記憶素子が格納するデータとを比較し、
    両者が一致したカラムブロックの直後のカラムブロック
    にマークを付するサブステップであることを特徴とする
    検索メモリの使用方法。