JP3143029B2 - データ圧縮方法及びその装置並びにデータ伸長方法及びその装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、各種記憶装置における
格納データの圧縮や読出データの伸長、あるいはデジタ
ル通信機器等における転送データの圧縮や伸長に使用さ
れるデータ圧縮方法及びその装置並びにデータ伸長方法
及びその装置に関するものである。

【０００２】

【従来の技術】この種の圧縮のための符号化に使用され
る符号として、「データ圧縮アルゴリズムとその実現」
（インターフェース，ＣＱ出版社，Ａｕｇ．１９９
２．，１０５〜１１７ページ）や特開平３−６８２１９
号公報に示されているような適応型符号と呼ばれるもの
がある。この適応型符号は、文字列（入力データ列）を
読み込みながらその統計的性質を抽出して符号化を行う
ため、文字列を読み終わると同時に符号化が終了すると
いう特徴を有する。この適用型符号の一種であるユニバ
ーサル符号の代表的なものに、Ｌｅｍｐｅｌ−Ｚｉｐ符
号（その符号化の概念をつかみやすいことからスライド
辞書法とも呼ばれる）がある。

【０００３】このスライド辞書法では、与えられた文字
列の中から現在の符号化を行っている文字の近傍の何文
字かを保存するバッファを用意し、このバッファを辞書
として利用して、符号化を行う方法である。符号化が進
むにつれ、このバッファに保存されている文字列は、与
えられた文字列中をスライドしていくことから、スライ
ド辞書法と呼ばれるようになった。

【０００４】符号化における辞書の参照は、現時点で符
号化の対象となっている位置から始まる文字列に一致す
るバッファ中の文字列で最も長い最長一致系列を探すこ
とを基本としている。そして、そのような文字列が見つ
かれば、一致不一致を示す１ビットの一致フラグを
「１」にして、見つかった文字列のバッファ中の位置と
その長さを適当な桁数の２進数で表したものを符号語と
する。また、そのような文字列がバッファ中になければ
一致フラグを“０”にして、符号化の対象となっている
１文字をそのまま（例えば、ＡＳＣＩＩコードで）出力
したものを符号語とする。

【０００５】ここで、上記スライド辞書法において、辞
書内の一致データ列の長さを表わすデータ（長さ指示
子）は、各長さに一対一で対応する固定的な構造になっ
ており、従って、そのビット数も固定であるか、もしく
は、長さがある一定以上になると拡張フォーマットを用
いてビット数を増やすのみであった。

【０００６】

【発明が解決しようとする課題】ところが、このような
従来の技術においては、圧縮する前のデータが予め分か
っているような場合、残りデータ数がある数以下，すな
わち長さ指示子で表わせる上限の１／２以下になると、
長さ指示子のデータサイズが冗長となる。例えば、長さ
指示子を８ビットとすると、単純に考えて、８ビットで
表わせる上限は“１１１１１１１１”の２５５であるの
で、残りデータ数がその１／２以下，すなわち１２７に
なると“０１１１１１１１”となって、上位１ビットが
冗長となり、さらに、その１／２以下，すなわち６３に
なると“００１１１１１１”となって、上位２ビットが
冗長となり、以下、残りデータ数が１／２になる毎に上
位ビットが１ビットずつ冗長になり、そのビットが無駄
になっていた。これは、この圧縮方法(スライド辞書法)
が小さいサイズのデータ列に対して圧縮率が良くない原
因にもなっていた。

【０００７】そこで、本発明はこのような問題点を解決
するためになされたものであり、入力データ列の後部
で、長さ指示子で表わされる上限の１／２以下の長さ分
のデータに対する圧縮データの冗長な部分を取り除き、
より圧縮効率の高いデータ圧縮方法及びその装置並びに
データ伸長方法及びその装置を提供することを目的とす
るものである。

【０００８】

【課題を解決するための手段】請求項１に記載の発明
は、入力データ列のうち、各時点で符号化の対象となる
データの近傍のデータ列を所定数量まで記憶手段に格納
し、格納されたデータ列を符号化のために参照する辞書
として用い、各時点で符号化の対象となっている位置か
ら始まるデータ列に一致する上記辞書内のデータ列で、
上記所定数量の範囲内の既定の上限以下で最も長い一致
データ列を検索し、当該一致データ列が見つかれば、一
致を示すフラグと、見つかったデータ列の辞書内の位置
を示すポインタと、その長さを示す長さ指示子とから符
号語を構成するとともに、上記一致データ列が見つから
なければ、不一致を示すフラグと、符号化の対象となっ
ているデータそのものとから符号語を構成することによ
り、データの圧縮を行うデータ圧縮方法において、入力
データ列の残りデータ数を計数し、残りデータ数が上記
上限以下となった場合には、その残りデータ数を２進数
で表現可能な最小のビット数に上記長さ指示子のビット
数を設定し、設定した長さ指示子のビット数にて符号化
を行うようにしたものである。

【０００９】同様に、請求項２に記載の発明は、入力デ
ータ列のうち、各時点で符号化の対象となるデータの近
傍のデータ列を所定数量まで記憶手段に格納し、格納さ
れたデータ列を符号化のために参照する辞書として用
い、各時点で符号化の対象となっている位置から始まる
データ列に一致する上記辞書内のデータ列で、上記所定
数量の範囲内の既定の上限以下で最も長い一致データ列
を検索し、当該一致データ列が見つかれば、一致を示す
フラグと、見つかったデータ列の辞書内の位置を示すポ
インタと、その長さを示す長さ指示子とから符号語を構
成するとともに、上記一致データ列が見つからなけれ
ば、不一致を示すフラグと、符号化の対象となっている
データそのものとから符号語を構成することにより、デ
ータの圧縮を行うデータ圧縮装置において、入力データ
列の残りデータ数を計数する計数手段と、この計数手段
で計数された残りデータ数に基づき、その残りデータ数
が上記上限以下となったときに当該データ数を２進数で
表現可能な最小のビット数に上記長さ指示子のビット数
を設定する設定手段と、この設定手段で設定された長さ
指示子のビット数にて符号化を行う符号化手段とを備え
たものである。

【００１０】また、請求項３に記載の発明は、上記請求
項２のデータ圧縮装置において、不揮発性半導体記憶手
段に書き込まれるプログラムやデータを圧縮するもので
ある。

【００１１】一方、請求項４に記載の発明は、上記請求
項１記載のデータ圧縮方法または請求項２記載のデータ
圧縮装置によって圧縮された圧縮データを入力し、符号
語に含まれるフラグが不一致を示すときは、当該符号語
に含まれる他のデータを取り出して復号化するととも
に、当該データを復号化のために参照する所定数量の辞
書に入力し、また、符号語に含まれるフラグが一致を示
すときは、当該符号語に含まれるポインタと長さ指示子
とを用いて上記辞書内から対応するデータを取り出して
復号化するとともに、当該データを上記辞書に入力する
ことにより、圧縮データの伸長を行うデータ伸長方法で
あって、伸長データの残りデータ数を計数し、残りデー
タ数が上記所定数量の範囲内の既定の上限以下となった
場合には、その残りデータ数を２進数で表現可能な最小
のビット数から上記長さ指示子のビット数を判別し、判
別した長さ指示子のビット数を用いて復号化を行うよう
にしたものである。

