一種FPGA在軌重構配置數據壓縮算法

徐勇 李珂 馮國平 陶利民 龐波

(北京空間飛行器總體設計部，北京 100094)

?

一種FPGA在軌重構配置數據壓縮算法

徐勇 李珂 馮國平 陶利民 龐波

(北京空間飛行器總體設計部，北京 100094)

對現(xiàn)場可編程門陣列(FPGA)在軌重構配置文件壓縮，可以大大減少遙控上注時間。為此，文章利用FPGA配置文件中0值較多的特點，結合游程編碼(RLC)及字典編碼的優(yōu)勢，提出一種FPGA在軌重構配置數據壓縮算法，即結合零游程(Zeros Run Length，ZRL)編碼的VLZW壓縮算法(簡稱為ZRL-VLZW算法)。為減小航天器載計算機內存開銷，使用索引迭代方式存儲字典并限制字典長度。采用航天器常用FPGA多種資源占用比的配置文件，利用ZRL-VLZW、LZW和VLZW算法進行壓縮測試比較。結果表明：ZRL-VLZW算法性能優(yōu)于LZW算法和VLZW算法，可有效進行配置文件的壓縮，使在軌重構注入數據上注時間減少為原來的1/20～1/3。

現(xiàn)場可編程門陣列；在軌重構；配置數據壓縮

1 引言

隨著空間技術的發(fā)展，航天器體積、質量不斷縮小，計算速度越來越快，功能越來越多，傳統(tǒng)分立電路及小容量反熔絲現(xiàn)場可編程門陣列(FPGA)已經不能滿足航天器設計的要求[1]。因此，靜態(tài)隨機存儲器(SRAM)型FPGA在航天器設計中的應用越來越多，主要完成計算機接口、存儲器管理、信號處理和通信協(xié)議處理等功能?；赟RAM型的航天器載FPGA在軌重構技術，在提高航天器功能靈活性及可升級特性的同時，也能用于在軌修復FPGA局部永久損傷和設計錯誤等缺陷[2]，因此越來越多的航天器載FPGA板級電路具備在軌可重構功能[3-4]。然而，用于FPGA重構的配置文件數據量較大，以300萬門中等規(guī)模FPGA為例，其數據量為10.495 Mbit，航天器測控信道有限的帶寬使得FPGA重構程序上注需要漫長的時間，浪費航天器寶貴的可見觀測弧段時間，且當可見觀測弧段時間短時，則需要多次可見弧段時間續(xù)傳才能完成一個重構配置文件的上注，成為影響在軌重構計算機系統(tǒng)使用效率的一個重要因素。

在無法大幅提高遙控帶寬的前提下，減小重構配置數據量成為解決上述難題的最佳選擇。目前，數據壓縮算法主要包括算術編碼、可變長編碼(如Golomb、Huffman)及字典編碼。算術編碼算法依賴于數據的實時概率統(tǒng)計，計算量大，速度慢，不適合在航天器上應用?？勺冮L編碼算法比較適合于符合高斯分布的樣本，而FPGA的配置文件拆分為字節(jié)樣本時并不符合高斯分布特性。因此，F(xiàn)PGA配置文件壓縮經常使用字典編碼算法。然而，單純字典編碼算法在進行FPGA配置文件壓縮時，未充分利用FPGA配置文件中連續(xù)0數據區(qū)域較多的特點，導致壓縮效率較低。為此，本文在字典編碼算法VLZW(Variable Lempel Ziv Welch)[5]的基礎上，考慮了航天器計算機系統(tǒng)內存資源緊張的情況，根據航天器FPGA配置文件的數據分布特點，給出一種結合零游程(Zeros Run Length，ZRL)編碼的VLZW壓縮算法(簡稱為ZRL-VLZW算法)，并將其應用于航天器常用FPGA配置文件的壓縮中。驗證結果表明，ZRL-VLZW算法性能優(yōu)于LZW(Lempel Ziv Welch)算法和VLZW算法，可用于航天器可重構系統(tǒng)的在軌重構配置數據壓縮。

