JPH0650478B2 - デ−タ圧縮記憶方式 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はデータ圧縮記憶方式に関し、特に情報処理装置
において記憶装置等にデータを圧縮して記憶するための
データ圧縮記憶方式に関する。

〔従来の技術〕

従来、この種のデータ圧縮記憶方式は、ある一定のワー
ド幅のデータ、例えば１ワード幅のデータを１データと
して同一パターンのデータの繰返しを判定することによ
り、同一パターンのデータがｎ（正整数）個連続的に続
くデータ列については同一パターンのデータの繰返しで
あることを示すビット，繰返し回数ｎおよび繰り返され
るデータによって表し、同一パターンのデータが連続し
ていないデータ列（以下、不連続データ列と称する）に
ついては同一パターンのデータが連続していないデータ
数およびその不連続データ列によって表すことにより、
データ量を通常よりも削減させて記憶装置等に記憶させ
るという方式であった。

〔発明が解決しようとする問題点〕

上述した従来のデータ圧縮記憶方式は、固定されたワー
ド幅のデータについてのみ同一パターンの繰返しがある
か否かを判定していたので、そのワード幅で同一パター
ンが繰り返されるデータ列に対してはデータの圧縮が可
能であったが、そのワード幅の複数倍のワード幅で同一
パターンが繰り返されるデータ列を圧縮することはでき
ず、他のワード幅では圧縮可能なデータ列が設定された
ワード幅では圧縮できないという欠点がある。

本発明の目的は、上述の点に鑑み、同一パターンの比較
を同時に複数のワード幅で行うことができるようにする
ことにより、複数のワード幅でデータの圧縮が行われる
ようにしたデータ圧縮記憶方式を提供することにある。

〔問題点を解決するための手段〕

本発明のデータ圧縮記憶方式は、ｎ（正整数）×２ワー
ドのデータを一時的に保持するデータラッチ回路と、こ
のデータラッチ回路に保持されたｎ×２ワードのデータ
の先頭のワードから数えて１ワードないしｎワードのデ
ータとこれに続く１ワードないしｎワードのデータとが
同一パターンのデータであるか否かを比較する１ワード
比較器ないしｎワード比較器と、これら１ワード比較器
ないしｎワード比較器の比較結果に基づいてｍ（１≦ｍ
≦ｎの正整数）ワード比較器に優先権を与えるかいずれ
の比較器にも優先権を与えない優先順位判定回路と、こ
の優先順位判定回路によりｍワード比較器に優先権が与
えられた場合にはｍワード毎に同一パターン繰返し回数
を計数しいずれの比較器にも優先権が与えられなかった
場合には不連続データ列のワード数を計数するカウンタ
と、前記優先権順位判定回路によりｍワード比較器に優
先権が与えられた場合には前記ｍワード比較器に対応す
る圧縮ワード幅データおよび前記カウンタの計数値であ
る同一パターン繰返し回数からなる圧縮コードデータを
先頭に付加して前記ｍワードの同一パターンのデータを
記憶させ前記優先順位判定回路によりいずれの比較器に
も優先権が与えられなかった場合には圧縮なしを示す圧
縮ワード幅データおよび前記カウンタの計数値である不
連続ワード数を先頭に付加して不連続データ列を記憶さ
せる制御回路とを有する。

〔作用〕

本発明のデータ圧縮記憶方式では、データラッチ回路が
ｎ（正整数）×２ワードのデータを一時的に保持し、１
ワード比較器ないしｎワード比較器がデータラッチ回路
に保持されたｎ×２ワードのデータの先頭のワードから
数えて１ワードないしｎワードのデータとこれに続く１
ワードないしｎワードのデータとが同一パターンのデー
タであるか否かを比較し、優先順位判定回路が１ワード
比較器ないしｎワード比較器の比較結果に基づいてｍ
（１≦ｍ≦ｎの正整数）ワード比較器に優先権を与える
かいずれの比較器にも優先権を与えず、カウンタが優先
順位判定回路によりｍワード比較器に優先権が与えられ
た場合にはｍワード毎に同一パターン繰返し回数を計数
しいずれの比較器にも優先権が与えられなかった場合に
は不連続データ列のワード数を計数し、制御回路が優先
順位判定回路によりｍワード比較器に優先権が与えられ
た場合にはｍワード比較器に対応する圧縮ワード幅デー
タおよびカウンタの計数値である同一パターン繰返し回
数からなる圧縮コードデータを先頭に付加してｍワード
の同一パターンのデータを記憶させ優先順位判定回路に
よりいずれの比較器にも優先権が与えられなかった場合
には圧縮なしを示す圧縮ワード幅データおよびカウンタ
の計数値である不連続ワード数を先頭に付加して不連続
データ列を記憶させる。

