数値データの圧縮システム及び方法
【課題】FPC方式の技術的課題を解消し、浮動小数点形式の数値データの圧縮率を向上させる。
【解決手段】入力データのビット列及び予測データのビット列のそれぞれの差分による差分ビット列を所定の数の単位の組でメモリにバッファリングするバッファ部と、バッファリングされた差分ビット列のそれぞれから、符号部及び指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる1又はそれ以上のブロックに分割し、また分割されたブロックを、上位から下位の順に組ごとに組み替えて連結することにより、先行ビット列としてバッファリングする再構築部と、バッファリングされた先行ビット列ついて、先頭ブロックからの値が零となるブロックの連続数に基づき先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮部とを含む圧縮システム。
【解決手段】入力データのビット列及び予測データのビット列のそれぞれの差分による差分ビット列を所定の数の単位の組でメモリにバッファリングするバッファ部と、バッファリングされた差分ビット列のそれぞれから、符号部及び指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる1又はそれ以上のブロックに分割し、また分割されたブロックを、上位から下位の順に組ごとに組み替えて連結することにより、先行ビット列としてバッファリングする再構築部と、バッファリングされた先行ビット列ついて、先頭ブロックからの値が零となるブロックの連続数に基づき先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮部とを含む圧縮システム。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、主にコンピュータによる科学技術計算や表計算のソフトウェアで一般的に採用されている浮動小数点形式の数値データの処理に関し、連続して入力される数値入力データを効率的に圧縮及び伸長するためのシステム、方法及びその装置に関するものである。
【背景技術】
【0002】
浮動小数点形式の数値データを圧縮する方式として、従来技術には、当該データを「A×Z + R(A及びRは実数、Zは整数)」の形で表現し、整数部分Zをエントロピィ符号化といった公知の圧縮技術を用いてデータ圧縮するものが存在する(特許文献1〜4)。また、これ以外にも、当該整数部分Zを辞書方式で圧縮する方式(例えば、LZ形式のデータ圧縮)も存在する(非特許文献1)。
【0003】
また、これらの先行技術とは別に、IEEE754において規定されている64ビットの倍精度浮動小数点方式について、FPCという方式を用いて64ビットの浮動小数点形式の数値を有するデータ・ストリームを圧縮するシステムが存在している(非特許文献2)。
【0004】
図1に、先行技術である当該FPCのアルゴリズムの概要を示す。なお、図1は非特許文献2に記載のFig.1(FPC compression algorithm overview)をそのまま引用したものである。FPCは、IEEE754倍精度浮動小数点形式の数値データの線形入力シーケンス(uncompressed 1D block of doubles)における各64ビット・データ値(「doubleb」)に対して、(i)2つの予測器「fcm」及び「dfcm」を用いて各64ビット・データ値を予測し、(ii)各予測データ値と入力データ値「doubleb」をそれぞれ比較(「compare」)し、(iii)比較結果に基づいて「doubleb」により近い方の64ビット値(「closer value」)を「selector」で選択し、(iv)入力データ(「doubleb」)のビット列と選択された「closer value」のビット列との排他的論理和「XOR」を計算する。次いで、(v)その結果に対して、「leading zero byte counter」において先行0バイト部分をカウントし、(vi)当該カウント値に基づいて、前記「selector」からの「predictor code」と共に「encoder」で圧縮処理を行い、出力(「compressed block」)するものである。ここで、「encoder」での先行0バイト部分の圧縮では、先行0バイトの数を3ビットの値にエンコードして、1ビットの「predictor code」と連結して4ビットにコード化する。最終的な出力「compressed block」は、当該4ビット・コード(bitb+cntb)並びに圧縮されていない残余部(「residualb」)で構成される。
【先行技術文献】
【特許文献】
【0005】
特許文献1:特許第4049791号
特許文献2: 特許第4049792号
特許文献3: 特許第4049793号
特許文献4: 再表2004/098066号
【非特許文献】
【0006】
非特許文献1:「ISO/IEC MPEG-4 Audio Lossless Coding (ALS) におけるIEEE754浮動 小数点信号の可逆圧縮」、原田ら、信学論、Vol. J89-B, No. 2, pp. 204-313, 2006.)
非特許文献2: M. Burtscher and P. Ratanaworabhan, “FPC: A High-Speed Compressor for Double-Presicion Floating-Point Data,” (http://users.ices.utexas.edu/~burtscher/papers/tc09.pdf)
【発明の概要】
【発明が解決しようとする課題】
【0007】
本発明は、上記FPCと類似の値予測手法により数値データを圧縮する手法を基本にして、連続して入力される浮動小数点形式の数値データ・ストリームに対する圧縮率を向上することを目的とするものである。
【0008】
【表1】
【0009】
表1は、従来技術によるデータ圧縮率の比較を示している。表中、「表計算」は単利年率0.5%の利率計算を100,000年分行ったデータ、「科学技術計算」は後述する図2のfdtdの圧縮後データ、「観測データ」は同obs_tempの圧縮後データのサイズを示したものである。上記表1からも明らかなように、特に表計算及び科学技術計算の技術分野においては、FPC(非特許文献2)と比べ、ZIPに代表される辞書方式の圧縮方式では圧縮率が十分なものとはいえない場合も多く、上述したような、浮動小数点形式の数値データを「A×Z + R(A及びRは実数、Zは整数)」の形で表し、整数部分Zに対して辞書方式で圧縮を行う方式(非特許文献1)においても圧縮率が十分なものとはいえない。
【0010】
更に、上記FPCにおいては、そもそも倍精度浮動小数点形式の数値データの予測が困難であり、十分な圧縮率が得にくいという問題がある。当該予測困難性については、図2に参照されるグラフから更に説明される。図2のグラフにおいて、縦軸は上記〔非特許文献2〕で開示されるアルゴリズムを用いて種々のデータセットに対して行った予測の予測的中率、横軸は、IEEE754による倍精度浮動小数点形式の符号ビットを1ビット目としたときのビット位置を示している。また、「obs_temp」をはじめとする各データセットは、上記〔非特許文献2〕に開示されているとおりのものであり、ここで「fdtd」については、電磁界解析での数値計算において用いられ、本発明者がシミュレーション用に作成したものである。尚、当該「fdtd」の具体的な内容については本発明の対象外である点に留意されたい。
【0011】
図示のとおり、多くのデータにおいて、12ビット目以降のビット位置において予測的中率が低下し、的中率「0.5」(即ち、ランダムに予測したのと同じ結果)に近付いていることが分かる。即ち、従来のFPCによる方式では、このような倍精度浮動小数点形式のデータ予測が困難な条件下で圧縮を行うものとなることから、十分な圧縮率を得ることは難しい。更に、上記FPCにおいては、各々の浮動小数点形式データに対して別個に圧縮処理を実施している点も圧縮率を制限する一因となっている。
【0012】
そこで、本発明は、上記のような従来のFPCの問題点を解消するために、上記FPCと類似の値予測手法による数値データ圧縮方式を基本にして、更に、複数の浮動小数点形式の数値データを所与の数の単位で纏めて一組で処理するように構成し、及び数値データのビット列に対し、特に予測的中率の高い上位ビット列部分とそれ以外の下位ビット列部分に分離した上で、当該上位ビット列部分と下位ビット列部分を独立して圧縮処理を実施することにより、より効果的な浮動小数点形式の数値データの圧縮率を実現することを目的とするものである。
【課題を解決するための手段】
【0013】
本発明のシステムは、連続して入力される複数の入力データを、各入力データに対する予測データに基づいて圧縮するものであり、当該入力データ及び予測データの浮動小数点形式が、所定のビット数を有する符号部、指数部及び仮数部の順で表される2進数のビット列からなるように構成されている。
【0014】
より具体的には、本発明のシステムは、(i)入力データのビット列及び予測データのビット列のそれぞれの差分(例えば、排他的論理和)による差分ビット列を所定の数の単位の組でメモリにバッファリングするバッファ部、(ii)当該バッファリングされた差分ビット列のそれぞれから、符号部及び指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる1以上のブロックに分割し、また、当該分割されたブロックを、上位から下位の順に組ごとに組み替えて連結することにより、先行ビット列としてバッファリングする再構築部、(iii)当該バッファリングされた先行ビット列ついて、先頭ブロックからの値が零(0)となるブロックの連続数に基づき先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮部、を含むものである。
【0015】
当該本発明のシステムにより、上述したFPC方式の技術的課題を解消し、浮動小数点数の予測が困難な状況であっても、圧縮率を向上させることを可能にする。
【0016】
また、本発明のシステムにおける上記再構築部は、更に、上記連結された先行ビット列に対して、上位のブロックから順に値が非零(0でない)となるブロックを検査し、及び下位のブロックから順に値が零(0)となるブロックを検査し、当該非零ブロック及び当該零ブロックがそれぞれ検出された場合には、これらを入れ替えるように構成される。
【0017】
当該構成により、例えば、浮動小数点数の絶対値はほぼ等しいものの、符号ビットだけが異なるような振動データが連続して入力された場合にも十分な圧縮率を確保することを可能にする。
【0018】
更に、本発明のシステムにおける圧縮部は、差分ビット列から上位ビット列を除いた下位ビット列を組ごとに連結して形成される残余ビット列を、所定のビット数からなるブロックの単位で分割するように構成され、当該ブロックの単位で分割された各ブロックのうち、零(0)が所定のバイト数以上含まれるブロックを抽出及び削除することに基づいて、残余ビット列を圧縮する残余列圧縮部を備える。
【0019】
このように下位ビット列、即ち、浮動小数点形式の数値データにおける仮数部に対しても圧縮処理を行うことで、浮動小数点数の圧縮率を更に向上させることができる。同じ浮動小数点数が連続して入力されるような容易に予測可能データが入力される場合に特に有利である。
【図面の簡単な説明】
【0020】
【図1】図1は、従来技術のFPC方式の概要を示すブロック図である。
【図2】図2は、従来技術の倍精度浮動小数点形式の数値データの予測困難性を示すグラフである。
【図3】図3は、IEEE754で標準化されている倍精度浮動小数点データの表示形式を示す図である。
【図4】図4は、本発明の第1実施形態における圧縮方式の概要を示すブロック図である。
【図5】図5は、入力データAnと予測データPnから差分ビット列Dnを生成するイメージ図である。
【図6】図6は、本発明の第1実施形態の圧縮方式における圧縮器5の詳細を示すブロック図である。
【図7】図7は、本発明の第1の実施形態の圧縮方式におけるブロック組み替えに基づく再構築部の先行ビット列及び残余ビット列の形成を示すイメージ図である。
【図8】図8は、先行列圧縮部の圧縮先行ビット列の形成を示すイメージ図である。
【図9】図9は、本発明の第2の実施形態の圧縮方式のアドレス再構築部におけるブロック入れ替えを示すイメージ図である。
【図10】図10は、本発明の第2実施形態におけるアドレス再構築部におけるブロック入れ替え処理に係るより詳細なイメージ図である。
【図11】図11は、本発明の第2実施形態におけるアドレス再構築部におけるブロック入れ替え処理を示すフローチャートである。
【図12】図12は、本発明の第3実施形態における圧縮システムの改良の概要を示すブロック図である。
【図13】図13は、本発明の第3実施形態における2つの予測値に基づく2つの差分値計算を示すイメージ図である。
【図14】図14は、本発明の第3実施形態における2つの差分値に基づく比較器出力を示すイメージ図である。
【図15】図15は、発明の第3実施形態における先行ビット列の圧縮を示すイメージ図である。
【図16】図16は、本発明の第4実施形態における浮動小数点形式の数値データの圧縮方式を示すブロック図である。
【図17】図17は、本発明の第4実施形態の残余列圧縮部における残余ビット集合列Rの形成を示すイメージ図である。
【図18】図18は、本発明の第4実施形態の残余列圧縮部において圧縮される残余ビット集合列R’を示すイメージ図である。
【発明を実施するための形態】
【0021】
本発明の実施形態に係る圧縮・伸長システムを図面に基づいて説明する。尚、以下の実施形態は例示に過ぎず、特許請求の範囲に記載の発明がこれに限定されるものではない。
【0022】
図3は、IEEE754で標準化されている倍精度浮動小数点形式の数値データを2進数のビット列で表示する概要図である。IEEE754で標準化されている倍精度浮動小数形式のデータは、以下の計算式に基づいて表されるものである。
【0023】
【数1】
【0024】
ここで、「S」は符号部、「exp」は指数部、及び「fraction」は仮数部を示しており、図3のように2進数の表示形式において、上位ビットから順にそれぞれ1ビット、11ビット、及び52ビット、合計64ビットから形成される。
【0025】
以下、IEEE754で標準化されている倍精度浮動小数点形式の数値データに基づいて各実施形態を記載するが、本発明は、特に注記するもののほか、64ビットの倍精度浮動小数点形式の数値データに限定されるものではなく、IEEE754で同様に標準化されている32ビットの単精度浮動小数点形式の数値データのみならず、この他多倍長精度の浮動小数点形式(例えば、128ビット)の数値データにも適用でき、符号部、指数部及び仮数部で上位から下位の順に構成される2進数のビット列で表現される浮動小数点形式の数値データ全般に適用できるものである。
【実施形態】
【0026】
第1実施形態
図4は、本発明の圧縮システムの概要を示すブロック図である。入力される複数の浮動小数点形式の数値データに対し、コンピュータの中央処理装置は、レジスタやキャッシュ・メモリを含むメモリ操作を行いながら、各構成要素において次のように動作する。
【0027】
入力列1は、連続して入力されるN個の浮動小数点形式の入力データAn(n=1,2,・・・,N)を示している(Nは1以上の整数)。入力データAnは、差分器4に順次入力されるとともに、遅延器2において1クロック分遅延されて遅延器2から結合される予測器3に入力される。予測器3では、入力データAnが差分器4に入力されるタイミングと同期して、既に入力されていた入力データA0〜A(n−1)(但し、A0は入力列に先行する仮想的なデータ)から予測される浮動小数点形式の予測データPnを予測して、予測器3から結合される差分器4に入力する。差分器4では、入力された入力データAn及び予測された予測データPnの各ビット列の差分(例えば、排他的論理和)を計算し、差分ビット列Dnとして出力する。
【0028】
なお、図5に示したとおり、ここでの予測データPnは、例えば、非特許文献2に開示される公知技術を適用して、入力データA0〜A(n−1)から予測することができ、また、差分ビット列Dnのビット列表現においては、予測的中率の高い上位ビットほど「0」の出現確率が高いと想定される(図2も参照)。
【0029】
当該差分器4に結合される圧縮器5において、以下の図6に詳述する本発明の圧縮処理を行い、
を行う(Mは任意の自然数である)。
【0030】
図6は、本発明の圧縮方式における圧縮器5内部の詳細を示すブロック図である。
【0031】
圧縮器5は、差分器4からの複数の差分ビット列Dnを所定の数(ここではM個)の単位の組でメモリにバッファリングするバッファ部51、バッファリングされた1組の各差分ビット列Dnについて、浮動小数点形式の符号部及び指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる1又はそれ以上のブロックに分割、及び当該分割されたブロックを上位から下位の順に組ごとに組み替えて連結を行い、先行ビット列としてバッファリングし、また、当該差分ビット列から上位ビット列を除いた下位ビット列を組ごとに連結して形成されるビット列を残余ビット列としてバッファリングする再構築部52、及び、当該先行ビット列に対して圧縮処理を行って出力する先行列圧縮部53を備えている。
【0032】
更に図6の再構築部52について説明すると、図7に示すような態様で、各データのビット列を上位から8ビット(1バイト)、4ビット(1/2バイト)、4ビット(1/2バイト)、及びそれ以外の48ビット(12バイト)の順にブロック分割し、上位ビット列のブロック(8ビット+4ビット+4ビット)および下位ビット列(48ビット)について、それぞれのブロックを組単位で組み替えて上位ブロックから順番に連結してメモリにバッファリングする、アドレス演算を行うアドレス再構築部521、先行ビット列をバッファリングする先行列バッファ522、及び残余ビット列をバッファリングする残余列バッファ523を備えている。
【0033】
図2のグラフで示したとおり、本構成は、連続して入力される複数の入力浮動小数点に対してそれぞれ予測される予測データのうち、上位の数バイト部分については比較的高い予測的中率で予測できるという特徴に着目したものであり、所定のM個の差分ビット列のうち当該部分をブロック単位でまとめて組み替えた上で圧縮処理することで従来のFPCと比べて圧縮率を向上させるものである。
【0034】
ここで、図7に示す先行ビット列及び残余ビット列の構成について更に詳細に説明する。なお、ここでは簡単のためにM=4として説明するが、これに限定されるものではなく、Mは任意の自然数とすることができる。
【0035】
差分器4から入力される複数のデータのうち、連続して入力される4個(即ち、M個)のデータのビット列(Dn〜D(n+3))がバッファ部51にバッファリングされる。ここで、各ビット列の上位2バイト(16ビット)は、符号部(上位1ビット)及びそれに続く指数部(11ビット)の計12ビットを含むものである。再構築部52では、各データのビット列を符号部(1ビット)と指数部(11ビット)を含む上位16ビット(2バイト)からなる上位ビット列、及びそれ以外の48ビット(6バイト)の下位ビット列に分離し、更に当該上位ビット列を8ビット(1バイト)の第1ブロック及び4ビット(1/2バイト)の2つの第2及び第3ブロックに分割する。ここで、2つの第2及び第3ブロックに分割しているのは、第1ブロック及び第2ブロックの合計12ビットが、符号部(上位1ビット)と指数部(11ビット)との合計12ビットに一致するようにするためである。図7では、第1ブロックがブロック〔1〕〜〔4〕、第2ブロックがブロック〔5〕〜〔8〕、そして第3ブロックがブロック〔9〕〜〔12〕である。なお、下位のブロックは、48ビット(6バイト)の下位ビット列でそのまま構成される(ブロックI〜IV)。
【0036】
再構築部では、更に、図7に示すように、上位ビット列及び下位ビット列について、各ブロックを組単位で組み替えて上位ブロックから順に連結し、64ビットの先行ビット列Li及び192ビットの残余ビット列Riとして形成して、メモリ(先行列バッファ522及び残余列バッファ523)にバッファリングする。即ち、形成される先行ビット列Liは、第1ブロック(ブロック〔1〕〜〔4〕)、第2ブロック(ブロック〔5〕〜〔8〕)、第3ブロック(ブロック〔9〕〜〔12〕)の順番で連結したものである。同様に、形成される残余ビット列Riは、ブロックI〜IVの順番で連結したものである。
【0037】
次いで、当該先行ビット列Liを先行列圧縮部53に入力し、図8に示すように圧縮先行ビット列(ζ+Ui)を形成する。即ち、形成された64ビットの先行ビット列Liについて、1ブロックを1バイト(即ち8ビット)として、先頭ブロックから値が零(0)の連続するブロック部分Ziとそれ以外のブロック部分Uiに分割し、Ziの連続ブロック数(バイト数)zをカウントする。当該連続ブロック数zに基づいて先行ビット列Liを圧縮して圧縮先行ビット列を形成する。M=4である場合には、例えば、次の表2に表すテーブルを参照することで、8×zビットを3ビットに圧縮する。
【0038】
【表2】
【0039】
例えば、先行ビット列Li全体が零(0)の場合には、64ビットの先行ビット列Liを3ビットにまで最大限圧縮することができる。そしてMが特に2の階乗(即ち、M=2m)のときは、M×16(ビット)の先行ビット列Liを最大(m+1)ビットにまで圧縮することができることになる。
【0040】
図8の例の場合、Ziの連続ブロック数zは、「2」である。このときの3ビットのζは、表2より、「001」と表される。即ち、64ビット(先行ビット列Li)のビット列を、3ビット(「001」;ζ)+48ビット(非零ブロック;Ui)の合計51ビットに圧縮することができている。
【0041】
第2実施形態
本発明による第2の実施形態では、第1の実施形態における先行ビット列Liの圧縮率を向上させるために、アドレス再構築部521において、更に、図9〜図11に示すブロックの入れ替え処理を行う。
【0042】
第1実施形態に基づく複数の浮動小数点形式の数値データに対するブロックへの分割及び組み替えに関する構成を実施する場合に、絶対値はほぼ等しいものの、符号部のビットのみが異なるような振動データに対する圧縮が不十分なものとなる場合があるという課題を解決することができる。
【0043】
図9に示すとおり、先行ビット列Liに対して、上位ブロックから順に非零ブロックがあるか検査し、また、下位ブロックから順に零ブロックがあるか検査し、それぞれブロックが存在し検出された場合には、ブロックの入れ替えを行う。これにより、先頭ブロックから値が零(0)の連続するブロック部分Ziを拡張し、かつ、それ以外のブロック部分Uiを短縮することができる。
【0044】
伸長されたブロック部分Z’iは、上述した表2の3ビットζに、入れ替えフラグ1ビット、及び入れ替えブロック位置を示すビット列(8ビット)を加えた合計12ビットのζ’に圧縮することができる。最終的には、先行ビット列Liは、当該12ビットのζ’にブロック入れ替え後のU’iを連結したブロックに圧縮することができる(M=4の場合)。ここでの入れ替え位置を示すビット位置は、2×Mビット長のビットマップであり、入れ替えたブロック位置に対応するビットを「1」とするものである。
【0045】
図10は、第2実施形態における先行ビット列Liの別の実施例を示している。当該実施例を図11のフローチャートと共に説明する。尚、図10においても、M=4とし、また、1ブロックは1バイトで構成し、簡単のために先行ビット列Li及びL’iは16進数で表示している。
【0046】
先行ビット列Liに対して、上位ブロック(ブロック1)から順に非零ブロックを検査する(S100)。ここでは、ブロック2が「80」であり、非零ブロックとして検出される(S110)。そして、先行ビット列Liに対して、下位ブロック(ブロック8)から順に零ブロックを検査する(S120)。ここでは、ブロック8が「00」であり、零ブロックとして検出される(S130)。この場合、それぞれの検査ブロック位置の関係が「2<8」を満たしていることから(S140)、ブロック2「80」とブロック8「00」とを入れ替えるように操作し(S150)、入れ替えフラグ・ビットを「1」にし(S160)、更に、入れ替えブロック位置ビット列の第2ビットと第8ビットをそれぞれ「1」にする(S170)。この処理の結果、ζ及びLiは、図10に示すζ’及びL’iのように更新される。
【0047】
引き続き、検査を繰り返して、ブロック3から順に非零ブロックを検査していき、ブロック5の「01」を検出する(S100及びS110)。また、ブロック7から順に零ブロックを検査していき、ブロック6の「00」を検出する(S120及びS130)。そして、それぞれの検査ブロック位置の関係が「5<6」であるので(S140)、同様に、これらのブロックを入れ替えるように操作し(S150)、入れ替えフラグ・ビットを「1」にして(S160)、更に入れ替えブロック位置ビット列の第5ビット及び第6ビットをそれぞれ「1」にする(S170)。この処理の結果、ζ’及びL’iは図10に示すζ’’及びL’’iのように更新される。
【0048】
引き続き、検査を繰り返して、非零ブロックとしてブロック6を、零ブロックとしてブロック5を検出するが(S100〜S130)、検査ブロック位置の関係が「6>5」となり(S140)、これはすでに検査済みであることを意味するものであるため、繰り返しの検査処理を抜け、入れ替え処理を完了(END)する。
【0049】
このような入れ替え処理により、第1実施形態では、先頭ブロックから値が零(0)の連続するブロック部分Ziのブロック数z=1であったものが、第2実施形態では、先頭ブロックから値が零(0)の連続するブロック部分Z’iのブロック数z’’=5とすることができ、圧縮率の向上に成功する。
【0050】
以上より、本実施形態では第1実施形態に対して圧縮率を更に向上させることができる。なお、上記入れ替え処理の各ステップは、一例を示しているに過ぎずこれに限定されることはない。即ち、ブロック同士を入れ替え、入れ替えフラグ・ビットを更新することができる処理であればどのような態様で実施してもよい。
【0051】
第3実施形態
本発明による第3の実施形態は、主に、上記第1実施形態における、予測器3及び差分器4を用いて複数の入力された入力データAn及び複数の予測された予測データPnの各ビット列の差分(例えば、排他的論理和)から複数の差分ビット列Dnを出力するという構成についての代替の実施の形態を示すものである。
【0052】
図12に示すとおり、本実施形態では、2つの予測器31、32を用いて2つの異なる方式で2種類の予測値を計算する。差分器41、42において、2つの差分値を計算して圧縮器5’に出力する。そして、圧縮器5’が備える比較部50において所定のルールに基づいて差分値を当該2つの差分値から選択し、どちらの差分値を選択したかを示す選択ビットと共にバッファ部51’(図示せず)に内部出力する。この結果、圧縮器5’からの圧縮出力C’iには、Mビット(この場合4ビット)の選択ビット列(選択信号)も含まれることになる。
【0053】
以下、図12〜図15を用いて詳細に説明する。
【0054】
第1実施形態においては、図5に示したとおり、入力データAnが比較器4に入力されるタイミングと同期して、入力されていた入力データA0〜A(n−1)から予測される予測データPnを予測器3で予測し、差分器4において、入力データAn及び予測データPnの各ビット列の差分(例えば、排他的論理和)を計算し、差分ビット列Dnとして出力している。これに対し、本実施形態においては、図12及び13に示すとおり、2つの予測器31、32を用いて同様に予測データPn及びQnをそれぞれ別々に予測し、当該2つの予測器31、32にそれぞれ結合される2つの差分器41、42を用いて入力データAnと予測データPn及びQnとの各ビット列の差分(例えば、排他的論理和)をそれぞれ計算して、差分ビット列Dn及びEnとして圧縮器5’にそれぞれ出力する。
【0055】
圧縮器5’では、まず、比較部50によって、差分ビット列Dn及びEnの比較・選択を行う。なお、当該比較・選択に際しては、所定のビット数からなるブロックに分割して処理を行うが、ここでのビット数は、1バイト(即ち8ビット)でも1ビットでもよく、任意の数とすることができる。ここでは、バイト単位でブロックを形成することを想定する。
【0056】
図14に8個のブロック(ブロック1〜8)からなる、64ビットの2つの差分ビット列Dn及びEnの具体例を示す。なお、各ブロックの値は簡単のため16進数で表示している。比較部50では、各差分ビット列に対し、値が零(0)となる零ブロックの数bをカウントし、当該零ブロック数bが大きい方の差分ビット列を選択する。図14の場合は、差分ビット列Dn及びEnの各零ブロック数bd(=4)及びbe(=2)の値より、値が大きい方の差分ビット列Dnを選択出力Fnとして出力する。その際、どちらの差分ビット列を選択したかを示す1ビットの選択信号Snを、例えばDnを選択した場合はSn=0、Enを選択した場合はSn=1として、併せて出力する。
【0057】
このように、予測器31、32での予測精度がより高いものに対する差分ビット列を、比較部で選択するように圧縮器を構成することにより、その後の圧縮処理における圧縮率を向上させることができる。
【0058】
図15は、本実施形態の圧縮器5’において、先行列バッファ522にバッファリングされた64ビットの先行ビット列Liの圧縮に係る構成を図示したものである。尚、ここでもM=4と仮定しており、先行ビット列Li自体は第1実施形態において説明したのと同様に構成される。また、当該先行ビット列Liから構成されるζ及びUiについても第1実施形態と同様である(図8参照)。先行ビット列Liは、このζに、1×4ビット(即ちMビット)の選択信号Sn〜S(n+3)を加えて圧縮することができる。
【0059】
本発明は、本実施形態における差分ビット列の選択に係る構成に、更に実施形態2における先行ビット列に対するブロックの入れ替えに係る構成を組み合わせることにより、より一層データの圧縮率を向上させることができる。
【0060】
なお、上述した差分ビット列Dn及びEnの比較・選択について、差分器41、42に結合するように配置された上記比較部50で比較・選択を実施するのに替えて、差分ビット列Dn及びEn両方に対してバッファ部及び再構築部での処理並びにバッファリングを実施し、及び、先行列バッファから比較部50を結合するように比較部50を配置して、当該比較部50で先行列バッファに対して同様の比較・選択の処理を行うように構成することも可能である。
【0061】
以上の実施形態1〜3においては、IEEE754に規定される倍精度浮動小数点形式の数値データのビット列に対して、ブロックの分割をバイト単位(即ち、8ビット単位)により実施するものであるが、本発明はこれに限定されるものではなく、IEEE754に規定されるように、浮動小数点形式の数値データが符号部、指数部及び仮数部を用いて表現され、かつ、2進数のビット列が上位からこの順序で構成されるものであれば任意のデータに対して実現することができ、また、図7に示した分割するブロックの単位も、先行列を構成する上位ビット列が符号部及び指数部を含むものであればよく、バイト単位に限定されず、任意のビット数でよい。即ち、符号部及び指数部のビット数で分割ブロックを構成してもよく、更には符号部及び指数部のビット数の約数で1ブロックを構成し、複数ブロックで符号部及び指数部を含む上位ビット列としてもよい。
【0062】
第4実施形態
上述した実施形態1〜3では、先行ビット列に対して圧縮処理を行う構成であったが、第4の実施形態では、更に、残余ビット列に対しても圧縮処理を行う。
【0063】
本発明は、上述のとおり浮動小数点形式の数値データの予測困難性に着目したものであり、これを前提とした上で浮動小数点形式の数値データの圧縮率を向上させるものである。
【0064】
これに対し、同じ値のデータが連続するような一般に容易に予測可能とされるデータに対してこのような圧縮方式を適用した場合には、先行技術文献に記載されるような従来技術を適用した場合と比べて圧縮率が同等若しくはそれ以下になることも想定される。
【0065】
そこで、本実施形態では、このような容易に予測可能な浮動小数点形式の数値データが入力された場合でも圧縮率を向上させるため、更に、残余ビット列に対して、以下に説明する圧縮方式を適用することにより、圧縮率を向上させる。
【0066】
図16は、本実施形態における浮動小数点形式の数値データの圧縮システムを表すブロック図である。図6と比べて、残余列圧縮部54が追加されている。残余列圧縮部54は、残余列バッファ523にバッファリングされている残余ビット列の入力を受け、圧縮処理を行って圧縮出力をするものである。尚、残余列圧縮部54以外の各構成要素については、上述の実施形態1〜3に基づいて実現することができる。
【0067】
以下に、図17〜図18を用いて残余列圧縮部54における残余ビット列Riに対する圧縮方式について説明する。尚、上述のとおり、残余ビット列RiはM個の48ビット(即ち、6バイト)のビット列で構成される(図7参照)。
【0068】
図17は、残余列圧縮部54において、残余ビット列Riについて
をバッファリングしてまとめて連結し、残余ビットの集合列Rを形成する構成について記載している。ここでは、残余ビット列RiにおけるM個の6バイト列をr(i,1)〜r(i,M)としている。このようにして形成される残余ビット集合列Rは、6×Nバイト長のものとなる。残余ビット集合列Rに対し、図18に示すように6バイトの
の中から零(0)が6バイト連続する(即ち、値が0)もの、又は零(0)が5バイト含まれるものを抽出して、この抽出した位置を示す位置列Hを形成する。尚、零(0)が5バイト含まれるr(i,j)については、当該r(i,j)内の非零(0でない)となるバイトの位置、及びそのビット列を別途記憶する。図18においては、r(i0,1)及びr(i1,3)が、零(0)が6バイト連続するもの又は零(0)が5バイト含まれるものに該当し、これらの位置をH1及びH2として位置列Hを生成する。
【0069】
より具体的には、H1=M×(i0−1)+1、H2=M×(i1−1)+3の値から成る位置列Hを形成することになる。ここで、位置列Hの各構成要素は、nhバイト長となる。nhは、位置を記憶するために必要な容量であり、6バイトより小さくて済むようにする。
【0070】
一方、残余ビット集合列Rは、当該残余ビット集合列Rから、これらr(i0,1)及びr(i1,3)を削除することで圧縮され、圧縮残余ビット集合列R’が形成される。
【0071】
この結果、当初6×Nバイト長だった残余ビット集合列Rは、(6×N−2×6)バイト長の圧縮残余ビット集合列R’に圧縮することができる。圧縮残余ビット集合列R’及び位置列Hを圧縮出力として出力することで圧縮処理は終了する。
【0072】
本発明は、本実施形態において説明した残余ビット列に対する圧縮処理を、実施形態1〜3で記載した先行ビット列圧縮処理と併せて実施することで、特に、予測が容易な浮動小数点形式の数値データが連続して入力されるような場合に有効なものとなる。
【0073】
なお、本実施形態における位置列Hは、特定のr(i,j)の絶対位置を構成要素とするものであり、各構成要素は6バイトより小さい値で構成されるものであるが、特に実装上の観点からは、絶対位置ではなく相対位置として1バイトで各値を表現することができるようにし、当該相対位置、非零バイトr(i,j)の位置、非零バイトr(i,j)のビットパターンの3バイトを一組として非零バイトr(i,j)の出力とするようにすることもできる。更に、相対位置列に同じ値が連続して含まれる場合には、例えば、ランレングス法による圧縮手法を適用することにより、更なる数値データの圧縮が可能となる。
【0074】
以上、本発明の第1実施形態〜第4実施形態に係る連続して入力される複数の浮動小数点形式の数値データの圧縮方式について説明した。これらの実施形態の説明から分かるとおり、本圧縮方式は可逆式の圧縮方式であり、入力データAn(n=1,2,・・・,N)に対する
について、i=1,2・・・の順に圧縮動作と逆動作を行うことで、圧縮出力Ciを伸長して入力データAn(n=1,2,・・・,N)を復元することが可能である。
【0075】
圧縮結果
【表3】
【0076】
表3は、上述した表1に本願発明の一実施形態に基づいて実装し取得したデータを追加したものである。表3のとおり、本願発明の浮動小数点データの圧縮方式は、従来技術のFPC方式と比較すると、相対的に圧縮率の向上を実現することができている。
【産業上の利用分野】
【0077】
本発明の圧縮及び伸長システムは、連続して入力される複数の浮動小数点形式の数値入力データを効果的に圧縮してデータを取り扱うことができるため、大規模データを特にIEEE754に規定される倍精度浮動小数点形式において処理し、メモリに記憶する必要があるようなアプリケーションにおいて、有利なものとなる。
【0078】
具体的には、(i)表計算ソフトウェアにおいてセルに記憶する大規模データを浮動小数点形式の数値データとして記憶する場合、(ii)科学技術計算ソフトウェアの計算経過を主記憶内に保存する場合、(iii)フライトレコーダやドライブレコーダにおいて処理される実時間データのログを圧縮して記憶する場合、宇宙観測機から地球への通信といった狭帯域通信路において大規模データの通信を必要とする場合に、本発明によるシステム及び方法は特に有効なものとなる。
【技術分野】
【0001】
本発明は、主にコンピュータによる科学技術計算や表計算のソフトウェアで一般的に採用されている浮動小数点形式の数値データの処理に関し、連続して入力される数値入力データを効率的に圧縮及び伸長するためのシステム、方法及びその装置に関するものである。
【背景技術】
【0002】
浮動小数点形式の数値データを圧縮する方式として、従来技術には、当該データを「A×Z + R(A及びRは実数、Zは整数)」の形で表現し、整数部分Zをエントロピィ符号化といった公知の圧縮技術を用いてデータ圧縮するものが存在する(特許文献1〜4)。また、これ以外にも、当該整数部分Zを辞書方式で圧縮する方式(例えば、LZ形式のデータ圧縮)も存在する(非特許文献1)。
【0003】
また、これらの先行技術とは別に、IEEE754において規定されている64ビットの倍精度浮動小数点方式について、FPCという方式を用いて64ビットの浮動小数点形式の数値を有するデータ・ストリームを圧縮するシステムが存在している(非特許文献2)。
【0004】
図1に、先行技術である当該FPCのアルゴリズムの概要を示す。なお、図1は非特許文献2に記載のFig.1(FPC compression algorithm overview)をそのまま引用したものである。FPCは、IEEE754倍精度浮動小数点形式の数値データの線形入力シーケンス(uncompressed 1D block of doubles)における各64ビット・データ値(「doubleb」)に対して、(i)2つの予測器「fcm」及び「dfcm」を用いて各64ビット・データ値を予測し、(ii)各予測データ値と入力データ値「doubleb」をそれぞれ比較(「compare」)し、(iii)比較結果に基づいて「doubleb」により近い方の64ビット値(「closer value」)を「selector」で選択し、(iv)入力データ(「doubleb」)のビット列と選択された「closer value」のビット列との排他的論理和「XOR」を計算する。次いで、(v)その結果に対して、「leading zero byte counter」において先行0バイト部分をカウントし、(vi)当該カウント値に基づいて、前記「selector」からの「predictor code」と共に「encoder」で圧縮処理を行い、出力(「compressed block」)するものである。ここで、「encoder」での先行0バイト部分の圧縮では、先行0バイトの数を3ビットの値にエンコードして、1ビットの「predictor code」と連結して4ビットにコード化する。最終的な出力「compressed block」は、当該4ビット・コード(bitb+cntb)並びに圧縮されていない残余部(「residualb」)で構成される。
【先行技術文献】
【特許文献】
【0005】
特許文献1:特許第4049791号
特許文献2: 特許第4049792号
特許文献3: 特許第4049793号
特許文献4: 再表2004/098066号
【非特許文献】
【0006】
非特許文献1:「ISO/IEC MPEG-4 Audio Lossless Coding (ALS) におけるIEEE754浮動 小数点信号の可逆圧縮」、原田ら、信学論、Vol. J89-B, No. 2, pp. 204-313, 2006.)
非特許文献2: M. Burtscher and P. Ratanaworabhan, “FPC: A High-Speed Compressor for Double-Presicion Floating-Point Data,” (http://users.ices.utexas.edu/~burtscher/papers/tc09.pdf)
【発明の概要】
【発明が解決しようとする課題】
【0007】
本発明は、上記FPCと類似の値予測手法により数値データを圧縮する手法を基本にして、連続して入力される浮動小数点形式の数値データ・ストリームに対する圧縮率を向上することを目的とするものである。
【0008】
【表1】
【0009】
表1は、従来技術によるデータ圧縮率の比較を示している。表中、「表計算」は単利年率0.5%の利率計算を100,000年分行ったデータ、「科学技術計算」は後述する図2のfdtdの圧縮後データ、「観測データ」は同obs_tempの圧縮後データのサイズを示したものである。上記表1からも明らかなように、特に表計算及び科学技術計算の技術分野においては、FPC(非特許文献2)と比べ、ZIPに代表される辞書方式の圧縮方式では圧縮率が十分なものとはいえない場合も多く、上述したような、浮動小数点形式の数値データを「A×Z + R(A及びRは実数、Zは整数)」の形で表し、整数部分Zに対して辞書方式で圧縮を行う方式(非特許文献1)においても圧縮率が十分なものとはいえない。
【0010】
更に、上記FPCにおいては、そもそも倍精度浮動小数点形式の数値データの予測が困難であり、十分な圧縮率が得にくいという問題がある。当該予測困難性については、図2に参照されるグラフから更に説明される。図2のグラフにおいて、縦軸は上記〔非特許文献2〕で開示されるアルゴリズムを用いて種々のデータセットに対して行った予測の予測的中率、横軸は、IEEE754による倍精度浮動小数点形式の符号ビットを1ビット目としたときのビット位置を示している。また、「obs_temp」をはじめとする各データセットは、上記〔非特許文献2〕に開示されているとおりのものであり、ここで「fdtd」については、電磁界解析での数値計算において用いられ、本発明者がシミュレーション用に作成したものである。尚、当該「fdtd」の具体的な内容については本発明の対象外である点に留意されたい。
【0011】
図示のとおり、多くのデータにおいて、12ビット目以降のビット位置において予測的中率が低下し、的中率「0.5」(即ち、ランダムに予測したのと同じ結果)に近付いていることが分かる。即ち、従来のFPCによる方式では、このような倍精度浮動小数点形式のデータ予測が困難な条件下で圧縮を行うものとなることから、十分な圧縮率を得ることは難しい。更に、上記FPCにおいては、各々の浮動小数点形式データに対して別個に圧縮処理を実施している点も圧縮率を制限する一因となっている。
【0012】
そこで、本発明は、上記のような従来のFPCの問題点を解消するために、上記FPCと類似の値予測手法による数値データ圧縮方式を基本にして、更に、複数の浮動小数点形式の数値データを所与の数の単位で纏めて一組で処理するように構成し、及び数値データのビット列に対し、特に予測的中率の高い上位ビット列部分とそれ以外の下位ビット列部分に分離した上で、当該上位ビット列部分と下位ビット列部分を独立して圧縮処理を実施することにより、より効果的な浮動小数点形式の数値データの圧縮率を実現することを目的とするものである。
【課題を解決するための手段】
【0013】
本発明のシステムは、連続して入力される複数の入力データを、各入力データに対する予測データに基づいて圧縮するものであり、当該入力データ及び予測データの浮動小数点形式が、所定のビット数を有する符号部、指数部及び仮数部の順で表される2進数のビット列からなるように構成されている。
【0014】
より具体的には、本発明のシステムは、(i)入力データのビット列及び予測データのビット列のそれぞれの差分(例えば、排他的論理和)による差分ビット列を所定の数の単位の組でメモリにバッファリングするバッファ部、(ii)当該バッファリングされた差分ビット列のそれぞれから、符号部及び指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる1以上のブロックに分割し、また、当該分割されたブロックを、上位から下位の順に組ごとに組み替えて連結することにより、先行ビット列としてバッファリングする再構築部、(iii)当該バッファリングされた先行ビット列ついて、先頭ブロックからの値が零(0)となるブロックの連続数に基づき先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮部、を含むものである。
【0015】
当該本発明のシステムにより、上述したFPC方式の技術的課題を解消し、浮動小数点数の予測が困難な状況であっても、圧縮率を向上させることを可能にする。
【0016】
また、本発明のシステムにおける上記再構築部は、更に、上記連結された先行ビット列に対して、上位のブロックから順に値が非零(0でない)となるブロックを検査し、及び下位のブロックから順に値が零(0)となるブロックを検査し、当該非零ブロック及び当該零ブロックがそれぞれ検出された場合には、これらを入れ替えるように構成される。
【0017】
当該構成により、例えば、浮動小数点数の絶対値はほぼ等しいものの、符号ビットだけが異なるような振動データが連続して入力された場合にも十分な圧縮率を確保することを可能にする。
【0018】
更に、本発明のシステムにおける圧縮部は、差分ビット列から上位ビット列を除いた下位ビット列を組ごとに連結して形成される残余ビット列を、所定のビット数からなるブロックの単位で分割するように構成され、当該ブロックの単位で分割された各ブロックのうち、零(0)が所定のバイト数以上含まれるブロックを抽出及び削除することに基づいて、残余ビット列を圧縮する残余列圧縮部を備える。
【0019】
このように下位ビット列、即ち、浮動小数点形式の数値データにおける仮数部に対しても圧縮処理を行うことで、浮動小数点数の圧縮率を更に向上させることができる。同じ浮動小数点数が連続して入力されるような容易に予測可能データが入力される場合に特に有利である。
【図面の簡単な説明】
【0020】
【図1】図1は、従来技術のFPC方式の概要を示すブロック図である。
【図2】図2は、従来技術の倍精度浮動小数点形式の数値データの予測困難性を示すグラフである。
【図3】図3は、IEEE754で標準化されている倍精度浮動小数点データの表示形式を示す図である。
【図4】図4は、本発明の第1実施形態における圧縮方式の概要を示すブロック図である。
【図5】図5は、入力データAnと予測データPnから差分ビット列Dnを生成するイメージ図である。
【図6】図6は、本発明の第1実施形態の圧縮方式における圧縮器5の詳細を示すブロック図である。
【図7】図7は、本発明の第1の実施形態の圧縮方式におけるブロック組み替えに基づく再構築部の先行ビット列及び残余ビット列の形成を示すイメージ図である。
【図8】図8は、先行列圧縮部の圧縮先行ビット列の形成を示すイメージ図である。
【図9】図9は、本発明の第2の実施形態の圧縮方式のアドレス再構築部におけるブロック入れ替えを示すイメージ図である。
【図10】図10は、本発明の第2実施形態におけるアドレス再構築部におけるブロック入れ替え処理に係るより詳細なイメージ図である。
【図11】図11は、本発明の第2実施形態におけるアドレス再構築部におけるブロック入れ替え処理を示すフローチャートである。
【図12】図12は、本発明の第3実施形態における圧縮システムの改良の概要を示すブロック図である。
【図13】図13は、本発明の第3実施形態における2つの予測値に基づく2つの差分値計算を示すイメージ図である。
【図14】図14は、本発明の第3実施形態における2つの差分値に基づく比較器出力を示すイメージ図である。
【図15】図15は、発明の第3実施形態における先行ビット列の圧縮を示すイメージ図である。
【図16】図16は、本発明の第4実施形態における浮動小数点形式の数値データの圧縮方式を示すブロック図である。
【図17】図17は、本発明の第4実施形態の残余列圧縮部における残余ビット集合列Rの形成を示すイメージ図である。
【図18】図18は、本発明の第4実施形態の残余列圧縮部において圧縮される残余ビット集合列R’を示すイメージ図である。
【発明を実施するための形態】
【0021】
本発明の実施形態に係る圧縮・伸長システムを図面に基づいて説明する。尚、以下の実施形態は例示に過ぎず、特許請求の範囲に記載の発明がこれに限定されるものではない。
【0022】
図3は、IEEE754で標準化されている倍精度浮動小数点形式の数値データを2進数のビット列で表示する概要図である。IEEE754で標準化されている倍精度浮動小数形式のデータは、以下の計算式に基づいて表されるものである。
【0023】
【数1】
【0024】
ここで、「S」は符号部、「exp」は指数部、及び「fraction」は仮数部を示しており、図3のように2進数の表示形式において、上位ビットから順にそれぞれ1ビット、11ビット、及び52ビット、合計64ビットから形成される。
【0025】
以下、IEEE754で標準化されている倍精度浮動小数点形式の数値データに基づいて各実施形態を記載するが、本発明は、特に注記するもののほか、64ビットの倍精度浮動小数点形式の数値データに限定されるものではなく、IEEE754で同様に標準化されている32ビットの単精度浮動小数点形式の数値データのみならず、この他多倍長精度の浮動小数点形式(例えば、128ビット)の数値データにも適用でき、符号部、指数部及び仮数部で上位から下位の順に構成される2進数のビット列で表現される浮動小数点形式の数値データ全般に適用できるものである。
【実施形態】
【0026】
第1実施形態
図4は、本発明の圧縮システムの概要を示すブロック図である。入力される複数の浮動小数点形式の数値データに対し、コンピュータの中央処理装置は、レジスタやキャッシュ・メモリを含むメモリ操作を行いながら、各構成要素において次のように動作する。
【0027】
入力列1は、連続して入力されるN個の浮動小数点形式の入力データAn(n=1,2,・・・,N)を示している(Nは1以上の整数)。入力データAnは、差分器4に順次入力されるとともに、遅延器2において1クロック分遅延されて遅延器2から結合される予測器3に入力される。予測器3では、入力データAnが差分器4に入力されるタイミングと同期して、既に入力されていた入力データA0〜A(n−1)(但し、A0は入力列に先行する仮想的なデータ)から予測される浮動小数点形式の予測データPnを予測して、予測器3から結合される差分器4に入力する。差分器4では、入力された入力データAn及び予測された予測データPnの各ビット列の差分(例えば、排他的論理和)を計算し、差分ビット列Dnとして出力する。
【0028】
なお、図5に示したとおり、ここでの予測データPnは、例えば、非特許文献2に開示される公知技術を適用して、入力データA0〜A(n−1)から予測することができ、また、差分ビット列Dnのビット列表現においては、予測的中率の高い上位ビットほど「0」の出現確率が高いと想定される(図2も参照)。
【0029】
当該差分器4に結合される圧縮器5において、以下の図6に詳述する本発明の圧縮処理を行い、
を行う(Mは任意の自然数である)。
【0030】
図6は、本発明の圧縮方式における圧縮器5内部の詳細を示すブロック図である。
【0031】
圧縮器5は、差分器4からの複数の差分ビット列Dnを所定の数(ここではM個)の単位の組でメモリにバッファリングするバッファ部51、バッファリングされた1組の各差分ビット列Dnについて、浮動小数点形式の符号部及び指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる1又はそれ以上のブロックに分割、及び当該分割されたブロックを上位から下位の順に組ごとに組み替えて連結を行い、先行ビット列としてバッファリングし、また、当該差分ビット列から上位ビット列を除いた下位ビット列を組ごとに連結して形成されるビット列を残余ビット列としてバッファリングする再構築部52、及び、当該先行ビット列に対して圧縮処理を行って出力する先行列圧縮部53を備えている。
【0032】
更に図6の再構築部52について説明すると、図7に示すような態様で、各データのビット列を上位から8ビット(1バイト)、4ビット(1/2バイト)、4ビット(1/2バイト)、及びそれ以外の48ビット(12バイト)の順にブロック分割し、上位ビット列のブロック(8ビット+4ビット+4ビット)および下位ビット列(48ビット)について、それぞれのブロックを組単位で組み替えて上位ブロックから順番に連結してメモリにバッファリングする、アドレス演算を行うアドレス再構築部521、先行ビット列をバッファリングする先行列バッファ522、及び残余ビット列をバッファリングする残余列バッファ523を備えている。
【0033】
図2のグラフで示したとおり、本構成は、連続して入力される複数の入力浮動小数点に対してそれぞれ予測される予測データのうち、上位の数バイト部分については比較的高い予測的中率で予測できるという特徴に着目したものであり、所定のM個の差分ビット列のうち当該部分をブロック単位でまとめて組み替えた上で圧縮処理することで従来のFPCと比べて圧縮率を向上させるものである。
【0034】
ここで、図7に示す先行ビット列及び残余ビット列の構成について更に詳細に説明する。なお、ここでは簡単のためにM=4として説明するが、これに限定されるものではなく、Mは任意の自然数とすることができる。
【0035】
差分器4から入力される複数のデータのうち、連続して入力される4個(即ち、M個)のデータのビット列(Dn〜D(n+3))がバッファ部51にバッファリングされる。ここで、各ビット列の上位2バイト(16ビット)は、符号部(上位1ビット)及びそれに続く指数部(11ビット)の計12ビットを含むものである。再構築部52では、各データのビット列を符号部(1ビット)と指数部(11ビット)を含む上位16ビット(2バイト)からなる上位ビット列、及びそれ以外の48ビット(6バイト)の下位ビット列に分離し、更に当該上位ビット列を8ビット(1バイト)の第1ブロック及び4ビット(1/2バイト)の2つの第2及び第3ブロックに分割する。ここで、2つの第2及び第3ブロックに分割しているのは、第1ブロック及び第2ブロックの合計12ビットが、符号部(上位1ビット)と指数部(11ビット)との合計12ビットに一致するようにするためである。図7では、第1ブロックがブロック〔1〕〜〔4〕、第2ブロックがブロック〔5〕〜〔8〕、そして第3ブロックがブロック〔9〕〜〔12〕である。なお、下位のブロックは、48ビット(6バイト)の下位ビット列でそのまま構成される(ブロックI〜IV)。
【0036】
再構築部では、更に、図7に示すように、上位ビット列及び下位ビット列について、各ブロックを組単位で組み替えて上位ブロックから順に連結し、64ビットの先行ビット列Li及び192ビットの残余ビット列Riとして形成して、メモリ(先行列バッファ522及び残余列バッファ523)にバッファリングする。即ち、形成される先行ビット列Liは、第1ブロック(ブロック〔1〕〜〔4〕)、第2ブロック(ブロック〔5〕〜〔8〕)、第3ブロック(ブロック〔9〕〜〔12〕)の順番で連結したものである。同様に、形成される残余ビット列Riは、ブロックI〜IVの順番で連結したものである。
【0037】
次いで、当該先行ビット列Liを先行列圧縮部53に入力し、図8に示すように圧縮先行ビット列(ζ+Ui)を形成する。即ち、形成された64ビットの先行ビット列Liについて、1ブロックを1バイト(即ち8ビット)として、先頭ブロックから値が零(0)の連続するブロック部分Ziとそれ以外のブロック部分Uiに分割し、Ziの連続ブロック数(バイト数)zをカウントする。当該連続ブロック数zに基づいて先行ビット列Liを圧縮して圧縮先行ビット列を形成する。M=4である場合には、例えば、次の表2に表すテーブルを参照することで、8×zビットを3ビットに圧縮する。
【0038】
【表2】
【0039】
例えば、先行ビット列Li全体が零(0)の場合には、64ビットの先行ビット列Liを3ビットにまで最大限圧縮することができる。そしてMが特に2の階乗(即ち、M=2m)のときは、M×16(ビット)の先行ビット列Liを最大(m+1)ビットにまで圧縮することができることになる。
【0040】
図8の例の場合、Ziの連続ブロック数zは、「2」である。このときの3ビットのζは、表2より、「001」と表される。即ち、64ビット(先行ビット列Li)のビット列を、3ビット(「001」;ζ)+48ビット(非零ブロック;Ui)の合計51ビットに圧縮することができている。
【0041】
第2実施形態
本発明による第2の実施形態では、第1の実施形態における先行ビット列Liの圧縮率を向上させるために、アドレス再構築部521において、更に、図9〜図11に示すブロックの入れ替え処理を行う。
【0042】
第1実施形態に基づく複数の浮動小数点形式の数値データに対するブロックへの分割及び組み替えに関する構成を実施する場合に、絶対値はほぼ等しいものの、符号部のビットのみが異なるような振動データに対する圧縮が不十分なものとなる場合があるという課題を解決することができる。
【0043】
図9に示すとおり、先行ビット列Liに対して、上位ブロックから順に非零ブロックがあるか検査し、また、下位ブロックから順に零ブロックがあるか検査し、それぞれブロックが存在し検出された場合には、ブロックの入れ替えを行う。これにより、先頭ブロックから値が零(0)の連続するブロック部分Ziを拡張し、かつ、それ以外のブロック部分Uiを短縮することができる。
【0044】
伸長されたブロック部分Z’iは、上述した表2の3ビットζに、入れ替えフラグ1ビット、及び入れ替えブロック位置を示すビット列(8ビット)を加えた合計12ビットのζ’に圧縮することができる。最終的には、先行ビット列Liは、当該12ビットのζ’にブロック入れ替え後のU’iを連結したブロックに圧縮することができる(M=4の場合)。ここでの入れ替え位置を示すビット位置は、2×Mビット長のビットマップであり、入れ替えたブロック位置に対応するビットを「1」とするものである。
【0045】
図10は、第2実施形態における先行ビット列Liの別の実施例を示している。当該実施例を図11のフローチャートと共に説明する。尚、図10においても、M=4とし、また、1ブロックは1バイトで構成し、簡単のために先行ビット列Li及びL’iは16進数で表示している。
【0046】
先行ビット列Liに対して、上位ブロック(ブロック1)から順に非零ブロックを検査する(S100)。ここでは、ブロック2が「80」であり、非零ブロックとして検出される(S110)。そして、先行ビット列Liに対して、下位ブロック(ブロック8)から順に零ブロックを検査する(S120)。ここでは、ブロック8が「00」であり、零ブロックとして検出される(S130)。この場合、それぞれの検査ブロック位置の関係が「2<8」を満たしていることから(S140)、ブロック2「80」とブロック8「00」とを入れ替えるように操作し(S150)、入れ替えフラグ・ビットを「1」にし(S160)、更に、入れ替えブロック位置ビット列の第2ビットと第8ビットをそれぞれ「1」にする(S170)。この処理の結果、ζ及びLiは、図10に示すζ’及びL’iのように更新される。
【0047】
引き続き、検査を繰り返して、ブロック3から順に非零ブロックを検査していき、ブロック5の「01」を検出する(S100及びS110)。また、ブロック7から順に零ブロックを検査していき、ブロック6の「00」を検出する(S120及びS130)。そして、それぞれの検査ブロック位置の関係が「5<6」であるので(S140)、同様に、これらのブロックを入れ替えるように操作し(S150)、入れ替えフラグ・ビットを「1」にして(S160)、更に入れ替えブロック位置ビット列の第5ビット及び第6ビットをそれぞれ「1」にする(S170)。この処理の結果、ζ’及びL’iは図10に示すζ’’及びL’’iのように更新される。
【0048】
引き続き、検査を繰り返して、非零ブロックとしてブロック6を、零ブロックとしてブロック5を検出するが(S100〜S130)、検査ブロック位置の関係が「6>5」となり(S140)、これはすでに検査済みであることを意味するものであるため、繰り返しの検査処理を抜け、入れ替え処理を完了(END)する。
【0049】
このような入れ替え処理により、第1実施形態では、先頭ブロックから値が零(0)の連続するブロック部分Ziのブロック数z=1であったものが、第2実施形態では、先頭ブロックから値が零(0)の連続するブロック部分Z’iのブロック数z’’=5とすることができ、圧縮率の向上に成功する。
【0050】
以上より、本実施形態では第1実施形態に対して圧縮率を更に向上させることができる。なお、上記入れ替え処理の各ステップは、一例を示しているに過ぎずこれに限定されることはない。即ち、ブロック同士を入れ替え、入れ替えフラグ・ビットを更新することができる処理であればどのような態様で実施してもよい。
【0051】
第3実施形態
本発明による第3の実施形態は、主に、上記第1実施形態における、予測器3及び差分器4を用いて複数の入力された入力データAn及び複数の予測された予測データPnの各ビット列の差分(例えば、排他的論理和)から複数の差分ビット列Dnを出力するという構成についての代替の実施の形態を示すものである。
【0052】
図12に示すとおり、本実施形態では、2つの予測器31、32を用いて2つの異なる方式で2種類の予測値を計算する。差分器41、42において、2つの差分値を計算して圧縮器5’に出力する。そして、圧縮器5’が備える比較部50において所定のルールに基づいて差分値を当該2つの差分値から選択し、どちらの差分値を選択したかを示す選択ビットと共にバッファ部51’(図示せず)に内部出力する。この結果、圧縮器5’からの圧縮出力C’iには、Mビット(この場合4ビット)の選択ビット列(選択信号)も含まれることになる。
【0053】
以下、図12〜図15を用いて詳細に説明する。
【0054】
第1実施形態においては、図5に示したとおり、入力データAnが比較器4に入力されるタイミングと同期して、入力されていた入力データA0〜A(n−1)から予測される予測データPnを予測器3で予測し、差分器4において、入力データAn及び予測データPnの各ビット列の差分(例えば、排他的論理和)を計算し、差分ビット列Dnとして出力している。これに対し、本実施形態においては、図12及び13に示すとおり、2つの予測器31、32を用いて同様に予測データPn及びQnをそれぞれ別々に予測し、当該2つの予測器31、32にそれぞれ結合される2つの差分器41、42を用いて入力データAnと予測データPn及びQnとの各ビット列の差分(例えば、排他的論理和)をそれぞれ計算して、差分ビット列Dn及びEnとして圧縮器5’にそれぞれ出力する。
【0055】
圧縮器5’では、まず、比較部50によって、差分ビット列Dn及びEnの比較・選択を行う。なお、当該比較・選択に際しては、所定のビット数からなるブロックに分割して処理を行うが、ここでのビット数は、1バイト(即ち8ビット)でも1ビットでもよく、任意の数とすることができる。ここでは、バイト単位でブロックを形成することを想定する。
【0056】
図14に8個のブロック(ブロック1〜8)からなる、64ビットの2つの差分ビット列Dn及びEnの具体例を示す。なお、各ブロックの値は簡単のため16進数で表示している。比較部50では、各差分ビット列に対し、値が零(0)となる零ブロックの数bをカウントし、当該零ブロック数bが大きい方の差分ビット列を選択する。図14の場合は、差分ビット列Dn及びEnの各零ブロック数bd(=4)及びbe(=2)の値より、値が大きい方の差分ビット列Dnを選択出力Fnとして出力する。その際、どちらの差分ビット列を選択したかを示す1ビットの選択信号Snを、例えばDnを選択した場合はSn=0、Enを選択した場合はSn=1として、併せて出力する。
【0057】
このように、予測器31、32での予測精度がより高いものに対する差分ビット列を、比較部で選択するように圧縮器を構成することにより、その後の圧縮処理における圧縮率を向上させることができる。
【0058】
図15は、本実施形態の圧縮器5’において、先行列バッファ522にバッファリングされた64ビットの先行ビット列Liの圧縮に係る構成を図示したものである。尚、ここでもM=4と仮定しており、先行ビット列Li自体は第1実施形態において説明したのと同様に構成される。また、当該先行ビット列Liから構成されるζ及びUiについても第1実施形態と同様である(図8参照)。先行ビット列Liは、このζに、1×4ビット(即ちMビット)の選択信号Sn〜S(n+3)を加えて圧縮することができる。
【0059】
本発明は、本実施形態における差分ビット列の選択に係る構成に、更に実施形態2における先行ビット列に対するブロックの入れ替えに係る構成を組み合わせることにより、より一層データの圧縮率を向上させることができる。
【0060】
なお、上述した差分ビット列Dn及びEnの比較・選択について、差分器41、42に結合するように配置された上記比較部50で比較・選択を実施するのに替えて、差分ビット列Dn及びEn両方に対してバッファ部及び再構築部での処理並びにバッファリングを実施し、及び、先行列バッファから比較部50を結合するように比較部50を配置して、当該比較部50で先行列バッファに対して同様の比較・選択の処理を行うように構成することも可能である。
【0061】
以上の実施形態1〜3においては、IEEE754に規定される倍精度浮動小数点形式の数値データのビット列に対して、ブロックの分割をバイト単位(即ち、8ビット単位)により実施するものであるが、本発明はこれに限定されるものではなく、IEEE754に規定されるように、浮動小数点形式の数値データが符号部、指数部及び仮数部を用いて表現され、かつ、2進数のビット列が上位からこの順序で構成されるものであれば任意のデータに対して実現することができ、また、図7に示した分割するブロックの単位も、先行列を構成する上位ビット列が符号部及び指数部を含むものであればよく、バイト単位に限定されず、任意のビット数でよい。即ち、符号部及び指数部のビット数で分割ブロックを構成してもよく、更には符号部及び指数部のビット数の約数で1ブロックを構成し、複数ブロックで符号部及び指数部を含む上位ビット列としてもよい。
【0062】
第4実施形態
上述した実施形態1〜3では、先行ビット列に対して圧縮処理を行う構成であったが、第4の実施形態では、更に、残余ビット列に対しても圧縮処理を行う。
【0063】
本発明は、上述のとおり浮動小数点形式の数値データの予測困難性に着目したものであり、これを前提とした上で浮動小数点形式の数値データの圧縮率を向上させるものである。
【0064】
これに対し、同じ値のデータが連続するような一般に容易に予測可能とされるデータに対してこのような圧縮方式を適用した場合には、先行技術文献に記載されるような従来技術を適用した場合と比べて圧縮率が同等若しくはそれ以下になることも想定される。
【0065】
そこで、本実施形態では、このような容易に予測可能な浮動小数点形式の数値データが入力された場合でも圧縮率を向上させるため、更に、残余ビット列に対して、以下に説明する圧縮方式を適用することにより、圧縮率を向上させる。
【0066】
図16は、本実施形態における浮動小数点形式の数値データの圧縮システムを表すブロック図である。図6と比べて、残余列圧縮部54が追加されている。残余列圧縮部54は、残余列バッファ523にバッファリングされている残余ビット列の入力を受け、圧縮処理を行って圧縮出力をするものである。尚、残余列圧縮部54以外の各構成要素については、上述の実施形態1〜3に基づいて実現することができる。
【0067】
以下に、図17〜図18を用いて残余列圧縮部54における残余ビット列Riに対する圧縮方式について説明する。尚、上述のとおり、残余ビット列RiはM個の48ビット(即ち、6バイト)のビット列で構成される(図7参照)。
【0068】
図17は、残余列圧縮部54において、残余ビット列Riについて
をバッファリングしてまとめて連結し、残余ビットの集合列Rを形成する構成について記載している。ここでは、残余ビット列RiにおけるM個の6バイト列をr(i,1)〜r(i,M)としている。このようにして形成される残余ビット集合列Rは、6×Nバイト長のものとなる。残余ビット集合列Rに対し、図18に示すように6バイトの
の中から零(0)が6バイト連続する(即ち、値が0)もの、又は零(0)が5バイト含まれるものを抽出して、この抽出した位置を示す位置列Hを形成する。尚、零(0)が5バイト含まれるr(i,j)については、当該r(i,j)内の非零(0でない)となるバイトの位置、及びそのビット列を別途記憶する。図18においては、r(i0,1)及びr(i1,3)が、零(0)が6バイト連続するもの又は零(0)が5バイト含まれるものに該当し、これらの位置をH1及びH2として位置列Hを生成する。
【0069】
より具体的には、H1=M×(i0−1)+1、H2=M×(i1−1)+3の値から成る位置列Hを形成することになる。ここで、位置列Hの各構成要素は、nhバイト長となる。nhは、位置を記憶するために必要な容量であり、6バイトより小さくて済むようにする。
【0070】
一方、残余ビット集合列Rは、当該残余ビット集合列Rから、これらr(i0,1)及びr(i1,3)を削除することで圧縮され、圧縮残余ビット集合列R’が形成される。
【0071】
この結果、当初6×Nバイト長だった残余ビット集合列Rは、(6×N−2×6)バイト長の圧縮残余ビット集合列R’に圧縮することができる。圧縮残余ビット集合列R’及び位置列Hを圧縮出力として出力することで圧縮処理は終了する。
【0072】
本発明は、本実施形態において説明した残余ビット列に対する圧縮処理を、実施形態1〜3で記載した先行ビット列圧縮処理と併せて実施することで、特に、予測が容易な浮動小数点形式の数値データが連続して入力されるような場合に有効なものとなる。
【0073】
なお、本実施形態における位置列Hは、特定のr(i,j)の絶対位置を構成要素とするものであり、各構成要素は6バイトより小さい値で構成されるものであるが、特に実装上の観点からは、絶対位置ではなく相対位置として1バイトで各値を表現することができるようにし、当該相対位置、非零バイトr(i,j)の位置、非零バイトr(i,j)のビットパターンの3バイトを一組として非零バイトr(i,j)の出力とするようにすることもできる。更に、相対位置列に同じ値が連続して含まれる場合には、例えば、ランレングス法による圧縮手法を適用することにより、更なる数値データの圧縮が可能となる。
【0074】
以上、本発明の第1実施形態〜第4実施形態に係る連続して入力される複数の浮動小数点形式の数値データの圧縮方式について説明した。これらの実施形態の説明から分かるとおり、本圧縮方式は可逆式の圧縮方式であり、入力データAn(n=1,2,・・・,N)に対する
について、i=1,2・・・の順に圧縮動作と逆動作を行うことで、圧縮出力Ciを伸長して入力データAn(n=1,2,・・・,N)を復元することが可能である。
【0075】
圧縮結果
【表3】
【0076】
表3は、上述した表1に本願発明の一実施形態に基づいて実装し取得したデータを追加したものである。表3のとおり、本願発明の浮動小数点データの圧縮方式は、従来技術のFPC方式と比較すると、相対的に圧縮率の向上を実現することができている。
【産業上の利用分野】
【0077】
本発明の圧縮及び伸長システムは、連続して入力される複数の浮動小数点形式の数値入力データを効果的に圧縮してデータを取り扱うことができるため、大規模データを特にIEEE754に規定される倍精度浮動小数点形式において処理し、メモリに記憶する必要があるようなアプリケーションにおいて、有利なものとなる。
【0078】
具体的には、(i)表計算ソフトウェアにおいてセルに記憶する大規模データを浮動小数点形式の数値データとして記憶する場合、(ii)科学技術計算ソフトウェアの計算経過を主記憶内に保存する場合、(iii)フライトレコーダやドライブレコーダにおいて処理される実時間データのログを圧縮して記憶する場合、宇宙観測機から地球への通信といった狭帯域通信路において大規模データの通信を必要とする場合に、本発明によるシステム及び方法は特に有効なものとなる。
【特許請求の範囲】
【請求項1】
連続して入力される複数の入力データを各前記入力データに対する予測データに基づいて圧縮するシステムであって、
前記入力データ及び前記予測データの浮動小数点形式が、所定のビット数を有する符号部、指数部及び仮数部の順で表される2進数のビット列からなるように構成され、
前記入力データのビット列及び前記予測データのビット列のそれぞれの差分ビット列を所定の数の単位の組でバッファリングするバッファ部と、
前記バッファリングされた差分ビット列のそれぞれから、前記符号部及び前記指数部に対応するビット列部分を含む所定の数のビット数からなる上位ビット列を、所定のビット数からなる1以上のブロックに分割、及び該分割されたブロックを上位から下位の順に前記組ごとに組み替えて連結を行うことにより、先行ビット列としてバッファリングする再構築部と、
前記バッファリングされた先行ビット列ついて、先頭ブロックからの値が零となるブロックの連続数に基づき前記先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮部と、を含むシステム。
【請求項2】
請求項1に記載のシステムにおいて、
前記再構築部が、更に、前記連結が行われた先行ビット列に対して、上位のブロックから順に値が非零となるブロックを検査し、及び下位のブロックから順に値が零となるブロックを検査し、当該非零ブロック及び当該零ブロックがそれぞれ検出された場合には、これらを入れ替えるように構成され、
前記先行列圧縮部において形成される前記圧縮先行ビット列が、更に、前記入れ替えたブロックの位置を示すビット列を含む、システム。
【請求項3】
請求項1又は2に記載のシステムにおいて、前記予測データが第1の予測データ及び第2の予測データを含み、前記システムは、更に、
前記バッファ部においてバッファリングされる前記差分ビット列が、前記入力データのビット列と前記第1予測データ及び前記第2予測データのビット列とのそれぞれの差分による第1の差分ビット列及び第2の差分ビット列から選択されて、前記バッファ部に出力される比較部を含み、
該選択は、前記第1差分ビット列及び前記第2差分ビット列がそれぞれ備える前記所定のビット数のブロックの数に基づいて行われる、システム。
【請求項4】
請求項1から3のいずれか1項に記載のシステムにおいて、前記入力データ及び前記予測データが、IEEE754に規定される64ビットの倍精度浮動小数点形式のデータであり、
前記再構築部で分割されるブロックがバイト単位であり、更に、前記差分ビット列の上位ビット列が、1バイトの第1のブロック、1/2バイトの第2のブロック、及び1/2バイトの第3のブロックの順に分割して形成されることを含む、システム。
【請求項5】
請求項1から3のいずれか1項に記載のシステムにおいて、
前記上位ビット列のビット数が、前記符号部及び前記指数部を表すビット数であり、前記再構築部で分割されるブロックが、該ビット数の単位に基づいて構成される、システム。
【請求項6】
請求項1から5のいずれか1項に記載のシステムにおいて、
前記再構築部が、更に、前記差分ビット列から前記上位ビット列を除いた下位ビット列を組ごとに連結して形成される残余ビット列を、所定のビット数からなる第4のブロックの単位で分割するように構成され、更に、
該第4のブロックの単位で分割された各ブロックのうち、零が所定のバイト数以上含まれるブロックを抽出及び削除することに基づいて、前記残余ビット列を圧縮する残余列圧縮部を備える、システム。
【請求項7】
連続して入力される複数の入力データを各前記入力データに対する予測データに基づいて圧縮する方法であって、
該方法は、コンピュータによって実施され、
前記入力データ及び前記予測データの浮動小数点形式が、所定のビット数を有する符号部、指数部及び仮数部の順で表される2進数のビット列からなるように構成され、
前記入力データのビット列及び前記予測データのビット列のそれぞれの差分ビット列を所定の数の単位の組でメモリにバッファリングするバッファ・ステップと、
前記バッファリングされた差分ビット列のそれぞれから、前記符号部及び前記指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる1以上のブロックに分割、及び該分割されたブロックを上位から下位の順に前記組ごとに組み替えて連結を行うことにより、先行ビット列としてバッファリングする再構築ステップと、
前記バッファリングされた先行ビット列について、先頭ブロックからの値が零となるブロックの連続数に基づき前記先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮ステップと、を含み、
前記再構築ステップが、更に、前記連結された先行ビット列に対して、上位のブロックから順に値が非零となるブロックを検査し、及び下位のブロックから順に値が零となるブロックを検査し、当該非零ブロック及び当該零ブロックがそれぞれ検出された場合には、これらを入れ替えるように構成されることを特徴とする、方法。
【請求項1】
連続して入力される複数の入力データを各前記入力データに対する予測データに基づいて圧縮するシステムであって、
前記入力データ及び前記予測データの浮動小数点形式が、所定のビット数を有する符号部、指数部及び仮数部の順で表される2進数のビット列からなるように構成され、
前記入力データのビット列及び前記予測データのビット列のそれぞれの差分ビット列を所定の数の単位の組でバッファリングするバッファ部と、
前記バッファリングされた差分ビット列のそれぞれから、前記符号部及び前記指数部に対応するビット列部分を含む所定の数のビット数からなる上位ビット列を、所定のビット数からなる1以上のブロックに分割、及び該分割されたブロックを上位から下位の順に前記組ごとに組み替えて連結を行うことにより、先行ビット列としてバッファリングする再構築部と、
前記バッファリングされた先行ビット列ついて、先頭ブロックからの値が零となるブロックの連続数に基づき前記先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮部と、を含むシステム。
【請求項2】
請求項1に記載のシステムにおいて、
前記再構築部が、更に、前記連結が行われた先行ビット列に対して、上位のブロックから順に値が非零となるブロックを検査し、及び下位のブロックから順に値が零となるブロックを検査し、当該非零ブロック及び当該零ブロックがそれぞれ検出された場合には、これらを入れ替えるように構成され、
前記先行列圧縮部において形成される前記圧縮先行ビット列が、更に、前記入れ替えたブロックの位置を示すビット列を含む、システム。
【請求項3】
請求項1又は2に記載のシステムにおいて、前記予測データが第1の予測データ及び第2の予測データを含み、前記システムは、更に、
前記バッファ部においてバッファリングされる前記差分ビット列が、前記入力データのビット列と前記第1予測データ及び前記第2予測データのビット列とのそれぞれの差分による第1の差分ビット列及び第2の差分ビット列から選択されて、前記バッファ部に出力される比較部を含み、
該選択は、前記第1差分ビット列及び前記第2差分ビット列がそれぞれ備える前記所定のビット数のブロックの数に基づいて行われる、システム。
【請求項4】
請求項1から3のいずれか1項に記載のシステムにおいて、前記入力データ及び前記予測データが、IEEE754に規定される64ビットの倍精度浮動小数点形式のデータであり、
前記再構築部で分割されるブロックがバイト単位であり、更に、前記差分ビット列の上位ビット列が、1バイトの第1のブロック、1/2バイトの第2のブロック、及び1/2バイトの第3のブロックの順に分割して形成されることを含む、システム。
【請求項5】
請求項1から3のいずれか1項に記載のシステムにおいて、
前記上位ビット列のビット数が、前記符号部及び前記指数部を表すビット数であり、前記再構築部で分割されるブロックが、該ビット数の単位に基づいて構成される、システム。
【請求項6】
請求項1から5のいずれか1項に記載のシステムにおいて、
前記再構築部が、更に、前記差分ビット列から前記上位ビット列を除いた下位ビット列を組ごとに連結して形成される残余ビット列を、所定のビット数からなる第4のブロックの単位で分割するように構成され、更に、
該第4のブロックの単位で分割された各ブロックのうち、零が所定のバイト数以上含まれるブロックを抽出及び削除することに基づいて、前記残余ビット列を圧縮する残余列圧縮部を備える、システム。
【請求項7】
連続して入力される複数の入力データを各前記入力データに対する予測データに基づいて圧縮する方法であって、
該方法は、コンピュータによって実施され、
前記入力データ及び前記予測データの浮動小数点形式が、所定のビット数を有する符号部、指数部及び仮数部の順で表される2進数のビット列からなるように構成され、
前記入力データのビット列及び前記予測データのビット列のそれぞれの差分ビット列を所定の数の単位の組でメモリにバッファリングするバッファ・ステップと、
前記バッファリングされた差分ビット列のそれぞれから、前記符号部及び前記指数部に対応するビット列部分を含む所定のビット数からなる上位ビット列を、所定のビット数からなる1以上のブロックに分割、及び該分割されたブロックを上位から下位の順に前記組ごとに組み替えて連結を行うことにより、先行ビット列としてバッファリングする再構築ステップと、
前記バッファリングされた先行ビット列について、先頭ブロックからの値が零となるブロックの連続数に基づき前記先行ビット列を圧縮して圧縮先行ビット列を形成する先行列圧縮ステップと、を含み、
前記再構築ステップが、更に、前記連結された先行ビット列に対して、上位のブロックから順に値が非零となるブロックを検査し、及び下位のブロックから順に値が零となるブロックを検査し、当該非零ブロック及び当該零ブロックがそれぞれ検出された場合には、これらを入れ替えるように構成されることを特徴とする、方法。
【図2】
【図3】
【図4】
【図5】
【図6】
【図1】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図3】
【図4】
【図5】
【図6】
【図1】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【公開番号】特開2012−253696(P2012−253696A)
【公開日】平成24年12月20日(2012.12.20)
【国際特許分類】
【出願番号】特願2011−126795(P2011−126795)
【出願日】平成23年6月6日(2011.6.6)
【出願人】(506209422)地方独立行政法人 東京都立産業技術研究センター (134)
【Fターム(参考)】
【公開日】平成24年12月20日(2012.12.20)
【国際特許分類】
【出願日】平成23年6月6日(2011.6.6)
【出願人】(506209422)地方独立行政法人 東京都立産業技術研究センター (134)
【Fターム(参考)】
[ Back to top ]