【００１２】同様に、請求項５に記載の発明は、請求項
１記載のデータ圧縮方法または請求項２記載のデータ圧
縮装置によって圧縮された圧縮データを入力し、符号語
に含まれるフラグが不一致を示すときは、当該符号語に
含まれる他のデータを取り出して復号化するとともに、
当該データを復号化のために参照する所定数量の辞書に
入力し、また、符号語に含まれるフラグが一致を示すと
きは、当該符号語に含まれるポインタと長さ指示子とを
用いて上記辞書内から対応するデータを取り出して復号
化するとともに、当該データを上記辞書に入力すること
により、圧縮データの伸長を行うデータ伸長装置であっ
て、伸長データの残りデータ数を計数する計数手段と、
この計数手段で計数された残りデータ数に基づき、その
残りデータ数が上記所定数量の範囲内の既定の上限以下
となったときに当該データ数を２進数で表現可能な最小
のビット数から上記長さ指示子のビット数を判別する判
別手段と、この判別手段で判別された長さ指示子のビッ
ト数を用いて復号化を行う復号化手段とを備えたもので
ある。

【００１３】また、請求項６に記載の発明は、上記請求
項５のデータ伸長装置において、プログラムやデータの
圧縮データが記憶された不揮発性半導体記憶手段から読
み出される圧縮データを伸長するものである。

【００１４】

【作用】請求項１記載のデータ圧縮方法によれば、圧縮
データのうち、最長一致データ列の長さを示す長さ指示
子のサイズ（ビット数）を、入力データ列の残りデータ
数が既定の上限以下となったときに２進数で表現可能な
最小のビット数に設定したので、入力データ列の後部
で、長さ指示子で表わされる上限の１／２以下の長さ分
のデータに対する圧縮データの冗長な部分を取り除き、
圧縮効率を向上することができる。

【００１５】また、請求項２記載のデータ圧縮装置によ
れば、上記請求項１と同様の作用を有するとともに、圧
縮を高速に行うことができる。

【００１６】また、請求項３記載のデータ圧縮装置によ
れば、不揮発性半導体記憶手段に書き込まれるプログラ
ムやデータを圧縮するので、高価な記憶素子を効率的に
使用することができる。

【００１７】一方、請求項４記載のデータ伸長方法によ
れば、伸長データの残りデータ数が既定の上限以下とな
ったとき、圧縮データにおける長さ指示子のビット数
を、残りデータ数を２進数で表現可能な最小のビット数
と判別し、復号化を行うようにしたので、上記により圧
縮されたデータを伸長することができる。

【００１８】また、請求項５記載のデータ伸長装置によ
れば、上記請求項４と同様の作用を有するとともに、伸
長を高速に行うことができる。

【００１９】また、請求項６記載のデータ伸長装置によ
れば、不揮発性半導体記憶手段から読み出されるプログ
ラムやデータの圧縮データを、高速に伸長することがで
きる。

【００２０】

【実施例】以下、本発明の一実施例を図面を参照して説
明する。図１は、本発明の一実施例に係るデータ圧縮装
置を示すブロック図である。図において、１は入力デー
タ列を一時保持する入力データバッファである。この入
力データバッファ１は、本実施例では、データバス幅８
ビット，アドレス８ビットで、計２５６バイトのシフト
レジスタで構成されており、アドレスＦＦｈ（ｈは１６
進表記を意味し、この場合２５５番地，すなわち最上位
番地）にデータを入力することにより、各番地のデータ
はアドレスの若い方に向かってシフトされる。また、後
述する最長一致データ列検索装置３からの検索終了信号
（トリガ）を受けると、一致データ列有／無フラグが
“１”の時は、一致データ列長の示すバイト数だけ新た
なデータを入力し、バッファ内のデータはそのバイト数
分だけ順次シフトされる。また、一致データ列有／無フ
ラグが“０”の場合は、新たなデータを１バイト入力
し、バッファ内のデータは１バイトシフトされる。

【００２１】２は前述したスライド辞書法に基づくスラ
イド辞書が格納される辞書バッファであり、本実施例で
は、この辞書バッファ２もデータバス幅８ビット，アド
レス８ビットで、計２５６バイトのシフトレジスタで構
成されている。入力データは、辞書バッファ２に空きが
ある時，すなわち辞書サイズ（ｄｉｃ＿ｓｉｚｅ）＜２
５６の時は、この辞書サイズ（ｄｉｃ＿ｓｉｚｅ）をア
ドレスとしてラッチされる（Ｄ（ｄｉｃ＿ｓｉｚｅ）＝
入力データ）。一方、辞書バッファ２が満杯の時，すな
わち辞書サイズ（ｄｉｃ＿ｓｉｚｅ）＝２５６の時は、
まず辞書データをアドレス００ｈに向かってシフト（Ｄ
（ｎ）＝Ｄ（ｎ＋１），ｎ＝１，２，・・・，２５４）
してからアドレスＦＦｈにラッチされる。後述する最長
一致データ列検索時は、最長一致データ列検索装置３の
制御によるアドレスの示すデータを出力し、辞書データ
の検索が行なわれる。

【００２２】最長一致データ列検索装置３は、上記入力
データバッファ１のアドレス００ｈを先頭とするデータ
列と最も長く一致する２バイト以上のデータ列を、上記
２５６バイトの辞書バッファ２のうち、後述する辞書サ
イズカウンタ４の出力する辞書サイズ（ｄｉｃ＿ｓｉｚ
ｅ）の示す領域の中から検索するものである。この検索
の結果、一致データ列が見つかった場合は、一致データ
列有／無フラグを“１”にして、一致データ列の先頭デ
ータの辞書上の位置（アドレス）を示す一致データ列ポ
インタ（ｃｒｓｐｄ＿ｐｏｉｎｔ）、及び一致データ列
の長さ（バイト数）を示す長さ指示子である一致データ
列長（ｃｒｓｐｄ＿ｌｅｎ）を後述する符号化装置７に
出力するとともに、一致データ列を辞書バッファ２に出
力する。見つからなかった場合は、一致データ列有／無
フラグを“０”にして、生データ１バイトを符号化装置
７及び辞書バッファ２に出力する。

【００２３】また、本実施例では、この最長一致データ
列検索装置３から辞書バッファ２にデータ列を出力する
際、１バイト出力する毎に辞書サイズカウンタ４にイン
クリメント信号を出力するとともに、残りデータ数カウ
ンタ５にデクリメント信号を出力する。出力を終える
と、最長一致データ列検索装置３は符号化装置７に対し
て検索終了信号（トリガー）を出力し、一回の最長一致
データ列検索処理を終える。また、符号化装置７からの
符号化終了信号（トリガー）を受けると、再び上述した
最長一致検索処理を開始する。

【００２４】辞書サイズカウンタ４は、カウント最大値
が２５６に設定されたアップカウンタで構成され、圧縮
開始時に図示しないシステムリセット信号によりリセッ
トされる。そして、上述した最大一致データ列検索装置
３からのインクリメント信号によりカウントアップし、
最大値（２５６）に達すると、以降その値を保持する。
この辞書サイズカウンタ４の出力（辞書サイズｄｉｃ＿
ｓｉｚｅ）は、上記最長一致データ列検索装置３に出力
される。

【００２５】残りデータ数カウンタ５は、本願発明にお
いて備えられた計数手段に相当するもので、本圧縮装置
の利用分野で想定される最大のデータ数が設定可能なビ
ット数のダウンカウンタで構成され、圧縮開始前に入力
データ列のデータ数がセットされる。以降、最長一致デ
ータ列検索装置３からのデクリメント信号を受ける毎に
カウントダウンし、残りデータ数を長さ指示子データサ
イズジェネレータ６に出力する。

【００２６】長さ指示子データサイズジェネレータ６
は、本願発明において備えられた設定手段に相当するも
ので、ゲート回路からなるエンコーダで構成され、上記
残りデータ数カウンタ５からの出力値（残りデータ数ｒ
ｅｍ＿ｓｉｚｅ）を元にして対応する長さ指示子データ
サイズ（ｌｅｎ＿ｓｉｚｅ）を生成し、符号化装置７に
出力する。この長さ指示子データサイズジェネレータ６
の入力（残りデータ数ｒｅｍ＿ｓｉｚｅ）と出力（長さ
指示子データサイズ）の対応表を図２に示す。なお、残
りデータ数が２５７以上の時も最大一致データ列長の上
限は２５６なので、長さ指示子の最大値は２５５とな
る。また、残りデータ数が１の時は、２バイト以上の一
致データ列はある得ないので、一致データ列有／無フラ
グは常に０となり、従って、長さ指示子データサイズも
０となる。