2 ZRL-VLZW壓縮算法

2.1 SRAM型FPGA配置文件介紹

SRAM型FPGA的可編程特性，包括邏輯真值表、互聯(lián)、IP核參數、IO屬性、RAM參數等配置信息，是由內部的配置存儲器控制的[6]。該配置存儲器可由JTAG鏈寫入，由FPGA上電主動加載，由外部SelectMap口被動寫入，甚至可以在工作過程中進行寫入刷新，以糾正單粒子翻轉造成的影響。寫入/加載入配置存儲器的數據即為配置文件，該文件的組成主要包含若干幀的數據，還包含同步頭、寫入命令、寫入地址、校驗、復位命令等諸多控制FPGA啟動信息幀。

2.2 自適應零游程預壓縮

在航天器計算機中，存儲資源是非常有限的，VLZW算法中使用字符串的方式存儲字典，不僅字典項的長度信息需要存儲，而且字典項中的字符串長度還不固定，實現(xiàn)時需要復雜的數據結構，并占用大量的內存資源。另外，在FPGA配置文件中存在大片連續(xù)的零數據(圖1中藍色部分)，針對這部分數據，可采用比VLZW算法效率更高的零游程(ZRL)編碼進行預壓縮。基于此，本文對VLZW算法進行改進，包括利用游程編碼提高連續(xù)‘0’區(qū)域的編碼效率及使用迭代字典存儲方法。

圖1 FPGA配置文件數據內容Fig.1 Contents of FPGA configuration file

(1)首先使用一種僅針對0系數進行游程編碼的自適應零游程編碼[7]進行數據預壓縮，獲得零游程數據DataA和非零數據DataB。自適應零游程(如圖2所示)包含普通和零游程2種模式：編碼時做前向自適應建模，并在2種模式中轉換。其規(guī)則比較簡單：初始模式為普通模式，該模式下直接將輸入樣本輸出，若連續(xù)輸入0達到2個，進入零游程模式；在零游程模式無輸出，只計0個數，直到輸入非0時退回普通模式，并輸出0游程個數和該非0樣本。

圖2 前向自適應零游程編碼示例Fig.2 An instance of forward adaptive zeros run length coding

(2)限制字典長度，當字典長度達到設定邊界Nmax時，初始化字典，重新建立字典。

(3)提出迭代式的字典存儲方式，減少字典存儲規(guī)模。本文的字典中，每個索引項的內容不再使用字符串+長度的方式存儲，而是存儲為前綴Prefix索引號+后綴字符Suffix的方式(Pre_Index，Suff_Symb)。其中：Pre_Index為字典索引，取值范圍為1～Nmax；Suff_Symb為數據符號。因此，每個字典的位數是固定的，有利于CPU或者FPGA實現(xiàn)本文算法時簡單地管理數據，同時內存開銷也隨之減小。

2.3 ZRL-VLZW算法流程

ZRL-VLZW算法的計算流程如下。

(1)開始數據壓縮，使用自適應零游程編碼對配置文件進行預壓縮，獲得兩部分數據，即零游程數據DataA和非零數據DataB。

(2)對DataB采用字典編碼進行編碼。

(2.1)進行算法的初始化，以8 bit/Symbol為例，按照迭代式字典的格式，建立初始字典為D={(0，i)|i=1～256}；此時字典中僅包含256個索引項，每項的第1個元素Pre_Index為0，解壓縮迭代查字典時表示迭代查詢到了盡頭，停止一個索引的解碼。初始化時令計算前綴Pre=0。

(2.2)讀入符號C，與當前前綴Pre組成查詢項(Pre，C)，到字典中查詢是否存在與(Pre，C)一致的索引項。如果存在，則跳到①執(zhí)行，否則跳到②執(zhí)行。①將前綴Pre賦值為新查詢到的字典索引CAM(Pre，C)，并判斷編碼是否結束：是，則輸出Code(Pre)；否則，跳到(2.2)繼續(xù)編碼。②判斷字典長度是否小于Nmax：是，則初始化字典；否則，將(Pre，C)加入字典，輸出Code(Pre)，并令Pre=CAM(0，C)。然后，判斷編碼是否結束：是，則輸出Code(Pre)；否則，跳到(2.2)繼續(xù)編碼。

