転送帯域を増すためにzlib圧縮を学んでみました。

先日、Uartを使えるようになったのですが、転送帯域が115Kbpsとなかなかに遅いです。転送速度を上げるために、パラレルにしたり、周波数を上げたりすることが考えられます。

一方で、データに目を向けてみると、圧縮して送信することで、転送帯域を上げることが可能です。今回はデータを圧縮転送帯域を増すためにzlib圧縮を学ぶことにしたので、備忘録として記載します。

まずは以下サイトで総論を学びました。

今更だけど、圧縮についてまとめてみたい | PINTO!
- 可逆圧縮では、ハフマン符号と辞書を組み合わせたLZ77が主流であることがわかりました。
- zlibもgzipもZIPもDeflateを使っていることがわかりました

次に以下サイトでPythonでzlib, glibで圧縮する方法を学びました。 Pythonだと以下のようなコマンドで簡単に圧縮を試せることがわかりました。

import zlib
s = b'wwww'
t = zlib.compress(s)

ただ、↑のtをprintすると以下のような意味不明な出力を吐きました。wは0x77なのですが、値がまったく出てきていません。

0000: 2f2b9c78
0004: 00072f2f
0008: dd01aa04

↑の調査のために、ZLIBのフォーマットをRFC1950(ZLIBのフォーマット定義)調べることにしました。すると、以下がわかりました。

先頭の2byteはCMFとFLG。↑のログだとCMF(0x78-> CINFO=7:32K window CM(Compression method)=8: deflate), FLG(0x9C)
残りは圧縮データ(t[2:-4])
RFC 1951 DEFLATE Compressed Data Format Specification で定義
末尾の4byteはChecksum

というわけで、データ圧縮の定義はRFC1951に記載があることがわかりました。

各ブロックは、LZ77 アルゴリズムとハフマン符号化の組み合わせで圧縮されます。
各ブロックは、次のデータを含む 3 ビットのヘッダーから始まります。
第1ビット BFINAL
次の2ビット BTYPE

ただ、↑を見ても正直よくわからないので、解説サイトを調べてみたら、以下にたどり着きました。これも難しいのですが、何回か読んでいて少し理解しました。

0-255のリテラルデータ or 戻り距離
0x100(256)はブロックの終端
0x257-285の値は長さ符号
3.2.6. 固定ハフマン符号を使った圧縮 (BTYPE=01)に記載されているようにリテラル値は符号に割り当てられている('a'(0x61) ->0x91になる)

また、最後に以下を見るといい感じで頭が整理されました。

Zlibによる圧縮を学んでみました。結局のところ、Zlib自体は先頭と末尾はヘッダとChecksumついているくらいで、まだ大丈夫かなでしたが、 Deflateについて難しすぎました。。

FPGAで動かすために、ハード化することも相当大変そうなので、もっと簡易化されたアルゴリズムを探さないと、というのが結論です笑