【００２７】符号化装置７は、本願発明における符号化
手段に相当するもので、従来からある符号化装置に後述
する本願特有の機能が付加されたものである。この符号
化装置７は、前記最長一致データ列検索装置３からの検
索終了信号をトリガにして符号化処理を開始し、符号化
された圧縮データビットストリームを出力データ同期ク
ロックとともに出力する。すなわち、まず、一致データ
列有／無フラグ１ビットを出力する。次に、このフラグ
が“０”のときは、生データを８ビット（１バイト）を
ＬＳＢ（最下位ビット）から順次出力する。また、フラ
グが“１”のときは、先ず一致データ列長（ｃｒｓｐｄ
＿ｌｅｎ）２〜２５６から１を引いた８ビット（１〜２
５５）のうちＬＳＢから長さ指示子データサイズジェネ
レータ６の出力する長さ指示子データサイズが表わすビ
ット数分だけ順次出力する。次に、一致データ列ポイン
タ（ｃｒｓｐｄ＿ｐｏｉｎｔ）８ビットをＬＳＢから順
次出力する。これらの圧縮データビットストリームの出
力が終わると、符号化終了信号を最長一致データ列検索
装置３に出力する。

【００２８】次に、このように構成されたデータ圧縮装
置の動作について説明する。圧縮の対象となる入力デー
タ列は、２５６バイトの入力データバッファ１に一旦蓄
えられる。ここでは、例えば“ａｂｃａｂｄ・・・ａｂ
ｃ”となる２５６バイトの入力データ列を例に取って以
下の説明を行う。なお、圧縮開始時には辞書サイズカウ
ンタ４がシステムリセット信号によりリセットされて０
となり、また、残りデータ数カウンタ５に入力データ数
として２５６がセットされている。

【００２９】最長一致データ列検索装置３は、図３にフ
ローチャートで示すアルゴリズムに従って最長一致デー
タ列検索処理を実行する。すなわち、先ずステップ１０
１で、９ビット（０〜２５６）の一致データ列長（ｃｒ
ｓｐｄ＿ｌｅｎ）を０に初期化し、辞書バッファ２のア
ドレスを示す８ビット（０〜２５５）の辞書ポインタ
（ｄｉｃ＿ｐｏｉｎｔ）を０に初期化，すなわち辞書の
先頭に初期化する。また、ステップ１０２で一時的（テ
ンポラリ）な一致データ列長（ｃｏｍｐ＿ｌｅｎ）を０
に初期化し、入力データバッファ１のアドレスを示す８
ビット（０〜２５５）の入力データバッファポインタ
（ｓｔｒ＿ｐｏｉｎｔ）を０に初期化，すなわち入力デ
ータ列の先頭に初期化する。

【００３０】次に、ステップ１０３で、上記入力データ
バッファポインタ（ｓｔｒ＿ｐｏｉｎｔ）に対応する入
力データ（Ｓ），すなわち“ａ”と辞書ポインタ（ｄｉ
ｃ＿ｐｏｉｎｔ）に対応する辞書データ（Ｄ）とが一致
するか否かを判別する。今、辞書バッファ２には未だデ
ータが入力されていないので、不一致となってステップ
１０４に進み、辞書ポインタ（ｄｉｃ＿ｐｏｉｎｔ）を
インクリメントし、ステップ１０５で、辞書ポインタ
（ｄｉｃ＿ｐｏｉｎｔ）が辞書サイズカウンタ４の出力
する辞書サイズ（ｄｉｃ＿ｓｉｚｅ）以上となったか否
かを判別する。辞書サイズカウンタ４は圧縮開始時にシ
ステムリセット信号によりリセットされて０となってい
るので、このステップ１０５の判別は（Ｙ）となってス
テップ１１３に進む。

【００３１】ステップ１１３では、一致データ列長（ｃ
ｒｓｐｄ＿ｌｅｎ）が２以上か否かが判別される。すな
わち、一致データ列長が１バイト以下では圧縮する意味
がないので、ステップ１１５に進んで一致データ列有／
無フラグ（ｃｒｓｐｄ＿ｆｌａｇ）を０とし、一致デー
タ列長が２バイト以上であれば有効な一致データ列を検
出したとして、ステップ１１４に進んで該フラグを１と
する。今、一致データ列長（ｃｒｓｐｄ＿ｌｅｎ）はス
テップ１０１で初期化されたままで０であるので、ステ
ップ１１３からステップ１１５に進んで一致データ列有
／無フラグ（ｃｒｓｐｄ＿ｆｌａｇ）を０とする。ま
た、この時、入力データ列の先頭データである生データ
１バイト“ａ”を符号化装置７と辞書バッファ２に出力
するとともに、辞書サイズカウンタ４にインクリメント
信号を出力し、残りデータ数カウンタ５にデクリメント
信号を出力する。そして、ステップ１１６に進んで検索
終了信号を符号化装置７と入力データバッファ１に出力
し、一回目の検索処理を終了する。

【００３２】符号化装置７は、上述した最長一致データ
列検索装置３からの検索終了信号をトリガーにして図４
にフローチャートで示す符号化処理を開始する。すなわ
ち、ステップ２０１で最長一致データ列検索装置３から
の一致データ列有／無フラグ１ビットを圧縮データビッ
トストリームとして出力する。次に、ステップ２０２で
上記一致データ列有／無フラグが１か否かを判別する。
今、該フラグは０であるので、ステップ２０３に進ん
で、最長一致データ列検索装置３からの生データ８ビッ
ト（１バイト“ａ”）をＬＳＢ（最下位ビット）から順
次出力する。そして、ステップ２０６に進み、符号化終
了信号を最長一致データ列検索装置３に出力し、一回目
の符号化処理を終了する。

【００３３】上記符号化装置７からの符号化終了信号を
トリガーにして最長一致データ列検索装置３が起動さ
れ、図３のフローチャートで示す処理が実行される。こ
こで、２回目，３回目の最長一致データ列検索処理にお
いても、入力データ列の先頭データはそれぞれ“ｂ”，
“ｃ”となるので、入力データ列の先頭データと一致す
るデータを辞書の中から検索するステップ１０３〜１０
５の処理において一致データ列は見つからず、上記と同
様な検索処理及び符号化処理となる。そして、辞書バッ
ファ２には、入力データ列の先頭からの３バイト“ａｂ
ｃ”が格納され、辞書サイズカウンタ４から出力される
辞書サイズ（ｄｉｃ＿ｓｉｚｅ）は３を示し、残りデー
タ数カウンタ５の出力する残りデータ数（ｒｅｍ＿ｓｉ
ｚｅ）は２５３となり、長さ指示子データサイズジェネ
レータ６の出力する長さ指示子データサイズ（ｌｅｎ＿
ｓｉｚｅ）は８のままである（図２参照）。

