JPH09180468A - 連想記憶装置 - Google Patents

連想記憶装置

Info

Publication number
JPH09180468A
JPH09180468A JP7334743A JP33474395A JPH09180468A JP H09180468 A JPH09180468 A JP H09180468A JP 7334743 A JP7334743 A JP 7334743A JP 33474395 A JP33474395 A JP 33474395A JP H09180468 A JPH09180468 A JP H09180468A
Authority
JP
Japan
Prior art keywords
data
register
stored
search
address
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
JP7334743A
Other languages
English (en)
Inventor
Tomoharu Ichikawa
智治 市川
Yutaka Aoki
裕 青木
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.)
Asahi Kasei Microsystems Co Ltd
Asahi Kasei Microdevices Corp
Original Assignee
Asahi Kasei Microsystems Co Ltd
Asahi Kasei Microdevices 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 Asahi Kasei Microsystems Co Ltd, Asahi Kasei Microdevices Corp filed Critical Asahi Kasei Microsystems Co Ltd
Priority to JP7334743A priority Critical patent/JPH09180468A/ja
Publication of JPH09180468A publication Critical patent/JPH09180468A/ja
Withdrawn legal-status Critical Current

Links

Classifications

    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management

Landscapes

  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Memory System (AREA)

Abstract

(57)【要約】 【課題】大容量の連想記憶装置を高速検索を可能としな
がら低消費電力とする。 【解決手段】メモリセルアレイ２に例えばデータ圧縮ア
ルゴリズムによって構築される動的辞書を表すストリン
グテーブルを検索対象データとしてワード単位で格納
し、このストリングテーブルをΩレジスタ３ａ及びＫレ
ジスタ３ｂに保持された検索データをもとに参照して、
検索データと検索対象データとの一致をワード毎に独立
に検出する一致検出回路を備えた一致検出回路アレイ４
で検出する。このとき、検索範囲限定回路６で、Ωレジ
スタ３ａの値に基づいて検索範囲の先頭位置を決定する
とともにテーブルポインタＴP の値から検索範囲の末尾
を決定し、これを検索動作決定回路５に通知することに
より、この検索動作決定回路５で決定された検索範囲で
一致検出回路アレイの一致検出回路をアクティブ状態に
制御する。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、入力された検索デ
ータに基づいて多数の検索対象データを検索して同一又
は類似のデータの有無を出力する連想記憶装置に係り、
特に検索データに基づいて検索範囲を限定することがで
きる連想記憶装置に関する。
【０００２】
【従来の技術】従来のデータ検索機能を有する連想記憶
装置（ＣＡＭ：Content AddressableMemory）として
は、例えば図９に示す構成のものが提案されている。こ
の従来例は、所定ビット数ｍ（例えばｍ＝３２）のワー
ドデータでなる検索対象データを記憶する所定数ｎ（例
えばｎ＝１２８）のワードデータ記憶部ＷＭ 1 〜ＷＭn
が並列に設けられ、各ワードデータ記憶部ＷＭ1 〜ＷＭ
n にはワードデータを記憶する所定ビット数に対応する
数のメモリセルＭＣ1 〜ＭＣm を有し、これら各メモリ
セルＭＣ1 〜ＭＣm はワード線Ｗ1 〜Ｗn によって活性
化されると共に、記憶データが検索データに対応するワ
ードを表すビット線Ｂ1 〜Ｂmによって読出される。
【０００３】そして、各ビット線Ｂ1 〜Ｂm 及び各ワー
ドデータ記憶部ＷＭ1 〜ＷＭn のメモリセルＭＣ1 〜Ｍ
Ｃm から読出されたビットデータが一致検出回路ＣＣ1
〜ＣＣn に供給されて一致判断が行われる。これら一致
検出回路ＣＣ1 〜ＣＣn は、入力される共通の回路動作
信号線ＳC がアクティブであるときに各ビット線Ｂ1〜
Ｂm 及びメモリセルＭＣ1 〜ＭＣm の一致検出を行い、
ワード内の全てのビット線Ｂ1 〜Ｂm 及びメモリセルＭ
Ｃ1 〜ＭＣm のビットデータが一致したときに一致信号
線Ｃ1 〜Ｃn がアクティブとなる。
【０００４】この構成によれば、予め各ワードデータ記
憶部ＷＭ1 〜ＷＭn に検索対象データを格納しておき、
この状態で、検索を行う場合には、先ず各ワード線Ｗ1
〜Ｗ n をアクティブ状態とすると共に、ビット信号線Ｂ
1 〜Ｂm に検索データの各ビットを設定した状態で、回
路動作信号線ＳC をアクティブ状態とすることにより、
検索データとワードデータ記憶部ＷＭ1 〜ＷＭn に格納
されている検索対象データとが一致した一致検出回路Ｃ
Ｃi （ｉ＝１，２……ｎ）がアクティブ状態となって、
検索対象データから検索データと一致するデータを抽出
することができる。
【０００５】
【発明が解決しようとする課題】しかしながら、上記従
来の連想記憶装置にあっては、各ワードデータ記憶部Ｗ
Ｍ1 〜ＷＭn 毎に一致検出回路ＣＣ1 〜ＣＣn を有する
ので、一度の検索で検索対象データの全ワードを同時に
一致検出することができ、高速検索が可能であるが、全
ての一致検出回路ＣＣ1 〜ＣＣn が同時に動作状態とな
るため、大容量の連想記憶装置においては消費電流が非
常に大きなものとなってしまうという未解決の課題があ
る。
【０００６】そこで、本発明は、上記従来例の未解決の
課題に着目してなされたものであり、高速検索を可能と
しながら低消費電力とすることができる大容量の連想記
憶装置を提供することを目的としている。
【０００７】
【課題を解決するための手段】上記目的を達成するため
に、請求項１に係る連想記憶装置は、入力された検索デ
ータに基づいてメモリセルアレイに格納された多数の検
索対象データを検索して同一又は類似のデータの有無を
出力する連想記憶装置において、前記検索データに基づ
いて検索すべき検索対象データの存在する範囲を限定す
る検索範囲限定手段と、該検索範囲限定手段で限定され
た範囲内で前記検索対象データを検索するデータ検索手
段とを備えたことを特徴としている。
【０００８】この請求項１の発明においては、検索範囲
限定手段で検索データに基づいて検索対象データの存在
する範囲を限定し、この限定された範囲内についてのみ
データ検索手段で検索することにより、このデータ検索
手段に含まれる一致検出回路の動作数を限定して省電力
化を図る。また、請求項２に係る連想記憶装置は、請求
項１の発明において、前記メモリセルアレイには、デー
タ圧縮アルゴリズムによって検索データに対して過去の
文字列に専用のアドレスを割当てて辞書形式で登録され
る動的辞書が格納されていることを特徴としている。
【０００９】この請求項２の発明においては、データ圧
縮アルゴリズムでは動的辞書をメモリセルアレイに格納
してゆくので、検索するデータが存在する範囲を予め限
定することができ、簡単な構成で検索範囲の限定を正確
に行うことができる。
【００１０】
【発明の実施の形態】以下、本発明の実施形態を図面に
基づいて説明する。図１は本発明の一実施形態を示すブ
ロック図である。図中、１は連想記憶装置であって、検
索対象データを検索単位であるワード単位で例えば１０
ワード分を格納したメモリセルアレイ２と、検索データ
を保持するΩレジスタ３ａ及びＫレジスタ３ｂと、メモ
リセルアレイ２のワード毎に検索対象データと検索デー
タとの一致を各ワード毎に独立に検出する一致検出回路
ＣＣ1 〜ＣＣn を備えた一致検出回路アレイ４と、この
一致検出回路アレイ４の各一致検出回路ＣＣ1 〜ＣＣ n
のうち所定の範囲を一致検出動作信号ＳC1〜ＳCnによっ
て動作状態とする検索動作決定回路５と、前記Ωレジス
タ３ａの値から検索範囲の先頭位置を決定すると共に、
テーブルポインタＴP の値から検索範囲の末尾位置を決
定して検索動作決定回路５に通知する検索範囲限定手段
としての検索範囲限定回路６とを備えている。
【００１１】次に、上記連想記憶装置を使用するデータ
圧縮アルゴリズムの１つであるＤＣＬＺ（Data Compres
sion Limpel Ziv ）アルゴリズム処理を図２を伴って説
明する。このＤＣＬＺアルゴリズムでは、検索データに
対して過去の文字列に専用のコードを割当てて辞書形式
で登録する動的辞書を作成するようにしている。この処
理は、先ずステップＳ１で、ストリングテーブルの初期
化を行う。この初期化は、入力される全てのシングルバ
イトストリング（非圧縮データバイト）をメモリに記憶
する。このとき、各データが記憶されているアドレスを
エントリーアドレスＡＤＤと称す。
【００１２】次いで、ステップＳ２に移行して、非圧縮
データの最初の入力バイトのエントリーアドレスＡＤＤ
をΩレジスタ３ａに格納する。次いで、ステップＳ３に
移行して、現在の非圧縮データの入力バイトに続く入力
バイトが存在するか否かを判定する。ここで、続く入力
バイトが存在しないときには、ステップＳ４に移行して
最終ストリングを表すコードを出力して処理を終了し、
続く入力バイトが存在する場合には、ステップＳ５に移
行する。
【００１３】このステップＳ５では、続く入力バイトを
Ｋレジスタ３ｂに格納してからステップＳ６に移行し、
ストリングΩＫがストリングテーブルに存在するか否か
を判定する。この判定は、検索データΩＫと検索対象デ
ータとの一致検出を行うもので、一致するデータが存在
しない場合は、ステップＳ７に移行してΩレジスタ３ａ
に格納されているエントリーアドレスＡＤＤを出力し、
次いでステップＳ８に移行して新たにストリングΩＫを
ストリングテーブルに追加する。つまり、ストリングΩ
Ｋが新たな記憶データとなる。また、このとき出力され
るエントリーアドレスＡＤＤが、圧縮データとなる。
【００１４】次いで、ステップＳ９に移行して、Ｋレジ
スタに格納されている入力バイトのエントリーアドレス
ＡＤＤをΩレジスタ３ａに入力してからステップＳ３に
戻る。一方、ステップＳ６の判定結果が、ストリングΩ
Ｋと一致するデータが存在するものであるときには、ス
テップＳ１０に移行して、ストリングΩＫのエントリー
アドレスＡＤＤをΩレジスタ３ａに格納してから前記ス
テップＳ３に戻る。
【００１５】以上のようなＤＣＬＺアルゴリズム処理を
使用して文字データの圧縮を行う場合を図３について説
明する。この図３では、ａ，ｂ，ｃの３文字で構成され
た文字列「ａｂｃａｂｃａｃａｃｂ」をデータ圧縮する
場合を説明する。ここで、図３（ａ）は、入力バイト、
Ｋレジスタ及びΩレジスタ、出力コードの内容を夫々表
し、図３（ｂ）はメモリセルアレイ２に構築される辞書
の内容がアドレスに対してＫレジスタの内容及びΩレジ
スタの内容とが対応付けられて表されている。
【００１６】先ず、図２の処理が実行開始されると、先
ずステップＳ１で辞書の初期化が行われ、図３（ｂ）に
示すように、アドレス“１”に対応するＫ記憶領域に
「ａ」、アドレス“２”に対応するＫ記憶領域に「ｂ」
及びアドレス“３”に対応するＫ記憶領域に「ｃ」が夫
々格納され、Ω記憶領域にはなにも格納されない。次い
でステップＳ２に移行して、先頭の入力バイト「ａ」に
対応する辞書のアドレス“１”がΩレジスタに書込まれ
る。
【００１７】次いで、続く入力バイト「ｂ」が存在する
ので、ステップＳ３からステップＳ５に移行して、入力
バイト「ｂ」をＫレジスタに書込み、次いでステップＳ
６に移行して両レジスタに書込まれたデータ「ｂ，１」
が辞書内にあるか否かを判定し、辞書内に存在しないの
で、ステップＳ７に移行して、Ωレジスタのアドレスデ
ータ「１」を出力コードとして出力し、次いでステップ
Ｓ８で辞書の終端即ちアドレス“４”に対応するＫ記憶
領域に「ｂ」をΩ記憶領域に「１」を夫々格納し、次い
でステップＳ９でＫレジスタの内容「ｂ」に対応する辞
書のアドレス“２”をΩレジスタ３ａに格納してからス
テップＳ３に戻る。
【００１８】ここで、続く入力バイト「ｃ」が存在する
ことにより、前記と同様にステップＳ５に移行して、入
力バイト「ｃ」をＫレジスタに書込み、次いでステップ
Ｓ６に移行して、両レジスタに書込まれている「ｃ，
２」が辞書内に存在するか否かを判定し、この場合も辞
書内に「ｃ，２」が存在しないので、ステップＳ７に移
行して、Ωレジスタの内容“２”を出力コードとして出
力し、次いでステップＳ８に移行して辞書のアドレス
“５”に対応するＫ記憶領域に「ｃ」を、Ω記憶領域に
「２」を夫々記憶し、次いでステップＳ９に移行してＫ
レジスタの内容「ｃ」に対応する辞書のアドレス“３”
をΩレジスタに格納してから前記ステップＳ３に戻る。
【００１９】このステップＳ３でも、続く入力バイト
「ａ」が存在することにより、これをＫレジスタに格納
し、且つ「ａ，３」が辞書に存在しないことにより、こ
れを辞書のアドレス“６”に格納し、“３”を出力コー
ドとして出力し、Ｋレジスタに格納されている「ａ」に
対応する辞書のアドレス“１”をΩレジスタに格納して
からステップＳ３に戻る。
【００２０】この場合も続く入力バイト「ｂ」が存在す
ることから、これをＫレジスタに格納し、「ｂ，１」が
辞書に格納されているか否かを判定する。この場合に
は、辞書のアドレス“４”に「ｂ，１」が格納されてい
るので、ステップＳ１０に移行して、アドレス“４”を
Ωレジスタに格納してからステップＳ３に戻る。ここで
も、続く入力バイト「ｃ」が存在するので、これをＫレ
ジスタに格納すると共に、「ｃ，４」が辞書にないの
で、“４”を出力コードとして出力すると共に、辞書の
アドレス“７”に「ｃ，４」を格納し、且つＫレジスタ
の内容「ｃ」に対応するアドレス“３”をΩレジスタに
格納してからステップＳ３に戻る。
【００２１】このように順次図２の処理を繰り返すこと
により、図３（ａ）に示すように出力コードが出力され
ると共に、図３（ｂ）に示すように辞書が構築される。
以上のようなＤＣＬＺアルゴリズム処理の動作を図４〜
図６を用いて簡単に説明する。これらの図４〜図６で
は、Ωレジスタ３ａ及びＫレジスタ３ｂに検索データを
保持すると共に、ストリングテーブルＳＴに検索対象デ
ータを配置し、Ωレジスタ３ａ及びＫレジスタ３ｂに保
持された検索データと完全に一致するものがストリング
テーブルＳＴ中に存在するか否かを調べることを検索と
いう。
【００２２】図４〜図６の例では、メモリセルアレイ２
には、アドレスとして“０”からＡＤＤMAX までが設定
され、テーブルポインタ(Table Ptr) はストリングテー
ブルＳＴの構築範囲の次の書込アドレスＡW 又はＡW+1
即ち未構築範囲の先頭アドレスを常に示しており、さら
にメモリセルアレイ２のストリングテーブル構築範囲内
におけるアドレスＡＤＤ1 にはデータΩ1 及びＫ1 が既
に書込まれているものとする。
【００２３】そして、先ず図４に示すように、Ωレジス
タ３ａにデータΩ1 が設定され、Ｋレジスタ３ｂにデー
タＫ1 が設定されると、これらデータΩ1 及びＫ1 の組
をストリングテーブルＳＴ上で検索する（ステップＳ
６）。このとき、ストリングテーブルＳＴのアドレスＡ
ＤＤ1 に既にデータΩ1 及びＫ1 の組が書込まれている
ので、検索データと検索対象データの一致を検出するこ
とができる。
【００２４】このように一致が検出されたときには、ス
トリングテーブルＳＴに新たなデータは追加されないの
で、テーブルポインタＴP の指すアドレスは変化せずそ
のまま維持される。そして、検索データに一致する検索
対象データが検出されると、図５に示すように、該当す
る検索対象データのアドレスＡＤＤ1 がΩレジスタ３ａ
に設定され（ステップＳ１０）、次いで後続の入力デー
タがあるか否かを判定し、後続入力データとしてデータ
Ｋ2 があるときには、このデータＫ2 がＫレジスタ３ｂ
に設定される（ステップＳ５）。
【００２５】そして、Ωレジスタ３ａ及びＫレジスタ３
ｂに設定されたアドレスＡＤＤ1 及びデータＫ2 の組を
ストリングテーブルＳＴ上で検索するが、このデータＡ
ＤＤ 1 及びＫ2 の組はストリングテーブルＳＴ上に存在
しない。そこで、図６に示すように、ストリングテーブ
ルＳＴに新たなデータを追加する。具体的には、テーブ
ルポインタＴP の指すストリングテーブルの未構築領域
の先頭アドレスＡW にデータＡＤＤ1 及びＫ2 を書込
み、テーブルポインタＴPの指すアドレスを１つ増加さ
せてアドレスＡW ＋１に更新する（ステップＳ８）。次
いで、Ｋレジスタ３ｂに格納されているデータＫ2 のエ
ントリーアドレスＡＤＤ2 をΩレジスタ３ａに設定し、
次の入力データＫ3 をＫレジスタ３ｂに設定する。
【００２６】以上のようにΩレジスタ３ａ及びＫレジス
タにデータが設定される毎にストリングテーブルを検索
して一致の検出を繰り返す。このように、例えばデータ
ＡＤＤ1 及びＫ2 をストリングテーブルＳＴ内で検索し
たときに一致するデータが存在しない場合には、図６の
ようにアドレスＡＤＤ1 以降にデータＡＤＤ1 及びＫ2
が書込まれることになり、再度同じデータを検索した場
合に一致データが存在する場所は図６で示されるように
アドレスＡＤＤ1 以降にしか存在しない。これを一般的
に表現すると、Ωレジスタ３ａ及びＫレジスタ３ｂに設
定されたデータΩ及びＫを検索する場合、そのデータは
アドレスΩ以降にしか存在しない。つまり検索されるデ
ータ自身によって、検索データの存在範囲を限定するこ
とができる。
【００２７】また、メモリセルアレイ２上にストリング
テーブルが構築されていない部分は、データ検索の対象
とする必要がないことは明らかであり、この部分はデー
タの検索対象から外すことができる。したがって、検索
範囲限定回路６では、Ωレジスタ３ａに書込まれるアド
レスに基づいてメモリセルアレイ２の検索を開始する先
頭アドレスを決定すると共に、テーブルポインタＴP の
指すアドレスを検索末尾アドレスとして選定し、これら
の範囲内を検索範囲として限定する。
【００２８】次に、上記実施形態の動作を説明する。
今、図１に示すように、メモリセルアレイ１の記憶容量
が例えば１０ワードであって、その内７ワードがストリ
ングテーブルとして既に構築されており、Ωレジスタ３
ａ及びＫレジスタ３ｂに夫々検索するデータはΩx （＝
３）及びＫX が格納され、テーブルポインタＴP がアド
レス８を示しているものとする。
【００２９】この状態では、Ωレジスタ３ａに格納され
た検出するデータΩX が検索範囲限定回路６に入力され
ることにより、この検索範囲限定回路６で、検索範囲を
現在のΩレジスタ３ａに格納されている検出するデータ
ΩX の属するアドレス“３”以降のアドレス“４”から
現在テーブルポインタＴP が示しているアドレス“８”
までの範囲を検索範囲として限定する。
【００３０】そして、検索範囲限定回路６で限定された
アドレス“４”からアドレス“８”を選択するために、
検索動作決定回路５に通知する。このため、検索動作決
定回路５では、一致検出動作信号Ｓ4 〜Ｓ8 をアクティ
ブ状態としてこれに対応する各一致検出回路ＣＣ4 〜Ｃ
Ｃ8 を動作状態とする。このように、メモリセルアレイ
１の検索対象ワードを格納した格納ワード領域１０の内
４つのワード格納領域にのみ検索すればよく、検索範囲
を制限しない場合に比較して４／１０だけ一致検出回路
を動作させればよいので消費電力を削減することができ
る。
【００３１】なお、上記実施形態においては、一致検出
動作信号ＳC1〜ＳCnで一致検出回路アレイ４を構成する
ワード単位の一致検出回路をアクティブとする場合につ
いて説明したが、これに限定されるものではなく、ワー
ドを適当な大きさにまとめたセグメント単位で与えるよ
うにすれば、消費電力の削減効果は低減するが、回路規
模を小さくする構造にすることも可能である。
【００３２】なお、上記実施形態における図２のデータ
圧縮を行うＤＣＬＺアルゴリズムによって圧縮された圧
縮データを伸張するには、図７に示すようなデータ伸張
アルゴリズムを適用することが好ましい。このデータ伸
張アルゴリズムは、先ずステップＳ２１でストリングテ
ーブルの初期化を行って、アドレス“１”，“２”及び
“３”のＫ格納領域に夫々データ“ａ”，“ｂ”及び
“ｃ”を格納すると共に、テーブルポインタをアドレス
“４”に設定し、次いでステップＳ２２に移行して、最
初の入力コードをＯＬＤＣＯＤＥレジスタに格納する。
【００３３】次いでステップＳ２３に移行してストリン
グテーブルのＯＬＤＣＯＤＥレジスタに格納されている
コードに対応するアドレスのＫ格納領域のデータをＫレ
ジスタ及びストリングテーブルのＣＯＤＥレジスタに格
納されているコードに対応するアドレスにおけるΩ格納
領域及びＫ格納領域にデータが格納されていないときの
先頭シンボルデータを表すＦレジスタに格納する。
【００３４】次いで、ステップＳ２４に移行して、Ｋレ
ジスタの値を出力してからステップＳ２５に移行する。
このステップＳ２５では、後続する有為な入力コードが
存在するか否かを判定し、後続する入力コードがない場
合にはデータ伸張処理を終了し、後続する入力コードが
ある場合には、ステップＳ２６に移行する。
【００３５】このステップＳ２６では、入力コードをＣ
ＯＤＥレジスタ及びＩＮＣＯＤＥレジスタに格納し、次
いでステップＳ２７に移行して、ストリングテーブルの
ＣＯＤＥレジスタに格納されているコードに対応するア
ドレスにおけるΩ格納領域及びＫ格納領域にデータが格
納されているか否かを判定し、該当するデータが格納さ
れていないときには、ステップＳ２８に移行して、Ｆレ
ジスタに格納されているデータをＬＩＦＯ(Last-in,Fir
st-out) メモリに格納し、次いでステップＳ２９に移行
してＯＬＤＣＯＤＥレジスタに格納されているコードを
ＣＯＤＥレジスタに格納してからステップＳ３０に移行
する。
【００３６】ステップＳ３０では、ストリングテーブル
のＣＯＤＥレジスタに格納されているコードに対応する
アドレスのΩ格納領域が空状態ではないか即ちデータが
格納されているか否かを判定し、データが格納されてい
るときにはステップＳ３１に移行する。このステップＳ
３１では、ストリングテーブルのＣＯＤＥレジスタに格
納されているコードに対応するアドレスのＫ格納領域の
値をＫレジスタに格納し、次いでステップＳ３２に移行
して、Ｋレジスタの値を前記ＬＩＦＯメモリに格納し、
次いでステップＳ３３に移行して、ストリングテーブル
のＣＯＤＥレジスタに格納されているコードに対応する
Ω格納領域の値をＣＯＤＥレジスタに格納してから前記
ステップＳ３０に戻る。
【００３７】一方、ステップＳ３０の判定結果が、スト
リングテーブルのＣＯＤＥレジスタに格納されているコ
ードに対応するアドレスのΩ格納領域が空き状態である
ときには、ステップＳ３４に移行して、ストリングテー
ブルのＣＯＤＥレジスタに格納されているコードに対応
するアドレスのＫ格納領域の値をＫレジスタに格納し、
次いでステップＳ３５に移行して、Ｋレジスタの値をＬ
ＩＦＯメモリに格納し、次いでステップＳ３６に移行し
て、Ｋレジスタの値をＦレジスタに格納してからステッ
プＳ３７に移行する。
【００３８】このステップＳ３７では、ＬＩＦＯメモリ
に格納されているデータがあるか否かを判定し、格納デ
ータがあるときには、ステップＳ３８に移行して、最新
の格納データを読出して出力してからステップＳ３７に
戻り、ＬＩＦＯメモリに格納されているデータが無いと
きにはステップＳ３９に移行する。このステップＳ３９
では、ＯＬＤＣＯＤＥレジスタに格納されているコード
及びＫレジスタに格納されているデータを夫々ストリン
グテーブルにおけるテーブルポインタで指示されている
アドレスのΩ格納領域及びＫ格納領域に夫々登録した後
テーブルポインタを１つ歩進させ、次いでステップＳ４
０に移行してＩＮＣＯＤＥレジスタの値をＯＬＤＣＯＤ
Ｅレジスタに格納してから前記ステップＳ２５に戻る。
【００３９】このデータ伸張アルゴリズムを使用して前
述したデータ圧縮アルゴリズムで圧縮したデータ「１，
２，３，４，６，８」を伸張する場合を図８を伴って説
明する。ここで、図８（ａ）は入力コードに対する内部
レジスタ及び出力バイトの関係を示しており、図８
（ｂ）はメモリセルアレイ２に構築される動的辞書であ
るストリングテーブルのアドレスに対するΩ格納領域及
びＫ格納領域の内容の関係を示している。
【００４０】先ず初期化によってストリングテーブルに
図８（ｂ）に示すようにアドレス１〜３に対応するＫ格
納領域に夫々“ａ”〜“ｃ”を書込むと共に、Ω格納領
域は空き状態(null)とし、さらにテーブルポインタをア
ドレス“４”に設定する（ステップＳ２１）。次いで、
最初の入力コード“１”を、図８（ａ）に示すように、
ＯＬＤＣＯＤＥレジスタに格納すると共に、ストリング
テーブルのＯＬＤＣＯＤＥレジスタに格納された入力コ
ードに対応するアドレス“１”におけるＫ格納領域に格
納されているデータ“ａ”をＫレジスタ及びＦレジスタ
に格納し、且つＫレジスタに格納されたデータ“ａ”を
出力する（ステップＳ２２〜Ｓ２４）。
【００４１】そして、後続の入力コードとして“２”が
存在するので、ステップＳ２５からステップＳ２６に移
行して、入力コード“２”を夫々ＣＯＤＥレジスタ及び
ＩＮＣＯＤＥレジスタに格納し、次いでストリングテー
ブルのＣＯＤＥレジスタに格納された入力コード“２”
に対応するアドレス“２”にはデータ“ｂ”が格納され
ているので、直接ステップＳ３０に移行する。
【００４２】このとき、ストリングテーブルのＣＯＤＥ
レジスタに格納されている入力コード“２”に対応する
アドレス“２”のΩ格納領域が空であるので、ステップ
Ｓ３０からステップＳ３４に移行し、ストリングテーブ
ルにおけるアドレス“２”のＫ格納領域のデータ“ｂ”
をＫレジスタに格納し、次いでＫレジスタの値をＬＩＦ
Ｏメモリ及びＦレジスタに格納する。
【００４３】そして、ステップＳ３７の判定でＬＩＦＯ
メモリがデータが格納されていると判断されるので、ス
テップＳ３８に移行して、ＬＩＦＯメモリからデータ
“ｂ”を取出し、これを出力してからステップＳ３７に
戻る。このとき、ＬＩＦＯメモリからデータ“ｂ”を取
出したことにより、このＬＩＦＯメモリが空となるの
で、ステップＳ３９に移行して、ＯＬＤＣＯＤＥレジス
タに格納されている入力コード“１”とＫレジスタに格
納されているデータ“ｂ”とを夫々テーブルポインタで
指示されるアドレス“４”のΩ格納領域及びＫ格納領域
に記憶し、且つテーブルポインタをアドレス“５”に更
新する。
【００４４】次いで、ＩＮＣＯＤＥレジスタに格納され
ている入力コード“２”をＯＬＤＣＯＤＥレジスタに格
納してからステップＳ２５に戻る。そして、後続入力コ
ードとして“３”が存在するので、これをＣＯＤＥレジ
スタ及びＩＮＣＯＤＥレジスタに格納し、ＣＯＤＥレジ
スタに格納されている入力コード“３”に対応するスト
リングテーブルにおけるアドレス“３”にデータが格納
されており、そのΩ格納領域が空であるので、前述と同
様にステップＳ３０からステップＳ３４に移行してスト
リングテーブルにおけるＣＯＤＥレジスタに格納されて
いるコード“３”に対応するアドレス“３”のＫ格納領
域のデータ“ｃ”をＫレジスタに格納し、このＫレジス
タに格納したデータ“ｃ”をＬＩＦＯメモリに格納し、
これを取出して出力してから、ＯＬＤＣＯＤＥレジスタ
に格納されている入力コード“２”及びＫレジスタに格
納されているデータ“ｃ”をストリングテーブルのテー
ブルポインタで指示されているアドレス“５”のΩ格納
領域及びＫ格納領域に格納し、次いでＩＮＣＯＤＥレジ
スタに格納されている入力コード“３”をＯＬＤＣＯＤ
Ｅレジスタに格納してから前記ステップＳ２５に戻る。
【００４５】そして、後続する入力コード“４”が存在
するので、この入力コード“４”をＣＯＤＥレジスタ及
びＩＮＣＯＤＥレジスタに格納し、ストリングテーブル
のＣＯＤＥレジスタに格納されたコード“４”に対応す
るアドレス“４”にデータが格納されており、そのΩ格
納領域にコード“１”が格納されているので、ステップ
Ｓ３０からステップＳ３１に移行し、アドレス“４”の
Ｋ格納領域に格納されているデータ“ｂ”をＫレジスタ
に格納し、このＫレジスタに格納したデータ“ｂ”をＬ
ＩＦＯメモリに格納し、アドレス“４”のΩ格納領域の
コード“１”をＣＯＤＥレジスタに格納してからステッ
プＳ３０に戻る。
【００４６】このとき、ＣＯＤＥレジスタに格納されて
いるコード“１”に対応するストリングテーブルのアド
レス“１”ではΩ格納領域が空であるので、ステップＳ
３０を経てステップＳ３４に移行し、アドレス“１”の
Ｋ格納領域に格納されているデータ“ａ”をＫレジスタ
に格納すると共に、このデータ“ａ”をＬＩＦＯメモリ
及びＦレジスタに格納する。ここで、ＬＩＦＯメモリに
は、前回の処理時におけるデータ“ｂ”に続いてデータ
“ａ”が格納されることになる。
【００４７】このため、ステップＳ３７からステップＳ
３８に移行して、先ずＬＩＦＯメモリから先ず後から格
納したデータ“ａ”を取出して出力し、次いでデータ
“ｂ”を取出して出力する。そして、ＬＩＦＯメモリか
らのデータ取出しが終了して空の状態となると、ステッ
プＳ３９に移行して、ＯＬＤＣＯＤＥレジスタに格納さ
れている入力コード“３”及びＫレジスタに格納されて
いるデータ“ａ”をストリングテーブルのテーブルポイ
ンタで指示されているアドレス“６”のΩ格納領域及び
Ｋ格納領域に格納し、次いでＩＮＣＯＤＥレジスタに格
納されている入力コード“４”をＯＬＤＣＯＤＥレジス
タに格納してから前記ステップＳ２５に戻る。
【００４８】このとき、後続する入力コード“６”が存
在するので、これがＣＯＤＥレジスタ及びＩＮＣＯＤＥ
レジスタに格納され、ストリングテーブルのＣＯＤＥレ
ジスタに格納されたコード“６”に対応するアドレス
“６”にデータが格納されており、そのΩ格納領域が空
でないので、ステップＳ２７，Ｓ３０を経てステップＳ
３１に移行し、ＣＯＤＥレジスタに格納されているコー
ド“６”に対応するアドレス“６”のＫ格納領域のデー
タ“ａ”をＫレジスタに格納し、続いてこのＫレジスタ
に格納されたデータ“ａ”をＬＩＦＯメモリに格納し、
次いでアドレス“６”のΩ格納領域に格納されているコ
ード“３”をＣＯＤＥレジスタに格納してからステップ
Ｓ３０に戻る。
【００４９】このとき、ＣＯＤＥレジスタに格納されて
いるコード“３”に対応するストリングテーブルのアド
レス“３”にはＫ格納領域にデータ“ｃ”が存在するこ
とにより、このデータ“ｃ”をＫレジスタに格納し、こ
のＫレジスタに格納されたデータ“ｃ”をＬＩＦＯメモ
リ及びＦレジスタに格納してから、ＬＩＦＯメモリから
データ“ｃ”及び“ａ”をその順に取出してこれらを出
力する。
【００５０】次いで、ＯＬＤＣＯＤＥレジスタに格納さ
れているコード“４”及びＫレジスタに格納されている
データ“ｃ”を夫々ストリングテーブルのテーブルポイ
ンタで指示されているアドレス“７”のΩ格納領域及び
Ｋ格納領域に登録すると共に、テーブルポインタを
“８”に更新し、次いでＩＮＣＯＤＥレジスタに格納さ
れているコード“６”をＯＬＤＣＯＤＥレジスタに格納
してから前記ステップＳ２５に戻る。
【００５１】このとき、続いて入力コード“８”が存在
するので、この入力コード“８”をＣＯＤＥレジスタ及
びＩＮＣＯＤＥレジスタに格納する。ここで、ＣＯＤＥ
レジスタに格納されたコード“８”に対応するストリン
グテーブルのアドレス“８”には未だデータが格納され
ていないので、ステップＳ２７からステップＳ２８に移
行し、Ｆレジスタに格納されているデータ“ｃ”をＬＩ
ＦＯメモリに格納し、次いでＯＬＤＣＯＤＥレジスタに
格納されているコード“６”をＣＯＤＥレジスタに格納
してからステップＳ３０に移行する。
【００５２】ここで、ＣＯＤＥレジスタに格納されたコ
ード“６”に対応するストリングテーブルのアドレス
“６”におけるΩ格納領域にコード“３”が格納されて
おり空ではないので、ステップＳ３１に移行し、アドレ
ス“６”のＫ格納領域のデータ“ａ”をＫレジスタに格
納し、次いでデータ“ａ”をＬＩＦＯメモリに前記デー
タ“ｃ”の後に格納し、次いでアドレス“６”のΩ格納
領域に格納されているコード“３”をＣＯＤＥレジスタ
に格納してから前記ステップＳ３０に戻る。
【００５３】このとき、ＣＯＤＥレジスタに格納された
コード“３”に対応するストリングテーブルのアドレス
“３”はΩ格納領域が空であるので、ステップＳ３０か
らステップＳ３４に移行して、アドレス“３”のＫ格納
領域のデータ“ｃ”をＫレジスタに格納し、このＫレジ
スタのデータ“ｃ”をＬＩＦＯメモリ及びＦレジスタに
格納する。
【００５４】このとき、ＬＩＦＯレジスタには、
“ｃ”、“ａ”、“ｃ”がその順に格納されているの
で、これらが新しいものから順に取出されて、これらが
出力され、ＬＩＦＯレジスタが空になると、ステップＳ
３９に移行して、ＯＬＤＣＯＤＥレジスタに格納されて
いるコード“６”及びＫレジスタに格納されているデー
タ“ｃ”をストリングテーブルのテーブルポインタで指
示されているアドレス“８”に登録すると共に、テーブ
ルポインタをアドレス“９”に更新してからステップＳ
２５に戻る。
【００５５】このとき、後続の入力コードが存在しない
ため、データ伸張処理を終了する。この結果、出力は
「ａ，ｂ，ｃ，ａ，ｂ，ｃ，ａ，ｃ，ａ，ｃ」となり、
データ圧縮時の入力データに対して最後のデータ“ｂ”
を除く全てが正確に復号化される。したがって、最後の
データ“ｂ”を圧縮データに付加しておくことにより、
データの復号を正確に行うことができる。
【００５６】なお、上記実施形態においては、ＤＣＬＺ
アルゴリズムを実現する場合について説明したが、これ
に限定されるものではなく、例えばアルファベット順に
構築された辞書の検索にも利用することができる。すな
わち、予めメモリセルアレイ１のアドレス順にアルファ
ベット順のワードを格納して辞書を構築しておくと共
に、各ワードの例えば先頭一文字のアルファベットとこ
れが含まれるアドレス範囲とをテーブル化して検索範囲
設定テーブルを作成しておき、検索するデータの先頭一
文字をもとに検索範囲設定テーブルを参照して検索対象
となるアドレス範囲を決定し、これに応じて検索動作決
定回路５で一致検出動作信号ＳC1〜ＳCnのうち該当する
一致検出動作信号ＳCi 〜ＳCjをアクティブ状態とすれ
ばよい。
【００５７】
【発明の効果】以上説明したように、請求項１の発明に
よれば、検索範囲限定手段で検索データに基づいて検索
対象データの存在する範囲を限定し、この限定された範
囲内についてのみデータ検索手段で検索することによ
り、一致検出回路の動作数を限定して省電力化を図るこ
とができるという効果が得られる。
【００５８】また、請求項２の発明によれば、データ圧
縮アルゴリズムでは動的辞書をメモリセルアレイに格納
してゆくので、検索するデータが存在する範囲を予め限
定することができ、簡単な構成で検索範囲の限定を正確
に行うことができるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の一実施形態を示すブロック図である。
【図２】データ圧縮アルゴリズムを示すフローチャート
である。
【図３】図２の動作説明に供する説明図であって、
（ａ）は入力バイト、Ｋレジスタ及びΩレジスタ、出力
コードの内容を夫々表し、（ｂ）はメモリセルアレイに
構築される辞書がアドレスに対してＫレジスタの内容及
びΩレジスタの内容とが対応付けられて表されている。
【図４】図１の実施形態における動作の説明に供する説
明図である。
【図５】図１の実施形態における動作の説明に供する説
明図である。
【図６】図１の実施形態における動作の説明に供する説
明図である。
【図７】データ伸張アルゴリズムを示すフローチャート
である。
【図８】図７の動作説明に供する説明図であって、
（ａ）は入力コード、ＣＯＤＥレジスタ、ＩＮＣＯＤＥ
レジスタ、ＯＬＤＣＯＤＥレジスタ、Ｋレジスタ、Ｆレ
ジスタ、出力の内容を夫々表し、（ｂ）はメモリセルア
レイに構築される辞書がアドレスに対してＫレジスタの
内容及びΩレジスタの内容とが対応付けられて表されて
いる。
【図９】従来例を示すブロック図である。
【符号の説明】
１ 連想記憶装置 ２ メモリセルアレイ ３ａ Ωレジスタ ３ｂ Ｋレジスタ ４ 一致検出回路アレイ ５ 検索動作決定回路 ６ 検索範囲限定回路

