4

次の特性を持つバイナリ (16 進データ) の組み込みシステムなど、リソースが制限された環境向けに最適化された FAST 解凍ルーチンが必要です。

  1. データは 8 ビット (バイト) 指向です (データ バスは 8 ビット幅)。
  2. バイト値の範囲は 0 ～ 0xFF で均一ではありませんが、各 DataSet にはポアソン分布 (ベル カーブ) があります。
  3. データセットは高度に固定されており (フラッシュに焼き付けられる)、各セットが 1 - 2MB を超えることはめったにありません

圧縮には必要なだけの時間がかかる場合がありますが、組み込みシステム (3Mhz - 12Mhz コア、2k バイト RAM) のような制限されたリソース環境で実行されるため、メモリ フットプリントが最小の最悪のシナリオでは、1 バイトの解凍に 23uS かかります。 .

適切な減圧ルーチンは何ですか?

基本的なランレングス エンコーディングは無駄が多すぎるようです。圧縮データにヘッダー セットを追加して、未使用のバイト値を使用して繰り返しパターンを表現すると、驚異的なパフォーマンスが得られることがすぐにわかります。

ほんの数分しか投資していない私と一緒に、このようなものを愛する人々からのはるかに優れたアルゴリズムがすでに存在しているに違いありません?

基本的なRLEと比較してパフォーマンスを比較できるように、PCで試してみる「すぐに使える」例をいくつか用意したいと思います。

4

6 に答える 6

4

値の事前分布がある場合、つまり各値の妥当性がすべてのデータセットで固定されている場合は、固定コードを使用してハフマン符号化を作成できます（コードツリーをデータに埋め込む必要はありません）。

データに応じて、固定コードまたはlz77を使用してハフマンを試してみます（ブライアンのリンクを参照）。

于 2009-08-29T17:37:12.973 に答える
4

パフォーマンスが唯一の懸念事項である場合に使用する2つのソリューション：

  • LZOにはGPLライセンスがあります。
  • liblzfにはBSDライセンスがあります。
  • miniLZO.tar.gzこLZO​​れは、組み込み開発により適した「縮小」バージョンに再パックされただけです。

解凍すると、どちらも非常に高速になります。ほとんどの場合LZOよりもわずかに小さい圧縮データが作成されることがわかりました。liblzf速度については独自のベンチマークを行う必要がありますが、私はそれらを「本質的に等しい」と考えています。zlibどちらも（ご想像のとおり）圧縮もしませんが、どちらもよりも光年速くなります。

LZO、特にminiLZO、およびliblzf両方とも埋め込みターゲットに最適です。

于 2009-09-12T04:07:20.433 に答える
2

これはオーディオのように見えるので、差分PCMまたはADPCM、あるいは同様のものを検討します。これにより、品質を大幅に低下させることなく、サンプルあたり4ビットに削減されます。

最も基本的な差分PCM実装では、現在のサンプルとアキュムレータの間の4ビットの符号付き差を保存し、その差をアキュムレータに追加して次のサンプルに移動します。[-8,7]の外で差がある場合は、値をクランプする必要があり、アキュムレータが追いつくまでにいくつかのサンプルが必要になる場合があります。デコードはほとんどメモリを使用せずに非常に高速で、各値をアキュムレータに追加し、次のサンプルとしてアキュムレータを出力します。

基本的なDPCMに比べて、信号が大きくなりピッチが高くなったときにアキュムレータがより速く追いつくのを助けるための小さな改善は、ルックアップテーブルを使用して、4ビット値をより大きな非線形範囲にデコードすることです。 、ただし、限界に向かって大きく増加します。および/または値の1つを予約して、乗数を切り替えることができます。エンコーダーまでいつ使用するかを決定します。これらの改善により、品質を向上させるか、サンプルあたり4ビットではなく3ビットを使用することができます。

デバイスに非線形μ-lawまたはA-lawADCがある場合、8ビットサンプルで11〜12ビットに匹敵する品質を得ることができます。または、デコーダーで自分で行うこともできます。http://en.wikipedia.org/wiki/M-law_algorithm

あなたが作っているものによっては、すでにあなたのためにこれらすべてを行っている安価なチップがあるかもしれません。私は何も調べていません。

于 2009-08-29T20:10:49.797 に答える
2

頭に浮かぶ主な 2 つのアルゴリズムは、HuffmanとLZです。

最初は基本的に辞書を作成するだけです。ディクショナリのサイズを十分に制限すれば、かなり高速になるはずですが、圧縮率はあまり高くありません。

後者は、出力ファイルの繰り返し部分に後方参照を追加することで機能します。ファイル i/o を使用して後方参照を読み取るか、最近読み取ったデータのチャンクを RAM に保存する必要があることを除いて、これはおそらく実行にほとんどメモリを必要としません。

繰り返されるセクションが互いに接近する傾向がある場合は、LZ が最良の選択肢であると思います。あなたが言及したように、ハフマンは頻繁に繰り返される要素の辞書を持つことによって機能します。

于 2009-08-28T19:55:39.493 に答える
1

コマンドラインスイッチを備えた圧縮ソフトウェアツール、またはさまざまなアルゴリズムを試すことができる圧縮ライブラリを使用して、さまざまな圧縮アルゴリズムを試す必要があります。アプリケーションの一般的なデータを使用します。次に、ニーズに最適なアルゴリズムがわかります。

于 2009-08-29T17:54:41.800 に答える
1

起動時にアプリケーション イメージを RAM に解凍するブートローダーとして、組み込みシステムで zlib を使用しました。ライセンスはかなり寛大で、GPL のナンセンスはありません。これは単一の malloc 呼び出しを行いますが、私の場合は、これを静的ブロックへのポインターを返すスタブと、対応する free() スタブに置き換えただけです。これは、メモリ割り当ての使用状況を監視して適切なサイズを取得することで行いました。システムが動的メモリ割り当てをサポートできる場合は、はるかに簡単です。

http://www.zlib.net/

于 2009-09-05T13:01:46.670 に答える