【００３４】さて、次の４回目の検索処理において、入
力データ列の先頭データは“ａ”となる。図３のフロー
チャートのステップ１０３において、入力データバッフ
ァポインタ（ｓｔｒ＿ｐｏｉｎｔ）に対応する入力デー
タ（Ｓ），すなわち“ａ”と辞書ポインタ（ｄｉｃ＿ｐ
ｏｉｎｔ）に対応する辞書データ（Ｄ），すなわち
“ａ”とが一致する。従って、ステップ１０６に進ん
で、入力データバッファポインタ（ｓｔｒ＿ｐｏｉｎ
ｔ），辞書ポインタ（ｄｉｃ＿ｐｏｉｎｔ）及びテンポ
ラリ一致データ列長（ｃｏｍｐ＿ｌｅｎ）がそれぞれイ
ンクリメントされ、それぞれ１となる。次に、ステップ
１０７では、辞書ポインタ（ｄｉｃ＿ｐｏｉｎｔ）が辞
書サイズ（ｄｉｃ＿ｓｉｚｅ）以上になったか否かが判
定され、辞書ポインタは１で辞書サイズは３であるの
で、ステップ１０８に進む。このステップ１０８では、
入力データバッファポインタ（ｓｔｒ＿ｐｏｉｎｔ）に
対応する入力データ（Ｓ）と辞書ポインタ（ｄｉｃ＿ｐ
ｏｉｎｔ）に対応する辞書データ（Ｄ）との一致が判別
され、それぞれ“ｂ”となって一致するので、ステップ
１０６に戻って上述したインクリメントが行われ、入力
データバッファポインタ（ｓｔｒ＿ｐｏｉｎｔ），辞書
ポインタ（ｄｉｃ＿ｐｏｉｎｔ），テンポラリ一致デー
タ列長（ｃｏｍｐ＿ｌｅｎ）はそれぞれ２となる。

【００３５】次のステップ１０７では辞書ポインタが２
で辞書サイズの３以上とならないので、ステップ１０８
に進む。ここで、入力データバッファポインタ（ｓｔｒ
＿ｐｏｉｎｔ）に対応する入力データ（Ｓ）は“ｄ”で
辞書ポインタ（ｄｉｃ＿ｐｏｉｎｔ）に対応する辞書デ
ータ（Ｄ）は“ｃ”であり、一致しないのでステップ１
０９に進み、テンポラリ一致データ列長（ｃｏｍｐ＿ｌ
ｅｎ）が一致データ列長（ｃｒｓｐｄ＿ｌｅｎ）より大
きいか否かが判別される。テンポラリ一致データ列長
（ｃｏｍｐ＿ｌｅｎ）は２で、一致データ列長（ｃｒｓ
ｐｄ＿ｌｅｎ）はステップ１０１で初期化されたままで
０であるので、ステップ１１０に進む。ステップ１１０
では、一致データ列長（ｃｒｓｐｄ＿ｌｅｎ）にテンポ
ラリ一致データ列長（ｃｏｍｐ＿ｌｅｎ）の値２が代入
され、８ビット（０〜２５５）の一致データ列ポインタ
（ｃｒｓｐｄ＿ｐｏｉｎｔ）には辞書ポインタ（ｄｉｃ
＿ｐｏｉｎｔ）から一致データ列長（ｃｒｓｐｄ＿ｌｅ
ｎ）を引いた値０が代入され、また辞書ポインタ（ｄｉ
ｃ＿ｐｏｉｎｔ）が一致データ列長（ｃｒｓｐｄ＿ｌｅ
ｎ）から１を引いた値分(ここでは１)だけデクリメント
されて１となり、ステップ１０２に戻る。なお、上記ス
テップ１０７で辞書ポインタが辞書サイズ以上になる
と、ステップ１１１，１１２において上記ステップ１０
９，１１０と同様の一致データ列長の更新処理が行われ
る。また、ステップ１０９の判別の時点で既に一致デー
タ列長（ｃｒｓｐｄ＿ｌｅｎ）に値が代入されており、
この値がテンポラリ一致データ列長（ｃｏｍｐ＿ｌｅ
ｎ）の値以上の場合は、上記ステップ１１０の処理は行
わずに、ステップ１０２に戻る。

【００３６】さて、ステップ１０２では、テンポラリ一
致データ列長（ｃｏｍｐ＿ｌｅｎ）が０に初期化される
とともに、入力データバッファポインタ（ｓｔｒ＿ｐｏ
ｉｎｔ）が入力データ列の先頭に初期化される。この時
点で、入力データ列の先頭データは“ａ”で、辞書ポイ
ンタ（ｄｉｃ＿ｐｏｉｎｔ）の値１に対応するデータは
“ｂ”であって、それ以降にも一致するデータはないの
で、ステップ１０３〜１０５のループを１回廻って、ス
テップ１０４で辞書ポインタの値が３となると、ステッ
プ１０５で辞書サイズの値３と等しくなるので、ステッ
プ１１３に進む。ステップ１１３では、一致データ列長
（ｃｒｓｐｄ＿ｌｅｎ）の値が２であるので、２以上の
条件が満たされ、ステップ１１４に進んで一致データ列
有／無フラグを“１”とする。また、この時、一致デー
タ列の先頭データの辞書上の位置（アドレス）を示す一
致データ列ポインタ（ｃｒｓｐｄ＿ｐｏｉｎｔ）の値０
及び一致データ列の長さ（バイト数）を示す一致データ
列長（ｃｒｓｐｄ＿ｌｅｎ）の値２を符号化装置７に出
力し、一致データ列“ａｂ”を辞書に出力するととも
に、１バイト出力する毎に辞書サイズカウンタ４にイン
クリメント信号を出力し、残りデータ数カウンタ５にデ
クリメント信号を出力する。そして、ステップ１１６に
進んで検索終了信号を符号化装置７と入力データバッフ
ァ１に出力し、今回の検索処理を終了する。

【００３７】符号化装置７は、同様に、この検索終了信
号をトリガーにして図４にフローチャートで示す符号化
処理を開始する。ステップ２０１で最長一致データ列検
索装置３からの一致データ列有／無フラグ１ビットを圧
縮データビットストリームとして出力する。次に、ステ
ップ２０２で上記一致データ列有／無フラグが１か否か
を判別する。今、該フラグは１であるので、ステップ２
０４に進んで、９ビットの一致データ列長（２〜２５
６）から１を引いて下位８ビット（１〜２５５）をＬＳ
Ｂから長さ指示子データサイズのビット数分順次出力す
る。今、長さ指示子データサイズは８であるので、８ビ
ット全て出力する。次に、ステップ２０５に進んで、一
致データ列ポインタ（ｃｒｓｐｄ＿ｐｏｉｎｔ）８ビッ
トをＬＳＢから順次出力する。そして、ステップ２０６
に進み、符号化終了信号を最長一致データ列検索装置３
に出力し、今回の符号化処理を終了する。このとき符号
化装置７から出力される圧縮データビットストリーム
は、一致データ列有／無フラグ１ビットと一致データ列
長８ビットと一致データ列ポインタ８ビットの計１７ビ
ットとなる。この場合、余り圧縮の意味がないが、例え
ば、入力データ列が“ａｂｃａｂｃ・・・”となる３バ
イト一致の場合では、２４ビットが１７ビットに圧縮さ
れることになる。

【００３８】以上のような処理が繰り返されて、入力デ
ータ列の残りデータ数が１２８バイト以下になると、残
りデータ数カウンタ５から出力される残りデータ数（ｒ
ｅｍ＿ｓｉｚｅ）も１２８以下となり、長さ指示子デー
タサイズジェネレータ６から出力される長さ指示子デー
タサイズ（ｌｅｍ＿ｓｉｚｅ）は７以下となる（図２参
照）。従って、一致データ列が見つかった場合の圧縮デ
ータビットストリームは、一致データ列有／無フラグ１
ビットと一致データ列長１〜７ビットと一致データ列ポ
インタ８ビットの計１０〜１６ビットとなる。具体的に
は、上記入力データ列の後尾の“ａｂｃ”が辞書バッフ
ァ２の先頭からの“ａｂｃ”と一致すると、残りデータ
数が３となって長さ指示子データサイズは２となるので
（図２参照）、一致データ列有／無フラグ１ビットと一
致データ列長２ビットと一致データ列ポインタ８ビット
の計１１ビットとなる。すなわち、３バイト（２４ビッ
ト）が１１ビットに圧縮されたことになり、従来技術で
は、この場合でも１７ビットのままであるので、本実施
例の圧縮処理の方が圧縮率が格段に良いことがわかる。

