GPS定位数据压缩算法的设计与实现

1、GPS定位数据压缩算法的设计与实现摘要为了解决嵌入式车载系统存储空间小、定位数据量大的矛盾，根 据定位数据的特点，提出了专用于定全数据压缩的改进型半字节压缩算法。该算法是一种在原半字节压缩算法的基础上改进的算法，经过实际测 试，压缩比可达50。若将压缩预处理也折算法在内，总压缩比可达80以上，为车载系统节省了大量的存储资源。除此之外，也缩短了信道的占用时间，大大地缓解了向控制调度中心 上传数据的压力。关键词数据压缩数据格式压缩预处理半字节压缩算法嵌入式车载系 统般体积较小，无存储量大的硬盘等设备，系统程序、应用程序一般装在 或中。由于或等存储介质的价格相对台式机上广泛使用的硬盘、光盘等来说 是

2、非常昂贵的，因此，在幵发嵌入式系统的软件产品时必须将软件所占的 存储空间限制在一定的范围内。在车载系统的研发过程中，范文先生网收集整理主要需解决的问题是车载系统为了实现自导航，必须存储大量的定位数据每天需要存储约6 ；其二是这些数据还要通过信道上传到控制调度中心若通过短信业务发送， 每次160，则需要每分上传6次无疑，数据压缩是在不增加硬件成本的前提下，从软件的角度来充分 发挥系统现有资源的有效办法。 数据压缩方法种类繁多，可以分为无损压缩和有损压缩两大类。 无损压缩利用数据的统计冗余进行压缩。 数据统计冗余度的理论限制，般为 21 到 51。 这类方法广泛用于文本数据、程序和特殊应用场合的图

3、像数据如指纹 图像、医学图像等的压缩。有损压缩方法利用了人类视觉对图像中的某些频率成分不敏感的特 性，允许压缩过程中的损失一定的信息。虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影 响较小，却换来了大得多的压缩比。有损压缩广泛应用于语音、图像和视频数据的压缩。 目前现在的压缩算法很多，但不能直接用于嵌入式系统当中，这完全 由嵌入式系统的特点所决定。首先，用于嵌入式系统的数据压缩方法应是无损压缩方法。 其次，压缩代码和解码所需的信息代码必须足够短，否则就会失去压 缩的意义。还有，嵌入式系统的数据压缩必须结合具体的数据格式的特点，才能 进一步提高数据的压缩比。除此之外， 目前的压缩程

4、序的启动执行必须人为干扰， 不能自动执行， 因为它们是为文件系统设计的，而嵌入式系统的数据压缩必须能够自动执 行。1 数据格式板由变频器、信号通道、微处理器和存储单元等组成。 板的型号甚多，性能各异，但大多采用美国国家海洋电子协会制定的 -0183 通信标准格式。本系统选择的是美国公司的板。板语句的输入、输出是通过 232 串行接口完成的，其通信端口的数据 格式应该设置为 8 个数据位、 1 个起始位和 1 个停止位，校验方式选为无 奇偶校验，波特率设置为 4800 波特。-0183 通信标准的输出数据采用的是码，其内容包含了纬度、经度、 高度、速度、日期、时间、航向以及卫星状况等信息， 语句

5、有六种，包括，、 和。对于不同的用途，选用的语句记录也不同，例如嵌入式车载系统的使 用者只关心其日期和时间、 纠度、面速度信息， 因而可以只选用记录语句。一条 $语句包括 13 个记录语句标识头、世界时间、定位状态、纬度、 纬度方位、经度、经度方位、地面速度、地面路线、日期、磁偏角、校验 和和结束标记，它一共占用 70 个字节其中还包括用于分隔记录所使用的 11 个逗号，例如 $,121530998,40000162,116195476,000,24081,160102,*3 由此可见，从板接收下来的数据流是文本字符串，根据数据格式的特点， 本设计中拟采用半字节法完成压缩及解压缩的任务。该方法

