面向星载计算机的双重索引数据压缩方法  

Double Index Data Compression Method for Onboard Computer

作　　者：邓岸华 乔磊[2] 杨孟飞[3] DENG An-Hua;QIAO Lei;YANG Meng-Fei(School of Computer Science and Technology,Xidian University,Xi’an 710071,China;Beijing Institute of Control Engineering,Beijing 100190,China;China Academy of Space Technology,Beijing 100094,China)

机构地区：[1]西安电子科技大学计算机科学与技术学院,陕西西安710071 [2]北京控制工程研究所,北京100190 [3]中国空间技术研究院,北京100094

出　　处：《软件学报》2022年第10期3844-3857,共14页Journal of Software

基　　金：国家自然科学基金(61632005,62032004,61802017)。

摘　　要：随着星载计算机系统功能的日益复杂,程序规模也在快速扩大.在存储资源极其受限的背景下,需要稳定、有效的代码压缩功能来保障星载软件的正常存储与运行.混合压缩算法是目前无损数据压缩的主流算法,具有压缩率高、代码规模和计算资源需求大的特点.然而,在航天星载计算机等嵌入式系统中,由于其运行环境特殊,需要较高的可靠性和抗干扰能力,无法实现混合压缩算法应有的效果.同时,单一压缩模型压缩率较低.针对以上问题,在LZ77算法代码体积和内存消耗优势的基础上提出了改进方法:为压缩过程设计一种新的匹配记录表以存储高价值数据索引来辅助压缩,实现了原算法局部性优势与高价值数据全局分布的互补,更大程度上减少了数据冗余;结合动态填充、变长编码等进一步优化编码结构,降低存储需求;最终,设计并实现了一种更加适合航天嵌入式环境的无损数据压缩算法(LZRC).实验结果表明:(1)新算法在比LZ77算法代码体积仅多出3.5 KB的条件下,对软件代码的平均压缩比提高了17%;(2)新算法的运行内存需求仅为混合压缩算法的12%,代码体积也减少了84%,更加适合星载计算机系统.As the functions of on-board computer systems become more and more complex,the scale of programs is also growing rapidly.A stable and effective code compression function is required to ensure the storage and operation of on-board software under the background of extremely limited storage resources.Hybrid compression is currently the mainstream algorithm for lossless data compression,and it has the characteristics of high compression rate,large code size,and large demand for computing resources.However,embedded systems such as spaceborne computers require reliability and anti-jamming capabilities,and hybrid compression cannot play its amazing effect.At the same time,the compression rate of a single model is too low to meet the demand.This study proposes an improvement method based on the advantage of the low resource requirement of LZ77 algorithm,the details are as follows.The new algorithm uses a new matching record table for the compression.This table stores high-value indexes to assist in compression,which realizes the complementarity between the local advantages of the original algorithm and the global distribution of high-value data,and reduces data redundancy to a greater extent.In addition,the new algorithm combines dynamic filling,variable length coding,and other methods to further optimize the coding structure and reduce storage requirements.Finally,the lossless data compression algorithm(LZRC)is designed and implemented,which is more suitable for the aerospace field.Experimental results show that:(1)the code size of the new algorithm is 3.5 KB more than the code size of the original algorithm,and the average compression ratio of software has increased by 17%;(2)compared with hybrid compression,the runtime memory of the proposed algorithm is only 12%,and the code size is also reduced by 84%,which is more suitable for on-board computer systems.

关 键 词：数据压缩 LZ77 嵌入式操作系统 资源受限 匹配记录表 多重索引 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]