【００３９】以上のような最長一致データ列検索処理及
び符号化処理が繰り返し行われて、符号化装置７から出
力される圧縮データビットストリームのフォーマット
は、図５の示すようになる。すなわち、図５において、
Ｆｎはそれに続くデータＤｎに対する圧縮フラグ（一致
データ列有／無フラグ）１ビットで、“０”のときは非
圧縮データ、“１”のときは圧縮データを表している。
また、データＤｎは上記フラグＦｎに対するデータで、
フラグＦｎが“０”の時は生データ１バイト（ＬＳＢか
ら８ビット）、“１”のときは圧縮データが８〜１６ビ
ットの範囲となる。このフラグＦｎ＝１の時の圧縮デー
タＤｎは、１〜８ビット可変長の一致データ列長（ｃｒ
ｓｐｄ＿ｌｅｎ）がＬＳＢから順に並べられ、その後に
８ビットの一致データ列ポインタ（ｃｒｓｐｄ＿ｐｏｉ
ｎｔ）がＬＳＢから順に並べられる。この８ビットの一
致データ列ポインタ（ｃｒｓｐｄ＿ｐｏｉｎｔ）は一致
データ列の辞書内の先頭アドレスを示しており、１〜８
ビットの一致データ列長（ｃｒｓｐｄ＿ｌｅｎ）は、１
〜２５５で２〜２５６の長さを表し、図２に示したよう
に残りデータ数に対応している。すなわち、残りデータ
数が１２８バイト以下になると、一致データ列長（ｃｒ
ｓｐｄ＿ｌｅｎ）の対応する下位ビットのみが必要とな
り、それ以外の上位ビットは冗長ビットなって不要とな
り、長さ指示子データサイズは１〜７ビットとなる。従
って、その分だけ従来技術に比べて圧縮率が向上する。

【００４０】従って、このデータ圧縮装置（方法）を予
めデータ数が分かっている通信装置や記憶装置に適用す
ることにより、従来技術に比して転送データ量や記憶デ
ータ量が少なくなるので、転送速度の向上や記憶容量の
削減を図ることができる。特に、本願発明の対象とする
スライド辞書法が不得意とする小さいサイズ（辞書サイ
ズと比して）のデータ列を圧縮する際に効果的である。
また、記憶容量の削減に関しては、ＲＯＭ等の不揮発性
半導体記憶素子を用いる例えばゲームカセット等におい
て、高価な記憶素子を効率的に使用することができる。
また、このゲームカセットにおいては、小さいサイズの
プログラムやデータが多数格納されるので、更に効果的
である。

【００４１】なお、上記実施例では、圧縮の高速化を図
るためデータ圧縮装置を実現したが、高速性が余り要求
されない分野、例えばゲームカセット用ＲＯＭへのプロ
グラムやデータの書き込み等においては、上述した処理
をソフトウエアで実現し、コンピュータにより実行する
ようにしても良い。

【００４２】図６は、本発明の一実施例に係るデータ伸
長装置を示すブロック図であり、上述したデータ圧縮装
置により圧縮されて転送又は記憶された圧縮データビッ
トストリームを伸長するものである。

【００４３】１１は、本発明における復号化手段に相当
するデマルチプレクサであり、従来からあるデマルチプ
レクサに後述する本願特有の機能が付加されたものであ
る。このデマルチプレクサ１１は、図５に示した圧縮デ
ータビットストリームを入力とし、入力データの先頭ビ
ットにあるフラグＦｎで圧縮か非圧縮かを判断し、必要
なビット数のデータ（Ｄｎ）を入力する。すなわち、非
圧縮（Ｆｎ＝０）であれば、続く８ビットを蓄えてバイ
トデータとして伸長データ列に出力するとともに、辞書
バッファ１２に書き込む。なお、伸長データ列の出力は
出力データ同期用クロックとともに行われ、辞書バッフ
ァ１２への書き込みはライトクロックとシフトクロック
により行われる。この辞書バッファ１２への書込みは、
辞書バッファ１２に空きがあれば（ｄｉｃ＿ｓｉｚｅ＜
２５６）、ライトアドレスは辞書サイズｄｉｃ＿ｓｉｚ
ｅとなり、書き込んだ後、辞書サイズカウンタ１３にイ
ンクリメント信号を出力し、残りデータ数カウンタ１４
にデクリメント信号を出力する。また、辞書バッファ１
２が満杯であれば（ｄｉｃ＿ｓｉｚｅ＝２５６）、まず
辞書データをアドレス００ｈに向かってシフト（Ｄ
（ｎ）＝Ｄ（ｎ＋１），ｎ＝０，１，・・・，２５４）
してから、アドレスＦＦｈに書き込む。一方、圧縮（Ｆ
ｎ＝１）の時は、これに続くデータＤｎのビット数を、
長さ指示子データサイズジェネレータ１５の出力する長
さ指示子データサイズを参照して“長さ指示子データサ
イズ（ｌｅｎ＿ｓｉｚｅ）＋８”と決める。そして、先
ず長さ指示子データサイズ（ｌｅｎ＿ｓｉｚｅ）のビッ
ト数分入力し、８ビットに足りない上位（８−ｌｅｎ＿
ｓｉｚｅ）ビットに“０”を補充し、８ビットの一致デ
ータ列長（ｃｒｓｐｄ＿ｌｅｎ）を構成する。さらに続
く８ビットを入力し、１バイトの一致データ列ポインタ
（ｃｒｓｐｄ＿ｐｏｉｎｔ）を構成する。このようにし
て得られた一致データ列長（ｃｒｓｐｄ＿ｌｅｎ）と一
致データ列ポインタ（ｃｒｓｐｄ＿ｐｏｉｎｔ）を元に
して、辞書バッファ１２内の一致データ列を参照する。
まず、一致データ列ポインタ（ｃｓｒｐｄ＿ｐｏｉｎ
ｔ）の示すアドレスの辞書データＤ（ｃｓｒｐｄ＿ｐｏ
ｉｎｔ）を読み出す。このデータを伸長データとして出
力し、一致データ列長（ｃｒｓｐｄ＿ｌｅｎ）をデクリ
メントする。また、伸長されたデータＤ（ｃｓｒｐｄ＿
ｐｏｉｎｔ）を辞書バッファ１２に書き込む。上記同
様、辞書バッファ１２に空きがあれば（ｄｉｃ＿ｓｉｚ
ｅ＜２５６）、ライトアドレスは辞書サイズｄｉｃ＿ｓ
ｉｚｅとなる（Ｄ（ｄｉｃ＿ｓｉｚｅ）＝Ｄ（ｃｒｓｐ
ｄ＿ｐｏｉｎｔ）。そして、辞書サイズカウンタ１３に
インクリメント信号を出力するとともに、残りデータ数
カウンタ１４にデクリメント信号を出力し、一致データ
列ポインタ（ｃｒｓｐｄ＿ｐｏｉｎｔ）をインクリメン
トする。一方、辞書バッファ１２が満杯であれば（ｄｉ
ｃ＿ｓｉｚｅ＝２５６）、まず辞書データをアドレス０
０ｈに向かってシフト（Ｄ（ｎ）＝Ｄ（ｎ＋１），ｎ＝
０，１，・・・，２５４）してから、アドレスＦＦｈに
書き込む（Ｄ（２５５）＝Ｄ（ｃｒｓｐｄ＿ｐｏｉｎ
ｔ））。そして、残りデータ数カウンタ１４にデクリメ
ント信号を出力し、一致データ列ポインタ（ｃｒｓｐｄ
＿ｐｏｉｎｔ）のインクリメントは行わない。一致デー
タ列長（ｃｒｓｐｄ＿ｌｅｎ）のデクリメント処理にお
いてボローがでたら１回の復号化処理を終了し、入力デ
ータの次のフラグのチェックを行う。すなわち、一致デ
ータ列長（ｃｒｓｐｄ＿ｌｅｎ）は、（実際の一致デー
タ列長）−１の値を表しているので、００ｈになるまで
ではなく、ボローが出てＦＦｈになるまでが実際の一致
データ列長の処理となる。

