[go: up one dir, main page]

JP2001184870A - 連想メモリ装置およびそれを用いた可変長符号復号装置 - Google Patents

連想メモリ装置およびそれを用いた可変長符号復号装置

Info

Publication number
JP2001184870A
JP2001184870A JP36960699A JP36960699A JP2001184870A JP 2001184870 A JP2001184870 A JP 2001184870A JP 36960699 A JP36960699 A JP 36960699A JP 36960699 A JP36960699 A JP 36960699A JP 2001184870 A JP2001184870 A JP 2001184870A
Authority
JP
Japan
Prior art keywords
comparison
data
match
bit
circuit
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
JP36960699A
Other languages
English (en)
Inventor
Hisakazu Sato
尚和 佐藤
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Mitsubishi Electric Corp
Original Assignee
Mitsubishi Electric Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Mitsubishi Electric Corp filed Critical Mitsubishi Electric Corp
Priority to JP36960699A priority Critical patent/JP2001184870A/ja
Priority to US09/621,531 priority patent/US6389524B1/en
Publication of JP2001184870A publication Critical patent/JP2001184870A/ja
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C15/00—Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/04—Addressing variable-length words or parts of words
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C15/00—Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
    • G11C15/04—Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores using semiconductor elements

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

(57)【要約】 【課題】 検索の対象となるキーワード長を可変に設定
でき、可変長符号のデコードにも効率的に適用可能な連
想メモリ装置を提供する。 【解決手段】 タグアレイ１３は、複数のタグデータを
保持し、検索キーワードとの間で一致比較を実行する。
タグアレイ１３は、各タグデータに対応して設けられる
一致比較回路１５−０〜１５−ｍを有する。各一致比較
回路は、ＣＭセルおよびＣＣセルを有する。各ＣＭセル
は、タグデータのうちの対応するビットを保持し、検索
キーワードの対応するビットとの間で一致比較を実行す
る。各ＣＣセルは、各ＣＭセルの機能に加えて、比較条
件入力線ＣＬ，ＣＬ／によって予め入力される制御条件
信号を保持し、制御条件信号に応じて、対応するビット
におけるタグデータと検索キーワードとの間の不一致検
出を無効とする。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】この発明は、入力された検索
データと記憶しているデータとの比較結果に応じて、記
憶しているデータを出力する連想メモリ装置に関し、よ
り特定的には、比較の対象となるデータ長をソフトウェ
ア的に変更することが可能な連想メモリ装置および当該
連想メモリ装置を用いた可変長符号復号装置に関する。
【０００２】
【従来の技術】特定のキーワードと一致するタグを有す
るデータを検索し、これを読出すメモリ装置として、た
とえば特開平１０−５００７６号公報等に開示される連
想メモリ装置が知られている。連想メモリ装置は、装置
内に格納されたデータの一部（これを以降タグあるいは
タグ部と呼ぶ）と入力されたキーワードとを比較して、
タグ部がキーワードと一致したデータを自動的に読出す
ように構成したものである。
【０００３】
【発明が解決しようとする課題】しかしながら、従来の
連想メモリ装置においては、タグ部のデータ長すなわ
ち、検索の対象となるキーワード長がハードウェア的に
決められることが一般的であった。したがって、たとえ
ば、可変長符号化されたデータにおいては、検索対象と
なるキーワード長を必ずしも一定にできないため、この
ようなデータを連想メモリ装置で処理することは、一般
に困難であった。
【０００４】ここで、比較対象としたいタグが、ハード
ウェア的に予め定められたデータ長よりも短く、かつ格
納されているすべてのタグが同じデータ長であれば、残
りのビットを特定の値で埋め尽くし、与える検索キーワ
ードの対応ビットを同じ値に固定することで正しい検索
を行なうことが可能である。
【０００５】しかしながら、このような方式では、比較
対象となるタグ部データ長がまちまちであり、さらには
デコード後でないと一致したタグのデータ長が定まらな
いため、このような方式を可変長符号のデコードに使用
することはできない。
【０００６】また、別の方式として、タグとして使用し
ていないビットにどのような値が入っていても正しく検
索が実行できるように、連想メモリに対するデータの格
納方法を工夫する方式も考えられている。たとえば、ハ
ードウェア的に定められたタグの長さが８ビットの連想
メモリ装置において、６ビットのタグを持つデータを検
索する場合において、検索キーワードの残り２ビットの
どのような値が入っていても正しいデータが検索される
ようにデータを格納する。
【０００７】すなわち、本来６ビットを有するタグに、
“００”，“０１”，“１０”，“１１”の２ビットデ
ータを拡張して、１つの６ビットのタグに基づいて４つ
の８ビットのタグを作成し、これらのタグに対して同じ
データを対応させる。このようにして、ハードウェア的
に定められたタグのデータ長よりも短い検索データによ
って正しい検索を行なうことができる。
【０００８】しかしながら、この場合には、１つの符号
に対して複数（上の例では４つ）のエントリを必要とす
るため、データ格納の効率が極めて悪くなってしまうと
いう問題点がある。
【０００９】この発明は、このような問題点を解決する
ためになされたものであって、この発明の目的は、検索
対象となるキーワード長をソフトウェア的に変更するこ
とが可能で、可変長符号の復号にも効率よく適用するこ
とが可能な連想メモリ装置およびそれを用いた可変長符
号復号装置を提供することである。
【００１０】
【課題を解決するための手段】請求項１記載の連想メモ
リ装置は、複数ビットを有する検索データの入力に応じ
てデータを出力する連想メモリ装置であって、各々が複
数ビットを有する複数のタグデータを保持し、入力され
た検索データと複数のタグデータの各々との間において
一致比較を行なうキーワード比較アレイを備え、キーワ
ード比較アレイは、複数のタグデータに対応してそれぞ
れ設けられ、検索データと複数のタグデータのうちの対
応する１つとを比較する複数の一致比較回路を含み、各
複数の一致比較回路は、対応するタグデータのうちのｎ
ビット（ｎ：０以上の整数）をそれぞれ保持し、各々
が、保持するビットと検索データの対応するビットとの
間で一致比較を実行するｎ個の比較機能付きメモリ部
と、対応するタグデータのうちのｎビットを除く残りの
ビットを構成する、少なくとも１ビットを有するｍ個
（ｍ：自然数）のビットグループのそれぞれに対応して
設けられる、各々が、対応するビットグループのデータ
および外部から予め与えられる比較条件信号を保持し
て、ビットグループのデータと検索データの対応するビ
ットとの間で一致比較を実行するとともに、比較条件信
号に応じて一致比較の結果を無効化することが可能であ
るｍ個の比較結果無効化機能付きメモリ部とを有し、キ
ーワード比較アレイは、複数の一致比較回路に対応して
それぞれ設けられる、複数の一致検出信号線をさらに含
み、各複数の一致検出信号線は、対応する一致比較回路
に含まれる、一致比較の結果が無効化されたｋ個（ｋ：
０〜ｍの整数）を除く（ｍ−ｋ）個の比較結果無効化機
能付きメモリ部およびｎ個の比較機能付きメモリ部にお
ける、一致比較の結果に応じて電位レベルが定められ、
各複数の一致検出信号線の電位レベルに応答して、検索
データと一致した複数のタグデータのうちの１つに対応
するデータを出力するデータ格納アレイをさらに備え
る。
【００１１】請求項２記載の連想メモリ装置は、請求項
１記載の連想メモリ装置であって、キーワード比較アレ
イは、一致比較を制御するための一致比較制御部をさら
に含み、一致比較制御部は、一致比較の実行に先立って
複数の一致検出信号線を第１の電位にプリチャージした
後に、比較結果無効化機能付メモリ部および比較機能付
きメモリ部の各々に対して一致比較の実行を指示し、各
比較機能付きメモリ部は、一致比較の実行が指示された
場合には、検索データと対応するタグデータとの間にお
いて対応するビット同士が不一致であるときにおいて、
対応する一致検出信号線を第１の電位よりも低い第２の
電位を供給する電源ノードと結合し、各比較結果無効化
機能付メモリ部は、一致比較の実行が指示された場合に
は、比較条件信号によって一致比較の結果が無効化され
ておらず、かつ、検索データと対応するタグデータとの
間において対応するビット同士が不一致であるときにお
いて、対応する一致検出信号線を電源ノードと結合す
る。
【００１２】請求項３記載の連想メモリ装置は、請求項
２記載の連想メモリ装置であって、各ビットグループ
は、１ビットのデータを有し、各比較機能付きメモリ部
は、対応するタグデータのうちの対応する１ビットのデ
ータを保持するための第１のメモリ回路と、対応する一
致検出信号線と電源ノードとの間に直列に接続される第
１および第２のスイッチ回路とを有し、第１のスイッチ
回路は、一致比較制御部によって一致比較の実行が指示
された場合にオンし、第２のスイッチ回路は、第１のメ
モリ回路に保持されるデータと、検索データの対応する
ビットのデータとが不一致であるときにオンし、各比較
結果無効化機能付メモリ部は、各比較機能付きメモリ部
の構成に加えて、さらに、比較条件信号を保持するため
の第２のメモリ回路と、第１および第２のスイッチ回路
と直列に接続され、比較条件信号によって一致比較の結
果が無効化されている場合にオフされる第３のスイッチ
回路とを有する。
【００１３】請求項４記載の連想メモリ装置は、請求項
２記載の連想メモリ装置であって、各ビットグループ
は、ｉビット（ｉ：２以上の自然数）のデータを有し、
各比較結果無効化機能付メモリ部は、対応するタグデー
タのうちの対応するｉビットをそれぞれ保持するための
ｉ個の第１のメモリ回路と、比較条件信号を保持するた
めの第２のメモリ回路と、一致比較制御部によって一致
比較の実行が指示された場合にオンする第１のスイッチ
回路と、ｉ個の第１のメモリ回路にそれぞれ対応して設
けられ、各々は、対応する第１メモリ回路に保持される
データと、検索データの対応するビットのデータとが不
一致であるときにオンするｉ個の第２のスイッチ回路
と、比較条件信号によって一致比較の結果が無効化され
ている場合にオフされる第３のスイッチ回路とを有し、
前第１および第２のスイッチ回路は、互いに直列に電源
ノードと直列に接続され、ｉ個の第３のスイッチ回路
は、第１および第２のスイッチ回路と対応する一致検出
信号線との間に並列に接続される。
【００１４】請求項５記載の連想メモリ装置は、請求項
２記載の連想メモリ装置であって、各ビットグループ
は、ｉビット（ｉ：３以上の自然数）のデータを有し、
比較条件信号は、ｊビット（ｊ：２以上の自然数）を有
し、各比較結果無効化機能付メモリ部は、比較条件信号
のｊビットを保持するための比較条件保持回路と、対応
するビットグループのｉビットのデータにそれぞれ対応
する第１番目から第ｉ番目までのデータ比較回路とを有
し、各データ比較回路は、ｉビットのうちの対応するビ
ットを保持するための第１のメモリ回路と、一致比較制
御部によって一致比較の実行が指示された場合にオンす
る第１のスイッチ回路と、第１メモリ回路に保持される
データと、検索データの対応するビットのデータとが不
一致であるときにオンする第２のスイッチ回路と、一致
信号線と電源ノードとの間に、第１および第２のスイッ
チ回路と直列に接続される第３のスイッチ回路とを有
し、比較条件信号のｊビットの組合せに応じて、各デー
タ比較回路中の第３のスイッチ回路はオンオフされる。
【００１５】請求項６記載の連想メモリ装置は、請求項
５記載の連想メモリ装置であって、比較条件信号のｊビ
ットの組合せに応じて、第１番目から第ｉ番目までのデ
ータ比較回路のうち、第Ｌ番目（Ｌ：ｉ以下の整数）ま
でのデータ比較回路において、第３のスイッチ回路はオ
ンされる。
【００１６】請求項７記載の連想メモリ装置は、請求項
５記載の連想メモリ装置であって、比較条件信号のビッ
ト数ｊと、各ビットグループの有するビット数ｉとの関
係は、ｉ＝２j−１で表わされる。
【００１７】請求項８記載の連想メモリ装置は、請求項
２記載の連想メモリ装置であって、一致比較制御部は、
各複数の一致検出信号線の電位レベルに応じて、入力さ
れた検索データと一致するタグデータが存在したどうか
を示す検索結果を出力する。
【００１８】請求項９記載の連想メモリ装置は、請求項
１記載の連想メモリ装置であって、複数のタグデータお
よび比較条件信号は、予め連想メモリ装置外部より入力
される。
【００１９】請求項１０記載の可変長符号復号装置は、
可変長符号データの復号を行なう可変長符号復号装置で
あって、復号の対象として入力される可変長符号データ
のビット列を受けて、１回の復号処理の対象となる一定
ビット数を含む検索データを出力する検索データ設定回
路と、検索データの入力に応じて、可変長符号データに
対応する復号データおよび復号データのビット長を示す
符号長データとを出力する連想メモリ回路とを備え、連
想メモリ回路は、符号化された可変長符号データを複数
のタグデータの一部ビットとして保持し、入力された検
索データと複数のタグデータの各々との間において一致
比較を行なうキーワード比較アレイを含み、キーワード
比較アレイは、複数のタグデータに対応してそれぞれ設
けられ、検索データと複数のタグデータのうちの対応す
る１つとを比較する複数の一致比較回路を有し、各複数
の一致比較回路は、対応するタグデータを構成する、少
なくとも１ビットを有するｍ個（ｍ：自然数）のビット
グループのそれぞれに対応して設けられるｍ個の比較結
果無効化機能付きメモリ部を有し、各々比較結果無効化
機能付きメモリ部は、対応するビットグループのデータ
および外部から予め与えられる比較条件信号を保持し
て、ビットグループのデータと検索データの対応するビ
ットとの間で一致比較を実行するとともに、比較条件信
号に応じて一致比較の結果を無効化することが可能であ
るｍ個の比較結果無効化機能付きメモリ部とを有し、キ
ーワード比較アレイは、複数の一致比較回路に対応して
それぞれ設けられる、複数の一致検出信号線をさらに有
し、各複数の一致検出信号線は、対応する一致比較回路
に含まれる一致比較の結果が無効化されたｋ個（ｋ：０
〜ｍの整数）を除く（ｍ−ｋ）個の比較結果無効化機能
付きメモリ部における一致比較の結果に応じて電位レベ
ルが定められ、連想メモリ回路は、各複数の一致検出信
号線の電位レベルに応答して、複数のタグデータのうち
の１つに対応する可変長符号データに関する、復号デー
タおよび符号長データを出力するデータ格納アレイをさ
らに含み、符号長データに応じて、検索データ設定回路
に対して、入力される可変長符号データのビット列のう
ち、次の１回の復号処理の対象となる先頭ビットを指定
するための復号対象ポインタ回路をさらに備える。
【００２０】請求項１１記載の可変長符号復号装置は、
請求項１０記載の可変長符号復号装置であって、対応す
る一致比較回路に含まれるｍ個の比較結果無効化機能付
きメモリ部のうち、可変長符号データに対応するデータ
が保持されていない比較結果無効化機能付きメモリにお
いて、一致比較の結果は無効化される。
【００２１】請求項１２記載の可変長符号復号装置は、
請求項１０記載の可変長符号復号装置であって、キーワ
ード比較アレイは、一致比較を制御するための一致比較
制御部をさらに含み、一致比較制御部は、一致比較の実
行に先立って複数の一致検出信号線を第１の電位にプリ
チャージするとともに、比較結果無効化機能付メモリ部
の各々に対して一致比較の実行を指示し、各比較結果無
効化機能付メモリ部は、一致比較の実行が指示された場
合には、比較条件信号によって一致比較の結果が無効化
されておらず、かつ、検索データと対応するタグデータ
との間において対応するビット同士が不一致であるとき
において、対応する一致検出信号線を第１の電位よりも
低い第２の電位を供給する電源ノードと結合する。
【００２２】請求項１３記載の可変長符号復号装置は、
請求項１２記載の可変長符号復号装置であって、各ビッ
トグループは、１ビットのデータを有し、各比較結果無
効化機能付メモリ部は、対応するタグデータのうちの対
応する１ビットのデータを保持するための第１のメモリ
回路と、比較条件信号を保持するための第２のメモリ回
路と、対応する一致検出信号線と電源ノードとの間に直
列に接続される第１および第２のスイッチ回路とを有
し、第１のスイッチ回路は、一致比較制御部によって一
致比較の実行が指示された場合にオンし、第２のスイッ
チ回路は、第１のメモリ回路に保持されるデータと、検
索データの対応するビットのデータとが不一致であると
きにオンし、第１および第２のスイッチ回路と直列に接
続され、比較条件信号によって一致比較の結果が無効化
されている場合にオフされる第３のスイッチ回路をさら
に有する。
【００２３】請求項１４記載の可変長符号復号装置は、
請求項１２記載の可変長符号復号装置であって、各ビッ
トグループは、ｉビット（ｉ：２以上の自然数）のデー
タを有し、各比較結果無効化機能付メモリ部は、対応す
るタグデータのうちの対応するｉビットをそれぞれ保持
するためのｉ個の第１のメモリ回路と、比較条件信号を
保持するための第２のメモリ回路と、一致比較制御部に
よって一致比較の実行が指示された場合にオンする第１
のスイッチ回路と、ｉ個の第１のメモリ回路にそれぞれ
対応して設けられ、各々は、対応する第１メモリ回路に
保持されるデータと、検索データの対応するビットのデ
ータとが不一致であるときにオンするｉ個の第２のスイ
ッチ回路と、比較条件信号によって一致比較の結果が無
効化されている場合にオフされる第３のスイッチ回路と
を有し、前第１および第２のスイッチ回路は、互いに直
列に、電源ノードと直列に接続され、ｉ個の第３のスイ
ッチ回路は、第１および第２のスイッチ回路と対応する
一致検出信号線との間に並列に接続される。
【００２４】請求項１５記載の可変長符号復号装置は、
請求項１２記載の可変長符号復号装置であって、各ビッ
トグループは、ｉビット（ｉ：３以上の自然数）のデー
タを有し、比較条件信号は、ｊビット（ｊ：２以上の自
然数）を有し、各比較結果無効化機能付メモリ部は、比
較条件信号のｊビットを保持するための比較条件保持回
路と、対応するビットグループのｉビットのデータにそ
れぞれ対応する第１番目から第ｉ番目までのデータ比較
回路とを有し、各データ比較回路は、ｉビットのうちの
対応するビットを保持するための第１のメモリ回路と、
一致比較制御部によって一致比較の実行が指示された場
合にオンする第１のスイッチ回路と、第１メモリ回路に
保持されるデータと、検索データの対応するビットのデ
ータとが不一致であるときにオンする第２のスイッチ回
路と、一致信号線と電源ノードとの間に、第１および第
２のスイッチ回路と直列に接続される第３のスイッチ回
路とを有し、比較条件信号のｊビットの組合せに応じ
て、各データ比較回路中の第３のスイッチ回路はオンオ
フされる。
【００２５】請求項１６記載の可変長符号復号装置は、
請求項１５記載の可変長符号復号装置であって、比較条
件信号のｊビットの組合せに応じて、第１番目から第ｉ
番目までのデータ比較回路のうち、第Ｌ番目（Ｌ：ｉ以
下の整数）までのデータ比較回路において、第３のスイ
ッチ回路はオンされる。
【００２６】請求項１７記載の可変長符号復号装置は、
請求項１０記載の可変長符号復号装置であって、検索デ
ータは、復号処理を実行する場合に所定レベルに設定さ
れる復号実行ビットを含み、各複数の一致比較回路は、
内部に所定レベルを保持して、検索データのうちの復号
実行ビットとの間で一致比較を実行する比較機能付きメ
モリ部をさらに有し、キーワード比較アレイは、一致比
較を制御するための一致比較制御部をさらに含み、一致
比較制御部は、一致比較の実行に先立って複数の一致検
出信号線を第１の電位にプリチャージした後に、比較結
果無効化機能付メモリ部および比較機能付きメモリ部の
各々に対して一致比較の実行を指示し、各比較機能付き
メモリ部は、一致比較の実行が指示された場合には、検
索データと対応するタグデータとの間において対応する
ビット同士が不一致であるときにおいて、対応する一致
検出信号線を第１の電位よりも低い第２の電位を供給す
る電源ノードと結合し、各比較結果無効化機能付メモリ
部は、一致比較の実行が指示された場合には、比較条件
信号によって一致比較の結果が無効化されておらず、か
つ、検索データと対応するタグデータとの間において対
応するビット同士が不一致であるときにおいて、対応す
る一致検出信号線を電源ノードと結合する。
【００２７】請求項１８記載の可変長符号復号装置は、
請求項１７記載の可変長符号復号装置であって、一致比
較制御部は、各複数の一致検出信号線の電位レベルに応
じて、入力された検索データと一致するタグデータが存
在したどうかを示す検索結果を出力する。
【００２８】
【発明の実施の形態】以下において、本発明の実施の形
態について図面を参照して詳しく説明する。なお、図中
における同一符号は同一または相当部分を示す。
【００２９】［実施の形態１］図１は、本発明の実施の
形態１に従う連想メモリ装置１００の全体構成を示す概
略ブロック図である。
【００３０】図１を参照して、連想メモリ装置１００
は、内部にタグ部のデータ（以下、タグデータとも称す
る）を記憶し、タグデータと外部から入力された検索キ
ーワードとの間で一致比較を行なうキーワード比較部１
と、キーワード比較部１における比較結果に応じて、内
部に記憶されたデータを読出すデータ格納部２とを備え
る。
【００３１】キーワード比較部１は、外部から入力され
る複数のタグデータを保持するとともに、検索キーワー
ドと各タグデータとの間の比較動作を実行するためのタ
グアレイ１３と、データの書込動作時において外部から
入力される書込アドレスに応答して、タグアレイ１３中
の対応する領域を活性化するためのタグワード線制御部
１２と、タグデータの書込時および検索データの読出時
において外部からそれぞれ入力される、検索キーワード
および書込タグデータをタグアレイ１３に与えるための
タグワード制御部１１と、タグアレイ１３における比較
動作を制御するとともに比較結果を出力するための一致
検出制御部１４とを含む。
【００３２】タグアレイ１３の詳細な構成は後ほど説明
するが、タグアレイ１３中には、（ｍ＋１）個（ｍ：自
然数）のタグデータを格納することができる。
【００３３】一致検出制御部１４は、入力された検索キ
ーワードと一致するタグデータがタグアレイ１３内に格
納されているか否かを示す検索判定結果と、検索キーワ
ードと一致したタグデータを特定するための一致信号Ｍ
Ｔ０〜ＭＴｍを出力する。
【００３４】データ格納部２は、外部から入力された書
込データを保持するためのデータアレイ２３と、書込デ
ータをデータアレイ２３に伝達するためのデータワード
制御部２１と、データ書込時において外部から入力され
る書込アドレスおよび、検索データ読出時においてキー
ワード比較部１から出力される一致信号ＭＴ０〜ＭＴｍ
に応じて、データアレイ２３中の対応する領域を活性化
するためのデータワード線制御部２２と、データワード
線制御部２２の指示に応じてデータアレイ２３から読出
されたデータを増幅して出力するためのセンスアンプ部
２４とを含む。
【００３５】タグアレイ１３およびデータアレイ２３
は、それぞれ、行列状に配置された複数の記憶素子を有
するが、後ほど詳しく説明するように、タグアレイ１３
に配置される記憶素子は、比較機能を有する。また、デ
ータアレイ２３の構成は、一般のＲＡＭメモリ（Random
Access Memory）のメモリセルアレイと同様の構成であ
る。
【００３６】連想メモリ装置１００においては、当該連
想メモリ装置１００に対するアクセスが読出／書込のい
ずれであるかを示すための制御信号や、動作タイミング
を規定するためのクロック信号などがさらに入力される
が、図１においては、表記を簡略化するために、これら
の信号については説明を割愛している。
【００３７】タグデータ（書込タグ）と、書込データと
は、書込アドレスによって対応付けられて、タグアレイ
１３およびデータアレイ２３にそれぞれ記憶される。
【００３８】図２は、キーワード比較部１の構成を説明
するためのブロック図である。図２を参照して、タグア
レイ１３は、（ｍ＋１）行×（ｎ＋１）列に配置された
複数の比較機能付記憶素子を有する。後程説明するよう
に、比較機能付記憶素子は、通常の比較機能付記憶素子
（以下、ＣＭセルと称する）および、比較結果の無効化
を指定することが可能な比較機能付記憶素子（以降、Ｃ
Ｃセルと称する）を含む。
【００３９】図３は、ＣＭセルの構成を説明するための
回路図である。図３を参照して、ＣＭセル３００は、タ
グワード線ＴＷＬ、一致信号線ＭＬ、比較動作制御線Ｃ
ＥＬ、およびデータ信号線ＫＬ，ＫＬ／と接続される。
データ信号線ＫＬおよびＫＬ／には、互いに相補の信号
が伝達される。
【００４０】ＣＭセル３００は、ノードＮａおよびＮｂ
のデータをラッチするためのインバータ対を形成する、
ＩＶ１０およびＩＶ１２をそれぞれ構成するトランジス
タ３０１，３０３およびトランジスタ３０２，３０４
と、ノードＮａおよびノードＮｂにデータ信号線ＫＬお
よびＫＬ／のデータをそれぞれ書込むための書込トラン
ジスタ３０５および３０６と、ノードＮａに保持された
データとデータ信号線ＫＬによって伝達されるデータと
の間で一致比較を行なうための比較回路３２０とを含
む。
【００４１】比較回路３２０は、ノードＮｂと接続され
るゲートを有しデータ信号線ＫＬとノードＮｃとの間に
接続されるトランジスタ３０７と、ノードＮａと接続さ
れるゲートを有し、ノードＮｃとデータ信号線ＫＬ／と
の間に接続されるトランジスタ３０８と、一致信号線Ｍ
Ｌと接地ノードとの間に直列に接続されるトランジスタ
３０９および３１０とを有する。トランジスタ３０９お
よび３１０のゲートは、ノードＮｃおよび比較動作制御
線ＣＥＬにそれぞれ接続される。
【００４２】このような構成とすることにより、タグワ
ード線ＴＷＬの活性化（Ｈレベル）に応じて、データ信
号線ＫＬおよびＫＬ／に伝達されるデータが、トランジ
スタ３０５および３０６をそれぞれ介してノードＮａお
よびノードＮｂに伝達され、インバータＩＶ１０および
ＩＶ１２によって保持される。
【００４３】比較回路３２０において、トランジスタ３
０７および３０８は、インバータ対ＩＶ１０，ＩＶ１２
によって保持されるデータに応じて、データ信号線ＫＬ
およびＫＬ／のいずれか一方とノードＮｃとを接続す
る。これにより、ノードＮａに保持されるデータとデー
タ信号線ＫＬによって伝達されるデータとが一致しない
ときに、トランジスタ３０９はオンされる。比較動作制
御線ＣＥＬの活性化によってトランジスタ３１０がオン
され、かつノードＮａの保持データとデータ信号線ＫＬ
の伝達データとが異なってトランジスタ３０９がオンさ
れたときにおいて、一致信号線ＭＬは、接地ノードと接
続される。
【００４４】図４は、ＣＣセルの具体的な構成を示す回
路図である。図４を参照して、ＣＣセル４００は、ＣＭ
セルが接続されるタグワード線ＴＷＬ、比較動作制御線
ＣＥＬ、一致信号線ＭＬおよびデータ信号線ＫＬ，ＫＬ
／に加えて、比較条件入力線ＣＬ，ＣＬ／とさらに接続
される。比較条件入力線ＣＬおよびＣＬ／は、比較条件
信号ＣＮおよびその反転信号ＣＮ／をそれぞれ伝達す
る。
【００４５】比較条件信号ＣＮは、タグデータの書込時
において、タグワード制御部１１から与えられ、検索キ
ーワードとタグデータの間で比較動作を実行するビット
において、信号レベルが「真（Ｈレベル）」に設定され
る信号である。
【００４６】ＣＣセル４００は、ＣＭセル部３００を構
成するトランジスタ４０１〜４１０と、比較結果無効化
回路４４０を構成するトランジスタ４１１〜４１７とを
有する。このうちトランジスタ４０１〜４０９の接続態
様については、図３で説明したＣＭセルの場合と同様で
あるので説明は繰返さない。また、トランジスタ４１０
は、比較結果無効化回路４４０に含まれるトランジスタ
４１７を介して接地ノードと接続される。
【００４７】比較結果無効化回路４４０は、比較条件入
力線ＣＬおよびＣＬ／の信号レベルをノードＮｄおよび
Ｎｅに伝達するための書込トランジスタ４１５および４
１６と、ノードＮｄおよびＮｅのデータを保持するため
のインバータ対ＩＶ１４およびＩＶ１６をそれぞれ構成
するトランジスタ４１１，４１３およびトランジスタ４
１２，４１４を有する。
【００４８】トランジスタ４１５および４１６のゲート
はタグワード線ＴＷＬに接続され、タグワードの書込時
に与えられる書込アドレスに応じたタグワード線ＴＷＬ
の活性化によって、比較条件入力線ＣＬ，ＣＬ／によっ
て伝達される比較条件信号ＣＮ，ＣＮ／が、ノードＮｄ
およびＮｅにそれぞれ伝達され、ラッチされる。
【００４９】比較結果無効化回路４４０は、ノードＮｄ
の電位レベルに応じてオンオフするトランジスタ４１７
をさらに有する。したがって、ノードＮｄの電位レベル
がＨレベルであるとき、すなわち、ラッチされる比較条
件信号ＣＮが「真（Ｈレベル）」である場合において、
トランジスタ４１７はオンされる。一方、ノードＮｄの
電位レベルがＬレベルであるとき、すなわち、ラッチさ
れる比較条件信号ＣＮが「偽（Ｌレベル）」である場合
において、トランジスタ４１７はオフされる。
【００５０】このような構成とすることにより、ＣＣセ
ルは、比較動作制御信号ＣＥが活性化され、かつデータ
信号線ＫＬに伝達されるデータとノードＮａに保持され
るデータのレベルが一致せず、さらにノードＮｄにラッ
チされる比較条件信号ＣＮが「真（Ｈレベル）」である
場合においてのみ、一致信号線ＭＬと接地ノードとを接
続する。すなわち、ノードＮｄに保持される比較条件信
号ＣＮが「偽（Ｌレベル）」である場合には、ＣＭセル
部における比較結果に関わらず、一致信号線ＭＬと接地
ノードとが接続されることはない。
【００５１】再び図２を参照して、図２の例において
は、最左の２列においては、ＣＭセルが配置され、その
他の残りの列についてはＣＣセルが配置されている。こ
れにより、本実施の形態においては、検索キーワードと
格納されたタグデータとの間で最上位の２ビットについ
ては必ず比較動作が実行されるが、タグデータの残りビ
ットについては、比較動作を実行するか否かは、比較条
件信号ＣＮによって外部から指定することが可能であ
る。
【００５２】同一の行に属する比較機能付記憶素子は、
タグアレイ１３に格納される複数のタグデータにそれぞ
れ対応する一致比較回路１５−０〜１５−ｍを構成す
る。
【００５３】一致比較回路１５−０〜１５−ｍに対応し
て、すなわち比較機能付記憶素子の行に対応して、タグ
ワード線ＴＷＬ０〜ＴＷＬｍおよび一致信号線ＭＬ０〜
ＭＬｍがそれぞれ配置される。
【００５４】タグワード線制御部１２は、タグデータの
書込動作時において、書込アドレスに応じて、タグワー
ド線ＴＷＬ０〜ＴＷＬｍの活性化（Ｈレベルへ）／非活
性化（Ｌレベルへ）を制御する。タグワードの書込が指
定されたアドレスに対応するタグワード線は、タグワー
ド線制御部１２によって活性化される。
【００５５】一致信号線ＭＬ０〜ＭＬｍの各々は、対応
する一致比較回路における、検索キーワードと格納され
るタグデータとの間の一致比較結果に応答してその電位
が定められる。一致検出制御部１４は、一致信号線ＭＬ
０〜ＭＬｍの電位レベルに応答して、一致検出信号ＭＴ
０〜ＭＴｍおよび検索判定結果を出力する。
【００５６】一致検出制御部１４は、さらに、各比較機
能付記憶素子に対して比較動作の実行を指示するための
比較動作制御信号ＣＥを出力する。比較動作制御信号Ｃ
Ｅは、比較制御線ＣＥＬによって各比較機能付記憶素子
に伝達される。
【００５７】比較機能付記憶素子の各列に対応して、デ
ータ信号線ＫＬ０〜ＫＬｎと、これらの相補線ＫＬ／０
〜ＫＬ／ｎが設けられる。さらに、ＣＣセルが配置され
る列ごとに、比較条件入力線が設けられる。図２の例に
おいては、ＣＭセルが配置される最左の２列を除く残り
の列に対応して、比較条件入力線ＣＬ２〜ＣＬｎおよび
これらの相補線ＣＬ／２〜ＣＬ／ｎが設けられる。
【００５８】タグワード制御部１２は、データの書込動
作時においては、外部から与えられる書込タグを受け
る。書込タグは、タグデータの各ビットデータと、ＣＣ
セルに対応するタグデータの各ビットにおける比較動作
の有効／無効を指定するための比較条件信号とを含む。
書込タグの各データは、データ信号線ＫＬ０〜ＫＬｎお
よびＫＬ／０〜ＫＬ／ｎと、比較条件入力線ＣＬ２〜Ｃ
ＬｎおよびＣＬ／２〜ＣＬ／ｎとによって、タグアレイ
１３に伝達され、対応するＣＣセルおよびＣＭセルに格
納される。
【００５９】タグワード制御部１２は、検索データ読出
動作時においては、外部から検索キーワードを受ける。
検索キーワードの各ビットは、データ信号線ＫＬ０，Ｋ
Ｌ／０〜ＫＬｎ，ＫＬ／ｎによって、タグアレイ１３に
伝達され、対応するＣＣセルおよびＣＭセルにおいて、
記憶されたタグデータのビットとの間で比較が行なわれ
る。
【００６０】一致検出制御部１４は、検索データ読出動
作時において、すべての一致信号線ＭＬ０〜ＭＬｍを所
定電位にプリチャージする。その後、一致検出制御部１
４は、比較動作制御信号ＣＥを活性化（Ｈレベル）し、
比較動作の開始を指示する。各ＣＣセルおよびＣＭセル
においては、自らの記憶しているデータと、データ信号
線ＫＬ０〜ＫＬｎに与えられたデータが一致しない場合
において、対応する一致信号線上にプリチャージされた
電荷を接地ノードに向けてディスチャージする。
【００６１】ただし、ＣＣセルにおいては、保持される
比較条件信号が偽（Ｌレベル）に設定されている場合に
おいては、比較結果無効化回路の作用により、比較結果
に関わらず一致信号線のディスチャージは実行されな
い。
【００６２】すなわち、一致信号線ＭＬ０〜ＭＬｍの各
々は、自らに接続されたすべてのＣＭセルおよびＣＣセ
ルにおいて記憶されるタグデータの各ビットとデータ信
号線ＫＬ０〜ＫＬｎによって伝達される検索キーワード
の各ビットが完全に一致したか、または不一致のビット
に対応するＣＣセルの全てにおいて、比較条件信号ＣＮ
が「偽」とされて比較結果が無効化されている場合にお
いてのみ、予めプリチャージされた電位を保持する。
【００６３】それ以外の場合、すなわち、一本の一致信
号線に接続されたＣＭセルおよび、比較条件信号ＣＮが
「真」とされて比較結果が無効化されていないＣＣセル
のうちの少なくとも１つにおいて、記憶されるタグデー
タおよび検索キーワードの対応するビット同士の間で不
一致が検出された場合には、その一致信号線はディスチ
ャージされる。
【００６４】一致検出制御部１４は、比較動作の終了
後、一致信号線ＭＬ０〜ＭＬｍの各々電位レベルを十分
に増幅して、一致検出信号ＭＴ０〜ＭＴｍとして出力す
る。また、ディスチャージされずに残った一致信号線が
存在した場合には、検索キーワードと一致したタグデー
タが存在したことが示されるため、これに対応して検索
判定結果が活性化（Ｈレベル）される。
【００６５】図５は、データ格納部の構成を詳細に説明
するためのブロック図である。図５を参照して、データ
アレイ２３は、（ｍ＋１）行×（ｋ＋１）列に配置され
たＲＡＭセルＭ００〜Ｍｍｋを含む。ＲＡＭセルの各行
に対応して、データワード線ＤＷＬ０〜ＤＷＬｍがそれ
ぞれ設けられ、ＲＡＭセルの各列に対応してビット線Ｂ
Ｌ０〜ＢＬｋがそれぞれ設けられる。ＢＬ／０〜ＢＬ／
ｋは、ビット線ＢＬ０〜ＢＬｋと相補の信号を伝達し、
ＢＬ０〜ＢＬｋとの間でビット線対をそれぞれ形成す
る。
【００６６】図６は、ＲＡＭセルの一例を示す回路図で
ある。図６においては、ＲＡＭセルの構成の一例とし
て、いわゆるＣ−ＭＯＳ型のＳＲＡＭセルの構成が示さ
れる。
【００６７】図６を参照して、ＲＡＭセル５００は、デ
ータワード線ＤＷＬの活性化に応じて、ビット線対Ｂ
Ｌ，ＢＬ／の伝達するデータをそれぞれ取込むための書
込トランジスタ５０５および５０６と、取込まれたデー
タをラッチするためのインバータＩＶ２０およびＩＶ２
２をそれぞれ構成するトランジスタ５０１，５０３およ
びトランジスタ５０２，５０４を含む。このようなＳＲ
ＡＭセルの動作についてはよく知られているのでここで
は説明を省略する。本発明においては、ＲＡＭセルとし
て、ランダムアクセス可能な、一般的に知られるメモリ
セルの回路構成を自由に適用することが可能である。
【００６８】再び図５を参照して、データワード線制御
部２２は、データの書込動作時において、タグアレイ部
１３に記憶される各タグデータと対応付けられるデータ
の各ビットの値をデータアレイ部２３に記録するため
に、書込アドレスに応じてデータワード線ＤＷＬ０〜Ｄ
ＷＬｍを選択的に活性化（Ｈレベルへ）する。
【００６９】データワード線制御部２２は、データの読
出動作時においては、キーワード比較部１から出力され
る一致検出信号ＭＴ０〜ＭＴｍに応答して、データワー
ド線ＤＷＬ０〜ＤＷＬｍを選択的に活性化する。この場
合には、活性化されたデータワード線に接続されるＲＡ
Ｍメモリからデータがビット線対に読出され、ビット線
対に読出されたデータはセンスアンプ部２４によって増
幅される。
【００７０】これにより、キーワード比較部において、
検索キーワードと一致したタグデータが存在した場合に
は、一致したタグデータに対応する（ｋ＋１）ビットの
データがセンスアンプ部２４より検索出力として読出さ
れる。
【００７１】また、検索データ読出時においては、デー
タ読出の速度が低下したり、誤ってＲＡＭセルが保持し
ているデータが破壊されたりすることを避けるために、
各ビット線対を予め適当な電位にプリチャージしておく
ことが必要であり、データワード制御部２１は、検索デ
ータ読出時においてこのようなプリチャージ動作を実行
する。
【００７２】データ格納部２は、以上説明したように、
検索データ読出時において、データワード線ＤＷＬ０〜
ＤＷＬｍが、外部から入力されるアドレス信号ではなく
キーワード比較部１における一致検出結果に基づいて選
択的に活性化されることを除いては、その動作は、通常
のメモリ装置と同様である。
【００７３】以上で説明したように、実施の形態１に従
う連想メモリ装置においては、タグデータの各ビットデ
ータを書込む場合において、タグデータの当該ビットと
検索キーワードの対応するビットとの間における比較動
作を、外部からの信号入力によって無効化することがで
きる。これにより、検索キーワードと比較されるタグデ
ータのビット長を外部からの信号入力によってソフトウ
ェア的に任意に指定することが可能となる。これによ
り、後程詳しく説明するように、当該連想メモリ装置を
可変長符号の復号にも効率よく適用することが可能とな
る。
【００７４】なお、図２に示したように、ＣＭセルを設
けることとした列に対応するビットにおいては、常に検
索キーワードとタグデータとの間の比較結果が有効とさ
れる。ただし、このように常に比較動作が有効とされる
ビット列を必ずしも設ける必要がない場合には、タグア
レイ１３中の記憶素子をすべてＣＣセルで構成すること
も可能である。図３および図４で説明したように、ＣＣ
セルの回路規模は、ＣＭセルよりも大きいので、固定的
に一致比較を実行するビットに対応する列に関しては、
ＣＭセルを適用した方が、レイアウト設計上有利な構成
となる。
【００７５】［実施の形態２］実施の形態１で説明した
ように、本発明の構成は、タグデータを構成する複数ビ
ットのうち、ＣＭセルに対応付けられるビットを除いた
残りのビットを、複数のビットグループに分割して、各
ビットグループごとにＣＣセルを設ける構成と捉えるこ
とが可能である。実施の形態１は、各ビットグループが
１ビットからなるケースに相当し、ＣＣセルの各列ごと
に、比較条件入力線ＣＬを設けることにより、検索の対
象となるキーワード長を１ビット単位で指定できる場合
について説明した。
【００７６】実施の形態２においては、実施の形態２
は、各ビットグループが複数ビットから構成されるケー
ス、具体的には、検索の対象となるキーワード長の指定
が、２ビット単位や３ビット単位等のより粗い精度で足
りる場合において、ハードウェア規模を抑制することが
可能なＣＣセルの構成について説明する。
【００７７】図７は、実施の形態２に従うＣＣセルの構
成を示す回路図である。図７を参照して、実施の形態２
に従うＣＣセル８００は、実施の形態１に従うＣＣセル
部４５０の構成に加えて、比較回路８５０をさらに有す
る。
【００７８】ＣＣセル部４５０は、トランジスタ４０１
〜４１７によって構成されるが、その構成および動作は
図４に示すとおりであるので説明は繰返さない。
【００７９】比較回路８５０は、図３に示したＣＭセル
と類似の構成を有し、ノードＮｆに保持されたデータと
データ信号線ＫＬ１によって伝達されるデータとの間で
一致比較を実行し、両者が不一致の場合にトランジスタ
８０９をオンする。
【００８０】ＣＣセル部４５０は、ノードＮｇに保持さ
れたデータとデータ信号線ＫＬ０によって伝達されるデ
ータとの間で一致比較を実行し、両者が不一致の場合に
は、トランジスタ４０９をオンする。
【００８１】トランジスタ４０８および４０９は、トラ
ンジスタ４１０と一致信号線ＭＬとの間に互いに並列に
接続されるので、ＣＣセル８００においては、データＮ
ｇおよびＮｆにそれぞれ保持されたデータ（タグデータ
のビット）と、データ信号線ＫＬ０およびＫＬ１によっ
てそれぞれ伝達されるデータ（検索キーワードのビッ
ト）がそれぞれ一致する場合には、トランジスタ４０９
および８０９はオフされるが、少なくともいずれか一方
においてデータが不一致である場合には、トランジスタ
４１０と一致信号線ＭＬとの間にディスチャージ経路が
形成される。
【００８２】ＣＣセル部４５０中のトランジスタ４１０
および４１７は、比較動作制御線ＣＥＬおよび比較条件
信号ＣＮを保持するノードＮｈの電位レベルに応じてそ
れぞれオンオフする。
【００８３】したがって、一旦一致信号線ＭＬがプリチ
ャージされ、ＣＣセル８００に対して比較動作制御線Ｃ
ＥＬによって比較動作の実行が指示された場合において
は、一致信号線ＭＬがディスチャージされずに当初のプ
リチャージレベルを維持するには、トランジスタ４１７
がオフ状態であるか、もしくは、トランジスタ４１７が
オン状態である場合にはトランジスタ４０９および８０
９の両方がオフ状態であることが必要となる。
【００８４】この結果、ノードＮｈに保持された比較条
件信号ＣＮは、比較回路８５０における比較動作の無効
化に対しても有効となり、比較条件信号ＣＮを「偽（Ｈ
レベル）」とした場合には、データ信号線ＫＬ０および
ＫＬ１に対応する２ビットの一致比較結果を無効化する
ことが可能となる。
【００８５】一方、比較条件信号ＣＮの値が「真（Ｈレ
ベル）」である場合には、一致信号線ＭＬが当初のプリ
チャージレベルを維持するためには、データ信号線ＫＬ
０およびＫＬ１に対応する検索キーワードのビットの両
方について、ＣＣセル８００内に保持されるタグデータ
のビットと一致していることが必要となる。
【００８６】このような構成とすることにより、実施の
形態２に従うＣＣセルは、２ビット単位で、検索キーワ
ードとタグデータ間の一致比較結果の有効／無効を指定
することが可能となる。
【００８７】さらに、実施の形態２に従うＣＣセルによ
って、キーワード長の指定を３ビット以上のｊビット
（ｊ：自然数）単位で指定することも可能である。この
場合には、ｎの値に対応して、比較回路８５０に対応す
る回路をビット数に応じて追加する構成とすればよい。
【００８８】［実施の形態２の変形例］実施の形態２の
変形例においては、検索の対象となるキーワード長の指
定を、比較条件信号によってエンコードする構成につい
て説明する。
【００８９】図８は、本発明の実施の形態２の変形例に
従うＣＣセル９００の構成を示す回路図である。
【００９０】図８に示すＣＣセル９００は、一例とし
て、検索キーワードのうちの３ビットについての比較条
件を２ビットの比較条件信号ＣＮ０，ＣＮ１によってエ
ンコードした場合によって示している。
【００９１】図８を参照して、ＣＣセル９００は、比較
回路９５０、９６０および９７０と、比較条件保持回路
９８０および９８５を含む。
【００９２】比較回路９５０、９６０および９７０は、
データ信号線ＫＬ０、ＫＬ１およびＫＬ２に対応してそ
れぞれ設けられる。比較条件保持回路９８０および９８
５は、比較条件入力線ＣＬ０およびＣＬ１に伝達される
比較条件信号ＣＮ０およびＣＮ１をタグワード線ＴＷＬ
の活性化に応じて取込み、ノードＮｙ０およびＮｙ１に
それぞれ保持する。比較回路９５０、９６０および９７
０の比較結果が有効／無効のいずれであるかは、ノード
Ｎｙ０およびＮｙ１の電位レベルの組合せに応じて決定
される。
【００９３】次に、比較回路の構成について説明する。
まず、比較回路９５０の構成を代表的に説明する。比較
回路９５０は、タグワード線ＴＷＬの活性化に応じて、
データ信号線ＫＬ０およびＫＬ０／によって伝達される
データを取込むための書込トランジスタ４０５および４
０６と、書込トランジスタ４０５および４０６によって
取込まれたデータを保持するためのインバータ対を形成
するトランジスタ４０１〜４０４を有する。タグワード
線ＴＷＬの活性化に応答して取込まれたデータ信号線Ｋ
Ｌ０のデータはノードＮｘ０に保持される。
【００９４】比較回路９５０は、さらに、ノードＮｘ０
に保持されるデータとデータ信号線ＫＬ０に伝達される
データとの間の一致を比較するためのトランジスタ４０
７〜４０９をさらに要する。両者のデータが一致する場
合、トランジスタ４０９はオフされ、両者が不一致の場
合にはオンされる。
【００９５】比較回路９５０は、さらに、トランジスタ
４０９と接地ノードとの間に接続され、ノードＮｙ０お
よびノードＮｙ１の電位レベルに応じてそれぞれがオン
オフされるトランジスタ９２１および９２２と、比較動
作制御線ＣＥＬの電位レベルに応じてトランジスタ４０
９と一致信号線ＭＬとの間を接続／遮断するトランジス
タ９２３とをさらに有する。
【００９６】このような構成とすることにより、比較回
路９５０においては、比較条件入力線ＣＥＬの電位レベ
ルがＨレベルに変化して、比較動作が指示された場合に
おいては、データ信号線ＫＬ０のデータとノードＮｘ０
に保持されるデータとが不一致であり、比較条件信号Ｃ
Ｎ０，ＣＮ１のいずれか一方が「真（Ｈレベル）」であ
る場合において、一致信号線ＭＬの電位をディスチャー
ジする経路が形成される。
【００９７】比較回路９６０は、比較回路９５０のトラ
ンジスタ４０１〜４０９と同様の構成を有するトランジ
スタ８０１〜８０９と、トランジスタ８０９と接地ノー
ドとの間に接続されノードＮｙ１と接続されるゲートを
有するトランジスタ９２４と、比較動作制御線ＣＥＬと
接続されるゲートを有しトランジスタ８０９と一致信号
線ＭＬとの間に接続されるトランジスタ９２５とを有す
る。
【００９８】比較回路９６０は、タグワード線ＴＷＬの
活性化に応じて、データ信号線ＫＬ１のデータをノード
Ｎｘ１に取込んで保持するとともに、トランジスタ８０
７〜８０９によって、ノードＮｘ１に保持されるデータ
とデータ信号線ＫＬ１によって伝達されるデータとの間
の一致比較を行なうことができる。
【００９９】このような構成とすることにより、比較回
路９６０においては、比較動作制御線ＣＥＬの電位レベ
ルをＨレベルにすることによって、比較動作を指示した
場合においては、ノードＮｘ１に保持されるデータとデ
ータ信号線ＫＬ１とのデータが不一致であり、かつ比較
条件信号ＣＮ１が「真（Ｈレベル）」である場合におい
て、一致信号線ＭＬのディスチャージ経路が形成され
る。
【０１００】比較回路９７０も類似の構成を有し、タグ
ワード線ＴＷＬの活性化に応じてデータ信号線ＫＬ２か
ら取込んだデータをノードＮｘ２によって保持するとと
もに、ノードＮｘ２に保持されるデータとデータ信号線
ＫＬ２に伝達されるデータとの一致比較を実行する。
【０１０１】比較回路９７０は、さらに、トランジスタ
９０９と接地ノードとの間に直列に接続されるトランジ
スタ９２６および９２７とトランジスタ９０９と一致信
号線ＭＬとの間に接続されるトランジスタ９２８とを有
する。トランジスタ９２６、９２７および９２８のゲー
トは、ノードＮｙ０、ノードＮｙ１および比較動作制御
線ＣＥＬとそれぞれ接続されるので、比較回路９７０に
よって比較動作が実行される場合には、データ信号線Ｋ
Ｌ２のデータとノードＮｘに保持されるデータとが不一
致で、かつ比較条件信号ＣＮ０およびＣＮ１の両方が
「真（Ｈレベル）」である場合において、一致信号線Ｍ
Ｌのディスチャージ経路が形成される。
【０１０２】したがって、比較回路９５０〜９７０にお
ける各ビットのキーワードのビット比較結果の有効／無
効を、比較条件信号ＣＮ０およびＣＮ１の信号レベルを
（ＣＮ０，ＣＮ１）と表記して整理すれば、（０，０）
である場合には、データ信号線ＫＬ０〜ＫＬ２に対応す
る３ビットすべてのキーワード比較が無効であり、
（０，１）である場合には、最左ビットＫＬ０に対応す
るキーワード比較のみが有効であり、（１，０）の場合
には、左から２ビット分のデータ信号線ＫＬ０およびＫ
Ｌ１に対応するキーワード比較が有効であり、（１，
１）の場合には、データ信号線ＫＬ０〜ＫＬ２に対応す
る３ビットすべてに関してキーワード比較が有効である
ということになる。
【０１０３】これにより、比較条件信号ＣＮ０およびＣ
Ｎ１の２ビットの組合せによって、データ信号線ＫＬ０
〜ＫＬ２に対応する３ビットのキーワード比較の一部ま
たは全部の有効／無効を制御することが可能となる。
【０１０４】図８に示したＣＣセル９００においては、
３ビットのうちの真ん中のビット、すなわちデータ信号
線ＫＬ１に関する比較結果のみの有効／無効は指定不可
能である。
【０１０５】しかしながら、後程詳細に説明するよう
に、このような連想メモリを可変長符号の復号に用いる
ことを考えた場合には、キーワード比較は上位ビットか
らＮビット（Ｎ：自然数）で与えられ、この範囲でキー
ワード比較を実行すればよいため、このような指定方法
は必要とされない。
【０１０６】逆に言えば、実施の形態２に従うＣＣセル
９００を適用することによって、可変長符号の復号に用
いられる連想メモリ装置において、検索の対象となるキ
ーワード長の指定を、比較条件信号のエンコードによっ
て効率的に実行できる。
【０１０７】図８においては、３ビット分のキーワード
比較の結果を２ビットの比較条件信号によって有効ある
いは無効とする場合を示したが、同様の手法によって、
Ｉビット（Ｉ：自然数）の比較条件信号によって、２I
−１ビット分のキーワードの比較条件を指定することが
できる。たとえば、７ビット分のキーワードの比較条件
を３ビットの比較条件信号でエンコードすることや、あ
るいは、１５ビット分のキーワードの比較条件を、４ビ
ットの比較条件信号にエンコードすること等が同様に可
能である。
【０１０８】［実施の形態３］実施の形態３において
は、実施の形態１および２で説明した連想メモリ装置を
使用した可変長符号のデコードについて説明する。
【０１０９】ここでは、まず実施の形態１において説明
した連想メモリ装置１００を用いて、図９に示すような
可変長符号方式に従ったデコードを行なう場合を考え
る。
【０１１０】ここでは、連想メモリ装置の大きさは、図
２および図５において、自然数ｎ、ｍおよびｋが、それ
ぞれ８、１５および１５であるとする。
【０１１１】図９を参照して、ここで説明する可変長符
号化方式においては、０〜７の８個のデータが、符号長
１、２、４および６のいずれかを有する可変長符号に符
号化される。
【０１１２】図１０は、図９に従う可変長符号方式に従
うデコードを行なうために、連想メモリ装置１００に記
憶されるべきデータを説明する図である。
【０１１３】図１０においては、書込タグに示すデータ
は２進数表記をしているが、その他のデータについては
１６進数表記としている。また、“？”は、書込まれる
値を問わないということを示している。
【０１１４】図１０を参照して、各書込アドレスに対応
して、キーワード比較部に書込まれる書込タグと、デー
タ格納部に書込まれる書込データの内容とが定められ
る。
【０１１５】タグデータの最上位ビットは、対応する書
込アドレスについて、デコードに使用されるデータが格
納されているか否かを指示するために設けられる。すな
わち、デコードに有効なタグ情報が設定されているアド
レスについてのみデータ信号線ＫＬ０に対応するビット
に“１”を設定してタグデータを書込み、検索データ読
出の際、すなわちデコードを行なう際には、データ信号
線ＫＬ０に“１”が入力されるように検索キーワードを
与えることによって、キーワード比較部内に偶然存在す
る、無効なタグ情報による誤った一致検出を防ぐことが
可能となる。
【０１１６】タグデータの上位２ビット以降に書込まれ
るデータは、図９に示す可変長符号に対応するデータを
上位ビット側から左詰めにしたものであり、各ビットの
データは、データ信号線ＫＬ１〜ＫＬ８によってそれぞ
れ書込まれる。
【０１１７】また、データ信号線ＫＬ２〜ＫＬ８に対応
するビットにおいて、“？”が設定されるビットについ
ては書込まれる値が問われないが、対応する比較条件信
号を制御条件入力線ＣＬ２〜ＣＬ８によって「偽
（０）」と設定して、比較対象から除外することで、キ
ーワード検索を正常に実行できる。
【０１１８】データ格納部においては、可変長符号に対
応する復号データおよび符号長は、書込アドレスによっ
て、タグデータとしてキーワード比較部内に記憶された
可変長符号と対応付けて記録される。
【０１１９】このような場合において、たとえば、以下
のような可変長符号のデコードを一例として説明する。
【０１２０】 “１１０１＿００１０＿１１１１＿１１１１……” このとき、デコードを行なうために連想メモリ装置１０
０に対して１回目から５回目までに与えられる検索キー
ワードおよび検索出力として得られる復号データおよび
符号長は、図１１に示すようになる。
【０１２１】図１１は、連想メモリ装置１００を用いた
可変長符号のデコードを説明する図である。
【０１２２】最初のデコードでは、１回目の検索とし
て、検索キーワードに、可変長符号のデコードを実行す
ることを示すビットおよび可変長符号の先頭の８ビット
からなる“１＿１１０１＿００１０”を入力する。
【０１２３】このような検索キーワードの入力に応答し
て、アドレス“３”において、検索キーワードと格納さ
れたタグデータとの間で一致検出がなされるため、これ
に対応してアドレス“３”に対応する復号データ“３”
および符号長“４”が出力される。また、一致検出制御
部から出力される検索判定結果は、活性化（Ｈレベル）
される。
【０１２４】２回目のデコードにおいては、１回目のデ
コードで得られた符号長４ビットを除外し、第５ビット
目を先頭とする８ビットがデコードの対象となる。よっ
て、２回目のデコードにおいては、検索キーワードとし
て“１＿００１０＿１１１１”が与えられる。
【０１２５】この場合には、アドレス“０”によって検
索キーワードとタグデータとの間の一致が検出され、復
号データ“０”および符号長“１”が得られる。
【０１２６】同様にして、３回目および４回目のデコー
ドを実行すると、５回目のデコードにおいては、検索デ
ータとして“１＿１１１１＿１１１１”が与えられる。
【０１２７】図１０に示されるように、連想メモリ装置
１００は、このようなキーワードに一致するタグ情報を
有していないので、検索判定結果は活性化されない。よ
って、連想メモリ装置の外部より、検索判定結果が活性
化されないことから、与えられた可変長符号がデコード
不能であることを検知でき、誤り回避の措置をとること
が可能となる。
【０１２８】図１２は、連想メモリ装置１００を用い
た、実施の形態３に従う可変長符号装置の復号装置の全
体構成を示す概略ブロック図である。
【０１２９】図１２を参照して、可変長符号復号装置１
０００は、外部から与えられる可変長符号データを一時
的に格納するためのＶＬＣバッファ１０１０と、ＶＬＣ
ポインタ１０４０の指示に応じて、デコードの対象とな
る可変長符号データのビットを検索キーワードとして連
想メモリ１００に与えるＶＬＣ整置回路１０２０と、連
想メモリ１００と、連想メモリ装置１００から出力され
た符号長に応じて、デコードの対象となる可変符号長デ
ータの先頭ビットを指定するためのＶＬＣポインタ１０
４０とを備える。
【０１３０】ＶＬＣバッファ１０１０は、外部から可変
符号長データを受けるとともに、保持しているデータの
ビット数が一定量を下回ると、新たに外部から可変長符
号データを補充する機能を有する。
【０１３１】ＶＬＣポインタ１０４０は、デコード対象
の可変長符号データが、ＶＬＣバッファ１０１０内のど
こに格納されているかを、その先頭ビット位置によって
指定する。ＶＬＣポインタ１０４０は、１回の検索キー
ワードの入力に対応するデコード結果に応答して、連想
メモリ装置１００から出力された符号長のデータに基づ
いて、自らの値を更新する。
【０１３２】ＶＬＣ整置回路１０２０は、ＶＬＣポイン
タ１０４０の指示に応じて、ＶＬＣバッファ１０１０よ
り、デコード対象となる可変符号長データの対象ビット
を左詰にして取出し、さらに、その最左端（すなわち最
上位ビット）に、１ビットのデータ“１”を拡張して連
想メモリ装置１００に与える機能を有する。
【０１３３】連想メモリ装置１００からの出力データに
は、図１０に示されるように、復号データと符号長とが
含まれており、符号長は、ＶＬＣポインタ１０４０に与
えられ、復号データは外部に出力される。
【０１３４】このような構成とすることによって、可変
長符号復号装置１０００は、図９から図１１で説明した
ような、可変長符号化データの復号を実行することがで
きる。
【０１３５】なお、図１２においては、記載の簡略化の
ために、連想メモリ装置１００に対するデータ書込経路
については記載を省略しているが、デコードに先立っ
て、図１０に示したように、書込タグおよび書込データ
を入力すればよい。
【０１３６】また、図１２に示すような可変長復号装置
１０００を、専用のハードウェアとして構成しなくて
も、マイクロプロセッサと連想メモリ装置とを組合せる
ことによっても、同様の可変長データの復号を実行する
ことが可能である。
【０１３７】また、図９および図１０で説明した可変長
符号方式に従う場合においては、ＫＬ３以降について
は、２ビットずつ比較結果の有効／無効を指定すること
ができるので、データ信号線ＫＬ３〜ＫＬ８に対応する
列における比較機能付記憶素子には、図７で説明した実
施の形態２に従うＣＣセル８００を適用することが可能
である。この場合には、比較条件入力線ＣＬ２〜ＣＬ８
によるのと同等の指定を、より少ない配線数で実現する
ことができるとともに、ＣＣセル部のレイアウト面積を
抑制することができる。
【０１３８】また、用いられる可変長符号化の方式によ
って、キーワード比較の有効／無効を、３ビット以上の
単位で設定できる場合にも、図７および図８で説明した
ＣＣセル８００および９００を用いた構成を連想メモリ
装置１００に導入して、可変符号長データ復号装置を構
成することも可能である。
【０１３９】今回開示された実施の形態はすべての点で
例示であって制限的なものではないと考えられるべきで
ある。本発明の範囲は上記した説明ではなくて特許請求
の範囲によって示され、特許請求の範囲と均等の意味お
よび範囲内でのすべての変更が含まれることが意図され
る。
【０１４０】
【発明の効果】請求項１、２、３および９記載の連想メ
モリ装置は、検索データと各タグデータとの間における
各ビットの一致比較に際して、比較結果無効化機能付き
メモリ部に対応するビットにおいては、比較条件信号に
応じて一致比較結果を無効化できる。この結果、検索デ
ータと各タグデータとの間において、一致比較の対象と
なるビット数をソフトウェア的に任意に設定することが
できる。
【０１４１】請求項４記載の連想メモリ装置は、１つの
比較条件信号に応じて、複数ビットの一致比較結果の有
効／無効を指定できるので、請求項１記載の連想メモリ
装置が奏する効果に加えて、一致比較の対象となるビッ
ト数の指定を複数ビットごとに行なえる場合において、
比較結果無効化機能付きメモリ部のハードウェア規模を
抑制することができる。
【０１４２】請求項５および７記載の連想メモリ装置
は、複数ビットからなる比較条件信号の各ビットの信号
レベルの組合せに応じて、１つの比較結果無効化機能付
きメモリ部に対応付けられる複数ビット中における一致
比較結果の有効／無効を指定できる。したがって、請求
項１記載の連想メモリ装置が奏する効果に加えて、比較
結果無効化機能付きメモリ部のハードウェア規模を抑制
することができる。
【０１４３】請求項６記載の連想メモリ装置は、複数ビ
ットからなる比較条件信号の各ビットの信号レベルの組
合せに応じて、１つの比較結果無効化機能付きメモリ部
に対応付けられるｉビット（ｉ：自然数）中における、
第ｌビット（ｌ：ｉ以下の整数）までの一致比較結果の
無効化を指定できるので、請求項５記載の連想メモリ装
置が奏する効果に加えて、たとえば、可変長符号データ
を効率的に記憶することができる。
【０１４４】請求項８記載の連想メモリ装置は、検索デ
ータと一致したタグデータが存在したか否かの情報を独
立して出力するので、請求項１記載の連想メモリ装置が
奏する効果に加えて、検索データと各タグデータ間での
一致比較結果をより直接的に検知することができる。
【０１４５】請求項１０、１１、１２および１３記載の
可変長符号復号装置は、検索データと各タグデータとの
間における各ビットの一致比較に際して、比較結果無効
化機能付きメモリ部に対応するビットにおいては、比較
条件信号に応じて一致比較結果を無効化することが可能
な連想メモリ回路を用いて、可変長符号のデコードを実
行する。したがって、検索データと各タグデータとの間
において、一致比較の対象となるビット数をソフトウェ
ア的に任意に設定して、可変長符号のデコードを効率的
に実行することが可能である。
【０１４６】請求項１４記載の可変長符号復号装置は、
１つの比較条件信号に応じて、複数ビットの一致比較結
果の有効／無効を指定できる連想メモリ回路を備えるの
で、請求項１０記載の可変長符号復号装置が奏する効果
に加えて、可変長符号の符号長が複数ビットごとに異な
る場合において、ハードウェア規模を抑制することがで
きる。
【０１４７】請求項１５および１６記載の可変長符号復
号装置は、複数ビットからなる比較条件信号の各ビット
の信号レベルの組合せに応じて、１つの比較結果無効化
機能付きメモリ部に対応付けられる複数ビットにおける
一致比較結果の有効／無効を指定できる連想メモリ回路
を備えるので、請求項１０記載の可変長符号復号装置が
奏する効果に加えて、ハードウェア規模を抑制すること
ができる。
【０１４８】請求項１７記載の可変長符号復号装置は、
可変長符号の復号を実行する場合に所定レベルに設定さ
れる復号実行ビットを検索データおよびタグデータの一
部に含ませた上で、連想メモリ回路における一致比較を
実行する。したがって、請求項１０記載の可変長符号復
号装置が奏する効果に加えて、連想メモリ回路内に偶然
存在する無効なタグデータによる誤ったデータ検索を防
止することが可能となる。
【０１４９】請求項１８記載の可変長符号復号装置は、
復号実行ビットを検索データおよびタグデータの一部に
含ませた上で、連想メモリ回路における一致比較を実行
し、検索データと一致するタグデータが存在するか否か
の情報を独立して得ることができる。したがって、請求
項１８記載の可変長符号復号装置が奏する効果に加え
て、連想メモリ回路内に偶然存在する無効なタグデータ
による誤ったデータ検索を可変長符号復号装置外部より
直接的に検知することができる。
【図面の簡単な説明】
【図１】 実施の形態１に従う連想メモリ装置１００の
全体構成を示す概略ブロック図である。
【図２】 キーワード比較部１の構成を説明するブロッ
ク図である。
【図３】 ＣＭセルの構成を示す回路図である。
【図４】 ＣＣセルの構成を示す回路図である。
【図５】 データ格納部２の構成を示すブロック図であ
る。
【図６】 ＲＡＭセルの構成を示す回路図である。
【図７】 実施の形態２に従うＣＣセル８００の構成を
示す回路図である。
【図８】 実施の形態２の変形例に従うＣＣセル９００
の構成を示す回路図である。
【図９】 可変長符号方法の一例を説明する図である。
【図１０】 図９の可変長符号方法に基づいたデコード
を行なうために連想メモリ装置１００に格納するデータ
を説明する図である。
【図１１】 図１０に従って連想メモリ装置１００に格
納されたデータに基づいて行なわれる可変長符号データ
のデコードを説明する図である。
【図１２】 本発明の実施の形態３に従う可変長符号復
号装置１０００を説明する概略ブロック図である。
【符号の説明】
１ キーワード比較部、２ データ格納部、１１ タグ
ワード制御部、１２タグワード線制御部、１３ タグア
レイ、１４ 一致検出制御部、２１ データワード制御
部、２２ データワード線制御部、２３ データアレ
イ、２４ センスアンプ回路、８００，９００ ＣＣセ
ル。