〔実施例〕

次に、本発明について図面を参照して詳細に説明する。

第１図は、本発明の一実施例を示すブロック図である。
本実施例のデータ圧縮記憶方式は、１ワードを１バイト
（８ビット）とし同一パターンの一致を比較可能な最大
ワード幅ｎを３とした場合の一例を示すものである。こ
のデータ圧縮記憶方式は、６（＝ｎ×２）個のデータラ
ッチ回路１〜６と、１バイト比較器７と、２バイト比較
器８と、３バイト比較器９と、優先順位判定回路10と、
制御回路11と、カウンタ12と、切換え回路13と、記憶回
路14とから構成されている。

データラッチ回路１〜６は、それぞれ１バイトのデータ
を保持するラッチ回路であり、初段のデータラッチ回路
１から終段のデータラッチ回路６まで順次直列に接続さ
れている。初段のデータラッチ回路１の入力には、記憶
する入力データをのせるデータバス21が接続されてお
り、データラッチ回路１〜６はデータバス21からの入力
データを順次後段のデータラッチ回路に送りながら全体
で６バイトの入力データを一時的に保持する。各データ
ラッチ回路１〜６の出力は、ラッチデータをのせるデー
タラッチバス22〜27にそれぞれ接続されている。

１バイト比較器７は、入力がデータラッチバス26とデー
タラッチバス27とにそれぞれ接続されており、データラ
ッチバス26の１バイトデータとデータラッチバス27の１
バイトデータとを比較して一致したときにその旨を示す
１バイト比較一致信号を１バイト比較一致信号線31に出
力する。

２バイト比較器８は、入力がデータラッチバス24および
25とデータラッチバス26および27とにそれぞれ接続され
ており、データラッチバス24および25の２バイトデータ
とデータラッチバス26および27の２バイトデータとを比
較して一致したときにその旨を示す２バイト比較一致信
号を２バイト比較一致信号線32に出力する。

３バイト比較器９は、入力がデータラッチバス22,23お
よび24とデーラッチバス25,26および27とにそれぞれ接
続されており、データラッチバス22,23および24の３バ
イトデータとデータラッチバス25,26および27の３バイ
トデータとを比較して一致したときにその旨を示す３バ
イト比較一致信号を３バイト比較一致信号線33に出力す
る。

優先順位判定回路10は、入力は１バイト比較一致信号線
31,2バイト比較一致信号線32および３バイト比較一致信
号線33にそれぞれ接続されていて、１バイト比較一致信
号線31,2バイト比較一致信号線32および３バイト比較一
致信号線33上の１バイト比較一致信号，２バイト比較一
致信号および３バイト比較一致信号の優先順位を判定し
て優先権を与える比較器の番号を２ビットで表した一致
比較器番号データを２ビットの一致比較器番号データバ
ス29に出力する。すなわち、優先順位判定回路10は、１
バイト比較器７に優先権を与える場合には“０１”
（“ ”で囲われた数字は２進数であることを示す。以
下同様）を、２バイト比較器８に優先権を与える場合に
は“１０”を、３バイト比較器９に優先権を与える場合
には“１１”をそれぞれ一致比較器番号データバス29に
出力する。なお、１バイト比較一致信号，２バイト比較
一致信号および３バイト比較一致信号のいずれも出力さ
れておらず、いずれの比較器にも優先権を与えない場合
には、優先順位判定回路10はその旨を示す“００”を一
致比較器番号データとして一致比較器番号データバス29
に出力する。

制御回路11は、入力を一致比較番号データバス29に接続
されており、一致比較器番号データバス29上の一致比較
器番号データを保持して、カウンタ計数指示線34にカウ
ンタ計数指示信号を、切換え指示線35に切換え指示信号
を、書込み指示線36に書込み指示信号を、書込みアドレ
スデータバス37に書込みアドレスデータを、圧縮ワード
幅データバス38に圧縮ワード幅データをそれぞれ出力す
る。

カウンタ12は、入力をカウンタ計数指示線34に接続さ
れ、カウンタ計数指示線34からのカウンタ計数指示信号
に基づいてｍワードの同一パターンの繰返し回数または
不連続データ列のワード数を計数し、その計数値を６ビ
ットの圧縮ワード数データバス30に出力する。

