(57)【特許請求の範囲】
【請求項１】
現在の入力データを入力する入力手段と、過去の入力データを保持する保持手段と、前記現在の入力データとの比較対象となる過去の入力データの全ての出現位置に対応して設けられ、前記現在の入力データと前記過去の入力データとの比較を、前記過去の入力データの全ての出現位置に対して同時に行うことにより、最長一致長及び最長一致位置を求める比較手段と、同一の入力データ列の繰り返し回数をカウントするカウント手段と、前記繰り返し回数を前記入力データ列の符号として出力する出力手段とを備えることを特徴とするデータ圧縮装置。
【請求項２】
前記最長一致長及び前記最長一致位置を格納するデータ領域のビット長は、入力データのビット長と同一であること特徴とする請求項１に記載のデータ圧縮装置。
【請求項３】
前記入力手段及び前記保持手段は、データ列のバイトシフトを行うバレルシフタを備え、前記バレルシフタは、前記現在の入力データ及び前記過去の入力データの一致長分のシフトを１度に行うことを特徴とする請求項１または２に記載のデータ圧縮装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータ圧縮装置に関し、特に、Ｚｉｖ−Ｌｅｍｐｅｌ符号（ＬＺ符号）による圧縮処理を高速に行う場合に適用して好適なものである。
【０００２】
【従来の技術】
従来のＬＺ符号化では、過去のデータの出現位置をハッシュテーブルを用いて検索するものがあった。また、過去のデータと入力中のデータとを１バイト単位で比較するハードコンパレータ方式を用いることにより、圧縮処理の高速化を図るものがあった。
【０００３】
【発明が解決しようとする課題】
しかしながら、ハッシュテーブル方式では、処理速度が遅いという問題がある。また、ハードコンパレータ方式は、１バイト単位のコンパレートであり、動作クロック以上の処理速度で処理できないという問題がある。さらに、従来の方式では、プリント時の余白エリアの最大圧縮率が低いという問題がある。
【０００４】
そこで、本発明の目的は、データ圧縮を高速に行うことが可能なデータ圧縮装置を提供することである。
【０００５】
【課題を解決するための手段】
上述した課題を解決するために、本発明によれば、比較対象となる過去の入力データの全ての出現位置に対応した比較手段を設けるようにしている。また、本発明の一態様によれば、同一の入力データ列の繰り返し回数を入力データ列の符号として出力するようにしている。
【０００６】
このことにより、過去の入力データ列と現在の入力データ列との１回の比較動作により、過去のデータ列の中から最長一致長及び最長一致位置を求めることが可能となり、最長一致長及び最長一致位置を求める際に、過去のデータ列の出現位置を１つ１つ溯りながら比較処理を何度も行う必要がなくなることから、ＬＺ符号によるデータ圧縮を高速に行うことが可能となる。さらに、プリント時の余白部分については、同一の入力データ列の繰り返しとなるため、余白部分のデータ圧縮を効率的に行うことが可能となる。
【０００７】
また、本発明の一態様によれば、最長一致長及び最長一致位置を格納するデータ領域のビット長は、入力データのビット長と同一である。
このことにより、現在の入力データ列と過去の入力データ列とが一致した時に、ＬＺ符号を出力し、現在の入力データ列と過去の入力データ列とが一致しない時に、現在の入力データをそのまま出力した場合においても、生データ及びＬＺ符号を同一のデータフォーマット上で出力することか可能となり、効率的なデータ圧縮を行うことが可能となる。
【０００８】
また、本発明の一態様によれば、過去の入力データ及び現在の入力データの一致長分のシフトを、バレルシフタを用いて行うようにしている。
このことにより、過去のデータ列及び現在の入力データ列の一致長分のシフトを１度に行うことが可能となり、ＬＺ符号によるデータ圧縮を高速に行うことが可能となる。
【００１０】
【発明の実施の形態】
以下、本発明の一実施例に係わるデータ圧縮装置について図面を参照しながら説明する。図１は、本発明の第１実施例に係わるデータ圧縮方法を説明する図である。図１において、１バイト単位の入力データ列を、過去の入力データ列と比較する。そして、過去の入力データ列の中に現在の入力データ列と一致するものがあれば、一致したかどうかを示すフラグデータを“１”に設定する。そして、入力データ列と一致した部分のうち、一致長の最も長い部分を一致位置ｐｏｓと一致長ｌｅｎで置き換える。
【００１１】
例えば、過去の入力データ列（ヘキサで示す）として、“０２、０５、０８、０Ｃ、０Ｂ、０Ａ、０３、０４、０５、・・・”が入力され、現在の入力データ列として、“０Ａ、０Ｂ、０Ｃ、１Ａ、１Ｂ、０Ｄ、・・・”が入力されたものとすると、現在の入力データ列と過去の入力データ列とを比較する。ここで、最長一致時のデータが８バイトまでに制限されているものとすると、１バイト分のフラグデータと、８バイト分のデータＤ０〜Ｄ７を用意し、データＤ０〜Ｄ７をフラグデータの各ビット値とリンクさせる。そして、現在のデータ列の“０Ａ、０Ｂ、０Ｃ”の部分が過去のデータ列と一致したものとすると、フラグデータの７ビット目を“１”に設定する。また、データＤ０の上位３ビット分を一致長ｌｅｎ、データＤ０の下位５ビット分を一致位置ｐｏｓに割り当て、現在のデータ列の“０Ａ、０Ｂ、０Ｃ”の部分の符号として、一致位置ｐｏｓ＝５及び一致長ｌｅｎ＝３を表す符号をデータＤ０として出力する。
【００１２】
次に、現在の入力データ列及び過去の入力データ列を一致長ｌｅｎ＝３つだけシフトする。そして、シフト後の“１Ａ、１Ｂ、０Ｄ、・・・”という現在の入力データ列を、シフト後の“０Ｃ、０Ｂ、０Ａ、０３、０４、０５、・・・”という過去の入力データ列と比較する。ここで、現在の入力データ列の“１Ａ”というデータは、過去のデータ列のいずれのデータとも一致しない。この場合、フラグデータの６ビット目を“０”に設定するとともに、現在の入力データ列の“１Ａ”の符号をそのままデータＤ１として出力する。なお、“１Ａ”は１バイトのデータであり、一致長ｌｅｎ及び一致位置ｐｏｓを示すデータも１バイトである。このため、一致長ｌｅｎ及び一致位置ｐｏｓを示すデータを格納するデータＤ０〜Ｄ７の領域を、入力データをそのままデータＤ０〜Ｄ７に格納する場合に用いることが可能となり、データＤ０〜Ｄ７の領域を有効に利用することができる。以上の処理をデータＤ０〜Ｄ７について行い、１バイト分のフラグデータと８バイト分の圧縮データとが１組となる７２ｂｉｔの出力データを生成する。
【００１３】
図２は、本発明の一実施例に係わるデータ圧縮装置のシステム構成を示すブロック図である。図２において、ＣＰＵ１のプログラム２及びワークＲＡＭ３が設けられ、ＣＰＵ１は、Ｉ／Ｏポート４、５を介して圧縮回路６を制御する。なお、ＣＰＵ１による圧縮回路６の制御は、Ｄｒｅｑ信号及びＤａｃｋ信号を用いたデータ入出力制御であり、終了はｅｎｄ信号を用いる。また、圧縮回路６へのデータ入力Ｄｉｎは６４ｂｉｔ、圧縮回路６からのデータ出力Ｄｏｕｔは７２ビットである（なお、図２において、太線はバイト単位のデータを示している。以下の図５〜１０、図１３、図１８、図１９も同様）。圧縮回路６は、ＬＺ符号によるデータ圧縮を行う。ここで、圧縮回路６は、過去の入力データＤｉｎの中から現在の入力データＤｉｎとの一致をサーチするコンパレータを、比較対象となる過去の入力データＤｉｎの全ての出現位置に対して備えている。
【００１４】
図３は、図２のデータ圧縮装置のデータ入力シーケンスを示すフローチャートである。図３において、ＣＰＵ１は、圧縮回路６からのｉＤｒｅｑ（データ入力要求）がある度に（ステップＳ１）、８ｂｉｔ分の入力データＤｉｎを圧縮回路６に出力するとともに、ｉＤａｃｋ（データ入力許可）を出力する（ステップＳ２）。そして、ＣＰＵ１は、圧縮対象となる全てのデータの出力が終了すると（ステップＳ３）、ｉＥＮＤ（データ入力の終了）を圧縮回路６に出力する（ステップＳ４）。
【００１５】
図４は、図２のデータ圧縮装置のデータ出力シーケンスを示すフローチャートである。図４において、ＣＰＵ１は、圧縮回路６からのｋＤｒｅｑ（データ出力要求）がある度に（ステップＳ１１）、７２ｂｉｔ分の出力データＤｏｕｔを圧縮回路６から読み出すとともに、ｋＤａｃｋ（データ出力許可）を圧縮回路６に出力する（ステップＳ１３）。ＣＰＵ１は、圧縮回路６からｋＥＮＤ（データ出力の終了）を受け取るまで以上の処理を続ける（ステップＳ１４）。
【００１６】
図５は、本発明の第１実施例に係わるデータ圧縮装置の圧縮回路６の構成を示すブロック図である。図５において、ｉｎｐｕｔ  ＦＩＦＯ１１は８バイト分のＦＩＦＯであり、圧縮回路６に入力された入力データＤｉｎを現在の入力データ列として保持する。スライドＦＩＦＯ１２は３２バイト分のＦＩＦＯであり、ｉｎｐｕｔ  ＦＩＦＯ１１から出力されたデータｉＦＤ０を過去の入力データ列として保持する。
【００１７】
サーチ回路１３は、ｉｎｐｕｔ  ＦＩＦＯ１１に保持されている現在の入力データ列ｉＦＤ０〜ｉＦＤ７とスライドＦＩＦＯ１２に保持されている過去の入力データ列ＳＦＤ０〜ＳＦＤ３１とを比較する。そして、一致する部分があれば、過去の入力データ列ＳＦＤ０〜ＳＦＤ３１の中の一致位置Ｍａｔｃｈ−Ｐｏｓ及び一致長Ｍａｔｃｈ−Ｌｅｎを出力するとともに、Ｍａｔｃｈ  Ｆｌａｇ＝１とする。一方、一致する部分がない場合は、Ｍａｔｃｈ  Ｆｌａｇ＝０とする。
【００１８】
ここで、サーチ回路１３は、過去の入力データ列ＳＦＤ０〜ＳＦＤ３１の全てのデータの出現位置に対応するコンパレータを備えている。そして、現在の入力データｉＦＤ０〜ｉＦＤ７をそれらの全てのコンパレータに１度に供給することにより、現在の入力データ列ｉＦＤ０〜ｉＦＤ７と過去の入力データ列ＳＦＤ０〜ＳＦＤ３１との１回の比較処理により、一致位置Ｍａｔｃｈ−Ｐｏｓ及び一致長Ｍａｔｃｈ−Ｌｅｎを算出する。このことにより、過去の入力データ列ＳＦＤ０〜ＳＦＤ３１との一致位置Ｍａｔｃｈ−Ｐｏｓ及び一致長Ｍａｔｃｈ−Ｌｅｎを算出する場合に、過去の入力データ列ＳＦＤ０〜ＳＦＤ３１を１つずつ溯りながら比較処理を行う必要がなくなり、一致位置Ｍａｔｃｈ−Ｐｏｓ及び一致長Ｍａｔｃｈ−Ｌｅｎを高速に算出することが可能となる。
【００１９】
出力回路１４は、Ｍａｔｃｈ  Ｆｌａｇ＝１の場合は、一致位置Ｍａｔｃｈ−Ｐｏｓ及び一致長Ｍａｔｃｈ−Ｌｅｎからなる１バイトの圧縮データを生成し、Ｍａｔｃｈ  Ｆｌａｇ＝０の場合は、ｉｎｐｕｔ  ＦＩＦＯ１１から出力された１バイトのデータｉＦＤ０をそのまま用いることにより、１バイト分のフラグデータと８バイト分の圧縮データが１組となる９バイトの出力データＤｏｕｔを生成する。そして、ＣＰＵ１とのｋＤｒｅｑ、ｋＤａｃｋ及びｋｅｎｄ信号の通信結果に基づいて、出力データＤｏｕｔをＣＰＵ１に送信する。
【００２０】
シーケンサ１５は、ＣＰＵ１とのｉＤｒｅｑ、ｉＤａｃｋ及びｉｅｎｄ信号の通信結果に基づいて、ｉｎｐｕｔ  ＦＩＦＯ１１、スライドＦＩＦＯ１２及び出力回路１４のデータの入出力制御を行う。
【００２１】
図６は、図５の圧縮回路６のｉｎｐｕｔ  ＦＩＦＯ１１の構成例を示すブロック図である。図６において、８バイト分のラッチ２１ａ〜２１ｃが設けられ、各ラッチ２１ａ〜２１ｃは、セレクタ２２ａ、２２ｂ、・・・を介して次段のラッチ２１ａ〜２１ｃに接続されている。各セレクタ２２ａ、２２ｂ、・・・は、Ｓｈｉｆｔ  Ｍｏｄｅ＝０の場合、ｉｎｐｕｔ  ＦＩＦＯ１１に入力されたデータＤｉｎを選択して、次段のラッチ２１ａ〜２１ｃに出力する。一方、ＳｈｉｆｔＭｏｄｅ＝１の場合、前段のラッチ２１ａ〜２１ｃから出力された入力データｉＦＤ０〜ｉＦＤ７を選択して、次段のラッチ２１ａ〜２１ｃに出力する。ラッチ２１ａ〜２１ｃは、入力データｉＦＤ０〜ｉＦＤ７を保持する。そして、Ｓｈｉｆｔ  Ｍｏｄｅ＝１の場合、ｉ−ｓｆｔＣＬＫが入力されるごとに、現在保持している入力データｉＦＤ０〜ｉＦＤ７をセレクタ２２ａ、２２ｂ、・・・を介して次段のラッチ２１ａ〜２１ｃにシフトする。一方、Ｓｈｉｆｔ  Ｍｏｄｅ＝０の場合、ｉｎｐｕｔ  ＦＩＦＯ１１に入力されたデータＤｉｎが、Ｌ０〜Ｌ７で選択されたラッチ２１ａ〜２１ｃにラッチされる。
【００２２】
図７は、図５の圧縮回路６のスライドＦＩＦＯ１２の構成例を示すブロック図である。図７において、３２バイト分のラッチ３１ａ〜３１ｃが設けられ、各ラッチ３１ａ〜３１ｃは、次段のラッチ３１ａ〜３１ｃに接続されている。ここで、ラッチ３１ａ〜３１ｃは、過去の入力データＳＦＤ３１〜ＳＦＤ０を保持し、ｓ−ｓｆｔＣＬＫが入力されるごとに、現在保持している過去の入力データＳＦＤ３１〜ＳＦＤ０を次段のラッチ３１ａ〜３１ｃにシフトする。
【００２３】
図８は、図５の圧縮回路６のサーチ回路１３の構成例を示すブロック図である。図８において、比較部４１には、ｉｎｐｕｔ  ＦＩＦＯ１１に保持されている現在の入力データｉＦＤ０〜ｉＦＤ７とスライドＦＩＦＯ１２に保持されている過去の入力データＳＦＤ３１〜ＳＦＤ０が入力される。そして、現在の入力データｉＦＤ０〜ｉＦＤ７と過去の入力データＳＦＤ３１〜ＳＦＤ０との比較を行い、過去の入力データＳＦＤ３１〜ＳＦＤ０の各位置に対応した一致長ｌｅｎ１〜３１を出力する。プライオリティエンコーダ４２は、一致長ｌｅｎ１〜３１の中から、最長一致長Ｍａｔｃｈ＿ｌｅｎを選択する。そして、最長一致長Ｍａｔｃｈ＿ｌｅｎが２以上の場合、Ｍａｔｃｈ＿Ｆｌａｇ＝１を出力するとともに、最長一致長Ｍａｔｃｈ＿ｌｅｎ及び最長一致位置Ｍａｔｃｈ＿ｐｏｓを出力する。一方、最長一致長Ｍａｔｃｈ＿ｌｅｎが１以下の場合、Ｍａｔｃｈ＿Ｆｌａｇ＝０を出力する。
【００２４】
図９は、図５の圧縮回路６の比較部４１の構成例を示すブロック図である。図９において、比較部４１には、３１個のコンパレータ５１ａ〜５１ｃが設けられ、各コンパレータ５１ａ〜５１ｃは、過去の入力データＳＦＤ３１〜ＳＦＤ０の各出現位置に対応している。ここで、入力データＳＦＤ３１〜ＳＦＤ０は全部で３２個あるが、一致長が１の出現位置に対応するコンパレータは不要なため、コンパレータ５１ａ〜５１ｃは全部で３１個でよい。また、現在の８個の入力データｉＦＤ０〜ｉＦＤ７を一度に比較するため、２×８入力のコンパレータ５１ｃが３１個だけ必要となるが、過去の入力データＳＦＤ６〜ＳＦＤ１の各出現位置に対応する部分は、比較対照となる過去の入力データＳＦＤ３１〜ＳＦＤ０がそれぞれ７〜２個しかない。このため、過去の入力データＳＦＤ６〜ＳＦＤ１の出現位置に対応するコンパレータ５１ａ、５２ｂ、・・・は、それぞれ２×２入力〜２×７入力でよい。各コンパレータ５１ａ〜５１ｃは、現在の入力データｉＦＤ０〜ｉＦＤ７と過去の入力データＳＦＤ３１〜ＳＦＤ０との比較を行い、その時の一致長ｌｅｎ１〜３１を出力する
このように、比較部４１には、現在の８個の入力データｉＦＤ０〜ｉＦＤ７と過去の３２個の入力データＳＦＤ３１〜ＳＦＤ０のうちの連続する８個分との比較を行うためのコンパレータ５１ａ〜５１ｃが、過去の入力データＳＦＤ３１〜ＳＦＤ０の全ての出現位置に対応して設けられている。このため、現在の入力データｉＦＤ０〜ｉＦＤ７と過去の入力データＳＦＤ３１〜ＳＦＤ０との最長一致位置を検出する場合、現在の入力データｉＦＤ０〜ｉＦＤ７をシフトさせながら過去の入力データＳＦＤ３１〜ＳＦＤ０との比較を何度も行う必要がなくなり、最長一致位置及び最長一致長を１回の比較処理により検出することが可能となる。
【００２５】
図１０は、図９の比較部４１のコンパレータ５１ｃの構成例を示すブロック図である。図１０において、コンパレータ５１ｃは、現在の８個の入力データｉＦＤ０〜ｉＦＤ７をＡ０〜Ａ７に入力するとともに、過去の３２個の入力データＳＦＤ３１〜ＳＦＤ０の中の連続する８個をＢ０〜Ｂ７に入力する。そして、現在の８個の入力データｉＦＤ０〜ｉＦＤ７と過去の３２個の入力データＳＦＤ３１〜ＳＦＤ０の中の連続する８個とを比較し、その時の一致長ｌｅｎを出力する。ここで、一致長ｌｅｎは０〜８の値を取り得るので、一致長ｌｅｎのビット数は３ビット必要になる。
【００２６】
図１１は、図１０のコンパレータ５１ｃの出力データの一例を示す図である。図１１において、一致したバイト数を一致長ｌｅｎとして、コード化して出力する。ここで、１バイトマッチは圧縮効果がないため、０を出力する。
【００２７】
図１２は、図８のサーチ回路１３のプライオリティエンコーダ４２の構成例を示すブロック図である。図１２において、プライオリティエンコーダ４２は最大一致長算出部６１を備え、最大一致長算出部６１は３１個の一致長ｌｅｎ１〜３１の中の最大一致長Ｍａｔｃｈ＿ｌｅｎを出力するとともに、最大一致長Ｍａｔｃｈ＿ｌｅｎを与える最長一致位置Ｍａｔｃｈ＿ｐｏｓをｉ１〜ｉ３１の中から選択して出力する。また、最大一致長Ｍａｔｃｈ＿ｌｅｎはコンパレータ６２に対しても出力され、コンパレータ６２は最大一致長Ｍａｔｃｈ＿ｌｅｎと０とを比較する。そして、最大一致長Ｍａｔｃｈ＿ｌｅｎ＝０の場合は、コンパレータ６２は１を出力し、コンパレータ６２からの出力がインバータ６３で反転されて、Ｍａｔｃｈ＿Ｆｌａｇ＝０が出力される。一方、最大一致長Ｍａｔｃｈ＿ｌｅｎが０でない場合は、コンパレータ６２は０を出力し、コンパレータ６２からの出力がインバータ６３で反転されて、Ｍａｔｃｈ＿Ｆｌａｇ＝１が出力される。図１３は、図５の圧縮回路６の出力回路１４の構成例を示すブロック図である。図１３において、８ビット分のＭａｔｃｈ＿Ｆｌａｇを格納するラッチ７３及び８バイト分の圧縮データＤ０〜Ｄ７を格納するためのラッチ７４ａ〜７４ｃが設けられている。プライオリティエンコーダ４２から出力されたＭａｔｃｈ＿Ｆｌａｇの値はラッチ７３に出力されるとともに、シーケンサ７１及びセレクタ７２に出力される。セレクタ７２は、Ｍａｔｃｈ＿Ｆｌａｇ＝１の場合、プライオリティエンコーダ４２から出力された最大一致長Ｍａｔｃｈ＿ｌｅｎ及び最長一致位置Ｍａｔｃｈ＿ｐｏｓをラッチ７４ａ〜７４ｃに出力する。一方、セレクタ７２は、Ｍａｔｃｈ＿Ｆｌａｇ＝０の場合、ｉｎｐｕｔ  ＦＩＦＯ１１から出力された８ビットの生データＤｔｈｒｕをラッチ７４ａ〜７４ｃに出力する。
【００２８】
シーケンサ７１は、シーケンサ１５からｐｕｔ信号が出力されるごとに、Ｆ７及びＬＤ０、Ｆ６及びＬＤ１、・・・、Ｆ０及びＬＤ７を順次選択し、８ビット分のＭａｔｃｈ＿Ｆｌａｇをラッチ７３に格納するとともに、８バイト分の圧縮データＤ０〜Ｄ７をラッチ７４ａ〜７４ｃに格納する。そして、８ビット分のＭａｔｃｈ＿Ｆｌａｇがラッチ７３に格納されるとともに、８バイト分の圧縮データＤ０〜Ｄ７がラッチ７４ａ〜７４ｃに格納されると、これらの７２ｂｉｔ分のデータをＤｏｕｔとして出力するとともに、ＫＤｒｅｑをＣＰＵ１に出力する。そして、ＣＰＵ１が７２ｂｉｔ分の出力データＤｏｕｔを取り込み、ＣＰＵ１がｋＤａｃｋを出力すると、出力回路１４は、ＣＰＵ１から出力されたｋＤａｃｋを取り込み、シーケンサ１５からｊＥＮＤが出力されるまで、以上の出力動作を繰り返す。その後、シーケンサ１５からｊＥＮＤが出力されると、出力回路１４は、ｋＥＮＤをＣＰＵ１に出力して出力動作を終了する。
【００２９】
図１４は、図５の圧縮回路６のシーケンサ１５の動作を示すフローチャートである。図１４において、圧縮回路６が圧縮動作を行う場合、シーケンサ１５は、ｉｎｐｕｔ  ＦＩＦＯ１１及びスライドＦＩＦＯ１２にｒｅｓｅｔ信号を出力し、ラッチ２１ａ〜２１ｃ及びラッチ３１ａ〜３１ｃをクリアする（ステップＳ２１）。次に、ｉｎｐｕｔ  ＦＩＦＯ１１のｓｈｉｆｔ  ｍｏｄｅを０に設定し（ステップＳ２２）、ｉｎｐｕｔ  ＦＩＦＯ１１のセレクタ２２ａ、２２ｂ、・・・をデータＤｉｎの入力モードに切り替え、ｎ＝０とする（ステップＳ２３）。次に、ｉＤｒｅｑをＣＰＵ１に出力し（ステップＳ２４）、ＣＰＵ１からｉＤａｃｋが返ってくると（ステップＳ２５）、ｉｎｐｕｔ  ＦＩＦＯ１１にＬ７〜Ｌ０を順次出力ことにより（ステップＳ２６〜Ｓ２８）、ＣＰＵ１から出力された入力データＤｉｎをラッチ２１ａ〜２１ｃにラッチさせる。一方、ＣＰＵ１からのｉＤａｃｋの応答待ちの状態で、ＣＰＵ１からｉＥＮＤが出力されると（ステップＳ２９）、出力回路１４にｊＥＮＤを出力する（ステップＳ３０）。
【００３０】
次に、ｉｎｐｕｔ  ＦＩＦＯ１１のラッチ２１ａ〜２１ｃに８バイト分の入力データＤｉｎがラッチされると（ステップＳ２８）、ｐｕｔ信号を出力回路１４に出力する（ステップＳ３１）。次に、サーチ回路１３から出力されたＭａｔｃｈ  Ｆｌａｇが１の場合（ステップＳ３２）、ｓｈｉｆｔ  ｍｏｄｅを１に設定し、ｉ−ｓｆｔＣＬＫ及びｓ−ｓｆｔＣＬＫを最大一致長Ｍａｔｃｈ＿ｌｅｎ回だけ出力することにより、ｉｎｐｕｔ  ＦＩＦＯ１１のラッチ２１ａ〜２１ｃにラッチされているデータｉＦＤ０〜ｉＦＤ７をＭａｔｃｈ＿ｌｅｎ回だけシフトさせるとともに、スライドＦＩＦＯ１２のラッチ３１ａ〜３１ｃにラッチされているデータＳＦＤ３１〜ＳＦＤ０をＭａｔｃｈ＿ｌｅｎ回だけシフトさせる（ステップＳ３３）。そして、ｃｏｕｎｔにＭａｔｃｈ＿ｌｅｎを設定する（ステップＳ３４）。一方、サーチ回路１３から出力されたＭａｔｃｈ  Ｆｌａｇが０の場合（ステップＳ３２）、ｓｈｉｆｔ  ｍｏｄｅを１に設定し、ｉ−ｓｆｔＣＬＫ及びｓ−ｓｆｔＣＬＫを１回だけ出力することにより、ｉｎｐｕｔ  ＦＩＦＯ１１のラッチ２１ａ〜２１ｃにラッチされているデータｉＦＤ０〜ｉＦＤ７を１回だけシフトさせるとともに、スライドＦＩＦＯ１２のラッチ３１ａ〜３１ｃにラッチされているデータＳＦＤ３１〜ＳＦＤ０を１回だけシフトさせる（ステップＳ３５）。そして、ｃｏｕｎｔに１を設定する（ステップＳ３６）。
【００３１】
次に、ｉｎｐｕｔ  ＦＩＦＯ１１のｓｈｉｆｔ  ｍｏｄｅを０に設定し（ステップＳ３７）、ｉｎｐｕｔ  ＦＩＦＯ１１のセレクタ２２ａ、２２ｂ、・・・をデータＤｉｎの入力モードに切り替える。次に、ｉＤｒｅｑをＣＰＵ１に出力し（ステップＳ３８）、ＣＰＵ１からｉＤａｃｋが返ってくると（ステップＳ３９）、ｉｎｐｕｔ  ＦＩＦＯ１１にＬ（７−ｃｏｕｎｔ）を出力することにより（ステップＳ４０）、データシフトにより空になったＬ（７−ｃｏｕｎｔ）番目のラッチ２１ａ〜２１ｃに新たな入力データＤｉｎをラッチさせる。以上の処理をｉｎｐｕｔ  ＦＩＦＯ１１のシフトの回数ｃｏｕｎｔだけ行うことにより（ステップＳ４１、Ｓ４２）、データｉＦＤ０〜ｉＦＤ７のシフトにより空になったラッチ２１ａ〜２１ｃをＦｉｌｌにする。ラッチ２１ａ〜２１ｃがＦｉｌｌになると、ステップＳ３１に戻り、ｐｕｔ信号を出力回路１４に出力する。一方、ＣＰＵ１からのｉＤａｃｋの応答待ちの状態で、ＣＰＵ１からｉＥＮＤが出力されると（ステップＳ４３）、出力回路１４にｊＥＮＤを出力する（ステップＳ４４）。
【００３２】
図１５は、図１３の出力回路１４のシーケンサ７１の動作を示すフローチャートである。図１５において、ｎ＝０に設定し（ステップＳ５１）、シーケンサ１５からｐｕｔ信号が出力されると（ステップＳ５２）、Ｆ（７−ｎ）及びＬＤｎを出力する（ステップＳ５３）。以上の処理を８ビット分のＭａｔｃｈ＿Ｆｌａｇ及び８バイト分の圧縮データＤ０〜Ｄ７について行い（ステップＳ５２〜ｓ５５）、８ビット分のＭａｔｃｈ＿Ｆｌａｇがラッチ７３に格納されるとともに、８バイト分の圧縮データＤ０〜Ｄ７がラッチ７４ａ〜７４ｃに格納されると、これらの７２ｂｉｔ分のデータをＤｏｕｔとして出力し、ＫＤｒｅｑをＣＰＵ１に出力する（ステップＳ５６）。そして、ＣＰＵ１がｋＤａｃｋを出力すると（ステップＳ５７）、シーケンサ１５からｊＥＮＤが出力されるまで（ステップＳ５８）、以上の出力動作を繰り返す。その後、シーケンサ１５からｊＥＮＤが出力されると、ｋＥＮＤをＣＰＵ１に出力し（ステップＳ５９）、出力動作を終了する。
【００３３】
以上説明したように、本発明の第１実施例に係わるデータ圧縮装置によれば、比較対象となる過去の入力データ列の全てのデータに対応したコンパレータをパラレルに配置することにより、比較サーチを１回で完了することが可能となり、処理を高速に行うことが可能になる。また、最長マッチング列を８バイトにすることにより、効率的な圧縮データを生成することが可能となる。
【００３４】
次に、本発明の第２実施例に係わるデータ圧縮装置について説明する。第１実施例でのマッチング時の全データのシフトは、一致した文字数の回数だけ行われ、一致した文字数が多い場合には、データシフトに時間がかかる。そこで、本発明の第２実施例では、一致した文字数分のシフトを単純なシフトレジスタを用いて行う代わりに、バレルシフタを用いて行うことにより、複数文字数分のシフトを１回のシフト動作で行い、シフト動作を高速化する。
【００３５】
図１６は、本発明の第２実施例に係わるデータ圧縮装置のバレルシフタの構成例を示すブロック図である。図１６において、バレルシフタには、ｎバイト前のフリップフロップ８１ａ〜８１ｃの出力を現在のフリップフロップ８１ｄに設定するためのセレクタ８２が設けられている。このバレルシフタを図６のｉｎｐｕｔ  ＦＩＦＯ１１及び図７のスライドＦＩＦＯ１２に設ける。このことにより、ｉ−ｓｆｔＣＬＫ及びｓ−ｓｆｔＣＬＫを１回出力するだけで、ｉｎｐｕｔ  ＦＩＦＯ１１のラッチ２１ａ〜２１ｃにラッチされているデータｉＦＤ０〜ｉＦＤ７のシフトをＭａｔｃｈ＿ｌｅｎ分だけ行うことが可能となるとともに、スライドＦＩＦＯ１２のラッチ３１ａ〜３１ｃにラッチされているデータＳＦＤ３１〜ＳＦＤ０のシフトをＭａｔｃｈ＿ｌｅｎ分だけ行うことが可能となり、複数バイトのシフト処理を高速に行うことが可能となる。
【００３６】
次に、本発明の第３実施例に係わるデータ圧縮装置について説明する。本発明の第１実施例では、余白部分についてのデータ圧縮を行うと、余白部分の８バイト分のデータが１バイト分のデータに圧縮される。しかし、余白部分では、同一データが数百バイト以上に渡って繰り返し出現することが多い。このため、余白部分については、第１実施例のデータ圧縮方法をそのまま適用したのでは、非効率である。そこで、本発明の第３実施例では、複数バイトに渡る同一データの繰り返しを検出するための追加回路を設ける。そして、余白部分等のリピートデータに対し、その繰り返し回数を符号化することにより、圧縮率の向上を図るようにする。
【００３７】
図１７は、本発明の第３実施例に係わるデータ圧縮方法を説明する図である。図１７において、１バイト単位の入力データ列を、過去のデータ列と比較する。そして、現在の８バイト分の全ての入力データ列が過去の最後尾の入力データと一致するかどうか調べる。ここで、現在の８バイト分の全ての入力データ列が過去の最後尾の入力データと一致した場合、フラグデータを“１”に設定し、現在の入力データ列を８バイト分ずつシフトしながら、現在の８バイト分の全ての入力データ列が過去の最後尾の入力データと何回一致するかをカウントする。そして、その時のカウント値ＣＮＴを符号化する。
【００３８】
ここで、繰り返しデータを符号化する場合、入力データを一致長ｌｅｎ及び一致位置ｐｏｓで符号化する時に用いたデータ構造をそのまま採用する。すなわち、一致長ｌｅｎの格納領域に繰り返しデータの識別情報を格納し、一致位置ｐｏｓの格納領域に８バイトデータの繰り返しのカウント値ＣＮＴを格納する。ここで、図１の符号化方法では、一致長ｌｅｎ＝１の場合は、生データがそのまま出力されるため、図１１に示すように、一致長ｌｅｎ＝１の符号は使用されていない。そこで、一致長ｌｅｎ＝１の符号を余白部分の繰り返しデータを識別するために使用する。
【００３９】
例えば、過去のデータ列（ヘキサで示す）の最後尾（出現位置０）が、“００”の状態で、現在のデータ列として、“００、００、００、００、００、００、００、００・・・”が入力されたものとする。そして、現在の８バイト分の全ての入力データ“００、００、００、００、００、００、００、００”と過去の最後尾の入力データ“００”との一致が確認されると、フラグデータの７ビット目を“１”に設定する。また、データＤ０の一致長ｌｅｎの領域（上位３ビット）に１を格納し、データＤ０のカウント値ＣＮＴの領域（下位５ビット）に１を格納する。次に、現在の入力データ列を８バイト分だけシフトし、シフト後の現在の８バイト分の全ての入力データ列が過去の最後尾の入力データ“００”と一致するかどうかを調べる。そして、一致する場合は、データＤ０のカウント値ＣＮＴを１だけ増加させる。以上の動作を現在の８バイト分の全ての入力データ列が過去の最後尾の入力データと一致しなくなるまで続け、シフト後の現在の８バイト分の全ての入力データ列が過去の最後尾の入力データと一致する場合は、データＤ０のカウント値ＣＮＴを１ずつ増やしていく。現在の８バイト分の全ての入力データ列が過去の最後尾の入力データと一致しなくなると、データＤ０のカウント値ＣＮＴのカウントアップを終了し、その時の現在の入力データ列の符号をデータＤ１に格納する。以上の処理をデータＤ０〜Ｄ７について行い、１バイト分のフラグデータと８バイト分の圧縮データが１組となる７２ｂｉｔの出力データを生成する。
【００４０】
このように、現在の入力データ列を８バイト分ずつシフトした時に、余白部分に対応する入力データ“００”が続く限りは、データＤ０のカウント値ＣＮＴが１ずつ増えるだけで、余白部分のデータを格納するためにデータＤ１〜Ｄ７の領域を使用する必要がない。このため、余白部分のデータ圧縮を効率的に行うことが可能となる。なお、図１７の実施例では、カウント値ＣＮＴを格納する領域が５ｂｉｔ分しか用意されていないので、カウント値ＣＮＴが３２以上になると、カウント値ＣＮＴをそれ以上アウントアップできないので、次のデータＤ１〜Ｄ７の領域に余白部分のデータを格納する必要がある。しかし、ＬＺ符号を使用した場合に比べ、最大で３２倍の圧縮効果がある。
【００４１】
図１８は、本発明の第３実施例に係わるデータ圧縮装置のコンパレータの構成例を示すブロック図である。このコンパレータは、現在の８バイト分の全ての入力データ列と過去の最後尾の入力データとが一致するかどうかを調べるためのものである。図１８において、コンパレータ９１には、ｉｎｐｕｔ  ＦＩＦＯ１１から出力される現在の入力データｉＦＤ０〜ｉＦＤ７とスライドＦＩＦＯ１２から出力される過去の最後尾の入力データＳＦＤ０とが供給される。そして、現在の全ての入力データｉＦＤ０〜ｉＦＤ７が過去の最後尾の入力データＳＦＤ０と一致する場合、Ｒｅｐ−Ｆｌａｇ＝１に設定し、現在の全ての入力データｉＦＤ０〜ｉＦＤ７が過去の最後尾の入力データＳＦＤ０と一致しない場合、Ｒｅｐ−Ｆｌａｇ＝０に設定する。
【００４２】
図１９は、本発明の第３実施例に係わるデータ圧縮装置の出力回路の構成例を示すブロック図である。図１９において、出力回路１４’は、図１３の出力回路１４に対し、セレクタ１０１〜１０３、加算器１０４、コンパレータ１０５、インバータ１０６及びＡＮＤ回路１０７が新たに設けられており、図１８のコンパレータ９１から出力されるＲｅｐ−Ｆｌａｇの値がシーケンサ７１’及びセレクタ１０１に供給される。
【００４３】
シーケンサ７１’は、まず、Ｓｅｌ＿Ｒｅｐｉｎｃ＝０に設定する。そして、Ｒｅｐ−Ｆｌａｇ＝０の場合、セレクタ１０１、１０２により、セレクタ７２’からの出力データが選択される。そして、Ｍａｔｃｈ−Ｆｌａｇの値に応じて、最大一致長Ｍａｔｃｈ＿ｌｅｎ及び最長一致位置Ｍａｔｃｈ＿ｐｏｓまたは生データＤｔｈｒｕがラッチ７４ａ’〜７４ｃ’に供給される。
【００４４】
一方、Ｓｅｌ＿Ｒｅｐｉｎｃ＝０の時にＲｅｐ−Ｆｌａｇ＝１になると、セレクタ１０１、１０２により、“００１００００１”という８ビットデータが選択される。そして、ＬＤｎを出力することにより、ｎ番目のラッチ７４ａ’〜７４ｃ’にこの８ビットデータが格納される。ここで、この８ビットデータの上位３ビットは繰り返しデータの識別情報を表し、下位５ビットは８バイトデータの繰り返し回数ＣＮＴを表している。従って、“００１００００１”という８ビットデータをラッチ７４ａ’〜７４ｃ’に格納することにより、８バイトデータの繰り返しデータが１回出現したという情報が記憶される。
【００４５】
次に、シーケンサ１５からｐｕｔ信号が出力された時にＲｅｐ−Ｆｌａｇが１の場合、シーケンサ７１’は、Ｓｅｌ＿Ｒｅｐｉｎｃ＝１に設定するとともに、Ｓｅｌ＿Ｄ＝ｎに設定し、ＬＤｎを出力する。このことにより、ｎ番目のラッチ７４ａ’〜７４ｃ’にラッチされているデータＤｎがセレクタ１０３により選択され、加算器１０４によりデータＤｎに１が加算される。そして、データＤｎに１を加算した値がセレクタ１０２により選択され、その加算結果がｎ番目のラッチ７４ａ’〜７４ｃ’にラッチされる。このことにより、ｎ番目のラッチ７４ａ’〜７４ｃ’にラッチされているデータＤｎの繰り返し回数ＣＮＴを１だけ増加させることができる。ここで、コンパレータ１０５は加算器１０４から出力された加算結果を監視し、Ｄｎに格納されている繰り返し回数ＣＮＴが３２に達すると、そのことをＡＮＤ回路１０７を介してシーケンサ７１’に伝える。シーケンサ７１’は、Ｄｎに格納されている繰り返し回数ＣＮＴが３２に達したという知らせを受けると、ｎ＋１番目のラッチ７４ａ’〜７４ｃ’に対して以上の動作を行う。そして、８ビット分のＭａｔｃｈ＿Ｆｌａｇがラッチ７３’に格納されるとともに、８バイト分の圧縮データＤ０〜Ｄ７がラッチ７４ａ’〜７４ｃ’に格納されると、これらの７２ｂｉｔ分のデータをＤｏｕｔとして出力するとともに、ＫＤｒｅｑをＣＰＵ１に出力する。
【００４６】
図２０は、図１９の出力回路１４’のシーケンサ７１’の動作を示すフローチャートである。図２０において、Ｓｅｌ＿Ｒｅｐｉｎｃ＝０に設定し（ステップＳ６１）、ｎ＝０に設定する（ステップＳ６２）。次に、シーケンサ１５からｐｕｔ信号が出力されると（ステップＳ６３）、Ｒｅｐ−Ｆｌａｇ＝１かどうかを判断し（ステップＳ６４）、Ｒｅｐ−Ｆｌａｇ＝０の場合、Ｆ（７−ｎ）及びＬＤｎを出力する（ステップＳ６５）。以上の処理を８ビット分のＭａｔｃｈ＿Ｆｌａｇ及び８バイト分の圧縮データＤ０〜Ｄ７について行い（ステップＳ６３〜ｓ６７）、８ビット分のＭａｔｃｈ＿Ｆｌａｇがラッチ７３’に格納されるとともに、８バイト分の圧縮データＤ０〜Ｄ７がラッチ７４ａ’〜７４ｃ’に格納されると、これらの７２ｂｉｔ分のデータをＤｏｕｔとして出力し、ＫＤｒｅｑをＣＰＵ１に出力する（ステップＳ６８）。
【００４７】
一方、ステップＳ６４において、Ｒｅｐ−Ｆｌａｇ＝１の場合、Ｓｅｌ＿Ｒｅｐｉｎｃ＝０に設定し（ステップＳ７２）、Ｆ（７−ｎ）及びＬＤｎを出力する（ステップＳ７３）。次に、シーケンサ１５からｐｕｔ信号が出力されると（ステップＳ７４）、Ｒｅｐ−Ｆｌａｇ＝１かつＤｎのＣＮＴが３２より小さいかどうかを判断する（ステップＳ７５）。そして、Ｒｅｐ−Ｆｌａｇ＝１かつＤｎのＣＮＴが３２より小さい場合は、Ｓｅｌ＿Ｄ＝ｎ、Ｓｅｌ＿Ｒｅｐｉｎｃ＝１に設定する（ステップＳ７６）。Ｓｅｌ＿Ｄ＝ｎ、Ｓｅｌ＿Ｒｅｐｉｎｃ＝１に設定することにより、ラッチ７４ａ’〜７４ｃ’に格納されているＤ０〜Ｄ７のうちのＤｎがセレクタ１０３により選択され、加算器１０４で１だけ加算された値がセレクタ１０２で選択され、ラッチ７４ａ’〜７４ｃ’に戻される。そして、ＬＤｎを出力することにより（ステップＳ７７）、Ｄｎに１を加算した値がＤｎを格納していたラッチ７４ａ’〜７４ｃ’にラッチされる。以上の動作をシーケンサ１５からｐｕｔ信号が出力される度に行い、Ｒｅｐ−Ｆｌａｇ＝０になるかまたはＤｎのＣＮＴが３２以上になると、ステップＳ６６に進み、ｎを１だけ増加させる。一方、ステップＳ７４において、ｐｕｔ信号の出力の待機中に、シーケンサ１５からｊＥＮＤが出力されると（ステップＳ７８）、ｋＥＮＤをＣＰＵ１に出力し（ステップＳ７１）、出力動作を終了する。
【００４８】
次に、ＣＰＵ１がｋＤａｃｋを出力すると（ステップＳ６９）、シーケンサ１５からｊＥＮＤが出力されるまで（ステップＳ７０）、以上の出力動作を繰り返す。そして、シーケンサ１５からｊＥＮＤが出力されると、ｋＥＮＤをＣＰＵ１に出力し（ステップＳ７１）、出力動作を終了する。
【００４９】
なお、上述した実施例では、データ圧縮について説明したが、データ伸張に適用するようにしてもよい。また、上述した実施例では、８ｂｉｔのデータを８バイトずつ処理する例について示したが、これ以外であってもよい。また、上述した実施例では、現在の８バイト分のデータを過去の３２バイト分のデータと比較する場合について示したが、これ以外であってもよい。例えば、現在の１６バイト分のデータを過去の６４バイト分のデータと比較するようにしてもよい。
【００５０】
【発明の効果】
以上説明したように、本発明によれば、比較対象となる過去の入力データの全ての出現位置に対応した比較手段を設けることにより、現在の入力データと過去の入力データとの比較を過去の入力データの全ての出現位置に対して同時に行うことが可能となり、ＬＺ符号における最長一致長及び最長一致位置を過去のデータ列と現在の入力データ列との１回の比較動作により求めることが可能となることから、ＬＺ符号によるデータ圧縮を高速に行うことが可能となる。
【００５１】
また、本発明の一態様によれば、一致長及び出現位置を格納する領域のビット長を入力データのビット長と一致させることにより、生データとＬＺ符号とを同一のデータフォーマット上で混在させて出力することが可能となり、データ圧縮を効率的に行うことが可能となる。
【００５２】
また、本発明の一態様によれば、過去のデータ列及び現在の入力データ列の一致長分のシフトを、バレルシフタを用いて行うことにより、過去の入力データ列及び現在の入力データ列の一致長分のシフトを１度に行うことが可能となり、ＬＺ符号によるデータ圧縮を高速に行うことが可能となる。
【００５３】
また、本発明の一態様によれば、同一の入力データ列の繰り返し回数を入力データ列の符号として出力することにより、プリント時の余白部分のデータ圧縮を効率的に行うことが可能となる。
【図面の簡単な説明】
【図１】本発明の第１実施例に係わるデータ圧縮方法を説明する図である。
【図２】本発明の一実施例に係わるデータ圧縮装置のシステム構成を示すブロック図である。
【図３】図２のデータ圧縮装置のデータ入力シーケンスを示すフローチャートである。
【図４】図２のデータ圧縮装置のデータ出力シーケンスを示すフローチャートである。
【図５】本発明の第１実施例に係わるデータ圧縮装置の圧縮回路の構成を示すブロック図である。
【図６】図５の圧縮回路のｉｎｐｕｔ  ＦＩＦＯの構成例を示すブロック図である。
【図７】図５の圧縮回路のスライドＦＩＦＯの構成例を示すブロック図である。
【図８】図５の圧縮回路のサーチ回路の構成例を示すブロック図である。
【図９】図５の圧縮回路の比較部の構成例を示すブロック図である。
【図１０】図９の比較部のコンパレータの構成例を示すブロック図である。
【図１１】図１０のコンパレータの出力データの一例を示す図である。
【図１２】図８のサーチ回路のプライオリティエンコーダの構成例を示すブロック図である。
【図１３】図５の圧縮回路６の出力回路１４の構成例を示すブロック図である。
【図１４】図５の圧縮回路６のシーケンサ１５の動作を示すフローチャートである。
【図１５】図１３の出力回路１４のシーケンサ７１の動作を示すフローチャートである。
【図１６】本発明の第２実施例に係わるデータ圧縮装置のバレルシフタの構成例を示すブロック図である。
【図１７】本発明の第３実施例に係わるデータ圧縮方法を説明する図である。
【図１８】本発明の第３実施例に係わるデータ圧縮装置のコンパレータの構成例を示すブロック図である。
【図１９】本発明の第３実施例に係わるデータ圧縮装置の出力回路の構成例を示すブロック図である。
【図２０】図１９の出力回路１４’のシーケンサ７１’の動作を示すフローチャートである。
【符号の説明】
１  ＣＰＵ
２  プログラム
３  ＲＡＭ
４、５  Ｉ／Ｏポート
６  圧縮回路
１１  ｉｎｐｕｔ  ＦＩＦＯ
１２  スライド  ＦＩＦＯ
１３  サーチ回路
１４、１４’  出力回路
１５、７１  シーケンサ
２１ａ〜２１ｃ、３１ａ〜３１ｃ、８１ａ〜８１ｄ  フリップフロップ
２２ａ、２２ｂ、７２、８２、７２’、１０１〜１０３  セレクタ
４１  比較部
４２  プライオリティエンコーダ
５１ａ〜５１ｃ、６２、９１、１０５  コンパレータ
６１  最大一致長算出部
７３、７４ａ〜７４ｃ、７３’、７４ａ’〜７４ｃ’  ラッチ
１０４  加算器
１０６  インバータ
１０７  ＡＮＤ回路
【図１】
0003610381.tif 000002
【図２】
0003610381.tif 000003
【図３】
0003610381.tif 000004
【図４】
0003610381.tif 000005
【図５】
0003610381.tif 000006
【図６】
0003610381.tif 000007
【図７】
0003610381.tif 000008
【図８】
0003610381.tif 000009
【図９】
0003610381.tif 000010
【図１０】
0003610381.tif 000011
【図１１】
0003610381.tif 000012
【図１２】
0003610381.tif 000013
【図１３】
0003610381.tif 000014
【図１４】
0003610381.tif 000015
【図１５】
0003610381.tif 000016
【図１６】
0003610381.tif 000017
【図１７】
0003610381.tif 000018
【図１８】
0003610381.tif 000019
【図１９】
0003610381.tif 000020
【図２０】
0003610381.tif 000021