Claims (18)

    【特許請求の範囲】
  1. 【請求項１】 複数ビットを有する検索データの入力に
    応じてデータを出力する連想メモリ装置であって、 各々が複数ビットを有する複数のタグデータを保持し、
    入力された前記検索データと前記複数のタグデータの各
    々との間において一致比較を行なうキーワード比較アレ
    イを備え、 前記キーワード比較アレイは、前記複数のタグデータに
    対応してそれぞれ設けられ、前記検索データと前記複数
    のタグデータのうちの対応する１つとを比較する複数の
    一致比較回路を含み、 各複数の一致比較回路は、 対応する前記タグデータのうちのｎビット（ｎ：０以上
    の整数）をそれぞれ保持し、各々が、保持するビットと
    前記検索データの対応するビットとの間で一致比較を実
    行するｎ個の比較機能付きメモリ部と、 対応する前記タグデータのうちの前記ｎビットを除く残
    りのビットを構成する、少なくとも１ビットを有するｍ
    個（ｍ：自然数）のビットグループのそれぞれに対応し
    て設けられる、各々が、対応する前記ビットグループの
    データおよび外部から予め与えられる比較条件信号を保
    持して、前記ビットグループのデータと前記検索データ
    の対応するビットとの間で一致比較を実行するととも
    に、前記比較条件信号に応じて前記一致比較の結果を無
    効化することが可能であるｍ個の比較結果無効化機能付
    きメモリ部とを有し、 前記キーワード比較アレイは、前記複数の一致比較回路
    に対応してそれぞれ設けられる、複数の一致検出信号線
    をさらに含み、 各前記複数の一致検出信号線は、対応する前記一致比較
    回路に含まれる、一致比較の結果が無効化されたｋ個
    （ｋ：０〜ｍの整数）を除く（ｍ−ｋ）個の前記比較結
    果無効化機能付きメモリ部および前記ｎ個の比較機能付
    きメモリ部における、前記一致比較の結果に応じて電位
    レベルが定められ、 各前記複数の一致検出信号線の電位レベルに応答して、
    前記検索データと一致した前記複数のタグデータのうち
    の１つに対応するデータを出力するデータ格納アレイを
    さらに備える、連想メモリ装置。
  2. 【請求項２】 前記キーワード比較アレイは、前記一致
    比較を制御するための一致比較制御部をさらに含み、 前記一致比較制御部は、前記一致比較の実行に先立って
    前記複数の一致検出信号線を第１の電位にプリチャージ
    した後に、前記比較結果無効化機能付メモリ部および前
    記比較機能付きメモリ部の各々に対して前記一致比較の
    実行を指示し、各比較機能付きメモリ部は、前記一致比
    較の実行が指示された場合には、前記検索データと前記
    対応するタグデータとの間において対応するビット同士
    が不一致であるときにおいて、対応する前記一致検出信
    号線を前記第１の電位よりも低い第２の電位を供給する
    電源ノードと結合し、 各前記比較結果無効化機能付メモリ部は、前記一致比較
    の実行が指示された場合には、前記比較条件信号によっ
    て前記一致比較の結果が無効化されておらず、かつ、前
    記検索データと前記対応するタグデータとの間において
    対応するビット同士が不一致であるときにおいて、対応
    する前記一致検出信号線を前記電源ノードと結合する、
    請求項１記載の連想メモリ装置。
  3. 【請求項３】 各前記ビットグループは、１ビットのデ
    ータを有し、 各比較機能付きメモリ部は、 前記対応するタグデータのうちの対応する１ビットのデ
    ータを保持するための第１のメモリ回路と、 対応する前記一致検出信号線と前記電源ノードとの間に
    直列に接続される第１および第２のスイッチ回路とを有
    し、 前記第１のスイッチ回路は、前記一致比較制御部によっ
    て前記一致比較の実行が指示された場合にオンし、 前記第２のスイッチ回路は、前記第１のメモリ回路に保
    持されるデータと、前記検索データの対応するビットの
    データとが不一致であるときにオンし、 各前記比較結果無効化機能付メモリ部は、各前記比較機
    能付きメモリ部の構成に加えて、さらに、 前記比較条件信号を保持するための第２のメモリ回路
    と、 前記第１および第２のスイッチ回路と直列に接続され、
    前記比較条件信号によって前記一致比較の結果が無効化
    されている場合にオフされる第３のスイッチ回路とを有
    する、請求項２記載の連想メモリ装置。
  4. 【請求項４】 各前記ビットグループは、ｉビット
    （ｉ：２以上の自然数）のデータを有し、 各前記比較結果無効化機能付メモリ部は、 前記対応するタグデータのうちの対応するｉビットをそ
    れぞれ保持するためのｉ個の第１のメモリ回路と、 前記比較条件信号を保持するための第２のメモリ回路
    と、 前記一致比較制御部によって前記一致比較の実行が指示
    された場合にオンする第１のスイッチ回路と、 前記ｉ個の第１のメモリ回路にそれぞれ対応して設けら
    れ、各々は、対応する前記第１メモリ回路に保持される
    データと、前記検索データの対応するビットのデータと
    が不一致であるときにオンするｉ個の第２のスイッチ回
    路と、 前記比較条件信号によって前記一致比較の結果が無効化
    されている場合にオフされる第３のスイッチ回路とを有
    し、 前第１および第２のスイッチ回路は、互いに直列に前記
    電源ノードと直列に接続され、 前記ｉ個の第３のスイッチ回路は、前記第１および第２
    のスイッチ回路と対応する前記一致検出信号線との間に
    並列に接続される、請求項２記載の連想メモリ装置。
  5. 【請求項５】 各前記ビットグループは、ｉビット
    （ｉ：３以上の自然数）のデータを有し、 前記比較条件信号は、ｊビット（ｊ：２以上の自然数）
    を有し、 各前記比較結果無効化機能付メモリ部は、 前記比較条件信号のｊビットを保持するための比較条件
    保持回路と、 対応する前記ビットグループの前記ｉビットのデータに
    それぞれ対応する第１番目から第ｉ番目までのデータ比
    較回路とを有し、 各前記データ比較回路は、 前記ｉビットのうちの対応するビットを保持するための
    第１のメモリ回路と、 前記一致比較制御部によって前記一致比較の実行が指示
    された場合にオンする第１のスイッチ回路と、 前記第１メモリ回路に保持されるデータと、前記検索デ
    ータの対応するビットのデータとが不一致であるときに
    オンする第２のスイッチ回路と、 前記一致信号線と前記電源ノードとの間に、前記第１お
    よび前記第２のスイッチ回路と直列に接続される第３の
    スイッチ回路とを有し、 前記比較条件信号のｊビットの組合せに応じて、各デー
    タ比較回路中の前記第３のスイッチ回路はオンオフされ
    る、請求項２記載の連想メモリ装置。
  6. 【請求項６】 前記比較条件信号のｊビットの組合せに
    応じて、第１番目から第ｉ番目までのデータ比較回路の
    うち、第Ｌ番目（Ｌ：ｉ以下の整数）までのデータ比較
    回路において、前記第３のスイッチ回路はオンされる、
    請求項５記載の連想メモリ装置。
  7. 【請求項７】 前記比較条件信号のビット数ｊと、各前
    記ビットグループの有するビット数ｉとの関係は、ｉ＝
    ２j−１で表わされる、請求項５記載の連想メモリ装
    置。
  8. 【請求項８】 前記一致比較制御部は、各前記複数の一
    致検出信号線の電位レベルに応じて、入力された前記検
    索データと一致する前記タグデータが存在したどうかを
    示す検索結果を出力する、請求項２記載の連想メモリ装
    置。
  9. 【請求項９】 前記複数のタグデータおよび前記比較条
    件信号は、予め前記連想メモリ装置外部より入力され
    る、請求項１記載の連想メモリ装置。
  10. 【請求項１０】 可変長符号データの復号を行なう可変
    長符号復号装置であって、 復号の対象として入力される可変長符号データのビット
    列を受けて、１回の復号処理の対象となる一定ビット数
    を含む検索データを出力する検索データ設定回路と、 前記検索データの入力に応じて、前記可変長符号データ
    に対応する復号データおよび前記復号データのビット長
    を示す符号長データとを出力する連想メモリ回路とを備
    え、 前記連想メモリ回路は、 符号化された前記可変長符号データを複数のタグデータ
    の一部ビットとして保持し、入力された前記検索データ
    と前記複数のタグデータの各々との間において一致比較
    を行なうキーワード比較アレイを含み、 前記キーワード比較アレイは、前記複数のタグデータに
    対応してそれぞれ設けられ、前記検索データと前記複数
    のタグデータのうちの対応する１つとを比較する複数の
    一致比較回路を有し、 各複数の一致比較回路は、 対応する前記タグデータを構成する、少なくとも１ビッ
    トを有するｍ個（ｍ：自然数）のビットグループのそれ
    ぞれに対応して設けられるｍ個の比較結果無効化機能付
    きメモリ部を有し、 各前記々比較結果無効化機能付きメモリ部は、対応する
    前記ビットグループのデータおよび外部から予め与えら
    れる比較条件信号を保持して、前記ビットグループのデ
    ータと前記検索データの対応するビットとの間で一致比
    較を実行するとともに、前記比較条件信号に応じて前記
    一致比較の結果を無効化することが可能であるｍ個の比
    較結果無効化機能付きメモリ部とを有し、 前記キーワード比較アレイは、前記複数の一致比較回路
    に対応してそれぞれ設けられる、複数の一致検出信号線
    をさらに有し、 各前記複数の一致検出信号線は、対応する前記一致比較
    回路に含まれる一致比較の結果が無効化されたｋ個
    （ｋ：０〜ｍの整数）を除く（ｍ−ｋ）個の前記比較結
    果無効化機能付きメモリ部における前記一致比較の結果
    に応じて電位レベルが定められ、 前記連想メモリ回路は、各前記複数の一致検出信号線の
    電位レベルに応答して、前記複数のタグデータのうちの
    １つに対応する前記可変長符号データに関する、前記復
    号データおよび前記符号長データを出力するデータ格納
    アレイをさらに含み、 前記符号長データに応じて、検索データ設定回路に対し
    て、前記入力される可変長符号データのビット列のう
    ち、次の１回の復号処理の対象となる先頭ビットを指定
    するための復号対象ポインタ回路をさらに備える、可変
    長符号復号装置。
  11. 【請求項１１】 対応する前記一致比較回路に含まれる
    ｍ個の前記比較結果無効化機能付きメモリ部のうち、前
    記可変長符号データに対応するデータが保持されていな
    い前記比較結果無効化機能付きメモリにおいて、前記一
    致比較の結果は無効化される、請求項１０記載の可変長
    符号復号装置。
  12. 【請求項１２】 前記キーワード比較アレイは、前記一
    致比較を制御するための一致比較制御部をさらに含み、 前記一致比較制御部は、前記一致比較の実行に先立って
    前記複数の一致検出信号線を第１の電位にプリチャージ
    するとともに、前記比較結果無効化機能付メモリ部の各
    々に対して前記一致比較の実行を指示し、 各前記比較結果無効化機能付メモリ部は、前記一致比較
    の実行が指示された場合には、前記比較条件信号によっ
    て前記一致比較の結果が無効化されておらず、かつ、前
    記検索データと前記対応するタグデータとの間において
    対応するビット同士が不一致であるときにおいて、対応
    する前記一致検出信号線を前記第１の電位よりも低い第
    ２の電位を供給する電源ノードと結合する、請求項１０
    記載の可変長符号復号装置。
  13. 【請求項１３】 各前記ビットグループは、１ビットの
    データを有し、 各前記比較結果無効化機能付メモリ部は、 前記対応するタグデータのうちの対応する１ビットのデ
    ータを保持するための第１のメモリ回路と、 前記比較条件信号を保持するための第２のメモリ回路
    と、 対応する前記一致検出信号線と前記電源ノードとの間に
    直列に接続される第１および第２のスイッチ回路とを有
    し、 前記第１のスイッチ回路は、前記一致比較制御部によっ
    て前記一致比較の実行が指示された場合にオンし、 前記第２のスイッチ回路は、前記第１のメモリ回路に保
    持されるデータと、前記検索データの対応するビットの
    データとが不一致であるときにオンし、 前記第１および第２のスイッチ回路と直列に接続され、
    前記比較条件信号によって前記一致比較の結果が無効化
    されている場合にオフされる第３のスイッチ回路をさら
    に有する、請求項１２記載の可変長符号復号装置。
  14. 【請求項１４】 各前記ビットグループは、ｉビット
    （ｉ：２以上の自然数）のデータを有し、 各前記比較結果無効化機能付メモリ部は、 前記対応するタグデータのうちの対応するｉビットをそ
    れぞれ保持するためのｉ個の第１のメモリ回路と、 前記比較条件信号を保持するための第２のメモリ回路
    と、 前記一致比較制御部によって前記一致比較の実行が指示
    された場合にオンする第１のスイッチ回路と、 前記ｉ個の第１のメモリ回路にそれぞれ対応して設けら
    れ、各々は、対応する前記第１メモリ回路に保持される
    データと、前記検索データの対応するビットのデータと
    が不一致であるときにオンするｉ個の第２のスイッチ回
    路と、 前記比較条件信号によって前記一致比較の結果が無効化
    されている場合にオフされる第３のスイッチ回路とを有
    し、 前第１および第２のスイッチ回路は、互いに直列に、前
    記電源ノードと直列に接続され、 前記ｉ個の第３のスイッチ回路は、前記第１および第２
    のスイッチ回路と対応する前記一致検出信号線との間に
    並列に接続される、請求項１２記載の可変長符号復号装
    置。
  15. 【請求項１５】 各前記ビットグループは、ｉビット
    （ｉ：３以上の自然数）のデータを有し、 前記比較条件信号は、ｊビット（ｊ：２以上の自然数）
    を有し、 各前記比較結果無効化機能付メモリ部は、 前記比較条件信号のｊビットを保持するための比較条件
    保持回路と、 対応する前記ビットグループの前記ｉビットのデータに
    それぞれ対応する第１番目から第ｉ番目までのデータ比
    較回路とを有し、 各前記データ比較回路は、 前記ｉビットのうちの対応するビットを保持するための
    第１のメモリ回路と、 前記一致比較制御部によって前記一致比較の実行が指示
    された場合にオンする第１のスイッチ回路と、 前記第１メモリ回路に保持されるデータと、前記検索デ
    ータの対応するビットのデータとが不一致であるときに
    オンする第２のスイッチ回路と、 前記一致信号線と前記電源ノードとの間に、前記第１お
    よび前記第２のスイッチ回路と直列に接続される第３の
    スイッチ回路とを有し、 前記比較条件信号のｊビットの組合せに応じて、各デー
    タ比較回路中の前記第３のスイッチ回路はオンオフされ
    る、請求項１２記載の可変長符号復号装置。
  16. 【請求項１６】 前記比較条件信号のｊビットの組合せ
    に応じて、第１番目から第ｉ番目までのデータ比較回路
    のうち、第Ｌ番目（Ｌ：ｉ以下の整数）までのデータ比
    較回路において、前記第３のスイッチ回路はオンされ
    る、請求項１５記載の可変長符号復号装置。
  17. 【請求項１７】 前記検索データは、復号処理を実行す
    る場合に所定レベルに設定される復号実行ビットを含
    み、 各前記複数の一致比較回路は、内部に前記所定レベルを
    保持して、前記検索データのうちの前記復号実行ビット
    との間で一致比較を実行する比較機能付きメモリ部をさ
    らに有し、 前記キーワード比較アレイは、前記一致比較を制御する
    ための一致比較制御部をさらに含み、 前記一致比較制御部は、前記一致比較の実行に先立って
    前記複数の一致検出信号線を第１の電位にプリチャージ
    した後に、前記比較結果無効化機能付メモリ部および前
    記比較機能付きメモリ部の各々に対して前記一致比較の
    実行を指示し、 各比較機能付きメモリ部は、前記一致比較の実行が指示
    された場合には、前記検索データと前記対応するタグデ
    ータとの間において対応するビット同士が不一致である
    ときにおいて、対応する前記一致検出信号線を前記第１
    の電位よりも低い第２の電位を供給する電源ノードと結
    合し、 各前記比較結果無効化機能付メモリ部は、前記一致比較
    の実行が指示された場合には、前記比較条件信号によっ
    て前記一致比較の結果が無効化されておらず、かつ、前
    記検索データと前記対応するタグデータとの間において
    対応するビット同士が不一致であるときにおいて、対応
    する前記一致検出信号線を前記電源ノードと結合する、
    請求項１０記載の可変長符号復号装置。
  18. 【請求項１８】 前記一致比較制御部は、各前記複数の
    一致検出信号線の電位レベルに応じて、入力された前記
    検索データと一致する前記タグデータが存在したかどう
    かを示す検索結果を出力する、請求項１７記載の可変長
    符号復号装置。