切換え回路13は、一方の入力に２ビットの圧縮ワード幅
データバス38と６ビットの圧縮ワード数データバス30と
を合わせた１バイト（８ビット）幅の圧縮コードデータ
が入力され、他方の入力にデータラッチバス27が接続さ
れている。また、制御入力に切換え指示線35が接続され
ている。切換え回路13は、切換え指示線35からの切換え
指示信号に基づいて圧縮コードデータとデータラッチバ
ス27からのデータとを選択的に切り換えて書込みデータ
バス28に出力する。

記憶回路14は、書込み指示線36からの書込み指示信号に
基づいて書込みデータバス28上のデータを書込みアドレ
スデータバス37により指示されたアドレスに書き込んで
記憶する。

第２図を参照すると、本実施例のデータ圧縮記憶方式に
おける圧縮コードデータは１バイト（８ビット）で構成
されていて、ビット０および１が圧縮ワード幅を示し、
ビット２〜７がビット０および１により示された圧縮ワ
ード幅の同一パターンのデータの同一パターン繰返し回
数を示す。

次に、このように構成された本実施例のデータ圧縮記憶
方式の動作について説明する。

(1)同一パターンのデータが連続しない場合 最初に送られてきたデータは、データラッチ回路６に保
持され、次に送られてきたデータはデータラッチ回路５
に保持され、以下順次３〜６バイト目のデータがデータ
ラッチ回路４〜１にそれぞれ保持されて、データラッチ
回路１〜６に全体で６バイトのデータが保持される。

この状態では、１バイト比較器７によりデータラッチ回
路６の１バイトのデータとデータラッチ回路５の１バイ
トのデータとが互いに比較され、２バイト比較器８によ
りデータラッチ回路６および５の２バイトのデータとデ
ータラッチ回路４および３の２バイトのデータとが互い
に比較され、３バイト比較器９によりデータラッチ回路
６，５および４の３バイトのデータとデータラッチ回路
３，２および１の３バイトのデータとが互いに比較され
る。

いま、同一パターンのデータが連続していない場合であ
るので、１バイト比較器７，２バイト比較器８および３
バイト比較器９の全てがデータの不一致を検出する。し
たがって、１バイト比較一致信号線31,2バイト比較一致
信号線32および３バイト比較一致信号線33に出力される
１バイト比較一致信号，２バイト比較一致信号および３
バイト比較一致信号はそれぞれ“０”となり、優先順次
判定回路10は一致比較器番号データバス29に一致比較器
番号データとして“００”を出力する。

一致比較器番号データバス29上の一致比較器番号データ
“００”を入力した制御回路11は、この一致比較器番号
データ“００”を保持し、切換え指示線35に切換え指示
信号を出力して切換え回路13にデータラッチバス27を選
択するように指示する。切換え指示信号を受けた切換え
回路13は、データラッチバス27のデータを書込みデータ
バス28に出力するように切り換える。

また、制御回路11は、書込みアドレスデータバス37に書
込みアドレスデータを出力して記憶回路14に対して書込
みアドレスを指示する。なお、制御回路11は、書込みア
ドレスとして圧縮コードデータを格納するアドレスを保
持して、その次のアドレスから順にアドレッシングす
る。

さらに、制御回路11は、書込み指示線36に書込み指示信
号を出力して記憶回路14に書込みデータバス28上のデー
タを書き込むように指示するとともに、カウンタ計数指
示線34にカウンタ計数指示信号を出力してカウンタ12に
計数を行うように指示する。このため、記憶回路14に不
連続データ列のデータが１バイトだけ書き込まれるとと
もに、カウンタ12が１つ計数される。なお、カウンタ12
の値は、一致比較器番号データバス29上の一致比較器番
号データの値が変化した際に制御回路12を介してゼロク
リアされる。

記憶回路14にデータラッチ回路６にラッチされた１バイ
トのデータが書き込まれると、前段のデータラッチ回路
にラッチされていた各データはそれぞれ次段のデータラ
ッチ回路に転送され、初段のデータラッチ回路１にはデ
ータバス21から供給される新たな１バイトのデータが保
持される。

上述と同様の処理が順次行われ、不連続データ列のデー
タが１バイトずつ次々に記憶回路14に書き込まれる。

この状態から１バイト比較器７，２バイト比較器８およ
び３バイト比較器９のうちのいずれか１つの比較器でも
データの一致を検出すると、優先順位判定回路10は一致
比較器番号データバス29に出力する一致比較器番号デー
タを“００”から他の値に変更する。

