ストリームデータ圧縮技術 ASE Coding

LCA-DLTの圧縮モジュールはシンボルよりも短いビット列に圧縮できない。たとえ、単純なデータパターン（例えばすべて0）が入力されても、シンボルよりも小さい単位に圧縮できない。この弱点はストリームデータ圧縮の研究を始めた当初からの問題であり、LCA-DLTの開発と同時並行的に進めてきた課題であった。この問題を解決する新方式ASE Coding (Adaptive Stream-based Entropy Coding)を開発した。

圧縮されたあとのデータが可変長にできることをシャノンの平均情報量をヒントとした。シャノンの平均情報量ではシンボルの出現確率 に関し、 の総和を取ることで、データ全体を表すビット数(エントロピー)を得る。一方、LCA-DLTで、ストリームのあるシンボルを圧縮しているときの変換テーブルの使用エントリ数 に対し、ストリームのある区間の の平均を求めると、同一区間のシャノンの平均情報量に漸近することを発見した。すなわち、データストリームの任意の局所の情報量(データを表現するビット数)を変換テーブルの状態で表現でき、さらに、その情報量は全シンボルを表すビット数以下になる。この情報量の特性を用いて、データストリームを遅延なく圧縮・解凍できるASE Codingを開発した。

圧縮器は変換テーブル、エントロピー計算、シリアライザから構成される。変換テーブルは入力されたシンボルと比較してヒットしない場合はその先頭にプッシュし、ヒットするときには、そのエントリを先頭に移動して、他をプッシュすることで、常に登録またはヒットしたシンボルが先頭から保持される。このテーブルにシンボルがヒットする場合は圧縮でき、圧縮されたシンボルはテーブルのインデクスをとる。さらに、そのインデクスをエントロピー計算によりビット削減する。上述の を計算することで、疑似エントロピーを得る。

例えば、右図のようにテーブル数が16のときインデクス幅は4ビットで表されるが、使用しているエントリ数は3であるため、 となり、インデクスの下位2ビットで表現できる。この圧縮シンボルにCmarkを付加し、合計3ビットで圧縮シンボルが構成されシリアライザへと渡される。シリアライザは圧縮器の出力のビット幅に変換し伝送路へと出力する。解凍器は、デシリアライザ、エントロピー計算、変換テーブルからなり、圧縮器と同様の動作をする。デシリアライザは伝送路のビット幅でデータを受信し、その1ビット目がCmarkであるので、0であれば、続くシンボル幅を取り出してテーブルへと登録する。1のときはエントロピー計算を参照して、その数値に等しいビット数を取り出し、上位に0を埋めることで、テーブルのインデクスとして検索し、テーブル内のシンボルを解凍器から出力して元のデータに復号する。

以上のようにASE Codingは流れるデータストリームを止めることなく圧縮・復号化を実行でき、データストリームのシンボルよりも短いビット列に圧縮する、可変長での圧縮が可能である。さらに、圧縮器・解凍器のいずれの処理もハードウェアと親和性が高く、高速動作が可能である。

また、LCA-DLTと同程度の圧縮性能を示す構成のハードウェア実装が、それに比べて1／10のサイズに縮小できる。性能を検証するために、上述したHDMIの映像をリアルタイムに圧縮するASE Codingの回路をFPGAを用いて実装したところ、初期遅延は4サイクル、そのあとは毎サイクルでの圧縮処理が可能で、200MHzで動作し、LCA-DLTに比べ良好な圧縮率を維持することを確認している。

Research articles in Journals and Magazines

  1. Shinichi Yamagiwa, Yuma Ichinomiya. Stream-Based Visually Lossless Data Compression Applying Variable Bit-Length ADPCM Encoding, Sensors, 4602, (2021-07-05), DOI:10.3390/s21134602
  2. Shinichi Yamagiwa, Koichi Marumo, Suzukaze Kuwabara. Exception Handling Method Based on Event from Look-Up Table Applying Stream-Based Lossless Data Compression, Electronics, 240, (2021-01-21), DOI:10.3390/electronics10030240
  3. Shinichi Yamagiwa, Suzukaze Kuwabara. Autonomous Parameter Adjustment Method for Lossless Data Compression on Adaptive Stream-Based Entropy Coding, IEEE Access, 186890--186903, (2020-10-08), DOI:10.1109/access.2020.3029705
  4. Shinichi Yamagiwa, Eisaku Hayakawa, Koichi Marumo. Stream-Based Lossless Data Compression Applying Adaptive Entropy Coding for Hardware-Based Implementation, Algorithms, 159, (2020-06-30), DOI:10.3390/a13070159

Conference Proceedings

  1. Taiki Kato, Shinichi Yamagiwa, Koichi Marumo. Performance Enhancement of Stream-Based Decompression Process by Notifying Compression Buffer Size, 2023 IEEE Symposium on Computers and Communications (ISCC), 491-494, (2023-08-28), DOI:10.1109/iscc58397.2023.10218261
  2. Shinichi Yamagiwa, Eisaku Hayakawa, Koichi Marumo. Adaptive entropy coding method for stream-based lossless data compression, Proceedings of the 17th ACM International Conference on Computing Frontiers, 265–268, (2020-05-11), DOI:10.1145/3387902.3394037

獲得予算

  1. （受託研究）科学技術振興機構 さきがけ（IoTが拓く未来・徳田英幸総括）「高性能ストリームデータ圧縮技術の開発」（研究代表者　山際伸一）、2020年11月１日　～　2024年３月３１日
  2. （科研費）基盤研究B　代表, “大局的エントロピー予測によるデータ圧縮の最適化技法の開発”, 2020-2023,（研究代表者　山際伸一）
  3. （科研費）挑戦的研究（萌芽）　代表, “知覚的エントロピー劣化によってストリームデータの圧縮率の制御は可能か？”, 2018-2021, （研究代表者　山際伸一）