データ処理装置およびデータ処理方法
【課題】特にマシン語のプログラムデータの圧縮符号化および復号処理を行うために用いて好適なデータ処理方法を提供する。
【解決手段】ＲＩＳＣによるマシン語のプログラムデータは、データ長が３２ビットの固定フォーマットで決められた所定領域に対して、同じ意味のコードが格納されるため、ＬＺ７７符号による符号化を行う際のスライドが４バイト毎に一致する可能性が高くなる。そこで、バイト単位でプログラムデータの４バイト毎に小さい値の変換アドレス値TAddressを割り当てる変換テーブルを用いて、アドレス値Addressを変換する。そして、値が「０」〜「１５」までの変換アドレス値TAddressを、符号長が４ビットの符号に符号化し、値が「１５」〜「２５５」の変換アドレス値TAddressを符号長が８ビットの符号に符号化する。
【解決手段】ＲＩＳＣによるマシン語のプログラムデータは、データ長が３２ビットの固定フォーマットで決められた所定領域に対して、同じ意味のコードが格納されるため、ＬＺ７７符号による符号化を行う際のスライドが４バイト毎に一致する可能性が高くなる。そこで、バイト単位でプログラムデータの４バイト毎に小さい値の変換アドレス値TAddressを割り当てる変換テーブルを用いて、アドレス値Addressを変換する。そして、値が「０」〜「１５」までの変換アドレス値TAddressを、符号長が４ビットの符号に符号化し、値が「１５」〜「２５５」の変換アドレス値TAddressを符号長が８ビットの符号に符号化する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの符号化および復号を行うデータ処理装置およびデータ処理方法に関する。
【背景技術】
【０００２】
従来から、ハードディスクドライブ（ＨＤＤ）といった２次記憶媒体に対して格納するプログラムやデータ（以下、特に記載のない限り、これらを纏めてデータと呼ぶ）を圧縮符号化することが行われていた。データを圧縮符号化してＨＤＤなどに格納することで、記憶領域を節約してより多くのデータが格納可能となる。また、圧縮符号化により格納されるデータのデータサイズが小さくなるため、ＨＤＤに対するアクセス速度が向上するという効果もある。
【０００３】
特許文献１には、ＨＤＤに格納されるデータに対して参照頻度や属性値を付加し、より頻繁にアクセスされるデータは圧縮符号化を行わず、アクセス頻度のより低いデータを圧縮符号化してＨＤＤに格納する技術が開示されている。特許文献１によれば、データの圧縮符号化および復号処理を含めたＨＤＤに対するアクセス速度を向上させることが可能となる。
【０００４】
また、近年では、機器を休止状態から高速に起動するために、機器が休止状態に移行する際にメモリの状態をイメージ化したスナップショットを保持しておき、機器が休止状態から復帰する際に、このスナップショットをメモリの元の位置に展開し直すことで、当該メモリの状態をスナップショット取得時の状態に復元する技術が知られている。特許文献２には、パーティション、ファイル、ディレクトリ単位でのスナップショットの取得方法について開示されている。
【０００５】
さらに、近年では、主記憶装置の状態を丸ごとイメージ化したスナップショットをハードディスクドライブなどに保持することで、省電力モードなどの休止状態から復帰する際の起動を高速化する、ハイバネーションと呼ばれる技術が実用化されている。
【０００６】
ところで、データを効率よく圧縮符号化する方法として、ユニバーサル符号により圧縮符号化する方法が実用化されている。このユニバーサル符号は、情報保存型のデータ圧縮方法であり、データ圧縮時に情報源の統計的な性質を予め仮定しないため、種々のタイプ（文字コード、オブジェクトコードなど）のデータに適用することができる。
【０００７】
ユニバーサル符号の代表的な方法として、ジブ−レンペル(Ziv-Lempel)符号がある。Ziv-Lempel符号では、ユニバーサル型と、増分分解型(Incremental parsing) の２つのアルゴリズムが提案されている。これらのうち、ユニバーサル型アルゴリズムを用いた実用的な方法として、ＬＺＳＳ(Lempel-Ziv-Storer-Syzmanski)符号がある。
【０００８】
ＬＺＳＳ符号のベースとなるＬＺ７７符号の符号化アルゴリズムは、符号化データを、過去のデータ系列の任意の位置から一致する最大長の系列に区切り、過去の系列の複製として符号化する。
【０００９】
より具体的には、符号化済みの入力データを格納する移動窓と、これから符号化するデータを格納する先読みバッファとを備え、先読みバッファのデータ系列と移動窓のデータ系列の全ての部分系列とを照合して、移動窓中で一致する最大長の部分系列を求める。そして、移動窓中でこの最大長の部分系列を指定するために、「その最大長の部分系列の開始位置」と「一致する長さ」と「不一致をもたらした次のシンボル」との組を符号化する。
【００１０】
次に、先読みバッファ内の符号化したデータ系列を移動窓に移して、先読みバッファ内に符号化したデータ系列分の新たなデータ系列を入力する。以下、同様の処理を繰り返していくことで、データを部分系列に分解して符号化を実行していく。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ところで、上述したハイバネーションでは、主記憶装置の状態を丸ごとイメージ化したスナップショットを作成する。すなわち、ハイバネーションにより作成されるスナップショットは、スナップショット作成直前に起動していたプログラムのコードデータを含むことになる。
【００１２】
近年の多くのＣＰＵ(Central Processing Unit)は、ＲＩＳＣ(Reduced Instruction Set Computer)方式を採用しているため、マシン語によるプログラムのコードデータは、４バイトや８バイト単位で命令が並び、この４バイトや８バイト毎にデータが一致する可能性が高い。また、この４バイトや８バイト毎の一致可能性のピークを無視して全体を考えた場合、最近出現したバイトで一致可能性が高くなる。一方、ある程度離れたバイトでは、一致可能性の低い同じような確率が続くことになる。
【００１３】
そのため、上述したユニバーサル符号を用いて一致位置に対して静的なハフマン符号化を行っても、余り符号化効率が良くないという問題点があった。また、符号化効率の割にはハードウェア構成が複雑となり、設計コストが嵩むと共にバグの可能性が増加するおそれがあるという問題点があった。
【００１４】
本発明は、上記に鑑みてなされたものであって、特にマシン語のプログラムデータの圧縮符号化および復号処理を行うために用いて好適なデータ処理装置およびデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上述した課題を解決し、目的を達成するために、本発明は、入力データを順次記憶するスライド記憶手段と、連続的に入力された入力データからなる入力データ列と一致する、スライド記憶手段に記憶されるデータ列を探索する探索手段と、探索手段で探索されたデータ列から１を選択して、選択されたデータ列の長さを求めてレングス値を生成するレングス生成手段と、レングス生成手段でレングス値を生成するために用いたデータ列における開始データの、スライド記憶手段内での位置を求めアドレス値を生成するアドレス値生成手段と、アドレス値の出現頻度に従い、アドレス値生成手段で生成されたアドレス値のうち、出現頻度が高いアドレス値から所定数のアドレス値を、予め定められた値以下の変換アドレス値に変換する変換手段と、レングス値と変換アドレス値とを符号化する符号化手段とを有することを特徴とする。
【００１６】
また、本発明は、スライド記憶手段が、入力データを順次記憶するスライド記憶ステップと、比較手段が、探索手段が、連続的に入力された入力データからなる入力データ列と一致する、スライド記憶手段に記憶されるデータ列を探索する探索ステップと、レングス生成手段が、探索ステップで探索されたデータ列から１を選択して、選択されたデータ列の長さを求めてレングス値を生成するレングス生成ステップと、アドレス値生成手段が、レングス生成ステップでレングス値を生成するために用いたデータ列における開始データの、スライド記憶手段内での位置を求めアドレス値を生成するアドレス値生成ステップと、変換手段が、アドレス値の出現頻度に従い、アドレス値生成ステップで生成されたアドレス値のうち、出現頻度が高いアドレス値から所定数のアドレス値を、予め定められた値以下の変換アドレス値に変換する変換ステップと符号化手段が、レングス値と変換アドレス値とを符号化する符号化ステップとを有することを特徴とする。
【発明の効果】
【００１７】
本発明によれば、特にマシン語のプログラムデータの圧縮符号化および復号処理を行うために用いて好適なデータ処理装置およびデータ処理方法が提供可能となる効果がある。
【図面の簡単な説明】
【００１８】
【図１】図１は、本発明に係るデータ処理装置を適用可能なプリンタ装置の一例の構成を示すブロック図である。
【図２】図２は、本発明の実施形態に適用可能なプリンタ装置の全体的な処理を示すフローチャートである。
【図３】図３は、エンコーダの一例の構成を示すブロック図である。
【図４】図４は、符号フォーマットの例を示す略線図である。
【図５】図５は、本実施形態に適用可能な符号化処理について説明するための略線図である。
【図６】図６は、スライド探索処理およびリスト探索処理におけるフラグ処理を説明するための略線図である。
【図７】図７は、スライド探索処理およびリスト探索処理におけるフラグ処理を説明するための略線図である。
【図８】図８は、マシン語のプログラムデータの特徴について説明するための略線図である。
【図９】図９は、マシン語のプログラムデータの特徴について説明するための略線図である。
【図１０】図１０は、変換テーブルETRANSTABLEの例を示す略線図である。
【図１１】図１１は、本発明の実施形態による符号化処理の全体的な流れを示す一例のフローチャートである。
【図１２】図１２は、スライド探索処理の例をより詳細に示すフローチャートである。
【図１３】図１３は、リスト探索処理の例をより詳細に示すフローチャートである。
【図１４】図１４は、スライド追加処理の例をより詳細に示すフローチャートである。
【図１５】図１５は、スライド符号化処理の例をより詳細に示すフローチャートである。
【図１６】図１６は、エンコーダの一例の構成をより詳細に示すブロック図である。
【図１７】図１７は、スライド／リスト生成処理部の一例のハードウェア構成を示すブロック図である。
【図１８】図１８は、デコーダの一例の構成を示すブロック図である。
【図１９】図１９は、逆変換テーブルDTRANSTABLEの一例を示す略線図である。
【図２０】図２０は、符号データを復号する一例の処理を示すフローチャートである。
【図２１】図２１は、デコーダの一例の構成をより詳細に示すブロック図である。
【図２２】図２２は、スライド展開部の一例のハードウェア構成を示すブロック図である。
【発明を実施するための形態】
【００１９】
以下に添付図面を参照して、この発明に係るデータ処理装置の一実施形態を詳細に説明する。図１は、本発明に係るデータ処理装置を適用可能なプリンタ装置の一例の構成を示す。図１の例では、プリンタ装置は、制御部２００、メインメモリ２１０、プリンタエンジン２１１および不揮発性のメモリであるフラッシュメモリ２４０を備える。フラッシュメモリ２４０は、図１に例示されるようにプリンタ装置に内蔵されていてもよいし、プリンタ装置に対して脱着可能とされていてもよい。
【００２０】
制御部２００は、ＣＰＵ(Central Processing Unit)２１２、ＣＰＵ Ｉ／Ｆ２０１、メモリコントローラ２０２、符号化部２０４、復号部２０５、画像処理部２０６、ディレイメモリ２０７、エンジンコントローラ２０８、パネルコントローラ２２０、パネル２２１、スキャナ２３０、平滑フィルタ２３１、フラッシュメモリコントローラ２４１、エンコーダ２４２およびデコーダ２４３を含む。
【００２１】
ＣＰＵ２１２は、メインメモリ２１０に格納されるプログラムに従い、このプリンタ装置の全体の動作を制御する。ＣＰＵ２１２は、ＣＰＵ Ｉ／Ｆ２０１を介してメモリコントローラ２０２に接続される。メモリコントローラ２０２は、ＣＰＵ２１２、符号化部２０４、復号部２０５、画像処理部２０６、通信Ｉ／Ｆ２０９、平滑フィルタ２３１、フラッシュメモリコントローラ２４１、エンコーダ２４２およびデコーダ２４３の、メインメモリ２１０に対するアクセスを調停する。
【００２２】
メインメモリ２１０は、メモリコントローラ２０２に接続される。メモリコントローラ２０２は、メインメモリ２１０に対するアクセスの制御を行う。
【００２３】
メインメモリ２１０は、プログラム領域２１０Ａおよびデータ領域２１０Ｂを有する。プログラム領域２１０Ａは、ＣＰＵ２１２が動作するためのプログラムが格納される。データ領域２１０Ｂは、例えばネットワークを介して供給ＰＤＬデータが格納されると共に、ＣＭＹＫバンドデータ、バンドデータが圧縮符号化された符号データ、ならびに、その他のデータが格納される。
【００２４】
符号化部２０４は、メインメモリ２１０に格納されるバンドデータを符号化する。符号化されたバンドデータは、メモリコントローラ２０２を介してメインメモリ２１０に供給される。復号部２０５は、後述するプリンタエンジン２１１に同期して、符号化部２０４で符号化されメインメモリ２１０に書き込まれた符号化バンドデータをメインメモリ２１０から読み出して復号する。復号されたバンドデータは、メモリコントローラ２０２を介して画像処理部２０６に供給される。画像処理部２０６は、復号部２０５から供給されたバンドデータに対して階調処理など所定の画像処理を施す。
【００２５】
画像処理が施されたバンドデータは、ディレイメモリ２０７を介してエンジンコントローラ２０８に転送される。ディレイメモリ２０７は、画像処理部２０６から出力されるバンドデータの転送速度と、エンジンコントローラ２０８からプリンタエンジン２１１に転送されるバンドデータの転送速度との違いを吸収する。
【００２６】
エンジンコントローラ２０８は、プリンタエンジン２１１を制御する。図１では、プリンタエンジン２１１としてＣＭＹＫ各色の版のうち１の版のものだけが記載され、その他の版については煩雑さを避けるために省略されている。
【００２７】
通信Ｉ／Ｆ２０９は、ネットワークを介しての通信を制御する。例えば、ネットワークに接続されるコンピュータから出力されたＰＤＬ(Page Description Language)データは、通信Ｉ／Ｆ２０９により受信される。通信Ｉ／Ｆ２０９は、受信したＰＤＬデータを、メモリコントローラ２０２を介してメインメモリ２１０に転送する。
【００２８】
なお、ネットワークは、ＬＡＮ(Local Area Network)などの所定の範囲内で通信を行うものでもよいし、インターネットなどより広範囲に通信可能なものでもよい。また、ネットワークは、有線通信に限らず無線通信を用いたものでもよいし、ＵＳＢ(Universal Serial Bus)やＩＥＥＥ(Institute Electrical and Electronics Engineers)１３９４といったシリアル通信を行うものでもよい。
【００２９】
フラッシュメモリ２４０は、ＣＰＵ２１２上で動作するためのプログラムや、当該プログラムに用いられる各種データが、本実施形態による圧縮符号化方法により圧縮符号化されて格納される。例えば、メインメモリ２１０のプログラム領域２１０Ａに対して、マシン語によるコードとして展開されるプログラムデータが、展開イメージのまま圧縮符号化され、スナップショットとしてフラッシュメモリ２４０に記憶される。フラッシュメモリコントローラ２４１は、フラッシュメモリ２４０に対するアクセスの制御を行う。
【００３０】
エンコーダ２４２は、本実施形態による、ＬＺ７７符号を用いた圧縮符号化方法により、プログラムデータの圧縮符号化を行う。また、デコーダ２４３は、当該圧縮符号化方法により圧縮符号化された圧縮データの復号を行う。
【００３１】
プリンタ装置の全体的な動作について、概略的に説明する。例えばコンピュータで生成されたＰＤＬデータがネットワークを介して通信Ｉ／Ｆ２０９に受信され、メインメモリ２１０のデータ領域２１０Ｂに記憶される。ＣＰＵ２１２は、メインメモリ２１０のデータ領域２１０ＢからＰＤＬデータを読み出し、ＰＤＬを解析して、解析結果に基づきＣＭＹＫのバンド画像を描画する。描画されたＣＭＹＫのバンド画像によるＣＭＹＫバンドデータは、メインメモリ２１０のデータ領域２１０Ｂに格納される。
【００３２】
符号化部２０４は、データ領域２１０ＢからＣＭＹＫバンドデータを読み出して、例えば予測符号化などを用いて符号化する。ＣＭＹＫバンドデータが符号化された符号データは、メインメモリ２１０のデータ領域２１０Ｂに格納される。
【００３３】
復号部２０５は、メインメモリ２１０のデータ領域２１０ＢからＣＭＹＫバンドデータが符号化された符号データを読み出して復号し、復号されたＣＭＹＫバンドデータをメモリコントローラ２０２を介して画像処理部２０６に供給する。画像処理部２０６は、復号部２０５から供給されたＣＭＹＫバンドデータに対して所定の画像処理を施す。画像処理されたＣＭＹＫバンドデータは、ディレイメモリ２０７およびプリンタエンジンコントローラ２０８を介してプリンタエンジン２１１に供給される。プリンタエンジン２１１は、供給されたＣＭＹＫバンドデータに基づきプリントアウトを行う。
【００３４】
図２は、本実施形態に適用可能なプリンタ装置の全体的な処理を示すフローチャートである。概略的には、例えばユーザがプリンタ装置の電源をＯＮとすると、電源立ち上げ処理が行われ（ステップＳ１）、プリンタ装置がＲＵＮ状態（稼働状態）になる（ステップＳ２）。ユーザの電源ＯＦＦ操作などにより、電源立ち下げ処理が行われ（ステップＳ３）、プリンタ装置がスリープ状態となる（ステップＳ４）。
【００３５】
ステップＳ１の電源立ち上げ処理では、フラッシュメモリ２４０に圧縮符号化されてスナップショットとして格納されたプログラムデータがフラッシュメモリ２４０から読み出され（ステップＳ１−１）、デコーダ２４３で本実施形態による復号方法に従い復号され、マシン語によるプログラムデータとされる（ステップＳ１−２）。このマシン語のプログラムデータは、メモリコントローラ２０２を介してメインメモリ２１０に供給され、プログラム領域２１０Ａに格納される（ステップＳ１−３）。
【００３６】
一方、ステップＳ３の電源立ち下げ処理では、メインメモリ２１０のプログラム領域２１０Ａに格納されるマシン語によるプログラムデータがメインメモリ２１０から読み出され（ステップＳ３−１）、エンコーダ２４２で本実施形態による符号化方法に従い圧縮符号化される（ステップＳ３−２）。圧縮符号化されたマシン語プログラムデータは、フラッシュメモリ２４０に対してスナップショットとして格納される（ステップＳ３−３）。
【００３７】
このように、電源立ち下げ処理時に、メインメモリ２１０のプログラム領域２１０Ａに格納されるマシン語のプログラムデータを、メモリ上のイメージのまま圧縮符号化し、スナップショットとしてフラッシュメモリ２４０に格納することで、電源立ち上げ処理を高速化することができる。
【００３８】
＜エンコーダ＞
図３は、エンコーダ２４２の一例の構成を示す。エンコーダ２４２において、データ読み込み部３００により、メインメモリ２１０のプログラム領域２１０Ａから、マシン語によるプログラムデータがメモリコントローラ２０２を介して読み出される。データ読み込み部３００に読み込まれたデータは、スライド／リスト生成処理部３０１に供給される。
【００３９】
スライド／リスト生成処理部３０１は、入力されたデータを順次記憶するＦＩＦＯ方式のスライド記憶部を有する。スライド／リスト生成処理部３０１は、供給されたデータとスライド記憶部に記憶された過去の入力データとを順次比較する。そして、供給されたデータと過去の入力データとが一致した場合には、当該過去の入力データのスライド記憶部内の位置を示すアドレス値Addressを保持すると共に、一致した長さを示す値であるレングスLengthをカウントアップする。両者が一致しない場合には、データ値そのものをPASS符号として符号化する。
【００４０】
ここで、本実施形態においては、詳細を後述する規則に従いアドレス値Addressを変換し、変換アドレス値TAddressとする。そして、これらPASS符号と、変換アドレス値TAddressおよびレングスLengthと、符号の種類を示すヘッダとを出力する。
【００４１】
スライド／リスト生成処理部３０１のから出力された各値は、符号フォーマット生成処理部３０２に供給される。符号フォーマット生成処理部３０２は、供給されたPASS符号、変換アドレス値TAddress、レングスLengthおよびヘッダとを、図４に例示されるようなフォーマットで符号化する。
【００４２】
図４において、PASS符号は、データ長が１ビットで値が「０」のヘッダに対して、後に８ビットのデータ長を持つデータ値が接続されてなる。スライド符号は、データ長が２ビットのヘッダに対して、レングスLengthおよびアドレス値Addressが順次接続される。レングスLengthは、符号長が８ビットとされる。
【００４３】
ここで、本実施形態においては、変換アドレス値TAddressは、自身の値に応じて２種類の符号長のうち何れか一方を選択されて符号化される。図４の例では、変換アドレス値TAddressは、符号長が８ビットの符号と、符号長が４ビットの符号とのうち何れかに符号化される。符号長が８ビットの符号に符号化された変換アドレス値TAddressを含むスライド符号を、第１スライド符号と呼び、ヘッダが「１０」とされる。また、符号長が４ビットの符号に符号化された変換アドレス値TAddressを含むスライド符号を、第２スライド符号と呼び、ヘッダが「１１」とされる。
【００４４】
なお、この図４に例示される符号フォーマットは、一例であって、これに限られるものではない。例えば、変換アドレス値TAddressの符号長は、第１および第２のスライド符号それぞれで８ビットまたは４ビットに限られない。
【００４５】
符号フォーマット生成処理部３０２で生成されたPASS符号、ならびに、第１および第２スライド符号は、符号書き込み部３０３に供給される。符号書き込み部３０３は、供給されたPASS符号、ならびに、第１および第２およびスライド符号を、メモリコントローラ２０２およびフラッシュメモリコントローラ２４１を介してフラッシュメモリ２４０に書き込む。
【００４６】
＜符号化処理の概略＞
次に、本実施形態に適用可能な、スライド／リスト生成処理部３０１における符号化処理について説明する。本実施形態では、ＬＺ７７符号を用い、スライド探索処理とリスト探索処理とを繰り返すことによって、データの符号化を行う。スライド探索処理は、１単位（例えば１バイト）の入力データと一致する、所定単位分の長さを持つスライド記憶部に記憶される過去の入力データを探索する。スライド記憶部内の過去の入力データに、入力データと一致するデータが探索されなかった場合には、入力データそのものをPASS符号として用いる。
【００４７】
スライド探索処理において、入力データに一致するスライド記憶部内の過去の入力データが探索された場合、その一致した過去の入力データをルートとして、リスト探索処理が行われる。リスト探索処理は、ルートとされた入力データに対して連続的に入力された入力データ列と一致する、スライド記憶部内の過去の入力データ列（リストと呼ぶ）を探索する。
【００４８】
リスト探索処理時に、入力データと一致するリストが無くなると、直前のリストから１を選び、選択されたリストのルートとなる過去の入力データのスライド記憶部内での位置をアドレス値Addressとし、当該リストの長さをレングスLengthとして出力する。
【００４９】
すなわち、スライド／リスト生成処理部３０１では、スライド探索処理でリスト探索処理のルートとなる過去の入力データを形成する。そして、リスト探索処理で、ルートに基づくリストの成長および淘汰を行い、最終的に残ったリストに基づき符号化を行う。
【００５０】
図５を用いてより具体的に説明する。図５の例では、スライド記憶部は、番号＃０〜＃１５で示されるように、直列に接続された１６個のレジスタを持ち、ＦＩＦＯ(First In First Out)として構成される。各レジスタは、それぞれ１単位（例えば１バイト）のデータを格納可能であるものとする。なお、以下では、このスライド記憶部が有するレジスタをスライドと呼ぶ。
【００５１】
処理＃１において、スライド記憶部の各スライドには、入力の新しい順、すなわち図５の右側から左側に向けて、「ａ，ｂ，ｃ，ａ，ａ，ｂ，ｃ，ａ，ｂ，ｃ，ｄ，ｂ，ｃ，ａ，ｃ，ａ」と、１６個の過去に入力されたデータが既に格納されているものとする。最初に、スライド／リスト生成処理部３０１に対して入力データ「ａ」が入力される。スライド探索処理により、この入力データ「ａ」と、各スライドに記憶された過去の入力データのそれぞれとを比較し、一致しているデータを探索する。図５の例では、番号＃０、＃３、＃４、＃７、＃１３および＃１５のスライドに格納されているデータが入力データと一致していることが分かる。したがって、これらの番号のスライドに格納されているデータが、リスト探索処理におけるルートとなる。
【００５２】
スライド探索処理によって、各スライドに記憶された過去の入力データから、入力データ「ａ」と一致しているデータが探索されたので、処理＃２のリスト探索処理が行われる。
【００５３】
処理＃２では、各スライドに記憶される過去の入力データを左に１だけシフトさせて、処理＃１で入力された入力データ「ａ」をスライド記憶部の番号＃０のスライドに追加する。それと共に、次の入力データ「ｃ」がスライド／リスト生成処理部３０１に対して入力される。リスト探索処理では、各スライドに記憶される過去の入力データのうち、直前の処理＃１において入力データが一致した各スライド内の過去の入力データが格納されていたスライドから、新たな入力データ「ｃ」と一致するデータを探索する。
【００５４】
図５の例では、処理＃１において入力データと一致した番号＃０および＃４のスライドに格納される過去の入力データは、処理＃２において入力データと一致していない。一方、処理＃１において入力データと一致した番号＃３、＃７、＃１３および＃１５のスライドに格納された過去の入力データは、データ「ｃ」であって、新たな入力データ「ｃ」と一致する。
【００５５】
処理＃２のリスト探索処理によって、直前の処理＃１において入力データが一致した各スライド内の過去の入力データが格納されたスライドから、処理＃２における入力データ「ｃ」と一致するデータが探索されたので、次の処理はリスト探索処理となる。なお、処理＃２は、リスト探索処理の開始点であるので、リストの長さを示すレングスLengthは、値「０」とされる。
【００５６】
処理＃３では、上述の処理＃２と同様にして、各スライドに記憶される過去の入力データを左に１だけシフトさせて、処理＃２で入力された入力データ「ｃ」をスライド記憶部の番号＃０のスライドに追加する。それと共に、次の入力データ「ｂ」がスライド／リスト生成処理部３０１に対して入力される。そして、各スライドに記憶される過去の入力データのうち、直前の処理＃２において入力データが一致した各スライド内の過去の入力データが格納されたスライドから、新たな入力データ「ｂ」と一致するデータを探索する。
【００５７】
図５の例では、処理＃２において探索された番号＃１５のスライドに格納される過去の入力データは、処理＃３において入力データと一致していない。一方、処理＃２において探索された番号＃３、＃７および＃１３のスライドに格納される、処理＃３における過去の入力データはデータ「ｂ」であって、新たな入力データ「ｂ」と一致する。次の処理＃４では、この番号＃３、＃７および＃１３のスライドに格納される過去の入力データが、リスト探索の対象となる。すなわち、この処理＃３の段階では、番号＃３、＃７および＃１３に係るリストが残っている。処理＃３では、リストの長さが「１」となり、レングスLengthが値「１」とされる。
【００５８】
このような処理を繰り返していき、リストが最も長くなるデータ列を求める。図５の例では、処理＃５において、直前の処理＃４においてリスト探索された番号＃１３のスライドに格納される過去の入力データ「ｃ」と、新たな入力データ「ｇ」とが一致しなくなり、リストが途切れる。そこで、処理＃５では、１つ前の処理＃４において残っているリストから１を選択し、そのスライドのスライド記憶部における位置（番号）をアドレス値Addressとし、リストの長さをレングスLengthとしてスライド符号に符号化する。図５の例では、アドレス値Addressが「１３」、レングスLengthが「３」とされる。
【００５９】
さらに、処理＃５では、入力データ「ｇ」についてスライド探索処理を行う。この例では、各スライドに過去の入力データとしてデータ「ｇ」が記憶されていないため、一致するデータがないとされる。この場合、処理は処理＃６に移行され、入力データ「ｇ」がそのまま用いられてPASS符号に符号化される。
【００６０】
PASS符号への符号化が行われると、処理＃７で、各スライドに記憶される過去の入力データが左に１だけシフトされると共に、直前のリスト探索処理（処理＃５）で入力された入力データ「ｇ」がスライド記憶部の番号＃０のスライドに追加される。そして、次の入力データ「b」に対してスライド探索処理が行われる。
【００６１】
ここで、スライド記憶部は、ＦＩＦＯ方式により各スライドに格納されたデータのシフトを行うことができるため、入力データとの一致を記憶したリストをそのままの状態で保持しながら、次の入力データの処理に移行することができる。
【００６２】
例えば、図５の例では、入力データが、処理＃１において番号＃０、＃３、＃４、＃７、＃１３および＃１５のスライドに格納される過去の入力データと一致している。各スライドに格納されたデータを、新たなデータの入力に伴い順次シフトさせることで、例えば処理＃２の当該番号＃０、＃３、＃４、＃７、＃１３および＃１５のスライドに対して次のデータが格納されることになる。したがって、スライド記憶部において、スライド探索処理で一致が探索された番号のスライドに格納されるデータを、リスト探索処理毎に入力データと比較していくことで、入力データのデータ列と一致する、過去の入力データのデータ列を探索することができる。
【００６３】
このように、スライド記憶部をＦＩＦＯ方式とすることで、リスト探索処理を簡易に行うことができる。
【００６４】
なお、上述の処理によれば、リスト探索処理において入力データと一致するリストが無く、処理がリスト探索処理からスライド探索処理に移行する際に、１処理分、符号化が進行しない時間が生じることになる。すなわち、１処理を１クロックで行うとした場合、リスト探索処理からスライド探索処理に移行する際に、１クロック分の無駄が生じてしまうことになる。
【００６５】
＜フラグ処理＞
上述したスライド探索処理およびリスト探索処理は、フラグによって制御される。このスライド探索処理およびリスト探索処理におけるフラグ処理について、図６および図７を用いて説明する。
【００６６】
図６は、スライド探索処理の結果を示すＲフラグRFLGmを示す。図６に例示されるように、スライド記憶部の各スライドに対して、図の右側から左側へ向けて「ａ，ｂ，ｃ，ａ，ａ，ｂ，ｃ，ａ，ｂ，ｃ，ｄ，ｂ，ｃ，ａ，ｃ，ａ」のように過去の入力データが格納された状態で、入力データ「ａ」が入力された場合、番号＃０、＃３、＃４、＃７、＃１３および＃１５のスライドで、入力データと各スライドに記憶される過去の入力データとが一致する。そこで、これらの番号のスライドに対応するＲフラグRFLG0、RFLG3、RFLG4、RFLG7、RFLG13およびRFLG15を、それぞれ一致したことを示す値「１」とする。
【００６７】
このように、入力データと、各スライドに記憶される過去の入力データとが一致する場合は、符号化処理を行わずにリスト探索処理が行われる。このとき、ＲフラグRFLGmの各スライドに対する位置は、固定的である。入力データと一致する、各スライドに記憶される過去の入力データが無い場合は、入力データをそのまま用いてPASS符号に符号化し、次の入力データに対してスライド探索処理を行う。
【００６８】
図７は、リスト探索処理の結果を示すＷフラグWFLGmの例を示す。リスト探索処理では、新たに入力された入力データと一致するデータが、各スライドのうちＲフラグRFLGmが「１」とされたスライドに格納されるデータから探索される。若し、一致するデータが探索されたら、当該スライドに対するＷフラグWFLGmの値を、一致したことを示す値「１」とする。
【００６９】
図７の例では、各スライドに記憶される過去の入力データのうち、ＲフラグRFLGmが値「１」である番号＃０、＃３、＃４、＃７、＃１３および＃１５のスライドに格納されるデータに対してリスト探索処理が行われる。これらのうち、入力データ「ｃ」に対して、番号＃３、＃７、＃１３および＃１５のスライドに格納されるデータが一致するので、対応するＷフラグWFLG3、WFLG7、WFLG13およびWFLG15の値を、一致したことを示す値「１」とする。各スライドに記憶される過去の入力データのうち、このＷフラグWFLGmの値が「１」とされたスライドに格納されるデータは、直前に入力データと一致したスライドに格納される過去の入力データと、現在入力データと一致した過去の入力データとが連なっていることを示す。
【００７０】
次に、値が「１」のＷフラグWFLGmを探索する。この値「１」のＷフラグWFLGmが存在する場合は、各ＷフラグWFLGmを新たなＲフラグRFLGmとし、上述と同様にして次の入力データに対してリスト探索処理を行う。
【００７１】
一方、探索の結果、値が「１」のＷフラグWFLGmが存在しないとされた場合は、リストが途絶えたことを意味する。この場合は、値が「１」のＲフラグRFLGmを１つ選択し、選択したＲフラグRFLGmに対応するスライドのアドレス値Addressと、そのときのレングスLengthとをスライド符号に符号化する。
【００７２】
ここで、図８および図９を用いて、マシン語のプログラムデータの特徴について、概略的に説明する。図８は、ＲＩＳＣ(Reduced Instruction Set Computer)技術によるＣＰＵに対するマシン語プログラムにおける命令フォーマットの例を示す。図８（ａ）は、Ｒ（レジスタ）タイプ命令の例、図８（ｂ）は、Ｉ（イミディエイト）タイプ命令の例、図８（ｃ）は、Ｊ（ジャンプ）タイプ命令の例をそれぞれ示す。各命令は、３２ビットを所定に分割した領域に所定のニーモニックが格納される。各ニーモニックの意味を、図８（ｄ）に示す。
【００７３】
各ニーモニックのうち、オペレーションコードを示すニーモニック「Ｏｐ」は、Ｒタイプ、ＩタイプおよびＪタイプそれぞれの命令において、固定的に先頭の６ビットの領域に格納される。このように、ＲＩＳＣにおいては、データ長が３２ビットの固定フォーマットで決められた所定領域に対して、同じ意味のコードが格納されるため、スライドが４バイト（３２ビット）毎または８バイト毎に一致する可能性が高くなる。
【００７４】
図９は、マシン語のプログラムデータにおけるスライドの一致位置に関する統計結果の例を示す。図９において、横軸がスライドの一致位置（アドレス値Address）を示し、縦軸が一致回数（出現頻度）を示す。図９に示される統計結果によれば、４バイト毎に一致回数の大きなピークが現れることが示されている。また、４バイト毎のピークを除外して全体的な変化を見ると、一致位置がより近いほどスライドの一致する確率が高くなることが分かる。一方、スライドの一致位置がある程度離れると、低い一致確率に収束することが分かる。
【００７５】
本実施形態では、上述したような、マシン語のプログラムデータにおいて、４バイト毎にスライドの一致確率のピークが現れることを利用して、スライド符号の符号化を行う。
【００７６】
具体的には、スライド符号のアドレス値Addressを、対応するスライドの一致回数が多い順に並べ替えて、並べ替え後の順序を示す値からなる変換アドレス値TAddressを生成する。そして、４ビットで表現可能な所定数の変換アドレス値TAddress、すなわち値が「０」〜「１５」までの変換アドレス値TAddressを、符号長が４ビットの符号に符号化する。この符号長が４ビットの符号に符号化された変換アドレス値TAddressにより、第２スライド符号が形成される。一方、値が「１５」〜「２５５」の変換アドレス値TAddressは、符号長が８ビットの符号に符号化する。この符号長が８ビットの符号に符号化された変換アドレス値TAddressにより、第１スライド符号が形成される。
【００７７】
アドレス値Addressを変換アドレス値TAddressに変換するためには、例えば図１０に例示されるような変換テーブルETRANSTABLEを用いることができる。この変換テーブルETRANSTABLEに列挙される数値は、変換後の変換アドレス値TAddressを示す。また、変換テーブルETRANSTABLEに列挙される数値の順番を示す値（「０」から始まるものとする）が変換前のアドレス値Addressを示す。すなわち、変換テーブルETRANSTABLEに対してアドレス値Addressを入力すると、入力されたアドレス値Addressに対応する位置の値が変換アドレス値TAddressとして出力される。
【００７８】
変換テーブルETRANSTABLEは、図１０から分かるように、４個のアドレス値Address毎に小さい値の変換アドレス値TAddressを割り当てている。換言すれば、図９の統計結果に従い、バイト単位でプログラムデータの４バイト毎に小さい値の変換アドレス値TAddressを割り当てる。また、図９の統計結果によれば、スライドの一致位置がある程度離れると一致回数が少ない値に収束するので、変換テーブルETRANSTABLEの後方に行くに従い、最後尾の値（すなわちアドレス値Address「２５５」）を除き、この変換アドレス値TAddressの規則性を弱めている。
【００７９】
さらに、変換テーブルETRANSTABLEの先頭部分において、アドレス値Address「０」に対して変換アドレス値TAddress「１５」を割り当てている。これは、図９を用いて説明したように、統計結果の全体的な特性として、スライドの一致位置が近いほど一致回数も大きい傾向にあることから来ている。
【００８０】
具体的には、変換テーブルETRANSTABLEにおいて、変換前のアドレス値Address「３」は、変換アドレス値TAddress「０」に変換される。また、変換前のアドレス値Address「０」は、変換アドレス値TAddress「１５」に変換される。同様に、変換前のアドレス値Address「１１」は、変換アドレス値TAddress「２」に変換される。
【００８１】
なお、上述したように、値が「０」〜「１５」までの変換アドレス値TAddressは、全て符号長が４ビットの符号に変換される。そのため、実際には、変換テーブルETRANSTABLEにおいて変換アドレス値TAddress「０」〜「１５」に対応付けるアドレス値Addressの順番は、変更することができる。同様に、変換アドレス値TAddress「１６」〜「２５５」に対応付けるアドレス値Addressの順番も変更できる。
【００８２】
ここでは、変換テーブルETRANSTABLEが、変換アドレス値TAddressが列挙され、変換アドレス値TAddressの順番が元のアドレス値Addressを示すように説明したが、これはこの例に限定されない。例えば、変換前のアドレス値Addressと、変換後の変換アドレス値TAddressとを１対１に対応付けたテーブルとしてもよい。
【００８３】
また、ここでは、小さい値の変換アドレス値TAddressを４バイト毎に割り当てているが、これはこの例に限定されない。すなわち、小さい値の変換アドレス値TAddressの割り当て単位は、プログラムデータの命令フォーマットに応じて設定することができる。例えば、命令フォーマットが６４ビットのデータ長で構成されていれば、小さい値の変換アドレス値TAddressを８バイト毎に割り当てることが考えられる。
【００８４】
＜符号化処理の詳細＞
次に、スライド／リスト生成処理部３０１における符号化処理について、より詳細に説明する。図１１は、本実施形態による符号化処理の全体的な流れを示す一例のフローチャートである。なお、図１１のフローチャートの処理に先立って、符号読み込み部３００は、ある長さのデータを処理対象のデータとして予め保持しているものとする。
【００８５】
最初のステップＳ１０で、スライド／リスト生成処理部３０１は、スライド探索処理およびリスト探索処理のうち何れが有効かを示すフラグListFLGを、スライド探索処理を行っていることを示す値「０」に初期化する。次に、ステップＳ１１で、スライド／リスト生成処理部３０１は、符号読み込み部３００から１単位分のデータを入力データとして読み込む。読み込んだ入力データは、スライド記憶部に格納される。
【００８６】
入力データがスライド記憶部に格納されると、ステップＳ１２で、１単位分のデータに対するスライド探索処理が行われると共に、ステップＳ１３で、１単位分のデータに対するリスト探索処理が行われる。詳細は後述するが、本実施形態においては、スライド探索処理を行うスライド探索部と、リスト探索処理を行うリスト探索部とが別個の構成とされているので、ステップＳ１２およびステップＳ１３の処理を並列的に行うことが可能である。
【００８７】
処理はステップＳ１４に移行され、スライド／リスト生成処理部３０１は、フラグListFLGの値が「０」か否かを判定する。若し、「０」であると判定されたら、現在スライド探索処理が有効であるとされ、処理はステップＳ１５に移行される。ステップＳ１５では、フラグSFINDFLGの値が「１」であるか否かが判定される。若し、値が「１」であれば、スライド記憶部１０１において入力データと一致する過去の入力データが探索されたとされ、ステップＳ１６でフラグListFLGの値がリスト探索処理が有効であることを示す「１」とされる。
【００８８】
そして、処理がステップＳ２５に移行され、スライド記憶部に対して入力データが追加される。次のステップＳ２６で、処理対象のデータ全てに対する処理が終了したか否かが判定される。若し、終了していないと判定されたら、処理はステップＳ１１に戻され、次の１単位分のデータが入力データとして読み込まれる。一方、終了していると判定されたら、一連の符号化処理が終了される。
【００８９】
一方、ステップＳ１５で、フラグSFINDFLGの値が「０」であると判定されたら、スライド記憶部１０１において入力データと一致する過去の入力データが探索されなかったとされ、処理はステップＳ１７に移行される。ステップＳ１７では、フラグListFLGの値が「０」とされてスライド探索処理が有効であるとされ、次のステップＳ１８で入力データがPASS符号に符号化される。また、一致フラグFLAGが値「０」とされる。そして、処理はステップＳ２５に移行される。
【００９０】
また、上述のステップＳ１４において、フラグListFLGの値が「０」ではない、すなわち「１」であると判定されたら、現在リスト探索処理が有効であるとされ、処理がステップＳ１９に移行される。ステップＳ１９では、フラグLFINDFLGの値が「１」か否かを判定する。若し、「１」であると判定されたら、処理はステップＳ２５に移行される。
【００９１】
一方、ステップＳ１９で、フラグLFINDFLGの値が「１」ではない、すなわち、フラグLFINDFLGの値が「０」であると判定されたら、処理はステップＳ２０に移行される。ステップＳ２０では、アドレス値Addressが変換テーブルETRANSTABLEに従い変換アドレス値TAddressに変換され、この変換アドレス値TAddressと、レングスLengthおよびヘッダとが、図４に例示される第１または第２スライド符号に符号化される。そして、処理はステップＳ２１に移行され、フラグSFINDFLGの値が「１」であるか否かが判定される。若し、「１」であると判定されたら、リスト探索処理においてリストが継続されたとされて処理がステップＳ２２に移行され、フラグListFLGの値が「１」とされる。そして、処理がステップＳ２５に移行される。
【００９２】
一方、ステップＳ２０でフラグSFINDFLGの値が「０」であると判定されたら、リスト探索処理においてリストが途切れたとされ、処理がステップＳ２３に移行され、フラグListFLGの値が「０」とされる。次のステップＳ２４で入力データがそのままPASS符号に符号化され、レジスタ１４１に格納される。そして、処理はステップＳ２５に移行される。
【００９３】
図１２は、図１１のステップＳ１２における一例のスライド探索処理をより詳細に示すフローチャートである。なお、この図１２、ならびに、以下の図１３および図１４では、スライド記憶部におけるスライドを、スライドの番号を含めるように、スライド[x]のように表す。また、ＦＩＦＯ構成とされるスライド記憶部において先頭のスライドを、スライド[0]とする。
【００９４】
先ず、ステップＳ３０〜ステップＳ３２で、レングスLength、フラグSFINDFLGおよび変数IWがそれぞれ値「０」に初期化される。処理はステップＳ３３に移行され、入力データとスライド[IW]に格納された過去の入力データとが一致するか否かが判定される。若し、一致すると判定されたら、処理はステップＳ３４に移行され、フラグSFINDFLGの値が「１」とされ、次のステップＳ３５で、ＲフラグRFLG[IW]の値が「１」とされる。
【００９５】
そして、処理はステップＳ３７に移行され、変数IWがスライドサイズ未満、すなわち、スライド記憶部が有するスライド数未満であるか否かが判定される。若し、変数IWがスライドサイズ未満であると判定されたら、ステップＳ３８で変数IWに「１」が加えられ、処理がステップＳ３３に戻される。一方、ステップＳ３７で、変数IWがスライドサイズ以上であると判定されたら、一連の処理が終了される。
【００９６】
一方、ステップＳ３３で入力データとスライド[IW]に格納された過去の入力データとが一致しないと判定されたら、処理はステップＳ３６に移行され、ＲフラグRFLG[IW]の値が「０」とされる。そして、処理がステップＳ３７に移行される。
【００９７】
図１３は、図１１のステップＳ１３による一例のリスト探索処理をより詳細に示すフローチャートである。先ず、ステップＳ４０およびステップＳ４１で、フラグLFINDFLGおよび変数IWがそれぞれ値「０」に初期化される。
【００９８】
ステップＳ４２で、入力データとスライド[IW]に格納された過去の入力データとが一致し、且つ、ＲフラグRFLG[IW]の値が「１」であるか否かが判定される。若し、それぞれの条件を満たすと判定されたら、処理はステップＳ４３に移行され、ＷフラグWFLG[IW]の値が「１」とされ、次のステップＳ４４で、フラグLFINDFLGの値が「１」とされる。そして、処理がステップＳ４６に移行される。
【００９９】
一方、ステップＳ４２で、上述の条件を満たさない、すなわち、入力データとスライド[IW]に格納された過去の入力データとが一致しない、または、ＲフラグRFLG[IW]の値が「１」でないと判定されたら、処理はステップＳ４５に移行され、ＷフラグWFLG[IW]の値が「０」とされる。そして、処理がステップＳ４６に移行される。
【０１００】
ステップＳ４６では、変数IWがスライドサイズ未満であるか否かが判定される。若し、変数IWがスライドサイズ未満であると判定されたら、ステップＳ４７で変数IWに「１」が加えられ、処理がステップＳ４２に戻される。一方、変数IWがスライドサイズ以上であると判定されたら、処理がステップＳ４８に移行される。
【０１０１】
ステップＳ４８では、フラグLFINDFLGの値が「０」であるか否かが判定される。若し、値が「０」であると判定されたら、処理がステップＳ４９に移行されて変数IWが値「０」に初期化され、次のステップＳ５０でＲフラグRFLG[IW]の値が「１」であるか否かが判定される。若し、「１」であると判定されたら、処理はステップＳ５１に移行される。
【０１０２】
ステップＳ５１では、変数IWがアドレス値Addressとされ、次のステップＳ５２で、スライドサイズを変数IWに代入する。そして、処理がステップＳ５３に移行される。ステップＳ５３では、変数IWがスライドサイズ未満であるか否かが判定される。若し、変数IWがスライドサイズ未満であると判定されたら、ステップＳ５４で変数IWに「１」が加算されて処理がステップＳ５０に戻される。
【０１０３】
一方、ステップＳ５３で、変数IWがスライドサイズ以上であると判定されたら、一連の処理が終了される。例えば、上述したステップＳ５２を経由してこのステップＳ５３に到達した場合、ステップＳ５２で変数IWにスライドサイズが代入されているため、必ず処理が終了される。
【０１０４】
上述したステップＳ４８で、フラグLFINDFLGの値が「０」ではないと判定されたら、処理はステップＳ５５に移行され、変数IWが値「０」に初期化される。次のステップＳ５６で、ＲフラグRFLG[IW]に対してＷフラグWFLG[IW]が設定される。そして、ステップＳ５７で、変数IWがスライドサイズ未満であるか否かが判定される。若し、変数IWがスライドサイズ未満であると判定されたら、ステップＳ５８で変数IWに「１」が加算されて処理がステップＳ５６に戻される。一方、ステップＳ５７で変数IWがスライドサイズ以上であると判定されたら、処理は次のステップＳ５９に移行され、レングスLengthに対して１が加算され、一連の処理が終了される。
【０１０５】
図１４は、図１１のステップＳ２５による一例のスライド追加処理をより詳細に示す一例のフローチャートである。先ず、ステップＳ７０で、変数IWがスライド数から１を減じた値に設定される。次のステップＳ７１で、スライド[IW]に、スライド[IW−１]の値が格納され、ステップＳ７２で、変数IWが「０」を超えるか否かが判定される。若し、変数IWが「０」を超えると判定されたら、処理はステップＳ７３に移行され、変数IWから「１」が減じられる。そして、処理がステップＳ７１に戻される。一方、ステップＳ７２で、変数IWが「０」以下であると判定されたら、処理はステップＳ７４に移行され、スライド[0]に対して入力データが格納される。
【０１０６】
図１５は、図１１のステップＳ２０による一例のスライド符号化処理をより詳細に示す。符号フォーマットは、図４に示したフォーマットに従うものとする。先ず、ステップＳ８０で、アドレス値Addressが変換テーブルETRANSTABLEにより変換アドレス値TAddressに変換される。次に、ステップＳ８１で、変換アドレス値TAddressの値が「１６」未満であるか否かが判定される。なお、変換アドレス値TAddressは、値「０」から開始されるものとする。
【０１０７】
若し、変換アドレス値TAddressが値「１６」未満であると判定されたら、処理はステップＳ８２に移行され、ヘッダの符号化が行われる。この例では、ヘッダは、符号長が２ビット、値「１０」の符号に符号化される。ヘッダの符号化が行われると、次のステップＳ８３で、一致長さすなわちレングスLengthの符号化が行われる。この例では、レングスLengthは、符号長が８ビットの符号に符号化される。そして、次のステップＳ８４で、一致位置すなわち変換アドレス値TAddressの符号化がなされる。変換アドレス値TAddressが値「１６」未満であるので、符号長が４ビットの符号に符号化される。
【０１０８】
一方、変換アドレス値TAddressが値「１６」以上であると判定されたら、処理はステップＳ８５に移行され、ヘッダの符号化が行われる。この例では、ヘッダは、符号長が２ビット、値「１１」の符号に符号化される。ヘッダの符号化が行われると、次のステップＳ８６で、一致長さすなわちレングスLengthの符号化が行われる。この例では、レングスLengthは、符号長が８ビットの符号に符号化される。そして、次のステップＳ８７で、一致位置すなわち変換アドレス値TAddressの符号化がなされる。変換アドレス値TAddressが値「１６」以上であるので、符号長が８ビットの符号に符号化される。
【０１０９】
図１６は、エンコーダ２４２の一例の構成をより詳細に示す。なお、図１６において、上述の図３と共通する部分には同一の符号を付し、詳細な説明を省略する。エンコーダ２４２は、データ読み込み部３００、スライド／リスト生成処理部３０１、符号フォーマット生成処理部３０２および符号書き込み部３０３を有すると共に、メモリコントローラＩ／Ｆ３１０、データアドレス生成部３１１および符号アドレス生成部３１２を有する。
【０１１０】
データアドレス生成部３１１は、メインメモリ２１０のプログラム領域２１０Ａからプログラムデータを読み出す際のメモリアドレスを生成する。データ読み込み部３００は、データアドレス生成部３１１で生成されたメモリアドレスからのデータの読み出しを、メモリコントローラＩ／Ｆ３１０を介してメモリコントローラ２０２に対して要求する。この要求に応じてメモリコントローラ２０２によりメインメモリ２１０のプログラム領域２１０Ａから読み出されたプログラムデータがメモリコントローラ２０２からエンコーダ２４２に対して供給され、メモリコントローラＩ／Ｆ３１０を介してデータ読み込み部３００に供給される。データ読み込み部３００は、供給されたプログラムデータを、スライド／リスト生成処理部３０１に供給する。
【０１１１】
スライド／リスト生成処理部３０１は、供給されたプログラムデータから、既に説明したようにしてアドレス値Address、レングスLength、PASS符号およびヘッダを生成する。ここで、アドレス値Addressは、変換テーブルETRANSTABLEにより変換アドレス値TAddressに変換される。これら変換アドレス値TAddress、レングスLength、PASS符号（データ値）およびヘッダは、符号フォーマット生成処理部３０２に供給される。符号フォーマット生成処理部３０２は、図４で説明した符号フォーマットに従い、供給された各値からPASS符号、第１スライド符号および第２スライド符号を生成する。生成されたPASS符号、第１スライド符号および第２スライド符号は、符号書き込み部３０３に供給される。
【０１１２】
符号書き込み部３０３は、供給されたPASS符号、第１スライド符号および第２スライド符号をメモリコントローラＩ／Ｆ３１０を介してメモリコントローラ２０２に供給する。それと共に、符号書き込み部３０３は、これらの符号を符号アドレス生成部３１２で生成されたメモリアドレスに従いフラッシュメモリ２４０に書き込むように、メモリコントローラＩ／Ｆ３１０を介してメモリコントローラ２０２に要求する。メモリコントローラ２０２は、この要求に従い、供給された符号を、フラッシュメモリコントローラ２４１を介してフラッシュメモリ２４０に書き込む。
【０１１３】
＜スライド／リスト生成処理部のハードウェア構成例＞
図１７は、上述したスライド探索処理、リスト探索処理および符号化処理を実行するスライド／リスト生成処理部３０１の、一例のハードウェア構成を示す。スライド／リスト生成処理部３０１は、スライド探索部１００、スライド記憶部１０１、リスト探索部１０２およびコントローラ１０３を有する。
【０１１４】
コントローラ１０３は、例えばマイクロプロセッサからなり、図１１のフローチャートを用いて説明した、ステップＳ１２およびステップＳ１３の処理を除いた、ステップＳ１１〜ステップＳ２６による処理を行い、スライド／リスト生成処理部３０１の動作を制御する。例えば、コントローラ１０３は、上述した現在スライド探索処理およびリスト探索処理のうち何れが有効かを示すフラグListFLGによる動作制御を行う。
【０１１５】
スライド／リスト生成処理部３０１に対して、例えば１クロック毎に１単位の入力データが入力され、スライド探索部１００、スライド記憶部１０１およびリスト探索部１０２にそれぞれ供給される。入力データは、さらに、出力側のレジスタ１４１にも格納される。レジスタ１４１に格納される入力データは、PASS符号の符号化の際のデータ値として用いられる。以下では、データの１単位を１バイトとする。
【０１１６】
スライド記憶部１０１は、各々がレジスタからなり、それぞれ１単位のデータが格納されるｎ個（例えば２５６個）のスライド１２０1、１２０2、…、１２０nが直列に接続されて構成される。また、各スライド１２０1、１２０2、…、１２０nの出力は、次のレジスタに供給されると共に、後述するスライド探索部１００の対応する比較器１１１mの一方の入力端と、リスト探索部１０２の対応する比較器１３０mの一方の入力端にそれぞれ供給される。
【０１１７】
なお、比較器１３０mは、比較器１３０1〜１３０nのうち任意の比較器を表す。このような表記は、比較器１１１1〜１１１n、セレクタ１３１1〜１３１n、レジスタ１３２1〜１３２nにおいて共通とする。
【０１１８】
なお、アドレス値AddressおよびレングスLengthのデータ長は、スライド記憶部１０１が有するスライド数ｎに応じて決められる。すなわち、スライド数ｎ＝２５６であれば、アドレス値AddressおよびレングスLengthが「２５６」までの値を表現可能に、それぞれのデータ長が８ビットに決められる。
【０１１９】
スライド記憶部１０１は、これらｎ個のスライド１２０1、１２０2、…、１２０nによりＦＩＦＯが構成され、入力されたデータがスライド１２０1からスライド１２０2、スライド１２０3、…と１クロック毎に順次送られていく。
【０１２０】
スライド探索部１００は、ｎ個の比較器１１１1、１１１2、…、１１１nと、ｎ入力の論理和回路１１０とを有する。比較器１１１1、１１１2、…、１１１nのそれぞれは、一方および他方の入力端に入力されたデータを比較し、両者が一致していれば値「１」を出力し、一致していなければ値「０」を出力する。
【０１２１】
比較器１１１1、１１１2、…、１１１nの一方の入力端には、上述したように、スライド記憶部１０１が有するスライド１２０1、１２０2、…、１２０nの出力がそれぞれ入力される。また、比較器１１１1、１１１2、…、１１１nそれぞれの他方の入力端には、入力データが入力される。
【０１２２】
比較器１１１1、１１１2、…、１１１nそれぞれの出力は、ｎ入力の論理和回路１１０に入力されると共に、後述するリスト探索部１０２のセレクタ（ＳＥＬ）１３１1、１３１2、…、１３１nの一方の入力端にそれぞれ入力される。論理和回路１１０の出力は、フラグSFINDFLGとしてコントローラ１０３に供給される。このフラグSFINDFLGは、スライド１２０1、１２０2、…、１２０nのデータのうち少なくとも１が入力データと一致しているか否かを示す。
【０１２３】
リスト探索部１０２は、それぞれｎ個の比較器１３０1、１３０2、…、１３０n、セレクタ１３１1、１３１2、…、１３１n、ならびに、レジスタ１３２1、１３２2、…、１３２nと、アドレス値生成部１３３と、ｎ入力の論理和回路１３４とを有する。比較器１３０1、１３０2、…、１３０nのそれぞれは、一方および他方の入力端に入力されたデータを比較し、両者が一致していれば値「１」を出力し、一致していなければ値「０」を出力する。
【０１２４】
比較器１３０1、１３０2、…、１３０nの一方の入力端には、上述したように、スライド記憶部１０１が有するスライド１２０1、１２０2、…、１２０nの出力がそれぞれ入力される。また、比較器１３０1、１３０2、…、１３０nそれぞれの他方の入力端には、入力データが入力される。
【０１２５】
比較器１３０1、１３０2、…、１３０nの出力は、ＷフラグWFLGmであって、ｎ入力の論理和回路１３４にそれぞれ入力されると共に、セレクタ１３１1、１３１2、…、１３１nの他方の入力端にそれぞれ入力される。論理和回路１３４の出力は、フラグLFINDFLGとしてコントローラ１０３に供給される。フラグLFINDFLGは、ＷフラグWFLG1、WFLG2、…、WFLGnのうち少なくとも１の値が「１」であることを示す。
【０１２６】
セレクタ１３１1、１３１2、…、１３１nの出力は、ＲフラグRFLGmとされて、それぞれレジスタ１３２1、１３２2、…、１３２nに格納される。セレクタ１３１1、１３１2、…、１３１nは、コントローラ１０３から図示しない経路を経て供給されるフラグListFLGにより、一方および他方の端子のうち何れを選択するかが制御される。
【０１２７】
若し、フラグListFLGの値が「０」であって、現在スライド探索処理が有効であることが示されていれば、セレクタ１３１1、１３１2、…、１３１nは、それぞれの一方の入力端に入力された、スライド探索部１００における比較器１１１1、１１１2、…、１１１nの出力をレジスタ１３２1、１３２2、…、１３２nに供給するように制御される。例えば、セレクタ１３１m（なお、１≦ｍ≦ｎとする）は、対応するレジスタ１３２mに格納される値が「０」のときに入力端が選択されるように制御される。
【０１２８】
一方、フラグListFLGの値が「１」であって、現在リスト探索処理が有効であることが示されていれば、セレクタ１３１1、１３１2、…、１３１nは、それぞれの他方の入力端に入力された、リスト探索部１０２における比較器１３０1、１３０2、…、１３０nを選択してレジスタ１３２1、１３２2、…、１３２nに供給するように制御される。例えば、セレクタ１３１mは、対応するレジスタ１３２mに格納される値が「１」のときに他方の入力端が選択されるように制御される。
【０１２９】
レジスタ１３２1、１３２2、…、１３２nは、セレクタ１３１1、１３１2、…、１３１nからの出力が供給されると、格納されているＲフラグRFLG1、RFLG2、…、RFLGnを出力する。すなわち、レジスタ１３２1、１３２2、…、１３２nに格納されるＲフラグRFLG1、RFLG2、…、RFLGnは、供給されたセレクタ１３１1、１３１2、…、１３１nからの出力により更新される。
【０１３０】
レジスタ１３２1、１３２2、…、１３２nから出力されたＲフラグRFLG1、RFLG2、…、RFLGnは、比較器１３０1、１３０2、…、１３０nの動作を制御する制御信号として、比較器１３０1、１３０2、…、１３０nの制御端にそれぞれ供給される。例えば、例えば比較器１３０mは、対応するレジスタ１３２mから供給された制御信号が値「１」を示していれば比較動作を行い、値「０」を示していれば比較動作を行わない。これは、比較器１３０1、１３０2、…、１３０nそれぞれの動作は、比較器１３０1、１３０2、…、１３０n自身の出力により絞り込まれていくことを意味する。
【０１３１】
レジスタ１３２1、１３２2、…、１３２nから出力されたＲフラグRFLG1、RFLG2、…、RFLGnは、さらにアドレス値生成部１３３にも供給される。アドレス値生成部１３３は、図４の処理＃５で説明したように、リスト探索処理が終了した際に、レジスタ１３２1、１３２2、…、１３２nから供給されるＲフラグRFLG1、RFLG2、…、RFLGnのうち、値が「１」であるＲフラグRFLGmを選択し、選択されたＲフラグRFLGmの番号をアドレス値Addressとして出力する。アドレス値生成部１３３から出力されたアドレス値Addressは、アドレス変換部１４４に供給される。
【０１３２】
アドレス変換部１４４は、図１０を用いて説明した変換テーブルETRANSTABLEを持ち、供給されたアドレス値Addressを、変換テーブルETRANSTABLEに従い変換アドレス値TAddressに変換する。アドレス値Addressが変換された変換アドレス値TAddressは、レジスタ１４０に格納されると共に、コントローラ１０３に供給される。
【０１３３】
コントローラ１０３は、スライド探索部１００から供給されたフラグSFINDFLGと、リスト探索部１０２から供給されたフラグLFINDFLGと、アドレス変換部１４４から供給された変換アドレス値TAddress値とに基づき、レングスLengthおよびヘッダを生成する。レングスLengthおよび一致フラグFLAGは、それぞれレジスタ１４３および１４２に格納される。
【０１３４】
なお、レジスタ１４０〜１４３にそれぞれ格納された変換アドレス値TAddress、データ値、ヘッダおよびレングスLengthは、それぞれ符号フォーマット生成処理部３０２に読み出され、図４に例示する符号フォーマットに従い符号化され符号データが生成される。
【０１３５】
このような構成において、スライド探索処理は、以下のように行われる。すなわち、比較器１１１1、１１１2、…、１１１nによる、入力データと、スライド１２０1、１２０2、…、１２０nに格納された過去の入力データとの比較処理が行われる。比較結果がそれぞれ論理和回路１１０に供給され、フラグSFINDFLGが出力される。比較結果は、セレクタ１３１1、１３１2、…、１３１nにも供給され、スライド探索処理の間は、レジスタ１３２1、１３２2、…、１３２nに格納される。図１７の構成によれば、この一連の処理を１クロックで実行可能である。
【０１３６】
また、リスト探索処理は、以下のように行われる。すなわち、比較器１３０1、１３０2、…、１３０nによる、入力データと、スライド１２０1、１２０2、…、１２０nに格納された過去の入力データとの比較処理が行われる。このとき、レジスタ１３２1、１３２2、…、１３２nに格納されるＲフラグRFLG1、RFLG2、…、RFLGnの値に基づき、比較器１３０1、１３０2、…、１３０nの比較動作が制御される。例えば、ＲフラグRFLG1、RFLG2、…、RFLGnの値が全て「０」であれば、比較器１３０1、１３０2、…、１３０n全ての比較動作が行われないことになる。この状態を、リスト探索処理が行われていない状態とする。
【０１３７】
比較器１３０1、１３０2、…、１３０nによる比較結果がそれぞれ論理和回路１３４に供給され、フラグLFINDFLGが出力される。また、各比較結果は、セレクタ１３１1、１３１2、…、１３１nに供給され、リスト探索処理の間は、レジスタ１３２1、１３２2、…、１３２nに格納される。また、レジスタ１３２1、１３２2、…、１３２nに格納されるＲフラグRFLG1、RFLG2、…、RFLGnは、アドレス値生成部１３３にも保持される。
【０１３８】
アドレス値生成部１３３は、レジスタ１３２1、１３２2、…、１３２nに格納される値が全て「０」であれば、保持しているＲフラグRFLG1、RFLG2、…、RFLGnのうち値が「１」のＲフラグRFLGmの位置を、アドレス値Addressとし、さらにアドレス変換部１４４で変換アドレス値TAddressとしてコントローラ１０３に渡す。図１７の構成によれば、このリスト探索処理による一連の処理を１クロックで実行可能である。
【０１３９】
図１７の構成によれば、スライド探索部１００と、リスト探索部１０２とがそれぞれ別個の構成とされると共に、スライド探索部１００とリスト探索部１０２とでスライド記憶部１００を共有する。そのため、スライド探索部１００によるスライド探索処理と、リスト探索部１０２によるリスト探索処理とを並列的に実行することが可能である。したがって、リスト探索処理からスライド探索処理へと移行する際の１クロック分の無駄が生じず、符号化処理をより高速化できる。また、図１７の構成によれば、先読みバッファや大規模なマトリクスアレイなどの構成が不要なので、ハードウェア規模を小さくできる。
【０１４０】
なお、エンコーダ２４２の構成は、図１７に示した構成に限定されない。すなわち、ＬＺ７７符号の符号化を行い、レングスLengthおよびアドレス値Addressを出力するものであれば、他の構成のエンコーダを適用することができる。
【０１４１】
＜デコーダ＞
図１８は、デコーダ２４３の一例の構成を示す。デコーダ２４３において、符号読み込み部４００により、上述したエンコーダ２４２で符号化された符号データがフラッシュメモリ２４０から読み込まれる。符号読み込み部４００に読み込まれた符号データは、符号フォーマット解析部４０１に供給される。符号フォーマット解析部４０１は、図４を用いて説明した符号フォーマットに従い、供給された符号データを解釈してデータ値、変換アドレス値TAddress、レングスLengthおよびヘッダを取り出す。取り出されたこれらのデータは、スライド展開部４０２に供給される。
【０１４２】
スライド展開部４０２は、図５を用いて説明したように、直列に接続された複数のレジスタがＦＩＦＯとして構成される、スライド記憶部を持つ。各レジスタは、スライドと呼ばれ、それぞれ１単位（例えば１バイト）のデータを格納可能とされる。スライド展開部４０２は、供給された変換アドレス値TAddressを元のアドレス値Addressに逆変換し、このアドレス値Addressと、供給されたデータ値、レングスLengthおよびヘッダに基づき、スライド記憶部における各スライドに対してデータを展開し、符号データを復号する。復号されたデータは、データ書き込み部４０３に供給され、メインメモリ２１０のプログラム領域２１０Ａに書き込まれる。
【０１４３】
図１９は、変換アドレス値TAddressを元のアドレス値Addressに変換するための逆変換テーブルDTRANSTABLEの一例を示す。この逆変換テーブルDTRANSTABLEに列挙される数値は、元のアドレス値Addressを示す。また、逆変換テーブルDTRANSTABLEに列挙される数値の順番を示す値が、変換アドレス値TAddressを示す。
【０１４４】
すなわち、逆変換テーブルDTRANSTABLEにおいて、変換アドレス値TAddress「０」は、元のアドレス値Address「３」に変換される。また、変換アドレス値TAddress「１５」は、元のアドレス値Address「０」に変換される。同様に、変換アドレス値TAddress「２」は、元のアドレス値Address「１１」に変換される。
【０１４５】
＜復号処理の詳細＞
図２０は、上述した本実施形態の符号化方法により符号化された符号データを、デコーダ２４３で復号する一例の処理を示すフローチャートである。なお、符号読み込み部４００により、フラッシュメモリ２４０から予め符号データが読み込まれているものとする。先ず、ステップＳ１００で、符号フォーマット解析部４０１は、符号読み込み部４００に読み込まれている圧縮データのヘッダを読み込み、ヘッダの値が「０」であるか否かを判定する（ステップＳ１０１）。
【０１４６】
若し、ヘッダの値が「０」であれば、当該ヘッダを含む符号がPASS符号であると判定され、処理がステップＳ１０２に移行される。ステップＳ１０２で、符号フォーマット解析部４０１は、次のステップＳ１０２でヘッダに続く８ビットをデータ値として読み込む。読み込まれたデータ値は、そのまま出力データとして出力される（ステップＳ１０３）と共に、スライド展開部４０２に供給されスライドに追加される（ステップＳ１０４）。データ値のスライドに対する追加処理は、図１４のフローチャートで説明したのと同様の手順により行われる。そして、処理がステップＳ１１５に移行される。
【０１４７】
ステップＳ１１５では、例えば符号読み込み部４００により、読み込まれている符号データに対する処理が全て終了したか否かが判定される。全て終了したと判定されたら、一連の復号処理が終了される。一方、符号読み込み部４００に読み込まれている全ての符号データに対する処理が終了していないと判定されたら、処理はステップＳ１００に戻され、次の符号に対する処理が行われる。
【０１４８】
符号フォーマット解析部４０１は、ステップＳ１０１でヘッダの値が「０」ではないと判定したら、処理をステップＳ１０５に移行させ、ヘッダに続く８ビットをレングスLengthとして読み込む。読み込んだレングスLengthは、スライド展開部４０２に供給される。
【０１４９】
次のステップＳ１０６で、符号フォーマット解析部４０１は、ヘッダの値が「１１」であるか否かを判定する。若し、ヘッダの値が「１１」であると判定したら、処理をステップＳ１０７に移行させ、ヘッダに続く４ビットを変換アドレス値TAddressとして読み込む。一方、ヘッダの値が「１１」ではないと判定したら、処理をステップＳ１０８に移行させ、ヘッダに続く８ビットを変換アドレス値TAddressとして読み込む。ステップＳ１０７またはステップＳ１０８で読み込まれた変換アドレス値TAddressは、スライド展開部４０２に供給される。
【０１５０】
次のステップＳ１０９で、スライド展開部４０２は、図１９に例示した逆変換テーブルDTRANSTABLEを用いて、変換アドレス値TAddressを元のアドレス値Addressに変換する。
【０１５１】
次のステップＳ１１０で、スライド展開部４０２は、スライド記憶部のアドレス値Addressで示されるスライドに格納されるデータを読み込む。読み込まれたデータは、出力データとして出力される（ステップＳ１１１）と共に、スライド展開部４０２に供給されスライドに追加される（ステップＳ１１２）。
【０１５２】
処理はステップＳ１１３に移行され、レングスLengthが「０」より大きいか否かが判定される。若し、レングスLengthが「０」以下であると判定されたら、処理はステップＳ１１５に移行される。一方、レングスLengthが「０」より大きいと判定されたら、ステップＳ１１４でレングスLengthから「１」が減じられた値が新たなレングスLengthとされて、処理がステップＳ１１０に戻される。
【０１５３】
図２１は、デコーダ２４３の一例の構成をより詳細に示す。なお、図２１において、上述の図１８と共通する部分には同一の符号を付し、詳細な説明を省略する。デコーダ２４３は、符号読み込み部４００、符号フォーマット解析部４０１、スライド展開部４０２およびデータ書き込み部４０３を有すると共に、メモリコントローラＩ／Ｆ４１０、符号アドレス生成部４１１およびデータアドレス生成部４１２を有する。
【０１５４】
符号アドレス生成部４１１は、フラッシュメモリ２４０から圧縮符号化されたプログラムデータを読み出す際のメモリアドレスを生成する。符号読み込み部４００は、符号アドレス生成部４１１で生成されたメモリアドレスからのデータの読み出しを、メモリコントローラＩ／Ｆ４１０を介してメモリコントローラ２０２に対して要求する。この要求に応じてメモリコントローラ２０２によりフラッシュメモリ２４０から読み出された、プログラムデータが圧縮符号化された符号データが、メモリコントローラ２０２からデコーダ２４３に対して供給され、メモリコントローラＩ／Ｆ４１０を介して符号読み込み部４００に供給される。符号読み込み部４００は、この符号データを、符号フォーマット解析部４０１に供給する。
【０１５５】
符号フォーマット解析部４０１は、図４で説明した符号フォーマットに従い、供給された符号データから、ヘッダ、レングスLength、データ値および変換アドレス値TAddressを取り出して、スライド展開部４０２に供給する。ここで、変換アドレス値TAddressは、逆変換テーブルDTRANSTABLEを用いて元のアドレス値Addressに変換される。スライド展開部４０２は、このアドレス値Addressと、供給されたデータ値、レングスLengthおよびヘッダに基づき、スライド記憶部における各スライドに対してデータを展開し、符号データを元のプログラムデータに復号する。復号されたプログラムデータは、データ書き込み部４０３に供給される。
【０１５６】
データ書き込み部４０３は、供給されたプログラムデータをメモリコントローラＩ／Ｆ４１０を介してメモリコントローラ２０２に供給する。それと共に、データ書き込み部４０３は、当該プログラムデータをデータアドレス生成部４１２で生成されたメモリアドレスに従いメインメモリ２１０のプログラム領域２１０Ａに書き込むように、メモリコントローラＩ／Ｆ３１０を介してメモリコントローラ２０２に要求する。メモリコントローラ２０２は、この要求に従い、供給されたプログラムデータを、メインメモリ２１０のプログラム領域２１０Ａに書き込む。
【０１５７】
＜スライド展開部のハードウェア構成＞
図２２は、スライド展開部４０２の一例のハードウェア構成を示す。スライド展開部４０２は、スライド記憶部５００、コントローラ５０１、セレクタ５０２および５０３、ならびに、アドレス逆変換部５２０を有する。アドレス逆変換部５２０は、上述した逆変換テーブルDTRANSTABLEを有し、符号フォーマット解析部４０１から供給された変換アドレス値TAddressを逆変換テーブルDTRANSTABLEを用いて元のアドレス値Addressに変換して、コントローラ５０１に渡す。
【０１５８】
コントローラ５０１は、例えばマイクロプロセッサからなり、アドレス値Address、レングスLengthおよび一致フラグFLAGが供給され、供給されたこれらのデータに基づきこのスライド展開部４０２の全体の動作を制御する。例えばコントローラ５０１は、スライド記憶部５００におけるデータ値のスライドに対する追加処理や、セレクタ５０２および５０３の動作などを制御する。
【０１５９】
スライド記憶部５００は、各々がレジスタからなり、それぞれ１単位のデータが格納されるｎ個のスライド５１１1、５１１2、…、５１１nが直列に接続されて構成されたＦＩＦＯと、当該ＦＩＦＯの先頭に接続されるセレクタ５１０とを有する。
【０１６０】
各スライド５１０1、５１０2、…、５１０nの出力は、さらに、それぞれセレクタ５０２に供給される。セレクタ５０２の出力は、セレクタ５０３に供給されると共に、セレクタ５１０にも供給される。
【０１６１】
符号フォーマット解析部４０１から読み込まれたデータ値がセレクタ５１０に供給されると共に、セレクタ５０３にも供給される。セレクタ５１０は、図１３のステップＳ１０４のスライド追加処理時には、入力されたデータ値をスライド５１１1に追加する。また、図１３のステップＳ１０８のスライド追加処理時には、ステップＳ１０６においてスライド符号のアドレス値Addressに基づき選択されたスライドから出力されたデータを、スライド５１１1に追加する。
【０１６２】
セレクタ５０２は、図１３のステップＳ１０６の処理時に、コントローラ５０１から供給されるアドレス値Addressに従い、スライド記憶部５００の各スライド５１１1、５１１2、…、５１１nの出力からスライド５１１Addressの出力を選択し、選択した出力を、セレクタ５０３および５１０にそれぞれ供給する。
【０１６３】
セレクタ５０３は、図１３のステップＳ１０３において、ステップＳ１０２で読み込まれたデータ値を出力する。また、図１３のステップＳ１０７のデータ出力処理時に、セレクタ５０２から供給されたデータを出力する。
【０１６４】
なお、デコーダ２４３の構成は、図２２に示した構成に限定されない。すなわち、レングスLengthおよびアドレス値Addressに基づきＬＺ７７符号の復号を行うものであれば、他の構成のデコーダを適用することができる。
【０１６５】
また、上述では、本発明がプリンタ装置に適用されるように説明したが、これは一例でありこの例に限定されない。すなわち、本発明は、マシン語のプログラムデータの可逆符号化をハードウェアを用いて行う他の装置にも適用することが可能である。
【符号の説明】
【０１６６】
１００ スライド探索部
１０１ スライド記憶部
１０２ リスト探索部
１０３ コントローラ
１１０，１３４ 論理和回路
１１１1〜１１１n，１３０1〜１３０n 比較器
１２０1〜１２０n スライド
１３１1〜１３１n セレクタ
１３２1〜１３２n レジスタ
１３３ アドレス値生成部
１４４ アドレス変換部
２００ プリンタ装置
２１０ メインメモリ
２１０Ａ プログラム領域
２４０ フラッシュメモリ
２４２ エンコーダ
２４３ デコーダ
３０１ スライド／リスト生成処理部
４０２ スライド展開部
５００ スライド記憶部
５０１ コントローラ
５０２，５０３，５１０ セレクタ
５１１1〜５１１n スライド
５２０ アドレス逆変換部
【先行技術文献】
【特許文献】
【０１６７】
【特許文献１】特開平７−３１９７４３号公報
【特許文献２】特開２００４−１７８２８９号公報
【技術分野】
【０００１】
本発明は、データの符号化および復号を行うデータ処理装置およびデータ処理方法に関する。
【背景技術】
【０００２】
従来から、ハードディスクドライブ（ＨＤＤ）といった２次記憶媒体に対して格納するプログラムやデータ（以下、特に記載のない限り、これらを纏めてデータと呼ぶ）を圧縮符号化することが行われていた。データを圧縮符号化してＨＤＤなどに格納することで、記憶領域を節約してより多くのデータが格納可能となる。また、圧縮符号化により格納されるデータのデータサイズが小さくなるため、ＨＤＤに対するアクセス速度が向上するという効果もある。
【０００３】
特許文献１には、ＨＤＤに格納されるデータに対して参照頻度や属性値を付加し、より頻繁にアクセスされるデータは圧縮符号化を行わず、アクセス頻度のより低いデータを圧縮符号化してＨＤＤに格納する技術が開示されている。特許文献１によれば、データの圧縮符号化および復号処理を含めたＨＤＤに対するアクセス速度を向上させることが可能となる。
【０００４】
また、近年では、機器を休止状態から高速に起動するために、機器が休止状態に移行する際にメモリの状態をイメージ化したスナップショットを保持しておき、機器が休止状態から復帰する際に、このスナップショットをメモリの元の位置に展開し直すことで、当該メモリの状態をスナップショット取得時の状態に復元する技術が知られている。特許文献２には、パーティション、ファイル、ディレクトリ単位でのスナップショットの取得方法について開示されている。
【０００５】
さらに、近年では、主記憶装置の状態を丸ごとイメージ化したスナップショットをハードディスクドライブなどに保持することで、省電力モードなどの休止状態から復帰する際の起動を高速化する、ハイバネーションと呼ばれる技術が実用化されている。
【０００６】
ところで、データを効率よく圧縮符号化する方法として、ユニバーサル符号により圧縮符号化する方法が実用化されている。このユニバーサル符号は、情報保存型のデータ圧縮方法であり、データ圧縮時に情報源の統計的な性質を予め仮定しないため、種々のタイプ（文字コード、オブジェクトコードなど）のデータに適用することができる。
【０００７】
ユニバーサル符号の代表的な方法として、ジブ−レンペル(Ziv-Lempel)符号がある。Ziv-Lempel符号では、ユニバーサル型と、増分分解型(Incremental parsing) の２つのアルゴリズムが提案されている。これらのうち、ユニバーサル型アルゴリズムを用いた実用的な方法として、ＬＺＳＳ(Lempel-Ziv-Storer-Syzmanski)符号がある。
【０００８】
ＬＺＳＳ符号のベースとなるＬＺ７７符号の符号化アルゴリズムは、符号化データを、過去のデータ系列の任意の位置から一致する最大長の系列に区切り、過去の系列の複製として符号化する。
【０００９】
より具体的には、符号化済みの入力データを格納する移動窓と、これから符号化するデータを格納する先読みバッファとを備え、先読みバッファのデータ系列と移動窓のデータ系列の全ての部分系列とを照合して、移動窓中で一致する最大長の部分系列を求める。そして、移動窓中でこの最大長の部分系列を指定するために、「その最大長の部分系列の開始位置」と「一致する長さ」と「不一致をもたらした次のシンボル」との組を符号化する。
【００１０】
次に、先読みバッファ内の符号化したデータ系列を移動窓に移して、先読みバッファ内に符号化したデータ系列分の新たなデータ系列を入力する。以下、同様の処理を繰り返していくことで、データを部分系列に分解して符号化を実行していく。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ところで、上述したハイバネーションでは、主記憶装置の状態を丸ごとイメージ化したスナップショットを作成する。すなわち、ハイバネーションにより作成されるスナップショットは、スナップショット作成直前に起動していたプログラムのコードデータを含むことになる。
【００１２】
近年の多くのＣＰＵ(Central Processing Unit)は、ＲＩＳＣ(Reduced Instruction Set Computer)方式を採用しているため、マシン語によるプログラムのコードデータは、４バイトや８バイト単位で命令が並び、この４バイトや８バイト毎にデータが一致する可能性が高い。また、この４バイトや８バイト毎の一致可能性のピークを無視して全体を考えた場合、最近出現したバイトで一致可能性が高くなる。一方、ある程度離れたバイトでは、一致可能性の低い同じような確率が続くことになる。
【００１３】
そのため、上述したユニバーサル符号を用いて一致位置に対して静的なハフマン符号化を行っても、余り符号化効率が良くないという問題点があった。また、符号化効率の割にはハードウェア構成が複雑となり、設計コストが嵩むと共にバグの可能性が増加するおそれがあるという問題点があった。
【００１４】
本発明は、上記に鑑みてなされたものであって、特にマシン語のプログラムデータの圧縮符号化および復号処理を行うために用いて好適なデータ処理装置およびデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上述した課題を解決し、目的を達成するために、本発明は、入力データを順次記憶するスライド記憶手段と、連続的に入力された入力データからなる入力データ列と一致する、スライド記憶手段に記憶されるデータ列を探索する探索手段と、探索手段で探索されたデータ列から１を選択して、選択されたデータ列の長さを求めてレングス値を生成するレングス生成手段と、レングス生成手段でレングス値を生成するために用いたデータ列における開始データの、スライド記憶手段内での位置を求めアドレス値を生成するアドレス値生成手段と、アドレス値の出現頻度に従い、アドレス値生成手段で生成されたアドレス値のうち、出現頻度が高いアドレス値から所定数のアドレス値を、予め定められた値以下の変換アドレス値に変換する変換手段と、レングス値と変換アドレス値とを符号化する符号化手段とを有することを特徴とする。
【００１６】
また、本発明は、スライド記憶手段が、入力データを順次記憶するスライド記憶ステップと、比較手段が、探索手段が、連続的に入力された入力データからなる入力データ列と一致する、スライド記憶手段に記憶されるデータ列を探索する探索ステップと、レングス生成手段が、探索ステップで探索されたデータ列から１を選択して、選択されたデータ列の長さを求めてレングス値を生成するレングス生成ステップと、アドレス値生成手段が、レングス生成ステップでレングス値を生成するために用いたデータ列における開始データの、スライド記憶手段内での位置を求めアドレス値を生成するアドレス値生成ステップと、変換手段が、アドレス値の出現頻度に従い、アドレス値生成ステップで生成されたアドレス値のうち、出現頻度が高いアドレス値から所定数のアドレス値を、予め定められた値以下の変換アドレス値に変換する変換ステップと符号化手段が、レングス値と変換アドレス値とを符号化する符号化ステップとを有することを特徴とする。
【発明の効果】
【００１７】
本発明によれば、特にマシン語のプログラムデータの圧縮符号化および復号処理を行うために用いて好適なデータ処理装置およびデータ処理方法が提供可能となる効果がある。
【図面の簡単な説明】
【００１８】
【図１】図１は、本発明に係るデータ処理装置を適用可能なプリンタ装置の一例の構成を示すブロック図である。
【図２】図２は、本発明の実施形態に適用可能なプリンタ装置の全体的な処理を示すフローチャートである。
【図３】図３は、エンコーダの一例の構成を示すブロック図である。
【図４】図４は、符号フォーマットの例を示す略線図である。
【図５】図５は、本実施形態に適用可能な符号化処理について説明するための略線図である。
【図６】図６は、スライド探索処理およびリスト探索処理におけるフラグ処理を説明するための略線図である。
【図７】図７は、スライド探索処理およびリスト探索処理におけるフラグ処理を説明するための略線図である。
【図８】図８は、マシン語のプログラムデータの特徴について説明するための略線図である。
【図９】図９は、マシン語のプログラムデータの特徴について説明するための略線図である。
【図１０】図１０は、変換テーブルETRANSTABLEの例を示す略線図である。
【図１１】図１１は、本発明の実施形態による符号化処理の全体的な流れを示す一例のフローチャートである。
【図１２】図１２は、スライド探索処理の例をより詳細に示すフローチャートである。
【図１３】図１３は、リスト探索処理の例をより詳細に示すフローチャートである。
【図１４】図１４は、スライド追加処理の例をより詳細に示すフローチャートである。
【図１５】図１５は、スライド符号化処理の例をより詳細に示すフローチャートである。
【図１６】図１６は、エンコーダの一例の構成をより詳細に示すブロック図である。
【図１７】図１７は、スライド／リスト生成処理部の一例のハードウェア構成を示すブロック図である。
【図１８】図１８は、デコーダの一例の構成を示すブロック図である。
【図１９】図１９は、逆変換テーブルDTRANSTABLEの一例を示す略線図である。
【図２０】図２０は、符号データを復号する一例の処理を示すフローチャートである。
【図２１】図２１は、デコーダの一例の構成をより詳細に示すブロック図である。
【図２２】図２２は、スライド展開部の一例のハードウェア構成を示すブロック図である。
【発明を実施するための形態】
【００１９】
以下に添付図面を参照して、この発明に係るデータ処理装置の一実施形態を詳細に説明する。図１は、本発明に係るデータ処理装置を適用可能なプリンタ装置の一例の構成を示す。図１の例では、プリンタ装置は、制御部２００、メインメモリ２１０、プリンタエンジン２１１および不揮発性のメモリであるフラッシュメモリ２４０を備える。フラッシュメモリ２４０は、図１に例示されるようにプリンタ装置に内蔵されていてもよいし、プリンタ装置に対して脱着可能とされていてもよい。
【００２０】
制御部２００は、ＣＰＵ(Central Processing Unit)２１２、ＣＰＵ Ｉ／Ｆ２０１、メモリコントローラ２０２、符号化部２０４、復号部２０５、画像処理部２０６、ディレイメモリ２０７、エンジンコントローラ２０８、パネルコントローラ２２０、パネル２２１、スキャナ２３０、平滑フィルタ２３１、フラッシュメモリコントローラ２４１、エンコーダ２４２およびデコーダ２４３を含む。
【００２１】
ＣＰＵ２１２は、メインメモリ２１０に格納されるプログラムに従い、このプリンタ装置の全体の動作を制御する。ＣＰＵ２１２は、ＣＰＵ Ｉ／Ｆ２０１を介してメモリコントローラ２０２に接続される。メモリコントローラ２０２は、ＣＰＵ２１２、符号化部２０４、復号部２０５、画像処理部２０６、通信Ｉ／Ｆ２０９、平滑フィルタ２３１、フラッシュメモリコントローラ２４１、エンコーダ２４２およびデコーダ２４３の、メインメモリ２１０に対するアクセスを調停する。
【００２２】
メインメモリ２１０は、メモリコントローラ２０２に接続される。メモリコントローラ２０２は、メインメモリ２１０に対するアクセスの制御を行う。
【００２３】
メインメモリ２１０は、プログラム領域２１０Ａおよびデータ領域２１０Ｂを有する。プログラム領域２１０Ａは、ＣＰＵ２１２が動作するためのプログラムが格納される。データ領域２１０Ｂは、例えばネットワークを介して供給ＰＤＬデータが格納されると共に、ＣＭＹＫバンドデータ、バンドデータが圧縮符号化された符号データ、ならびに、その他のデータが格納される。
【００２４】
符号化部２０４は、メインメモリ２１０に格納されるバンドデータを符号化する。符号化されたバンドデータは、メモリコントローラ２０２を介してメインメモリ２１０に供給される。復号部２０５は、後述するプリンタエンジン２１１に同期して、符号化部２０４で符号化されメインメモリ２１０に書き込まれた符号化バンドデータをメインメモリ２１０から読み出して復号する。復号されたバンドデータは、メモリコントローラ２０２を介して画像処理部２０６に供給される。画像処理部２０６は、復号部２０５から供給されたバンドデータに対して階調処理など所定の画像処理を施す。
【００２５】
画像処理が施されたバンドデータは、ディレイメモリ２０７を介してエンジンコントローラ２０８に転送される。ディレイメモリ２０７は、画像処理部２０６から出力されるバンドデータの転送速度と、エンジンコントローラ２０８からプリンタエンジン２１１に転送されるバンドデータの転送速度との違いを吸収する。
【００２６】
エンジンコントローラ２０８は、プリンタエンジン２１１を制御する。図１では、プリンタエンジン２１１としてＣＭＹＫ各色の版のうち１の版のものだけが記載され、その他の版については煩雑さを避けるために省略されている。
【００２７】
通信Ｉ／Ｆ２０９は、ネットワークを介しての通信を制御する。例えば、ネットワークに接続されるコンピュータから出力されたＰＤＬ(Page Description Language)データは、通信Ｉ／Ｆ２０９により受信される。通信Ｉ／Ｆ２０９は、受信したＰＤＬデータを、メモリコントローラ２０２を介してメインメモリ２１０に転送する。
【００２８】
なお、ネットワークは、ＬＡＮ(Local Area Network)などの所定の範囲内で通信を行うものでもよいし、インターネットなどより広範囲に通信可能なものでもよい。また、ネットワークは、有線通信に限らず無線通信を用いたものでもよいし、ＵＳＢ(Universal Serial Bus)やＩＥＥＥ(Institute Electrical and Electronics Engineers)１３９４といったシリアル通信を行うものでもよい。
【００２９】
フラッシュメモリ２４０は、ＣＰＵ２１２上で動作するためのプログラムや、当該プログラムに用いられる各種データが、本実施形態による圧縮符号化方法により圧縮符号化されて格納される。例えば、メインメモリ２１０のプログラム領域２１０Ａに対して、マシン語によるコードとして展開されるプログラムデータが、展開イメージのまま圧縮符号化され、スナップショットとしてフラッシュメモリ２４０に記憶される。フラッシュメモリコントローラ２４１は、フラッシュメモリ２４０に対するアクセスの制御を行う。
【００３０】
エンコーダ２４２は、本実施形態による、ＬＺ７７符号を用いた圧縮符号化方法により、プログラムデータの圧縮符号化を行う。また、デコーダ２４３は、当該圧縮符号化方法により圧縮符号化された圧縮データの復号を行う。
【００３１】
プリンタ装置の全体的な動作について、概略的に説明する。例えばコンピュータで生成されたＰＤＬデータがネットワークを介して通信Ｉ／Ｆ２０９に受信され、メインメモリ２１０のデータ領域２１０Ｂに記憶される。ＣＰＵ２１２は、メインメモリ２１０のデータ領域２１０ＢからＰＤＬデータを読み出し、ＰＤＬを解析して、解析結果に基づきＣＭＹＫのバンド画像を描画する。描画されたＣＭＹＫのバンド画像によるＣＭＹＫバンドデータは、メインメモリ２１０のデータ領域２１０Ｂに格納される。
【００３２】
符号化部２０４は、データ領域２１０ＢからＣＭＹＫバンドデータを読み出して、例えば予測符号化などを用いて符号化する。ＣＭＹＫバンドデータが符号化された符号データは、メインメモリ２１０のデータ領域２１０Ｂに格納される。
【００３３】
復号部２０５は、メインメモリ２１０のデータ領域２１０ＢからＣＭＹＫバンドデータが符号化された符号データを読み出して復号し、復号されたＣＭＹＫバンドデータをメモリコントローラ２０２を介して画像処理部２０６に供給する。画像処理部２０６は、復号部２０５から供給されたＣＭＹＫバンドデータに対して所定の画像処理を施す。画像処理されたＣＭＹＫバンドデータは、ディレイメモリ２０７およびプリンタエンジンコントローラ２０８を介してプリンタエンジン２１１に供給される。プリンタエンジン２１１は、供給されたＣＭＹＫバンドデータに基づきプリントアウトを行う。
【００３４】
図２は、本実施形態に適用可能なプリンタ装置の全体的な処理を示すフローチャートである。概略的には、例えばユーザがプリンタ装置の電源をＯＮとすると、電源立ち上げ処理が行われ（ステップＳ１）、プリンタ装置がＲＵＮ状態（稼働状態）になる（ステップＳ２）。ユーザの電源ＯＦＦ操作などにより、電源立ち下げ処理が行われ（ステップＳ３）、プリンタ装置がスリープ状態となる（ステップＳ４）。
【００３５】
ステップＳ１の電源立ち上げ処理では、フラッシュメモリ２４０に圧縮符号化されてスナップショットとして格納されたプログラムデータがフラッシュメモリ２４０から読み出され（ステップＳ１−１）、デコーダ２４３で本実施形態による復号方法に従い復号され、マシン語によるプログラムデータとされる（ステップＳ１−２）。このマシン語のプログラムデータは、メモリコントローラ２０２を介してメインメモリ２１０に供給され、プログラム領域２１０Ａに格納される（ステップＳ１−３）。
【００３６】
一方、ステップＳ３の電源立ち下げ処理では、メインメモリ２１０のプログラム領域２１０Ａに格納されるマシン語によるプログラムデータがメインメモリ２１０から読み出され（ステップＳ３−１）、エンコーダ２４２で本実施形態による符号化方法に従い圧縮符号化される（ステップＳ３−２）。圧縮符号化されたマシン語プログラムデータは、フラッシュメモリ２４０に対してスナップショットとして格納される（ステップＳ３−３）。
【００３７】
このように、電源立ち下げ処理時に、メインメモリ２１０のプログラム領域２１０Ａに格納されるマシン語のプログラムデータを、メモリ上のイメージのまま圧縮符号化し、スナップショットとしてフラッシュメモリ２４０に格納することで、電源立ち上げ処理を高速化することができる。
【００３８】
＜エンコーダ＞
図３は、エンコーダ２４２の一例の構成を示す。エンコーダ２４２において、データ読み込み部３００により、メインメモリ２１０のプログラム領域２１０Ａから、マシン語によるプログラムデータがメモリコントローラ２０２を介して読み出される。データ読み込み部３００に読み込まれたデータは、スライド／リスト生成処理部３０１に供給される。
【００３９】
スライド／リスト生成処理部３０１は、入力されたデータを順次記憶するＦＩＦＯ方式のスライド記憶部を有する。スライド／リスト生成処理部３０１は、供給されたデータとスライド記憶部に記憶された過去の入力データとを順次比較する。そして、供給されたデータと過去の入力データとが一致した場合には、当該過去の入力データのスライド記憶部内の位置を示すアドレス値Addressを保持すると共に、一致した長さを示す値であるレングスLengthをカウントアップする。両者が一致しない場合には、データ値そのものをPASS符号として符号化する。
【００４０】
ここで、本実施形態においては、詳細を後述する規則に従いアドレス値Addressを変換し、変換アドレス値TAddressとする。そして、これらPASS符号と、変換アドレス値TAddressおよびレングスLengthと、符号の種類を示すヘッダとを出力する。
【００４１】
スライド／リスト生成処理部３０１のから出力された各値は、符号フォーマット生成処理部３０２に供給される。符号フォーマット生成処理部３０２は、供給されたPASS符号、変換アドレス値TAddress、レングスLengthおよびヘッダとを、図４に例示されるようなフォーマットで符号化する。
【００４２】
図４において、PASS符号は、データ長が１ビットで値が「０」のヘッダに対して、後に８ビットのデータ長を持つデータ値が接続されてなる。スライド符号は、データ長が２ビットのヘッダに対して、レングスLengthおよびアドレス値Addressが順次接続される。レングスLengthは、符号長が８ビットとされる。
【００４３】
ここで、本実施形態においては、変換アドレス値TAddressは、自身の値に応じて２種類の符号長のうち何れか一方を選択されて符号化される。図４の例では、変換アドレス値TAddressは、符号長が８ビットの符号と、符号長が４ビットの符号とのうち何れかに符号化される。符号長が８ビットの符号に符号化された変換アドレス値TAddressを含むスライド符号を、第１スライド符号と呼び、ヘッダが「１０」とされる。また、符号長が４ビットの符号に符号化された変換アドレス値TAddressを含むスライド符号を、第２スライド符号と呼び、ヘッダが「１１」とされる。
【００４４】
なお、この図４に例示される符号フォーマットは、一例であって、これに限られるものではない。例えば、変換アドレス値TAddressの符号長は、第１および第２のスライド符号それぞれで８ビットまたは４ビットに限られない。
【００４５】
符号フォーマット生成処理部３０２で生成されたPASS符号、ならびに、第１および第２スライド符号は、符号書き込み部３０３に供給される。符号書き込み部３０３は、供給されたPASS符号、ならびに、第１および第２およびスライド符号を、メモリコントローラ２０２およびフラッシュメモリコントローラ２４１を介してフラッシュメモリ２４０に書き込む。
【００４６】
＜符号化処理の概略＞
次に、本実施形態に適用可能な、スライド／リスト生成処理部３０１における符号化処理について説明する。本実施形態では、ＬＺ７７符号を用い、スライド探索処理とリスト探索処理とを繰り返すことによって、データの符号化を行う。スライド探索処理は、１単位（例えば１バイト）の入力データと一致する、所定単位分の長さを持つスライド記憶部に記憶される過去の入力データを探索する。スライド記憶部内の過去の入力データに、入力データと一致するデータが探索されなかった場合には、入力データそのものをPASS符号として用いる。
【００４７】
スライド探索処理において、入力データに一致するスライド記憶部内の過去の入力データが探索された場合、その一致した過去の入力データをルートとして、リスト探索処理が行われる。リスト探索処理は、ルートとされた入力データに対して連続的に入力された入力データ列と一致する、スライド記憶部内の過去の入力データ列（リストと呼ぶ）を探索する。
【００４８】
リスト探索処理時に、入力データと一致するリストが無くなると、直前のリストから１を選び、選択されたリストのルートとなる過去の入力データのスライド記憶部内での位置をアドレス値Addressとし、当該リストの長さをレングスLengthとして出力する。
【００４９】
すなわち、スライド／リスト生成処理部３０１では、スライド探索処理でリスト探索処理のルートとなる過去の入力データを形成する。そして、リスト探索処理で、ルートに基づくリストの成長および淘汰を行い、最終的に残ったリストに基づき符号化を行う。
【００５０】
図５を用いてより具体的に説明する。図５の例では、スライド記憶部は、番号＃０〜＃１５で示されるように、直列に接続された１６個のレジスタを持ち、ＦＩＦＯ(First In First Out)として構成される。各レジスタは、それぞれ１単位（例えば１バイト）のデータを格納可能であるものとする。なお、以下では、このスライド記憶部が有するレジスタをスライドと呼ぶ。
【００５１】
処理＃１において、スライド記憶部の各スライドには、入力の新しい順、すなわち図５の右側から左側に向けて、「ａ，ｂ，ｃ，ａ，ａ，ｂ，ｃ，ａ，ｂ，ｃ，ｄ，ｂ，ｃ，ａ，ｃ，ａ」と、１６個の過去に入力されたデータが既に格納されているものとする。最初に、スライド／リスト生成処理部３０１に対して入力データ「ａ」が入力される。スライド探索処理により、この入力データ「ａ」と、各スライドに記憶された過去の入力データのそれぞれとを比較し、一致しているデータを探索する。図５の例では、番号＃０、＃３、＃４、＃７、＃１３および＃１５のスライドに格納されているデータが入力データと一致していることが分かる。したがって、これらの番号のスライドに格納されているデータが、リスト探索処理におけるルートとなる。
【００５２】
スライド探索処理によって、各スライドに記憶された過去の入力データから、入力データ「ａ」と一致しているデータが探索されたので、処理＃２のリスト探索処理が行われる。
【００５３】
処理＃２では、各スライドに記憶される過去の入力データを左に１だけシフトさせて、処理＃１で入力された入力データ「ａ」をスライド記憶部の番号＃０のスライドに追加する。それと共に、次の入力データ「ｃ」がスライド／リスト生成処理部３０１に対して入力される。リスト探索処理では、各スライドに記憶される過去の入力データのうち、直前の処理＃１において入力データが一致した各スライド内の過去の入力データが格納されていたスライドから、新たな入力データ「ｃ」と一致するデータを探索する。
【００５４】
図５の例では、処理＃１において入力データと一致した番号＃０および＃４のスライドに格納される過去の入力データは、処理＃２において入力データと一致していない。一方、処理＃１において入力データと一致した番号＃３、＃７、＃１３および＃１５のスライドに格納された過去の入力データは、データ「ｃ」であって、新たな入力データ「ｃ」と一致する。
【００５５】
処理＃２のリスト探索処理によって、直前の処理＃１において入力データが一致した各スライド内の過去の入力データが格納されたスライドから、処理＃２における入力データ「ｃ」と一致するデータが探索されたので、次の処理はリスト探索処理となる。なお、処理＃２は、リスト探索処理の開始点であるので、リストの長さを示すレングスLengthは、値「０」とされる。
【００５６】
処理＃３では、上述の処理＃２と同様にして、各スライドに記憶される過去の入力データを左に１だけシフトさせて、処理＃２で入力された入力データ「ｃ」をスライド記憶部の番号＃０のスライドに追加する。それと共に、次の入力データ「ｂ」がスライド／リスト生成処理部３０１に対して入力される。そして、各スライドに記憶される過去の入力データのうち、直前の処理＃２において入力データが一致した各スライド内の過去の入力データが格納されたスライドから、新たな入力データ「ｂ」と一致するデータを探索する。
【００５７】
図５の例では、処理＃２において探索された番号＃１５のスライドに格納される過去の入力データは、処理＃３において入力データと一致していない。一方、処理＃２において探索された番号＃３、＃７および＃１３のスライドに格納される、処理＃３における過去の入力データはデータ「ｂ」であって、新たな入力データ「ｂ」と一致する。次の処理＃４では、この番号＃３、＃７および＃１３のスライドに格納される過去の入力データが、リスト探索の対象となる。すなわち、この処理＃３の段階では、番号＃３、＃７および＃１３に係るリストが残っている。処理＃３では、リストの長さが「１」となり、レングスLengthが値「１」とされる。
【００５８】
このような処理を繰り返していき、リストが最も長くなるデータ列を求める。図５の例では、処理＃５において、直前の処理＃４においてリスト探索された番号＃１３のスライドに格納される過去の入力データ「ｃ」と、新たな入力データ「ｇ」とが一致しなくなり、リストが途切れる。そこで、処理＃５では、１つ前の処理＃４において残っているリストから１を選択し、そのスライドのスライド記憶部における位置（番号）をアドレス値Addressとし、リストの長さをレングスLengthとしてスライド符号に符号化する。図５の例では、アドレス値Addressが「１３」、レングスLengthが「３」とされる。
【００５９】
さらに、処理＃５では、入力データ「ｇ」についてスライド探索処理を行う。この例では、各スライドに過去の入力データとしてデータ「ｇ」が記憶されていないため、一致するデータがないとされる。この場合、処理は処理＃６に移行され、入力データ「ｇ」がそのまま用いられてPASS符号に符号化される。
【００６０】
PASS符号への符号化が行われると、処理＃７で、各スライドに記憶される過去の入力データが左に１だけシフトされると共に、直前のリスト探索処理（処理＃５）で入力された入力データ「ｇ」がスライド記憶部の番号＃０のスライドに追加される。そして、次の入力データ「b」に対してスライド探索処理が行われる。
【００６１】
ここで、スライド記憶部は、ＦＩＦＯ方式により各スライドに格納されたデータのシフトを行うことができるため、入力データとの一致を記憶したリストをそのままの状態で保持しながら、次の入力データの処理に移行することができる。
【００６２】
例えば、図５の例では、入力データが、処理＃１において番号＃０、＃３、＃４、＃７、＃１３および＃１５のスライドに格納される過去の入力データと一致している。各スライドに格納されたデータを、新たなデータの入力に伴い順次シフトさせることで、例えば処理＃２の当該番号＃０、＃３、＃４、＃７、＃１３および＃１５のスライドに対して次のデータが格納されることになる。したがって、スライド記憶部において、スライド探索処理で一致が探索された番号のスライドに格納されるデータを、リスト探索処理毎に入力データと比較していくことで、入力データのデータ列と一致する、過去の入力データのデータ列を探索することができる。
【００６３】
このように、スライド記憶部をＦＩＦＯ方式とすることで、リスト探索処理を簡易に行うことができる。
【００６４】
なお、上述の処理によれば、リスト探索処理において入力データと一致するリストが無く、処理がリスト探索処理からスライド探索処理に移行する際に、１処理分、符号化が進行しない時間が生じることになる。すなわち、１処理を１クロックで行うとした場合、リスト探索処理からスライド探索処理に移行する際に、１クロック分の無駄が生じてしまうことになる。
【００６５】
＜フラグ処理＞
上述したスライド探索処理およびリスト探索処理は、フラグによって制御される。このスライド探索処理およびリスト探索処理におけるフラグ処理について、図６および図７を用いて説明する。
【００６６】
図６は、スライド探索処理の結果を示すＲフラグRFLGmを示す。図６に例示されるように、スライド記憶部の各スライドに対して、図の右側から左側へ向けて「ａ，ｂ，ｃ，ａ，ａ，ｂ，ｃ，ａ，ｂ，ｃ，ｄ，ｂ，ｃ，ａ，ｃ，ａ」のように過去の入力データが格納された状態で、入力データ「ａ」が入力された場合、番号＃０、＃３、＃４、＃７、＃１３および＃１５のスライドで、入力データと各スライドに記憶される過去の入力データとが一致する。そこで、これらの番号のスライドに対応するＲフラグRFLG0、RFLG3、RFLG4、RFLG7、RFLG13およびRFLG15を、それぞれ一致したことを示す値「１」とする。
【００６７】
このように、入力データと、各スライドに記憶される過去の入力データとが一致する場合は、符号化処理を行わずにリスト探索処理が行われる。このとき、ＲフラグRFLGmの各スライドに対する位置は、固定的である。入力データと一致する、各スライドに記憶される過去の入力データが無い場合は、入力データをそのまま用いてPASS符号に符号化し、次の入力データに対してスライド探索処理を行う。
【００６８】
図７は、リスト探索処理の結果を示すＷフラグWFLGmの例を示す。リスト探索処理では、新たに入力された入力データと一致するデータが、各スライドのうちＲフラグRFLGmが「１」とされたスライドに格納されるデータから探索される。若し、一致するデータが探索されたら、当該スライドに対するＷフラグWFLGmの値を、一致したことを示す値「１」とする。
【００６９】
図７の例では、各スライドに記憶される過去の入力データのうち、ＲフラグRFLGmが値「１」である番号＃０、＃３、＃４、＃７、＃１３および＃１５のスライドに格納されるデータに対してリスト探索処理が行われる。これらのうち、入力データ「ｃ」に対して、番号＃３、＃７、＃１３および＃１５のスライドに格納されるデータが一致するので、対応するＷフラグWFLG3、WFLG7、WFLG13およびWFLG15の値を、一致したことを示す値「１」とする。各スライドに記憶される過去の入力データのうち、このＷフラグWFLGmの値が「１」とされたスライドに格納されるデータは、直前に入力データと一致したスライドに格納される過去の入力データと、現在入力データと一致した過去の入力データとが連なっていることを示す。
【００７０】
次に、値が「１」のＷフラグWFLGmを探索する。この値「１」のＷフラグWFLGmが存在する場合は、各ＷフラグWFLGmを新たなＲフラグRFLGmとし、上述と同様にして次の入力データに対してリスト探索処理を行う。
【００７１】
一方、探索の結果、値が「１」のＷフラグWFLGmが存在しないとされた場合は、リストが途絶えたことを意味する。この場合は、値が「１」のＲフラグRFLGmを１つ選択し、選択したＲフラグRFLGmに対応するスライドのアドレス値Addressと、そのときのレングスLengthとをスライド符号に符号化する。
【００７２】
ここで、図８および図９を用いて、マシン語のプログラムデータの特徴について、概略的に説明する。図８は、ＲＩＳＣ(Reduced Instruction Set Computer)技術によるＣＰＵに対するマシン語プログラムにおける命令フォーマットの例を示す。図８（ａ）は、Ｒ（レジスタ）タイプ命令の例、図８（ｂ）は、Ｉ（イミディエイト）タイプ命令の例、図８（ｃ）は、Ｊ（ジャンプ）タイプ命令の例をそれぞれ示す。各命令は、３２ビットを所定に分割した領域に所定のニーモニックが格納される。各ニーモニックの意味を、図８（ｄ）に示す。
【００７３】
各ニーモニックのうち、オペレーションコードを示すニーモニック「Ｏｐ」は、Ｒタイプ、ＩタイプおよびＪタイプそれぞれの命令において、固定的に先頭の６ビットの領域に格納される。このように、ＲＩＳＣにおいては、データ長が３２ビットの固定フォーマットで決められた所定領域に対して、同じ意味のコードが格納されるため、スライドが４バイト（３２ビット）毎または８バイト毎に一致する可能性が高くなる。
【００７４】
図９は、マシン語のプログラムデータにおけるスライドの一致位置に関する統計結果の例を示す。図９において、横軸がスライドの一致位置（アドレス値Address）を示し、縦軸が一致回数（出現頻度）を示す。図９に示される統計結果によれば、４バイト毎に一致回数の大きなピークが現れることが示されている。また、４バイト毎のピークを除外して全体的な変化を見ると、一致位置がより近いほどスライドの一致する確率が高くなることが分かる。一方、スライドの一致位置がある程度離れると、低い一致確率に収束することが分かる。
【００７５】
本実施形態では、上述したような、マシン語のプログラムデータにおいて、４バイト毎にスライドの一致確率のピークが現れることを利用して、スライド符号の符号化を行う。
【００７６】
具体的には、スライド符号のアドレス値Addressを、対応するスライドの一致回数が多い順に並べ替えて、並べ替え後の順序を示す値からなる変換アドレス値TAddressを生成する。そして、４ビットで表現可能な所定数の変換アドレス値TAddress、すなわち値が「０」〜「１５」までの変換アドレス値TAddressを、符号長が４ビットの符号に符号化する。この符号長が４ビットの符号に符号化された変換アドレス値TAddressにより、第２スライド符号が形成される。一方、値が「１５」〜「２５５」の変換アドレス値TAddressは、符号長が８ビットの符号に符号化する。この符号長が８ビットの符号に符号化された変換アドレス値TAddressにより、第１スライド符号が形成される。
【００７７】
アドレス値Addressを変換アドレス値TAddressに変換するためには、例えば図１０に例示されるような変換テーブルETRANSTABLEを用いることができる。この変換テーブルETRANSTABLEに列挙される数値は、変換後の変換アドレス値TAddressを示す。また、変換テーブルETRANSTABLEに列挙される数値の順番を示す値（「０」から始まるものとする）が変換前のアドレス値Addressを示す。すなわち、変換テーブルETRANSTABLEに対してアドレス値Addressを入力すると、入力されたアドレス値Addressに対応する位置の値が変換アドレス値TAddressとして出力される。
【００７８】
変換テーブルETRANSTABLEは、図１０から分かるように、４個のアドレス値Address毎に小さい値の変換アドレス値TAddressを割り当てている。換言すれば、図９の統計結果に従い、バイト単位でプログラムデータの４バイト毎に小さい値の変換アドレス値TAddressを割り当てる。また、図９の統計結果によれば、スライドの一致位置がある程度離れると一致回数が少ない値に収束するので、変換テーブルETRANSTABLEの後方に行くに従い、最後尾の値（すなわちアドレス値Address「２５５」）を除き、この変換アドレス値TAddressの規則性を弱めている。
【００７９】
さらに、変換テーブルETRANSTABLEの先頭部分において、アドレス値Address「０」に対して変換アドレス値TAddress「１５」を割り当てている。これは、図９を用いて説明したように、統計結果の全体的な特性として、スライドの一致位置が近いほど一致回数も大きい傾向にあることから来ている。
【００８０】
具体的には、変換テーブルETRANSTABLEにおいて、変換前のアドレス値Address「３」は、変換アドレス値TAddress「０」に変換される。また、変換前のアドレス値Address「０」は、変換アドレス値TAddress「１５」に変換される。同様に、変換前のアドレス値Address「１１」は、変換アドレス値TAddress「２」に変換される。
【００８１】
なお、上述したように、値が「０」〜「１５」までの変換アドレス値TAddressは、全て符号長が４ビットの符号に変換される。そのため、実際には、変換テーブルETRANSTABLEにおいて変換アドレス値TAddress「０」〜「１５」に対応付けるアドレス値Addressの順番は、変更することができる。同様に、変換アドレス値TAddress「１６」〜「２５５」に対応付けるアドレス値Addressの順番も変更できる。
【００８２】
ここでは、変換テーブルETRANSTABLEが、変換アドレス値TAddressが列挙され、変換アドレス値TAddressの順番が元のアドレス値Addressを示すように説明したが、これはこの例に限定されない。例えば、変換前のアドレス値Addressと、変換後の変換アドレス値TAddressとを１対１に対応付けたテーブルとしてもよい。
【００８３】
また、ここでは、小さい値の変換アドレス値TAddressを４バイト毎に割り当てているが、これはこの例に限定されない。すなわち、小さい値の変換アドレス値TAddressの割り当て単位は、プログラムデータの命令フォーマットに応じて設定することができる。例えば、命令フォーマットが６４ビットのデータ長で構成されていれば、小さい値の変換アドレス値TAddressを８バイト毎に割り当てることが考えられる。
【００８４】
＜符号化処理の詳細＞
次に、スライド／リスト生成処理部３０１における符号化処理について、より詳細に説明する。図１１は、本実施形態による符号化処理の全体的な流れを示す一例のフローチャートである。なお、図１１のフローチャートの処理に先立って、符号読み込み部３００は、ある長さのデータを処理対象のデータとして予め保持しているものとする。
【００８５】
最初のステップＳ１０で、スライド／リスト生成処理部３０１は、スライド探索処理およびリスト探索処理のうち何れが有効かを示すフラグListFLGを、スライド探索処理を行っていることを示す値「０」に初期化する。次に、ステップＳ１１で、スライド／リスト生成処理部３０１は、符号読み込み部３００から１単位分のデータを入力データとして読み込む。読み込んだ入力データは、スライド記憶部に格納される。
【００８６】
入力データがスライド記憶部に格納されると、ステップＳ１２で、１単位分のデータに対するスライド探索処理が行われると共に、ステップＳ１３で、１単位分のデータに対するリスト探索処理が行われる。詳細は後述するが、本実施形態においては、スライド探索処理を行うスライド探索部と、リスト探索処理を行うリスト探索部とが別個の構成とされているので、ステップＳ１２およびステップＳ１３の処理を並列的に行うことが可能である。
【００８７】
処理はステップＳ１４に移行され、スライド／リスト生成処理部３０１は、フラグListFLGの値が「０」か否かを判定する。若し、「０」であると判定されたら、現在スライド探索処理が有効であるとされ、処理はステップＳ１５に移行される。ステップＳ１５では、フラグSFINDFLGの値が「１」であるか否かが判定される。若し、値が「１」であれば、スライド記憶部１０１において入力データと一致する過去の入力データが探索されたとされ、ステップＳ１６でフラグListFLGの値がリスト探索処理が有効であることを示す「１」とされる。
【００８８】
そして、処理がステップＳ２５に移行され、スライド記憶部に対して入力データが追加される。次のステップＳ２６で、処理対象のデータ全てに対する処理が終了したか否かが判定される。若し、終了していないと判定されたら、処理はステップＳ１１に戻され、次の１単位分のデータが入力データとして読み込まれる。一方、終了していると判定されたら、一連の符号化処理が終了される。
【００８９】
一方、ステップＳ１５で、フラグSFINDFLGの値が「０」であると判定されたら、スライド記憶部１０１において入力データと一致する過去の入力データが探索されなかったとされ、処理はステップＳ１７に移行される。ステップＳ１７では、フラグListFLGの値が「０」とされてスライド探索処理が有効であるとされ、次のステップＳ１８で入力データがPASS符号に符号化される。また、一致フラグFLAGが値「０」とされる。そして、処理はステップＳ２５に移行される。
【００９０】
また、上述のステップＳ１４において、フラグListFLGの値が「０」ではない、すなわち「１」であると判定されたら、現在リスト探索処理が有効であるとされ、処理がステップＳ１９に移行される。ステップＳ１９では、フラグLFINDFLGの値が「１」か否かを判定する。若し、「１」であると判定されたら、処理はステップＳ２５に移行される。
【００９１】
一方、ステップＳ１９で、フラグLFINDFLGの値が「１」ではない、すなわち、フラグLFINDFLGの値が「０」であると判定されたら、処理はステップＳ２０に移行される。ステップＳ２０では、アドレス値Addressが変換テーブルETRANSTABLEに従い変換アドレス値TAddressに変換され、この変換アドレス値TAddressと、レングスLengthおよびヘッダとが、図４に例示される第１または第２スライド符号に符号化される。そして、処理はステップＳ２１に移行され、フラグSFINDFLGの値が「１」であるか否かが判定される。若し、「１」であると判定されたら、リスト探索処理においてリストが継続されたとされて処理がステップＳ２２に移行され、フラグListFLGの値が「１」とされる。そして、処理がステップＳ２５に移行される。
【００９２】
一方、ステップＳ２０でフラグSFINDFLGの値が「０」であると判定されたら、リスト探索処理においてリストが途切れたとされ、処理がステップＳ２３に移行され、フラグListFLGの値が「０」とされる。次のステップＳ２４で入力データがそのままPASS符号に符号化され、レジスタ１４１に格納される。そして、処理はステップＳ２５に移行される。
【００９３】
図１２は、図１１のステップＳ１２における一例のスライド探索処理をより詳細に示すフローチャートである。なお、この図１２、ならびに、以下の図１３および図１４では、スライド記憶部におけるスライドを、スライドの番号を含めるように、スライド[x]のように表す。また、ＦＩＦＯ構成とされるスライド記憶部において先頭のスライドを、スライド[0]とする。
【００９４】
先ず、ステップＳ３０〜ステップＳ３２で、レングスLength、フラグSFINDFLGおよび変数IWがそれぞれ値「０」に初期化される。処理はステップＳ３３に移行され、入力データとスライド[IW]に格納された過去の入力データとが一致するか否かが判定される。若し、一致すると判定されたら、処理はステップＳ３４に移行され、フラグSFINDFLGの値が「１」とされ、次のステップＳ３５で、ＲフラグRFLG[IW]の値が「１」とされる。
【００９５】
そして、処理はステップＳ３７に移行され、変数IWがスライドサイズ未満、すなわち、スライド記憶部が有するスライド数未満であるか否かが判定される。若し、変数IWがスライドサイズ未満であると判定されたら、ステップＳ３８で変数IWに「１」が加えられ、処理がステップＳ３３に戻される。一方、ステップＳ３７で、変数IWがスライドサイズ以上であると判定されたら、一連の処理が終了される。
【００９６】
一方、ステップＳ３３で入力データとスライド[IW]に格納された過去の入力データとが一致しないと判定されたら、処理はステップＳ３６に移行され、ＲフラグRFLG[IW]の値が「０」とされる。そして、処理がステップＳ３７に移行される。
【００９７】
図１３は、図１１のステップＳ１３による一例のリスト探索処理をより詳細に示すフローチャートである。先ず、ステップＳ４０およびステップＳ４１で、フラグLFINDFLGおよび変数IWがそれぞれ値「０」に初期化される。
【００９８】
ステップＳ４２で、入力データとスライド[IW]に格納された過去の入力データとが一致し、且つ、ＲフラグRFLG[IW]の値が「１」であるか否かが判定される。若し、それぞれの条件を満たすと判定されたら、処理はステップＳ４３に移行され、ＷフラグWFLG[IW]の値が「１」とされ、次のステップＳ４４で、フラグLFINDFLGの値が「１」とされる。そして、処理がステップＳ４６に移行される。
【００９９】
一方、ステップＳ４２で、上述の条件を満たさない、すなわち、入力データとスライド[IW]に格納された過去の入力データとが一致しない、または、ＲフラグRFLG[IW]の値が「１」でないと判定されたら、処理はステップＳ４５に移行され、ＷフラグWFLG[IW]の値が「０」とされる。そして、処理がステップＳ４６に移行される。
【０１００】
ステップＳ４６では、変数IWがスライドサイズ未満であるか否かが判定される。若し、変数IWがスライドサイズ未満であると判定されたら、ステップＳ４７で変数IWに「１」が加えられ、処理がステップＳ４２に戻される。一方、変数IWがスライドサイズ以上であると判定されたら、処理がステップＳ４８に移行される。
【０１０１】
ステップＳ４８では、フラグLFINDFLGの値が「０」であるか否かが判定される。若し、値が「０」であると判定されたら、処理がステップＳ４９に移行されて変数IWが値「０」に初期化され、次のステップＳ５０でＲフラグRFLG[IW]の値が「１」であるか否かが判定される。若し、「１」であると判定されたら、処理はステップＳ５１に移行される。
【０１０２】
ステップＳ５１では、変数IWがアドレス値Addressとされ、次のステップＳ５２で、スライドサイズを変数IWに代入する。そして、処理がステップＳ５３に移行される。ステップＳ５３では、変数IWがスライドサイズ未満であるか否かが判定される。若し、変数IWがスライドサイズ未満であると判定されたら、ステップＳ５４で変数IWに「１」が加算されて処理がステップＳ５０に戻される。
【０１０３】
一方、ステップＳ５３で、変数IWがスライドサイズ以上であると判定されたら、一連の処理が終了される。例えば、上述したステップＳ５２を経由してこのステップＳ５３に到達した場合、ステップＳ５２で変数IWにスライドサイズが代入されているため、必ず処理が終了される。
【０１０４】
上述したステップＳ４８で、フラグLFINDFLGの値が「０」ではないと判定されたら、処理はステップＳ５５に移行され、変数IWが値「０」に初期化される。次のステップＳ５６で、ＲフラグRFLG[IW]に対してＷフラグWFLG[IW]が設定される。そして、ステップＳ５７で、変数IWがスライドサイズ未満であるか否かが判定される。若し、変数IWがスライドサイズ未満であると判定されたら、ステップＳ５８で変数IWに「１」が加算されて処理がステップＳ５６に戻される。一方、ステップＳ５７で変数IWがスライドサイズ以上であると判定されたら、処理は次のステップＳ５９に移行され、レングスLengthに対して１が加算され、一連の処理が終了される。
【０１０５】
図１４は、図１１のステップＳ２５による一例のスライド追加処理をより詳細に示す一例のフローチャートである。先ず、ステップＳ７０で、変数IWがスライド数から１を減じた値に設定される。次のステップＳ７１で、スライド[IW]に、スライド[IW−１]の値が格納され、ステップＳ７２で、変数IWが「０」を超えるか否かが判定される。若し、変数IWが「０」を超えると判定されたら、処理はステップＳ７３に移行され、変数IWから「１」が減じられる。そして、処理がステップＳ７１に戻される。一方、ステップＳ７２で、変数IWが「０」以下であると判定されたら、処理はステップＳ７４に移行され、スライド[0]に対して入力データが格納される。
【０１０６】
図１５は、図１１のステップＳ２０による一例のスライド符号化処理をより詳細に示す。符号フォーマットは、図４に示したフォーマットに従うものとする。先ず、ステップＳ８０で、アドレス値Addressが変換テーブルETRANSTABLEにより変換アドレス値TAddressに変換される。次に、ステップＳ８１で、変換アドレス値TAddressの値が「１６」未満であるか否かが判定される。なお、変換アドレス値TAddressは、値「０」から開始されるものとする。
【０１０７】
若し、変換アドレス値TAddressが値「１６」未満であると判定されたら、処理はステップＳ８２に移行され、ヘッダの符号化が行われる。この例では、ヘッダは、符号長が２ビット、値「１０」の符号に符号化される。ヘッダの符号化が行われると、次のステップＳ８３で、一致長さすなわちレングスLengthの符号化が行われる。この例では、レングスLengthは、符号長が８ビットの符号に符号化される。そして、次のステップＳ８４で、一致位置すなわち変換アドレス値TAddressの符号化がなされる。変換アドレス値TAddressが値「１６」未満であるので、符号長が４ビットの符号に符号化される。
【０１０８】
一方、変換アドレス値TAddressが値「１６」以上であると判定されたら、処理はステップＳ８５に移行され、ヘッダの符号化が行われる。この例では、ヘッダは、符号長が２ビット、値「１１」の符号に符号化される。ヘッダの符号化が行われると、次のステップＳ８６で、一致長さすなわちレングスLengthの符号化が行われる。この例では、レングスLengthは、符号長が８ビットの符号に符号化される。そして、次のステップＳ８７で、一致位置すなわち変換アドレス値TAddressの符号化がなされる。変換アドレス値TAddressが値「１６」以上であるので、符号長が８ビットの符号に符号化される。
【０１０９】
図１６は、エンコーダ２４２の一例の構成をより詳細に示す。なお、図１６において、上述の図３と共通する部分には同一の符号を付し、詳細な説明を省略する。エンコーダ２４２は、データ読み込み部３００、スライド／リスト生成処理部３０１、符号フォーマット生成処理部３０２および符号書き込み部３０３を有すると共に、メモリコントローラＩ／Ｆ３１０、データアドレス生成部３１１および符号アドレス生成部３１２を有する。
【０１１０】
データアドレス生成部３１１は、メインメモリ２１０のプログラム領域２１０Ａからプログラムデータを読み出す際のメモリアドレスを生成する。データ読み込み部３００は、データアドレス生成部３１１で生成されたメモリアドレスからのデータの読み出しを、メモリコントローラＩ／Ｆ３１０を介してメモリコントローラ２０２に対して要求する。この要求に応じてメモリコントローラ２０２によりメインメモリ２１０のプログラム領域２１０Ａから読み出されたプログラムデータがメモリコントローラ２０２からエンコーダ２４２に対して供給され、メモリコントローラＩ／Ｆ３１０を介してデータ読み込み部３００に供給される。データ読み込み部３００は、供給されたプログラムデータを、スライド／リスト生成処理部３０１に供給する。
【０１１１】
スライド／リスト生成処理部３０１は、供給されたプログラムデータから、既に説明したようにしてアドレス値Address、レングスLength、PASS符号およびヘッダを生成する。ここで、アドレス値Addressは、変換テーブルETRANSTABLEにより変換アドレス値TAddressに変換される。これら変換アドレス値TAddress、レングスLength、PASS符号（データ値）およびヘッダは、符号フォーマット生成処理部３０２に供給される。符号フォーマット生成処理部３０２は、図４で説明した符号フォーマットに従い、供給された各値からPASS符号、第１スライド符号および第２スライド符号を生成する。生成されたPASS符号、第１スライド符号および第２スライド符号は、符号書き込み部３０３に供給される。
【０１１２】
符号書き込み部３０３は、供給されたPASS符号、第１スライド符号および第２スライド符号をメモリコントローラＩ／Ｆ３１０を介してメモリコントローラ２０２に供給する。それと共に、符号書き込み部３０３は、これらの符号を符号アドレス生成部３１２で生成されたメモリアドレスに従いフラッシュメモリ２４０に書き込むように、メモリコントローラＩ／Ｆ３１０を介してメモリコントローラ２０２に要求する。メモリコントローラ２０２は、この要求に従い、供給された符号を、フラッシュメモリコントローラ２４１を介してフラッシュメモリ２４０に書き込む。
【０１１３】
＜スライド／リスト生成処理部のハードウェア構成例＞
図１７は、上述したスライド探索処理、リスト探索処理および符号化処理を実行するスライド／リスト生成処理部３０１の、一例のハードウェア構成を示す。スライド／リスト生成処理部３０１は、スライド探索部１００、スライド記憶部１０１、リスト探索部１０２およびコントローラ１０３を有する。
【０１１４】
コントローラ１０３は、例えばマイクロプロセッサからなり、図１１のフローチャートを用いて説明した、ステップＳ１２およびステップＳ１３の処理を除いた、ステップＳ１１〜ステップＳ２６による処理を行い、スライド／リスト生成処理部３０１の動作を制御する。例えば、コントローラ１０３は、上述した現在スライド探索処理およびリスト探索処理のうち何れが有効かを示すフラグListFLGによる動作制御を行う。
【０１１５】
スライド／リスト生成処理部３０１に対して、例えば１クロック毎に１単位の入力データが入力され、スライド探索部１００、スライド記憶部１０１およびリスト探索部１０２にそれぞれ供給される。入力データは、さらに、出力側のレジスタ１４１にも格納される。レジスタ１４１に格納される入力データは、PASS符号の符号化の際のデータ値として用いられる。以下では、データの１単位を１バイトとする。
【０１１６】
スライド記憶部１０１は、各々がレジスタからなり、それぞれ１単位のデータが格納されるｎ個（例えば２５６個）のスライド１２０1、１２０2、…、１２０nが直列に接続されて構成される。また、各スライド１２０1、１２０2、…、１２０nの出力は、次のレジスタに供給されると共に、後述するスライド探索部１００の対応する比較器１１１mの一方の入力端と、リスト探索部１０２の対応する比較器１３０mの一方の入力端にそれぞれ供給される。
【０１１７】
なお、比較器１３０mは、比較器１３０1〜１３０nのうち任意の比較器を表す。このような表記は、比較器１１１1〜１１１n、セレクタ１３１1〜１３１n、レジスタ１３２1〜１３２nにおいて共通とする。
【０１１８】
なお、アドレス値AddressおよびレングスLengthのデータ長は、スライド記憶部１０１が有するスライド数ｎに応じて決められる。すなわち、スライド数ｎ＝２５６であれば、アドレス値AddressおよびレングスLengthが「２５６」までの値を表現可能に、それぞれのデータ長が８ビットに決められる。
【０１１９】
スライド記憶部１０１は、これらｎ個のスライド１２０1、１２０2、…、１２０nによりＦＩＦＯが構成され、入力されたデータがスライド１２０1からスライド１２０2、スライド１２０3、…と１クロック毎に順次送られていく。
【０１２０】
スライド探索部１００は、ｎ個の比較器１１１1、１１１2、…、１１１nと、ｎ入力の論理和回路１１０とを有する。比較器１１１1、１１１2、…、１１１nのそれぞれは、一方および他方の入力端に入力されたデータを比較し、両者が一致していれば値「１」を出力し、一致していなければ値「０」を出力する。
【０１２１】
比較器１１１1、１１１2、…、１１１nの一方の入力端には、上述したように、スライド記憶部１０１が有するスライド１２０1、１２０2、…、１２０nの出力がそれぞれ入力される。また、比較器１１１1、１１１2、…、１１１nそれぞれの他方の入力端には、入力データが入力される。
【０１２２】
比較器１１１1、１１１2、…、１１１nそれぞれの出力は、ｎ入力の論理和回路１１０に入力されると共に、後述するリスト探索部１０２のセレクタ（ＳＥＬ）１３１1、１３１2、…、１３１nの一方の入力端にそれぞれ入力される。論理和回路１１０の出力は、フラグSFINDFLGとしてコントローラ１０３に供給される。このフラグSFINDFLGは、スライド１２０1、１２０2、…、１２０nのデータのうち少なくとも１が入力データと一致しているか否かを示す。
【０１２３】
リスト探索部１０２は、それぞれｎ個の比較器１３０1、１３０2、…、１３０n、セレクタ１３１1、１３１2、…、１３１n、ならびに、レジスタ１３２1、１３２2、…、１３２nと、アドレス値生成部１３３と、ｎ入力の論理和回路１３４とを有する。比較器１３０1、１３０2、…、１３０nのそれぞれは、一方および他方の入力端に入力されたデータを比較し、両者が一致していれば値「１」を出力し、一致していなければ値「０」を出力する。
【０１２４】
比較器１３０1、１３０2、…、１３０nの一方の入力端には、上述したように、スライド記憶部１０１が有するスライド１２０1、１２０2、…、１２０nの出力がそれぞれ入力される。また、比較器１３０1、１３０2、…、１３０nそれぞれの他方の入力端には、入力データが入力される。
【０１２５】
比較器１３０1、１３０2、…、１３０nの出力は、ＷフラグWFLGmであって、ｎ入力の論理和回路１３４にそれぞれ入力されると共に、セレクタ１３１1、１３１2、…、１３１nの他方の入力端にそれぞれ入力される。論理和回路１３４の出力は、フラグLFINDFLGとしてコントローラ１０３に供給される。フラグLFINDFLGは、ＷフラグWFLG1、WFLG2、…、WFLGnのうち少なくとも１の値が「１」であることを示す。
【０１２６】
セレクタ１３１1、１３１2、…、１３１nの出力は、ＲフラグRFLGmとされて、それぞれレジスタ１３２1、１３２2、…、１３２nに格納される。セレクタ１３１1、１３１2、…、１３１nは、コントローラ１０３から図示しない経路を経て供給されるフラグListFLGにより、一方および他方の端子のうち何れを選択するかが制御される。
【０１２７】
若し、フラグListFLGの値が「０」であって、現在スライド探索処理が有効であることが示されていれば、セレクタ１３１1、１３１2、…、１３１nは、それぞれの一方の入力端に入力された、スライド探索部１００における比較器１１１1、１１１2、…、１１１nの出力をレジスタ１３２1、１３２2、…、１３２nに供給するように制御される。例えば、セレクタ１３１m（なお、１≦ｍ≦ｎとする）は、対応するレジスタ１３２mに格納される値が「０」のときに入力端が選択されるように制御される。
【０１２８】
一方、フラグListFLGの値が「１」であって、現在リスト探索処理が有効であることが示されていれば、セレクタ１３１1、１３１2、…、１３１nは、それぞれの他方の入力端に入力された、リスト探索部１０２における比較器１３０1、１３０2、…、１３０nを選択してレジスタ１３２1、１３２2、…、１３２nに供給するように制御される。例えば、セレクタ１３１mは、対応するレジスタ１３２mに格納される値が「１」のときに他方の入力端が選択されるように制御される。
【０１２９】
レジスタ１３２1、１３２2、…、１３２nは、セレクタ１３１1、１３１2、…、１３１nからの出力が供給されると、格納されているＲフラグRFLG1、RFLG2、…、RFLGnを出力する。すなわち、レジスタ１３２1、１３２2、…、１３２nに格納されるＲフラグRFLG1、RFLG2、…、RFLGnは、供給されたセレクタ１３１1、１３１2、…、１３１nからの出力により更新される。
【０１３０】
レジスタ１３２1、１３２2、…、１３２nから出力されたＲフラグRFLG1、RFLG2、…、RFLGnは、比較器１３０1、１３０2、…、１３０nの動作を制御する制御信号として、比較器１３０1、１３０2、…、１３０nの制御端にそれぞれ供給される。例えば、例えば比較器１３０mは、対応するレジスタ１３２mから供給された制御信号が値「１」を示していれば比較動作を行い、値「０」を示していれば比較動作を行わない。これは、比較器１３０1、１３０2、…、１３０nそれぞれの動作は、比較器１３０1、１３０2、…、１３０n自身の出力により絞り込まれていくことを意味する。
【０１３１】
レジスタ１３２1、１３２2、…、１３２nから出力されたＲフラグRFLG1、RFLG2、…、RFLGnは、さらにアドレス値生成部１３３にも供給される。アドレス値生成部１３３は、図４の処理＃５で説明したように、リスト探索処理が終了した際に、レジスタ１３２1、１３２2、…、１３２nから供給されるＲフラグRFLG1、RFLG2、…、RFLGnのうち、値が「１」であるＲフラグRFLGmを選択し、選択されたＲフラグRFLGmの番号をアドレス値Addressとして出力する。アドレス値生成部１３３から出力されたアドレス値Addressは、アドレス変換部１４４に供給される。
【０１３２】
アドレス変換部１４４は、図１０を用いて説明した変換テーブルETRANSTABLEを持ち、供給されたアドレス値Addressを、変換テーブルETRANSTABLEに従い変換アドレス値TAddressに変換する。アドレス値Addressが変換された変換アドレス値TAddressは、レジスタ１４０に格納されると共に、コントローラ１０３に供給される。
【０１３３】
コントローラ１０３は、スライド探索部１００から供給されたフラグSFINDFLGと、リスト探索部１０２から供給されたフラグLFINDFLGと、アドレス変換部１４４から供給された変換アドレス値TAddress値とに基づき、レングスLengthおよびヘッダを生成する。レングスLengthおよび一致フラグFLAGは、それぞれレジスタ１４３および１４２に格納される。
【０１３４】
なお、レジスタ１４０〜１４３にそれぞれ格納された変換アドレス値TAddress、データ値、ヘッダおよびレングスLengthは、それぞれ符号フォーマット生成処理部３０２に読み出され、図４に例示する符号フォーマットに従い符号化され符号データが生成される。
【０１３５】
このような構成において、スライド探索処理は、以下のように行われる。すなわち、比較器１１１1、１１１2、…、１１１nによる、入力データと、スライド１２０1、１２０2、…、１２０nに格納された過去の入力データとの比較処理が行われる。比較結果がそれぞれ論理和回路１１０に供給され、フラグSFINDFLGが出力される。比較結果は、セレクタ１３１1、１３１2、…、１３１nにも供給され、スライド探索処理の間は、レジスタ１３２1、１３２2、…、１３２nに格納される。図１７の構成によれば、この一連の処理を１クロックで実行可能である。
【０１３６】
また、リスト探索処理は、以下のように行われる。すなわち、比較器１３０1、１３０2、…、１３０nによる、入力データと、スライド１２０1、１２０2、…、１２０nに格納された過去の入力データとの比較処理が行われる。このとき、レジスタ１３２1、１３２2、…、１３２nに格納されるＲフラグRFLG1、RFLG2、…、RFLGnの値に基づき、比較器１３０1、１３０2、…、１３０nの比較動作が制御される。例えば、ＲフラグRFLG1、RFLG2、…、RFLGnの値が全て「０」であれば、比較器１３０1、１３０2、…、１３０n全ての比較動作が行われないことになる。この状態を、リスト探索処理が行われていない状態とする。
【０１３７】
比較器１３０1、１３０2、…、１３０nによる比較結果がそれぞれ論理和回路１３４に供給され、フラグLFINDFLGが出力される。また、各比較結果は、セレクタ１３１1、１３１2、…、１３１nに供給され、リスト探索処理の間は、レジスタ１３２1、１３２2、…、１３２nに格納される。また、レジスタ１３２1、１３２2、…、１３２nに格納されるＲフラグRFLG1、RFLG2、…、RFLGnは、アドレス値生成部１３３にも保持される。
【０１３８】
アドレス値生成部１３３は、レジスタ１３２1、１３２2、…、１３２nに格納される値が全て「０」であれば、保持しているＲフラグRFLG1、RFLG2、…、RFLGnのうち値が「１」のＲフラグRFLGmの位置を、アドレス値Addressとし、さらにアドレス変換部１４４で変換アドレス値TAddressとしてコントローラ１０３に渡す。図１７の構成によれば、このリスト探索処理による一連の処理を１クロックで実行可能である。
【０１３９】
図１７の構成によれば、スライド探索部１００と、リスト探索部１０２とがそれぞれ別個の構成とされると共に、スライド探索部１００とリスト探索部１０２とでスライド記憶部１００を共有する。そのため、スライド探索部１００によるスライド探索処理と、リスト探索部１０２によるリスト探索処理とを並列的に実行することが可能である。したがって、リスト探索処理からスライド探索処理へと移行する際の１クロック分の無駄が生じず、符号化処理をより高速化できる。また、図１７の構成によれば、先読みバッファや大規模なマトリクスアレイなどの構成が不要なので、ハードウェア規模を小さくできる。
【０１４０】
なお、エンコーダ２４２の構成は、図１７に示した構成に限定されない。すなわち、ＬＺ７７符号の符号化を行い、レングスLengthおよびアドレス値Addressを出力するものであれば、他の構成のエンコーダを適用することができる。
【０１４１】
＜デコーダ＞
図１８は、デコーダ２４３の一例の構成を示す。デコーダ２４３において、符号読み込み部４００により、上述したエンコーダ２４２で符号化された符号データがフラッシュメモリ２４０から読み込まれる。符号読み込み部４００に読み込まれた符号データは、符号フォーマット解析部４０１に供給される。符号フォーマット解析部４０１は、図４を用いて説明した符号フォーマットに従い、供給された符号データを解釈してデータ値、変換アドレス値TAddress、レングスLengthおよびヘッダを取り出す。取り出されたこれらのデータは、スライド展開部４０２に供給される。
【０１４２】
スライド展開部４０２は、図５を用いて説明したように、直列に接続された複数のレジスタがＦＩＦＯとして構成される、スライド記憶部を持つ。各レジスタは、スライドと呼ばれ、それぞれ１単位（例えば１バイト）のデータを格納可能とされる。スライド展開部４０２は、供給された変換アドレス値TAddressを元のアドレス値Addressに逆変換し、このアドレス値Addressと、供給されたデータ値、レングスLengthおよびヘッダに基づき、スライド記憶部における各スライドに対してデータを展開し、符号データを復号する。復号されたデータは、データ書き込み部４０３に供給され、メインメモリ２１０のプログラム領域２１０Ａに書き込まれる。
【０１４３】
図１９は、変換アドレス値TAddressを元のアドレス値Addressに変換するための逆変換テーブルDTRANSTABLEの一例を示す。この逆変換テーブルDTRANSTABLEに列挙される数値は、元のアドレス値Addressを示す。また、逆変換テーブルDTRANSTABLEに列挙される数値の順番を示す値が、変換アドレス値TAddressを示す。
【０１４４】
すなわち、逆変換テーブルDTRANSTABLEにおいて、変換アドレス値TAddress「０」は、元のアドレス値Address「３」に変換される。また、変換アドレス値TAddress「１５」は、元のアドレス値Address「０」に変換される。同様に、変換アドレス値TAddress「２」は、元のアドレス値Address「１１」に変換される。
【０１４５】
＜復号処理の詳細＞
図２０は、上述した本実施形態の符号化方法により符号化された符号データを、デコーダ２４３で復号する一例の処理を示すフローチャートである。なお、符号読み込み部４００により、フラッシュメモリ２４０から予め符号データが読み込まれているものとする。先ず、ステップＳ１００で、符号フォーマット解析部４０１は、符号読み込み部４００に読み込まれている圧縮データのヘッダを読み込み、ヘッダの値が「０」であるか否かを判定する（ステップＳ１０１）。
【０１４６】
若し、ヘッダの値が「０」であれば、当該ヘッダを含む符号がPASS符号であると判定され、処理がステップＳ１０２に移行される。ステップＳ１０２で、符号フォーマット解析部４０１は、次のステップＳ１０２でヘッダに続く８ビットをデータ値として読み込む。読み込まれたデータ値は、そのまま出力データとして出力される（ステップＳ１０３）と共に、スライド展開部４０２に供給されスライドに追加される（ステップＳ１０４）。データ値のスライドに対する追加処理は、図１４のフローチャートで説明したのと同様の手順により行われる。そして、処理がステップＳ１１５に移行される。
【０１４７】
ステップＳ１１５では、例えば符号読み込み部４００により、読み込まれている符号データに対する処理が全て終了したか否かが判定される。全て終了したと判定されたら、一連の復号処理が終了される。一方、符号読み込み部４００に読み込まれている全ての符号データに対する処理が終了していないと判定されたら、処理はステップＳ１００に戻され、次の符号に対する処理が行われる。
【０１４８】
符号フォーマット解析部４０１は、ステップＳ１０１でヘッダの値が「０」ではないと判定したら、処理をステップＳ１０５に移行させ、ヘッダに続く８ビットをレングスLengthとして読み込む。読み込んだレングスLengthは、スライド展開部４０２に供給される。
【０１４９】
次のステップＳ１０６で、符号フォーマット解析部４０１は、ヘッダの値が「１１」であるか否かを判定する。若し、ヘッダの値が「１１」であると判定したら、処理をステップＳ１０７に移行させ、ヘッダに続く４ビットを変換アドレス値TAddressとして読み込む。一方、ヘッダの値が「１１」ではないと判定したら、処理をステップＳ１０８に移行させ、ヘッダに続く８ビットを変換アドレス値TAddressとして読み込む。ステップＳ１０７またはステップＳ１０８で読み込まれた変換アドレス値TAddressは、スライド展開部４０２に供給される。
【０１５０】
次のステップＳ１０９で、スライド展開部４０２は、図１９に例示した逆変換テーブルDTRANSTABLEを用いて、変換アドレス値TAddressを元のアドレス値Addressに変換する。
【０１５１】
次のステップＳ１１０で、スライド展開部４０２は、スライド記憶部のアドレス値Addressで示されるスライドに格納されるデータを読み込む。読み込まれたデータは、出力データとして出力される（ステップＳ１１１）と共に、スライド展開部４０２に供給されスライドに追加される（ステップＳ１１２）。
【０１５２】
処理はステップＳ１１３に移行され、レングスLengthが「０」より大きいか否かが判定される。若し、レングスLengthが「０」以下であると判定されたら、処理はステップＳ１１５に移行される。一方、レングスLengthが「０」より大きいと判定されたら、ステップＳ１１４でレングスLengthから「１」が減じられた値が新たなレングスLengthとされて、処理がステップＳ１１０に戻される。
【０１５３】
図２１は、デコーダ２４３の一例の構成をより詳細に示す。なお、図２１において、上述の図１８と共通する部分には同一の符号を付し、詳細な説明を省略する。デコーダ２４３は、符号読み込み部４００、符号フォーマット解析部４０１、スライド展開部４０２およびデータ書き込み部４０３を有すると共に、メモリコントローラＩ／Ｆ４１０、符号アドレス生成部４１１およびデータアドレス生成部４１２を有する。
【０１５４】
符号アドレス生成部４１１は、フラッシュメモリ２４０から圧縮符号化されたプログラムデータを読み出す際のメモリアドレスを生成する。符号読み込み部４００は、符号アドレス生成部４１１で生成されたメモリアドレスからのデータの読み出しを、メモリコントローラＩ／Ｆ４１０を介してメモリコントローラ２０２に対して要求する。この要求に応じてメモリコントローラ２０２によりフラッシュメモリ２４０から読み出された、プログラムデータが圧縮符号化された符号データが、メモリコントローラ２０２からデコーダ２４３に対して供給され、メモリコントローラＩ／Ｆ４１０を介して符号読み込み部４００に供給される。符号読み込み部４００は、この符号データを、符号フォーマット解析部４０１に供給する。
【０１５５】
符号フォーマット解析部４０１は、図４で説明した符号フォーマットに従い、供給された符号データから、ヘッダ、レングスLength、データ値および変換アドレス値TAddressを取り出して、スライド展開部４０２に供給する。ここで、変換アドレス値TAddressは、逆変換テーブルDTRANSTABLEを用いて元のアドレス値Addressに変換される。スライド展開部４０２は、このアドレス値Addressと、供給されたデータ値、レングスLengthおよびヘッダに基づき、スライド記憶部における各スライドに対してデータを展開し、符号データを元のプログラムデータに復号する。復号されたプログラムデータは、データ書き込み部４０３に供給される。
【０１５６】
データ書き込み部４０３は、供給されたプログラムデータをメモリコントローラＩ／Ｆ４１０を介してメモリコントローラ２０２に供給する。それと共に、データ書き込み部４０３は、当該プログラムデータをデータアドレス生成部４１２で生成されたメモリアドレスに従いメインメモリ２１０のプログラム領域２１０Ａに書き込むように、メモリコントローラＩ／Ｆ３１０を介してメモリコントローラ２０２に要求する。メモリコントローラ２０２は、この要求に従い、供給されたプログラムデータを、メインメモリ２１０のプログラム領域２１０Ａに書き込む。
【０１５７】
＜スライド展開部のハードウェア構成＞
図２２は、スライド展開部４０２の一例のハードウェア構成を示す。スライド展開部４０２は、スライド記憶部５００、コントローラ５０１、セレクタ５０２および５０３、ならびに、アドレス逆変換部５２０を有する。アドレス逆変換部５２０は、上述した逆変換テーブルDTRANSTABLEを有し、符号フォーマット解析部４０１から供給された変換アドレス値TAddressを逆変換テーブルDTRANSTABLEを用いて元のアドレス値Addressに変換して、コントローラ５０１に渡す。
【０１５８】
コントローラ５０１は、例えばマイクロプロセッサからなり、アドレス値Address、レングスLengthおよび一致フラグFLAGが供給され、供給されたこれらのデータに基づきこのスライド展開部４０２の全体の動作を制御する。例えばコントローラ５０１は、スライド記憶部５００におけるデータ値のスライドに対する追加処理や、セレクタ５０２および５０３の動作などを制御する。
【０１５９】
スライド記憶部５００は、各々がレジスタからなり、それぞれ１単位のデータが格納されるｎ個のスライド５１１1、５１１2、…、５１１nが直列に接続されて構成されたＦＩＦＯと、当該ＦＩＦＯの先頭に接続されるセレクタ５１０とを有する。
【０１６０】
各スライド５１０1、５１０2、…、５１０nの出力は、さらに、それぞれセレクタ５０２に供給される。セレクタ５０２の出力は、セレクタ５０３に供給されると共に、セレクタ５１０にも供給される。
【０１６１】
符号フォーマット解析部４０１から読み込まれたデータ値がセレクタ５１０に供給されると共に、セレクタ５０３にも供給される。セレクタ５１０は、図１３のステップＳ１０４のスライド追加処理時には、入力されたデータ値をスライド５１１1に追加する。また、図１３のステップＳ１０８のスライド追加処理時には、ステップＳ１０６においてスライド符号のアドレス値Addressに基づき選択されたスライドから出力されたデータを、スライド５１１1に追加する。
【０１６２】
セレクタ５０２は、図１３のステップＳ１０６の処理時に、コントローラ５０１から供給されるアドレス値Addressに従い、スライド記憶部５００の各スライド５１１1、５１１2、…、５１１nの出力からスライド５１１Addressの出力を選択し、選択した出力を、セレクタ５０３および５１０にそれぞれ供給する。
【０１６３】
セレクタ５０３は、図１３のステップＳ１０３において、ステップＳ１０２で読み込まれたデータ値を出力する。また、図１３のステップＳ１０７のデータ出力処理時に、セレクタ５０２から供給されたデータを出力する。
【０１６４】
なお、デコーダ２４３の構成は、図２２に示した構成に限定されない。すなわち、レングスLengthおよびアドレス値Addressに基づきＬＺ７７符号の復号を行うものであれば、他の構成のデコーダを適用することができる。
【０１６５】
また、上述では、本発明がプリンタ装置に適用されるように説明したが、これは一例でありこの例に限定されない。すなわち、本発明は、マシン語のプログラムデータの可逆符号化をハードウェアを用いて行う他の装置にも適用することが可能である。
【符号の説明】
【０１６６】
１００ スライド探索部
１０１ スライド記憶部
１０２ リスト探索部
１０３ コントローラ
１１０，１３４ 論理和回路
１１１1〜１１１n，１３０1〜１３０n 比較器
１２０1〜１２０n スライド
１３１1〜１３１n セレクタ
１３２1〜１３２n レジスタ
１３３ アドレス値生成部
１４４ アドレス変換部
２００ プリンタ装置
２１０ メインメモリ
２１０Ａ プログラム領域
２４０ フラッシュメモリ
２４２ エンコーダ
２４３ デコーダ
３０１ スライド／リスト生成処理部
４０２ スライド展開部
５００ スライド記憶部
５０１ コントローラ
５０２，５０３，５１０ セレクタ
５１１1〜５１１n スライド
５２０ アドレス逆変換部
【先行技術文献】
【特許文献】
【０１６７】
【特許文献１】特開平７−３１９７４３号公報
【特許文献２】特開２００４−１７８２８９号公報
【特許請求の範囲】
【請求項１】
入力データを順次記憶するスライド記憶手段と、
連続的に入力された前記入力データからなる入力データ列と一致する、前記スライド記憶手段に記憶されるデータ列を探索する探索手段と、
前記探索手段で探索された前記データ列から１を選択して、選択された該データ列の長さを求めてレングス値を生成するレングス生成手段と、
前記レングス生成手段で前記レングス値を生成するために用いた前記データ列における開始データの、前記スライド記憶手段内での位置を求めアドレス値を生成するアドレス値生成手段と、
前記アドレス値の出現頻度に従い、該アドレス値生成手段で生成された前記アドレス値のうち、該出現頻度が高い該アドレス値から所定数の該アドレス値を、予め定められた値以下の変換アドレス値に変換する変換手段と、
前記レングス値と前記変換アドレス値とを符号化する符号化手段と
を有する
ことを特徴とするデータ処理装置。
【請求項２】
前記変換手段は、
前記アドレス値生成手段で生成された前記アドレス値のうち、該アドレス値の所定単位毎の前記出現頻度が高い該アドレス値から所定数の該アドレス値を、予め定められた値以下の変換アドレス値に変換する
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記変換手段は、
前記アドレス値生成手段で生成された前記アドレス値のうち、前記所定単位毎の出現頻度を除外した全体の前記出現頻度が高い側のアドレス値を前記所定数のアドレス値に含めて、該所定数のアドレス値を予め定められた値以下の変換アドレス値に変換する
ことを特徴とする請求項２に記載のデータ処理装置。
【請求項４】
前記所定単位は４バイトである
ことを特徴とする請求項２または請求項３に記載のデータ処理装置。
【請求項５】
前記データは、マシン語によるプログラムデータである
ことを特徴とする請求項１乃至請求項４の何れか１項に記載のデータ処理装置。
【請求項６】
スライド記憶手段が、入力データを順次記憶するスライド記憶ステップと、
探索手段が、連続的に入力された前記入力データからなる入力データ列と一致する、前記スライド記憶手段に記憶されるデータ列を探索する探索ステップと、
レングス生成手段が、前記探索ステップで探索された前記データ列から１を選択して、選択された該データ列の長さを求めてレングス値を生成するレングス生成ステップと、
アドレス値生成手段が、前記レングス生成ステップで前記レングス値を生成するために用いた前記データ列における開始データの、前記スライド記憶手段内での位置を求めアドレス値を生成するアドレス値生成ステップと、
変換手段が、前記アドレス値の出現頻度に従い、該アドレス値生成ステップで生成された前記アドレス値のうち、該出現頻度が高い該アドレス値から所定数の該アドレス値を、予め定められた値以下の変換アドレス値に変換する変換ステップと、
符号化手段が、前記レングス値と前記変換アドレス値とを符号化する符号化ステップと
を有する
ことを特徴とするデータ処理方法。
【請求項１】
入力データを順次記憶するスライド記憶手段と、
連続的に入力された前記入力データからなる入力データ列と一致する、前記スライド記憶手段に記憶されるデータ列を探索する探索手段と、
前記探索手段で探索された前記データ列から１を選択して、選択された該データ列の長さを求めてレングス値を生成するレングス生成手段と、
前記レングス生成手段で前記レングス値を生成するために用いた前記データ列における開始データの、前記スライド記憶手段内での位置を求めアドレス値を生成するアドレス値生成手段と、
前記アドレス値の出現頻度に従い、該アドレス値生成手段で生成された前記アドレス値のうち、該出現頻度が高い該アドレス値から所定数の該アドレス値を、予め定められた値以下の変換アドレス値に変換する変換手段と、
前記レングス値と前記変換アドレス値とを符号化する符号化手段と
を有する
ことを特徴とするデータ処理装置。
【請求項２】
前記変換手段は、
前記アドレス値生成手段で生成された前記アドレス値のうち、該アドレス値の所定単位毎の前記出現頻度が高い該アドレス値から所定数の該アドレス値を、予め定められた値以下の変換アドレス値に変換する
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記変換手段は、
前記アドレス値生成手段で生成された前記アドレス値のうち、前記所定単位毎の出現頻度を除外した全体の前記出現頻度が高い側のアドレス値を前記所定数のアドレス値に含めて、該所定数のアドレス値を予め定められた値以下の変換アドレス値に変換する
ことを特徴とする請求項２に記載のデータ処理装置。
【請求項４】
前記所定単位は４バイトである
ことを特徴とする請求項２または請求項３に記載のデータ処理装置。
【請求項５】
前記データは、マシン語によるプログラムデータである
ことを特徴とする請求項１乃至請求項４の何れか１項に記載のデータ処理装置。
【請求項６】
スライド記憶手段が、入力データを順次記憶するスライド記憶ステップと、
探索手段が、連続的に入力された前記入力データからなる入力データ列と一致する、前記スライド記憶手段に記憶されるデータ列を探索する探索ステップと、
レングス生成手段が、前記探索ステップで探索された前記データ列から１を選択して、選択された該データ列の長さを求めてレングス値を生成するレングス生成ステップと、
アドレス値生成手段が、前記レングス生成ステップで前記レングス値を生成するために用いた前記データ列における開始データの、前記スライド記憶手段内での位置を求めアドレス値を生成するアドレス値生成ステップと、
変換手段が、前記アドレス値の出現頻度に従い、該アドレス値生成ステップで生成された前記アドレス値のうち、該出現頻度が高い該アドレス値から所定数の該アドレス値を、予め定められた値以下の変換アドレス値に変換する変換ステップと、
符号化手段が、前記レングス値と前記変換アドレス値とを符号化する符号化ステップと
を有する
ことを特徴とするデータ処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１１−１９３４０６（Ｐ２０１１−１９３４０６Ａ）
【公開日】平成２３年９月２９日（２０１１．９．２９）
【国際特許分類】
【出願番号】特願２０１０−６０００８（Ｐ２０１０−６０００８）
【出願日】平成２２年３月１６日（２０１０．３．１６）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【Ｆターム（参考）】
【公開日】平成２３年９月２９日（２０１１．９．２９）
【国際特許分類】
【出願日】平成２２年３月１６日（２０１０．３．１６）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【Ｆターム（参考）】
[ Back to top ]