一致比較器番号データバス29からの一致比較器番号デー
タが変化したことを制御回路11が検出すると、制御回路
11は保持していた圧縮コードデータを格納するアドレス
を書込みアドレスデータバス37に出力し、保持していた
一致比較器番号データ“００”を圧縮ワード幅データと
して圧縮ワード幅データバス38に出力する。また、制御
回路11は、切換え指示線35に切換え指示信号を出力して
圧縮ワード幅データバス38上の２ビットの圧縮ワード幅
データと圧縮ワード数データバス30上の圧縮ワード数デ
ータとを合成した圧縮コードデータを選択するように切
換え回路13に指示する。さらに、制御回路11は、記憶回
路14に対して書込み指示線36により書込み指示する。

この結果、記憶回路14の不連続データ列が書き込まれた
先頭のアドレス位置に圧縮コードデータが書き込まれ
る。

(2)ｍ（ｍは１≦ｍ≦ｎの正整数）バイト幅の同一パタ
ーンのデータが連続する場合 ｍバイト幅のデータが一致したことをｍバイト比較器が
検出すると、ｍバイト比較一致信号をｍバイト比較一致
信号線に出力する。

優先順位判定回路10は、複数の比較一致信号を入力した
場合には優先順位を判定し、優先権を付与する比較器に
対応する一致比較器番号データを一致比較器番号データ
バス29に出力する。ここでは、一致比較器番号データバ
ス29に出力される一致比較器番号データをｍとする。

一致比較器番号データバス29より一致比較器番号データ
ｍを入力した制御回路11は、こ一致比較器番号データｍ
を保持し、記憶回路14への書込み指示線36による書込み
指示を行わずにデータラッチ回路１〜６のｍバイト分の
データを次段以降のデータラッチ回路に送り、データバ
ス21よりｍバイト分の入力データを受け取る。また、制
御回路11は、ｍバイトごとにカウンタ計数指示信号をカ
ウンタ計数指示線34に出力し、このためカウンタ12はｍ
バイトごとに１ずつ計数される。

上述と同様の処理が、一致比較器番号データバス29上の
一致比較器番号データがｍから他の値に変化するまで連
続して行われる。

ここで、一致比較器番号データバス29上の一致比較器番
号データがｍ以外に変化すると、制御回路11は保持して
いた一致比較器番号データｍを圧縮ワード幅データバス
38に圧縮ワード幅データとして出力し、切換え指示線35
に切換え指示信号を出力して切換え回路13に対して圧縮
ワード幅データバス38と圧縮ワード数データバス30とを
合成した圧縮コードデータを選択するように指示する。
切換え指示線35により圧縮ワードデータを選択するよう
に指示された切換え回路13は、圧縮コードデータを書込
みデータバス28に出力する。また、制御回路11は、記憶
回路14に対して書込み指示線36により書込みを指示す
る。これにより、圧縮コードデータが記憶回路14に書き
込まれる。

次に、制御回路11は、切換え指示線35に切換え指示信号
を出力して切換え回路13にデータラッチバス27の選択を
指示し、記憶回路14の圧縮コードデータを書き込んだア
ドレスに続くアドレスから連続して後段側のデータラッ
チ回路からｍバイトのデータを記憶回路14に書き込んで
ゆく。すなわち、ｍバイトの同一パターンのデータを記
憶回路14に書き込む。

本実施例のデータ圧縮記憶方式では、上記(1)および(2)
の処理を適宜繰り返すことにより、入力データを圧縮し
て記憶回路14に記憶することができる。

第３図は、入力データと圧縮後のデータとの関係の一例
を示す図である。本例では、入力データのバイト０〜３
は、不連続データ列として圧縮コードデータ“０４”_Ｈ
（“ ”_Ｈで囲われた数字は16進数であることを示す。
以下同様）を先頭に付加されて圧縮後のデータのバイト
０〜４に記憶されている。入力データのバイト４〜９
は、２バイト幅のデータが３回連続していることを示す
圧縮コードデータ“８３”を先頭に付加された“ＦＦＤ
Ｆ”_Ｈというデータに圧縮されて圧縮後のデータのバイ
ト５〜７に記憶されている。入力データのバイト10〜15
は、３バイト幅のデータが２回連続していることを示す
圧縮コードデータ“Ｃ２”を先頭に付加された“ＡＡ５
５ＤＢ”_Ｈというデータに圧縮されて圧縮後のデータの
バイト８〜11に記憶されている。入力データのバイト16
〜19は、１バイト幅のデータが４回連続しているという
ことを示す圧縮コードデータ“４４”_Ｈを先頭に付加さ
れた“００”_Ｈというデータに圧縮されて圧縮後のデー
タのバイト12および13に記憶されている。このように本
例では、入力データの数が20に対して圧縮後のデータの
数は14となり、記憶データ数が削減されている。