【００４４】辞書バッファ１２は、前記データ圧縮装置
の辞書バッファ２と同様なもので、データバス８ビッ
ト，アドレス８ビットで、計２５６バイトのシフトレジ
スタで構成されている。デマルチプレクサ１１からの入
力データは、上述したように、辞書バッファ１２に空き
がある時，すなわち辞書サイズ（ｄｉｃ＿ｓｉｚｅ）＜
２５６の時は、この辞書サイズ（ｄｉｃ＿ｓｉｚｅ）を
アドレスとしてラッチされる（Ｄ（ｄｉｃ＿ｓｉｚｅ）
＝入力データ）。一方、辞書バッファ１２が満杯の時，
すなわち辞書サイズ（ｄｉｃ＿ｓｉｚｅ）＝２５６の時
は、まず辞書データをアドレス００ｈに向かってシフト
（Ｄ（ｎ）＝Ｄ（ｎ＋１），ｎ＝１，２，・・・，２５
４）してからアドレスＦＦｈにラッチされる。また、デ
マルチプレクサ１１の制御により、指定されたアドレス
（ｃｒｓｐｄ＿ｐｏｉｎｔ）のデータが読み出され、デ
マルチプレクサ１１に出力する。

【００４５】辞書サイズカウンタ１３は、カウント最大
値が２５６に設定されたアップカウンタで構成され、伸
長開始時に図示しないシステムリセット信号によりリセ
ットされる。そして、上述したデマルチプレクサ１１か
らのインクリメント信号によりカウントアップし、最大
値（２５６）に達すると、以降その値を保持する。この
辞書サイズカウンタ１３からの辞書サイズ（ｄｉｃ＿ｓ
ｉｚｅ）は、デマルチプレクサ１１に出力される。

【００４６】残りデータ数カウンタ１４は、本願発明に
おいて備えられた計数手段に相当するもので、本伸長装
置の利用分野で想定される最大のデータ数が設定可能な
ビット数のダウンカウンタで構成され、伸長開始前に入
力データ列のデータ数がセットされ、以降、デマルチプ
レクサ１１からのデクリメント信号によりカウントダウ
ンし、残りデータ数（ｒｅｍ＿ｓｉｚｅ）を長さ指示子
データサイズジェネレータ１５に出力する。

【００４７】長さ指示子データサイズジェネレータ１５
は、本願発明において備えられた判別手段に相当するも
ので、ゲート回路からなるエンコーダで構成され、上記
残りデータ数カウンタ１４からの出力値（残りデータ
数）を元にして対応する長さ指示子データサイズ（ｌｅ
ｎ＿ｓｉｚｅ），すなわち一致データ列長のビット数を
生成し、デマルチプレクサ１１に出力する。この長さ指
示子データサイズジェネレータ１５の入力（残りデータ
数）と出力（長さ指示子データサイズ）の対応関係は図
２に示した通りである。

【００４８】次に、このように構成されたデータ伸長装
置の動作について説明する。ここでは、前記データ圧縮
装置の動作説明で用いた具体例による圧縮データビット
ストリームを伸長するものとして説明する。この圧縮デ
ータビットストリームは、図５のＦｎ，Ｄｎで示すと、
Ｆ０＝０，Ｄ０＝“ａ”，Ｆ１＝０，Ｄ１＝“ｂ”，Ｆ
２＝０，Ｄ２＝“ｃ”，Ｆ３＝１，Ｄ３＝００００００
０１００００００００，Ｆ４＝０，Ｄ４＝“ｄ”，・・
・，Ｆｍａｘ＝１，Ｄｍａｘ＝１０００００００００と
なる。なお、伸長開始時には、辞書サイズカウンタ１３
がシステムリセット信号によりリセットされて０とな
り、また、残りデータ数カウンタ１４に入力データ数と
して２５６がセットされている。

【００４９】本データ伸長装置が起動され、上述した圧
縮データビットストリームがデマルチプレクサ１１に入
力されると、デマルチプレクサ１１は図７にフローチャ
ートで示す処理を開始する。すなわち、ステップ３０１
で入力データ列の先頭ビット（フラグＦ０）が１か否か
を判別する。今、入力データの先頭ビットＦ０＝０であ
るので、ステップ３０２に進み、次の８ビット（Ｄ０＝
“ａ”）を入力し、バイトデータとして伸長データ列に
出力する。次に、ステップ３０３で辞書バッファ１２に
空きが有るか否かを辞書サイズ（ｄｉｃ＿ｓｉｚｅ）よ
り判別し、空きが有れば（ｄｉｃ＿ｓｉｚｅ＜２５
６）、ステップ３０４に進んで、辞書サイズカウンタ１
３の示す辞書サイズ（ｄｉｃ＿ｓｉｚｅ）をアドレスと
して辞書バッファ１２に上記バイトデータを書き込む。
今、辞書サイズ（ｄｉｃ＿ｓｉｚｅ）は０であるので、
辞書バッファ１２のアドレス００ｈにデータＤ０＝
“ａ”が書き込まれる。この後、ステップ３０５で辞書
サイズカウンタ１３にインクリメント信号を出力してカ
ウントアップし、ステップ３０７で残りデータ数カウン
タ１４にデクリメント信号を出力してカウントダウン
し、ステップ３０１にもどる。なお、辞書バッファ１２
に空きがなければ（ｄｉｃ＿ｓｉｚｅ＝２５６）、ステ
ップ３０６に進み、辞書データをアドレス００ｈに向か
ってシフトしてからアドレスＦＦｈに書き込む。

【００５０】次の入力データのフラグＦ１＝０，データ
Ｄ１＝“ｂ”，その次のフラグＦ２＝０，データＤ２＝
“ｃ”であるので、ステップ３０１〜３０５，３０７を
２回繰り返し、伸長データ列には“ａ”の次に“ｂ”，
“ｃ”が出力される。また、今、辞書バッファ１２に
は、アドレス００ｈから“ａ”，“ｂ”，“ｃ”が順に
格納され、辞書サイズカウンタ１３から出力される辞書
サイズ（ｄｉｃ＿ｓｉｚｅ）は３となり、残りデータ数
カウンタ１４から出力される残りデータ数（ｒｅｍ＿ｓ
ｉｚｅ）は２５３となり、長さ指示子データサイズジェ
ネレータ１５から出力される長さ指示子データサイズ
（ｌｅｎ＿ｓｉｚｅ）は８のままとなる（図２参照）。

