一种创新性位图压缩与解压缩系统算法

李焕焕 吴祖民

摘 要：文章提出一种位图压缩与解压缩算法，可以很好地对位图压缩边界进行控制，简化解压缩流程。该算法有效避免由于位图解压缩误解码出现的误重传判断，直接提高卫星移动终端与模拟基站之间的数据交互效率。已有协议中，关于该部分的边界处理，具体算法实现并没有相关提案。本算法包括位图压缩算法、压缩边界处理算法、位图解压缩算法等3个子算法，经试验验证，该算法成功实现卫星移动终端与模拟基站之间的通信。

关键词：卫星通信；GMR-1；主动式轮询；可靠性传输

GMR-1 3G（GEO-Mobile Radio Third Generation）标准是面向地面3G标准，为实现GEO卫星移动通信系统与地面3G核心网互连而制定的[1]。该标准规定了空中接口通信的终端用户和接入网基站设备之间的通信接口[2]。为实现卫星通信终端进行话音、传真、视频等业务可靠性传输，如何在通信过程中保证信令控制以及业务数据实现有效传输与处理成为系统需要解决的重要问题。卫星终端与模拟基站交互依靠ACK/NACK消息实现数据接收反馈，当所分配信道资源不足以承载所生成的全局位图时，位图需要采用无损压缩机制进行压缩，以期达到利用最小的资源传送最大的信息量，可有效减少ACK/NACK消息数量，节省信道资源。位图压缩机制采用基于ITU-T Recommendation T.4的一維游程编码。

1 基于ITU-T Recommendation T.4的一维游程编码

如果窗口大小小于位图中的比特数，那么通过使用不压缩的位图提供全部的反馈消息；如果窗口大小大于位图中的比特数，那么将从启动序列号（Starting Sequence Number，SSN）开始采用一维游程编码（基于ITU-T Recommendation T.4）。

用于编码游程的T.4流程如下，一连串的1和0交替，游程由下表中的码字表示。对于T.4中关于游程0和1的码字有微小改动：用于指示1个0和3个0游程的终止码进行了调换。游程码字有两种类型：终止码和形成码。每一个游程可以表示为一个终止码或一个形成码加一个终止码。范围在0～63比特的游程编码为合适的终止码，大于63比特的游程首先编码为等于或小于要求的形成码，紧跟一个表示要求的游程与形成码表示游程之间差异的终止码。

在位图的开始或结尾没有特殊的码字，一个一比特的标识用来指示压缩位图以0游程还是1游程开始。假定压缩位图的长度为Lc，仅当能够获得压缩增益时才使用游程编码，否则将发送不压缩的位图。

2 算法描述

2.1 位图压缩算法

位图压缩算法采用基于ITU-T Recommendation T.4的一维游程无损压缩。本文首先根据当前协议参数v_r（将要接收的下一个RLC块的序列号）与v_q（接收窗口内没有被接收的最早的RLC数据块的序列号）值获取全局位图，如果全局位图比特数目要大于给定的位图占用比特数据，那么需要进入位图压缩流程，其压缩过程如下。

（1）根据变量v_r与v_q获取全局位图，全局位图的范围[v_q，v_r-1]。本文规定起始色码对应相应游程长度的编码比特与压缩首字节的最低位开始一一对应。

（2）获取可用于存储位图的最大承载比特N1。

（3）根据消息形式，可获取用于存储LENGTH字段的比特长度N2。

（4）确定起始色码，起始色码取决于序列号为v_q的数据块的接收情况，v_q表示未接收，起始色码设置为0。

（5）记录色码游程，交替进行，根据T4表（参考协议44.060）进行压缩。对应于（1）本文压缩起始从SSN开始执行。在此过程中，记录压缩后总长度。压缩后总长度N3在压缩过程中不断增加，与可用于存储位图的最大承载BIT有以下几种关系：

①如果压缩后长度N3小于可用于存储压缩位图的BIT长度N1，并且二者之间长度之差N4大于等于用于LENGTH字段存储的BIT长度N2，那么判定压缩增益，如果压缩增益大于1，将压缩后位图直接写入状态报告，传送至对端，转至步骤（7）。

②如果压缩后长度N3等于可用于存储压缩位图的比特长度N1，那么判定压缩增益，如果压缩增益大于1，将压缩后位图直接写入状态报告，传送至对端，转至步骤（7）。

③如果压缩后长度N3小于可用于存储压缩位图的BIT长度N1，但是二者之间BIT长度N4之差小于用于LENGTH字段存储的BIT长度N2，那么需要调用边界处理算法，转至步骤（6）。

④如果压缩后长度N3大于可用于存储压缩位图的BIT长度N1，那么需要调用边界处理算法，转至步骤（6）。

（6）使用CRBB边界处理算法进行处理，详细算法步骤参考2.2节。

