一種創(chuàng)新性位圖壓縮與解壓縮系統(tǒng)算法

李煥煥 吳祖民

摘 要：文章提出一種位圖壓縮與解壓縮算法，可以很好地對位圖壓縮邊界進(jìn)行控制，簡化解壓縮流程。該算法有效避免由于位圖解壓縮誤解碼出現(xiàn)的誤重傳判斷，直接提高衛(wèi)星移動(dòng)終端與模擬基站之間的數(shù)據(jù)交互效率。已有協(xié)議中，關(guān)于該部分的邊界處理，具體算法實(shí)現(xiàn)并沒有相關(guān)提案。本算法包括位圖壓縮算法、壓縮邊界處理算法、位圖解壓縮算法等3個(gè)子算法，經(jīng)試驗(yàn)驗(yàn)證，該算法成功實(shí)現(xiàn)衛(wèi)星移動(dòng)終端與模擬基站之間的通信。

關(guān)鍵詞：衛(wèi)星通信；GMR-1；主動(dòng)式輪詢；可靠性傳輸

GMR-1 3G（GEO-Mobile Radio Third Generation）標(biāo)準(zhǔn)是面向地面3G標(biāo)準(zhǔn)，為實(shí)現(xiàn)GEO衛(wèi)星移動(dòng)通信系統(tǒng)與地面3G核心網(wǎng)互連而制定的[1]。該標(biāo)準(zhǔn)規(guī)定了空中接口通信的終端用戶和接入網(wǎng)基站設(shè)備之間的通信接口[2]。為實(shí)現(xiàn)衛(wèi)星通信終端進(jìn)行話音、傳真、視頻等業(yè)務(wù)可靠性傳輸，如何在通信過程中保證信令控制以及業(yè)務(wù)數(shù)據(jù)實(shí)現(xiàn)有效傳輸與處理成為系統(tǒng)需要解決的重要問題。衛(wèi)星終端與模擬基站交互依靠ACK/NACK消息實(shí)現(xiàn)數(shù)據(jù)接收反饋，當(dāng)所分配信道資源不足以承載所生成的全局位圖時(shí)，位圖需要采用無損壓縮機(jī)制進(jìn)行壓縮，以期達(dá)到利用最小的資源傳送最大的信息量，可有效減少ACK/NACK消息數(shù)量，節(jié)省信道資源。位圖壓縮機(jī)制采用基于ITU-T Recommendation T.4的一維游程編碼。

1 基于ITU-T Recommendation T.4的一維游程編碼

如果窗口大小小于位圖中的比特?cái)?shù)，那么通過使用不壓縮的位圖提供全部的反饋消息；如果窗口大小大于位圖中的比特?cái)?shù)，那么將從啟動(dòng)序列號（Starting Sequence Number，SSN）開始采用一維游程編碼（基于ITU-T Recommendation T.4）。

用于編碼游程的T.4流程如下，一連串的1和0交替，游程由下表中的碼字表示。對于T.4中關(guān)于游程0和1的碼字有微小改動(dòng)：用于指示1個(gè)0和3個(gè)0游程的終止碼進(jìn)行了調(diào)換。游程碼字有兩種類型：終止碼和形成碼。每一個(gè)游程可以表示為一個(gè)終止碼或一個(gè)形成碼加一個(gè)終止碼。范圍在0～63比特的游程編碼為合適的終止碼，大于63比特的游程首先編碼為等于或小于要求的形成碼，緊跟一個(gè)表示要求的游程與形成碼表示游程之間差異的終止碼。

在位圖的開始或結(jié)尾沒有特殊的碼字，一個(gè)一比特的標(biāo)識用來指示壓縮位圖以0游程還是1游程開始。假定壓縮位圖的長度為Lc，僅當(dāng)能夠獲得壓縮增益時(shí)才使用游程編碼，否則將發(fā)送不壓縮的位圖。

2 算法描述

2.1 位圖壓縮算法

位圖壓縮算法采用基于ITU-T Recommendation T.4的一維游程無損壓縮。本文首先根據(jù)當(dāng)前協(xié)議參數(shù)v_r（將要接收的下一個(gè)RLC塊的序列號）與v_q（接收窗口內(nèi)沒有被接收的最早的RLC數(shù)據(jù)塊的序列號）值獲取全局位圖，如果全局位圖比特?cái)?shù)目要大于給定的位圖占用比特?cái)?shù)據(jù)，那么需要進(jìn)入位圖壓縮流程，其壓縮過程如下。