【００５１】さて、次の入力データの先頭ビットである
フラグＦ３＝１となるので、ステップ３０１からステッ
プ３０８に進み、長さ指示子データサイズのビット数
分，すなわち８ビット（０００００００１）を入力し、
そのまま８ビットの一致データ列長を構成する。次のス
テップ３０９では、８ビット（００００００００）を入
力し、１バイトの一致データ列ポインタを構成する。次
に、ステップ３１０に進み、辞書バッファ１２から上記
一致データ列ポインタ００ｈのデータ“ａ”を読み出し
て、伸長データとして出力する。そして、ステップ３１
１で一致データ列長（０００００００１）をデクリメン
トする。また、ステップ３１２で残りデータ数カウンタ
１４にデクリメント信号を出力する。次に、ステップ３
１３で、辞書バッファ１２に空きが有るか否かを辞書サ
イズ（ｄｉｃ＿ｓｉｚｅ）より判別し、空きが有れば
（ｄｉｃ＿ｓｉｚｅ＜２５６）、ステップ３１４に進ん
で、辞書サイズカウンタ１３の示す辞書サイズ（ｄｉｃ
＿ｓｉｚｅ）をアドレスとして辞書バッファ１２に伸長
データを書き込む。今、辞書サイズ（ｄｉｃ＿ｓｉｚ
ｅ）は３であるので、辞書バッファ１２のアドレス０３
ｈに伸長データ“ａ”が書き込まれる。この後、ステッ
プ３１５で、辞書サイズカウンタ１３にインクリメント
信号を出力してカウントアップし、ステップ３１６で一
致データ列ポインタ（００ｈ）をインクリメントして、
ステップ３１８に進む。なお、辞書バッファ１２に空き
がなければ（ｄｉｃ＿ｓｉｚｅ＝２５６）、ステップ３
１７に進み、辞書データをアドレス００ｈに向かってシ
フトしてからアドレスＦＦｈに書き込み、一致データ列
ポインタをインクリメントすることなく、ステップ３１
８に進む。

【００５２】ステップ３１８では、一致データ列長がボ
ローが出たか否かが判別される。一致データ列長は００
ｈでまだボローは出ていないので、ステップ３１０に戻
る。そして、上記と同様に、辞書バッファ１２から一致
データ列ポインタ０１ｈのデータ“ｂ”を読み出して、
伸長データとして出力するとともに（ステップ３１
０）、一致データ列長００ｈをデクリメントし（ステッ
プ３１１）、また、残りデータ数カウンタ１４にデクリ
メント信号を出力（ステップ３１２）する等して、上記
データ“ｂ”を辞書バッファ１２に書き込む（ステップ
３１４）。そして、辞書サイズカウンタ１３にインクリ
メント信号を出力し（ステップ３１５）、一致データ列
ポインタをインクリメントし（ステップ３１６）、ステ
ップ３１８に進む。ここで、一致データ列長は上記ステ
ップ３１０におけるデクリメントによりボローが出でＦ
Ｆｈとなっているので、最初のステップ３０１に戻る。
そして、入力データ列の次の先頭ビット（フラグＦ４）
は０であるので、ステップ３０２に進み、上記と同様な
処理が繰り返される。

【００５３】このような処理を繰り返して、入力データ
の先頭ビットＦｍａｘ＝１となると、ステップ３０１か
らステップ３０８に進むが、このステップ３０８におい
て、長さ指示子データサイズのビット数分入力する。こ
こで、残りデータ数（ｒｅｍ＿ｓｉｚｅ）は３となり、
長さ指示子データサイズジェネレータ１５からの長さ指
示子データサイズ（ｌｅｎ＿ｓｉｚｅ）は２となるの
で、次の２ビット，すなわち“１０”を入力し、８ビッ
トに足りない上位ビットに“０”を補充して、８ビット
の一致データ列長（００００００１０）を構成する。次
のステップ３０９では、８ビット（００００００００）
を入力し、１バイトの一致データ列ポインタを構成す
る。次に、ステップ３１０に進み、辞書バッファ１２か
ら上記一致データ列ポインタ００ｈのデータ“ａ”を読
み出して、伸長データとして出力する。そして、ステッ
プ３１１で一致データ列長（００００００１０）をデク
リメントする。また、ステップ３１２で残りデータ数カ
ウンタ１４にデクリメント信号を出力する。次に、ステ
ップ３１３で辞書バッファ１２に空きが有るか否かを辞
書サイズ（ｄｉｃ＿ｓｉｚｅ）より判別し、空きが有れ
ば（ｄｉｃ＿ｓｉｚｅ＜２５６）、ステップ３１４に進
んで、辞書サイズカウンタ１３の示す辞書サイズ（ｄｉ
ｃ＿ｓｉｚｅ）をアドレスとして辞書バッファ１２に伸
長データを書き込む。今、辞書サイズ（ｄｉｃ＿ｓｉｚ
ｅ）は２５３であるので、辞書バッファ１２のアドレス
ＦＤｈに伸長データ“ａ”が書き込まれる。この後、ス
テップ３１５で辞書サイズカウンタ１３にインクリメン
ト信号を出力してカウントアップし、ステップ３１６で
一致データ列ポインタ（００ｈ）をインクリメントし
て、ステップ３１８に進む。今、一致データ列長は０１
ｈであるので、上記ステップ３１０〜３１６を２回繰り
返し、一致データ列長がＦＦｈ（ボロー）となると、全
ての入力データの復号化処理が終了し、伸長データ列と
して“ａｂｃａｂｄ・・・ａｂｃ”が得られ、前述した
データ圧縮装置で圧縮する前の入力データ列が復元でき
たことになる。

【００５４】なお、上記実施例では、伸長処理の高速化
を図るためデータ伸長装置を実現したが、高速性が余り
要求されない分野においては、上述した処理をソフトウ
エアで実現し、コンピュータにより実行するようにして
も良い。

【００５５】また、予めデータ数が分かっており、ＲＯ
ＭやバッテリーバックアップされたＲＡＭ等の高価な不
揮発性半導体記憶手段に、小さいサイズのプログラムや
データが多数格納され、高速な読み出しが要求されるゲ
ームカセット等においては、上述したデータ伸長装置を
組み込むことにより、上記各条件が満たされるので、特
に効果的である。

【００５６】また、上記各実施例においては、データ圧
縮装置及びデータ伸長装置の辞書バッファ２、１２にシ
フトレジスタを用いた場合について示したが、これらの
辞書バッファに通常のメモリを用い、書き込みアドレス
を順次サイクリックに更新することにより、辞書内容を
上書きにより順次更新し、これによりスライド辞書を実
現するようにしても良い。

【００５７】

【発明の効果】請求項１記載の発明によれば、スライド
辞書法を用いてデータの圧縮を行うデータ圧縮方法にお
いて、入力データ列の残りデータ数を計数し、残りデー
タ数が辞書容量の範囲内の既定の上限以下となった場合
には、その残りデータ数を２進数で表現可能な最小のビ
ット数に長さ指示子のビット数を設定し、設定した長さ
指示子のビット数にて符号化を行うようにしたので、入
力データ列の後部で、長さ指示子で表わされる上限の１
／２以下の長さ分のデータに対する圧縮データの冗長な
部分を取り除くことができ、圧縮率を従来よりも高くす
ることができる効果がある。従って、この発明を予めデ
ータ数の分かっている通信装置や記憶装置に適用するこ
とにより、従来技術に比して転送データ量や記憶データ
量が少なくなるので、転送速度の向上や記憶容量の削減
を図ることができる。特に、本願発明の対象とするスラ
イド辞書法が不得意とする小さいサイズ（辞書サイズと
比して）のデータ列を圧縮する際に効果的である。

【００５８】また、請求項２記載の発明によれば、スラ
イド辞書法を用いてデータの圧縮を行うデータ圧縮装置
において、入力データ列の残りデータ数を計数する計数
手段と、この計数手段で計数された残りデータ数に基づ
き、その残りデータ数が辞書容量の範囲内の既定の上限
以下となったときに当該データ数を２進数で表現可能な
最小のビット数に長さ指示子のビット数を設定する設定
手段と、この設定手段で設定された長さ指示子のビット
数にて符号化を行う符号化手段とを備えたので、上記請
求項１と同様な効果が得られるとともに、圧縮を高速で
行うことができる効果がある。

【００５９】また、請求項３記載の発明によれば、不揮
発性半導体記憶手段に書き込まれるプログラムやデータ
を圧縮するので、高価な記憶素子を効率的に使用するこ
とができる効果がある。

