预测误差变长编码的数据压缩方法

预测误差变长编码的数据压缩方法

引用

CSDN

1.

https://blog.csdn.net/u012183892/article/details/117466842

在嵌入式生理信号数据采集和传输过程中，为了获取更精确信号特征，常会使用较高的采样率。但由于BLE，WiFi传输带宽的限制，有时候我们不得不对数据进行压缩后再传递。这样可以在传输同样数据量的数据，中包含更多的数据。所以这是一种以牺牲 MCU 运算效率为代价，降低存储内存占用、提高传输速率的常用方法。

一、问题背景

在某项目中，其数据特点是通道数多、采样率高，所以数据量很大。如果直接传输原始数据，对数据的传输带宽要求很高。为了满足要求，我们加入了这种预测误差+变长码的压缩方法，期望在同样的速度下，传输更大的数据量。

二、嵌入式常用压缩算法

在嵌入式中由于内存，运算速度等的限制，我们常用的压缩算法不可能很复杂。不可能使用pc中复杂的算法。压缩算法的原理主要分为以下两个步骤：

1. 数据去冗余：根据信息论的基本观点，如果两个数互相关联，则这两个数所包含的总信息量小于这两个数据各自包含的信息量之和，即这两个数据中有信息冗余，可以进行压缩。

对于生理信号这类信号，数据都是连续的。后面的数中包含信息的一部分，可以从前面一些数据中提取。所以可使用：一阶增量式（保存和前一个数的差值）、二阶预测（用两个点预测第三个点）、三阶预测等。

2. 选择合适的编码方式：基本原理就是根据待压缩数据的出现频率，频率高的数据用短码表示，不常使用数据的用长码表示。如代表的：哈夫曼编码。另外可以使用商余表示的哥伦布编码等。

三、预测误差压缩原理

压缩的整体思路：

对于脑电，ECG，BCG这类信号，在时域上一般都是连续的，即前后几个点的变化一般不会很大。所以根据此原理，我们可先使用前两个数计算出第三个数的预测值，然后将该预测值与第三个数的实际值相减，这样就得到了「预测误差」。最后将「预测误差」用变长码编码并保存，得到的数据就是我们压缩后的数据。

对于解压，我们只需要用相同的方法，从头开始得到「预测误差」，然后带入预测函数，就能得到实际压缩前的数据了。依次迭代循环，就能得到所有的原始数据。需要注意对于一段压缩数据，我们不能从中间任意位置开始解压，每次只能从头开始解压。

3.1 预测误差计算方法

我们这里考虑到MCU的运算速率，所以仅使用两个点去预测，实测已经足够了。如果想进一步提高压缩率，可以使用更高阶的预测函数，原理一样这里故不再赘述。

图1 预测误差示意图

假设原始数据为一数组，元素值排列为：y1，y2，y3.....。预测的方式是，使用y1，y2的值，得到预测值 y3'。预测公式为：

然后使用 y3' 和实际的 y3 相减，得到的就是我们的「预测误差」x：

所以我们只需要知道 x 的值就能反推出实际 y3 的值，而且一般情况下 x 的值相对于y3本身的值是小很多（证明略），所以我们实际只需要保存 x 的值，就能复原原来的数组。

需要注意的是 x 是有正负的。所以后面的编码也需要考虑符号位的表示。

所以每组数据的前两个数，我们不会压缩，从第三个数开始存放压缩后的数据。

图2 原始数据存放示意图

图3 压缩后数据存放示意图

3.2 固定整形编码

这是变长前缀编码的一种实现方式。这种编码主要的思路是：对于 int32_t 的原始数据，进过「预测」后误差一般已经很小了。所以前面对于正数前面有一堆0，对于负数前面有一堆1。这明显是一种浪费，所以我们用尽可能少的字节去表示这个数。

具体方法：我们使用头个字节的前两 bit 指示该数据后续 byte 的个数（最多4字节），后面依旧使用原来的二进制去编码，带符号位。

由于我们用前2bit为前缀，所以实际的数据范围会有所缩小。所以不能压缩超过下表范围的数据，最大可压缩数据范围：-2^29~2^29-1。

举例：对于一个int32_t 类型的数字：100