(3)將字典編碼后碼流Code與游程編碼碼流DataA一起作為壓縮后數據上注。

上述流程中，Code(N)定義為當前字典長度下N所需bit的最小位寬二進制編碼，CAM(A，B)定義為字典中(A,B)向量的存儲位置。

迭代字典的解壓縮算法為壓縮過程的逆過程，邊解壓邊建立解壓字典，解壓時根據壓縮數據中的索引號Index查詢當前字典，而基于迭代字典的解壓縮算法在查詢某個索引號Index時，要以迭代的方式將查詢到的索引項中Pre_Index賦值給Index并輸出符號C，直到Pre_Index為0為止，即為該索引號Index解碼完成。

3 基于壓縮的在軌FPGA重構流程

基于壓縮的在軌FPGA重構流程如下。

(1)首先，將FPGA配置文件切分為若干編碼保護段，防止誤碼擴散效應。

(2)每個段單獨進行壓縮。

(3)壓縮后碼流進一步按照航天器上注格式拆分打包為若干遙控幀向航天器上發(fā)送。遙控信道鏈路層采取數據完整性校驗及差錯重傳機制保障數據的無誤傳輸。

(4)由于航天器上計算機內存有限，航天器上的解碼過程為漸進性解碼：在接收到第1幀數據時，就開始解碼，內存中僅緩存當前遙控幀及動態(tài)重建的字典，解碼出的數據實時寫入FPGA外部的非易失性配置存儲器。解碼用完的遙控幀即可丟棄，因此內存中僅須要開辟較小的內存來存儲字典。

(5)在所有壓縮數據注入完成后，F(xiàn)PGA外部的非易失性配置存儲器中就包含了解壓后的完整配置文件，發(fā)送FPGA重加載指令，即可實現(xiàn)FPGA的在軌重構。

4 試驗數據及分析

為驗證ZRL-VLZW算法的有效性，開發(fā)了ZRL-VLZW、LZW、VLZW的Matlab驗證程序，以常用的Xilinx SRAM型FPGA XQR2V3000及XC4VSX55的實際工程設計配置文件為例進行壓縮測試，字典深度為16 384項。2種FPGA在不同資源占用比時的壓縮比，見表1和表2。

在對XQR2V3000及XC4VSX55兩款常用FPGA的多種資源占用比的比特文件進行壓縮試驗中可以看出：ZRL-VLZW算法均高于經典LZW算法及VLZW算法的性能，且當資源占用比越低時，優(yōu)勢越明顯。ZRL-VLZW算法可以將配置文件數據壓縮至1/20～1/3，壓縮比的大小取決于FPGA的資源占用比，這主要是由于在FPGA的配置文件中，當資源占用比較低時，存在大片連續(xù)零數據，ZRL-VLZW算法中自適應零游程編碼對這部分數據進行編碼的效率高于LZW算法，除連續(xù)零數據以外的其他數據的壓縮比等同于VLZW算法，從而達到更高的壓縮比。

表1 XQR2V3000 FPGA不同資源占用比時的3種算法壓縮效果對比

表2 XC4VSX55 FPGA不同資源占用比時的3種算法壓縮效果對比

5 結束語