（1）根據(jù)變量v_r與v_q獲取全局位圖，全局位圖的范圍[v_q，v_r-1]。本文規(guī)定起始色碼對應(yīng)相應(yīng)游程長度的編碼比特與壓縮首字節(jié)的最低位開始一一對應(yīng)。

（2）獲取可用于存儲(chǔ)位圖的最大承載比特N1。

（3）根據(jù)消息形式，可獲取用于存儲(chǔ)LENGTH字段的比特長度N2。

（4）確定起始色碼，起始色碼取決于序列號為v_q的數(shù)據(jù)塊的接收情況，v_q表示未接收，起始色碼設(shè)置為0。

（5）記錄色碼游程，交替進(jìn)行，根據(jù)T4表（參考協(xié)議44.060）進(jìn)行壓縮。對應(yīng)于（1）本文壓縮起始從SSN開始執(zhí)行。在此過程中，記錄壓縮后總長度。壓縮后總長度N3在壓縮過程中不斷增加，與可用于存儲(chǔ)位圖的最大承載BIT有以下幾種關(guān)系：

①如果壓縮后長度N3小于可用于存儲(chǔ)壓縮位圖的BIT長度N1，并且二者之間長度之差N4大于等于用于LENGTH字段存儲(chǔ)的BIT長度N2，那么判定壓縮增益，如果壓縮增益大于1，將壓縮后位圖直接寫入狀態(tài)報(bào)告，傳送至對端，轉(zhuǎn)至步驟（7）。

②如果壓縮后長度N3等于可用于存儲(chǔ)壓縮位圖的比特長度N1，那么判定壓縮增益，如果壓縮增益大于1，將壓縮后位圖直接寫入狀態(tài)報(bào)告，傳送至對端，轉(zhuǎn)至步驟（7）。

③如果壓縮后長度N3小于可用于存儲(chǔ)壓縮位圖的BIT長度N1，但是二者之間BIT長度N4之差小于用于LENGTH字段存儲(chǔ)的BIT長度N2，那么需要調(diào)用邊界處理算法，轉(zhuǎn)至步驟（6）。

④如果壓縮后長度N3大于可用于存儲(chǔ)壓縮位圖的BIT長度N1，那么需要調(diào)用邊界處理算法，轉(zhuǎn)至步驟（6）。

（6）使用CRBB邊界處理算法進(jìn)行處理，詳細(xì)算法步驟參考2.2節(jié)。

（7）每一次壓縮完成，都必須計(jì)算壓縮增益，如果壓縮增益大于1，才會(huì)將CRBB結(jié)構(gòu)發(fā)送，否則，將填寫未壓縮位圖URBB結(jié)構(gòu)。

2.2 CRBB邊界處理算法

本文提出的CRBB邊界處理算法，對位圖壓縮與信道可承載比特的特殊情況進(jìn)行處理，保證解壓縮順利進(jìn)行，避免由于壓縮解壓縮不正確帶來的RLC誤重傳問題。

CRBB邊界處理算法如圖1所示，邊界處理算法思想如下。

（1）如果滿足2.1節(jié)步驟（5）中的條件③，執(zhí)行以下步驟：

①按照壓縮BIT生成順序逆向回退長度為該色碼對應(yīng)游程長度的BIT長度N5。

②計(jì)算回退后的可用壓縮空間N6：

a.如果剩余BIT長度N6足夠存儲(chǔ)，LENGTH字段長度N2，那么填充帶有LENGTH字段的CRBB結(jié)構(gòu)。

b.如果剩余BIT長度N6不足以存儲(chǔ)，LENGTH字段長度N2，那么按照（6）中①所述，繼續(xù)回退，直至滿足剩余BIT長度N6足夠存儲(chǔ)LENGTH字段長度N2的條件。

（2）如果滿足3.1節(jié)步驟（5）中的條件④，執(zhí)行以下步驟：

①按照壓縮BIT生成順序逆向回退長度為該色碼對應(yīng)游程長度的BIT長度N5。

②計(jì)算回退后剩余的可用壓縮空間N6。

a.如果剩余可用壓縮空間長度N6等于零，那么表明LENGTH字段不存在，更新后的壓縮比特?cái)?shù)正好填滿可用壓縮空間N1。