6、属于无损压缩技术，其原理是去除字节中的冗余位，从而达到 压缩目的。然而，这种方法只适用于纯数字文本文件的压缩，显然定位数据并不 是纯数字的，还必须在压缩前进行一下压缩预处理，最后再利用半字节压 缩算法完成数据的压缩2 压缩预处理仔细观察以上各段数据记录，可以发现语句之间的数据 段还存在很多冗余。除此之外，这些记录中所含的信息既有英文字符又有数字，为了后续 的压缩，对语句中的各个记录应做如下的预处理 语句标识头因为每个语句的标识头都一样， 所以该记录段属地冗余 信息，完全可以去除，在解压缩时再在每个语句前加上该标识头即可。 世界时间该信息段以时、 分、秒、毫秒的格式指示出当时世界时间。 转换为北

7、京时间还需要再加上 8 小时。由于车载系统的定位数据的采集是以秒为单位的，所以毫秒量级的数 据对本系统根本无用，是冗余信息，由于世界时间是按秒增1，定位数据也是每委员长更新一次，所以世界时间可以在程序的一开始采集记录一下， 在解压缩时根据语句的指针值再加上起始时间便可以复原，因此该记录段 在第一次存储后，以后的语句中的该信息全都是冗余信息。 定位状态占用 1 个字节，不进行预处理。 由于车载系统处于的地方有可能收不到卫星信号如隧道中，致使定位 信息无效， 因此尽管该字段发生变化的概率较小， 又与其它信息段不相关， 在此仍不能做预处理。 纬度占用 9 个字节，不进行预处理。 纬度占用 10 个字

8、节，不进行预处理。 经度指示器占一个字节，它指示出经度是东经，还是匹配。由于各个 $语句中的该段信息在中国都是东径，它是冗余信息，因此 也采取程序一开始存储一次的方法。 纬度指示器占一个字节，各个 $语句中的该段信息完全一样，是冗 余信息，处理方法与上相同。 地面速度占用 4 个字节，不进行预处理。 日期占用 6 个字节，以日、月、年的格式显示，各个 $ 语句中的该 段信息在 24 小时内完全一样，是冗余信息，采取程序一开始存储一次的 方法，以后语句中的该段信息全部废除。 校验和占用 3 个字节， 该数据完成校验后便弃之， 不保留和进行压 缩。结束符合占用 2 个字节，只用来判断语句的有效数据

9、范围，其它记录 段与本系统的设计无关都不保留和进行压缩。通过以上压缩预处理后，保留了四个数据记录，共占用 24 个字节， 如图 1 所示。3 改进型半字节压缩算法文本数据的压缩的都是无损压缩技术，即还 原后的文件应该与源文件完全相同。文本文件压缩的方法有很多种， 如编码、算术编码和字节压缩方法等。 它们均是无损压缩方法，都适用于文本数据的压缩。半字节压缩方法是针对文本数据的特点所设计的，主要是去除文本中 的字节中的冗余位，从而达到减少数据文件所占用的存储空间的目的。在数据压缩技术中，除压缩重复字符外，还可以根据数据本身的特点 进行压缩。在计算机中，任何数据都是以某种代码的方式存储的在些文件中，

10、或许有一些代码具有某些相似之处，我们可以根据代码 的特点进行特定的操作，压缩掉这些数据的相似部分，或者说压缩掉这些 数据的特征部分，半字节压缩就是这样一种方法。半字节方法主要用于纯数字的文本文件的压缩，因为数字09的码的高四位都一样，是冗余的，因此每一个数字完全可以用低四位描述，即每个字节的八位编码可压缩为四位编码，压缩比理论上可趋近50。从图 1中可以看出， 经过预处理后的数据中， 包含的文本字节有 09 十个数字符号，、两个英文大写字母和一个小数点符号，共13 个字符。、的码的高四位显然与数字字节的不一样，半字节压缩方法不能简单套用。然而，我们知道四位二进制编码可区分 16种状态，用来表示