（7）每一次压缩完成，都必须计算压缩增益，如果压缩增益大于1，才会将CRBB结构发送，否则，将填写未压缩位图URBB结构。

2.2 CRBB边界处理算法

本文提出的CRBB边界处理算法，对位图压缩与信道可承载比特的特殊情况进行处理，保证解压缩顺利进行，避免由于压缩解压缩不正确带来的RLC误重传问题。

CRBB边界处理算法如图1所示，边界处理算法思想如下。

（1）如果满足2.1节步骤（5）中的条件③，执行以下步骤：

①按照压缩BIT生成顺序逆向回退长度为该色码对应游程长度的BIT长度N5。

②计算回退后的可用压缩空间N6：

a.如果剩余BIT长度N6足够存储，LENGTH字段长度N2，那么填充带有LENGTH字段的CRBB结构。

b.如果剩余BIT长度N6不足以存储，LENGTH字段长度N2，那么按照（6）中①所述，继续回退，直至满足剩余BIT长度N6足够存储LENGTH字段长度N2的条件。

（2）如果满足3.1节步骤（5）中的条件④，执行以下步骤：

①按照压缩BIT生成顺序逆向回退长度为该色码对应游程长度的BIT长度N5。

②计算回退后剩余的可用压缩空间N6。

a.如果剩余可用压缩空间长度N6等于零，那么表明LENGTH字段不存在，更新后的压缩比特数正好填满可用压缩空间N1。

b.如果剩余可用压缩空间N6大于零并且大于等于用于存储LENGTH字段长度的BIT长度N2，那么生成带有LENGTH字段的CRBB结构。

c.如果剩余可用压缩空间N6大于零并且小于用于存储LENGTH字段长度的BIT长度N2，那么需要按照压缩BIT生成顺序逆向回退长度为当前最后一个色码对应游程长度的BIT长度，计算回退后的可用压缩空间，如果剩余可用压缩空间长度N6足够存储LENGTH字段长度N2，那么填充带有LENGTH字段的CRBB结构。

2.3 CRBB解压缩算法

卫星终端或者基站作为接收端时，需要进行位图解压缩。

位图压缩过程已经对压缩边界作出识别，简化了解压缩过程。本文给出解压缩解析步骤如下：

（1）获取起始序列号，该序列号对应的RLC数据块为需要重传的数据块，更新发送单元相应序列号的数据块标识。

（2）分别获取黑码与白码的最低比特阈值B1和W1。

（3）根据LENGTH字段是否存在，计算需要解压缩的长度N9。

（4）读入压缩比特流，按照阈值获取相应比特流，查表，调用解压缩与位图解码流程进行解码。

（5）如果剩余需要解压缩的比特数目低于阈值B1或者W1（阈值由当前色码决定，本文取B1=9，W1=13），那么将剩余比特流全部读入，调用解压缩与位图解码流程进行解码。

（6）根据解压后的位图比特流，更新RLC数据发送单元的协议参数以及相应与序列号的数据块标识，如果确认收到，那么删除该PDU，如果否认确认，那么该数据标识更新为需要重傳。

采用本文的位图压缩方法，位图解压缩过程简化，避免由于边界不确定带来的误解压。

3 模拟试验

3.1 试验方案

为验证本方案的可行性，采用C语言编程实现本文所提出的位图压缩及解压缩算法。算法应用于卫星移动终端与模拟基站。使用卫星终端与地面模拟基站进行通信模拟试验，对卫星移动终端位图编码以及模拟基站位图解码情况进行成功率统计，如表1所示。

3.2 试验结果分析

如表1统计所示，采用本文提出的压缩算法及解压缩算法可将位图正确编解码，编码边界识别无误，不会造成识别误码率。

4 结语

本文提出的位图压缩算法以及解压缩算法适用于GMR-1 3G标准的通信系统，随着卫星通信技术的不断发展，通过算法改进进行卫星通信系统性能优化，已经成为一种趋势。

[参考文献]

[1]程宇新，罗常青，吴建军.新一代GEO卫星移动通信新标准GMR-13G简介[C].北京：第六届卫星通信新业务新技术学术年会，2010.

[2]范志勇.GMR通信系统传输数据处理的设计与实现[D].北京：北京交通大学，2014.

Abstract：In this paper， an innovative bitmap compression and decompression algorithm is proposed， which can control the compression boundary of the bitmap very well and simplify the decompression process. The misjudgment of the data resend caused by bitmap error decoding can be avoided. It has been improved the data interaction efficiency between the satellite mobile terminal and the analog base station. The existing agreement， no relevant proposal agreement about how to process bitmap boundary exists. The algorithm includes three parts， such as bitmap compression algorithm， the boundary process algorithm and bitmap decompression algorithm. The experiment proves that the algorithm can realize data communication between the satellite mobile terminal and the analog base station.

Key words：satellite communication； GMR-1； active polling； reliability transmission