ところで、本実施例のデータ圧縮記憶方式により圧縮記
憶されたデータを記憶回路14から読み出す場合には、圧
縮コードデータ内のビット０および１の圧縮ワード幅デ
ータを調べて“００”ならばビット２〜７の同一パター
ン繰返し回数で示されるバイト数分を出力し、“０１”
ならば次の１バイトデータを同一パターン繰返し回数分
出力し、“１０”ならば次の２バイトのデータを同一パ
ターン繰返し回数分出力し、“１１”ならば次の３バイ
トのデータを同一パターン繰返し回数分出力するように
する。

なお、上記実施例では、１ワードを１バイト（８ビッ
ト）とし同一パターンの一致を比較可能な最大ワード幅
ｎを３とした場合の一例について説明したが、１ワード
はかならずしも１バイトである必要はなく、また同一パ
ターンの一致を比較可能な最大ワード幅ｎも３である必
要はないことはいうまでもない。

また、圧縮ワード幅データを２ビットで示すようにした
が、同一パターンの一致を比較可能な最大ワード幅ｎを
大きくとった場合には、その分だけ大きなビット数が必
要になる。一般に、同一パターンの一致を比較可能な最
大ワード幅をｎとすると、圧縮ワード幅データのビット
数は（１＋［log₂n］）ビット必要となる。

〔発明の効果〕

以上説明したように本発明は、同一パターンの一致を比
較可能な最大ワード幅の２倍の数のデータラッチ回路
と、同一パターンの一致を比較する１ワード比較器ない
しｎワード比較器と、これら比較器の優先順位判定回路
と、同一パターン繰返し回数および不連続ワード数を計
数するカウンタと、書込み動作の制御を行う制御回路と
を設けたことにより、同一パターンの比較を同時に複数
のワード幅で行うことができ、固定ワード幅でデータ圧
縮を判定する場合に比べてさらに記憶データ量を削減で
きるという効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロック図、 第２図は本実施例のデータ圧縮記憶方式における圧縮コ
ードデータの構成の一例を示す図、 第３図は本実施例のデータ圧縮記憶方式による入力デー
タと圧縮後のデータとの関係の一例を示す符号構成図で
ある。 図において、 １〜６……データラッチ回路、 ７……１バイト比較器、 ８……２バイト比較器、 ９……３バイト比較器、 10……優先順位判定回路、 11……制御回路、 12……カウンタ、 13……切換え回路、 14……記憶回路、 21……データバス、 22〜27……データラッチバス、 28……書込みデータバス、 29……一致比較器番号データバス、 30……圧縮ワード数データバス、 31……１バイト比較一致信号線、 32……２バイト比較一致信号線、 33……３バイト比較一致信号線、 34……カウンタ計数指示線、 35……切換え指示線、 36……書込み指示線、 37……書込みアドレスデータバス、 38……圧縮ワード幅データバスである。

Claims (1)

【特許請求の範囲】
1. 【請求項１】ｎ（正整数）×２ワードのデータを一時的
   に保持するデータラッチ回路と、 このデータラッチ回路に保持されたｎ×２ワードのデー
   タの先頭のワードから数えて１ワードないしｎワードの
   データとこれに続く１ワードないしｎワードのデータと
   が同一パターンのデータであるか否かを比較する１ワー
   ド比較器ないしｎワード比較器と、 これら１ワード比較器ないしｎワード比較器の比較結果
   に基づいてｍ（１≦ｍ≦ｎの正整数）ワード比較器に優
   先権を与えるかいずれの比較器にも優先権を与えない優
   先順位判定回路と、 この優先順位判定回路によりｍワード比較器に優先権が
   与えられた場合にはｍワード毎に同一パターン繰返し回
   数を計数しいずれの比較器にも優先権が与えられなかっ
   た場合には不連続データ列のワード数を計数するカウン
   タと、 前記優先順位判定回路によりｍワード比較器に優先権が
   与えられた場合には前記ｍワード比較器に対応する圧縮
   ワード幅データおよび前記カウンタの計数値である同一
   パターン繰返し回数からなる圧縮コードデータを先頭に
   付加して前記ｍワードの同一パターンのデータを記憶さ
   せ前記優先順位判定回路によりいずれの比較器にも優先
   権が与えられなかった場合には圧縮なしを示す圧縮ワー
   ド幅データおよび前記カウンタの計数値である不連続ワ
   ード数を先頭に付加して不連続データ列を記憶させる制
   御回路と、 を有することを特徴とするデータ圧縮記憶方式。