11、 13 种不同的字符是足够的。压缩数据编码表如表 1 的慰，为了充分利用编码表中的状态，在原来13 个字节的基础上又新增添了两个字符和，其四位编码分别为1101 和1110。这两个字符是在压缩预处理过程中，用来记录那些因语句校验和出错 而舍弃的语句。因为每条语句的时间信息全部在预处理阶段被舍弃，在解压缩时要恢 复时间值。该值在正常情况下是根据时间的基数再加上语句的计数值由于每秒接受到一条语句，所以语句计数值就是以秒为单位的时间增量确定的。当发生语句校验和出错时，若处于定位有效状态，则在定位状态记录上不填写字符，而填写字符；若处在定位无效状态，则不填写字符，而填 写字节。在以后解压缩时，若检测到

12、、字节，时间的还原按正常的算法进行； 若检测到、字符时，进行的还原除了按正常的算法进行以外还要加上秒钟， 这样才能确保时间能够正确的恢复，这是因为、 字节表示上一条语句发 生错误已经被丢弃，语句的压缩是非连续的，有继句现象发生。表 1 压缩数据编码表预处理后所含的字符码四位二制编码备注01234567890011000000110001001100100011001100110100001101010011 01100011011100111000001110010010111001000001010000100101011001 0101110000000100100011010001010

13、1100111100010011010101111011100 1110 定位有效定位有效， 秒值 1 定位无效定位无效， 秒增 1 通过此编码表 进行转换后，原来经过压缩预处理后的固定 24 个字节第的文本数据就可 以减小一半压缩后为固定的 12 个字节长，压缩比为 50，若从未经过预处 理的文本数据算起，则压缩比可达到 80。由图 2 可知，实现半字节压缩算法需要解决两上问题首先是压缩对象 的计数；其次是如何把两个数字的低位合并到一个字节中。后一个问题只要规定好压缩后的字节中奇数号字符的四位编码与偶 数号字符的四位编码的存放次序即可，程序的实现非常简单，在此我们规 定编号是奇数的字符放在高

14、四位，编号为偶数的字符的编码放在低四位。假设压缩前的数据流中的前四个字节分别为1、2、 3、4,则压缩后的数据格式如图 3 所示半字节压缩中需要解决的首要问题是压缩对象的计数问题，解决此问 题的方法有两种一种是半字节计数器 -，另一种是全字节计数器 -。 不管那一种方法， 它们都要占用字节， 再加上压缩标识也要占用字节， 所以要影响数据的压缩比。改进后的半字节压缩算法完全解决了此问题，因为定位数据经过压缩 预处理后的数据长度是固定的 24 个字节长，不是动态可变的，所以不需 要解决压缩对象的计数问题。一般来说，任何一种压缩算法都需要用压缩指示字符作压缩数据的标 识，压缩标识符越短越好，因为过长

15、会影响缩效果。然而，由于定位数据中的所有字符都进行了编码处理，不存在原样字 符不进行压缩的字符， 在解压缩时原样输出， 因此压缩标识完全可以省略， 可进一步提高数据的压缩比。压缩预处理程序框图和改进后的半字节压缩算法框图如图 4 所示。 压缩文件包括解压缩所需的重要信息，由释放参数信息和依次压缩了 的定长数据块组成。释放参照信息包含有解压缩所要使用的时间基数信息，它通过语句计 数器以及错误代码号可以将时间还原。除此之外，释放参照信息还包括各个定长数据块在解压缩时所需的共 同信息，如、日期，压缩文件的格式如图 5 所示。嵌入式系统的压缩是不需要人为干涉、而自动实时完成的，具体的实 现方法是通过驻留内存单任务操作系统中，如或作为一个后台任务在多任 务操作系统中，如中对数据完成实时压缩或解压缩表2改进型半字节压缩算法的测试结果处理文件大小预处理后改进型半字节压缩压缩比1035=69 X 150001035=69 X 15001036=69 X 150360+2336+2336+231