Claims (2)

    【特許請求の範囲】
  1. 【請求項１】 入力された検索データに基づいてメモリ
    セルアレイに格納された多数の検索対象データを検索し
    て同一又は類似のデータの有無を出力する連想記憶装置
    において、前記検索データに基づいて検索すべき検索対
    象データの存在する範囲を限定する検索範囲限定手段
    と、該検索範囲限定手段で限定された範囲内で前記検索
    対象データを検索するデータ検索手段とを備えたことを
    特徴とする連想記憶装置。
  2. 【請求項２】 前記メモリセルアレイには、データ圧縮
    アルゴリズムによって検索データに対して過去の文字列
    に専用のアドレスを割当てて辞書形式で登録される動的
    辞書が格納されていることを特徴とする請求項１記載の
    連想記憶装置。
JP7334743A 1995-12-22 1995-12-22 連想記憶装置 Withdrawn JPH09180468A (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP7334743A JPH09180468A (ja) 1995-12-22 1995-12-22 連想記憶装置

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP7334743A JPH09180468A (ja) 1995-12-22 1995-12-22 連想記憶装置

Publications (1)

Publication Number Publication Date
JPH09180468A true JPH09180468A (ja) 1997-07-11

Family

ID=18280733

Family Applications (1)

Application Number Title Priority Date Filing Date
JP7334743A Withdrawn JPH09180468A (ja) 1995-12-22 1995-12-22 連想記憶装置

Country Status (1)

Country Link
JP (1) JPH09180468A (ja)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6181592B1 (en) 1999-01-18 2001-01-30 Nec Corporation Content addressable memory
WO2004054186A1 (ja) * 2002-12-12 2004-06-24 Fujitsu Limited データ中継装置、連想メモリデバイス、および連想メモリデバイス利用情報検索方法
US6766317B2 (en) 2001-07-18 2004-07-20 Alliance Semiconductor Range check cell and a method for the use thereof
US7249216B2 (en) 2002-12-12 2007-07-24 Fujitsu Limited Data relay apparatus, content addressable/associative memory device, and content addressable/associative memory device use information search method

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6181592B1 (en) 1999-01-18 2001-01-30 Nec Corporation Content addressable memory
US6766317B2 (en) 2001-07-18 2004-07-20 Alliance Semiconductor Range check cell and a method for the use thereof
WO2004054186A1 (ja) * 2002-12-12 2004-06-24 Fujitsu Limited データ中継装置、連想メモリデバイス、および連想メモリデバイス利用情報検索方法
US7249216B2 (en) 2002-12-12 2007-07-24 Fujitsu Limited Data relay apparatus, content addressable/associative memory device, and content addressable/associative memory device use information search method

Similar Documents

Publication Publication Date Title
JP3016868B2 (ja) 連想メモリを使用するｌｚｗデータ圧縮
JPH07114577A (ja) データ検索装置、データ圧縮装置及び方法
JPH07200247A (ja) データ圧縮装置および方法
JP3003915B2 (ja) 単語辞書検索装置
US20030208475A1 (en) Search engine for large-width data
US7290084B2 (en) Fast collision detection for a hashed content addressable memory (CAM) using a random access memory
US5081608A (en) Apparatus for processing record-structured data by inserting replacement data of arbitrary length into selected data fields
JP3141866B2 (ja) 連想記憶装置及び連想メモリ検索方法
JP2000305822A (ja) データベース管理装置，データベースレコード抽出装置，データベース管理方法及びデータベースレコード抽出方法
US6470334B1 (en) Document retrieval apparatus
US20030187877A1 (en) Database retrieval apparatus, retrieval method, storage medium, and program
JP2003521140A (ja) データの圧縮に必要な時間を短縮するための方法および装置
US6404362B1 (en) Method and apparatus for reducing the time required for decompressing compressed data
JPH09180468A (ja) 連想記憶装置
JPH09180469A (ja) 連想記憶装置
WO1992005494A1 (fr) Systeme equipe d'un processeur et procede de conversion d'adresses dans ledit systeme
JP2880199B2 (ja) 記号列検索方法および検索装置
JPH04308B2 (ja)
JP3038234B2 (ja) データ圧縮装置の辞書検索方式
JPH07105092A (ja) 記憶装置
JP2772124B2 (ja) 辞書検索方式
JP2772125B2 (ja) 辞書検索方式
JP2000151419A (ja) データ圧縮方法およびデータ圧縮装置
JP2535655B2 (ja) 辞書検索方式
JPS6373422A (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: 20030304