b.如果剩余可用壓縮空間N6大于零并且大于等于用于存儲(chǔ)LENGTH字段長度的BIT長度N2，那么生成帶有LENGTH字段的CRBB結(jié)構(gòu)。

c.如果剩余可用壓縮空間N6大于零并且小于用于存儲(chǔ)LENGTH字段長度的BIT長度N2，那么需要按照壓縮BIT生成順序逆向回退長度為當(dāng)前最后一個(gè)色碼對應(yīng)游程長度的BIT長度，計(jì)算回退后的可用壓縮空間，如果剩余可用壓縮空間長度N6足夠存儲(chǔ)LENGTH字段長度N2，那么填充帶有LENGTH字段的CRBB結(jié)構(gòu)。

2.3 CRBB解壓縮算法

衛(wèi)星終端或者基站作為接收端時(shí)，需要進(jìn)行位圖解壓縮。

位圖壓縮過程已經(jīng)對壓縮邊界作出識別，簡化了解壓縮過程。本文給出解壓縮解析步驟如下：

（1）獲取起始序列號，該序列號對應(yīng)的RLC數(shù)據(jù)塊為需要重傳的數(shù)據(jù)塊，更新發(fā)送單元相應(yīng)序列號的數(shù)據(jù)塊標(biāo)識。

（2）分別獲取黑碼與白碼的最低比特閾值B1和W1。

（3）根據(jù)LENGTH字段是否存在，計(jì)算需要解壓縮的長度N9。

（4）讀入壓縮比特流，按照閾值獲取相應(yīng)比特流，查表，調(diào)用解壓縮與位圖解碼流程進(jìn)行解碼。

（5）如果剩余需要解壓縮的比特?cái)?shù)目低于閾值B1或者W1（閾值由當(dāng)前色碼決定，本文取B1=9，W1=13），那么將剩余比特流全部讀入，調(diào)用解壓縮與位圖解碼流程進(jìn)行解碼。

（6）根據(jù)解壓后的位圖比特流，更新RLC數(shù)據(jù)發(fā)送單元的協(xié)議參數(shù)以及相應(yīng)與序列號的數(shù)據(jù)塊標(biāo)識，如果確認(rèn)收到，那么刪除該P(yáng)DU，如果否認(rèn)確認(rèn)，那么該數(shù)據(jù)標(biāo)識更新為需要重傳。

采用本文的位圖壓縮方法，位圖解壓縮過程簡化，避免由于邊界不確定帶來的誤解壓。

3 模擬試驗(yàn)

3.1 試驗(yàn)方案

為驗(yàn)證本方案的可行性，采用C語言編程實(shí)現(xiàn)本文所提出的位圖壓縮及解壓縮算法。算法應(yīng)用于衛(wèi)星移動(dòng)終端與模擬基站。使用衛(wèi)星終端與地面模擬基站進(jìn)行通信模擬試驗(yàn)，對衛(wèi)星移動(dòng)終端位圖編碼以及模擬基站位圖解碼情況進(jìn)行成功率統(tǒng)計(jì)，如表1所示。

3.2 試驗(yàn)結(jié)果分析

如表1統(tǒng)計(jì)所示，采用本文提出的壓縮算法及解壓縮算法可將位圖正確編解碼，編碼邊界識別無誤，不會(huì)造成識別誤碼率。

4 結(jié)語

本文提出的位圖壓縮算法以及解壓縮算法適用于GMR-1 3G標(biāo)準(zhǔn)的通信系統(tǒng)，隨著衛(wèi)星通信技術(shù)的不斷發(fā)展，通過算法改進(jìn)進(jìn)行衛(wèi)星通信系統(tǒng)性能優(yōu)化，已經(jīng)成為一種趨勢。

[參考文獻(xiàn)]

[1]程宇新，羅常青，吳建軍.新一代GEO衛(wèi)星移動(dòng)通信新標(biāo)準(zhǔn)GMR-13G簡介[C].北京：第六屆衛(wèi)星通信新業(yè)務(wù)新技術(shù)學(xué)術(shù)年會(huì)，2010.

[2]范志勇.GMR通信系統(tǒng)傳輸數(shù)據(jù)處理的設(shè)計(jì)與實(shí)現(xiàn)[D].北京：北京交通大學(xué)，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