对于这种情况,什么是好的(解)压缩例程
-
20-09-2019 - |
题
我需要一个针对受限资源环境(例如具有以下特征的二进制(十六进制数据)嵌入式系统)进行优化的快速解压缩例程:
- 数据是面向8位(字节)的(数据总线是8位宽)。
- 字节值的范围并非统一为 0 - 0xFF,而是在每个数据集中具有泊松分布(钟形曲线)。
- 数据集预先固定(烧录到Flash中)并且每组很少> 1 - 2MB
压缩可能需要尽可能多的时间,但在最坏的情况下,一个字节的解压应该花费 23uS,内存占用最小,因为它将在资源受限的环境(如嵌入式系统)(3Mhz - 12Mhz 内核,2k 字节 RAM)上完成。
什么是好的减压程序?
基本的运行长度编码似乎太浪费了 - 我可以立即看到,向压缩数据添加标头部分以使用未使用的字节值来表示经常重复的模式将带来惊人的性能!
对于我来说,只投入了几分钟,肯定已经有来自热爱这个东西的人的更好的算法了?
我想要一些“随时可用”的示例在 PC 上进行尝试,以便我可以比较基本 RLE 的性能。
解决方案
当性能是唯一问题时我使用的两种解决方案:
- 利兹奥 拥有 GPL 许可证。
- 库兹夫 拥有 BSD 许可证。
- miniLZO.tar.gz 这是
LZO
, ,只是重新打包成更适合嵌入式开发的“缩小”版本。
两者都是 极其 解压时速度很快。我发现 LZO
将创建比以下稍小的压缩数据 liblzf
在多数情况下。您需要制定自己的速度基准,但我认为它们“基本上相同”。两者都比 zlib
, ,尽管压缩效果都不好(正如您所期望的那样)。
LZO
, , 尤其 miniLZO
, , 和 liblzf
都非常适合嵌入式目标。
其他提示
如果您有预设的值分布,这意味着每个值的概率在所有数据集上都是固定的,则可以使用固定代码创建霍夫曼编码(代码树不必嵌入到数据中)。
根据数据,我会尝试使用固定代码或 lz77 的霍夫曼(请参阅布莱恩的链接)。
因为这似乎是音频,所以我会考虑差分 PCM 或 ADPCM 或类似的东西,这会将其减少到 4 位/样本,而不会造成太大的质量损失。
使用最基本的差分 PCM 实现,您只需存储当前样本和累加器之间的 4 位有符号差,并将该差值添加到累加器并移至下一个样本。如果差值超出 [-8,7],则必须限制该值,并且累加器可能需要几个样本才能赶上。解码速度非常快,几乎不使用内存,只需将每个值添加到累加器并将累加器输出作为下一个样本。
对基本 DPCM 的一个小改进是使用查找表将 4 位值解码到更大的非线性范围,在信号变得更大和更高的音调时帮助累加器更快地赶上,其中它们仍然是 1 接近零,但以更大的增量增加到极限。和/或您可以保留其中一个值来切换乘数。由编码器决定何时使用它。通过这些改进,您可以实现更好的质量,或者每个样本使用 3 位而不是 4 位。
如果您的设备具有非线性 μ 律或 A 律 ADC,则可以通过 8 位采样获得与 11-12 位相当的质量。或者您可以在解码器中自己完成。 http://en.wikipedia.org/wiki/M-law_algorithm
可能有一些便宜的芯片已经可以为您完成所有这些工作,具体取决于您正在制作的产品。我还没有调查过任何。
您应该使用带有命令行开关的压缩软件工具或可以尝试不同算法的压缩库来尝试不同的压缩算法。使用适合您的应用的典型数据。然后您就知道哪种算法最适合您的需求。
我在嵌入式系统中使用 zlib 作为引导加载程序,在启动时将应用程序映像解压缩到 RAM。该许可证非常宽松,没有 GPL 废话。它确实进行了一次 malloc 调用,但在我的例子中,我只是将其替换为返回指向静态块的指针的存根和相应的 free() 存根。我通过监视其内存分配使用情况来获得正确的大小来做到这一点。如果你的系统可以支持动态内存分配,那么就简单多了。