压缩前：00000000 00000000 00000000 01100100 （4byte）

压缩后：01000000 01100100（2byte）

可以看到前面2byte的数据都省去了，所以这种压缩编码适合数据本身很小（可以理解为变化小），但保存数据类型很大的这类数明显。

NOTE：这种压缩的极限就是1byte，而且对于上下边缘的数据可能还会越压缩越大的问题。

比如：对于 uint8_t 类型的数字：255

压缩前：11111111 （1byte）

压缩后，由于超过1byte数据范围，所以需要2byte去保存：

01000000 11111111（2byte）

3.3 Rice莱斯编码

Rice编码是将数据用商和余的方式进行编码。所以首先需要为待压缩的这组数据，选定一个合适的 系数M。M 的选择会影响除数的值。我们这里使用系数 M 的计算方式为：

M = 2^k；

k = log2（sum（abs（x））* 0.7）；

即 k 等于这组待压缩数据的「预测误差」绝对值的和乘以系数0.7，然后对2取对数。得到的 k 可能有正有负。我们限定：k 需要向上取正整数，即 ≥ 1。然后使用 k 得到除数M。

莱斯编码的步骤：

1. 对商编码；
   商数：q = x / M;
   对 q 进行一进制编码，得到u。编码值可以是0，也可以是1，和后面分隔符能区分开就行。如我们这里使用0编码。即q的值是多少就用多少个0表示，最后使用一个 1 分割。

需要注意：如果出现一个数据，远大于 M 的话，对商的编码可能会变得异常的长！

1. 对余编码；
   余数：r = abs(x) % M;
   对余数 r 进行二进制编码，得到b。

如下，当 k = 3时。

1. 对符号位编码；
   如果x位负数，f=1，否则 f=0.
2. 合并;
   将上述的三部分合并在一起就是我们最后的编码值 c，排列顺序不重要。只要压缩，解压的顺序保持一致就行。我这里使用 “符号位+余数+商” 的顺序：
   c = (f, b, u);

Rice编码举例说明：

已知：待压缩数据 x = 10，k=3；

所以：除数 M = 2^k = 8。

1.得到商：q = x / M = 10 / 8 = 1；
所以对q 编码：01。
2.得到余数：r = abs(x) % M = 2；
对 r 编码：010.
3.符号为正数，所以f = 0。
4.合并 c = 0 010 01；

同理：-15压缩后为：1 111 01；（可自己验证下）

由此可见，一个1byte的数据 10就被压缩为了一个6bit的数据c。这就是变长压缩的基本原理。然后将这个bit流挨个写入压缩后的字节流中，就完成了数据的压缩。如果数据都很小，莱斯编码可有很好的压缩率。

四、代码实现

4.1 整体的压缩逻辑

主要思路：先使用二阶预测得到待压缩数据的「预测误差」数组，然后使用一个Rice测试函数，只计算 Rice 编码后的长度（先不写bit流）。判断编码后长度是否超过原数据长度，是就改用固定整形编码，否则使用Rice编码，开始写bit流。如果固定整型还是超过原始数据长度，则不压缩。

由此对于原始数据，可能有奈斯编码，整型编码，和不压缩三种情况。我们可以通过压缩后的返回值 K 去判断。在数据的传输过程中，K也要和压缩数据一起传输，方便解压程序选择正确的解压算法。

图4 软件流程图

4.2 分组压缩

实际的数据采集中，我们的压缩数据也要实时的传输。根据对实时性的要求高低，可以选择合适的数据长度，如 1s 数据为一组。每组压缩数据的第一个字节用来存储上述的 K 值。后面即为压缩后的数据。

4.3 源代码

// todo

五、测试

各通道数据实际的压缩率表现：

图3 压缩数据对比表

图3 压缩数据对比曲线

参考链接

1. Golomb coding
2. Huffman coding
3. R. F. Rice. Some Practical Universal Noiseless Coding Techniques. Technical Report 79/22, Jet Propulsion Laboratory, 1979.
4. Rice Coding
5. github C语言压缩开源项目GitHub - oz123/awesome-c: A curated list of awesome C frameworks, libraries, resources and other shiny things. Inspired by all the other awesome-... projects out there.