JP36960699A 1999-12-27 1999-12-27 連想メモリ装置およびそれを用いた可変長符号復号装置 Withdrawn JP2001184870A (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP36960699A JP2001184870A (ja) 1999-12-27 1999-12-27 連想メモリ装置およびそれを用いた可変長符号復号装置
US09/621,531 US6389524B1 (en) 1999-12-27 2000-07-21 Decoding device with associative memory permitting variable-length keyword comparisons

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP36960699A JP2001184870A (ja) 1999-12-27 1999-12-27 連想メモリ装置およびそれを用いた可変長符号復号装置

Publications (1)

Publication Number Publication Date
JP2001184870A true JP2001184870A (ja) 2001-07-06

Family

ID=18494866

Family Applications (1)

Application Number Title Priority Date Filing Date
JP36960699A Withdrawn JP2001184870A (ja) 1999-12-27 1999-12-27 連想メモリ装置およびそれを用いた可変長符号復号装置

Country Status (2)

Country Link
US (1) US6389524B1 (ja)
JP (1) JP2001184870A (ja)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2005048267A1 (ja) * 2003-11-12 2005-05-26 Matsushita Electric Industrial Co., Ltd. Ｃａｍ回路及びその出力方法
JP2007142864A (ja) * 2005-11-18 2007-06-07 Mitsubishi Electric Corp テーブル装置、可変長符号化／復号装置、可変長符号化装置及び可変長復号装置
JPWO2008087750A1 (ja) * 2007-01-19 2010-05-06 三菱電機株式会社 テーブル装置、可変長符号化装置、可変長復号装置及び可変長符号化復号装置
JP2010166552A (ja) * 2008-12-17 2010-07-29 Mitsubishi Electric Corp テーブル装置、符号化装置、復号装置および符号化／復号装置

Families Citing this family (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6452823B1 (en) * 2001-01-31 2002-09-17 Motorola, Inc. Non-volatile magnetic cache memory and method of use
US6545906B1 (en) * 2001-10-16 2003-04-08 Motorola, Inc. Method of writing to scalable magnetoresistance random access memory element
US6771525B2 (en) * 2002-05-31 2004-08-03 Mosaid Technologies Incorporated Method and apparatus for performing variable word width searches in a content addressable memory
US7095646B2 (en) * 2002-07-17 2006-08-22 Freescale Semiconductor, Inc. Multi-state magnetoresistance random access cell with improved memory storage density
US6956763B2 (en) * 2003-06-27 2005-10-18 Freescale Semiconductor, Inc. MRAM element and methods for writing the MRAM element
US6967366B2 (en) * 2003-08-25 2005-11-22 Freescale Semiconductor, Inc. Magnetoresistive random access memory with reduced switching field variation
US7129098B2 (en) * 2004-11-24 2006-10-31 Freescale Semiconductor, Inc. Reduced power magnetoresistive random access memory elements
US7477559B2 (en) * 2005-11-01 2009-01-13 Stmicroelectronics S.R.L. Sense amplifier for low-voltage applications
US20090116727A1 (en) * 2006-05-02 2009-05-07 Accretech Usa, Inc. Apparatus and Method for Wafer Edge Defects Detection
US20100002484A1 (en) * 2008-07-07 2010-01-07 Broadcom Corporation Content addressable memory array with an invalidate feature
US9934857B2 (en) * 2016-08-04 2018-04-03 Hewlett Packard Enterprise Development Lp Ternary content addressable memories having a bit cell with memristors and serially connected match-line transistors

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2687004B1 (fr) * 1992-01-31 1994-03-18 France Telecom Architecture de memoire associative.
JP2741836B2 (ja) 1993-02-22 1998-04-22 現代電子産業株式会社 適応型可変長符号器
US5479627A (en) * 1993-09-08 1995-12-26 Sun Microsystems, Inc. Virtual address to physical address translation cache that supports multiple page sizes
US5526504A (en) * 1993-12-15 1996-06-11 Silicon Graphics, Inc. Variable page size translation lookaside buffer
DE19526960A1 (de) * 1994-09-27 1996-03-28 Hewlett Packard Co Eine Übersetzungs-Querzuordnungs-Puffer-Organisation mit variabler Seitengrößenabbildung und Opfer-Cache-Speicherung
US5640526A (en) * 1994-12-21 1997-06-17 International Business Machines Corporation Superscaler instruction pipeline having boundary indentification logic for variable length instructions
JP2836596B2 (ja) 1996-08-02 1998-12-14 日本電気株式会社 連想メモリ
KR100263672B1 (ko) * 1997-05-08 2000-09-01 김영환 가변적인 페이지 크기를 지원하는 어드레스 변환장치
US6014732A (en) * 1997-10-22 2000-01-11 Hewlett-Packard Company Cache memory with reduced access time
US6125441A (en) * 1997-12-18 2000-09-26 Advanced Micro Devices, Inc. Predicting a sequence of variable instruction lengths from previously identified length pattern indexed by an instruction fetch address
US6157980A (en) * 1998-03-23 2000-12-05 International Business Machines Corporation Cache directory addressing scheme for variable cache sizes

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2005048267A1 (ja) * 2003-11-12 2005-05-26 Matsushita Electric Industrial Co., Ltd. Ｃａｍ回路及びその出力方法
US7289345B2 (en) 2003-11-12 2007-10-30 Matsushita Electric Industrial Co., Ltd. CAM circuit and output method thereof
JPWO2005048267A1 (ja) * 2003-11-12 2007-11-29 松下電器産業株式会社 Ｃａｍ回路及びその出力方法
JP4790417B2 (ja) * 2003-11-12 2011-10-12 パナソニック株式会社 Ｃａｍ回路及びその出力方法
JP2007142864A (ja) * 2005-11-18 2007-06-07 Mitsubishi Electric Corp テーブル装置、可変長符号化／復号装置、可変長符号化装置及び可変長復号装置
JPWO2008087750A1 (ja) * 2007-01-19 2010-05-06 三菱電機株式会社 テーブル装置、可変長符号化装置、可変長復号装置及び可変長符号化復号装置
JP4703730B2 (ja) * 2007-01-19 2011-06-15 三菱電機株式会社 テーブル装置、可変長符号化装置、可変長復号装置及び可変長符号化復号装置
US8291150B2 (en) 2007-01-19 2012-10-16 Mitsubishi Electric Corporation Table device, variable length coding apparatus, variable length decoding apparatus, and variable length coding and decoding apparatus
JP2010166552A (ja) * 2008-12-17 2010-07-29 Mitsubishi Electric Corp テーブル装置、符号化装置、復号装置および符号化／復号装置

Also Published As

Publication number Publication date
US6389524B1 (en) 2002-05-14

Similar Documents

Publication Publication Date Title
KR100373849B1 (ko) 어소시어티브 캐시 메모리
US5202969A (en) Single-chip-cache-buffer for selectively writing write-back and exclusively writing data-block portions to main-memory based upon indication of bits and bit-strings respectively
US6081441A (en) Content-addressable memory
US6381673B1 (en) Method and apparatus for performing a read next highest priority match instruction in a content addressable memory device
JP2001184870A (ja) 連想メモリ装置およびそれを用いた可変長符号復号装置
US4567578A (en) Cache memory flush scheme
US7010741B2 (en) Method and circuit for error correction in CAM cells
US4879687A (en) Memory device having valid bit storage units to be reset in batch
US5657291A (en) Multiport register file memory cell configuration for read operation
US4930104A (en) Content-addressed memory
US7606054B2 (en) Cache hit logic of cache memory and processor chip having the same
US6591331B1 (en) Method and apparatus for determining the address of the highest priority matching entry in a segmented content addressable memory device
US6525987B2 (en) Dynamically configured storage array utilizing a split-decoder
JP2000353388A (ja) 内容参照可能メモリの改良
US6868475B2 (en) Content addressable memory having data width extension capability
JPS62264498A (ja) 内容アドレス式メモリ
US5978245A (en) Associative memory device having circuitry for storing a coincidence line output
US6816396B2 (en) Apparatus for detecting multiple hits in a CAMRAM memory array
JPH06333395A (ja) 連想メモリ
US20040223364A1 (en) Content addressable memory architecture providing improved speed
JP2001167585A (ja) 連想記憶装置
US20050083719A1 (en) Semiconductor memory device used for cache memory
KR20030081029A (ko) 반도체 기억 장치
US6614675B1 (en) Pipelined content addressable memory with read only element encoding scheme
JP3187203B2 (ja) 連想記憶回路

Legal Events

Date Code Title Description
A300 Application deemed to be withdrawn because no request for examination was validly filed

Free format text: JAPANESE INTERMEDIATE CODE: A300

Effective date: 20070306