【００６０】一方、請求項４記載の発明によれば、上記
請求項１記載のデータ圧縮方法または請求項２記載のデ
ータ圧縮装置によって圧縮された圧縮データを伸長する
データ伸長方法であって、伸長データの残りデータ数を
計数し、残りデータ数が辞書容量の範囲内の既定の上限
以下となった場合には、その残りデータ数を２進数で表
現可能な最小のビット数から長さ指示子のビット数を判
別し、判別した長さ指示子のビット数を用いて復号化を
行うようにしたので、上記により圧縮されたデータを伸
長することができる効果がある。

【００６１】また、請求項５記載の発明によれば、上記
請求項１記載のデータ圧縮方法または請求項２記載のデ
ータ圧縮装置によって圧縮された圧縮データを伸長する
データ伸長装置であって、伸長データの残りデータ数を
計数する計数手段と、この計数手段で計数された残りデ
ータ数に基づき、その残りデータ数が辞書容量の範囲内
の既定の上限以下となったときに当該データ数を２進数
で表現可能な最小のビット数から長さ指示子のビット数
を判別する判別手段と、この判別手段で判別された長さ
指示子のビット数を用いて復号化を行う復号化手段とを
備えたので、上記請求項４と同様の効果を有するととも
に、伸長を高速に行うことができる効果がある。

【００６２】また、請求項６記載の発明によれば、不揮
発性半導体記憶手段から読み出されるプログラムやデー
タの圧縮データを高速に伸長できる効果がある。

【図面の簡単な説明】

【図１】本発明の一実施例に係るデータ圧縮装置を示す
ブロック図。

【図２】上記実施例における残りデータ数と長さ指示子
データサイズとの対応表を示す図。

【図３】上記実施例のおける最長一致データ列検索装置
の動作を示すフローチャート。

【図４】上記実施例における符号化装置の動作を示すフ
ローチャート。

【図５】上記実施例における圧縮データビットストリー
ムの説明図。

【図６】本発明の一実施例に係るデータ伸長装置を示す
ブロック図。

【図７】上記実施例のおけるデマルチプレクサの動作を
示すフローチャート。

【符号の説明】

２，１２ 辞書バッファ ３ 最長一致データ列検索装置 ４，１３ 辞書サイズカウンタ ５，１４ 残りデータ数カウンタ ６，１５ 長さ指示子データサイズジェネレータ ７ 符号化装置 １１ デマルチプレクサ

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平１−314430（ＪＰ，Ａ) 特開 平２−233025（ＪＰ，Ａ) 特開 平３−68219（ＪＰ，Ａ) 特開 平３−204232（ＪＰ，Ａ) 特開 平３−204233（ＪＰ，Ａ) 特開 平３−78322（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) H03M 7/40

Claims (6)

(57)【特許請求の範囲】
1. 【請求項１】 入力データ列のうち、各時点で符号化の
   対象となるデータの近傍のデータ列を所定数量まで記憶
   手段に格納し、格納されたデータ列を符号化のために参
   照する辞書として用い、各時点で符号化の対象となって
   いる位置から始まるデータ列に一致する上記辞書内のデ
   ータ列で、上記所定数量の範囲内の既定の上限以下で最
   も長い一致データ列を検索し、当該一致データ列が見つ
   かれば、一致を示すフラグと、見つかったデータ列の辞
   書内の位置を示すポインタと、その長さを示す長さ指示
   子とから符号語を構成するとともに、上記一致データ列
   が見つからなければ、不一致を示すフラグと、符号化の
   対象となっているデータそのものとから符号語を構成す
   ることにより、データの圧縮を行うデータ圧縮方法にお
   いて、 入力データ列の残りデータ数を計数し、残りデータ数が
   上記上限以下となった場合には、その残りデータ数を２
   進数で表現可能な最小のビット数に上記長さ指示子のビ
   ット数を設定し、設定した長さ指示子のビット数にて符
   号化を行うことを特徴とするデータ圧縮方法。
2. 【請求項２】 入力データ列のうち、各時点で符号化の
   対象となるデータの近傍のデータ列を所定数量まで記憶
   手段に格納し、格納されたデータ列を符号化のために参
   照する辞書として用い、各時点で符号化の対象となって
   いる位置から始まるデータ列に一致する上記辞書内のデ
   ータ列で、上記所定数量の範囲内の既定の上限以下で最
   も長い一致データ列を検索し、当該一致データ列が見つ
   かれば、一致を示すフラグと、見つかったデータ列の辞
   書内の位置を示すポインタと、その長さを示す長さ指示
   子とから符号語を構成するとともに、上記一致データ列
   が見つからなければ、不一致を示すフラグと、符号化の
   対象となっているデータそのものとから符号語を構成す
   ることにより、データの圧縮を行うデータ圧縮装置にお
   いて、 入力データ列の残りデータ数を計数する計数手段と、こ
   の計数手段で計数された残りデータ数に基づき、その残
   りデータ数が上記上限以下となったときに当該データ数
   を２進数で表現可能な最小のビット数に上記長さ指示子
   のビット数を設定する設定手段と、この設定手段で設定
   された長さ指示子のビット数にて符号化を行う符号化手
   段とを備えたことを特徴とするデータ圧縮装置。
3. 【請求項３】 不揮発性半導体記憶手段に書き込まれる
   プログラムやデータを圧縮することを特徴とする請求項
   ２記載のデータ圧縮装置。
4. 【請求項４】 請求項１記載のデータ圧縮方法または請
   求項２記載のデータ圧縮装置によって圧縮された圧縮デ
   ータを入力し、符号語に含まれるフラグが不一致を示す
   ときは、当該符号語に含まれる他のデータを取り出して
   復号化するとともに、当該データを復号化のために参照
   する所定数量の辞書に入力し、また、符号語に含まれる
   フラグが一致を示すときは、当該符号語に含まれるポイ
   ンタと長さ指示子とを用いて上記辞書内から対応するデ
   ータを取り出して復号化するとともに、当該データを上
   記辞書に入力することにより、圧縮データの伸長を行う
   データ伸長方法であって、 伸長データの残りデータ数を計数し、残りデータ数が上
   記所定数量の範囲内の既定の上限以下となった場合に
   は、その残りデータ数を２進数で表現可能な最小のビッ
   ト数から上記長さ指示子のビット数を判別し、判別した
   長さ指示子のビット数を用いて復号化を行うことを特徴
   とするデータ伸長方法。
5. 【請求項５】 請求項１記載のデータ圧縮方法または請
   求項２記載のデータ圧縮装置によって圧縮された圧縮デ
   ータを入力し、符号語に含まれるフラグが不一致を示す
   ときは、当該符号語に含まれる他のデータを取り出して
   復号化するとともに、当該データを復号化のために参照
   する所定数量の辞書に入力し、また、符号語に含まれる
   フラグが一致を示すときは、当該符号語に含まれるポイ
   ンタと長さ指示子とを用いて上記辞書内から対応するデ
   ータを取り出して復号化するとともに、当該データを上
   記辞書に入力することにより、圧縮データの伸長を行う
   データ伸長装置であって、 伸長データの残りデータ数を計数する計数手段と、この
   計数手段で計数された残りデータ数に基づき、その残り
   データ数が上記所定数量の範囲内の既定の上限以下とな
   ったときに当該データ数を２進数で表現可能な最小のビ
   ット数から上記長さ指示子のビット数を判別する判別手
   段と、この判別手段で判別された長さ指示子のビット数
   を用いて復号化を行う復号化手段とを備えたことを特徴
   とするデータ伸長装置。
6. 【請求項６】 プログラムやデータの圧縮データが記憶
   された不揮発性半導体記憶手段から読み出される圧縮デ
   ータを伸長することを特徴とする請求項５記載のデータ
   伸長装置。