使用壓縮算法對FPGA在軌重構上注配置文件壓縮，可以大大縮短航天器在軌重構數據的上注時間，提高航天器可重構系統(tǒng)的應用效率。本文提出一種航天器FPGA在軌重構配置數據壓縮算法ZRL-VLZW，利用FPGA配置文件中0值數據較多的特點，并結合了游程編碼及字典編碼的優(yōu)勢。同時，為盡量減小航天器計算機的內存開銷，將VLZW算法進行字典長度限制，并使用索引迭代方式存儲字典。試驗中采用航天常用FPGA的多種資源占用比的配置文件進行壓縮測試，并與LZW算法和VLZW算法進行比較，結果表明：ZRL-VLZW算法可以有效進行配置文件的壓縮，且性能優(yōu)于LZW算法和VLZW算法,可使在軌重構數據上注時間減少至1/20～1/3。

References)

[1]楊孟飛，郭樹玲，孫增圻．航天器控制應用的星載計算機技術[J]．航天控制，2005，23(2)：78-84

Yang Mengfei,Guo Shuling,Sun Zengqi.On-board computer techniques for spacecraft control[J].Aerospace Control，2005，23(2)：78-84 (in Chinese)

[2]劉源，孫兆偉，沈毅，等.可重構星載信息處理系統(tǒng)FPGA預規(guī)劃技術[J].哈爾濱工程大學學報,2013,34(7)：878-888

Liu Yuan,Sun Zhaowei,Shen Yi,et al.FPGA pre-layout plan for reconfigurable on-board information processing system[J].Journal of Harbin Engineering University,2013,34(7)：878-888 (in Chinese)

[3]孫兆偉，劉源，邢雷，等.面向多任務的可重構星載計算機設計[J].系統(tǒng)工程與電子技術，2011，33(6)：1407-1414

Sun Zhaowei,Liu Yuan,Xing Lei，et al.Design of reconfigurable on-board computer for multitask[J].Systems Engineering and Electronics，2011,33(6)：1407-1414 (in Chinese)

[4]Williams J A，Dawood A S，Visser S J，et al． Reconfigurable on board processing and real-time remote sensing [J]．IEEE Trans． on Information and Systems，2003，86(5)：819-829

[5]邢虹.FPGA位流生成及其壓縮[D].上海：復旦大學，2008

Xing Hong.Generation and compression of FPGA bit-stream [D].Shanghai：Fudan University,2008 (in Chinese)

[6]Xilinx Inc.Xapp779-correcting single-event upsets in Virtex-II platform FPGA configuration memory[R].San Jose,California：Xilinx Inc.,2007

[7]徐勇，徐智勇，張啟衡，等.適于硬件實現(xiàn)的低復雜度圖像壓縮[J].光學精密工程，2009，17(9)：2262-2268

Xu Yong,Xu Zhiyong，Zhang Qiheng，et al.Low complexity image compression scheme for hardware implementation [J].Optics and Precision Engineering,2009，17(9)：2262-2268 (in Chinese)

(編輯：夏光)

Configuration Data Compression Algorithm for FPGA On-orbit Reconfiguration

XU Yong LI Ke FENG Guoping TAO Limin PANG Bo

(Beijing Institute of Spacecraft System Engineering,Beijing 100094,China)

The time for uploading FPGA on-orbit reconfiguration file can be reduced multiple times by using compression technology,so an algorithm called ZRL-VLZW (Zero Run Length VLZW) is proposed.It takes character of continues 0 data in configuration file to play the advantage of run length coding.In order to minimize the memory overhead of satellite computer,the entry number of words dictionary is limited and iterative dictionary is employed. In the experiments,the performances of proposed algorithm are compared with LZW (Lempel Ziv Welch) and VLZW (Variable Lempel Ziv Welch) algorithm in compression configuration file of typical FPGAs. The results show that the proposed algorithm ZRL-VLZW can obtain higher compression ratio than that of LZW and VLZW. The time for uploading FPGA on-orbit reconfiguration file can be reduced to 1/20～1/3 by using the proposed algorithm.

FPGA；on-orbit reconfiguration；configuration data compression

2015-02-28；

2015-05-20

國家重大科技專項工程

徐勇，男，博士，研究方向為星載電子系統(tǒng)、星載圖像信息處理。Email：andrexu@163.com。

TP332.1

A

10.3969/j.issn.1673-8748.2015.06.013