(57)【要約】  予測誤差算出部１１１が、入力データごとに予測誤差を算出し、予測誤差符号化部１１２が予測誤差の値を符号化して予測誤差符号を生成し、ランレングス計数部１２１が予測誤差のランレングスを計数し、ランレングス符号化部１２２が、予測誤差の値が変化した際に、計数されたランレングスを符号化してランレングス符号を生成し、符号結合部１３１が、ランレングス符号を対応する予測誤差の予測誤差符号に結合して結合符号を生成し、予測誤差判定部１４１が、予測誤差の値が特定の値である場合に当該予測誤差に対する結合符号を出力符号として選択し、他の値である場合に当該予測誤差に対する予測誤差符号を出力符号として選択し、符号出力部１５１が選択された出力符号を出力する。
2011108089.tif 000002
【特許請求の範囲】
【請求項１】
データを順次入力するデータ圧縮装置であって、
データの入力前にデータの値を予測し、データを入力する度に、入力した入力データの値と当該入力データに対して予測した予測値との差を予測誤差として算出する予測誤差算出部と、
前記予測誤差算出部により予測誤差が算出される度に、算出された予測誤差の値を符号化して予測誤差符号を生成する予測誤差符号化部と、
前記予測誤差算出部により算出された予測誤差のランレングスを計数するランレングス計数部と、
予測誤差の値が変化した際に、前記ランレングス計数部により計数されたランレングスを符号化してランレングス符号を生成するランレングス符号化部と、
前記ランレングス符号化部によりランレングス符号が生成される度に、生成されたランレングス符号を当該ランレングス符号に対応する予測誤差の予測誤差符号に結合して結合符号を生成する符号結合部と、
前記予測誤差算出部により算出された予測誤差の値に応じて、当該予測誤差に対する予測誤差符号及び結合符号のいずれかを出力符号として選択する符号選択部とを有することを特徴とするデータ圧縮装置。
【請求項２】
前記符号選択部は、
前記予測誤差算出部により算出された予測誤差の値が特定の値である場合に当該予測誤差に対する結合符号を選択し、前記予測誤差算出部により算出された予測誤差の値が他の値である場合に当該予測誤差に対する予測誤差符号を選択することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項３】
前記符号選択部は、
前記予測誤差算出部により算出された予測誤差の値が特定の値である場合に、前記ランレングス計数部に当該予測誤差のランレングスの計数の開始を指示し、
前記ランレングス計数部は、
前記符号選択部により指示のあった予測誤差のランレングスの計数を開始することを特徴とする請求項２に記載のデータ圧縮装置。
【請求項４】
前記データ圧縮装置は、更に、
前記予測誤差算出部のデータ入力に先立ち、前記予測誤差算出部が入力することになる複数の入力予定データに対して特定の値を選定し、選定した値の予測誤差に対する出力符号として結合符号を選択するよう前記符号選択部に指示する選定指示部を有し、
前記符号選択部は、
前記予測誤差算出部により算出された予測誤差の値が前記選定指示部から指示された値である場合に出力符号として当該予測誤差に対する結合符号を選択し、前記予測誤差算出部により算出された予測誤差の値が他の値である場合に出力符号として当該予測誤差に対する予測誤差符号を選択することを特徴とする請求項１〜３のいずれかに記載のデータ圧縮装置。
【請求項５】
前記データ圧縮装置は、更に、
前記予測誤差算出部のデータ入力に先立ち、入力予定データごとに前記予測誤差算出部の予測方式と同じ方式によりデータ値を予測し、入力予定データごとに予測誤差を算出する先行予測誤差算出部と、
前記先行予測誤差算出部により算出された予測誤差のランレングスを計数する先行ランレングス計数部と、
結合符号の符号長を算出する結合符号長算出値として所定の値が設定されており、前記先行予測誤差算出部により算出された予測誤差の値が前記結合符号長算出値と一致する場合に当該予測誤差の値と前記先行ランレングス計数部によるランレングスとに基づき結合符号の符号長を算出し、前記先行予測誤差算出部により算出された予測誤差の値が前記結合符号長算出値に一致しない場合に当該予測誤差の値に基づき予測誤差符号の符号長を算出して、前記複数の入力予定データでの合計符号長を算出する符号長算出部とを有し、
前記選定指示部は、
前記符号長算出部により算出された合計符号長が所定の条件を満たす場合に、前記結合符号長算出値を前記符号選択部において結合符号を選択させる値として選定することを特徴とする請求項４に記載のデータ圧縮装置。
【請求項６】
前記データ圧縮装置は、
結合符号長算出値としてそれぞれに異なる値が設定されており、それぞれの結合符号長算出値に基づいて予測誤差ごとに結合符号の符号長及び予測誤差符号の符号長のいずれかを算出して、前記複数の入力予定データでの合計符号長を算出する複数の符号長算出部を有し、
前記選定指示部は、
最小の合計符号長の符号長算出部の結合符号長算出値を前記符号選択部において結合符号を選択させる値として選定することを特徴とする請求項５に記載のデータ圧縮装置。
【請求項７】
前記データ圧縮装置は、更に、
結合符号長算出値として値０が設定されており、前記先行予測誤差算出部により算出された予測誤差の値が０である場合に結合符号の符号長を算出し、前記先行予測誤差算出部により算出された予測誤差の値が０でない場合に予測誤差符号の符号長を算出する符号長算出部と、
結合符号長算出値として絶対値１以下が設定されており、前記先行予測誤差算出部により算出された予測誤差の絶対値が１以下である場合に結合符号の符号長を算出し、前記先行予測誤差算出部により算出された予測誤差の絶対値が１以下でない場合に予測誤差符号の符号長を算出する符号長算出部との少なくともいずれかを有することを特徴とする請求項６に記載のデータ圧縮装置。
【請求項８】
前記データ圧縮装置は、
結合符号長算出値が設定されておらず、前記先行予測誤差算出部により算出された予測誤差に対して予測誤差符号の符号長のみを算出して、前記複数の入力予定データでの合計符号長を算出する特例符号長算出部を有し、
前記選定指示部は、
前記符号長算出部により算出された合計符号長が前記特例符号長算出部により算出された合計符号長よりも小さい場合に、前記符号長算出部の結合符号長算出値を前記符号選択部において結合符号を選択させる値として選定し、
前記符号長算出部により算出された合計符号長が前記特例符号長算出部により算出された合計符号長以上である場合に、前記符号選択部に対して予測誤差の値にかかわらず出力符号として予測誤差符号のみを選択するよう指示することを特徴とする請求項５に記載のデータ圧縮装置。
【請求項９】
前記予測誤差符号化部は、
予測誤差の値を可変長符号により符号化して予測誤差符号を生成し、
前記ランレングス符号化部は、
ランレングスを可変長符号により符号化してランレングス符号を生成することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項１０】
前記予測誤差符号化部は、
前記予測誤差算出部により予測誤差が算出される度に、算出された予測誤差の値が所定の固定ビット数で表される整数値のうちの最小値に該当するか否かを判断し、前記予測誤差の値が前記最小値に該当する場合に前記予測誤差の値を前記固定ビット数により符号化して予測誤差符号を生成し、前記予測誤差の値が前記最小値に該当しない場合に前記予測誤差の値を正の整数にマッピングし、マッピングした正の整数を可変長符号により符号化して予測誤差符号を生成することを特徴とする請求項９に記載のデータ圧縮装置。
【請求項１１】
前記予測誤差符号化部は、
アルファ符号、ガンマ符号、デルタ符号、オメガ符号及びゴロム符号のいずれかにより予測誤差符号を生成し、
前記ランレングス符号化部は、
アルファ符号、ガンマ符号、デルタ符号、オメガ符号及びゴロム符号のいずれかによりランレングス符号を生成することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項１２】
前記予測誤差符号化部は、
次に入力するデータの１つ前に入力したデータの値を次に入力するデータの予測値とすることを特徴とする請求項１に記載のデータ圧縮装置。
【請求項１３】
前記予測誤差符号化部は、
次に入力するデータに先行して入力している２つ以上のデータを用いた線形演算を行って、次に入力するデータの予測値を算出することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項１４】
データを順次入力するコンピュータが行うデータ圧縮方法であって、
前記コンピュータが、データの入力前にデータの値を予測し、データを入力する度に、入力した入力データの値と当該入力データに対して予測した予測値との差を予測誤差として算出し、
予測誤差を算出する度に、前記コンピュータが、算出した予測誤差の値を符号化して予測誤差符号を生成し、
前記コンピュータが、算出した予測誤差のランレングスを計数し、
予測誤差の値が変化した際に、前記コンピュータが、計数したランレングスを符号化してランレングス符号を生成し、
ランレングス符号を生成する度に、前記コンピュータが、生成したランレングス符号を当該ランレングス符号に対応する予測誤差の予測誤差符号に結合して結合符号を生成し、
前記コンピュータが、算出した予測誤差の値に応じて、当該予測誤差に対する予測誤差符号及び結合符号のいずれかを出力符号として選択することを特徴とするデータ圧縮方法。
【請求項１５】
データを順次入力するコンピュータに、
データの入力前にデータの値を予測し、データを入力する度に、入力した入力データの値と当該入力データに対して予測した予測値との差を予測誤差として算出する予測誤差算出処理と、
前記予測誤差算出処理により予測誤差が算出される度に、算出された予測誤差の値を符号化して予測誤差符号を生成する予測誤差符号化処理と、
前記予測誤差算出処理により算出された予測誤差のランレングスを計数するランレングス計数処理と、
予測誤差の値が変化した際に、前記ランレングス計数処理により計数されたランレングスを符号化してランレングス符号を生成するランレングス符号化処理と、
前記ランレングス符号化処理によりランレングス符号が生成される度に、生成されたランレングス符号を当該ランレングス符号に対応する予測誤差の予測誤差符号に結合して結合符号を生成する符号結合処理と、
前記予測誤差算出処理により算出された予測誤差の値に応じて、当該予測誤差に対する予測誤差符号及び結合符号のいずれかを出力符号として選択する符号選択処理とを実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ圧縮技術に関する。
【背景技術】
【０００２】
従来より、データの可逆圧縮には様々な手法が用いられている。
例えば、予測符号化を利用し、予測誤差を出現頻度に応じた可変長符号化と組み合わせる方法が一般的に用いられている。
また、データの変化が無い領域においては、ランレングス符号化を用いる手法が一般的に用いられている。
特許文献１では、画像の符号化処理を行う際に、入力データの過去の履歴において、所定の複数のデータが一致しない場合には予測符号化と可変長符号化を行い、一致した場合に、ランレングス符号化モードに移行して、ランレングス符号化を行う技術が開示されている。
復号時にも、復号済みデータの履歴において、所定の複数のデータが一致する場合にランレングス符号化モードに移行することにより、復号可能であることが示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−１０９１９４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１においては、入力データの変化が無い領域についてのみランレングス符号化を行うため、一定の傾きで増減するデータなどの予測モデルに適合した変化を続けるデータについてはランレングス符号化されず、圧縮効率に課題がある。
また、ランレングス符号化モードの判定を複数のデータの比較処理により行わなければならないため、モード判定のための計算量が増え、実行速度が低下するという課題がある。【０００５】
この発明は上記のような課題を解決することを主な目的とし、温度や電力量などのセンサデータなどの時系列データの圧縮において、一定の傾きで増減するデータなどの予測モデルに適合した変化を続けるデータに対しても効率よく圧縮が可能であり、かつ計算量を減らしてより圧縮伸張の実行速度を高めることができるデータ圧縮技術を提供することを主な目的とする。
【課題を解決するための手段】
【０００６】
本発明に係るデータ圧縮装置は、
データを順次入力するデータ圧縮装置であって、
データの入力前にデータの値を予測し、データを入力する度に、入力した入力データの値と当該入力データに対して予測した予測値との差を予測誤差として算出する予測誤差算出部と、
前記予測誤差算出部により予測誤差が算出される度に、算出された予測誤差の値を符号化して予測誤差符号を生成する予測誤差符号化部と、
前記予測誤差算出部により算出された予測誤差のランレングスを計数するランレングス計数部と、
予測誤差の値が変化した際に、前記ランレングス計数部により計数されたランレングスを符号化してランレングス符号を生成するランレングス符号化部と、
前記ランレングス符号化部によりランレングス符号が生成される度に、生成されたランレングス符号を当該ランレングス符号に対応する予測誤差の予測誤差符号に結合して結合符号を生成する符号結合部と、
前記予測誤差算出部により算出された予測誤差の値に応じて、当該予測誤差に対する予測誤差符号及び結合符号のいずれかを出力符号として選択する符号選択部とを有することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、入力データに対して予測誤差を算出し、予測誤差のランレングスを計数するので、一定の傾きで増減するデータについても効率的にランレングス符号化を行うことができる。
また、本発明では、予測誤差の値に応じて予測誤差符号及び結合符号のいずれかを出力符号として選択するため、データ値の変動特性に対応させて、結合符号が選択される予測誤差を適切に決定することにより、圧縮効率を高めることができる。
【図面の簡単な説明】
【０００８】
【図１】実施の形態１に係るデータ圧縮装置の構成例を示す図。
【図２】実施の形態１に係るデータ圧縮装置の動作例を示すフローチャート図。
【図３】実施の形態１に係るデータ圧縮装置の動作例を示すフローチャート図。
【図４】実施の形態２に係るデータ圧縮装置の構成例を示す図。
【図５】実施の形態２に係るデータ圧縮装置の動作例を示すフローチャート図。
【図６】実施の形態２に係るデータ圧縮装置の動作例を示すフローチャート図。
【図７】実施の形態２に係るデータ圧縮装置の動作例を示すフローチャート図。
【図８】実施の形態１に係る入力データ値、予測誤差、ランレングス等の例を示す図。
【図９】実施の形態１及び２に係るデータ圧縮装置のハードウェア構成例を示す図。
【図１０】実施の形態１に係るデータ伸張装置の構成例を示す図。
【図１１】実施の形態１に係るデータ伸張装置の動作例を示すフローチャート図。
【発明を実施するための形態】
【０００９】
実施の形態１．
図１は、本実施の形態に係るデータ圧縮装置１００の機能ブロックの構成の一例を示す図である。
【００１０】
データ圧縮装置１００は、圧縮の対象となるデータ（入力データ）を順次入力し、圧縮を行って出力データを出力する。
入力データは、例えば電力量や温度などを含むセンサデータのような、時系列データであり、データが時間の経過順に並んでいる場合が特に好適である。
入力データの処理単位は例えば８ビット、１６ビット、３２ビット、６４ビットなどのＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）による処理に適した固定長であり、対象データは固定小数点または整数化された数値とすることで、高速な演算が可能となる。
例えば温度データを小数点以下１桁まで扱う場合には元データを１０倍して３２ビット整数として扱うことができる。
出力データは、可変長符号化された上で処理単位にパックされて出力される。
以下の説明では処理単位を３２ビットとする。
【００１１】
データ圧縮装置１００は、予測誤差算出部１１１、予測誤差符号化部１１２、ランレングス計数部１２１、ランレングス符号化部１２２、符号結合部１３１、予測誤差判定部１４１、出力符号切換え部１４２、符号出力部１５１を含む。
【００１２】
予測誤差算出部１１１は、入力データを一定の処理単位ごとに入力し、過去に入力したデータの履歴を用いて現在処理中のデータを予測した予測値と実際の現在処理中のデータとの差分を取ることにより予測誤差Ｅを算出する。
つまり、予測誤差算出部１１１は、データの入力前にデータの値を予測し、データを入力する度に、入力した入力データの値と当該入力データに対して予測した予測値との差を予測誤差Ｅとして算出する。
【００１３】
例えば、予測誤差算出部１１１では、現在処理中のデータの直前に入力されたデータの値を予測値とすることができる。
つまり、予測誤差算出部１１１は、次に入力するデータの１つ前に入力したデータの値を次に入力するデータの予測値とする。
センサデータなどの時系列データにおいては、センサのサンプリング間隔が測定対象の変化に対して短い場合に、変化幅の小さい時系列信号となり、直前のデータとの差分（予測誤差Ｅ）が０または絶対値の小さい値に集約され、圧縮率を高めることができる。
例えば室内温度を１分間隔で小数点以下１桁まで計測したデータなどのような場合がこのケースに当てはまる。
直前のデータとの差分を取る方法（以下、差分法）により、最小の演算量で予測誤差算出が可能となり、高速な圧縮処理が可能となる。
【００１４】
また別の例では、予測誤差算出部１１１は、直前のＮ（Ｎ≧２）個のデータから線形予測を行ってもよい。
つまり、予測誤差算出部１１１は、次に入力するデータに先行して入力している２つ以上のデータを用いた線形演算を行って、次に入力するデータの予測値を算出するようにしてもよい。
より具体的には、計測時間をｘとし、データをｙとし、Ｎ組のデータ（ｘ１，ｙ１），（ｘ２，ｙ２），．．．，（ｘＮ，ｙＮ）から以下の一次方程式のパラメータａ、ｂを最小二乗法により求める。
ｙ＝ａｘ＋ｂ
なお、最小二乗法は、以下の式による。
【００１５】
【数１】
2011108089.tif 000003
【００１６】
例えば、直前の３点のデータを用いて予測する場合、サンプリング間隔を等間隔と仮定すれば、以下の式により予測値ｙ４’を求めることができる。
【００１７】
【数２】
2011108089.tif 000004
【００１８】
予想値ｙ４’を四捨五入などにより整数化し、その後実際に入力したデータｙ４との予測誤差Ｅ＝ｙ４’−ｙ４を算出する。
これにより、積算電力量計による電力量などのセンサデータのようにほぼ一定の割合で増加（あるいは減少）するデータの場合に予測誤差Ｅが０または絶対値の小さい値に集約され、圧縮率を高めることができる。
【００１９】
予測誤差符号化部１１２は、予測誤差算出部１１１により予測誤差Ｅが算出される度に、算出された予測誤差Ｅを可変長符号化し、予測誤差符号Ｃｅを出力する。
可変長符号化の方法としてはガンマ符号あるいはデルタ符号を用いることができる。
ガンマ符号やデルタ符号は絶対値の小さい値を少ない符号長にて符号化する方式であり、既に述べたとおり、本実施の形態では予測誤差Ｅは０または絶対値の小さい値になっているため、高い圧縮効果が期待できる。
また、ガンマ符号やデルタ符号は固定的な符号化を行うため、算術符号化やハフマン符号化などのエントロピー符号にて必要となるシンボル出現頻度テーブルの作成が不要となり、計算量を削減して高速な処理が可能となる。
【００２０】
具体的にはガンマ符号であれば次のように符号化を行う。
符号化対象データを２進数で表したときのビット数−１個の０（２進）に続けて、符号化対象データを２進数で出力する。
例えば、以下のようになる（以下は、すべて２進数）。
１  →        １（（１ビット−１）個の０と、１）
１０  →    ０１０（（２ビット−１）個の０と、１０）
１００  →００１００（（３ビット−１）個の０と、１００）
【００２１】
対象データのビット数が５ビット以下であれば、ガンマ符号の方が短い符号を生成できるため、予測誤差Ｅの分布が０付近に集中するようなデータではガンマ符号により高い圧縮率を実現できる。
予測誤差Ｅの分布が０から外れる頻度が多くなる場合、例えば変動が大きいセンサデータなどでは、デルタ符号を用いることでより高い圧縮率を実現できる。
以下の説明ではガンマ符号を例に説明するが、デルタ符号でも同様である。
【００２２】
ガンマ符号あるいはデルタ符号は正の整数の符号化を行う方式であるので、０や負の値を含む予測誤差Ｅを符号化するために、予測誤差符号化部１１２は、ガンマ符号化あるいはデルタ符号化の前に次に示す変換を行う。
【００２３】
【数３】
2011108089.tif 000005
【００２４】
つまり、予測誤差Ｅ＝０のときは、値を１にし、予測誤差Ｅ＞０のときは、左シフトを行い、予測誤差Ｅ＜０のときは、左シフトを行い、ＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）を１にする。
この変換によれば、絶対値が小さい値を絶対値が小さい値として変換できるため、ガンマ符号化あるいはデルタ符号化により高い圧縮率を期待できる。
【００２５】
変換式Ｍ１においては、予測誤差Ｅが処理単位（例えば３２ビット）を符号付き整数と考えたときの最小値（１０進数表示で−２１４７４８３６４８、−２３１）の場合に、左シフトにより桁あふれが発生する。
そこで、予測誤差符号化部１１２は、予測誤差Ｅが処理単位の最小値Ｅｍｉｎ（処理単位が３２ビットの場合の１０進数表示での−２１４７４８３６４８、−２３１）である場合には、Ｍ１による変換を行わずにＥｍｉｎに対応する固定符号を出力する。
このようにすることで、桁あふれを考慮して処理単位を拡大する必要がなくなり、処理を高速化できる。
例えば、Ｅｍｉｎ＝０ｘ８０００００００（１６進）であり、Ｍ１（Ｅｍｉｎ）＝０ｘ１０００００００１（１６進）となって３３ビットとなる。
そこでＥ＝Ｅｍｉｎである場合にはそれに対応する符号を直接出力する。
例えば、ガンマ符号であれば、以下に示す６５ビットの符号を変換式Ｍ１による変換を行わずに出力する。
【００２６】
【数４】
2011108089.tif 000006
【００２７】
あるいは、Ｍ１（Ｅ）が３３ビットとなるケースはＥ＝Ｅｍｉｎの１ケースのみであるから、ガンマ符号においてＥのビット数が３３であることだけ分かれば復号可能である。
従って、以下のような３３ビットに符号化することで圧縮率を更に高めることができる。
【００２８】
【数５】
2011108089.tif 000007
【００２９】
データの特性として、予測誤差Ｅが０以上の整数となる場合が多い場合には、以下の変換式を用いることもできる。
【００３０】
【数６】
2011108089.tif 000008
【００３１】
例えば、積算電力量計の電力量データの場合は通常は増加のみであり、有効桁数を超えたときに０に戻るため、負の予測誤差が出現する頻度は極端に低いと考えられる。
従って、変換式Ｍ１よりも正の値のビット数が少ない変換式Ｍ２によって、より高い圧縮率を期待できる。
【００３２】
変換式Ｍ２においても、Ｍ１と同様に桁あふれが発生するため、Ｍ１の場合と同様な固定符号を使用することで、桁あふれを考慮して処理単位を拡大する必要がなくなり、処理を高速化できる。
【００３３】
ランレングス計数部１２１は、予測誤差Ｅが同じ値を続ける回数をカウントする。
ランレングス計数部１２１は、前回の予測誤差Ｅｐを保持し、現在処理中の予測誤差ＥｃがＥｐに等しい場合には、変数ランレングスＲに１を加算する。
ＥｃがＥｐと異なる場合には、ランレングス計数部１２１は、ランレングスＲの値をランレングス符号化部１２２に出力し、ランレングス符号化部１２２がランレングスを符号化する。
また、ランレングス計数部１２１は、ランレングスＲを１にリセットする。
ＥｃがＥｐに等しい場合でも、ランレングスＲ＋１が指定の最大値を超える場合には、ランレングス計数部１２１は、ランレングスＲをランレングス符号化部１２２に出力し、ランレングスＲを１にリセットするようにしてもよい。
【００３４】
ランレングス符号化部１２２は、ランレングス計数部１２１にて計数されたランレングスＲの値を可変長符号化し、ランレングス符号Ｃｒを出力する。
可変長符号化の方法としてはガンマ符号あるいはデルタ符号を用いることができる。
電力量や温度などのセンサデータに関しては、ランレングスの出現頻度分布は、１が最大（１が最頻）で値が大きくなるほど頻度が小さくなる傾向があるため、既に述べたように、ガンマ符号やデルタ符号で高い圧縮効果が期待できる。
また、ガンマ符号やデルタ符号により計算量を削減して高速な処理が可能となるのも既に述べた通りである。
ランレングスの場合には必ず１以上の整数となるため、予測誤差の符号化に関して述べたような特別の変換は不要であり、直接符号化する。
【００３５】
符号結合部１３１は、ランレングス符号化部１２２によりランレングス符号が生成される度に、予測誤差符号化部１１２による予測誤差符号Ｃｅとランレングス符号化部１２２によるランレングス符号Ｃｒを繋げて１つの結合符号Ｃｅｒとする。
順序は予測誤差符号化部１１２による予測誤差符号Ｃｅが先になるようにする。
すなわち、結合符号Ｃｅｒは、以下のようになる。
Ｃｅｒ＝Ｃｅ＋Ｃｒ    （＋は結合の意味）
【００３６】
予測誤差判定部１４１は、予測誤差Ｅの値により出力符号切換え部１４２を制御し、符号ＣｅとＣｅｒのいずれを出力符号とするかを選択する。
予測誤差判定部１４１は、符号選択部の例である。
【００３７】
比較的変動やノイズが少ないセンサデータでは、予測誤差Ｅ＝０が連続する頻度が大きいため、Ｅ＝０のときに結合符号Ｃｅｒを出力符号としそれ以外は予測誤差符号Ｃｅを出力符号とすることにより、圧縮率を高めることが可能である。
あるいは、一定の割合で緩やかに増減するセンサデータにおいて、前述の差分法により予測誤差Ｅを算出した場合には、＋１や−１が連続する頻度が大きくなる。
したがって、Ｅ＝１または−１の場合に結合符号Ｃｅｒを出力符号とし、それ以外は予測誤差符号Ｃｅを出力符号とすることにより、圧縮率を高めることが可能である。
更に傾きの大きな増減を行うセンサデータにおいては、予測誤差Ｅがより大きい値（例えば、予測誤差Ｅが５）のときでも予測誤差符号Ｃｅｒを出力符号とすることで圧縮率を高めることができる場合がある。
一般には予測誤差Ｅの絶対値が大きいほどそれが連続する確率は下がるため、予測誤差Ｅの絶対値が指定の閾値以下であれば結合符号Ｃｅｒを出力し、閾値を超える場合には予測誤差符号Ｃｅを出力するように判定を行うのが合理的である。
一方、全ての予測誤差に対してランレングスが小さい場合には全くランレングス符号化を行わないほうが圧縮率を高めることができる場合もある。
そのような場合には、予測誤差Ｅの値によらず予測誤差符号Ｃｅを出力符号として選択するという動作が有効となる。
【００３８】
以上のようにして、予測誤差Ｅの値に応じて予測誤差符号Ｃｅを出力符号とするか予測誤差符号とランレングス符号を結合した符号Ｃｅｒを出力符号とするかを切換えることにより、従来あったように一定値が連続する部分のみランレングス符号化を行うのではなく、電力量や温度などのセンサデータにて一定の割合で増減する場合などにもランレングス符号を適応的に付加可能とすることで圧縮率を高めることができる。
【００３９】
また、従来例ではランレングスモードに切換えるために複数の過去のデータの履歴を符号化時および復号時に常に照合する必要があり計算量が多くなるという課題があったが、本実施の形態によれば符号化時、復号時共に予測誤差の判定のみ行うことでランレングス符号の有無を判断できるため、計算量を削減して高速化を実現できる。
【００４０】
符号出力部１５１は、出力符号切換え部１４２にて選択された可変ビット数を持つ符号を処理単位（例えば３２ビット）に詰め込み、出力データとして出力する。
これまでに述べた符号化方法によれば、符号を１ビット単位で順に見ていくことにより復号可能であるため、詰め込みは処理単位のレジスタに対してＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）からＬＳＢに向かってビット単位で符号を隙間なく詰めていくのみであり、符号の境目やランレングス符号の有無を示すビットなどは不要である。
これらの処理はシフト処理とＯＲ処理により実現可能である。
符号は複数の処理単位にまたがってもよく、その場合には一つ前の処理単位のＬＳＢにその次の処理単位のＭＳＢが繋がるようにすればよい。
最終的には処理単位に詰め込まれた出力データ、出力データの処理単位の数、および出力データに含まれる符号数が出力される。
【００４１】
符号出力部１５１は、予測誤差符号Ｃｅを出力とする場合には、１入力データの入力毎に１符号を出力することも可能であるが、より好ましい例としては、ランレングスＲの符号化時に出力するように構成する。
すなわち、ランレングスＲの符号化時に、結合符号Ｃｅｒが出力符号として選択される場合には結合符号Ｃｅｒを出力し、予測誤差符号Ｃｅが出力符号として選択される場合には、予測誤差符号ＣｅをＲ回出力する。
そのとき、出現頻度の高い符号については、ｋ個をまとめて出力する。
前述のように予測誤差やランレングスは０や絶対値の小さい値の出現頻度が高くなるため、Ｅ＝０、１、−１などの頻度が高い。
例えば、Ｅ＝０、Ｒ＝４の場合、Ｃｅ＝１（２進）であるから、出力符号Ｃ＝１１１１（２進）とすることで、１回の処理単位への詰め込み処理で４回分の出力が可能となる。
詰め込み処理はビット操作により実現されるため、符号長が短く頻度が高い場合にはＣＰＵによる計算量が増えるという課題があったが、上記のようにすることで計算量を削減することができ、高速化が実現できる。
【００４２】
以上の説明では可変長符号化方法としてガンマ符号あるいはデルタ符号としたが、その他の整数の符号化方式であるアルファ符号、オメガ符号、ゴロム符号、ライス符号であってもよい。
また、算術符号、Ｒａｎｇｅ  Ｃｏｄｅｒ、ハフマン符号、シャノン符号や、その他の固定テーブルを用いた符号化方法などであってもよい。
【００４３】
次に、データ圧縮装置１００の動作について説明する。
【００４４】
図２は、本実施の形態に係るデータ圧縮装置１００の圧縮処理の流れの一例を示すフローチャートである。
【００４５】
圧縮工程Ｓ１０１において、予測誤差算出部１１１が、入力データと過去の履歴データを用いて予測誤差Ｅｃを算出する。
次に、圧縮工程Ｓ１０２にて、予測誤差符号化部１１２が、ガンマ符号またはデルタ符号により、予測誤差Ｅｃの予測誤差符号Ｃｅを生成する。なお、予測誤差符号化部１１２は、今回生成した予測誤差符号Ｃｅは次回の予測誤差符号の生成までバッファに滞留させておき、次回の予測誤差符号の生成時にバッファ内の予測誤差符号Ｃｅを出力符号切換え部１４２及び符号結合部１３１に出力する。
また、圧縮工程Ｓ１０３にて、ランレングス計数部１２１が、予測誤差Ｅｃが前回の予測誤差Ｅｐと一致するか判定し、一致した場合には圧縮工程Ｓ１０４にて、ランレングス計数部１２１が、ランレングスＲに１を加算する。
そして、圧縮工程Ｓ１０９にて、入力データが終了したかどうかの判定が行われ、入力データが終了していない場合には、圧縮工程Ｓ１０１に戻る。
入力データが終了している場合は、圧縮工程Ｓ１０９において、ランレングス計数部１２１で計数されたランレングスＲに対してランレングス符号化部１２２でランレングス符号Ｃｒが生成され、符号結合部１３１で予測誤差符号Ｃｅとランレングス符号Ｃｒが結合されて、結合符号Ｃｅｒが生成され、その後、圧縮工程が終了する。
【００４６】
一方、圧縮工程Ｓ１０３において、予測誤差Ｅｃが前回の予測誤差Ｅｐと一致しない場合には、圧縮工程Ｓ１０５にて、ランレングス計数部１２１がランレングスＲをランレングス符号化部１２２に出力し、ランレングス符号化部１２２が、ガンマ符号またはデルタ符号によりランレングス符号Ｃｒを生成する。
また、圧縮工程Ｓ１０６において、ランレングス計数部１２１は、ランレングスを１にリセットする。
次に、圧縮工程Ｓ１０７において、符号結合部１３１が、予測誤差符号化部１１２による予測誤差符号Ｃｅとランレングス符号化部１２２によるランレングス符号Ｃｒを結合して、結合符号Ｃｅｒを生成する。
ランレングス符号Ｃｒと結合する予測誤差符号は予測誤差符号化部１１２のバッファに滞留していた１つ前の入力データについての予測誤差符号Ｃｅである。
そして、圧縮工程Ｓ１０８にて、入力データが終了したかどうかの判定が行われ、入力データが終了していない場合には、圧縮工程Ｓ１０１に戻り、入力データが終了している場合は、圧縮工程が終了する。
【００４７】
なお、圧縮工程Ｓ１０２と、圧縮工程Ｓ１０３及びＳ１０４又は圧縮工程Ｓ１０３、Ｓ１０５及びＳ１０６は並行して実施することができる。
【００４８】
図３は、本実施の形態に係るデータ圧縮装置１００の符号出力の流れの一例を示すフローチャートである。
【００４９】
符号出力工程Ｓ２０１において、予測誤差判定部１４１が、図２の圧縮工程Ｓ１０１で予測誤差算出部１１１により算出された予測誤差Ｅｃを入力する。
次に、符号出力工程Ｓ２０２にて、予測誤差判定部１４１が、予測誤差Ｅｃが特定の値（例えば、０）であるかどうかの判定を行う。
予測誤差Ｅｃが特定の値である場合には、符号出力工程Ｓ２０３において、予測誤差判定部１４１は、出力符号として結合符号Ｃｅｒを選択し、出力符号切換え部１４２を操作して、結合符号Ｃｅｒを出力させるようにする。
この結果、図２の圧縮工程Ｓ１０７で結合符号Ｃｅｒが生成されると、結合符号Ｃｅｒが符号出力部１５１に出力される。
一方、符号出力工程Ｓ２０２において予測誤差Ｅｃが特定の値でない場合は、符号出力工程Ｓ２０４において、予測誤差判定部１４１は、出力符号として予測誤差符号Ｃｅを選択し、出力符号切換え部１４２を操作して、予測誤差符号Ｃｅを出力させるようにする。
この結果、図２の圧縮工程Ｓ１０２で生成された予測誤差符号Ｃｅが符号出力部１５１に出力される。
【００５０】
次に、図８に示す具体的なデータ値を用いて、本実施の形態に係るデータ圧縮装置１００の動作例を説明する。
図８の例では、予測値を１つ前の入力データの値としている。
【００５１】
図８では、ｎ回目に入力された入力データのデータ値が８であるとする。
また、ｎ回目の入力データの予測誤差Ｅを算出すると１となり、これにより、ｎ回目のデータ入力時点では予測誤差Ｅ＝１のランレングスＲは１となる。この時点では、予測誤差Ｅ＝１のランレングスＲはまだ確定していない。
予測誤差符号化部１１２は、予測誤差符号Ｃｅ（＝１）を生成し、予測誤差符号化部１１２内のバッファに滞留させておく、
また、予測誤差判定部１４１により、予測誤差Ｅ＝１が特定の値に一致するかどうかが判定される（図３の符号出力工程Ｓ２０２）。
特定の値を０としている場合（Ｅ＝０）は、予測誤差Ｅ＝１は特定の値でないため、予測誤差判定部１４１により予測誤差符号Ｃｅ（＝１）が出力符号として選択され、次回（ｎ＋１回目）においてバッファ内の予測誤差符号Ｃｅ（＝１）が出力符号として出力される。
一方、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）は、予測誤差Ｅ＝１は特定の値であるため、予測誤差判定部１４１により結合符号Ｃｅｒが出力符号として選択され、次回（ｎ＋１回目）以降に結合符号Ｃｅｒが出力符号として出力される。結合符号Ｃｅｒは、この時点では、まだ生成されていない。
【００５２】
ｎ＋１回目では、データ値が１０の入力データを入力する。
ｎ＋１回目における予測誤差Ｅは２（１０−８＝２）であり、ｎ回目の予測誤差Ｅ＝１と異なるため、予測誤差Ｅ＝１のランレングスＲは１で確定する。
予測誤差符号化部１１２は、予測誤差符号Ｃｅ（＝２）を生成し、予測誤差符号化部１１２内のバッファに滞留させておく。
また、予測誤差判定部１４１により、予測誤差Ｅ＝２が特定の値に一致するかどうかが判定される（図３の符号出力工程Ｓ２０２）。
特定の値を０としている場合（Ｅ＝０）は、予測誤差Ｅ＝２は特定の値でないため、予測誤差符号化部１１２により予測誤差符号Ｃｅ（＝２）が出力符号として選択され、次回（ｎ＋２回目）においてバッファ内の予測誤差符号Ｃｅ（＝２）が出力符号として出力される。
また、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）も、予測誤差Ｅ＝２は特定の値でないため、予測誤差符号化部１１２により予測誤差符号Ｃｅ（＝２）が出力符号として選択され、次回（ｎ＋２回目）においてバッファ内の予測誤差符号Ｃｅ（＝２）が出力符号として出力される。
予測誤差Ｅ＝１のランレングスＲが１で確定したため、ランレングス計数部１２１からランレングス符号化部１２２にランレングスＲ＝１が出力され、ランレングス符号Ｃｒが生成される。
更に、予測誤差符号化部１１２内のバッファから前回の予測誤差符号Ｃｅ（＝１）が出力され、符号結合部１３１において、ランレングス符号Ｃｒ（＝１）と結合されて、結合符号Ｃｅｒ（＝（１＋１））が生成される。
一方、新たな予測誤差Ｅ＝２のランレングスＲが１となる。新たな予測誤差Ｅ＝２のランレングスＲは、この時点では、まだ確定していない。
特定の値が０の場合（Ｅ＝０）は、ｎ回目の予測誤差Ｅ＝１に対する予測誤差判定部１４１の判定（符号出力工程Ｓ２０２）の結果、出力符号として予測誤差符号Ｃｅ（＝１）が選択されており、予測誤差符号Ｃｅ（＝１）が出力符号として出力される。
一方、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）は、ｎ回目の予測誤差Ｅ＝１に対する予測誤差判定部１４１の判定（符号出力工程Ｓ２０２）の結果、出力符号として結合符号Ｃｅｒが選択されており、ｎ＋１回目において生成された結合符号Ｃｅｒ（＝（１＋１））が出力符号として出力される。
【００５３】
ｎ＋２回目では、データ値が１０の入力データを入力する。
ｎ＋２回目における予測誤差Ｅは０（１０−１０＝０）であり、ｎ＋１回目の予測誤差Ｅ＝２と異なるため、予測誤差Ｅ＝２のランレングスＲは１で確定する。
予測誤差符号化部１１２は、予測誤差符号Ｃｅ（＝０）を生成し、予測誤差符号化部１１２内のバッファに滞留させておく。
また、予測誤差判定部１４１により、予測誤差Ｅ＝０が特定の値に一致するかどうかが判定される（図３の符号出力工程Ｓ２０２）。
特定の値を０としている場合（Ｅ＝０）は、予測誤差Ｅ＝０は特定の値であるため、予測誤差判定部１４１により結合符号Ｃｅｒが出力符号として選択され、次回（ｎ＋３回目）以降に結合符号Ｃｅｒが出力符号として出力される。結合符号Ｃｅｒは、この時点では、まだ生成されていない。
一方、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）は、予測誤差Ｅ＝０は特定の値でないため、予測誤差符号化部１１２により予測誤差符号Ｃｅ（＝０）が出力符号として選択され、次回（ｎ＋３回目）においてバッファ内の予測誤差符号Ｃｅ（＝０）が出力符号として出力される。
予測誤差Ｅ＝２のランレングスＲが１で確定したため、ランレングス計数部１２１からランレングス符号化部１２２にランレングスＲ＝１が出力され、ランレングス符号Ｃｒが生成される。
更に、予測誤差符号化部１１２内のバッファから前回の予測誤差符号Ｃｅ（＝２）が出力され、符号結合部１３１において、ランレングス符号Ｃｒ（＝１）と結合されて、結合符号Ｃｅｒ（＝（２＋１））が生成される。
一方、新たな予測誤差Ｅ＝０のランレングスＲが１となる。新たな予測誤差Ｅ＝０のランレングスＲは、この時点では、まだ確定していない。
特定の値が０の場合（Ｅ＝０）は、ｎ＋１回目の予測誤差Ｅ＝２に対する予測誤差判定部１４１の判定（符号出力工程Ｓ２０２）の結果、出力符号として予測誤差符号Ｃｅ（＝２）が選択されており、ｎ＋１回目に生成された予測誤差符号Ｃｅ（＝２）が出力符号として出力される。
また、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）も、ｎ＋１回目の予測誤差Ｅ＝２に対する予測誤差判定部１４１の判定（符号出力工程Ｓ２０２）の結果、出力符号として予測誤差符号Ｃｅ（＝２）が選択されており、ｎ＋１回目に生成された予測誤差符号Ｃｅ（＝２）が出力符号として出力される。
【００５４】
ｎ＋３回目では、データ値が１０の入力データを入力する。
ｎ＋３回目における予測誤差Ｅは０（１０−１０＝０）であり、ｎ＋２回目の予測誤差Ｅ＝０と同じであるため、予測誤差Ｅ＝０のランレングスＲは２になる。この時点では、予測誤差Ｅ＝０のランレングスＲはまだ確定していない。
予測誤差符号化部１１２は、予測誤差符号Ｃｅ（＝０）を生成し、予測誤差符号化部１１２内のバッファに滞留させておく。
また、予測誤差判定部１４１により、予測誤差Ｅ＝０が特定の値に一致するかどうかが判定される（図３の符号出力工程Ｓ２０２）。
特定の値を０としている場合（Ｅ＝０）は、予測誤差Ｅ＝０は特定の値であるため、予測誤差判定部１４１により結合符号Ｃｅｒが出力符号として選択され、次回（ｎ＋４回目）以降に結合符号Ｃｅｒが出力符号として出力される。結合符号Ｃｅｒは、この時点では、まだ生成されていない。
一方、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）は、予測誤差Ｅ＝０は特定の値でないため、予測誤差符号化部１１２により予測誤差符号Ｃｅ（＝０）が出力符号として選択され、次回（ｎ＋４回目）においてバッファ内の予測誤差符号Ｃｅ（＝０）が出力符号として出力される。
予測誤差Ｅ＝０のランレングスＲが未確定のため、ランレングス計数部１２１からランレングスＲは出力されず、ランレングス符号Ｃｒも生成されない。
この結果、結合符号Ｃｅｒも生成されない。
特定の値が０の場合（Ｅ＝０）は、ｎ＋２回目の予測誤差Ｅ＝０に対する予測誤差判定部１４１の判定（符号出力工程Ｓ２０２）の結果、出力符号として結合符号Ｃｅｒが選択されているが、結合符号Ｃｅｒは、この時点では、まだ生成されていないので、符号は出力されない。
一方、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）は、ｎ＋２回目の予測誤差Ｅ＝０に対する予測誤差判定部１４１の判定（符号出力工程Ｓ２０２）の結果、出力符号として予測誤差符号Ｃｅ（＝０）が選択されており、ｎ＋２回目に生成された予測誤差符号Ｃｅ（＝０）が出力符号として出力される。
【００５５】
ｎ＋４回目では、データ値が１１の入力データを入力する。
ｎ＋４回目における予測誤差Ｅは１（１１−１０＝１）であり、ｎ＋３回目の予測誤差Ｅ＝０と異なるため、予測誤差Ｅ＝０のランレングスＲは２で確定する。
予測誤差符号化部１１２は、予測誤差符号Ｃｅ（＝１）を生成し、予測誤差符号化部１１２内のバッファに滞留させておく。
また、予測誤差判定部１４１により、予測誤差Ｅ＝１が特定の値に一致するかどうかが判定される（図３の符号出力工程Ｓ２０２）。
特定の値を０としている場合（Ｅ＝０）は、予測誤差Ｅ＝１は特定の値でないため、予測誤差判定部１４１により予測誤差符号Ｃｅ（＝１）が出力符号として選択され、次回（ｎ＋５回目）においてバッファ内の予測誤差符号Ｃｅ（＝１）が出力符号として出力される。
一方、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）は、予測誤差Ｅ＝１は特定の値であるため、予測誤差判定部１４１により結合符号Ｃｅｒが出力符号として選択され、次回（ｎ＋５回目）以降に結合符号Ｃｅｒが出力符号として出力される。結合符号Ｃｅｒは、この時点では、まだ生成されていない。
予測誤差Ｅ＝０のランレングスＲが２で確定したため、ランレングス計数部１２１からランレングス符号化部１２２にランレングスＲ＝２が出力され、ランレングス符号Ｃｒが生成される。
更に、予測誤差符号化部１１２内のバッファから前回の予測誤差符号Ｃｅ（＝０）が出力され、符号結合部１３１において、ランレングス符号Ｃｒ（＝２）と結合されて、結合符号Ｃｅｒ（＝（０＋２））が生成される。
一方、新たな予測誤差Ｅ＝１のランレングスＲが１となる。新たな予測誤差Ｅ＝１のランレングスＲは、この時点では、まだ確定していない。
特定の値が０の場合（Ｅ＝０）は、ｎ＋３回目の予測誤差Ｅ＝０に対する予測誤差判定部１４１の判定（符号出力工程Ｓ２０２）の結果、出力符号として結合符号Ｃｅｒが選択されており、ｎ＋４回目において生成された結合符号Ｃｅｒ（＝（０＋２））が出力符号として出力される。
一方、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）は、ｎ＋３回目の予測誤差Ｅ＝０に対する予測誤差判定部１４１の判定（符号出力工程Ｓ２０２）の結果、出力符号として予測誤差符号Ｃｅ（＝０）が選択されており、ｎ＋３回目に生成された予測誤差符号Ｃｅ（＝０）が出力符号として出力される。
【００５６】
ｎ＋５回目では、データ値が１３の入力データを入力する。
ｎ＋５回目における予測誤差Ｅは２（１３−１１＝２）であり、ｎ＋４回目の予測誤差Ｅ＝１と異なるため、予測誤差Ｅ＝１のランレングスＲは１で確定する。
予測誤差符号化部１１２は、予測誤差符号Ｃｅ（＝２）を生成し、予測誤差符号化部１１２内のバッファに滞留させておく。
また、予測誤差判定部１４１により、予測誤差Ｅ＝２が特定の値に一致するかどうかが判定される（図３の符号出力工程Ｓ２０２）。
特定の値を０としている場合（Ｅ＝０）は、予測誤差Ｅ＝２は特定の値でないため、予測誤差符号化部１１２により予測誤差符号Ｃｅ（＝２）が出力符号として選択され、次回（ｎ＋６回目）においてバッファ内の予測誤差符号Ｃｅ（＝２）が出力符号として出力される。
また、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）も、予測誤差Ｅ＝２は特定の値でないため、予測誤差符号化部１１２により予測誤差符号Ｃｅ（＝２）が出力符号として選択され、次回（ｎ＋６回目）においてバッファ内の予測誤差符号Ｃｅ（＝２）が出力符号として出力される。
予測誤差Ｅ＝１のランレングスＲが１で確定したため、ランレングス計数部１２１からランレングス符号化部１２２にランレングスＲ＝１が出力され、ランレングス符号Ｃｒが生成される。
更に、予測誤差符号化部１１２内のバッファから前回の予測誤差符号Ｃｅ（＝１）が出力され、符号結合部１３１において、ランレングス符号Ｃｒ（＝１）と結合されて、結合符号Ｃｅｒ（＝（１＋１））が生成される。
一方、新たな予測誤差Ｅ＝２のランレングスＲが１となる。新たな予測誤差Ｅ＝２のランレングスＲは、この時点では、まだ確定していない。
特定の値が０の場合（Ｅ＝０）は、ｎ＋４回目の予測誤差Ｅ＝１に対する予測誤差判定部１４１の判定（符号出力工程Ｓ２０２）の結果、出力符号として予測誤差符号Ｃｅ（＝１）が選択されており、ｎ＋４回目において生成された予測誤差符号Ｃｅ（＝１）が出力符号として出力される。
一方、特定の値を＋１及び−１としている場合（｜Ｅ｜＝１）は、ｎ＋４回目の予測誤差Ｅ＝１に対する予測誤差判定部１４１の判定（符号出力工程Ｓ２０２）の結果、出力符号として結合符号Ｃｅｒが選択されており、ｎ＋５回目において生成された結合符号Ｃｅｒ（＝（１＋１））が出力符号として出力される。
【００５７】
このように、本実施の形態によれば、入力データに対して予測誤差を算出し、予測誤差のランレングスを計数するので、一定の傾きで増減するデータについても効率的にランレングス符号化を行うことができる。
また、本実施の形態では、予測誤差の値に応じて予測誤差符号及び結合符号のいずれかを出力符号として選択するため、データ値の変動特性に対応させて、結合符号が選択される予測誤差を適切に決定することにより、圧縮効率を高めることができる。
例えば、入力データ間でデータ値の変動があまりなく、予測誤差Ｅ＝０が連続する頻度が高い場合には、予測誤差Ｅ＝０のときに結合符号Ｃｅｒを出力符号とし、それ以外は予測誤差符号Ｃｅを出力符号とすることにより、圧縮率を高めることが可能である。
また、一定の割合で緩やかに増減するデータの場合は、予測誤差｜Ｅ｜＝１が連続する頻度が高いため、予測誤差｜Ｅ｜＝１のときに結合符号Ｃｅｒを出力符号とし、それ以外は予測誤差符号Ｃｅを出力符号とすることにより、圧縮率を高めることが可能である。
【００５８】
なお、上記の説明では、全ての予測誤差に対してランレングス計数部１２１でランレングスを計数しているが、特定の値の予測誤差に対してのみランレングスを計数するようにしてもよい。
つまり、予測誤差判定部１４１が、予測誤差算出部１１１により算出された予測誤差の値が特定の値（図３のＳ２０２で判断対象としている特定の値）である場合に、ランレングス計数部１２１に当該予測誤差のランレングスの計数の開始を指示する。
そして、ランレングス計数部１２１は、予測誤差算出部１１１より指示のあった予測誤差のランレングスの計数を開始する。
このようにすることで、ランレングス計数部１２１及びランレングス符号化部１２２の処理を効率化することができる。
【００５９】
図１０は、本実施の形態に係るデータ伸張装置３００の機能ブロックの構成の一例を示す図である。
【００６０】
データ伸張装置３００は、データ圧縮装置１００により圧縮された圧縮後データを順次入力し、伸張を行って、圧縮前の状態に復元したデータを出力する。データ圧縮装置１００により圧縮された圧縮後データは、データ圧縮装置１００の出力データ（符号化データ）、出力データの処理単位の数、および出力データに含まれる符号数を含む。さらに、データ圧縮装置１００の予測誤差判定部１４１にて使用された特定の値をエンコードしたデータを含んでもよい。その場合、圧縮後データは、出力データの処理単位の数、出力データに含まれる符号数、特定の値をエンコードしたデータを含むヘッダを有し、そのヘッダの直後から圧縮による出力データを有する構造とする。一方、特定の値については、圧縮後データに含めず、データ圧縮装置１００とデータ伸張装置３００で共通の値を固定的に持つか、共通の値を予め設定するとしても良い。
【００６１】
データ伸張装置３００は、予測誤差復号部３１１、データ復号部３１２、ランレングス復号部３２１、データ複製部３３１、復号予測誤差判定部３４１、出力データ切換え部３４２、データ入力部３５１を含む。
【００６２】
データ入力部３５１は、入力データを一定の処理単位（例えば３２ビットなど）ごとに入力し、処理単位内に含まれる符号を取り出す。符号が処理単位より小さい場合には一つの処理単位から複数の符号を順に取り出し、また、符号が処理単位より大きい場合や符号が複数の処理単位にまたがる場合には、順次入力データを入力して符号を取り出す。すなわち、データ圧縮装置１００における符号出力部１５１の逆の操作を行う。符号のビット長はガンマ符号、デルタ符号、その他の可変長符号化方法により、符号ビットをＭＳＢから順に見ていくことで一意に定まるため、このような符号の取り出しを行うことができる。
出力データに含まれる符号数をヘッダから予め入力し、取り出された符号の数を計数し、計数された符号数が出力データに含まれる符号数に一致したときに、それが最終データであることを知ることができ、データの入力を終了することができる。
また、出力データに含まれる処理単位の数をヘッダから予め入力し、符号化データの入力処理単位数を計数し、データの入力終了時にこれらの処理単位数が一致することを確認することで、データの整合性を確認することができる。
【００６３】
予測誤差復号部３１１は、データ入力部３５１により取り出された符号から予測誤差Ｅを復号しする。復号には、データ圧縮装置１００の予測誤差符号化部１１２に対応する復号方法を用いる。すなわち、予測誤差符号化部１１２がガンマ符号を用いるのであれば、予測誤差復号部３１１もガンマ符号を用いる。さらに、正の整数へのマッピングの逆変換を行うことにより、予測誤差Ｅを復号できる。
【００６４】
データ復号部３１２は、過去に復号されたデータの履歴を用いて現在のデータを予測した予測値と、予測誤差Ｅの差分を算出することにより元のデータを復号する。予測値の算出方法は予測誤差算出部１１１と同一とする。
【００６５】
復号予測誤差判定部３４１は、予測誤差Ｅの値により出力データ切換え部３４２を制御し、予測誤差符号Ｃｅと結合符号Ｃｅｒのいずれを復号したデータを対応する出力符号とするかを選択する。復号予測誤差判定部３４１は、予めヘッダから特定の値をエンコードしたものを入力し特定の値をデコードしておくか、固定の特定の値、あるいは設定された特定の値と予測誤差Ｅとを比較し、予測誤差Ｅが特定の値ではない場合には入力された符号はＣｅであると判断して、データ復号部３１２により復号されたデータを出力データとして出力データ切換え部３４２から出力させる。
【００６６】
予測誤差Ｅが特定の値である場合には、入力された符号は結合符号Ｃｅｒに含まれる予測誤差符号であると判断する。その場合、さらにランレングス復号部３２１がデータ入力部３５１により取り出された次の符号を入力し、ランレングスを復号する。復号には、データ圧縮装置１００のランレングス符号化部１２２に対応する復号方法を用いる。すなわち、ランレングス符号化部１２２がガンマ符号を用いるのであれば、ランレングス復号部３２１もガンマ符号を用いる。
【００６７】
予測誤差Ｅが特定の値である場合には、さらにデータ複製部３３１が、データ復号部３１２により復号されたデータをランレングス分繰返し出力することによりデータを複製する。そのとき、復号予測誤差判定部３４１は、出力データ切換え部３４２にデータ複製部３３１の出力を出力データとして出力させる。
【００６８】
次に、データ伸張装置３００の動作について説明する。
【００６９】
図１１は、本実施の形態に係るデータ伸張装置３００の伸張処理の流れの一例を示すフローチャートである。
【００７０】
伸張工程Ｓ６０１において、データ入力部３５１が、入力データを一定の処理単位ごとに入力し、処理単位内に含まれる符号を取り出す。データ入力部では入力した処理単位数と取り出された符号数を計数する。
次に、伸張工程Ｓ６０２にて予測誤差復号部３１１が、取り出された符号をガンマ符号またはデルタ符号またはその他の符号により復号し、予測誤差Ｅを生成する。
次に、伸張工程Ｓ６０３にてデータ復号部３１２が、予測誤差Ｅと過去に復号された履歴データを用いて現在のデータを復号する。
そして、伸張工程Ｓ６０４にて、復号予測誤差判定部３４１が、予測誤差Ｅが特定の値であるかどうかを判定する。
【００７１】
伸張工程Ｓ６０４において、予測誤差Ｅが特定の値に一致しない場合には、伸張工程Ｓ６０５にて復号予測誤差判定部３４１は出力データ切換え部３４２に復号された現在のデータを出力するよう選択させる。
【００７２】
一方、伸張工程Ｓ６０４において、次に、予測誤差Ｅが特定の値に一致した場合には、伸張工程Ｓ６０６にて、データ入力部３５１が次の符号を取り出す。データ入力部では入力した処理単位数と取り出された符号数を計数する。
次に、伸張工程Ｓ６０７にて、ランレングス復号部３２１が取り出された符号をガンマ符号またはデルタ符号またはその他の符号により復号し、ランレングスＲを生成する。
次に、伸張工程Ｓ６０８にて、データ複製部３３１が、データ復号部３１２により復号された現在のデータをランレングスＲ回分繰返し出力する。このとき、復号予測誤差判定部３４１は出力データ切換え部３４２にデータ複製部３３１の出力データを出力するよう選択させる。
【００７３】
そして、伸張工程Ｓ６０９において、データ入力部３５１が計数した符号数が圧縮後データのヘッダから入力した符号数に等しい場合にはデータの伸張を終了し、そうでない場合には伸張工程Ｓ６０１に戻る。
【００７４】
以上述べたように、復号された予測誤差の値によりその次の符号が次の予測誤差符号であるか、結合符号のランレングス符号であるかを判定することにより、本実施の形態による圧縮後データの伸張が可能である。
【００７５】
以上、本実施の形態では、
入力データ列を圧縮するデータ圧縮装置であって、
少なくとも１つ以上の入力データの履歴を用いて算出した予測値と、着目するデータとの差分である予測誤差を算出する手段と、
前記予測誤差を可変長符号により符号化して予測誤差符号を生成する手段と、
前記予測誤差のランレングスをカウントする手段と、
前記ランレングスを可変長符号により符号化してランレングス符号を生成する手段と、
前記予測誤差符号および前記ランレングス符号から出力符号を生成する手段とを含み、
前記出力符号を生成する手段は、前記予測誤差の値に応じて、予測誤差符号を出力符号とするか、予測誤差符号とランレングス符号を結合して出力符号とするかを選択するデータ圧縮装置を説明した。
【００７６】
また、本実施の形態では、
前記出力符号を生成する手段は、
前記予測誤差の絶対値が閾値より大きい場合には予測誤差符号を出力符号とし、
前記予測誤差の絶対値が閾値以下である場合には予測誤差符号とランレングス符号を結合して出力符号とすることを説明した。
【００７７】
また、本実施の形態では、
前記予測誤差を可変長符号により符号化して予測誤差符号を生成する手段は、
前記予測誤差を最も近い固定ビット数の整数に変換する手段と、
変換された整数値が前記固定ビット数で表される最小値である場合には、対応する固定ビット列を出力符号として符号化する手段と、
変換された整数値が前記最小値でない場合には、正の整数にマッピングし、可変長符号化する手段を含むことを説明した。
【００７８】
また、本実施の形態では、
前記可変長符号化する手段は、
アルファ符号またはガンマ符号またはデルタ符号またはオメガ符号またはゴロム符号により符号化することを説明した。
【００７９】
また、本実施の形態では、
前記ランレングスを可変長符号により符号化してランレングス符号を生成する手段は、
前記ランレングスをアルファ符号またはガンマ符号またはデルタ符号またはオメガ符号またはゴロム符号により符号化することを説明した。
【００８０】
また、本実施の形態では、
前記予測値は、着目するデータの直前のデータであることを説明した。
【００８１】
また、本実施の形態では、
前記予測値は、直前の少なくとも２つ以上のデータを用いた固定パラメータの線形演算であることを説明した。
【００８２】
実施の形態２．
図４は、本実施の形態に係るデータ圧縮装置２００の機能ブロックの構成の一例を示す図である。
データ圧縮装置２００は、圧縮前処理部１０１、圧縮処理部１０２、制御部１０３に大別される。
圧縮処理部１０２は、実施の形態１で説明したデータ圧縮装置１００と実質的に同じ構成であり、予測誤差判定部１４１が符号選択基準１４３を記憶している点が実施の形態１と異なる。
圧縮前処理部１０１は、先行予測誤差算出部２１１、先行ランレングス計数部２２１、符号長算出部１７１、１７２、１７３、符号長算出基準１８１、１８２、１８３、基準選択部１９１を有する。
圧縮前処理部１０１の内部構成の詳細は後述する。
【００８３】
本実施の形態に係るデータ圧縮装置２００は、入力データを２パス処理することにより、符号選択のための基準の最適化を行う。
制御部１０３は、圧縮処理のパス管理を行い、１パス目から入力データを圧縮前処理部１０１に入力させ、圧縮前処理部１０１に複数の基準に基づく圧縮後の符号長を算出させ、もっとも符号長が短い基準を選択させる。
圧縮前処理部１０１は、複数の符号選択基準のうち圧縮後の符号長が最も短い符号選択基準を選択するため、時間の経過により入力データの特性が変化する場合は、入力データの特性の変化に伴って、選択する符号選択基準が変化する場合がある。
なお、選択された基準に基づく圧縮後の符号長が目標とする圧縮ブロックサイズに満たない場合には、制御部１０３は、追加の入力データを圧縮前処理部１０１に入力して圧縮後の符号長を更新させる。
圧縮後の符号長が目標とする圧縮ブロックサイズを超えた場合には、制御部１０３は、２パス目として最後の入力データ追加の前までの入力データを圧縮処理部１０２に入力して圧縮処理を実行させる。
【００８４】
圧縮前処理部１０１について詳細に説明する。
圧縮前処理部１０１の先行予測誤差算出部２１１および先行ランレングス計数部２２１は、機能としては、実施の形態１で説明した予測誤差算出部１１１及びランレングス計数部１２１と同じであるが、以下の点が異なる。
本実施の形態では、先行予測誤差算出部２１１は、圧縮処理部１０２の予測誤差算出部１１１のデータ入力に先立ち、予測誤差算出部１１１が入力する予定のデータ（入力予定データともいう）を入力し、予測誤差算出部１１１と同じ方式によりデータ値を予測し、入力予定データごとに予測誤差を算出する。
先行ランレングス計数部２２１は、先行予測誤差算出部２１１により算出された予測誤差のランレングスを計数する。
【００８５】
符号長算出部１７１、１７２、１７３は予測誤差ＥおよびランレングスＲを可変長符号化したときの符号長を算出する。
図４の例では符号長算出部を３つ有する場合の例を示したが、符号長算出部の数は任意でよい。
【００８６】
符号長算出部１７１、１７２、１７３は、例えばガンマ符号化では、予測誤差Ｅを変換式Ｍ１またはＭ２で変換後に２進数で表したときのビット数Ｎｅに対して、符号長Ｇｅを以下のように算出することができる。
Ｇｅ＝２Ｎｅ−１
予測誤差ＥがＥ＝Ｅｍｉｎを満たす場合にはＧｅはＥｍｉｎに対応する符号の長さとすればよい。
また、符号長算出部１７１、１７２、１７３は、ランレングスＲを２進数で表したときのビット数Ｎｒに対して符号長Ｇｒを以下のように算出することができる。
Ｇｒ＝２Ｎｒ−１
また、符号長算出部１７１、１７２、１７３は、予測誤差ＥおよびランレングスＲとしたときの符号長Ｇは、以下のように算出することができる。
Ｇ＝Ｇｅ＋Ｇｒ  …予測誤差符号とランレングス符号の結合を出力符号とするとき
Ｇ＝Ｇｅ×Ｒ    …予測誤差符号のみを出力符号とするとき
【００８７】
ガンマ符号のような固定的な符号化方法を用いることにより、算術符号化やハフマン符号化などのエントロピー符号にて必要となるシンボル出現頻度テーブルの作成が不要となり、計算量を削減して高速な処理が可能となるのは実施の形態１にて説明した通りである。
更には、前述の通り、圧縮ブロックサイズを調整するために、入力データの追加処理により少しずつ入力データを増やして圧縮後の符号長を算出する場合、シンボル出現頻度テーブルを必要とする符号化方法では、テーブルの内容が変化するために、それまでに計算済みの符号長についても再計算が必要となるが、本実施の形態では固定的に符号長を算出できるため、追加したデータの符号長だけを計算すればよく、計算量を削減して高速化が可能である。
【００８８】
但し、本実施の形態で用いる符号化方式は、はガンマ符号あるいはデルタ符号でなくとも、その他の整数の符号化方式であるアルファ符号、オメガ符号、ゴロム符号、ライス符号であってもよい。
また、算術符号、Ｒａｎｇｅ  Ｃｏｄｅｒ、ハフマン符号、シャノン符号や、その他の固定テーブルを用いた符号化方法などであってもよい。
【００８９】
符号長算出部１７１、１７２、１７３は、符号長算出基準１８１、１８２、１８３に基づいて符号長の算出を行う。
例えば、符号長算出基準１８１を、
基準１＝ランレングス符号化なし（予測誤差の値に関わらず常に予測誤差符号の符号長を算出）
とすると、符号長算出部１７１は符号長Ｇ１を以下の式により算出する。
Ｇ１＝Ｇｅ×Ｒ
また、符号長算出基準１８２を、
基準２＝予測誤差Ｅが０の場合のみランレングス符号化あり
とすると、符号長算出部１７２は符号長Ｇ２を以下の式により算出する。
Ｇ２＝Ｇｅ＋Ｇｒ  …Ｅ＝０のとき
Ｇ２＝Ｇｅ×Ｒ    …Ｅ≠０のとき
さらに、符号長算出基準１８３を、
基準３＝予測誤差Ｅの絶対値が１以下の場合のみランレングス符号化あり
とすると、符号長算出部１７３は符号長Ｇ３を以下の式により算出する。
Ｇ３＝Ｇｅ＋Ｇｒ  …｜Ｅ｜≦１のとき
Ｇ３＝Ｇｅ×Ｒ    …｜Ｅ｜＞１のとき
以上、符号長算出部の算出例を示したが、ここに示した以外の基準を用いることが可能であることも当業者には明らかである。
【００９０】
符号長算出部は、入力予定データの全てについて符号長を合計し、合計符号長を算出する。
追加入力予定データの場合には、前回の合計符号長を入力あるいは内部保存し、追加入力予定データの符号長を加算する。
【００９１】
このように本実施の形態では、符号長算出部１７１、１７２、１７３の各々には、結合符号の符号長を算出する結合符号長算出値として所定の値が設定されている。
そして、符号長算出部１７１、１７２、１７３の各々は、先行予測誤差算出部２１１により算出された予測誤差の値が結合符号長算出値と一致する場合に当該予測誤差の値と先行ランレングス計数部２２１によるランレングスとに基づき結合符号の符号長を算出し、先行予測誤差算出部２１１により算出された予測誤差の値が結合符号長算出値に一致しない場合に当該予測誤差の値に基づき予測誤差符号の符号長を算出して、複数の入力予定データでの合計符号長を算出する。
つまり、符号長算出部１７２には結合符号長算出値として予測誤差Ｅ＝０が設定されており、予測誤差Ｅ＝０のときに結合符号の符号長を算出し、予測誤差Ｅ＝０以外のときは予測誤差符号の符号長を算出する。そして、符号長算出部１７２は、算出した結合符号の符号長及び予測誤差符号の符号長の合計符号長を算出する。
また、符号長算出部１７３には結合符号長算出値として予測誤差｜Ｅ｜≦１が設定されており、予測誤差｜Ｅ｜≦１のときに結合符号の符号長を算出し、予測誤差｜Ｅ｜＞１のときは予測誤差符号の符号長を算出する。そして、符号長算出部１７２は、算出した結合符号の符号長及び予測誤差符号の符号長の合計符号長を算出する。
また、符号長算出部１７３は、特例符号長算出部として機能し、結合符号長算出値が設定されておらず、先行予測誤差算出部２１１により算出された予測誤差に対して予測誤差符号の符号長のみを算出して、複数の入力予定データでの合計符号長を算出する。
【００９２】
基準選択部１９１は、それぞれの符号長算出部で算出した合計符号長を比較し、最も符号長が小さくなる符号長算出基準を選択して、符号長算出基準を示す基準コードと合計符号長を出力する。
つまり、基準選択部１９１は、最小の合計符号長という条件を満たす符号長算出部の結合符号長算出値（Ｅ＝０、｜Ｅ｜≦１等）を符号長算出基準として選定し、符号長算出基準として選定した値の予測誤差に対する出力符号として結合符号を選択するよう予測誤差判定部１４１（符号選択部）に指示する。
基準選択部１９１は、選定指示部の例である。
そして、基準選択部１９１により選定された符号長算出基準を示す基準コードは制御部１０３により２パス目の入力データと共に圧縮処理部１０２に入力され、予測誤差判定部１４１で基準コードがデコードされ、予測誤差判定部１４１が選択された符号長算出基準を符号選択基準１４３として保持する。
そして、予測誤差判定部１４１は、符号選択基準１４３に基づき、対象となる予測誤差に対しては結合符号を選択してデータ圧縮を実行する。
基準コードを前述の出力データの処理単位の数、および出力データに含まれる符号数などと共に圧縮ブロックのヘッダとして保存することにより、伸張時に同じ基準を用いて復号することが可能である。
【００９３】
以上述べたように、本実施の形態によれば、予測誤差に応じて予測誤差符号とランレングス符号を適応的に組合せる方法において、組合せの際の基準を入力データに応じて圧縮ブロック単位で最適化することができ、圧縮効率をさらに上げることができる。
【００９４】
次に、データ圧縮装置２００の動作について説明する。
【００９５】
図５は、本実施の形態に係るデータ圧縮装置２００の圧縮処理の流れの一例を示すフローチャートである。
圧縮工程Ｓ３０１において、制御部１０３が、一定のサイズの入力予定データについて圧縮パス１を実行し、圧縮工程Ｓ３０２にて合計符号長がブロックサイズ未満である場合、入力予定データを追加してＳ３０１の圧縮パス１を再実行する。
合計符号長がブロックサイズ以上である場合には、制御部１０３は、圧縮工程Ｓ３０３にて合計符号長がブロックサイズ以下となる入力データサイズを決定し、圧縮工程Ｓ３０４にて圧縮パス２を実行する。
【００９６】
図６は、本実施の形態に係るデータ圧縮装置２００の圧縮パス１処理の流れの一例を示すフローチャートである。
圧縮パス１工程Ｓ４０１において、先行予測誤差算出部２１１が、入力データと過去の履歴データを用いて予測誤差Ｅｃを算出する。
圧縮パス１工程Ｓ４０２にて、先行予測誤差算出部２１１が、予測誤差Ｅｃが前回の予測誤差Ｅｐと一致するか判定し、一致した場合には、先行ランレングス計数部２２１が、圧縮パス１工程Ｓ４０３にてランレングスＲに１を加算する。
一致しない場合には、圧縮パス１工程Ｓ４０４にて、各符号長算出部は、予測誤差ＥｐとランレングスＲを元に符号長加算を行い、圧縮パス１工程Ｓ４０５にて、先行ランレングス計数部２２１が、ランレングスを１にリセットする。
圧縮パス１工程Ｓ４０６にて入力データが終了したかどうかを判定し、終了していない場合には圧縮パス１工程Ｓ４０１に戻る。
終了した場合は圧縮パス１工程Ｓ４０７にて、各符号長算出部は、予測誤差ＥｃとランレングスＲを元に最後の符号長加算を行う。
圧縮パス１工程Ｓ４０８にて、基準選択部１９１が、符号長算出基準ごとに算出した合計符号長を比較し、合計符号長が最小である符号長算出基準を選択して基準コードと合計符号長を出力する。
【００９７】
図７は、本実施の形態に係るデータ圧縮装置２００の符号長加算処理の流れの一例を示すフローチャートである。
符号長加算工程Ｓ５０１において、各符号長算出部は、予測誤差の符号長を算出し、符号長加算工程Ｓ５０２において、ランレングスの符号長を算出し、符号長加算工程Ｓ５０３において、それぞれの符号長算出基準ごとに符号長を算出して、合計符号長にそれぞれ加算する。
【００９８】
本実施の形態に係るデータ圧縮装置２００の圧縮パス２処理については、図３のＳ２０２において予測誤差が特定値かどうかの判定を圧縮パス１処理にて選択された基準に基づいて実行する以外は、図２、図３に示した通りである。
【００９９】
このように、本実施の形態では、入力データの特性に応じて、圧縮ブロック単位で最適な符号長算出基準を選択することができ、圧縮効率をさらに上げることができる。
【０１００】
以上、本実施の形態では、
データ圧縮装置は、さらに、
予測誤差符号の符号長を算出する手段と、
ランレングス符号の符号長を算出する手段と、
予測誤差の値に応じた複数の基準に基づき、予測誤差符号の符号長または、予測誤差符号とランレングス符号を結合した符号の符号長から選択して、複数の基準にそれぞれ対応した複数の出力符号列の符号長を算出する手段と、
入力データブロックに対して複数の出力符号列の符号長を算出して、符号長が最小となる基準を該入力データブロックの基準として選択する手段と、
入力データブロックに入力データが追加されたときに、追加された入力データの複数の符号長を算出して追加前に算出された符号長に加算し、符号長が最小となる基準を再選択する手段と、
選択された基準にて該入力データブロックの出力符号列を生成する手段、
を含むことを説明した。
【０１０１】
また、本実施の形態では、
前記複数の基準は、
前記予測誤差によらず予測誤差符号を出力符号とする基準、
前記予測誤差が０の場合に予測誤差符号とランレングス符号を結合して出力符号とし、それ以外は予測誤差符号を出力符号とする基準、
前記予測誤差の絶対値が１以下の場合に予測誤差符号とランレングス符号を結合して出力符号とし、それ以外は予測誤差符号を出力符号とする基準、
のいずれか１つ以上を含むことを説明した。
【０１０２】
最後に、実施の形態１及び２に示したデータ圧縮装置１００、２００のハードウェア構成例について説明する。
図９は、実施の形態１及び２に示すデータ圧縮装置１００、２００のハードウェア資源の一例を示す図である。
なお、図９の構成は、あくまでもデータ圧縮装置１００、２００のハードウェア構成の一例を示すものであり、データ圧縮装置１００、２００のハードウェア構成は図９に記載の構成に限らず、他の構成であってもよい。
【０１０３】
図９において、データ圧縮装置１００、２００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。
ＣＰＵ９１１は、バス９１２を介して、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）９１３、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９１４、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。
更に、ＣＰＵ９１１は、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６、スキャナ装置９０７と接続していてもよい。また、磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカード（登録商標）読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。
通信ボード９１５、キーボード９０２、マウス９０３、スキャナ装置９０７、ＦＤＤ９０４などは、入力装置の一例である。
また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力装置の一例である。
【０１０４】
通信ボード９１５は、例えば、ＬＡＮ（ローカルエリアネットワーク）、インターネット、ＷＡＮ（ワイドエリアネットワーク）、ＳＡＮ（ストレージエリアネットワーク）などに接続されている。
【０１０５】
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。
プログラム群９２３のプログラムは、ＣＰＵ９１１がオペレーティングシステム９２１、ウィンドウシステム９２２を利用しながら実行する。
【０１０６】
また、ＲＡＭ９１４には、ＣＰＵ９１１に実行させるオペレーティングシステム９２１のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。
また、ＲＡＭ９１４には、ＣＰＵ９１１による処理に必要な各種データが格納される。
【０１０７】
また、ＲＯＭ９１３には、ＢＩＯＳ（Ｂａｓｉｃ  Ｉｎｐｕｔ  Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）プログラムが格納され、磁気ディスク装置９２０にはブートプログラムが格納されている。
データ圧縮装置１００、２００の起動時には、ＲＯＭ９１３のＢＩＯＳプログラム及び磁気ディスク装置９２０のブートプログラムが実行され、ＢＩＯＳプログラム及びブートプログラムによりオペレーティングシステム９２１が起動される。
【０１０８】
上記プログラム群９２３には、実施の形態１及び２の説明において「〜部」、「〜手段」として説明している機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
【０１０９】
ファイル群９２４には、実施の形態１及び２の説明において、「〜の判断」、「〜の判定」、「〜の符号化」、「〜の生成」、「〜の計数」、「〜の比較」、「〜の評価」、「〜の設定」、「〜の選択」、「〜の選定」等として説明している処理の結果を示す情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。
「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示などのＣＰＵの動作に用いられる。
抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。
また、実施の形態１及び２で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ等の記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【０１１０】
また、実施の形態１及び２の説明において「〜部」、「〜手段」として説明しているものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。
すなわち、実施の形態１及び２で説明したフローチャートに示すステップ、手順、処理により、本発明に係る「データ圧縮方法」を実現することができる。
また、「〜部」、「〜手段」として説明しているものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、実施の形態１及び２の「〜部」、「〜手段」としてコンピュータを機能させるものである。あるいは、実施の形態１及び２の「〜部」、「〜手段」の手順や方法をコンピュータに実行させるものである。
【０１１１】
このように、実施の形態１及び２に示すデータ圧縮装置１００、２００は、処理装置たるＣＰＵ、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータであり、上記したように「〜部」、「〜手段」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。
【符号の説明】
【０１１２】
１００  データ圧縮装置、１０１  圧縮前処理部、１０２  圧縮処理部、１０３  制御部、１１１  予測誤差算出部、１１２  予測誤差符号化部、１２１  ランレングス計数部、１２２  ランレングス符号化部、１３１  符号結合部、１４１  予測誤差判定部、１４２  出力符号切換え部、１４３  符号選択基準、１５１  符号出力部、１７１  符号長算出部、１７２  符号長算出部、１７３  符号長算出部、１８１  符号長算出基準、１８２  符号長算出基準、１８３  符号長算出基準、１９１  基準選択部、２００  データ圧縮装置、２１１  先行予測誤差算出部、２２１  先行ランレングス計数部、３００  データ伸張装置、３１１  予測誤差復号部、３１２  データ復号部、３２１  ランレングス復号部、３３１  データ複製部、３４１  復号予測誤差判定部、３４２  出力データ切換え部、３５１  データ入力部。
【図１】
2011108089.tif 000009
【図２】
2011108089.tif 000010
【図３】
2011108089.tif 000011
【図４】
2011108089.tif 000012
【図５】
2011108089.tif 000013
【図６】
2011108089.tif 000014
【図７】
2011108089.tif 000015
【図８】
2011108089.tif 000016
【図９】
2011108089.tif 000017
【図１０】
2011108089.tif 000018
【図１１】
2011108089.tif 000019
【手続補正書】
【提出日】平成24年4月11日(2012.4.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データを順次入力するデータ圧縮装置であって、
データの入力前にデータの値を予測し、データを入力する度に、入力した入力データの値と当該入力データに対して予測した予測値との差を予測誤差として算出する予測誤差算出部と、
前記予測誤差算出部により予測誤差が算出される度に、算出された予測誤差の値を符号化して予測誤差符号を生成する予測誤差符号化部と、
前記予測誤差算出部により算出された予測誤差のランレングスを計数するランレングス計数部と、
予測誤差の値が変化した際に、前記ランレングス計数部により計数されたランレングスを符号化してランレングス符号を生成するランレングス符号化部と、
前記ランレングス符号化部によりランレングス符号が生成される度に、生成されたランレングス符号を当該ランレングス符号に対応する予測誤差の予測誤差符号に結合して結合符号を生成する符号結合部と、
前記予測誤差算出部により算出された予測誤差の値に応じて、当該予測誤差に対する予測誤差符号及び結合符号のいずれかを出力符号として選択する符号選択部と、
前記予測誤差算出部のデータ入力に先立ち、前記予測誤差算出部が入力することになる複数の入力予定データに対して特定の値を選定し、選定した値の予測誤差に対する出力符号として結合符号を選択するよう前記符号選択部に指示する選定指示部を有し、
前記符号選択部は、
前記予測誤差算出部により算出された予測誤差の値が前記選定指示部から指示された値である場合に出力符号として当該予測誤差に対する結合符号を選択し、前記予測誤差算出部により算出された予測誤差の値が他の値である場合に出力符号として当該予測誤差に対する予測誤差符号を選択することを特徴とするデータ圧縮装置。
【請求項２】
前記符号選択部は、
前記予測誤差算出部により算出された予測誤差の値が前記選定指示部から指示された値である場合に、前記ランレングス計数部に当該予測誤差のランレングスの計数の開始を指示し、
前記ランレングス計数部は、
前記符号選択部により指示のあった予測誤差のランレングスの計数を開始することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項３】
前記データ圧縮装置は、更に、
前記予測誤差算出部のデータ入力に先立ち、入力予定データごとに前記予測誤差算出部の予測方式と同じ方式によりデータ値を予測し、入力予定データごとに予測誤差を算出する先行予測誤差算出部と、
前記先行予測誤差算出部により算出された予測誤差のランレングスを計数する先行ランレングス計数部と、
結合符号の符号長を算出する結合符号長算出値として所定の値が設定されており、前記先行予測誤差算出部により算出された予測誤差の値が前記結合符号長算出値と一致する場合に当該予測誤差の値と前記先行ランレングス計数部によるランレングスとに基づき結合符号の符号長を算出し、前記先行予測誤差算出部により算出された予測誤差の値が前記結合符号長算出値に一致しない場合に当該予測誤差の値に基づき予測誤差符号の符号長を算出して、前記複数の入力予定データでの合計符号長を算出する符号長算出部とを有し、
前記選定指示部は、
前記符号長算出部により算出された合計符号長が所定の条件を満たす場合に、前記結合符号長算出値を前記符号選択部において結合符号を選択させる値として選定することを特徴とする請求項１又は２に記載のデータ圧縮装置。
【請求項４】
前記データ圧縮装置は、
結合符号長算出値としてそれぞれに異なる値が設定されており、それぞれの結合符号長算出値に基づいて予測誤差ごとに結合符号の符号長及び予測誤差符号の符号長のいずれかを算出して、前記複数の入力予定データでの合計符号長を算出する複数の符号長算出部を有し、
前記選定指示部は、
最小の合計符号長の符号長算出部の結合符号長算出値を前記符号選択部において結合符号を選択させる値として選定することを特徴とする請求項３に記載のデータ圧縮装置。
【請求項５】
前記データ圧縮装置は、更に、
結合符号長算出値として値０が設定されており、前記先行予測誤差算出部により算出された予測誤差の値が０である場合に結合符号の符号長を算出し、前記先行予測誤差算出部により算出された予測誤差の値が０でない場合に予測誤差符号の符号長を算出する符号長算出部と、
結合符号長算出値として絶対値１以下が設定されており、前記先行予測誤差算出部により算出された予測誤差の絶対値が１以下である場合に結合符号の符号長を算出し、前記先行予測誤差算出部により算出された予測誤差の絶対値が１以下でない場合に予測誤差符号の符号長を算出する符号長算出部との少なくともいずれかを有することを特徴とする請求項４に記載のデータ圧縮装置。
【請求項６】
前記データ圧縮装置は、
結合符号長算出値が設定されておらず、前記先行予測誤差算出部により算出された予測誤差に対して予測誤差符号の符号長のみを算出して、前記複数の入力予定データでの合計符号長を算出する特例符号長算出部を有し、
前記選定指示部は、
前記符号長算出部により算出された合計符号長が前記特例符号長算出部により算出された合計符号長よりも小さい場合に、前記符号長算出部の結合符号長算出値を前記符号選択部において結合符号を選択させる値として選定し、
前記符号長算出部により算出された合計符号長が前記特例符号長算出部により算出された合計符号長以上である場合に、前記符号選択部に対して予測誤差の値にかかわらず出力符号として予測誤差符号のみを選択するよう指示することを特徴とする請求項３に記載のデータ圧縮装置。
【請求項７】
前記予測誤差符号化部は、
予測誤差の値を可変長符号により符号化して予測誤差符号を生成し、
前記ランレングス符号化部は、
ランレングスを可変長符号により符号化してランレングス符号を生成することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項８】
前記予測誤差符号化部は、
前記予測誤差算出部により予測誤差が算出される度に、算出された予測誤差の値が所定の固定ビット数で表される整数値のうちの最小値に該当するか否かを判断し、前記予測誤差の値が前記最小値に該当する場合に前記予測誤差の値を前記固定ビット数により符号化して予測誤差符号を生成し、前記予測誤差の値が前記最小値に該当しない場合に前記予測誤差の値を正の整数にマッピングし、マッピングした正の整数を可変長符号により符号化して予測誤差符号を生成することを特徴とする請求項７に記載のデータ圧縮装置。
【請求項９】
前記予測誤差符号化部は、
アルファ符号、ガンマ符号、デルタ符号、オメガ符号及びゴロム符号のいずれかにより予測誤差符号を生成し、
前記ランレングス符号化部は、
アルファ符号、ガンマ符号、デルタ符号、オメガ符号及びゴロム符号のいずれかによりランレングス符号を生成することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項１０】
前記予測誤差符号化部は、
次に入力するデータの１つ前に入力したデータの値を次に入力するデータの予測値とすることを特徴とする請求項１に記載のデータ圧縮装置。
【請求項１１】
前記予測誤差符号化部は、
次に入力するデータに先行して入力している２つ以上のデータを用いた線形演算を行って、次に入力するデータの予測値を算出することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項１２】
データを順次入力するコンピュータが行うデータ圧縮方法であって、
前記コンピュータが、データの入力前にデータの値を予測し、データを入力する度に、入力した入力データの値と当該入力データに対して予測した予測値との差を予測誤差として算出し、
予測誤差を算出する度に、前記コンピュータが、算出した予測誤差の値を符号化して予測誤差符号を生成し、
前記コンピュータが、算出した予測誤差のランレングスを計数し、
予測誤差の値が変化した際に、前記コンピュータが、計数したランレングスを符号化してランレングス符号を生成し、
ランレングス符号を生成する度に、前記コンピュータが、生成したランレングス符号を当該ランレングス符号に対応する予測誤差の予測誤差符号に結合して結合符号を生成し、
前記コンピュータが、算出した予測誤差の値に応じて、当該予測誤差に対する予測誤差符号及び結合符号のいずれかを出力符号として選択し、
前記コンピュータは、
データ入力に先立ち、入力することになる複数の入力予定データに対して特定の値を選定し、選定した値の予測誤差に対する出力符号として結合符号を選択するよう決定し、
入力データに対して算出した予測誤差の値が、データ入力に先立って選定した値である場合に、出力符号として当該予測誤差に対する結合符号を選択し、入力データに対して算出した予測誤差の値が、他の値である場合に、出力符号として当該予測誤差に対する予測誤差符号を選択することを特徴とするデータ圧縮方法。
【請求項１３】
データを順次入力するコンピュータに、
データの入力前にデータの値を予測し、データを入力する度に、入力した入力データの値と当該入力データに対して予測した予測値との差を予測誤差として算出する予測誤差算出処理と、
前記予測誤差算出処理により予測誤差が算出される度に、算出された予測誤差の値を符号化して予測誤差符号を生成する予測誤差符号化処理と、
前記予測誤差算出処理により算出された予測誤差のランレングスを計数するランレングス計数処理と、
予測誤差の値が変化した際に、前記ランレングス計数処理により計数されたランレングスを符号化してランレングス符号を生成するランレングス符号化処理と、
前記ランレングス符号化処理によりランレングス符号が生成される度に、生成されたランレングス符号を当該ランレングス符号に対応する予測誤差の予測誤差符号に結合して結合符号を生成する符号結合処理と、
前記予測誤差算出処理により算出された予測誤差の値に応じて、当該予測誤差に対する予測誤差符号及び結合符号のいずれかを出力符号として選択する符号選択処理と、
前記予測誤差算出処理のデータ入力に先立ち、前記予測誤差算出処理が入力することになる複数の入力予定データに対して特定の値を選定し、選定した値の予測誤差に対する出力符号として結合符号を選択するよう前記符号選択処理に指示する選定指示処理を実行させ、
前記符号選択処理において、
前記コンピュータに、
前記予測誤差算出処理により算出された予測誤差の値が前記選定指示処理から指示された値である場合に出力符号として当該予測誤差に対する結合符号を選択させ、前記予測誤差算出処理により算出された予測誤差の値が他の値である場合に出力符号として当該予測誤差に対する予測誤差符号を選択させることを特徴とするプログラム。
【国際調査報告】
2011108089.tif 000020
2011108089.tif 000021
2011108089.tif 000022
2011108089.tif 000023